Вопрос или проблема
Я пытаюсь построить алгоритм дерева решений, но, кажется, неправильно истолковал, как работает прирост информации.
Допустим, у нас есть сбалансированная задача классификации.
Тогда начальная энтропия должна равняться 1.
Давайте определим прирост информации следующим образом:
info_gain = initial_entropy - weighted_average(entropy(left_node) + entropy(right_node))
Мы получаем информацию, если уменьшаем начальную энтропию, т.е.
если info_gain > 0. Если info_gain == 0
это означает
weighted_average(entropy(left_node) + entropy(right_node)) == initial_entropy.
Допустим, у нас есть 4 признака так, что
weighted_average(entropy(left_node) + entropy(right_node)) идет в этом порядке
wa_of_feature_0 > wa_of_feature_1 > … > wa_of_feature_4.
Чем больше прирост информации превышает 0, тем больше признак упорядочивает систему.
Таким образом, на основе наших 4 признаков максимальный прирост информации будет
info_gain_max = initial_entropy - wa_of_feature_4
поскольку это даст нам большее число, чем использование wa_of_feature_n, где 1<=n<4.
Это правильная интерпретация?
Давайте начнем с определения того, что вы пытаетесь достичь в дереве решений.
Таким образом, мы хотим дерево, которое правильно классифицирует данные? Для этого из числа доступных признаков я хочу выбрать те признаки, которые дают мне наилучшую информацию о моих классах, т.е. насколько хорошо признак делит мои данные? что поможет мне лучше классифицировать.
Теперь энтропия – это такая техника, которая помогает мне понять, насколько “чист” мой поднабор, т.е. если я выбираю feature_1 для деления, насколько хорошо он разобьет мои данные так, что большинство меток классов будут из одного класса.
Таким образом, энтропия является мерой нечистоты. Если все экземпляры из одного класса, то нечистота равна 0, следовательно, E = 0, если количество экземпляров из обоих классов одинаково, то нечистота максимальна E=1.
Теперь нам нужно выбрать, какой атрибут лучше всего разделить первым, а затем рекурсивно, какие из них позже?
Вот здесь появляется прирост информации.
Прирост информации просто говорит мне, насколько полезен/хорош атрибут по сравнению с остальными атрибутами. Для этого мы сравниваем энтропию “родительского узла” до разбиения с нечистотой “дочерних узлов” после разбиения. Чем больше разница, тем лучше условие теста атрибута.
Более высокий прирост = более чистый класс
Таким образом, начальная энтропия должна равняться 1.
1 – это максимальная энтропия, это означает, что если у меня 4 экземпляра, 2 говорят + и 2 говорят -, следовательно, они очень нечисты. Это также может быть 0, если классы как 4+ и 0 -. и так далее по расчетам.
Мы получаем информацию, если уменьшаем начальную энтропию.
эта начальная энтропия является энтропией набора данных до разбиения или энтропией родительского узла. Это зависит от данных.
Чем больше прирост информации больше 0, тем больше признак упорядочивает
систему.
Нет, это не сравнивается с 0, а с приростами всех атрибутов друг с другом,
gain(w_1) = .4, g(W_2) = 1.2
Тогда наибольший прирост принадлежит W_2, следовательно, ДР будет использовать W_2 для разбиения.
Представьте, что у вас есть набор данных с 3 атрибутами A1, A2, A3, тогда какой атрибут вы должны протестировать первым?
Итак, вычислите энтропию полного набора, т.е. E(complete)
так же E(A1), E(A2), E(A3),
Теперь
gain(A1) = E(complete) - E(A1) = .2, gain(A2) = E(complete) - E(A2) = .5, gain(A3) = E(complete) - E(A3) = 1
наибольший прирост = 1, поэтому мы разделим по A3.
Если у атрибутов одинаковый прирост, то мы учитываем порядок.
Мы сравниваем энтропию дочерних узлов с родительской. Поэтому мы должны взвесить детей в зависимости от размера разбиения, а не 50-50.
Интуиция –
(Очень большой “уродливый” ребенок и “великолепный” маленький ребенок)
Взвешивание этих двух, не учитывая соответствующий размер, даст вам приемлемую энтропию, но на самом деле это не хорошее разбиение.
Пример кода
a = [0, 0, 0, 0, 1, 1, 1, 1, 1, 1]
p(0) = 0.4, p(1) = 0.6
entropy = -(0.4*np.log2(0.4) + 0.6*np.log2(0.6)) #Это равно - 0.97
#Давайте разберем и рассчитаем взвешенный спад
a1 = [0]; a2 = [0, 0, 0, 1, 1, 1, 1, 1, 1]
#Без веса
a1 = 0
a2 = -(0.33*np.log2(0.66) + 0.66*np.log2(0.33)) #Это равно - 1.25
Average = 1.25/2 #Это равно - 0.625
Выглядит как большой спад (0.97 –> 0.625) в энтропии, но данные не выглядят иначе, чем у родителя
#С весом
a1 = 0
a2 = -(0.33*np.log2(0.66) + 0.66*np.log2(0.33)) #Это равно - 1.25
Weighted average = (9/10) * 1.25 #Это равно - 1.125
Это больше (0.97 –> 1.125), чем у родителя
Ответ или решение
Индукция деревьев решений с использованием информации о прибыли и энтропии
Индукция деревьев решений — это мощная техника машинного обучения, которая позволяет эффективно решать задачи классификации и регрессии. В этой статье мы сосредоточимся на ключевых концепциях, таких как энтропия и информация о прибыли, которые играют центральную роль в этой методологии.
Что такое энтропия?
Энтропия — это мера неопределенности или беспорядка в наборе данных. В контексте классификации, энтропия показывает, насколько чисты или упорядочены классы в наборе данных. Основная формула для расчета энтропии выглядит следующим образом:
[
E(S) = – \sum_{i=1}^{c} p_i \log_2(p_i)
]
где ( p_i ) — это вероятности классов в наборе данных ( S ), а ( c ) — общее количество классов.
Энтропия варьируется от 0 (полная чистота, когда все экземпляры принадлежат одному классу) до 1 (максимальная неопределенность, когда классы распределены равномерно).
Понятие информации о прибыли
Информация о прибыли — это ключевая метрика, используемая для выбора оптимального прогнозного атрибута в узлах дерева решений. Она измеряет уменьшение неопределенности (или увеличение чистоты) при разделении данных на основе заданного атрибута. Степень информации о прибыли определяется как разница между энтропией родительского узла и взвешенной средней энтропией дочерних узлов после разбиения:
[
\text{info_gain} = E(S) – \left( \frac{|S{left}|}{|S|} E(S{left}) + \frac{|S{right}|}{|S|} E(S{right}) \right)
]
где:
- ( E(S) ) — энтропия исходного набора данных.
- ( S{left} ) и ( S{right} ) — поднаборы данных, полученные после разбиения.
- ( |S| ) — общее количество экземпляров в наборе данных.
Процесс выбора наилучшего атрибута
При индукции дерева решений важно правильно выбрать атрибут, который даст наибольшее увеличение информации о прибыли. Это делается путем вычисления информации о прибыли для всех доступных атрибутов, используя описанную выше формулу. Предположим, мы имеем несколько атрибутов:
- Атрибут 0
- Атрибут 1
- Атрибут 2
- Атрибут 3
Если результаты вычислений по атрибутам показывают, что:
[
\text{info_gain}(\text{A0}) > \text{info_gain}(\text{A1}) > \text{info_gain}(\text{A2}) > \text{info_gain}(\text{A3}),
]
то мы выбираем атрибут 0 для дальнейшего разбиения, так как он дает максимальную информацию о прибыли.
Взвешивание дочерних узлов
При вычислении взвешенной энтропии дочерних узлов важно учитывать размер каждого дочернего узла. Например, если один дочерний узел значительно больше другого, не следует просто усреднять их энтропии. Это может привести к искажению результатов:
[
\text{Weighted Average Entropy} = \frac{|S{left}|}{|S|} E(S{left}) + \frac{|S{right}|}{|S|} E(S{right}).
]
Таким образом, правильно взвешивая энтропии по размеру соответствующих узлов, можно более точно оценить качество разбиения.
Заключение
Индукция деревьев решений, использующая концепции энтропии и информации о прибыли, предоставляет мощную методологию для улучшения классификации в наборе данных. Полное понимание этих факторов позволяет создать более эффективные модели, способные лучше справляться с задачами предсказания.
Теперь, когда вы более подробно ознакомлены с основными концепциями, вы сможете более уверенно применять индукцию деревьев решений, выбирая наиболее информативные атрибуты для построения вашего дерева.