Метод дерев рішень

Размещено на http://www.allbest.ru/

Зміст

Вступ

Розділ 1. Метод дерев рішень

Розділ 2. Процес конструювання дерев рішень

Розділ 3. Алгоритми, що реалізують дерева рішень

Розділ 4. Приклад побудови дерев рішень

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



Вступ

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

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

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

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

Розділ 1. Метод дерев рішень

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

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

Метод дерева рішень ? це один з методів автоматичного аналізу величезних масивів даних.

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

Для подальшого розуміння введемо основні терміни з теорії дерев рішень:

Назва Опис

Об'єкт Приклад, шаблон, спостереження

Атрибут Ознака, незалежна змінна, властивість

Мітка класу Залежна змінна, цільова змінна, ознака визначає клас об'єкта

Вузол Внутрішній вузол дерева, вузол перевірки

Лист Кінцевий вузол дерева, вузол рішення

Перевірка (test) Умова у вузлі

Структура дерева містить такі елементи: «листя» і «гілки». На ребрах («гілках») дерева прийняття рішення записані атрибути, від яких залежить цільова функція, в «листі» записані значення цільової функції, а в інших вузлах -- атрибути, за якими розрізняються випадки. Щоб класифікувати новий випадок, треба спуститися по дереву до листа і видати відповідне значення. Подібні дерева рішень широко використовуються в інтелектуальному аналізі даних.

Мал. 1 Схема побудови дерева рішень

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

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

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

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

Кожен лист являє собою значення цільової змінної, зміненої в ході руху від кореня по аркушу. Кожен внутрішній вузол відповідає одній з вхідних змінних. Дерево може бути також «вивчено» поділом вихідних наборів змінних на підмножини, що засновані на тестуванні значень атрибутів. Це процес, який повторюється на кожному з отриманих підмножин. Рекурсія завершується тоді, коли підмножина в вузлі має ті ж значення цільової змінної, таким чином, воно не додає цінності для пророкувань. Процес, що йде «згори донизу», індукція дерев рішень (TDIDT), є прикладом поглинаючого «жадібного» алгоритму, і на сьогоднішній день є найбільш поширеною стратегією дерев рішень для даних, але це не єдина можлива стратегія. В інтелектуальному аналізі даних, дерева рішень можуть бути використані в якості математичних та обчислювальних методів, щоб допомогти описати, класифікувати і узагальнити набір даних, які можуть бути записані таким чином:

(x, Y) = (x1, x2, x3, … xk, Y)

Залежна змінна Y є цільовою змінною, яку необхідно проаналізувати, класифікувати й узагальнити. Вектор х складається з вхідних змінних x1, x2, x3 тощо, які використовуються для виконання цього завдання.

Малюють дерева зліва направо. Місця, де приймаються рішення, позначають квадратами ?, місця появи результатів ? колами _, можливі рішення ? пунктирними лініями --------, можливі результати ? суцільними лініями .

В аналізі рішень «дерево рішень» використовуються як візуальний і аналітичний інструмент підтримки прийняття рішень, де розраховуються очікувані значення (або очікувана корисність) конкуруючих альтернатив.

Дерево рішень складається з трьох типів вузлів:

Вузли рішення -- зазвичай представлені квадратами

Імовірнісні вузли -- представляються у вигляді кола

Замикаючі вузли -- представляються у вигляді трикутника



Мал. 2 Типи вузлів

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

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

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

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

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

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

Деякі методи дозволяють побудувати більше одного дерева рішень:

Дерево рішень «мішок», найбільш раннє дерево рішень, будує кілька дерев рішень, неодноразово інтерполюючи дані із заміною, і дерева голосувань для прогнозу консенсусу;

Випадковий класифікатор «лісовий» використовує ряд дерев рішень, з метою поліпшення ставки класифікації;

«Підвищені» дерева можуть бути використані для регресійного типу та класифікації типу проблем.

«Обертання лісу» -- дерева, в яких кожне дерево рішень аналізується першим застосуванням методу головних компонент (PCA) на випадкові підмножини вхідних функцій.

