Студопедия
Новини освіти і науки:
МАРК РЕГНЕРУС ДОСЛІДЖЕННЯ: Наскільки відрізняються діти, які виросли в одностатевих союзах


РЕЗОЛЮЦІЯ: Громадського обговорення навчальної програми статевого виховання


ЧОМУ ФОНД ОЛЕНИ ПІНЧУК І МОЗ УКРАЇНИ ПРОПАГУЮТЬ "СЕКСУАЛЬНІ УРОКИ"


ЕКЗИСТЕНЦІЙНО-ПСИХОЛОГІЧНІ ОСНОВИ ПОРУШЕННЯ СТАТЕВОЇ ІДЕНТИЧНОСТІ ПІДЛІТКІВ


Батьківський, громадянський рух в Україні закликає МОН зупинити тотальну сексуалізацію дітей і підлітків


Відкрите звернення Міністру освіти й науки України - Гриневич Лілії Михайлівні


Представництво українського жіноцтва в ООН: низький рівень культури спілкування в соціальних мережах


Гендерна антидискримінаційна експертиза може зробити нас моральними рабами


ЛІВИЙ МАРКСИЗМ У НОВИХ ПІДРУЧНИКАХ ДЛЯ ШКОЛЯРІВ


ВІДКРИТА ЗАЯВА на підтримку позиції Ганни Турчинової та права кожної людини на свободу думки, світогляду та вираження поглядів



Контакти
 


Тлумачний словник






Алгоритми

Скорочення дерева або відсікання гілок

Зупинка побудови дерева

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

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

Один з варіантів правил зупинки – "рання зупинка" (prepruning), вона визначає доцільність розбивки вузла. Перевага використання такого варіанта – зменшення часу на навчання моделі. Однак тут виникає ризик зниження точності класифікації. Тому рекомендується "замість зупинки використовувати відсікання" (Breiman, 1984).

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

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

Існує ще ряд правил, але слід зазначити, що жодне з них не має великої практичної цінності, а деякі застосовні лише в окремих випадках [35].

Рішення проблеми занадто гіллястого дерева є його скорочення шляхом відсікання (pruning) деяких гілок.

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

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

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

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

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

 

На сьогоднішній день існує велика кількість алгоритмів, що реалізують дерева рішень: CART, C4.5, CHAID, CN2, NewId, ITrule та інші.

Алгоритм CART (Classification and Regression Tree), як видно з назви, вирішує задачі класифікації і регресії. Він розроблений в 1974-1984 роках чотирма професорами статистики – Leo Breiman (Berkeley), Jerry Friedman (Stanford), Charles Stone (Berkeley) і Richard Olshen (Stanford).

Атрибути набору даних можуть мати як дискретне, так і числове значення.

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

Інші особливості алгоритму CART:

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

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

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

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

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

Функція оцінки якості розбивки, що використовується для вибору оптимального правила, – індекс Gini – був описаний вище. Відзначимо, що дана оцінна функція заснована на ідеї зменшення невизначеності у вузлі. Допустимо, є вузол, і він розбитий на два класи. Максимальна невизначеність у вузлі буде досягнута при розбивці його на дві підмножини по 50 прикладів, а максимальна визначеність – при розбивці на 100 і 0 прикладів.

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

Механізм відсікання. Цим механізмом, що має назву minimal cost-complexity tree pruning, алгоритм CART принципово відрізняється від інших алгоритмів конструювання дерев рішень. У розглянутому алгоритмі відсікання – це якийсь компроміс між одержанням дерева "підходящого розміру" та одержанням найбільш точної оцінки класифікації. Метод полягає в одержанні послідовності зменшуваних дерев, але дерева розглядаються не всі, а тільки "кращі представники".

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

Отже, основні характеристики алгоритму CART: бінарне розщеплення, критерій розщеплення – індекс Gini, алгоритми minimal cost-complexity tree pruning і V-fold cross-validation, принцип "виростити дерево, а потім скоротити", висока швидкість побудови, обробка пропущених значень.

 


Читайте також:

  1. Алгоритми арифметичних операцій над цілими невід’ємними числами у десятковій системі числення.
  2. Алгоритми групи KWE
  3. Алгоритми керування ресурсами
  4. Алгоритми переведення чисел з однієї позиційної системи числення в іншу
  5. Алгоритми побудови дерев екстремальної ваги
  6. Алгоритми симетричного і асиметричного шифрування
  7. Алгоритми та блок-схеми
  8. Алгоритми шифрування в електронних картах
  9. Засоби, методи і алгоритми контролю
  10. Криптографічні алгоритми з відкритим ключем
  11. Криптографічні алгоритми з секретним ключем




Переглядів: 649

<== попередня сторінка | наступна сторінка ==>
Критерій розщеплення | Модуль 4. Закономірності розвитку сітового господарства.

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

 

© studopedia.com.ua При використанні або копіюванні матеріалів пряме посилання на сайт обов'язкове.


Генерація сторінки за: 0.002 сек.