Почему Энтропия используется для принятия решений в Дереве решений??

Если вы новичок в машинном обучении, то к вам наверняка пришло сомнение, что «почему энтропия имеет решающее значение для принятия решения в DT???». Давайте углубимся в тему.

Что такое энтропия?

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

где pi — вероятность i-го класса.

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

Как мы знаем, энтропия — это мера беспорядка или неопределенности, т. е. энтропия — это показатель того, насколько беспорядочны ваши данные.

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

К счастью, визуальный осмотр можно заменить более математическим подходом к данным. Существует математическая функция для оценки беспорядка среди математических объектов, и мы можем применить ее к нашим данным. Требование этой функции состоит в том, что она обеспечивает минимальное значение, если в наборе есть однотипные объекты, и максимальное значение, если в наборе происходит равномерное смешивание объектов с разными метками (или категориями).

Почему энтропия в дереве решений?

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

На приведенном выше рисунке показан процесс разделения. у нас есть набор зеленых и фиолетовых кругов. Решение начинается с вычисления значений признаков внутри исходного набора. В зависимости от их значений они разбиты на два набора. В этом примере после разбиения набор выглядит более аккуратным, так как большинство зеленых кругов находится в наборе1, а большинство фиолетовых кружков — в наборе2.

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

На каждом шаге, каждом разветвлении требуется уменьшение энтропии, поэтому эта величина вычисляется до разреза и после разреза. Если он уменьшится, разбиение будет подтверждено, и мы сможем перейти к следующему шагу, в противном случае мы должны попытаться разбить другой признак или остановить эту ветвь.

До и после решения наборы разные и имеют разные размеры. Тем не менее, энтропию между этими наборами можно сравнить, используя взвешенную сумму, как мы увидим в следующем разделе.

Математика энтропии

Предположим, у нас есть N элементов, и эти элементы делятся на две категории: n имеют метку1 и m=N-n элементов имеют метку2. Введем вероятности двух меток:

Энтропия множества определяется следующим уравнением:

Набор или узел является чистым, если он содержит похожие элементы (т. е. элементы с одинаковыми метками), и беспорядочным, если он содержит элементы с разными метками. Когда в наборе нет элемента с меткой 1 (p=0) или если набор полон элементов с меткой 1 (p=1), энтропия равна нулю. Если у вас есть половина с меткой 1, половина с меткой 2 (p=1/2), энтропия максимальна (равна 1, так как это логарифмическая база 2).

Эта функция количественно определяет беспорядочность данных.

Как оценивается энтропия?

В деревьях решений при каждом разветвлении входной набор делится на 2. Давайте разберемся, как вы сравниваете энтропию до и после разделения. Представьте, что вы начинаете с беспорядочного набора с энтропией один (половина/половина, p=q). В худшем случае он может быть разделен на 2 беспорядочных набора, где половина элементов имеет метку 1, а другая половина имеет метку 2 в каждом наборе. Следовательно, энтропия каждого из двух результирующих наборов равна 1. В этом сценарии беспорядок не изменился, и мы хотели бы иметь одинаковую энтропию до и после разделения. Мы не можем просто суммировать энтропии двух наборов. Решение, часто используемое в математике, состоит в том, чтобы вычислить среднюю энтропию двух наборов. В данном случае среднее значение равно единице. Однако в деревьях решений вместо этого вычисляется взвешенная сумма энтропий (взвешенная по размеру двух подмножеств):

где N1 и N2 — количество элементов каждого набора после разделения, а E1 и E2 — их соответствующая энтропия. Это придает большее значение набору, который больше (если есть). Идея состоит в том, что будет немного лучше, если большой набор станет более аккуратным, так как для его уборки требуется больше усилий. Представьте себе наихудший случай, когда набор из 1000 элементов разделен на две части: набор из 999 элементов и набор из 1 элемента. Последний набор имеет нулевую энтропию, поскольку содержит только один элемент, одну метку. Но это не очень важно, так как подавляющее большинство данных все еще беспорядочны в большом наборе. Таким образом, двум наборам следует придавать значение относительно их размера.

Если у вас более 2 меток, вы можете обобщить формулу энтропии следующим образом:

где pi — отношение элементов каждой метки в наборе. Это довольно просто!

Заключение

Мы видели, что энтропия — это не просто математическая формула. У него простая интерпретация, понятная каждому. Если вы теперь видите, что такое энтропия, у вас должно быть более четкое представление о том, что делают деревья решений.

Используя энтропию, деревья решений упорядочивают больше, чем классифицируют данные.