Обучение дерева решений

Используемый в алгоритме деревьев классификации и регрессии (англ. classification and regression tree, CART) критерий Джини является мерой, насколько часто случайно выбранный элемент из набора неверно помечается, если он случайным образом помечается согласно распределению меток в подмножестве. Критерий Джини может быть вычислен путём суммирования вероятности ${\displaystyle p_{i}}$ элемента с выбранной меткой ${\displaystyle i}$, умноженной на вероятность ${\displaystyle \sum _{k\neq i}p_{k}=1-p_{i}}$ ошибки категоризации этого элемента. Критерий принимает минимум (нуль), когда все случаи в узле попадают в одну целевую категорию.

Для вычисления критерия Джини для набора элементов с ${\displaystyle J}$ классами, предположим, что ${\displaystyle i\in \{1,2,...,J\}}$, и пусть ${\displaystyle p_{i}}$ будет долей элементов, помеченных классом ${\displaystyle i}$ в наборе.

${\displaystyle \operatorname {I} _{G}(p)=\sum _{i=1}^{J}p_{i}\sum _{k\neq i}p_{k}=\sum _{i=1}^{J}p_{i}(1-p_{i})=\sum _{i=1}^{J}(p_{i}-{p_{i}}^{2})=\sum _{i=1}^{J}p_{i}-\sum _{i=1}^{J}{p_{i}}^{2}=1-\sum _{i=1}^{J}{p_{i}}^{2}}$

В алгоритмах генерации деревьев ID3, C4.5 и C5.0. используется Информационный выигрыш, который основывается на понятии энтропии и объёма информации из теории информации.

Энтропия определяется следующим образом

${\displaystyle \mathrm {H} (T)=\operatorname {I} _{E}\left(p_{1},p_{2},...,p_{J}\right)=-\sum _{i=1}^{J}{p_{i}\log _{2}p_{i}}}$,

где ${\displaystyle p_{1},p_{2},...}$ являются долями, в сумме дающими 1, которые представляют процент каждого класса, полученный от разбиения в дереве[15].

$${\displaystyle \overbrace {IG(T,a)} ^{\text{Information Gain}}=\overbrace {\mathrm {H} (T)} ^{\text{Entropy (parent)}}-\overbrace {\mathrm {H} (T|a)} ^{\text{Weighted Sum of Entropy (Children)}}}$$

${\displaystyle =-\sum _{i=1}^{J}p_{i}\log _{2}{p_{i}}-\sum _{a}{p(a)\sum _{i=1}^{J}-\Pr(i|a)\log _{2}{\Pr(i|a)}}}$

В формуле

• Information Gain=Информационный выигрыш
• Entropy (parent)=Энтропия (родитель)
• Weighted Sum of Entropy (Children)=Взвешенная сумма энтропии (наследники)

Информационный выигрыш используется для принятия решения, какой признак использовать для расщепления на каждом шаге построения дерева. Простота является лучшим выбором, так что мы хотим сохранять дерево небольшим. Чтобы это сделать, на каждом шаге нам следует выбрать расщепление, которое приводит к простейшим узлам-наследникам. Обычно используемая мера простоты называется информацией, которая измеряется в битах. Для каждого узла дерева значение информации «представляет ожидаемое количество, которая нужна для определения, должен ли новый объект классифицирован как да или нет, если дано, что пример достигает этого узла»"[15].

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

Расщепление, использующее признак ветер, приводит к двум узлам-наследникам, один узел для признака ветер со значением есть и один со значением нет. В этом наборе данных имеется шесть точек данных со значением есть для ветер, три имеют для целевого значения игра значение да и три имеют значение нет. Восемь оставшихся точек данных для параметра ветер со значением нет содержат два нет и шесть да. Информация ветер=да узла вычисляется с помощью уравнения для энтропии выше. Поскольку имеется равное число да и нет в этом узле, мы имеем

${\displaystyle I_{E}([3,3])=-{\frac {3}{6}}\log _{2}^{}{\frac {3}{6}}-{\frac {3}{6}}\log _{2}^{}{\frac {3}{6}}=-{\frac {1}{2}}\log _{2}^{}{\frac {1}{2}}-{\frac {1}{2}}\log _{2}^{}{\frac {1}{2}}=1}$

