Улучшенный критерий разбиения
Критерий (4) имеет один недостаток – он "предпочитает" атрибуты, которые имеют много значений. Рассмотрим гипотетическую задачу медицинской диагностики, где один из атрибутов идентифицирует личность пациента. Поскольку каждое значение этого атрибута уникальное, то при разбиении множества примеров по этому атрибуту получаются подмножества, содержащие только по одному примеру. Так как все эти множества "однопримерные", то и пример относится, соответственно, к одному единственному классу, тогда
$Info_x\,(T) = 0$, (4)
Значит критерий (4) принимает свое максимальное значение, и несомненно, что именно этот атрибут будет выбран алгоритмом. Однако, если рассмотреть проблему под другим углом – с точки зрения предсказательных способностей построенной модели, то становится очевидным вся бесполезность такой модели. Хотя на практике не так часто встречаются подобные задачи, но, тем не менее, необходимо предусмотреть и такие случаи.
Проблема решается введением некоторой нормализации. Пусть суть информации сообщения, относящегося, к примеру, указывает не на класс, к которому пример принадлежит, а на выход. Тогда, по аналогии с определением Info(T), мы имеем
$split\,\,info\,(X) = -\, \sum \limits_{i=1}^{n} \frac{T_i}{T}\,*\,\log_2\,\Bigl(\frac{T_i}{T}\Bigr)$, (5)
Выражение (5) оценивает потенциальную информацию, получаемую при разбиении множества T на n подмножеств.
Рассмотрим следующее выражение:
$gain\,\,ratio\,(X) = \frac{gain\,(X)}{split\,\,info\,(X)}$, (6)
Пусть выражение (6) является критерием выбора атрибута.
Очевидно, что атрибут, идентифицирующий пациента, не будет высоко оценен критерием (6). Пусть имеется k классов, тогда числитель выражения (6) максимально будет равен log2(k) и пусть n – количество примеров в обучающей выборке и одновременно количество значений атрибута, тогда знаменатель максимально равен log2(n). Если предположить, что количество примеров заведомо больше количества классов, то знаменатель растет быстрее, чем числитель, и, соответственно, выражение будет иметь небольшое значение. Таким образом, мы можем заменить критерий (4) на новый критерий (6), и опять же выбрать тот атрибут, который имеет максимальное значение по критерию. Критерий (4) использовался в алгоритме ID3, критерий (6) введен в модифицированном алгоритме С4.5.
Несмотря на то, что мы улучшили критерий выбора атрибута для разбиения, алгоритм может создавать узлы и листья, содержащие незначительное количество примеров. Чтобы избежать этого, следует воспользоваться еще одним эвристическим правилом: при разбиении множества T, по крайней мере два подмножества должны иметь не меньше заданного минимального количества примеров k (k>1); обычно оно равно 2. В случае невыполнения этого правила, дальнейшее разбиение этого множества прекращается, и соответствующий узел отмечается как лист.
Вероятно, что при таком ограничении может возникнуть ситуация когда примеры ассоциированные с узлом относятся к разным классам. В качестве решения листа выбирается класс, который наиболее часто встречается в узле, если же примеров равное количество из всех классов, то решение дает наиболее часто встречающийся класс у непосредственного предка данного листа.
Возвращаясь к вопросу о выборе порога для числовых атрибутов, можно ввести следующее дополнение: если минимальное число примеров в узле k тогда имеет смысл рассматривать только следующие значения TH1, TH2 … THn-1, так как при разбиении по первым и последним k – 1 порогам в узел попадает меньше k примеров.
Пропущенные данные
Алгоритм построения деревьев решений, рассматриваемый нами, предполагает, что для атрибута, выбираемого в качестве проверки, существуют все значения, хотя явно это нигде не утверждалось. Т.е. для любого примера из обучающей выборки существует значение по этому атрибуту.
Пока мы работаем с синтетическими данными, особых проблем не возникает, мы можем "сгенерировать" нужные данные. Но как только мы обратимся к практической стороне вопроса, то выясняется, что реальные данные далеки от идеальных, и что часто встречаются пропущенные, противоречащие и аномальные данные.
Мы подробнее остановимся на проблеме пропущенных данных. Первое решение, которое лежит на поверхности и само напрашивается – это не учитывать примеры с пропущенными значениями. Следует подчеркнуть, что крайне нежелательно отбрасывать весь пример только потому, что по одному из атрибутов пропущено значение, поскольку мы рискуем потерять много полезной информации.
Тогда нам необходимо выработать процедуру работы с пропущенными данными.
Пусть T – множество обучающих примеров и X – проверка по некоторому атрибуту A. Обозначим через U количество неопределенных значений атрибута A. Изменим формулы (2) и (3) таким образом, чтобы учитывать только те примеры, у которых существуют значения по атрибуту A.
$Info\,(T) = -\,\sum \limits_{j=1}^{k}\frac{freq\,(C_j,\,T)}{\mid T\mid\,-\,U}\,*\,\log_2\,\Bigl( \frac{freq\,(C_j,\,T)}{\mid T\mid\,-\,U}\Bigr)$, (7)
$Info_x\,(T) = \sum \limits_{i=1}^{n} \frac{\mid T_i\mid}{\mid T\mid\,-\,U}\,*\,Info\,(T_i)$, (8)
В этом случае при подсчете freq(Cj, T) учитываются только примеры с существующими значениями атрибута A.
Тогда критерий (4) можно переписать
$Gain\,(X) = \frac{\mid T \mid\,-\,U}{\mid T\mid}\,\bigl(Info\,(T)\,-\,Info_x\,(T)\bigr)$, (9)
Подобным образом изменяется и критерий (6). Если проверка имеет n выходных значений, то критерий (6) считается как в случае, когда исходное множество разделено на n+1 подмножеств.
Пусть теперь проверка X с выходными значениями O1, O2 … On выбран на основе модифицированного критерия (8).
Нам надо решить, что делать с пропущенными данными. Если пример из множества T с известным выходом Oi ассоциирован с подмножеством Ti, вероятность того, что пример из множества Ti равна 1. Пусть тогда каждый пример из подмножества Ti имеет вес, указывающий вероятность того, что пример принадлежит Ti. Если пример имеет значение по атрибуту A, тогда вес равен 1, в противном случае пример ассоциируется со всеми множествами T1, T2 … Tn, с соответствующими весами
$$\frac{|T_1|}{|T|\,-\,U},\,\frac{|T_2|}{|T|\,-\,U},\,\dots,\,\frac{|T_n|}{| T|\,-\,U}$$
Легко убедиться, что
$$\sum_{i=1}^n\frac{|T_i|}{|T|\,-\,U} = 1$$
Вкратце, этот подход можно сформулировать таким образом: предполагается, что пропущенные значения по атрибуту вероятностно распределены пропорционально частоте появления существующих значений.
Классификация новых примеров
Такая же методика применяется, когда дерево используется для классификации новых примеров. Если на каком-то узле дерева при выполнении проверки выясняется, что значение соответствующего атрибута классифицируемого примера пропущено, то алгоритм исследует все возможные пути вниз по дереву и определяет с какой вероятностью пример относится к различным классам. В этом случае, "классификация" – это скорее распределение классов. Как только распределение классов установлено, то класс, имеющий наибольшую вероятность появления, выбирается в качестве ответа дерева решений.
Следует отметить, что кроме подхода, использованного в описываемом алгоритме, применяются и другие методики. В конечном итоге, успех от использования того или иного метода работы с пропущенными данными, напрямую зависит как от предметной области, так и самих данных.
- J. Ross Quinlan. C4.5: Programs for Machine learning. Morgan Kaufmann Publishers 1993.
- К. Шеннон. Работы по теории информации и кибернетике. М. Иностранная литература, 1963
- Ю. М. Коршунов. Математические основы кибернетики. М. Энергоатомиздат, 1987