Файл: Лекція 15 Дерева_рішень.doc

Дерева рішень|розв'язань,вирішень,розв'язувань| - загальні|спільні| принципи роботи Введення|вступ|

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

Термінологія

Введемо|запроваджуватимемо| основні поняття з|із| теорії дерев рішень|розв'язань,вирішень,розв'язувань|, які уживатимуться в цій і подальших|наступних| статтях.

Назва	Опис
Об'єкт	Приклад|зразок|, шаблон, спостереження
Атрибут	Ознака,, властивість
Мітка класу	Залежна змінна, цільова змінна, ознака визначальний клас об'єкту
Вузол	Внутрішній вузол дерева, вузол перевірки
Лист|аркуш|	Кінцевий|скінченний| вузол дерева, вузол рішення|розв'язання,вирішення,розв'язування|
Перевірка (test|)	Умова у вузлі

Що таке дерево рішень|розв'язань,вирішень,розв'язувань| і типи вирішуваних|рішати,розв'язати| завдань|задач|

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

Під правилом розуміється логічна конструкція, представлена|уявляти| у вигляді|виді| "якщо ... то ...".

Область застосування|вживання| дерева рішень|розв'язань,вирішень,розв'язувань| в даний час|нині| широка, але|та| всі завдання|задачі|, що вирішуються|рішають,розв'язав| цим апаратом можуть бути об'єднані|з'єднані| в наступні|слідуючі| три класи:

---

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

• Класифікація: Дерева рішень|розв'язань,вирішень,розв'язувань| відмінно|чудово| справляються із|із| завданнями|задачами|, тобто віднесення об'єктів до одного із заздалегідь|наперед| відомих класів. Цільова змінна повинна мати дискретні значення.

• Регресія: Якщо цільова змінна має безперервні значення, дерева рішень|розв'язань,вирішень,розв'язувань| дозволяють встановити залежність цільової змінної від незалежних(вхідних) змінних. Наприклад, до цього класу відносяться завдання|задачі| чисельного прогнозирования(прогнози|передбачення| значень цільовій змінній).

Етапи побудови|шикування| дерев рішень|розв'язань,вирішень,розв'язувань|

При побудові|шикуванні| дерев рішень|розв'язань,вирішень,розв'язувань| особлива увага приділяється наступним|слідуючим| питанням: вибору критерію атрибуту, по якому піде розбиття, зупинки навчання|вчення| і відсікання гілок. Розглянемо|розглядуватимемо| всі ці питання по порядку.

Правило розбиття. Яким чином слід вибрати ознаку?

Для побудови|шикування| дерева на кожному внутрішньому вузлі необхідно знайти таку умову (перевірку), яка б розбивала множину|безліч|, що асоціюється з|із| цим вузлом на підмножини. В якості перевірки повинен бути вибраний один з атрибутів. Загальне|спільне| правило для вибору атрибуту можна сформулювати таким чином: вибраний атрибут повинен розбити множину|безліч| так, щоб отримані|одержувати| у результаті підмножини складалися з об'єктів, що належать до одного класу, або були максимально наближені до цього, тобто кількість об'єктів з|із| інших класів ("домішок|нечистот|") в кожній з цих множин|безлічі| була якомога менше.

---

Правило зупинки. Розбивати далі вузол або відзначити його як лист|аркуш|?

На додаток до основного методу побудови|шикування| дерев рішень|розв'язань,вирішень,розв'язувань| були запропоновані наступні|слідуючі| правила:

• Використання статистичних методів для оцінки доцільності подальшого|дальшого| розбиття, так звана "рання зупинка" (prepruning|). В кінцевому результаті|зрештою| "рання зупинка" процесу побудови|шикування| приваблива в плані економії часу навчання|вчення|, але|та| тут доречно зробити одне важливе|поважне| застереження: цей підхід будує менш точні класифікаційні моделі і тому рання зупинка украй|надто| небажана. Визнані авторитети в цій області Л.Брейман і Р. Куїнлен радять буквально наступне|слідуюче|: "Замість зупинки використовуйте відсікання".

