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

 

 

Міністерство освіти і  науки, молоді та спорту України

 

 

 

 

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

Курсова робота

 

 

 

 

 

 

 

Львів 2012

 

 

 

 

 

 

 

 

 

 

 

 

Зміст

 

1. Вступ……………………………….……………………………………….…….3

 

2. Основні означення та властивості….…………………………………………..4

 

3. Рекурсія. Обхід дерев. Префіксна та постфіксна форми запису виразів….….8

 

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

 

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

 

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

 

7. Висновок………………………………………………………………………….37

 

8. Список викоританої  літератури……………………………………………….38

 

 

 

 

 

 

 

 

 

 

 

1. Вступ

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

Метод дерева рішень - це один з методів автоматичного аналізу величезних масивів даних. Перші ідеї створення "дерев рішень" починаються з робіт П.Ховленда і Е.Ханта кінця 50-х років XX століття. Проте основоположною роботою, що дала імпульс для розвитку цього напряму, стала книга Е.Ханта, Дж.Мерина і П.Стоуна "Experiments in Induction", яку було опубліковано в 1966 р.

Область використання методу "дерева рішень" можна об'єднати в три класи:

опис даних: застосування "дерева рішень" дозволяє зберігати інформацію про вибірку даних в компактній і зручній для обробки формі, що містить в собі точні описи об'єктів;

класифікація: застосування "дерева рішень" дозволяє справитися із завданнями класифікації, тобто відношення об'єктів до одного з описаних класів;

регресія: якщо змінна має недостовірні значення, то застосування "дерева рішень" дозволяє визначити залежність цієї цільової змінної від незалежних (вхідних) змінних.

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

 

2. Основні означення та властивості.

Деревом називають зв’язний граф без простих циклів. Граф, який не містить простих циклів і складається з k компонент, називають лісом із k дерев.

Приклад 1.1.На рис 1.1 зображено приклади дерев. Граф, який зображено на рис 1.2 – не дерево, бо він незв’язний.

Зауваження. З означення випливає, що дерева й ліси являють собою прості графи.

 

                                     

Теорема 1.1. Нехай граф Т має nвершин. Тоді такі твердження еквівалентні:

1. Граф Т – дерево.
2. Граф Т не містить простих циклів і має (n-1) ребро;
3. Граф Т зв’язний і має (n-1) ребро;
4. Граф Т зв’язний, але вилучення довільного ребра робить його незв’язним;
5. Довільні дві вершини графа Т з’єднані точно одним простим шляхом;
6. Граф Т не містить простих циклів, але, додавши до нього довільне нове ребро(без додавання вершин), ми отримаємо точно один простий цикл.

Наслідок. Ліс із k дерев, який містить n вершин, має (n-k) ребер.

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

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

 

Приклад 1.2. На рис. 1.3, а зображено дерево, а на рис 1.3, б, в – кореневі дерева  з коренями відповідно у вершинах а та с.

Нехай Т – кореневе дерево . Якщо v– його вершина, відмінна від кореня, то батько v – це єдина вершина u така, що є орієнтоване ребро (u,v). Якщо u –батько, то v – син. Аналогічно за генеалогічною термінологією можна означити інших предків і нащадків вершини v. Вершини дерева, які не мають синів, називають листками. Вершини, які мають синів, називають внутрішніми. Зазначимо, що корінь належить до внутрішніх вершин.

Якщо а – вершина дерева, то піддерево з коренем а – це підграф, що містить а та всі вершини – нащадки вершини а, а також інцидентні їм ребра.

Кореневе дерево називають m-арним, якщо кожна його внутрішня вершина має не більше ніж m синів. Дерево називають повним m – арним, якщо його внутрішня вершина має точно m синів. У разі m = 2 дерево називають бінарним.

Упорядковане  кореневе дерево – це кореневе дерево, у якому сини кожної внутрішньої вершини упорядковано. На рисунку таке дерево зображають так, щоб сини кожної вершини були розміщені зліва направо.

Якщо внутрішня вершина  впорядкованого бінарного дерева має  двох синів, то першого називають лівим сином , а другого – правим. Піддерево з коренем у вершині, яка являє собою лівого сина вершини v, називають лівим піддеревом у вершині v. Якщо корінь піддерева – правий син вершини v, то таке піддерево називають правим піддеревом  у вершині v.

 

                             

Приклад 1.3. У дереві, зображеному на рис 1.4,  Л і П – відповідно ліве та праве піддерева у вершині c.

Теорема 1.2. Повне m – арне дерево із i внутрішніми вершинами містить n = mi + 1 вершин.

Приклад 1.4. На рис 1.5 зображено збалансоване бінарне дерево , яке має висоту 4; усі його листки на рівнях 3 або 4.

              

Теорема 1.3.Нехай m-арне дерево має висоту h. Тоді в ньому не більше ніж листків.

Доведення. Застосуємо математичну індукцію за h. У разі h = 1 твердження очевидне. Припустимо, що воно справджується для всіх m-арних дерев із меншою висотою, ніж h. Нехай Т – m-арне дерево з висотою h. Листки дерева Т – це листки піддерев, які отримують з Т вилученням ребер, що з'єднують корінь дерева Т із кожною вершиною рівня 1 (рис 1.6). Кожне із цих піддерев має не більшу висоту, ніж h-1. За індуктивною гіпотезою кожне з них має не більше ніж листків. Позаяк таких піддерев не більше ніж m, то загальна кількість листків у дереві Т не перевищує m* = . Теорему доведено.

                  

