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