Класифікація дерева рішень

Вступ

Дерева рішень (DTs) — це непараметричний контрольований метод навчання, який використовується для класифікації та регресії. Мета полягає в тому, щоб створити модель, яка передбачає значення цільової змінної шляхом вивчення простих правил прийняття рішень, виведених із характеристик даних.

Ентропія

Мета навчання — знайти найкращі розбиття у вузлах, щоб знайти найбільш оптимальне дерево. Розподіл виконується за такими критеріями, як: Ентропія.

Існує багато визначень ентропії, наприклад:

• Ентропія відповідає кількості інформації, що міститься в джерелі інформації.

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

• Ентропія - це метрика, яка вимірює непередбачуваність або забруднення в системі.

У деревах рішень ми розглядатимемо ентропію як міру чистоти всередині вузла. Метою моделі дерева рішень є зменшення ентропії вузлів при кожному розділенні:

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

Ентропія $H$ набору $X$ математично формулюється так:

$$H(X) = - \sum\limits\_{x \in X} p(x) \log p(x)$$

Збільшення інформації

Інформаційний приріст — це різниця між ентропією батьківського вузла та зваженою сумою ентропій вузлів chlid, і, отже, його можна сформулювати так:

$IG(Y, X) = H(Y) - \sum_{x \in unique(X)} P(x|X) \times H(Y | X = x)$

$= H(Y) - \sum_{x \in unique(X)} \frac{X.count(x)}{len(X)} \times H(Y[X == x])$

де:

• $H(.)$ - це ентропія.

• $Y$ — сукупність до розбиття, вона представляє батьківський вузол.

• $X$ - це змінна, яку ми хочемо використовувати для розбиття.

• $x$ є унікальним значенням X.

• $Y[X==x]$ — це розділений список лише зі значеннями $x$.

візьмемо правильний приклад:

Ми обчислимо приріст інформації, коли розділимо батьківський вузол на значення X:

$IG(parent, X) = H(parent) - \sum_{x \in unique(X)} P(x|X) \times H(parent | X = x)$

Спочатку ми обчислюємо ентропію батьківського вузла:

$H(parent) = - P(Y=Blue) \times \log P(Y=Blue) - P(Y=Yellow) \times \log P(Y=Yellow)$

$= - \frac{11}{21} \times \log(\frac{11}{21}) - \frac{10}{21} \times \log(\frac{10}{21}) = 0.3$

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

$unique(X) = [Circle, Square]$

$\sum\_{x \in unique(X)} P(x|X) \times H(Y | X = x) = P(Square|X) \times H(Y | X = Square)$

$+ P(Circle|X) \times H(Y | X = Circle)$

$= \frac{9}{21} \times H(Y | X = Square) + \frac{12}{21} \times H(Y | X = Circle)$

Як от:

• $H(Y | X = Square)$: представляє ентропію першого дочірнього вузла.

• $H(Y | X = Circle)$: представляє ентропію другого дочірнього вузла.

Ми починаємо з першого дочірнього вузла:

$H(Y | X = Square) = - P(Y=Blue | X = Square) \times \log P(Y=Blue| X = Square)$

$- P(Y=Yellow| X = Square) \times \log P(Y=Yellow| X = Square)$

$= - \frac{7}{9} \times \log\frac{7}{9} - \frac{2}{9} \times \log\frac{2}{9} = 0.23$

А потім другий дочірній вузол:

$H(Y | X = Circle) = - P(Y=Blue | X = Circle) \times \log P(Y=Blue| X = Circle)$

$- P(Y=Yellow| X = Circle) \times \log P(Y=Yellow| X = Circle)$

$= - \frac{4}{12} \times \log\frac{4}{12} - \frac{8}{12} \times \log\frac{8}{12} = 0.28$

\

Нарешті, ми підставляємо ентропії у формулу отримання інформації:

$IG(parent, X) = H(parent) - \sum_{x \in unique(X)} P(x|X) \times H(parent | X = x)$

$= 0.3 - \frac{9}{21} \times 0.23 - \frac{12}{21} \times 0.28 = 0.041$

\

\

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

$X^{\*} = \underset{X_i}{\operatorname{argmax}} IG(Y, X_i)$

Коли припинити розділення

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

• Якщо вузол чистий: H(вузол) = 0. Безглуздо далі розбивати вузол.

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

• Мінімальна кількість зразків на вузол: Ми також можемо встановити мінімальну кількість $N$ зразків на вузол. Якщо кількість вибірок на вузол дорівнює $N$, ми припиняємо розщеплення, навіть якщо вузол не є чистим.

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

Висновок

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