Деревья решений — C4.5 математический аппарат | Часть 1

В данной статье будет рассмотрен математический аппарат алгоритма обучения деревьев решений С4.5. Алгоритм был предложен Р. Куинленом как усовершенствованная версия алгоритма ID3, в которую добавлена возможность работы с пропущенными данными. Базовые идеи построения были описаны в статье «Деревья решений: общие принципы».

Прежде чем приступить к описанию алгоритма, определим обязательные требования к структуре обучающего набора данных и непосредственно к самим данным, при выполнении которых алгоритм C4.5 будет работоспособен и даст корректные результаты.

1. Данные должны быть структурированы, т.е. представлять собой таблицу, столбцы которой являются атрибутами (признаками), описывающими предметную область или бизнес-процесс, а строки — обучающие примеры, представляющие собой классифицируемые объекты для которых задана метка класса (поскольку алгоритм использует обучение с учителем). Все строки должны содержать один и тот же набор атрибутов.
2. Один из атрибутов должен быть определен как целевой, т.е. атрибут класса. Для каждого обучающего примера должна быть задана метка класса. Входные атрибуты могут быть как непрерывными, так и дискретными, а атрибут класса — только дискретным, т.е. принимать конечное число уникальных значений.
3. Каждый пример обучающего множества должен однозначно относиться к соответствующему классу. Вероятностные оценки степени принадлежности примеров к классу не используются (такая постановка относится к нечётким деревьям решений). Число классов в обучающем множестве должно быть намного меньше числа обучающих примеров.

Описание алгоритма обучения

Пусть задано обучающее множество S, содержащее m атрибутов и n примеров. Для множества S определено k классов C_1,C_2,…C_k. Задача заключается в построении иерархической классификационной модели в виде дерева решений на основе обучающего множества S.

Построение дерева решений производится сверху вниз — от корневого узла к листьям.

На первом шаге обучения формируется «пустое» дерево, которое состоит только из корневого узла, содержащего всё обучающее множество. Требуется разбить корневой узел на подмножества из которых будут сформированы узлы-потомки. Для этого выбирается один из атрибутов и формируются правила, которые разбивают обучающее множество на подмножества, число которых равно количеству p уникальных значений атрибута.

В результате разбиения получаются p (по числу значений атрибута) подмножеств и, соответственно, формируются p потомков корневого узла, каждому из которых поставлено в соответствие свое подмножество. Затем эта процедура рекурсивно применяется ко всем подмножествам до тех пор, пока не будет выполнено условие остановки обучения.

Основной проблемой при обучении деревьев решений является выбор атрибута, который обеспечит наилучшее разбиение (в соответствии с некоторой мерой качества) в текущем узле. Хотя некоторые алгоритмы обучения деревьев решений допускают использование каждого атрибута только один раз, в нашем случае это ограничение применяться не будет — каждый атрибут может применяться для разбиения произвольное число раз.

Пусть к обучающему множеству применяется правило разбиения, в котором используется атрибут A, принимающий p значений a_1,a_2,…,a_p. В результате будет создано p подмножеств S_1,S_2,…,S_p, куда будут распределены примеры, в которых атрибут A принимает соответствующее значение.

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

Обозначим N(C_jS) число примеров класса C_j в множестве S. Тогда вероятность класса C_j в этом множестве будет:

P= \frac{N(C_jS)}{N(S)}, (1)

где N(S) — общее число примеров в множестве S.

Величину

\text{Info}(S) = -\sum \limits_{i=1}^{m} \frac{N(S_i)}{N(S)}\,\log\,\Bigl(\frac{N(C_jS)}{N(S)}\Bigr), (2)

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

Эту же оценку, полученную после разбиения множества S по атрибуту A, можно записать в виде:

\text{Info}_A(S) = \sum \limits_{i=1}^{k} \frac{N(C_jS)}{N(S)}\text{Info}(S_i), (3)

где S_i — i-й узел, полученный при разбиении по атрибуту A. Тогда для выбора лучшего атрибута ветвления можно использовать следующий критерий:

\text{Gain}(A)=\text{Info}(S)- \text{Info}_A(S), (4)

называемый критерием прироста информации (от англ. gain — прирост, увеличение). Затем значение критерия вычисляется для всех потенциальных атрибутов разбиения, и выбирается тот атрибут, который максимизирует его.

Описанная процедура применяется к подмножествам S_i и далее, до тех пор, пока значения критерия не перестанут значимо увеличиваться при новых разбиениях или будет выполнено другое условие остановки.

Если в процессе построения дерева будет сформирован «пустой» узел, куда не попало ни одного примера, то он преобразуется в лист, который ассоциируется с классом, наиболее часто встречающимся у непосредственного предка узла.

Критерий прироста информации основан на свойстве энтропии, заключающемся в том, что она наибольшая, когда все классы равновероятны, т.е. выбор класса максимально неопределённый, и равна 0, когда все примеры в узле принадлежат одному классу (в этом случае отношение под логарифмом равно 1, а его значение 0). Таким образом, прирост информации отражает увеличение классовой однородности результирующих узлов.

Описанная процедура применима к дискретным атрибутам. В случае непрерывных атрибутов алгоритм работает несколько иначе. Выбирается порог, с которым будут сравниваться все значения. Пусть числовой атрибут X принимает конечное множество значений {x_1,x_2,…,x_p }. Упорядочив примеры по возрастанию значений атрибута, получим, что любое значение, лежащее между x_i и x_{i+1} делит все примеры на два подмножества. Первое подмножество будет содержать значения атрибута x_1,x_2,…,x_i, а второе — {x_{i+1},x_{i+2},…,x_p}.

Тогда в качестве порога можно выбрать среднее:

T_i= \frac{x_i+x_{i+1}}{2}, (5)

Таким образом, задача нахождения порога сводится к рассмотрению n-1 потенциальных пороговых значений {T_1,T_2,…,T_{n-1}}. Последовательно применяя формулы (2), (3) и (4) ко всем потенциальным порогам, выбираем то, которое даёт максимальное значение по критерию (4). Затем, это значение сравнивается со значением критерия (4), рассчитанным для других атрибутов. Если это значение окажется наибольшим из всех атрибутов, то оно выбирается в качестве порога для проверки.

Следует отметить, что все числовые тесты являются бинарными, т.е. делят узел дерева на две ветви.

Практическое использование деревьев решений

После того, как дерево решений построено на обучающем наборе данных и принято решение о его работоспособности (процент правильно распознанных примеров на обучающем множестве достаточно велик), можно приступать к практической работе с деревом — классификации новых объектов.

Новый объект, который требуется классифицировать, поступает сначала в корневой узел дерева, а затем перемещается по узлам, в каждом из которых проверяется соответствие значения атрибута правилу в данном узле, после чего объект перенаправляется в один из узлов-потомков. Процесс продолжается до тех пор, пока объект не окажется в листе. После этого ему присваивается метка класса, ассоциированного с данным листом.

Основным недостатком алгоритма C4.5 являются слишком «ветвистые» деревья, если атрибуты обучающего множества содержат много уникальных значений. Такие деревья как правило трудны для восприятия. Поэтому после построения дерева решений к нему применяется процедура упрощения, в процессе которой производится отсечение ветвей (pruning — стрижка). Она будет рассмотрена в следующей статье.

Литература

Другие материалы по теме:

Деревья решений: общие принципы

Деревья решений — C4.5 математический аппарат | Часть 2