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

Наведені міркування свідчать, що інфіксна форма запису виразів незручна. На практиці використовують префіксну та постфіксну форми запису, бо вони однозначно відповідають виразу і не потребують дужок. Ці форми запису називають польськими записами (на честь польського математика й логіка Яна Лукасевича, українця за походженням).

Приклад 1.8. Розглянемо логічний вираз . Послідовні етапи побудови подібного бінарного дерева зображено на рис. 1.14. Отримаємо такі форми запису виразу:

• інфіксна форма запису (відповідає обходу дерева виразу у внутрішньому порядку)

• польський запис (відповідає обходу дерева виразу в прямому порядку)

• зворротний польський запис (відповідає обходу дерева виразу в зворотному порядку)

              

Для обчислення значення виразу в польському записі його проглядають  справа наліво та знаходять два операнди разом зі знаком операції над ними. Ці операнди та знак операції вилучають із запису, виконують операцію, а її результат записують на місце вилучених символів.

Приклад 1.9. Обчислимо значення виразу в польському записі (стрілка означає піднесення до степеня )

+ - * 2 3 5 / 2 3 4

За сформульованим правилом виділимо 2 3, ці символи вилучимо й обчислимо 2 3 = 8, результат записуємо на місце вилучених символів:

+ - * 2 3 5 / 8 4; На наступному кроці отримаємо + - * 2 3 5 2. Далі + - 6 5 2, та +1 2. Результатом даного процесу буде число 3.

Для обчислення значення виразу в зворотному польському записі, його проглядають зліва направо та виділяють два операнди разом  зі знаком операції після них. Ці операнди та знак операції вилучають із запису, виконують операцію, а її результат записують на місце вилучених символів.

Приклад 1.10. Обчислимо значення виразу з зворотному польському записі

7 2 3 * - 4 9 3 / +.

Крок 1. 7 6 – 4 9 3 / +

Крок 2. 1 4 9 3 / +

Крок 3. 1 9 3 / +

Крок 4. 1 3 +

Крок 5. 4

Оскільки польські записи однозначні та їх значення можна обчислити  без сканування назад і вперед, їх широко використовують у комп'ютернних науках, особливо для конструювання  компіляторів.

4. Бінарне дерево пошуку

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

У бінарному дереві пошуку кожній вершині присвоєно значення, яке на-зивають ключем. Ключ – це елемент якоїсь лінійно впорядкованої множини: будь-які два її елементи можна порівняти.

Під час побудови бінарного  дерева пошуку використовують його рекур-сивну  властивість, яку можна описати  так. Кожна вершина розбиває дерево на два піддерева. Ліве піддерево  містить лише ключі, менші від  ключа цієї верши- ни, а праве –  ключі, більші від ключа вершини. Ця властивість повторюється для  кожної вершини.

Розглянемо алгоритм додавання об’єкта до дерева пошуку, який будує бінарне дерево пошуку. Почнемо з дерева, що містить лише одну вершину. Означимо її як корінь. Перший об’єкт списку присвоюємо кореню; це ключ кореня. Щоб додати новий об’єкт, виконуємо таку процедуру.

Алгоритм  додавання об’єкта до дерева

Наведемо кроки  алгоритму.

Крок 1. Почати з корення.

Крок 2. Якщо об’єкт менший, ніж ключ у вершині, то перейти до лівого сина.

Крок 3. Якщо об’єкт більший, ніж ключ у вершині, то перейти до правого сина.

Крок 4. Повторювати кроки 2 та 3, доки не досягнемо вершини, яку не визначено (тобто її немає).

Крок 5. Якщо досягнуто невизначену вершину, то визначити (тобто до- дати) вершину з новим об’єктом як ключем.

                             

                                           

Приклад 1.11. Побудуємо бінарне дерево пошуку для такого списку слів в українському алфавіті: математика, фізика, географія, зоологія, метеорологія, біологія, психологія, хімія. Процес побудови зображено на рис. 1.17.

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

Алгоритм  пошуку об’єкта в дереві

Наведемо кроки  алгоритму.

Крок 1. Почати з кореня.

Крок 2. Якщо об’єкт менший, ніж ключ у вершині, то перейти до лівого сина.

Крок 3. Якщо об’єкт більший, ніж ключ у вершині, то перейти до правого сина.

Крок 4. Якщо об’єкт дорівнює ключу у вершині, то об’єкт знайдено; виконати потрібні дії й вийти.

Крок 5. Повторювати кроки 2, 3 та 4, доки не досягнемо вершини, яку не визначено.

Крок 6. Якщо досягнуто невизначену вершину, то даний об’єкт не зберігається в дереві; виконати потрібні дії й вийти.

                       

Оцінимо обчислювальну  складність алгоритмів включення та пошуку (локалізації) об’єкта в бінарному  дереві пошуку. Припустимо, що є бінарне  дерево пошуку Т для списку з n об’єктів. Із дерева T утворимо повне бінарне дерево U, для чого додамо нові вершини (без ключів) так, щоб кожна вершина з ключем мала двох синів. Це показано на рис. 1.18, де вершини без ключів позначено подвійними кружечками.

        

Коли це зроблено, можна легко локалізувати об’єкт або додати новий об’єкт як ключ без додавання вершини. Найбільша кількість порівнянь, потрібних для додавання нового об’єкта, дорівнює довжині найдовшого шляху в U від кореня до листка, тобто висоті дерева. Внутрішні вершини дерева U – це (всі) вершини дерева T. Отже, дерево U має n внутрішніх вершин. За теоремою 1.2 кількість листків у ньому дорівнює 2n+1- n=n+1. Згідно з наслідком із теореми 1.3 висота дерева U більша чи дорівнює [log(n+1)]. Отже, потрібно щонайменше [log(n+1)] порівнянь, щоб додати чи локалізувати довільний об’єкт. Якщо дерево збалансоване, то його висота дорівнює [log(n+1)]. Отже, у цьому разі для додавання чи локалізації об’єкта потрібно не більше ніж [log(n+1)] порівнянь.

                     

Бінарне дерево пошуку може розбалансуватись унаслідок додавання  нових об’єктів, тому потрібен алгоритм ребалансування (тобто відновлення збалансованості). Проте процедура додавання об’єкта, яка відновлює дерево, навряд чи завжди доцільна, бо відновлення збалансованості дерева після випадкового додавання – досить складна операція.

Тому розглядають  також збалансованість із дещо послабленими вимогами; зокрема, означають АВЛ-дерево – бінарне дерево, у якому висоти двох піддерев кожної з його вершин відрізняються не більше ніж на одиницю. Таке означення збалансованості широко використовуються на практиці; його ввели 1962 р. Г.М. Адельсон-Вельський і Є.М. Ландіс. Приклад АВЛ – дерева наведено на рис. 1.19. Для АВЛ – дерев є дуже ефективна процедура ре балансування [7]. Водночас висота АВЛ – дерева незалежно від кількості вершин ніколи не перевищує висоту збалансованого дерева більше ніж на 45%. Якщо позначити висоту АВЛ – дерева з n вершинами як h(n). То log (n+1) ≤ h(n) < 1.44 log (n + +2)- 0.328.

 

5. Дерево рішень

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

