Вступ
Дерева рішень (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$, ми припиняємо розщеплення, навіть якщо вузол не є чистим.
До кінця навчання (розщеплення) кожен вузол, який спирається на кінець дерева рішень, називається «Листком», оскільки він не є коренем жодного піддерева. Кожен лист представлятиме врожайність класу з найбільшою кількістю зразків.
Висновок
Дерево рішень є одним із найвідоміших алгоритмів машинного навчання завдяки своїй ефективності, інтуїтивно зрозумілій основі та простій реалізації. Далі цей алгоритм можна використовувати з незалежними числовими змінними (дерево рішень Гауса), а також розширити його для вирішення завдань регресії.
