Одним из интуитивно понятных алгоритмов машинного обучения является дерево решений, которое подобно человеку ищет закономерности в данных путем группировки их по категориям (подгруппам). Рассмотрим как это происходит.
Так, самая популярная реализация производит серию операций разбиения данных на два поднабора по некоторому признаку (k) и порогу (tk). Последние выбираются так, чтобы данные в группах были максимально похожими. Для задач классификации это означает - из одинаковых классов, а задач регрессии - с максимально "близкой" предсказываемой переменной.
На языке математики эти требования формулируются в виде максимизации функции "выигрышей" или минимизации функции "издержек", которые отражают факторы "схожести"/"несхожести". В качестве функции издержек может выступать следующая:
Ее же можно использовать для получения функции "выигрышей" или прироста информации и решить обратную задачу - максимизации:
В задачах классификации в качестве меры загрязненности узла может выступать энтропия:
При более равновероятных распределениях классов энтропия больше, при "перекосах" - меньше (то есть при малых сомнениях в результатах). Построим график энтропии от pi в случае двух возможных исходов. Как можно заметить при pi = ½ она достигает максимального значения:
А теперь рассмотрим пример. Пусть нам надо классифицировать животное (собачка или котик) по набору признаков:
Обозначим p0 - вероятность того, что животное собачка, а p1 - котик. Изначально эти значения равны - 4/10 и 6/10. Подсчитаем энтропию всего набора до разбиения:
E=−∑pi⋅log2pi = - 4/10*log2(4/10) - 6/10*log2(6/10) =
-(-0.53 - 0.44) = 0.97
При разбиении по признаку шерстист (граница любая между 0 и 1):
- группа 0 (шерстист=0): p1=1, E0=0;
- группа 1: p0=4/9, p1=5/9,
E1=-(4/9*log2(4/9) + 5/9log2(5/9)) = -(4/9*(2-3.17) + 5/9(2.32 - 3.17) ) =
-(-0.52-0.47) = 0.99
IG = E - (0.99*0,9) = 0.97 - 0.89 = 0.08
Разбиение по признаку гавкает:
группа 0: p1=1, E0=0
группа 1: p0=4/5, p1=1/5
E1 = -(4/5*log2(4/5) + 1/5*log2(1/5)) =
-(-0.26-0.46)= 0.72
IG = E - 0.72*0.5 = 0.97 - 0.36 =0.61
Разбиение по признаку Лазает по деревьям:
группа 0: p0=1, E0=0
группа 1: p1=1, E1=0
IG = 0.97
Таким образом, первое разбиение дерево выберет по признаку Лазает по деревьям (с максимальным приростом информации). Последующие разбиения будут осуществляться по аналогичному принципу.