Дерева рішень використовують техніку «поділяй і володарюй» для послідовного поділу простору пошуку (тут простір пошуку – це множина об'єктів, серед яких шукають потрібний). Це нагадує гру «Двадцять запитань», розглянуту в наведеному нижче прикладі.

Приклад 1.12. Нехай є два гравці й перший із них має задумати якийсь предмет чи особу, а другий – задавати запитання та за відповідями першого гравця вгадати, який предмет чи яку особу задумано. Для цього дозволено задати не більше ніж двадцять запитань. Нехай перше запитання таке: «Чи цей об'єкт – жива істота?». Залежно від відповіді буде задано наступне запитання. Якщо відповідь на перше запитання – «так», то другим запитанням може бути «Чи це людина?». У разі відповіді «так» можна запитати «Чи це хтось із моїх друзів?». Якщо відповідь «ні», то наспупним запитанням може бути таке: «Чи ця людина – член моєї родини?». Після відповіді «так» можна називати імена членів родини. Зменшуючи в такий спосіб кількість об'єктів, ми зменшуємо простір пошуку і, зрештою, можемо визначити, хто чи що було задумано. Хід гри проілюстровано деревом, наведеним на рис. 1.20.

Це жива істота?

       ні             так

 

                        Це людина?

 ні            так

 

                                          Це мій друг?

                                          ні                 так

                                      Це член родини?

ні              так

 

                                                     Рис. 1.20.

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

Бінарне дерево пошуку – частковий випадок дерева рішень. Зазначимо, що дерево рішень – не обов'язково бінарне.

Приклад 1.13. Серед восьми монет є одна фальшива, вона має меншу вагу. Потрібно знайти цю монету послідовністю зважувань на балансових терезах. Під час кожного зважування на балансових терезах є три можливі відповіді на запитання «Яка чаша важча?», а саме, чаші мають однакову вагу, перша чаша легша або друга чаша легша. Отже, дерево рішень для послідовності зважувань 3-арне. Це дерево має щонайменше вісім листків, бо є вісім можливих варіантів розв'язку (кожна з восьми наявних монет може бути фальшивою). Найменша кількість зважувань, необхідних для виявлення фальшивої монети, дорівнює висоті дерева рішень. Із наслідку з теореми 1.3 випливає, що висота дерева рішень складає щонайменше = 2. Отже, потрібно не менше двох зважувань. У цьому прикладі фальшиву монету можна виявити, використавши два зважування. Розв'язок подано на рис. 1.21. Занумеруємо монети числами 1, 2,…,8. Розділимо монети на три групи: першу групу складуть монети з номерами 1, 2, 3, другу – монети з номерами 4, 5, 6, а третю – монети з номерами 7 та 8. Порівнюємо вагу монет першої й другої груп. Якщо одна із цих груп виявиться легшою, то це означає, що фальшива монета є в цій групі, і її можна виявити другим зважуванням. У разі балансу терезів фальшива одна з монет третьої групи, що також можна виявити другим зважуванням. Кількість зважувань дорівнює висоті дерева, тобто двом.

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

Об'єкти, що підлягають класифікації, характеризуються множиною властивостей А = {a_1,a₂,…a_m}. Кожна властивість a є A має множину значень, позначимо її як V_a. Наприклад, якщо об'єкти – це дні, то властивостями можуть бути Погода, Температура, Вологість, Вітер. Значення властивості Погода – «Сонце», «Хмари», «Дощ». Значення властивості Температура – «Спека», «Помірно» та «Холод». Значення властивості Вологість – «Норма» та «Висока». Значення властивості Вітер – «Слабкий» та «Сильний». Об'єкти різняться значеннями властивостей, ці значення записують у рядки таблиці. Кожен її рядок описує один об'єкт і являє собою кортеж значень його властивостей. Інакше кажучи, об'єкт задано кортежем значень його властивостей. Множина об'єктів, які потрібно класифікувати, утворює простір пошуку. Дерево рішень розбиває цей простір на класи, віднесення об'єкту до певного класу виконується приписуванням цьому об'єкту певної мітки (мітки класу).

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

Задано множину  об'єктів D = {D₁,D₂,…,D_n}, кожний елемент якої – кортеж D_i= {d_i1,d_i2,…,d_im}. Елементи кортежу D_i являють собою, відповідно, значення властивостей a₁,a₂,…,a_m. Окрім того, задано множину міток класів C = {c₁,c₂,..,c_k}. Дерево рішень або класифікаційне дерево – це кореневе дерево, асоційоване з множиною D, яке задовольняє такі умови:

• Кожну внутрішню вершину позначено символом властивості a_i.
• Кожне ребро позначено значенням властивості, асоційованої з вершиною, із якої це ребро виходить.
• Кожний листок позначено міткою класу c_j.

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

Розв'язування проблеми класифікації з використанням дерева рішень – процес, що складається з двох етапів.