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

1. Побудувати дерево рішень з використанням тренувальних даних.
2. Для кожного D_i є D визначити, до якого класу належить об'єкт.

Існує багато алгоритмів побудови дерев рішень. Усі ці алгоритми – рекурсивні та будують дерево рішень від кореня. Наведемо найпростіший алгоритм побудови дерев рішень – алгоритм ID3, який запропоновано 1986 р. Дж. Куїнланом.

Параметри рекурсивного алгоритму ID3(D,C,A) мають такий зміст:

• D – множина кортежів із значеннями властивостей відповідних об'єктів.
• C = {c₁,c₂,..,c_k}– множина міток класів.
• A = { a₁,a₂,…,a_m } – множина властивостей.

Будемо використовувати  також такі позначення:

• D (a = v) – множина об'єктів, для яких значення властивості a дорівнює v (очевидно, D (a = v) D )
• V_a – множина значень властивості a.

Алгоритм  побудови дерева рішень – ID3 (D,C,A)

• Утворити кореневу вершину R
• Якщо всі кортежі з множини D мають однакові мітки c є C, то R – листок, позначити його міткою c.
• Інакше якщо A = , то R – листок, позначити його міткою, яка найчастіше зустрічається серед міток кортежів із множини D.
• Інакше початок
• Вибрати властивість a є A та позначити вершину R символом цієї властивості
• Для кожного значення v є V_a виконати
• Додати нове ребро до кореневої вершини R
• Побудувати множину D (a = v)
• Якщо D (a = v) = , то кінець доданого ребра – листок, позначити його міткою, що найчастіше зустрічається серед міток кортежів із множини D.
• Інакше в кінцевій вершині доданого ребра побудувати дерево за допомогою ID3 (D (a = v), C, A \ {a})

Кінець

• Повернути кореневу вершину R

Алгоритм ID3(D,C,A) утворює та повертає вершину R дерева, яка може бути або листком, або коренем нового піддерева. Якщо ця вершина – листок, то алгоритм позначає її міткою c (c є C). Якщо ж вона – корінь нового піддерева, то алгоритм позначає цю вершину символом властивості a (a є A). Алгоритм завершує роботу тоді, коли всі листки будованого дерева одержать мітки класів (у такому разі нових звертань до алгоритму вже не буде).

Приклад 1.14. У табл 1.1 наведено результати участі певного гравця в тенісних турнірах та погодні умови під час проведення змагань. Результати змагань – це мітки класів («так» - виграш, «ні» - програш). Імена об'єктів містяться в стовпці Об'єкти. Множина властивостей A = {Погода, Температура, Вологість, Вітер}, значення кожної властивості містяться у відповідному стовпці. Наприклад, об'єкт D₁ характеризується таким кортежем значень властивостей: D₁ = (Сонце, Спека, Висока, Слабкий ), цей об'єкт позначено міткою «ні». На основі даних про тринадцять ігор (тренувальні дані) треба побудувати дерево рішень і прогнозувати результат чотирнадцятої гри, тобто присвоїти об'єкту D₁₄ одну із двох міток «так» або «ні». Дерево рішень побудуємо, застосувавши алгоритм ID3.

Під час першого звертання алгоритм утворює кореневу вершину дерева рішень, вибирає властивість із усієї множини властивостей A = {Погода, Температура, Вологість, Вітер}. Нехай перша вибрана властивість – Погода, символом цієї властивості буде позначено корінь. Усі можливі значення властивості Погода – «Сонце», «Хмари» та «Дощ», тому для цієї вершини утворимо три ребра, яким припишемо вказані значення. Тепер множину об'єктів розіб'ємо на три підмножини за значеннями властивості Погода (рис 1.22), вилучимо цю властивість із множини А та отримаємо зменшену множину властивостей А = {Температура, Вологість, Вітер}, яку розгядатимемо під час наступного звертання до алгоритму.

У вершині 2 на рис. 1.22 об'єкти {D₉,D₁₁} мають значення «так» результату гри, а об'єкти {D₁,D₂,D₈} – значення «ні». Отже, ця вершина – не листок, тому зі зменшеної множини властивостей А виберемо властивість, нехай нею буде Температура, якою позначимо вершину 2. Побудуємо ребра зі значеннямми Температури («Спека», «Помірно» та «Холод») і розіб'ємо множину об'єктів у вершині 2 на три підмножини так, щоб усі об'єкти в кожній з них мали однакове значення цієї властивості.

 