Методи регулювання

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

Так, невелике дерево може не охопити ту чи іншу важливу інформацію щодо вибіркового простору. Тим не менше, важко сказати, коли алгоритм повинен зупинитися, тому що неможливо спрогнозувати, додавання якого вузла дозволить значно зменшити помилку. Ця проблема відома як «ефект горизонту». Тим не менш, загальна стратегія обмеження дерева зберігається, тобто видалення вузлів реалізується в разі, якщо вони не дають додаткової інформації[6].

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

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

Переваги методу

Серед інших методів Data Mining, метод дерева прийняття рішень має кілька переваг:

Простий в розумінні та інтерпретації. Люди здатні інтерпретувати результати моделі дерева прийняття рішень після короткого пояснення

Не вимагає підготовки даних. Інші техніки вимагають нормалізації даних, додавання змінних, а також видалення пропущених даних.

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

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

Дозволяє оцінити модель за допомогою статистичних тестів. Це дає можливість оцінити надійність моделі.

Є надійним методом. Метод добре працює навіть в тому випадку, якщо були порушені початкові припущення, включені в модель.

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

Недоліки методу

Проблема отримання оптимального дерева рішень є NP-повною з точки зору деяких аспектів оптимальності навіть для простих завдань . Таким чином, практичне застосування алгоритму дерев рішень засноване на евристичних алгоритмах, таких як алгоритм «жадібності», де єдино оптимальне рішення вибирається локально в кожному вузлі. Такі алгоритми не можуть забезпечити оптимальність всього дерева в цілому.

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

Існують концепти, які складно зрозуміти з моделі, так як модель описує їх складним шляхом. Дане явище може бути викликано проблемами XOR, парності або мультіплексарності. У цьому випадку ми маємо справу з непомірно великими деревами. Існує кілька підходів вирішення даної проблеми, наприклад, спроба змінити репрезентацію концепту в моделі (складання нових суджень) , або використання алгоритмів, які більш повно описують і репрезентують концепт (наприклад, метод статистичних відносин, індуктивна логіка програмування).

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

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

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

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

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

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

дерево рішення вузол



Розділ 2. Процес конструювання дерева рішень

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

На схемі "дерева рішень" саме верхнє положення займає кінцева мета розв'язання проблеми (кінцевий результат).

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

Для кожного "дерева рішень" будується матриця. Часто вводяться коефіцієнти взаємної корисності рішень, одержувані опитуванням експертів. Вони показують вплив ступеня важливості одних рішень на інші.

Застосування методу "дерева рішень" дозволяє:

визначати шляхи досягнення мети з виконанням кількісної оцінки складності виникають завдань та оцінкою труднощі здійснення того чи іншого варіанту;

поліпшувати якість рішень в умовах невизначеності.

Для побудови дерева на кожному внутрішньому вузлі необхідно знайти таку умову (перевірку), яка б розбивала множину, що асоціюється з цим вузлом на підмножини. В якості такої перевірки має бути вибраний один з атрибутів.

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

Методика "Розділяй і володарюй"

Методика ґрунтована на рекурсивному розбитті безлічі об'єктів з повчальної вибірки на підмножини, що містять об'єкти, що відносяться до однакових класів.

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

Безліч об'єктів з повчальної вибірки розбивається на декілька підмножин відповідно до значення вибраної незалежної змінної. Таким чином, в кожній підмножині знаходитимуться об'єкти, у яких значення вибраної незалежної змінної буде одно і те ж.

Відносно повчальної вибірки T і безліч класів C можливі три ситуації:

Множина Т містить один або більше за об'єкти, що відносяться до одного класу cr. Тоді дерево рішень для T ? це лист, що визначає клас cr.;

Множина Т не містить жодного об'єкту(порожня множина). Тоді це знову лист, і клас, що асоціюється з листом, вибирається з іншої множини, відмінної від Т, наприклад з множини, що асоціюється з батьком;

