Застосування дерев рішень для задач класифікації

Лабораторна робота

Розробка програмного продукту.

Мета: Освоєння методів дерева рішень

Теоретичні відомості

Алгоритм CART

Алгоритм CART (ClassificationandRegressionTree), як видно з назви, вирішує завдання класифікації і регресії. Він розроблений в 1974-1984 роках чотирма професорами статистики - LeoBreiman (Berkeley), JerryFriedman (Stanford), CharlesStone (Berkeley) і RichardOlshen (Stanford).

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

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

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

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

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

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

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

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

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

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

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

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

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

 

Алгоритм ID3

Абстрактний

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

Введення

Дж. Росс Quinlan спочатку розроблений ID3 в Університеті Сіднея. Він вперше представлений ID3 в 1975 році в книзі, Machine Learning, вип. 1, немає. 1. ID3 базується Концепція системи навчання (CLS) алгоритм. Основний алгоритм CLS над безліччю підготовки випадків C:

Крок 1: Якщо всі екземпляри в C позитивні, то створіть YES вузлів і зупинився.

Якщо всі екземпляри в C негативні, створити NO вузлів і зупинився.

В іншому випадку виберіть функцію, F зі значеннями v1,..., Vn і створити рішення вузла.

Крок 2: Розділ підготовки випадках, C на підмножини, C1, C2,..., Cn відповідно до значень В.

Крок 3: застосувати алгоритм рекурсивно для кожного з множин Ci.

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

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

Обговорення

ID3 є ненаращіваемого алгоритму, тобто він отримує свої класи від фіксованого набору навчальних екземплярів. Інкрементний алгоритм змінює поточне визначення поняття, при необхідності, нового зразка. Класи, створені за ID3 є індуктивними, тобто, враховуючи невеликий набір навчальних випадках, конкретні класи, створені за ID3 будуть працювати для всіх майбутніх випадків. Розподіл невідомих повинно бути таким же, як тестів. Індукційна класи не можуть бути доведені, щоб працювати в будь-якому випадку, так як вони можуть класифікувати нескінченну кількість екземплярів. Зверніть увагу, що ID3 (або будь-якого індуктивного алгоритму) можуть неправильної класифікації даних.

Опис даних

Вибірка даних, використовуваних ID3 є певні вимоги, які є:

Атрибут Значення Опис - ті ж атрибути повинні описати кожен приклад і мають фіксоване число значень.

Визначених класів - атрибути Наприклад, мають бути вже визначені, тобто, вони не впізнали по ID3.

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

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

 

Вибір атрибутів

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

 

Алгоритм C4.5

C4.5 є вдосконаленою версією алгоритму ID3 того ж автора. Зокрема, в нову версію були додані відсікання гілок (англ. pruning), можливість роботи з числовими атрибутами, а також можливість побудови дерева з неповної навчальної вибірки, в якій відсутні значення деяких атрибутів.

Вимоги до даних

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

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

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

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

 

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

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

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

Обраний атрибут А має n значень, що дає розбиття на n підмножин. Далі створюються n нащадків кореня, кожному з яких поставлено у відповідність своя підмножина, отримана при розбитті Т. Процедура вибору атрибута і розбиття по ньому рекурсивно застосовується до всіх n нащадків і зупиняється в двох випадках:

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

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

 

Застосування дерев рішень для задач класифікації.

Основні визначення

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

Дерева рішень (decision trees) – один із таких методів автоматичного аналізу даних. Перші ідеї створення дерев рішень прозвучали у роботах Ховленда (Hoveland) і Ханта (Hunt) кінця 50-х років XX століття. Проте основною роботою, що дала імпульс для розвитку цього напрямку, стала книга Ханта, Мерина і Стоуна ((Hunt, Marin, Stone) «Experiments in Induction» у 1966р.

 

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

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

 

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

 

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

 

Мал. 1. Приклад фрагменту дерева рішень.

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

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

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

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