У вершині 5 з рис. 1.23 усі  об'єкти (D₁ та D₂)мають значення «ні» результату гри. Тому вершина 5 – листок, його позначимо міткою «ні». Вершині 7 відповідає лише один об'єкт (D₉)зі значенням «так» результату гри, тому вершина 7 – листок, який позначимо міткою «так». Вершині 6 відповідають об'єкти  D₈ і D₁₁, вони мають різні значення результатів гри, тому у вершині 6 потрібно будувати – корінь піддерева, яке будуватиметься при рекурсивному  звертанні до алгоритму для побудови дерева у вершині 6. Властивість Вологість має два значення: «Норма» та «Висока».

                  

На рис 1.24 об'єктам D₁₁ та D₈ відповідають листки, які, відповідно, одержать позначки «так» і «ні». Вилучаємо властивість Вологість, отже, А = {Вітер}.

        

         

Усі об'єкти, що розглядаємо  у вершині 3 з рис. 1.22, мають значення «так» результатів гри. Отже, вершина 3 – листок, його позначимо «так». У вершині 4 з рис 1.22, об'єкти мають різні значення результатів гри. Тому виберемо для цієї вершини властівість Вітер (єдина, що залишилася) із двома значеннями – «Слабкий» і «Сильний». Цими значеннями позначимо ребра, які утворимо у вершині 4. Множину об'єктів розіб'ємо на підмножини {D₄,D₅,D₁₀} зі значеннями результатів гри «так» та {D₆} – зі значеннями «ні». Позаяк усі листки одержали одержали мітки класів, то виконання закінчене. Дерево рішень подано на рис. 1.25. Користуючись цим деревом, можна прогнозувати результат гри для чотирнадцятого рядка таблиці (програш). Розгляд прикладу зверешено.

     

Приклад 1.15. Використовуючи дані з прикладу 1.14, можна побудувати інше дерево рішень, якщо властивості вибирати в іншій послідовності. Таке дерево зображено на рис. 1.26. Воно має менше вершин – відсутня властивість Температура – та меншу висоту.

Порівняння прикладів 1.14 та 1.15 показує вплив послідовності, за якою вибирались властивості, на висоту дерева рішень.

Простий спосіб здійснити  класифікацію об'єктів – це побудувати на основі дерева рішень правила вигляду ЯКЩО – ТО. Кількість таких правил дорівнює кількості листків дерева. Правила формують на шляхах від кореня до кожного листка дерева. Кожне правило має вигляд

ЯКЩО умова ТО рішення,

де умова – це кон'юнкція речень вигляду (значення властивості = v), а рішення – це речення вигляду (мітка класу = c).

Приклад 1.16. Наведемо правила, побудовані на основі цього дерева рішень, зображеного на рис 1.26.

Якщо (погода = сонце) ^ (вологість = висока) ТО (клас = ні);

Якщо (погода = сонце) ^ (вологість = норма) ТО (клас = так);

Якщо (погода = хмари)  ТО (клас = так);

Якщо (погода = дощ) ^ (вітер = слабкий) ТО (клас = так);

Якщо (погода = дощ) ^ (вітер = сильний) ТО (клас = ні);

За допомогою цих правил дістаємо прогноз для чотирнадцятого рядка таблиці 1.1. Оскільки (погода = дощ) і (вітер = сильний), то (клас = ні), тобто прогноз гри – програш.

Існує багато різних алгоритмів побудови дерев рішень. Зокрема широко застосовують у задачах прийняття рішень алгоритми C4.5, See5, CART, SPRINT та інші. Ці алгоритми відрізняються від ID3 тим, що в них інакше виконується вибір властивості для позначення внутрішньої вершини, побудова ребер, приписування класів листкам, тощо. Окрім того, у ці алгоритми вводять певні обчислення для оптимізації висоти дерева.

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

 

6. Бектрекінг (пошук із поверненням)

Опишемо загальний  метод, який дає змогу значно зменшити обсяг обчислень в алгоритмах типу повного перебору всіх можливостей. Щоб застосувати цей метод, розв’язок задачі повинен мати вигляд скінченної послідовності (x₁, …, x_n). Головна ідея методу полягає в тому, що розв’язок будують поступово, починаючи з з порожньої послідовності λ (довжиною ). Загалом, якщо є частковий (неповний) розв’язок (x₁, …, x_i), де i<n, то намагаємося знайти таке допустиме значення x_i+1, що можна продовжувати (x₁, …, x_i,x_i+1) до одержання повного розв’язку. Якщо таке допустиме, але ще не використане значення x_i+1 існує, то долучаємо цю нову компоненту до часткового розв’язку та продовжуємо процес для послідовності (x₁, …, x_i,x_i+1). Якщо такого значення x_i+1 немає, то повертаємося до попередньої послідовності (x₁, …, x_i+1) і продовжуємо процес, шукаючи нове, іще не викостане значення . Тому процес називають бектрекінгом (англ… backtracking – пошук із поверненнями).

