Вторая часть математического аппарата построения деревьев решений — алгоритм C4.5. Рассмотрены вопросы улучшения критерия разбиения, работы с пропущенными данными и классификации новых объектов.
Как было отмечено в статье «Деревья решений — C4.5 математический аппарат | Часть 1», критерий разбиения на основе прироста информации отдаёт предпочтение атрибутам, которые содержат большее число уникальных значений. Это связано с тем, что при этом создается большое количество узлов-потомков, дающее в итоге более равномерное распределение классов и, соответственно, меньшую энтропию разбиения. В предельном случае, если все значения атрибута будут уникальными, то для каждого примера будет создано отдельное правило и отдельный лист с единственным классом.
Как следствие, разбиение даст нулевую энтропию:
\text{Info}(S)=0, (1)
и максимальный прирост информации.
Это оптимально с «точки зрения» алгоритма, но абсолютно бессмысленно с практический точки зрения, поскольку:
Решение данной проблемы достаточно очевидно — чтобы алгоритм при выборе разбиения не отдавал предпочтение атрибутам с большим числом уникальных значений, следует ввести некоторый штраф, накладываемый на атрибут за количество созданных с его помощью узлов-потомков. Штраф может быть представлен в виде некоторого коэффициента для значения прироста информации.
Введём в рассмотрение показатель:
\text{Split-Info}(S)=\sum \limits_{i=1}^{p}\frac{N(S_i)}{N(S)}log\frac{N(S_i)}{N(S)}, (2)
который представляет собой оценку потенциальной информации, созданной при разбиении множества S на p подмножеств S_i. Тогда критерий прироста информации с учётом показателя \text{Split-Info}(S) будет иметь вид:
\text{Gain-Ratio}(S)=\frac{\text{Gain}(S)}{\text{Split-Info}(S)}, (3)
Новый критерий позволяет оценить долю информации, полученной при разбиении, которая является «полезной», то есть способствует улучшению классификации. Применение данного показателя, как правило, приводит к выбору более удачного атрибута, чем использование обычного критерия прироста информации.
Смысл этой модификации достаточно прост. N(S_i)N(S) — отношение числа примеров в подмножестве, полученном в результате разбиения, к числу примеров в родительском множестве S. Если в результате разбиения получается большое число подмножеств с небольшим числом примеров, что характерно для переобучения, то показатель \text{Split-Info} растет.
Поскольку он стоит в знаменателе выражения, то \text{Gain-Ratio} есть обычный прирост информации, «оштрафованный» с помощью \text{Split-Info}. Благодаря этому атрибут, для которого \text{Split-Info} растет, имеет меньше шансов быть выбранным для разбиений, чем при использовании обычного \text{Gain}-критерия.
Даже при использовании улучшенного критерия выбора атрибута разбиения, алгоритм может создавать узлы и листья, содержащие незначительное число примеров. Чтобы избежать этого, следует воспользоваться еще одним эвристическим правилом: при разбиении множества S, по крайней мере два подмножества должны иметь не меньше заданного минимального количества примеров u (u>1), обычно равного 2. В случае невыполнения этого правила, дальнейшее разбиение множества прекращается, и соответствующий узел объявляется листом.
Вероятно, что при таком ограничении может возникнуть ситуация когда примеры, попавшие в узел, относятся к разным классам. В качестве класса ассоциированного с листом, выбирается класс, который наиболее часто встречается в этом листе. Если же классы представлены в равных долях, то решение дает наиболее часто встречающийся класс у непосредственного предка данного листа.
Алгоритм С4.5 предполагает, что у атрибута, выбираемого для разбиения, отсутствуют пропущенные значения, хотя явно это нигде не утверждалось. Т.е. для любого примера из обучающей выборки значение данного атрибута существует.
Однако на практике чаще всего приходится иметь дело с «сырыми» данными, в которых присутствуют пропуски. Первое решение, которое лежит на поверхности — это не использовать примеры с пропущенными значениями. Однако исключение примеров из рассмотрения может привести к потере ценной информации, особенно когда исключенных примеров много. Поэтому предпочтительным решением является разработка процедур, позволяющих алгоритму обучения обрабатывать примеры с пропущенными значениями.
Пусть S — множество обучающих примеров и X — разбиение в узле по некоторому атрибуту A_i. Обозначим U количество неопределенных значений атрибута A_i. Изменим формулы (2) и (3) из статьи «Деревья решений — C4.5 математический аппарат | Часть 1» таким образом, чтобы учитывать только те примеры, для которых значения атрибута существуют.
\text{Info}(S)=-\sum \limits_{j=1}^{k}\frac{N(C_j,S)}{N(S)-U}log\frac{N(C_j,S)}{N(S)-U}, (4)
\text{Info}_x(S)=\sum \limits_{i=1}^{n}\frac{N(S_i)}{N(S)-U}\text{Info}(S_i), (5)
где N(C_j,S) — число примеров класса C_j в множестве S, N(S) — общее число примеров множества S. При этом в N(C_j,S) учитываются только примеры, не содержащие пропусков в значениях атрибута A_i.
Тогда критерий (4) из статьи «Деревья решений — C4.5 математический аппарат | Часть 1» может быть преобразован к виду:
\text{Gain}(X)=\frac{N(S)-U}{N(S)}(\text{Info}(S)-\text{Info}_x(S)), (6)
Подобным образом модифицируется и критерий (3). Если разбиение формирует p подмножеств, критерий (3) считается как при p+1 подмножеств.
Пусть разбиение X, формирующее p выходов O_1,O_2,…,O_p, использует атрибут, выбранный по критерию (4) из статьи «Деревья решений — C4.5 математический аппарат | Часть 1». Если пример из множества S, порождающий выход O_i, ассоциирован с подмножеством S_i, то вероятность того, что пример принадлежит подмножеству S_i равна 1. Тогда каждый пример из S_i имеет вес, отражающий вероятность того, что пример принадлежит S_i.
Если пример содержит значение атрибута A_i, то вес примера равен 1. В противном случае пример ассоциируется со всеми подмножествами S_1,S_2,…,S_p с соответствующими весами:
\frac{N(S_1)}{N(S)-U},\frac{N(S_2)}{N(S)-U},…,\frac{N(S_p)}{N(S)-U}, (7)
Несложно убедиться, что
\sum \limits_{i=1}^{p}\frac{N(S_i)}{N(S)-U}=1, (8)
Таким образом, этот подход можно сформулировать так: предполагается, что пропущенные значения по атрибуту распределены пропорционально частоте появления существующих значений.
Такая же методика применяется, когда дерево используется для классификации новых объектов. Если на каком-то узле дерева при выполнении проверки выясняется, что значение соответствующего атрибута классифицируемого примера пропущено, то алгоритм исследует все возможные пути вниз по дереву и определяет с какой вероятностью пример относится к различным классам. В этом случае, «классификация» — это скорее распределение классов. Как только распределение классов установлено, то класс, имеющий наибольшую вероятность появления, выбирается в качестве ответа дерева решений.
Следует отметить, что кроме подхода, использованного в описываемом алгоритме, применяются и другие методики. В конечном итоге, успех от использования того или иного метода работы с пропущенными данными, напрямую зависит как от предметной области, так и самих данных.
Другие материалы по теме:
