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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Методи ухвалення|прийняття,приймання| рішень

  Методи аналізу і вирішення проблем (методи ухвалення|прийняття,приймання| рішень) можуть бути різними залежно від типу|типа| вирішуваних|рішати,розв'язати| завдань|задач| або проблем. Проблеми можуть бути класифіковані таким чином:

• стандартні проблеми, що мають чітку структуру, причинно-наслідкові зв'язки, аналоги;

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

• слабоструктуровані проблеми, в яких далеко не завжди є видимими напрями|направлення| рішення|розв'язання,вирішення,розв'язування|, причинно-наслідкові зв'язки, самі проблеми не формулюються достатньо|досить| чітко;

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

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

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

  Всі методи ухвалення|прийняття,приймання| рішень можна розділити на дві групи: формалізовані (математичні) і неформалізовані (евристичні).

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

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

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

• економіко-математичні моделі і методи (ЕММ), що формалізують взаємозв'язки процесів і явищ;

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

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

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

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

Аналітичні методи характерні|вдача| тим, що між умовами вирішуваного|рішати,розв'язати| завдання|задачі| і її результатами встановлюються аналітичні, формульні| залежності.

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

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

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

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

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

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

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