Дерева рішень та задачі класифікації

Зазначимо, що у  кожній вершині дерева на рис. 1.30 відповідає послідовність довжиною від 0 до 4. У  неї k-й член дорівнює номеру клітинки з ферзем у k-му стовпці. Наприклад, вершинам шляху на рис. 1.30, який веде до успішного результату, відповідають такі послідовності: λ, (2), (2,4), (2,4,1), (2,4,1,3).

Приклад 1.20. Суми елементів підмножин [52]. Задано множину натуральних чисел {x₁, x₂, …, x_n}. Потрібно знайти її підмножину, сума елементів якої дорівнює заданому числу М.

Починаємо з порожньої  множини. Нагромаджуємо суму, послідовно добираючи доданки. Число з послідовності  x₁, x₂,…,x_n долучають до суми, якщо сума після додавання цього числа не перевищує M. Якщо сума настільки велика, що додавання будь-якого нового числа перевищує М, то повертаємось і змінюємо останній доданок у сумі. На рис. 1.33 проілюстровано алгоритм бектрекінг для задачі відшукання підмножин множини {31, 27, 11, 7, 5} із сумою 39.

Приклад 1.21. Побудова всіх максимальних незалежних множин вершин у простому графі G=(V,Г) [20,35]. Тут граф подано як пару, утворену множиною вершин V та відповідністю Г, котра показує, як зв’язані між собою вершини (див. підрозділ 1.3). Почнемо з порожньої множини й будемо додавати до них вершини зі збереженням незалежності. Нехай S_k – уже отримана множина з k вершин, Q_k – множина вершин, котрі можна додати до S_k, тобто Серед вершин Q_k  розрізняють ті, котрі вже було використано для розширення S_k (їх позначають Q_k^-), і ті, котрі ще не використано (їх позначають Q⁺_k). Загальна схема алгоритму бектрекінг для задачі побудови максимальних незалежних множин вершин у простому графі має такий вигляд.

Прямий крок від k до k+1 полягає у виборі вершини :

_{Крок  повернення від  k+1 до k:}

Якщо множина вершини S_k максимальна, то . Якщо , то множину S_k було розширено раніше, і вона не максимальна. Отже, перевірку максимальності задають такою умовою: .

Тут, як і завжди, доцільно намагатися почати кроки повернення якомога раніше, бо це обмежить розміри «непотрібної» частини дерева пошуку. У зв'язку з цим зауважимо таке. Нехай v є та . Цю вершину ніколи не вилучити з , оскільки з вилучають тільки вершини, суміжні з вершинами множини . Отже існування такої вершини v, що v є Q_k і - достатня умова для повернення. Окрім того, k ≤ n-1.

Алгоритм  побудови всіх максимальних незалежних множин вершин у простому графі G = (V,Г)

Крок 1. Ініціалізація. Виконати S₀:= , , , k=0.

Крок 2. Прямий крок. Вибрати вершину  x є і сформувати, як описано вище, множини , при цьому залишити та без змін. Виконати k:= k+1.

Крок 3. Перевірка. Якщо існує така вершина v, що v є і , то перейти до кроку 5, інакше перейти до кроку 4.

Крок 4. Якщо , то надрукувати максимальну незалежну множину S_k та перейти до кроку 5. Якщо , а то перейти до кроку 5, інакше перейти до кроку 2.

Крок 5. Крок повернення. Виконати k:=k-1. Вилучити вершину x із S_k+1, щоб одержати S_k. Виправити та , для чого вилучити вершину x із множини і долучити її до . Якщо k=0 та , то зупинитися (на цей момент уже буде надруковано всі максимальні незалежні множини). Інакше перейти до кроку 3.

Унаслідок зв'язку між кліками й незалежними множинами цей алгоритм можна використовувати також і для побудови максимальних клік.

7. Висновок

Отже, у цій роботі описані  основні означення дерев рішень, алгоритми обходу дерев рішень, префіксні  та постфіксні форми запису виразів, бінарне дерево пошуку, розглянувся  алгоритм побудови дерева рішень ID3, який був реалізований на прикладі, для кращого його розуміння. Також було звернуто увагу на бектрекінг(пошук із поверненням), та декілька видів задач, які мають відношення до дерев рішень.

Можна сказати, що дерево рішень — це кореневе дерево, у якому кожну внутрішню вершину позначено запитанням. Ребра, які виходять з кожної такої вершини, подають можливі відповіді на запитання, асоційоване з цією вершиною. Кожний листок являє собою прогноз розв’язку розглядуваної проблеми. Дерево рішень часто використовують для класифікації об’єктів. У такому разі кожна внутрішня вершина дерева рішень асоційована з якоюсь властивістю, що характеризує об’єкти, а кожному можливому значенню цієї властивості відповідає піддерево. Листки відображають результати класифікації.  Алгоритм побудови дерева рішень – один із найважливіших засобів індуктивного відновлення правил за даними, який забезпечує автоматичну побудову баз знань діагностичних експертних систем.

За допомогою дерев  рішень можна визначати, наприклад,  оцінку ризику підприємницької фірми, або спрогнозувати результат  будь – яких спортивних матчів. Метод  дерева рішень застосовують на практиці також у ситуаціях, коли результати одного рішення впливають на подальші рішення, тобто, як говорять, для прийняття  послідовних рішень.

Тобто, роблячи підсумок, можна із впевненістю сказати, що дерева рішень та задачі класифікації займають досить важливе місце у  науці, та у різних галузях комп’ютерних технологій.

8. Список використаної літератури
1. Дискретна математика: Підручник. – Львів: «Магнолія - 2006», 2010. – 432 с.
2. Методы и модели анализа даних: OLAP и Data Mining. – СПб.:БХВ-Петербург, 2004. – 336с.: ил.
3. Мошков М. Ю. Деревья решений. Теория и приложения. – Нижний Новгород: Нижегород. ун-т, 1994. – 175 с.