Роботу цього  алгоритму можна інтерпретувати як процес обходу певного дерева. Кожна його вершина відповідає якійсь послідовності (x₁, …, x_i), причому вершини, які відповідають послідовностям вигляду (x₁, …, x_i, y), - си-ни цієї вершини.Корінь дерева відповідає порожній послідовності.

Виконується обхід  цього дерева пошуком углиб. Окрім  того, задають предикат P, означений на всіх вершинах дерева. Якщо P (v) = F процес обходу відкидає розгляд вершин піддерева з коренем у вершині v, зменшуючи тим самим обсяг перебору. Сам предикат P (v) набуває значення F тоді, коли стає зрозумілим, що послідовність (x₁, …, x_i), яка відповідає вершині v, ніяким способом не можна добудувати до повного розв’язку.

Проілюструємо застосування алгоритму бектрекінг на конкретних прикладах.

Приклад 1.17. Побудова гамільтонових циклів у графі [23]. Починаємо з довільної вершини. Будуємо шлях без повторення вершин, доки це можливо. Якщо вдалося пройти всі вершини то перевіряємо, чи існує ребро, що з’єднує останню й початкову вершини цього шляху. Якщо описаний процес у певний момент неможливо продовжити, то повертаємося на одну вершину назад, і на-магаємося продовжити будову шляху (без повторення вершин) іншим способом.

                                     

Пошук усіх гамільтонових  циклів у графі з п’ятьма вершинами (рис. 1.27) то можна проілюструвати за допомогою дерева, зображеного на рис 1.28. роботу алгоритму почато з одноелементної послідовності, бо в циклі вибір першої вершини неістотний. Розв’язки задачі обведено, і до них у прямокут-них рамках приписано відповідні гамільтонові цикли.

      

Отже, замість  побудови та аналізу 5!=120 послідовностей довжиною 5. Елементами котрих є вершини  графа на рис. 1.27, ми розглянули всього 23 послідовності довжиною від 1 до 5.

Приклад 1.18. Розфарбування графа в n кольорів [52]. Нехай вершини графа позначено як a, b, c,…Спочатку розфарбуємо вершину a в колір 1. Після цього розфарбуємо вершину b  в колір 1, якщо b не суміжна з вершиною a, а ні, то розфарбуємо вершину b в колір 2. Перейдемо до третьої вершини c. Використаємо для вершини c колір 1, якщо це можливо, а ні, то колір 2, якщо це можливо. Тільки якщо жоден із кольорів 1 і 2 не можна використати, розфарбуємо вершину c в колір 3. Продовжуємо цей процес, доки це можливо, використовуючи один з n кольорів для кожної нової вершини, причому завжди братимемо перший можливий колір зі списку кольорів. Досягнувши вершини, яку не можна розфарбувати в жоден з n кольорів, повертаємося до останньої розфарбованої вершини, відміняємо її колір і розфарбовуємо в наступний можливий колір зі списку. Якщо й це неможливо, то повертаємось іще до попередньої вершини , відміняємо її колір і намагаємося розфарбувати в новий колір, наступний можливий зі списку. Цей процес продовжуємо аналогічно. Якщо розфарбування в n кольорів існує, то така процедура дає змогу знайти його. На рис. 1.29 зображено граф і процес розфарбування в три кольори його вершин із використанням алгоритму бектрекінг.

               

Приклад 1.19. Задача про n ферзів [7, 52]. Як n ферзів можна розмістити на шахівниці n×n так, щоб жодні два не били один одного? Для розв’язання цієї задачі потрібно визначити n позицій на шахівниці так, щоб жодні дві позиції не були в одному рядку, в доному стовпці та на одній діагоналі. Діагональ містить усі позиції з координатами (i,j) такі, що i+j=m для якогось m, або i-j=m(тут I– номер рядка, j – номер стовпця , m – ціле число). Починаємо з порожньої шахівниці. На (k+1)-му кроці намагаємось розмістити нового ферзя в (k+1)-му стовпці, причому в перших k стовпцях уже є ферзі. Перевіряємо клітинки в (k+1)-му стовпці, починаючи з верхньої. А саме, шукаємо таку позицію для ферзя, щоб він не був у рядку та на діагоналі з тими ферзями, які вже є на шахівниці. Якщо це неможливо, то повертаємося до місця ферзя на попередньому k-му кроці та розміщаємо цього ферзя на наступному можливому рядку в цьому k-му стовпці, якщо такий рядок є, а ні, то повертаємось до ферзя в (k-1)-му стовпці. Алгоритм бектрекінг для n=4 проілюстровано на рис. 1.30.