Вивчайте Розбиття Вузлів

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

Найкращий випадок: усі точки даних у вузлі належать до одного класу;
Найгірший випадок: рівна кількість точок даних для кожного класу.

Імпурність Джині

Щоб оцінити якість розділення, можна обчислити імпурність Джині. Це ймовірність того, що якщо випадково взяти дві точки з вузла (з поверненням), вони будуть різних класів. Чим нижча ця ймовірність (імпурність), тим краще розділення.

Ви можете обчислити індекс Джині для бінарної класифікації за наступною формулою:

\text{gini} = 1 - p_0^2 - p_1^2 = 1 - (\frac{m_0}{m})^2 - (\frac{m_1}{m})^2

Де

$m_i$ — кількість екземплярів класу $i$ у вузлі;
$m$ — кількість екземплярів у вузлі;
$p_i = \frac{m_i}{m}$ — ймовірність вибору класу $i$ .

А для багатокласової класифікації формула має вигляд:

\text{gini} = 1 - \sum_{i=0}^C p_i^2 = 1 - \sum_{i=0}^C(\frac{m_i}{m})^2

Де

$C$ — кількість класів.

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

Щоб розділити вузол рішення, необхідно знайти ознаку для розбиття та порогове значення:

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

Ентропія

Ентропія — це ще одна міра нечіткості. Для задачі бінарної класифікації ентропія $H$ вузла обчислюється за формулою:

H(p) = -p \log_2(p) - (1 - p) \log_2(1 - p)

де:

$p$ — частка позитивних прикладів (клас 1);
$1 - p$ — частка негативних прикладів (клас 0).

Для задачі багатокласової класифікації ентропія $H$ вузла обчислюється за формулою:

H(p_1, p_2, \dots, p_k) = -\sum_{i=1}^{k} p_i \log_2(p_i)

де:

$k$ — кількість класів;
$p_i$ — частка прикладів, що належать до класу $i$ у вузлі.

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

Примітка

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