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

Введение

Деревья решений (DT) — это непараметрический метод обучения с учителем, используемый для классификации и регрессии. Цель состоит в том, чтобы создать модель, которая прогнозирует значение целевой переменной, изучая простые правила принятия решений, выведенные из особенностей данных.

Энтропия

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

Существует множество определений энтропии, например:

Энтропия соответствует количеству информации, содержащейся в источнике информации.
Энтропию также можно рассматривать как случайность или меру неожиданности в наборе.

— Энтропия — это показатель, измеряющий непредсказуемость или нечистоту в системе.

В деревьях решений мы будем рассматривать энтропию как меру чистоты внутри узла. Цель модели дерева решений — уменьшить энтропию узлов при каждом разделении:

Таким образом, мы хотим максимизировать разницу между энтропией родительского узла и энтропией дочерних узлов. Эта разница называется Приростом информации.

Энтропия $H$ множества $X$ математически формулируется следующим образом:

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

Получение информации

Прирост информации — это разница между энтропией родительского узла и взвешенной суммой энтропий дочерних узлов, поэтому ее можно сформулировать следующим образом:

$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(node) = 0. Дальнейшее разбиение узла бессмысленно.
Максимальное количество глубин: Мы можем установить максимальную глубину, которой может достичь модель. Это означает, что даже если узел не является чистым, расщепление прекращается.
Минимальное количество выборок на узел: Мы также можем установить минимальное количество $N$ выборок на узел. Если количество выборок на узел равно $N$ , мы прекращаем разделение, даже если узел не является чистым.

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

Заключение

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