Множина Т містить об'єкти, що відносяться до різних класів. В цьому випадку слід розбити множину Т на деякі підмножини. Для цього вибирається одна з незалежних змінних xh, що має два і більше відмінних одне від одного значень ; множина Т розбивається на підмножини T1, T2,...,Tn, де кожна підмножина Ti містить усі об'єкти, у яких значення вибраної залежної змінної рівне . Далі процес триває рекурсивно для кожної підмножини до тих пір, поки значення залежної змінної в знову освіченій підмножині не буде однаковим (коли об'єкти належать одному класу). В цьому випадку процес для цієї гілки дерева припиняється.

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

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

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

Іншою проблемою при побудові дерева є проблема зупинки його розбиття.

Методи її рішення :

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

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

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

Побудувати усі можливі варіанти розбиття і вибрати найкращий проблематично за наявності великого числа незалежних змінних або при великому числі можливих класів.

Для прийняття рішення за допомогою "дерева рішень" необхідно виконати такі крокі:

1) оцінити стан ризику вектором чинників X = (x1, x2, x3, x4) (цей крок виконується користувачем системи);

2) визначити клас зростання прибули шляхом руху вектора X = (x1, x2, x3, x4) по дереву рішень з верхніх рівнів до нижніх (цей крок виконується системою).

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

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

Цінність правила, справедливого скажемо для 2-3 об'єктів, украй низька, і в цілях аналізу даних таке правило практично непридатні. Набагато прийнятніше мати дерево, що складається з малої кількості вузлів, яким би відповідала велика кількість об'єктів з повчальної вибірки. І тут виникає питання: а не чи побудувати усі можливі варіанти дерев, що відповідають повчальній множині, і з них вибрати дерево з найменшою глибиною? На жаль, це завдання являється NP- повною, це було показано Л. Хайфилем (L. Hyafill) і Р. Ривестом (R. Rivest), і, як відомо, цей клас завдань не має ефективних методів рішення.

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

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

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

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

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

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

Іноді навіть усічені дерева можуть бути все ще складні для сприйняття. У такому разі, можна удатися до методики витягання правил з дерева з подальшим створенням наборів правил, що описують класи.

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

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

Головна перевага "дерева рішень" перед іншими методами ? можливість пов'язати ставлення цілі з діями, що підлягають реалізації в сьогоденні. При побудові багаторівневого "дерева рішень" досягнення мети кожного з рівнів моделі забезпечується комплексом заходів попереднього рівня. Кожен рівень "дерева рішень" повинен займати певне місце в ієрархічній послідовності, складеної на основі дотримання причинно-наслідкових зв'язків.



Розділ 3. Алгоритми, що реалізують дерева рішень

Є різні способи вибирати алгоритм, що реалізує дерево рішень :

Алгоритм ID3, де вибір атрибуту відбувається на підставі приросту інформації(англ. Gain), або на підставі індексу Гіні.

Алгоритм C4.5 (поліпшена версія ID3), де вибір атрибуту відбувається на підставі нормалізованого приросту інформації (англ. Gain Ratio).

Алгоритм CART і його модифікації - IndCART, DB - CART.

Автоматичний детектор взаємодії Хі-квадрат (CHAID). Виконує багаторівневе розділення при розрахунку класифікації дерев;

Алгоритм ID3

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

Алгоритм ID3 ? один з алгоритмів для побудови дерева ухвалення рішень. Розроблений Джоном Р. Квинланом (англ. John R. Quinlan). Згодом Квинлан створив вдосконалену версію ? алгоритм C4.5.

Алгоритм дії:

Узяти усі невикористані ознаки і порахувати їх ентропію відносно тестових зразків

Вибрати ознаку, для якої ентропія мінімальна (інформаційна вигода відповідно максимальна)

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

Алгоритм наступний:

ID3 (Таблиця прикладів, Цільова ознака, Ознаки)

Якщо усі приклади позитивні, то повернути вузол з міткою "+".

Якщо усі приклади негативні, то повернути вузол з міткою "-".

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

Інакше:

