Вступ
Алгоритми ID3 і C4.5 придумані Джоном Квінланом (John R. Quinlan) для індукування Класифікаційних Моделей(Classification Models), які ще називають Деревами прийняття рішень(Decision Trees), із даних.
Перш за все ми маємо множину рядків даних. Кожен вектор, або рядок, має таку ж структуру, складається із набору пар властивість/значення. Одна із цих властивостей представляє категорію нашого вектору. Нашим завданням є побудувати дерево прийняття рішень, яке базуючись на відповідях про властивості, що не відповідають за категорію, зробити висновок про значення категорізаційної властивості. Зазвичай категорізаційна властивість приймає тільки два значення {Так, Ні}, або {true, false}, або {success, failure}. В будь-якому випадку одне із значень буде означати невдачу.
Для прикладу, ми можемо мати результати замірів про деяку подію, зроблених експертами. Для кожної події ми знаємо рішення, яке було прийняте експертами, напр. ствердне рішення, відхилити або ж інше. Іншими словами ми маємо вектор із некатегоризаційними властивостями та категоризаційну властивісь – прийняте рішення.
Розглянемо більш детальний приклад. Ми маємо справу із записами що засвідчують погодні умови для гри в гольф. Категоризаційна властивість є рішення про те чи слід грати в гру чи ні. Некатегоризаційні властивості такі:
ВЛАСТИВІСТЬ | МОЖЛИВІ ЗНАЧЕННЯ
============+======================= небо | сонячно, хмарно, дощ ------------+----------------------- температура | значення ------------+----------------------- вологість | значення ------------+----------------------- вітряно | так, ні ============+=======================
а тут набір даних для побудови дерева:
НЕБО | ТЕМПЕРАТУРА | ВОЛОГІСТЬ | ВІТРЯНО | ГРАТИ? ===================================================== сонячно| 30 | 85 | ні | Не грати сонячно| 27 | 90 | так | Не грати хмарно | 28 | 78 | ні | Грати дощ | 21 | 96 | ні | Грати дощ | 20 | 80 | ні | Грати дощ | 18 | 70 | так | Не грати хмарно | 18 | 65 | так | Грати сонячно| 22 | 95 | ні | Не грати сонячно| 21 | 70 | ні | Грати дощ | 24 | 80 | ні | Грати сонячно| 24 | 70 | так | Грати хмарно | 22 | 90 | так | Грати хмарно | 27 | 75 | ні | Грати дощ | 22 | 80 | так | Не грати
Зауважмо, що дві властивості мають недетерміновані значення – температура і вологість. ID3 алгоритм не може напряму мати справу із такими випадками, але є модифікації, які дозволють йому працювати із такими значеннями. Дерева прийняття рішень важливі не тільки тому, що вони дозволяють узагальнити те, що ми знаємо, або відомий набір даних для навчання, але тому, що ми можемо сподіватися на те, що алгоритм правильно скласифікує нові, невідомі випадки. Таким чином коли ми будуємо класифікаційну модель (дерево), ми повиння мати дані для навчання і дані для перевірки правильності побудованої моделі.
Спрощений приклад складу магазину, який включає тільки дискретні значення властивостей речей для продажу, та виручка як категоризаційну властивість, яка може мати два значення {висока, низька}. Некатигоризаційні властивості:
ВЛАСТИВІСТЬ | МОЖЛИВІ ЗНАЧЕННЯ ============+======================= вік | старий, середній, новий ------------+----------------------- конкуренція | ні, так ------------+----------------------- тип | ПЗ, "залізо" ------------+----------------------- і дані для навчання такі: ВІК | КОНКУРЕНЦІЯ | ТИП | ВИРУЧКА ========================================= старий | так | ПЗ | низька --------+-------------+---------+-------- старий | ні | ПЗ | низька --------+-------------+---------+-------- старий | ні | залізо | низька --------+-------------+---------+-------- сер. | так | ПЗ | низька --------+-------------+---------+-------- сер. | так | залізо | низька --------+-------------+---------+-------- сер. | ні | залізо | висока --------+-------------+---------+-------- сер. | ні | ПЗ | висока --------+-------------+---------+-------- новий | так | ПЗ | висока --------+-------------+---------+-------- новий | ні | залізо | висока --------+-------------+---------+-------- новий | ні | ПЗ | висока --------+-------------+---------+--------
Основні концепції алгоритму ID3 такі:
- В дереві рішень кожен вузол відповідає за некатегоризаційну властивість, а кожна дуга, яка виходить із кореня за можливі значення того атрибуту. Листки дерева визначають очікуване значення категоризаційної властивості для записів, що відповідають шляху пройденому від кореня до цього листочка. (Ось чому ми називаємо цю модель деревом прийняття рішень.)
- В дереві рішень кожен вузол повинен відповідати за некатегоризаційну властивість, яка є найбільш інформативна поміж інших властивостей, що ще не є в шляху від кореня до заданого вузла. (Це дає поняття “Хорошого” дерева прийняття рішень.)
- Ентропія використовується для визначчення на скільки вузол є інформативним. (Це дає визначення до того, що ми розуміємо під “Хорошим” деревом.)
С4.5 є доповненням до алгоритму ID3, що враховує допустимі значення, недетерміновані значення, відсікання дерева, виведення правил та інше.
Означення
Якщо є n можливих повідомлень, тоді вірогідність p кожного є рівна 1/n а інформативність передана цим повідомленням є такою -log(p) =
log(n).
Для прикладу, якщо є 16 повідомлень, тоді log(16) = 4
і нам потрібно 4 біти, щоб ідентифікувати кожне повідомлення.
В загальному, якщо ми маємо розподіл імовірностей P = (p1, p2, ..,
pn)
тоді інформативність передана цим розподілом, або Ентропія Р, визначається так::
Для прикладу, якщо P є (0.5, 0.5) тоді I(P) рівне 1, якщо P є (0.67, 0.33) тоді I(P) рівне 0.92, а якщо P є (1, 0) тоді I(P) дорівнює 0.
[Зауважте, що чим більш подібні ймовірності в розподілі, тим більша є інформативність]Якщо множина T записів є розбита на виокремлі класи
C1, C2, .., Ck базуючись на значенні категоризаційної властивості, тоді інформація, необхідна для ідентифікації класу елемента із множини Т є Info(T) = I(P), де P є ймовірнісний розподіл розбиття (C1, C2, .., Ck):
В нашому прикладі гри в гольф, ми отримуємо Info(T) = I(9/14, 5/14) = 0.94,
а в нашому прикладі із складом магазину ми отримуємо Info(T) = I(5/10,5/10) = 1.0.
Якщо перше розбиття T, базоване на значенні некатигоризованого атрибуту X буде таке T1, T2, .., Tn тоді інформація необхідна для визначення класу елементу із Т є середнім із інформацій необхідних для ідертифікації класу елемента Ti, іншими словами середнє із Info(Ti):
У випадку гри в гольф, для властивості Небо, ми маємо:
Дамо означення приросту інформації Gain(X,T) як
Це представляє різницю між інформацією необхідною для визначення елемента із Т і інформації необхідної для визначення елемента із Т, після того, якщо значення властивості Х було визначено, іншими словами приріст інформації завдяки відомості властивості Х.
В нашому прикладі із грою в гольф, для властивосіті Небо, приріст буде:
Якщо взяти властивість Вітряно, ми отримаємо такі значення
Info(Windy,T) = 0.892 та Gain(Windy,T) = 0.048. Таким чином Небо надає більше інформаційного приросту аніж Вітряно.
Ми можемо використовувати знання приросту для відсортовування властивостей і для побудови дерева прийняття рішень, де в кожному вузлі знаходиться властивість із найбільшим інформаційним приростом в порівнянні до інших властивостей, які не включені в шлях від кореня до поточного вузла.
Це впорядкування вирішує два завдання:
- Для створення малих дерев, що дозволяє після декількох питань визначити рішення.
- Задовольнити бажану оптимальність процесу для рядків, що розглядаються.
Алгоритм ID3
Алгоритм ID3 використовується для побудови дерев прийняття рішень, маючи множину некатегоризаційних властивостей C1, C2, .., Cn, категоризаційну властивість C,
і множину записів для навчання T.
function ID3 (R: множина некатегоризаційних властивостей,
C: категоризаційна властивість,
S: множина для навчання) returns дерево прийняття рішень;
begin
Якщо S пуста, повернути один вузол із значенням невдача;
Якщо S складаєтсья із рядків, для яких значення категоризаційної
властивості одне й те ж,
повернути єдиний вузол із тим значенням;
Якщо R пуста, тоді повернути єдиний вузол із значенням, яке є
найбільш частішим серед значень катеригоційної властивості,
що було знайдено серед рядків S;
Нехай D є властивістю із найбільшим приростом Gain(D,S)
серед властивостей в множині R;
Нехай {dj| j=1,2, .., m} - значення властивості D;
Нехай {Sj| j=1,2, .., m} - підмножини S, що включають
відповідні рядки із значенням dj для властивості D;
Повернути дерево із коренем поміченим D і дуги позначені
d1, d2, .., dm що продовжуються наступними деревами
ID3(R-{D}, C, S1), ID3(R-{D}, C, S2), .., ID3(R-{D}, C, Sm);
end ID3;В прикладі із грою в гольф ми отримуємо наступне дерево:
Небо
/ |
/ |
хмарно / |сонячно дощ
/ |
Грати Вологість Вітряно
/ | |
/ | |
<=75 / >75| так| ні
/ | |
Грати Не грати Не грати Грати
В прикладі із магазинним складом дерево буде:
Вік
/ |
/ |
нов/ |сер старе
/ |
Вис Competition Низька
/
/
ні/ так
/
Вис НизькаВикористання зважених приростів (Gain Ratios)
Поняття приросту (Gain) введене раніше має тенденцію одобряти властивості, що мають велику кількість значень. Для прикладу, якщо в нас є властивість D, що має різні значення для кожного рядка, тоді інформативність буде Info(D,T) рівною 0, таким чином приріст Gain(D,T)
є максимальним.
Щоб компенсувати це Квінлан запропонував використання наступного зглажування замість звичного приросту:
Gain(D,T)
GainRatio(D,T) = ----------
SplitInfo(D,T)
де SplitInfo(D,T) є інформація у відповідності до розбиття T на основі
значень категоризаційної властивості D. Таким чином SplitInfo(D,T) є
I(|T1|/|T|, |T2|/|T|, .., |Tm|/|T|)
де {T1, T2, .. Tm} є розбиття множини T продуковане значенням D.
У випадку нашої гри в гольф SplitInfo(Outlook,T) рівне
-5/14*log(5/14) - 4/14*log(4/14) - 5/14*log(5/14) = 1.577
таким чином GainRatio для Небо буде 0.246/1.577 = 0.156. І
SplitInfo(Windy,T) буде
-6/14*log(6/14) - 8/14*log(8/14) = 6/14*0.1.222 + 8/14*0.807 = 0.985
отже, GainRatio для Вітряно є 0.048/0.985 = 0.049Доповнення C4.5
С4.5 додає цілий ряд доповнень до оригінального алгоритму ID3.
Під час побудови дерева рішень ми можемо мати справу із навчальними даними, що мають рядки із невідомими значеннями властивостей під час обрахунку приросту, беручи до уваги лише рядки, де ця властивість визначена.
Під час використання дерева, ми можемо класифікувати рядки, що мають невідомі значення властивостей, вгадуючи ймовірності появи різних результатів.
Для нашого прикладу із грою у гольф, якщо ми маємо новий рядок, для якого Небо є сонячне і Вологість є невідомою, ми продовжуємо наступним чином:
Ми рухаємося від кореня Небо до вузла Вологість проходячи дугу іменовану 'сонячно'. В цій позиції, оскільки ми не знаємо значення Вологості ми спостерігаємо, що якщо вологість є менша за 75 є тільки два рядки коли слід грати, і якщо вологість є більша ніж 75 тоді є три рядки коли не слід грати. Таким чином ми можемо дати відповідь для рядка із ймовірностями (0.4, 0.6) грати або ж не грати.
Ми можемо мати справу із недетермінованими властивостями наступним чином. Припустимо що атрибут Ci є недетермінованим (число як для вологості). Ми визначаємо значення для цього атрибуту в множині для навчання. Скажімо ми маємо посортовані значення, A1, A2, .., Am. Тоді для кожного значення Aj, j=1,2,..m, ми розбиваємо рядки на такі, які менці за Aj, і такі які більші за Aj. Для кожного із розбиттів ви рахуємо приріст, або зважений приріст, і вибираємо таке розбиття, яке максимізує приріст.
В нашому прикладі із грою в гольф для вологості, якщо T є множиною навчання, ми визначаємо інформацію для кожного розбиття і знаходимо найкраще в точці 75.
Таким чином діапазон для цього атрибуду визначений як {<=75, >75}.
Зауважте що цей метод вимагає багато калькуляцій, тому є ресурсоємним.
Відсікання дерев прийняття рішень та виведення правил
Дерева прийняття рішень будуються на основі навчальних даних, таким чином вони практично завжди виводять правильні рішення для рядків із навчальної множини. Насправді для знаходження результату нерідко шлях по дереву може виявитися занадто довгим.
Відсікання дерева прийняття рішення полягає в заміні цілого піддерева листком. Заміна відбувається коли дерево виявляє, що очікувана помилка у піддереві є більша ніж у окремому листку. Для прикладу, якщо ми маємо таке просте дерево
було визначено за допомогою одного успішного червоного рядка і двох невдалих синіх рядків, нагадаємо що ці рядки були із навчальних даних, а потім у тестових даних ми виявили три червоні невдачі і один синій успіх, ми можемо застосувати зміну цілого піддерева одним листком невдачі. Таким чином після заміни ми будемо мати лише тві помилки замість п”яти.
Вінстон (Winston) показав як використати тест Фішера щоб визначити чи категорія-властивість дійсно залежить від заданої некатегоризаційної властивості. Якщо це так, то така властивість просто не має знаходитися в жодному шляху дерева.
Квінлан (Quinlan) і Брейман (Breiman) запропонували більш умудрену відсікаючу евристику.
Можна виробити набір правил на основі дерева прийняття рішення: записуємо правило для кожного шляху від кореня до листка.
В такому правилі ліва сторона легко будується із міткок вузлів і з”єднуюючих дуг.
Результуючий набір правил може бути спрощений:
Нехай LHS є ліва сторона правила. Нехай LHS’ є отриманий із LHS
шляхом вилучення деяких умов. Ми можемо впевнено замінити LHS за допомогою
LHS’
в цьому правилі, для кожного вектора із множини навчання, що задовольняє
LHS також задовольняє LHS’.
Правило може бути видалено, якщо “більш ніякі правила є незастосовні”.
This post has been translated from page: http://www.cis.temple.edu/~ingargio/cis587/readings/id3-c45.html, 02/25/2010.
Цей пост був перекладений із сторінки: http://www.cis.temple.edu/~ingargio/cis587/readings/id3-c45.html,
25.03.2010.
2 comments
| Markdown | Result |
|---|---|
| *text* | text |
| **text** | text |
| ***text*** | text |
| `code` | code |
| ~~~ more code ~~~~ |
more code |
| [Link](https://www.example.com) | Link |
| * Listitem |
|
| > Quote | Quote |
а для чого вони тобі?
Так, пару веду завтра по них. Тому і треба.