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

 

 

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

 

 

 

 

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

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

 

 

 

 

 

 

 

Львів 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, хоча на цих рисунках зображено різні дерева. Щоб уникнути неоднозначності інфіксної форми, використовують круглі дужки щоразу, коли зустрічають операцію. Повністю «одужкований» вираз, отриманий під час обходу дерева у внутрішньому порядку, називають інфіксною формою запису.