A - ознака, яка краще всього класифікує приклади(з максимальною інформаційною вигодою).

Створити корінь дерева рішення; ознакою в корені являтиметься А.

Для кожного можливого значення А( ):

Додати нову гілку дерева нижче кореня з вузлом зі значенням А=( )

Виділити підмножину прикладів, у яких Examples ( ) прикладів, у яких А=( ):

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

Інакше, нижче цієї нової гілки додати піддерево, викликаючи рекурсивно ID3 (Examples( ), Цільова ознака, Ознаки)

Повернути корень.

Переваги алгоритму ID3

Простота і інтерпретується класифікації. Алгоритм здатний

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

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

- Якщо множина предикатів В настільки багато, що на кроці 6 завжди знаходиться предикат, що розбиває вибірку S на не порожні підмножини S0 і S1, то алгоритм будує бінарне вирішальне дерево, що безпомилково класифікує вибірку ХІ.

- Алгоритм дуже простий для реалізації і легко піддається різним удосконаленням. Можна використати різні критерії розгалуження і критерії зупинки, вводити редукцію, і т. д.

Недоліки алгоритму ID3

- Жадність. Локально оптимальний вибір предиката вV не є глобально оптимальним. У разі вибору неоптимального предиката алгоритм не здатний повернутися на рівень вгору і замінити невдалий предикат.

- Чим далі вершина v розташована від кореня дерева, тим менше довжини підвибірки S, по якій доводиться приймати рішення про галуження у вершині v.

Тим менш статистично надійним є вибір предиката вV.

