5. Дерева рішень icon

5. Дерева рішень


Схожі
Реферат на тему: Дерева та ліси України...
Тематичний план дисципліни Плани лекцій та семінарських (практичних) занять...
Стан міжнародної наукової співпраці внз регіону та реалізація рішень монмолодьспорту з цього...
Нацiональна академiя наук України Інститут програмних систем нан україни...
“Управлінські рішення, класифікація та характеристика організаційних рішень...
П л а н
Акти державного управління...
Реферат на тему...
Реферат уроботі наведено результати теоретичних та експериментальних досліджень роботи...
Підготовка користувачів інформаційно-комунікаційних технологій...
7. 1 Вступ
Методика аналізу фінансового стану підприємства. Загальний аналіз фінансового стану підприємства...



5. Дерева рішень


Дерева рішень є найдавнішим алгоритмом аналізу даних. Роботи в цьому напрямку розчали Ховленд (Hoveland) та Хант (Hunt) у 1950-х роках.

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

Під правилом розуміють логічну конструкцію, що надана у вигляді «Якщо А, Тоді Б»

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


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

  • Атрибут – Властивість, ознака, незалежна змінна

  • Мітка класу – Залежна змінна, цільова змінна, ознака, що визначає клас об’єкту.

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

  • Лист – Кінцевий вузол дерева, вузол відповіді.

  • Перевірка – умова у вузлі.

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



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

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

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

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

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

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

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

Етапи побудови дерев рішень


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

Правило розбиття


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

Зупинка навчання


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

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

Правило відсікання


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

  • Побудувати дерево.

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

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

Правила


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

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

Практичний приклад


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

При навчанні дерева використано фактори

  • № паспорту

  • Прізвище, ім’я, по батькові

  • Адреса



Ці поля визначені як несуттєві

  • Розмір кредиту

  • Термін кредиту

  • Мета кредиту

  • Місячний дохід

  • Місячний розхід

  • Основні розходи

  • Наявність власного житла

Цільовим полем буде поле Видати кредит, що приймає значення Так / Ні.

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



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

Певні фактори можуть бути замінені одним узагальненим фактором. Наприклад, ^ Розмір кредиту, Термін кредиту, Середньомісячний дохід, Місячний розхід – можуть не використовуватися, бо існує фактор Кредит під заставу, що зрештою є їх точним узагальненням.

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

Якщо «Кредит під заставу» - Так і

«Термін проживання в цьому місті» > 19 років і

«Наявність нерухомості» - Так і

«Наявність банківського розрахунку» - Так

Тоді «Надати кредит» - Так

Достовірність = 98%

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

Переваги дерев рішень


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

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

  • Правила формуються на природній мові

  • Інтуїтивно зрозуміла модель

  • Висока точність прогнозу

  • Дерева рішень є самоадаптованими моделями, де втручання людини є мінімальним

  • Висока якість результату досягається за рахунок визначення значущих факторів для вибору відповіді.

  • Отриманий результат є статистично обґрунтованим.

Завдання, які вирішуються можуть бути об'єднані в наступні три класи:


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

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

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

Області застосування


  • Банківська справа – оцінка кредитоспроможності

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

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

  • Молекулярна біологія – аналіз будови сполучень




Скачати 54.64 Kb.
залишити коментар
Дата конвертації24.10.2013
Розмір54.64 Kb.
ТипДокументы, Освітні матеріали
Додати документ в свій блог або на сайт

Ваша оцінка цього документа буде першою.
Ваша оцінка:
Додайте кнопку на своєму сайті:
uadocs.exdat.com

База даних захищена авторським правом ©exdat 2000-2017
При копировании материала укажите ссылку
звернутися до адміністрації
Реферати
Автореферати
Методички
Документи
Поняття

опублікувати
Документи

Рейтинг@Mail.ru
наверх