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

Оновлено на September 03, 2024 4 хвилини читають

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

Вступ

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

Ентропія

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

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

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

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

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

entropy

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

entropy_reductioin

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

Ентропія $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$.

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

entropy_reductioin

Ми обчислимо приріст інформації, коли розділимо батьківський вузол на значення 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$, ми припиняємо розщеплення, навіть якщо вузол не є чистим.

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

Висновок

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