Я предполагаю, что энтропия упоминалась в контексте построения деревьев решений .
Чтобы проиллюстрировать, представьте себе задачу обучения до классификации имен по мужским / женским группам. Это дает список имен, каждое из которых помечено либо m, либо f, мы хотим узнать модель , которая соответствует данным и может использоваться для прогнозирования пола нового невидимого имени .
name gender
----------------- Now we want to predict
Ashley f the gender of "Amro" (my name)
Brian m
Caroline f
David m
Первый шаг - , решение , что функции данных относятся к целевому классу, который мы хотим предсказать. Некоторые примеры функций включают в себя: первая / последняя буква, длина, количество гласных, заканчивается ли это гласной и т. Д. Итак, после извлечения функции наши данные выглядят следующим образом:
# name ends-vowel num-vowels length gender
# ------------------------------------------------
Ashley 1 3 6 f
Brian 0 2 5 m
Caroline 1 4 8 f
David 0 2 5 m
Цель состоит в том, чтобы построить дерево решений . Примером дерева будет:
length<7
| num-vowels<3: male
| num-vowels>=3
| | ends-vowel=1: female
| | ends-vowel=0: male
length>=7
| length=5: male
в основном каждый узел представляет тест, выполненный для одного атрибута, и мы идем влево или вправо в зависимости от результата теста. Мы продолжаем обходить дерево, пока не достигнем конечного узла, который содержит прогноз класса (m или f)
Итак, если мы запустим имя Amro по этому дереву, мы начнем с проверки " это длина <7? </em>" и ответом будет yes , поэтому мы идем вниз по этой ветке. После ветки следующий тест « - это число гласных <3? </em>» снова оценивается как true . Это приводит к листовому узлу, помеченному m, и, таким образом, предсказание составляет мужской (который, как мне кажется, таков, поэтому дерево предсказало результат правильно ).
Дерево решений построено сверху вниз , но вопрос в том, как выбрать какой атрибут для разделения на каждом узле? Ответ заключается в том, чтобы найти функцию, которая наилучшим образом разбивает целевой класс на самые чистые из возможных дочерних узлов (то есть: узлы, которые не содержат смесь как мужского, так и женского, а скорее чистые узлы только с одним классом).
Эта мера чистоты называется информации . Он представляет ожидаемое количество информации , которое потребуется, чтобы указать, должен ли новый экземпляр (имя) быть классифицирован как мужской или женский, учитывая пример, который достиг узла. Мы рассчитываем это
основано на количестве мужских и женских классов в узле.
Энтропия , с другой стороны, является мерой примеси (противоположность). Он определен для двоичного класса со значениями a / b как:
Entropy = - p(a)*log(p(a)) - p(b)*log(p(b))
Эта двоичная энтропийная функция изображена на рисунке ниже (случайная величина может принимать одно из двух значений). Он достигает своего максимума, когда вероятность составляет p=1/2, то есть p(X=a)=0.5 или аналогично p(X=b)=0.5 с вероятностью 50% / 50% либо a, либо b (неопределенность максимальная). Функция энтропии находится на нулевом минимуме, когда вероятность равна p=1 или p=0 с полной уверенностью (p(X=a)=1 или p(X=a)=0 соответственно, последнее подразумевает p(X=b)=1).
Конечно, определение энтропии можно обобщить для дискретной случайной величины X с N результатами (а не только двумя):
(log в формуле обычно принимается как логарифм к основанию 2 )
Возвращаясь к нашей задаче классификации имен, давайте рассмотрим пример. Представьте, что в какой-то момент в процессе построения дерева мы рассматривали следующее разбиение:
ends-vowel
[9m,5f] <--- the [..,..] notation represents the class
/ \ distribution of instances that reached a node
=1 =0
------- -------
[3m,4f] [6m,1f]
Как видите, до раскола у нас было 9 мужчин и 5 женщин, то есть P(m)=9/14 и P(f)=5/14. Согласно определению энтропии:
Entropy_before = - (5/14)*log2(5/14) - (9/14)*log2(9/14) = 0.9403
Далее мы сравним ее с энтропией, вычисленной после рассмотрения разбиения, рассматривая две дочерние ветви. В левой ветви ends-vowel=1 имеем:
Entropy_left = - (3/7)*log2(3/7) - (4/7)*log2(4/7) = 0.9852
и правая ветвь ends-vowel=0, имеем:
Entropy_right = - (6/7)*log2(6/7) - (1/7)*log2(1/7) = 0.5917
Мы объединяем левую / правую энтропию, используя количество экземпляров на каждую ветвь как весовой коэффициент (7 экземпляров пошли влево, а 7 экземпляров - вправо), и получаем окончательную энтропию после разделения:
Entropy_after = 7/14*Entropy_left + 7/14*Entropy_right = 0.7885
Теперь, сравнивая энтропию до и после разделения, мы получаем меру прироста информации или того, сколько информации мы получили, выполнив разделение с использованием этой конкретной функции:
Information_Gain = Entropy_before - Entropy_after = 0.1518
Вы можете интерпретировать приведенный выше расчет следующим образом: выполнив разбивку с помощью функции end-vowels, мы смогли уменьшить неопределенность в результате прогнозирования поддерева на небольшое значение 0,1518 (измерено в * 1144). * биты как единицы информации ).
В каждом узле дерева этот расчет выполняется для каждого объекта, и объект с наибольшим информационным приростом выбирается для разделения жадным способом (таким образом, в пользу функции, которые производят pure , расщепляется с низкой неопределенностью / энтропией). Этот процесс применяется рекурсивно от корневого узла вниз и останавливается, когда конечный узел содержит экземпляры, имеющие все один и тот же класс (нет необходимости разбивать его дальше).
Обратите внимание, что я пропустил некоторые подробности , которые выходят за рамки этого поста, включая способы обработки числовых функций , пропущенных значений , переоснащение и обрезка деревьев и т.д ..