• Обмежити глибину дерева. Зупинити подальшу|дальшу| побудову|шикування|, якщо розбиття веде до дерева з|із| глибиною тієї, що перевищує задане значення.

• Розбиття повинне бути нетривіальним, тобто вузли, що вийшли в результаті, повинні містити|утримувати| не менше заданої кількості прикладів|зразків|.

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

Правило відсікання. Яким чином гілки дерева повинні відсікатися|відсікати|?

Дуже часто алгоритми побудови|шикування| дерев рішень|розв'язань,вирішень,розв'язувань| дають складні дерева, які "переповнені даними", мають багато вузлів і гілок. Такі "гіллясті" дерева дуже важко зрозуміти. До того ж гіллясте дерево, що має багато вузлів, розбиває повчальну множину|безліч| на все більшу кількість підмножин, що складаються зі все меншої кількості об'єктів.

Цінність правила, справедливого скажемо для 2-3 об'єктів, украй|надто| низка, і в цілях аналізу даних таке правило практично непридатно. Набагато переважно мати дерево, що складається з малої кількості вузлів, яким би відповідала велика кількість об'єктів з|із| повчальної вибірки.

Для вирішення вищеописаної проблеми часто застосовується так зване відсікання гілок (pruning|).

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

---

• побудувати|спорудити| дерево;

• відсікти або замінити поддеревом| ті гілки, які не приведуть до зростання помилки.

У відмінності|відзнаці| від процесу побудови|шикування|, відсікання гілок відбувається|походить| від низу до верху, рухаючись|сунути| з листя дерева, відзначаючи вузли як листя, або замінюючи їх поддеревом|. Хоча відсікання не є|з'являється,являється| панацеєю, але|та| в більшості практичних завдань|задач| дає добрі результати, що дозволяє говорити про правомірність використання подібної методики.

---

Переваги використання дерев рішень|розв'язань,вирішень,розв'язувань|

Розглянувши|розглядувати| основні проблеми, що виникають при побудові|шикуванні| дерев, було б несправедливо не згадати про їх достоїнства:

• швидкий процес навчання|вчення|;

• генерація правив в областях, де експертові важко формалізувати свої знання;

• витягання|видобування| правив на природній мові|язиці|;

• інтуїтивно зрозуміла класифікаційна модель;

• висока точність прогнозу, зіставна|порівнянна| з|із| іншими методами (статистика нейронные сети);

• побудова|шикування| непараметричних моделей.

Через цих і багатьох інших причин, методологія дерев рішень|розв'язань,вирішень,розв'язувань| є|з'являється,являється| важливим|поважним| інструментом в роботі кожного фахівця|спеціаліста|, що займається аналізом даних, незалежно від того практик він або теоретик.

Області застосування|вживання| дерев рішень|розв'язань,вирішень,розв'язувань|

Дерева рішень|розв'язань,вирішень,розв'язувань| є|з'являються,являються| прекрасним|чудовим| інструментом в системах підтримки ухвалення|прийняття,приймання| рішень, інтелектуального аналізу даних (data mining).

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

Дерева рішень|розв'язань,вирішень,розв'язувань| успішно застосовуються для вирішення практичних завдань|задач| в наступних|слідуючих| областях:

• Банківська справа|річ|. Оцінка кредитоспроможності клієнтів банку при видачі кредитів.

• Промисловість. Контроль за якістю продукції (виявлення дефектів), випробування без руйнувань (наприклад перевірка якості зварки|зварювання|) і так далі

• Медицина. Діагностика різних захворювань.

• Молекулярна біологія. Аналіз будови|споруди| амінокислот.

Це далеко не повний|цілковитий| список областей де можна використовувати дерева рішень|розв'язань,вирішень,розв'язувань|. Не досліджено ще багато потенційних областей застосування|вживання|.

---