Алгоритм схильний до перенавчання - як правило, він переускладнює структуру дерева. Узагальнена здатність алгоритму (якість класифікації нових об'єктів) відносно невисока.

Головна причина недоліків ? не оптимальність жадібної стратегії нарощування дерева. Перераховані недоліки більшою чи меншою мірою властиві більшості алгоритмів синтезу вирішальних дерев. Для їх усунення застосовують різні евристичні прийоми: редукцію, елементи глобальної оптимізації, "заглядання вперед" (look ahead).

Алгоритм CART

CART ? це алгоритм побудови бінарного дерева рішень - дихотомічній класифікаційній моделі. Кожен вузол дерева при розбитті має тільки двох нащадків.

CART, скорочення від Classification And Regression Tree, переводиться як 'Дерево Класифікації і Регресії' ? алгоритм бінарного дерева рішень, уперше опублікований Бриманом та ін. в 1984 році [1]. Алгоритм призначений для вирішення завдань класифікації і регресії. Існує також декілька модифікованих версій ? алгоритми IndCART і DB-CART. Алгоритм IndCART, є частиною пакету Ind і відрізняється від CART використанням іншого способу обробки пропущених значень, не здійснює регресійну частину алгоритму CART і має інші параметри відсікання.

Алгоритм DB-CART базується на наступній ідеї: замість того щоб використати повчальний набір даного для визначення розбиття, використовуємо його для оцінки розподілу вхідних і вихідних значень і потім використовуємо цю оцінку, щоб визначити розбиття. DB, відповідно означає ? 'distribution based'. Стверджується, що ця ідея дає значне зменшення помилки класифікації, в порівнянні із стандартними методами побудови дерева. Основними відмінностями алгоритму CART від алгоритмів сімейства ID3 є:

-бінарне представлення дерева рішень;

-функція оцінки якості розбиття;

-механізм відсікання дерева;

-алгоритм обробки пропущених значень;

-побудова дерев регресії.

Алгоритм CART використовує так званий індекс Gini (на честь італійського економіста Corrado Gini), який оцінює " відстань" між розподілами класів.

У алгоритмі CART кожен вузол дерева рішень має двох нащадків. На кожному кроці побудови дерева правило, формоване у вузлі, ділить задану безліч прикладів (повчальну вибірку) на дві частини ? частина, в якій виконується правило (нащадок ? right) і частина, в якій правило не виконується (нащадок ? left). Для вибору оптимального правила використовується функція оцінки якості розбиття. Навчання дерева рішень відноситься до класу навчання з учителем, тобто повчальна і тестова вибірки містять класифікований набір прикладів. Оцінна функція, використовувана алгоритмом CART, базується на інтуїтивній ідеї зменшення нечистоти (невизначеності) у вузлі. Алгоритм CART використовує так званий індекс Gini (на честь італійського економіста Corrado Gini (сумарний критерій міри відмінності фактичного розподілу доходів, витрат на споживання або іншої пов'язаної з ними змінної від гіпотетичного розподілу доходів, при якому кожен індивід наділяється однаковою долею доходу)), який оцінює " відстань" між розподілами класів.



,

де c - поточний вузол, а pj - імовірність класу j на вузлі c.

В процесі зростання дерева алгоритм CART проводить для кожного вузла повний перебір усіх атрибутів, на основі яких може бути побудоване розбиття, і вибирає той, який максимізував значення показника

,

де s ? ідентифікатор розбиття, t ? ідентифікатор вузла, tL и tR ? лівий та правий наслідники вузла t відповідно, PL и PR - відношення числа прикладів в лівому та правому наслідниках до їх загального числа в множині, що навчається, P(j|tL) и P(j|tR) - відношення числа прикладів класу j в лівому і правому наслідниках до їх загального числа в кожному з них. Процес побудови регресійних дерев рішень (мал. 3) в основному аналогічний класифікаційним, але замість міток класів в листі розташовуватимуться числові значення. Фактично при цьому реалізується кусково-постійна функція вхідних змінних.

Мал. 3 Побудова регресійних дерев рішень



В результаті в кожному листі повинні опинитися приклади з схожими значеннями вихідний змінної. Чим ближче вони будуть, тим менше стане їх дисперсія. Тому вона є хорошою мірою "чистоти" вузла. Тоді найкращим розбиттям у вузлі є те, яке забезпечить максимальне зменшення дисперсії вихідний змінної в нім.

Алгоритм С4.5

C4.5 ? алгоритм для побудови дерев рішень, розроблений Джоном Квинланом (англ. John Ross Quinlan). C4.5 є вдосконаленою версією алгоритму ID3 того ж автора.

C4.5 ? алгоритм побудови дерева рішень, кількість нащадків у вузла не обмежена. Не уміє працювати з безперервним цільовим полем, тому вирішує тільки завдання класифікації.

Серед поліпшень варто відмітити наступні:

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

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

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

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

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

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

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

Алгоритм C4.5 вирішує цю проблему шляхом введення нормалізації.

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

Побудова дерева

Нехай є Т ? повчальна вибірка прикладів, а С ? безліч класів, що складається з k елементів. Для кожного прикладу з T відома його приналежність до якого-небудь з класів C1…Ck.

Побудова дерева рішень алгоритмом C4.5 принципово не відрізняється від його побудови в ID3. На першому кроці є корінь і асоційована з ним множина T, яке необхідно розбити на підмножини. Для цього необхідно вибрати один з атрибутів в якості перевірки. Вибраний атрибут A має n значень, що дає розбиття на n підмножин. Далі створюються нащадків кореня, кожному з яких поставлена у відповідність своя підмножина, отримана при розбитті T.

Процедура вибору атрибуту і розбиття по ньому рекурсивно застосовується до усіх n нащадків і зупиняється в двох випадках:

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

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

У повчальній вибірці можуть бути присутніми об'єкти з пропущеними значеннями атрибутів. В цьому випадку їх або відкидають (що спричиняє за собою ризик втратити частину даних), або застосувати підхід, що припускає, що пропущені значення по змінній імовірнісний розподілений пропорційно частоті появи існуючих значень.

Алгоритм C4.5, вдосконалена версія алгоритму ID3 (Iterative Dichotomizer), використовує теоретико-інформаційний підхід. Для вибору найбільш відповідного атрибуту, пропонується наступний критерій:

Gain(X) = Info(T) - Infox(T), (1)

де Info(T) - ентропія множини T, а

(2)

Множини T1, T2, ... Tn отримані при розбитті вихідної множини T по перевірці X. Обирається атрибут, що дає максимальне значенння по критерію (1).

Алгоритм покриття

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

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

Для вибору незалежної змінної і її значення, яке розділяє множину, виконуються наступні дії:

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

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

Вибираються умови, що покривають найбільшу кількість об'єктів вибраного класу.

Вибрана умова є умовою розбиття підмножини на два нових.

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

Розділ 4. Приклад побудови дерева рішень

Своєчасна розробка і ухвалення правильного рішення ? головні завдання роботи управлінського персоналу будь-якої організації. Непродумане рішення може дорого коштувати компанії.

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

Процес прийняття управлінських рішень за допомогою дерева рішень у загальному випадку припускає виконання п'яти етапів:

Етап 1. Формулювання завдання.

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

Етап 2. Побудова "дерева рішень".

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

Етап 4. Установлення виграшів (чи програшів, як виграшів зі знаком мінус) для кожної можливої комбінації альтернатив (дій) і станів середовища.

Етап 5. Вирішення завдання.

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

Приклад 1. Головному інженерові компанії потрібно вирішити, монтувати або ні нову виробничу лінію, що використовує новітню технологію. Якщо нова лінія працюватиме безвідмовно, компанія отримає прибуток 200 млн. рублів. Якщо ж вона відмовить, компанія може втратити 150 млн. рублів. За оцінками головного інженера, існує 60% шансів, що нова виробнича лінія відмовить. Можна створити експериментальну установку, а потім вже вирішувати, монтувати або ні виробничу лінію. Експеримент обійдеться в 10 млн. рублів. Головний інженер вважає, що існує 50% шансів, що експериментальна установка працюватиме. Якщо експериментальна установка працюватиме, то 90%% шансів зате, що змонтована виробнича лінія також працюватиме. Якщо ж експериментальна установка не працюватиме, то тільки 20%% шансів за те, що виробнича лінія заробить. Чи слід будувати експериментальну установку? Чи слід монтувати виробничу лінію? Яка очікувана вартісна оцінка найкращого рішення?

У вузлі F (мал. 3) можливі результати "лінія працює" з вірогідністю 0,4 (що приносить прибуток 200) і "лінія не працює" з вірогідністю 0,6 (що приносить збиток - 150) => оцінка вузла F. EMV( F) = 0,4 x 200 + 0,6 х( - 150) = - 10. Це число ми пишемо над вузлом F.

EMV(G) = 0.

У вузлі 4 ми вибираємо між рішенням "монтуємо лінію" (оцінка цього рішення EMV( F) = - 10) і рішенням "не монтуємо лінію" (оцінка цього рішення EMV(G) = 0) : EMV(4) = max {EMV( F), EMV(G)} = max {- 10, 0} = 0 = EMV(G). Цю оцінку ми пишемо над вузлом 4, а рішення "монтуємо лінію" відкидаємо і закреслюємо.

Аналогічно:

EMV( B) = 0,9 х 200 + 0,1 х (-150) = 180 - 15 = 165.

EMV(С) = 0.

EMV(2) = max {EMV(В), EMV(С} = max {165, 0} = 165 = EMV(5).

Тому у вузлі 2 відкидаємо можливе рішення "не монтуємо лінію".

EM V(D) = 0,2 х 200 + 0,8 х (-150) = 40 -- 120 = -80.

EMV( E) = 0.

EMV(3) = max {EMV(D), EMV(E)} = max {-80, 0} = 0 = EMV( E).

Тому у вузлі 3 відкидаємо можливе рішення "не монтуємо лінію".

ЕМ V( A) = 0,5 х 165 + 0,5 х 0 -- 10 = 72,5.

EMV(l) = max {EMV(A), EMV(4)} = max {72,5; 0} = 72,5 = EMV( A).

Тому у вузлі 1 відкидаємо можливе рішення "не монтуємо лінію".

Очікувана вартісна оцінка найкращого рішення дорівнює 72,5 млн. рублів. Будуємо установку. Якщо установка працює, то монтуємо лінію. Якщо установка не працює, то лінію монтувати не потрібно.

Приклад 2. Компанія розглядає питання про будівництво заводу. Можливі три варіанти дій.

A. Побудувати великий завод вартістю M1 = 700 тисяч доларів. При цьому варіанті можливі великий попит(річний доход у розмірі R1 = 280 тисяч доларів впродовж наступних 5 років) з вірогідністю p1 = 0,8 і низький попит(щорічні збитки R2 = 80 тисяч доларів) з вірогідністю р2 = 0,2.

Б. Побудувати маленький завод вартістю М2 = 300 тисяч доларів. При цьому варіанті можливі великий попит(річний доход у розмірі T1= 180 тисяч доларів впродовж наступних 5 років) з вірогідністю p1 = 0,8 і низький попит(щорічні збитки Т2 = 55 тисяч доларів) з вірогідністю р2 = 0,2.

B. Відкласти будівництво заводу на один рік для збору додаткової інформації, яка може бути позитивною або негативною з вірогідністю p 3 = 0,7 і p4 = 0,3 відповідно. У разі позитивної інформації можна побудувати заводи за вказаними вище розцінками, а вірогідність великого і низького попиту міняється на p 5 = 0,9 і р6 = 0,1 відповідно. Доходи на подальші чотири роки залишаються колишніми. У разі негативної інформації компанія заводи будувати не буде.

Мал. 5 Дерево рішень для прикладу 2



Усі розрахунки виражені в поточних цінах і не повинні дисконтуватися. Намалювавши дерево рішень, визначимо найбільш ефективну послідовність дій, ґрунтуючись на очікуваних доходах.

Очікувана вартісна оцінка вузла А (мал. 5) дорівнює ЕМ V(А) = 0,8 х 1400 + 0,2 х (-400) -- 700 = 340.

EMV( B) = 0,8 х 900 + 0,2 х (-275) -- 300 = 365.

EMV( D) = 0,9 x 1120 + 0,1 x (-320) -- 700 = 276.

EMV(E) = 0,9 x 720 + 0,1 х (-220) -- 300 = 326.

EMV(2) = max {EMV( D), EMV( E)} = max {276, 326} = 326 = EMV( E). Тому на вузлі 2 відкидаємо можливе рішення "великий завод".

EMV( C) = 0,7 x 326 + 0,3 x 0 = 228,2.

EMV(1) = max {ЕМ V( A), EMV(B), EMV( C)} = max {340; 365; 228,2} = 365 = EMV( B). Тому на вузлі 1 відкидаємо можливе рішення «маленький завод».

Дослідження проводити не треба. Будуємо маленький завод. Очікувана вартісна оцінка цього найкращого рішення дорівнює 365 тисяч доларів.



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

1. J. Ross Quinlan. C4.5: Programs for Machine learning / J. Ross Quinlan. - NY: Morgan Kaufmann Publishers, 1993.

2. S.Murthy. Automatic construction of decision trees from data: A Multi-disciplinary survey/ S.Murthy. W.: Conde Nast ? 1997.

3. К. Шеннон. Работы по теории информации и кибернетике./ К. Шеннон.? М.: Мысль, 1963. - (Иностранная литература)

4. С.А. Айвазян Прикладная статистика и основы эконометрики / С.А. Айвазян, В.С Мхитарян. ? М.: Юнити, 1998.

5. Ананий В. Левитин Глава 10. Ограничения мощи алгоритмов: Деревья принятия решения // Алгоритмы: введение в разработку и анализ = Introduction to The Design and Analysis of Aigorithms. -- М.: Вильямс, 2006. -- С. 409-417.

6. http://www.basegroup.ru/glossary/definitions/decision_trees/

7. http://uk.wikipedia.org/wiki/Дерево_прийнняття_рішень/

8. http://www.basegroup.ru/library/analysis/tree/description/

9. http://samoucka.ru/

Размещено на Allbest.ru

...