Для узла с ветер=нет имелось восемь точек данных, шесть с целевым значением да и два с нет. Таким образом, мы имеем

${\displaystyle I_{E}([6,2])=-{\frac {6}{8}}\log _{2}^{}{\frac {6}{8}}-{\frac {2}{8}}\log _{2}^{}{\frac {2}{8}}=-{\frac {3}{4}}\log _{2}^{}{\frac {3}{4}}-{\frac {1}{4}}\log _{2}^{}{\frac {1}{4}}=0,8112781}$

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

${\displaystyle I_{E}([3,3],[6,2])=I_{E}}$ (ветер - да или нет) ${\displaystyle ={\frac {6}{14}}\cdot 1+{\frac {8}{14}}\cdot 0,8112781=0,8921589}$

Чтобы найти информационный выигрыш расщепления с помощью ветер, мы должны вычислить информацию в данных до расщепления. Исходные данные содержали девять да и пять нет.

${\displaystyle I_{E}([9,5])=-{\frac {9}{14}}\log _{2}^{}{\frac {9}{14}}-{\frac {5}{14}}\log _{2}{\frac {5}{14}}=0,940286}$

Теперь мы можем вычислить информационный выигрыш, получаемый расщеплением по признаку ветер.

${\displaystyle IG}$ (ветер) ${\displaystyle =I_{E}([9,5])-I_{E}([3,3],[6,2])=0,940286-0,8921589=0,0481271}$

Чтобы построить дерево, нужно вычислить информационный выигрыш каждого возможного первого расщепления. Лучшее первое расщепление, это то, которое даёт наибольший информационный выигрыш. Этот процесс повторяется для каждого узла (со смешанными признаками), пока дерево не будет построено. Этот пример заимствован из статьи Виттена, Франка и Холла[15].

Представленное в CART[3] понижение дисперсии часто используется в случаях, когда целевая переменная непрерывна (дерево регрессии), это означает, что использование многих других метрик требовало бы дискретизации перед применением. Понижение дисперсии узла N определяется как общее сокращение дисперсии целевой переменной x как следствие расщепления в этом узле:

${\displaystyle I_{V}(N)={\frac {1}{|S|^{2}}}\sum _{i\in S}\sum _{j\in S}{\frac {1}{2}}(x_{i}-x_{j})^{2}-\left({\frac {1}{|S_{t}|^{2}}}\sum _{i\in S_{t}}\sum _{j\in S_{t}}{\frac {1}{2}}(x_{i}-x_{j})^{2}+{\frac {1}{|S_{f}|^{2}}}\sum _{i\in S_{f}}\sum _{j\in S_{f}}{\frac {1}{2}}(x_{i}-x_{j})^{2}\right)}$,

где ${\displaystyle S}$, ${\displaystyle S_{t}}$ и ${\displaystyle S_{f}}$ являются множеством индексов до расщепления, множеством индексов, для которых тест даёт true и множеством индексов, для которых тест даёт false соответственно. Каждое из слагаемых выше является оценкой величины отклонения, хотя и записанной без прямой ссылки на среднее.

Среди других методов анализа данных деревья решений имеют ряд преимуществ:

• Легки для понимания и интерпретации. Люди способны понять модели деревьев решений после краткого объяснения. Деревья можно изобразить графически таким образом, что их легко интерпретировать, не будучи экспертом[16].
• Способны работать как с числовыми, так и качественными данными[16]. Другие техники обычно специализируются на анализе данных, которые имеют только один тип переменных. (Например, правила отношений могут быть использованы только с категориальными переменными, в то время как нейронные сети могут быть использованы только с числовыми (количественными) переменными или приведёнными к значениям 0/1.)
• Требует малой подготовки данных. Другие техники часто требуют нормализации данных. Поскольку деревья могут обрабатывать качественные независимые переменные, нет необходимости создавать фиктивные переменные[16].
• Использует модель белого ящика. Если данная ситуация наблюдаема в модели, условия объясняются легко булевской логикой. В отличие от этого, в модели чёрного ящика объяснение результатов обычно трудно понять, например, ввиду применения искусственной нейронной сети.
• Можно удостовериться в правильности модели с помощью статистических тестов. Это делает возможным проверять достоверность модели.
• Нестатистический подход, который не делает никаких предположений для тренировочных данных или отклонений предсказания. Например, не делается никаких предположений о распределении, независимости или постоянстве дисперсии
• Хорошо работает с большими наборами данных. Большое количество данных может быть проанализировано с помощью стандартных вычислительных ресурсов за приемлемое время.
• Отражают человеческое принятие решений более тесно, чем другие подходы[16]. Это может быть полезным при моделировании человеческих решений и человеческого поведения.
• Более устойчив к колинеарности.
• По выполненному отбору признаков. Дополнительные бесполезные признаки будут использованы в меньшей мере, так что они могут быть удалены из последующих прогонов.
• Деревья решений можно аппроксимировать любой булевой функцией, эквивалентной XOR[17].

• Деревья могут оказаться существенно неустойчивыми. Небольшие изменения в тренировочных данных могут привести к существенным изменения в дереве, а в конце концов и к конечным предсказаниям[16].
• Известно, что задача обучения до оптимального дерева решений NP-полна по некоторым вопросам оптимальности и даже для простых концепций[18][19]. Как следствие, практические обучающие алгоритмы дерева решений основаны на эвристике, такой как жадный алгоритм, когда локальные оптимальные решения принимаются для каждого узла. Такие алгоритмы не могут гарантировать получение глобально оптимального дерева решений. Чтобы уменьшить эффект локальной оптимальности, предлагаются некоторые методы, такие как дерево двойственного информационного расстояния (англ. dual information distance, DID)[20].

• Обучение дерева решений может создать сверхсложные деревья, которые не обобщаются хорошо из тренировочных данных (что известно как переобучение[21]). Механизмы, такие как обрезка, становятся необходимыми для избежания этой проблемы (за исключением некоторых алгоритмов, таких подходов, как условное умозаключение (англ. Conditional Inference), которое не требует обрезки)[12][13].
• Для данных, имеющих качественные переменные с различным числом уровней информационный выигрыш в дереве решений смещён в сторону атрибутов с бо́льшими уровнями[22]. Однако проблема смещения с помощью условного умозаключения[12], двухступенчатого подхода[23] или адаптивного отбора признаков по отдельным объектам[24].

Многие пакеты интеллектуального анализа данных реализуют один или несколько алгоритмов деревьев решений.

Примерами служат Salford Systems CART (который лицензировал проприетарный код оригинальных авторов CART)[3], IBM SPSS Modeler, RapidMiner, SAS Enterprise Miner, Matlab, R (программное обеспечение с открытым кодом для статистических вычислений, которое включает несколько реализаций CART, таких как пакеты rpart, party и randomForest), Weka (свободно распространяемый пакет программ с открытым кодом для интеллектуального анализа данных, содержащий много алгоритмов дерева решений), Orange, KNIME, Microsoft SQL Server и scikit-learn (свободно распространяемая библиотека на языке Python с открытым кодом для обучения машин).

В дереве решений все пути из корневого узла к листу идут через конъюнкцию (AND). В графе решений возможно использование дизъюнкции (OR) для объединения путей с помощью сообщения минимальной длины (англ. Minimum message length, MML) [25]. Графы решений расширяются далее с разрешением до этого не использованных атрибутов обучать динамически и использовать в различных местах графа[26]. Более общая схема кодирования приводит к лучшим предсказаниям и показателям логарифмических потерь. В общем случае графы решений дают модели с меньшим числом листьев, чем деревья решений.

Эволюционные алгоритмы использовались для исключения локальных оптимальных решений и поиска деревьев решений с меньшим априорным смещением[27][28].

Можно упростить деревья с помощью метода Монте-Карло для цепей Маркова (англ. Markov chain Monte Carlo, MCMC)[29].

Дерево можно просматривать снизу вверх[30].