Наслідок. Якщо m-арне дерево з висотою h має l листків, то h . Якщо m- арне повне та збалансоване, то h= .

3. Рекурсія. Обхід дерев. Префіксна та постфіксна форми запису виразів

Об’єкт називають рекурсивним, якщо він містить сам себе, або означений за допомогою самого себе. Рекурсія – потужний засіб у математичних означеннях.

Приклад 1.5. У підрозділі 1.1 сформульовано означення повного бінарного дерева. Тепер означимо його рекурсивно:

а) о (ізольована вершина) – повне бінарне дерево;

б) якщо А та В – повні бінарні дерева, то конструкція, зображена на рис 1.7, - повне бінарне дерево.

                                     

Приклад 1.6. Рекурсивне означення функції n! для невід'ємних цілих чисел має такий вигляд:

а) 0! = 1;

б) якщо n>0, то n! = n(n-1)!

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

Чимало задач можна  моделювати з використанням кореневих  дерев. Поширене таке загальне формулювання задачі: виконати задану операцію обробити з кожною вершиною дерева. Тут обробити – параметр загальнішої задачі відвідування всіх вершин, або так званого обходу дерева. Розглядаючи розв'язування цієї задачі як єдиний послідовний процес відвідування вершини дерева в певному порядку, можна вважати їх розміщеними одна за одною. Опис багатьох алгоритмів істотно спрощується, якщо можна говорити про наступну вершину дерева, маючи на увазі якесь упорядкування. Є три принципи впорядкування вершин, які природно випливають зі структури дерева. Як і саму деревоподібну структуру, їх зручно формулювати за допомогою рекурсії.

Звертаючись до бінарного  дерева, де R–корінь, А та В – ліве та праве піддерева, можна означити такі впорядкування.

1. Обхід упрямому порядку(preorder) або зверху вниз: R, А, В (корінь відвідують до обходу піддерев);
2. Обхід у внутрішному порядку (inorder) або зліва направо: А, R, В;
3. Обхід у зворотному порядку (postorder) або знизу вверх А, В, R (тобто корінь відвідують після обходу піддерев).

Нижче наведено рекурсивні алгоритми обходу бінарних дерев. У кожному способі обходу використано команду обробити (v) , де v – вершина. Цей термін залишено невизначеним, бо його значення залежить від того, що ми хочемо зробити під час проходження вершин. Для наших цілей достатньо використати звичайну команду друку символу.

Алгоритм обходу в прямому порядку позначено як ОПП (х), у внутрішньому – як ОВП (х) і зворотному – як ОЗП (х). У всіх трьох алгоритмах х – це корінь дерева, яке обходять. Лівого сина вершини v позначено як лс (v), а правого – як пс (v).

Алгоритм обходу дерева в прямому порядку –  ОПП(корінь)

• Обробити (корінь)
• Якщо лс (корінь) існує, то ОПП (лс(корінь))
• Якщо пс (корінь) існує, то ОПП (пс(корінь))

Алгоритм обходу дерева у внутрішньому порядку – ОВП(корінь)

• Якщо лс (корінь) існує, то ОВП (лс(корінь))
• Обробити (корінь)
• Якщо пс (корінь) існує, то ОВП (пс(корінь))

Алгоритм обходу дерева у зворотному порядку – ОЗП(корінь)

• Якщо лс (корінь) існує, тоОЗП (лс(корінь))
• Якщо пс (корінь) існує, то ОЗП (пс(корінь))
• Обробити (корінь)

               

Приклад 1.7. На рис. 1.8 зображено бінарне дерево. Різні обходи дадуть такі послідовності вершин:

• Обхід у прямому порядку: abdehocfmpq;
• Обхід у внутрішньому порядку: dbheoafcpmq;
• Обхід у зворотному порядку: dhoebfpqmca;

Зазначені способи обходу бінарних дерев можна узагальнити  й на довільні m-арні дерева. Обхід таких дерев у прямому порядку (зверху вниз) схематично зображено на рис 1.9, у внутрішньому порядку (зліва направо) – на рис. 1.10, у зворотному (знизу вверх) – на рис 1.11.

                      

                          

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

Подамо його у вигляді  дерева. Послідовність дій відтворено на рис. 1.12. Рамкою на ньому обведено дерево, яке відповідає заданому арифметичному виразу. Внутрішнім вершинам цього дерева відповідають символи операцій, а листкам – операнди.

                  

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

• у разі обходу у прямому порядку – префіксний або польський запис:

* + a / b c – d * e f.

• уразі обходу у внутрішньому порядку – інфіксний запис (поки що без дужок, потрібних для визначення операцій):

a + b / c * d – e * f

• уразі обходу в зворотному порядку – постфіксний або зворотний польський запис:

abc / + def * - *.

                          

Звернімося спочатку до інфіксної  форми запису виразу. Без дужок  вона неоднозначна: один запис може відповідати різним деревам. Наприклад, дереву, зображеному на рис 1.13, у разі обходу зліва направо відповідає той самий вираз a + b / c * d – e * f, що й дереву на рис 1.12, хоча на цих рисунках зображено різні дерева. Щоб уникнути неоднозначності інфіксної форми, використовують круглі дужки щоразу, коли зустрічають операцію. Повністю «одужкований» вираз, отриманий під час обходу дерева у внутрішньому порядку, називають інфіксною формою запису.

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

Приклад 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.

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

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