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

Обновлено на September 03, 2024 4 Прочнет минуты

Введение

Деревья решений (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$, мы прекращаем разделение, даже если узел не является чистым.

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

Заключение

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