Алгоритм формирования дерева решений по обучающей выборке

Ниже описывается алгоритм формирования дерева решений по обучающей выборке, использованный в системе ID3. Задача, которую решает алгоритм, формулируется следующим образом. Задано:

q множество целевых непересекающихся классов { С ₁, С ₂,..., С _к};

q обучающая выборка S, в которой содержатся объекты более чем одного класса.

Алгоритм использует последовательность тестовых процедур, с помощью котор множество S разделяется на подмножества, содержащие объекты одного класса. Ключевой в алгоритме является процедура построения дерева решений, в котором терминальные узлы соответствуют тестовым процедурам, каждая из которых имеет дело с единственным атрибутом объектов из обучающей выборки. Как увидим ниже, причина заключается в выборе этих тестов.

Пусть Т представляет собой любую тестовую процедуру, имеющую дело с одним из атрибутов, а { О ₁, О ₂,..., О _n}– множество допустимых выходных значений такой процедуры при ее применении к произвольному объекту х. Применение процедуры Т к объекту х обозначим как Т(х). Следовательно, процедура Т(х) разбивает множество S на составляющие {S₁, S₂,..., S_n}, такие, что

S_i={x|T(x)=0_i}.

Такое разделение графически представлено на рис. 20.3.

Рис. 20.3. Дерево разделения объектов обучающей выборки

Если рекурсивно заменять каждый узел S_i на рис. 20.3 поддеревом, то в результате будет построено дерево решений для обучающей выборки S. Как отмечалось выше, ключевым фактором в решении этой проблемы является выбор тестовой процедуры – для каждого поддерева нужно найти наиболее подходящий атрибут, по которомуможновыполнять дальнейшее разделение объектов.

Квинлан (Quinlan) использует для этого заимствованное из теории информации понятие неопределенности. Неопределенность – это число, описывающее множество сообщений М = { m₁, m₂,..., m_n }. Вероятность получения определенного сообщения т_i из этого множества определим как р(т_i). Объем информации, содержащейся в этом сообщении, в таком случае будет равен

I(т_i) = –log p(т_i).

Таким образом, объем информации в сообщении связан с вероятностью получения этого сообщения обратной монотонной зависимостью. Поскольку объем информации измеряется в битах, логарифм в этой формуле берется по основанию 2.

Неопределенность U(M) множества сообщений, обычно называемая энтропией, является, взвешенной суммой количества информации в каждом отдельном сообщении, причем в качестве весовых коэффициентов используются вероятности получения соответствующих сообщений:

U(M) = -S _i p(т_i) log p(т_i), i = 1,..., n.

Ясно, что чем большую неожиданность представляет получение определенного сообщения из числа возможных, тем более оно информативно. Если все сообщения в множестве равновероятны, энтропия множества сообщений достигает максимума. Cпособ, который использует Квинлан, базируется на следующих предположениях.

q Корректное дерево решения, сформированное по обучающей выборке S, будет разделять объекты в той же пропорции, в какой они представлены в этой выборке.

q Для какого-либо объекта, который нужно классифицировать, тестирующую про­цедуру можно рассматривать как источник сообщений об этом объекте.

Пусть n _i – количество объектов в S, принадлежащих классу С_i. Тогда вероятность того, что произвольный объект с, "выдернутый" из S, принадлежит классу С_i, можно оценить по формуле

p(cÎ C_i)=N_i/ | S |,

а количество информации, которое несет такое сообщение, равно

I(cÎ C_i) = -log₂ p (m_i) (cÎ C_i) бит.

Рассмотрим энтропию множества целевых классов, считая их также множеством сообщений {C₁, С₂,..., C_k}. Энтропия также может быть вычислена как взвешенная сумма количества информации в отдельных сообщениях, причем весовые коэффициенты можно определить, учитывая представительство классов в обучающей выборке:

U(M) = - å _i=1,…,k log₂ p (m_i) бит.

Энтропия U (M) соответствует среднему количеству информации, которое необходимо для определения принадлежности произвольного объекта (с Î S) какому-то классу до того, как будет выполнена хотя бы одна тестирующая процедура. После того как соответствующая тестирующая процедура Т выполнит разделение S на подмножества { S₁, S₂,..., S_n }, энтропия будет определяться соотношением

U_T(S) = - å _i=1,…,n (| S |/| S_i) ´ U (S_i).

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

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

G_S(T) = U(S) – U_T(S).

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

Вернемся к нашему примеру с погодой и посмотрим, как эти формулы интерпретируются в самом простом случае, когда множество целевых классов включает всего два элемента. Пусть р – число объектов класса П в множестве обучающей выборки S, а п – число объектов класса Н в этом же множестве. Таким образом, произвольный объект принадлежит к классу П с вероятностью р/(р + п), а к классу Н – с вероятностью п/(р + п). Ожидаемое количество информации в множестве сообщений M = {П, Н} равно

U (M) = - р/ (р + n) log₂(p/ (p + n)) – n/ (р + n) log₂(n/ (p + n)).

Пусть тестирующая процедура Т, как и ранее, разделяет множество S на подмножества { S₁, S₂,..., S_n }, и предположим, что каждый компонент S_i содержит p_i объектов класса П и n_i объектов класса Н. Тогда энтропия каждого подмножества S_i будет равна

U (S) = - р_i / (р_i + n_i) log₂(p_i / (p_i + n_i)) – n_i / (р_i + n_i) log₂(n_i / (p_i + n_i)).

Ожидаемое количество информации в части дерева, включающейкорневойузел, можно представить взвешенной суммой:

U_T(S) = - å _i=1,…,n ((р_i + n_i) / (p + n)) ´ U (S_i).

Отношение (р_i + n_i) / (p + n)соответствует весу каждой i -и ветви дерева, аналогичного приведенному на рис. 20.3. Оно показывает, какая часть всех объектов S принадлежит подмножеству S_i.

В последней версии этого алгоритма, использованной в системе С4.5, Квинлан выбрал отличающуюся эвристику. Использование меры прироста информации в приведенном выше виде приводит к тому, что предпочтение отдается тестирующим процедурам, имеющим наибольшее количество выходных значений { O₁ , O₂ ,..., O_n }.

Несмотря на это, описанный алгоритм успешно применялся при обработке достаточно больших обучающих выборок (см., например, [Quinlan, I983J). Сложность алгоритма зависит в основном от сложности процедуры выбора очередного теста для дальнейшего разделения обучающей выборки на все более мелкие подмножества, а последняя линейно зависит от произведения количества объектов в обучающей выборке на количество атрибутов, использованное дляих представления. Кроме того, система может работать с зашумленными и неполными данными (см. [Qvinlan, 1986, b]).

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

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

В состав программного комплекса С4.5, в котором используется описанный алгоритм, включен модуль С4.5Rules, формирующий из дерева решений набор порождающих правил. В нем применяется эвристика отсечения, с помощью которой дерево решений упрощается. При этом, во-первых, формируемые правила становятся более понятными, а значит, упрощается сопровождение экспертной системы, а во-вторых, они меньше зависят от использованной обучающей выборки. Как упоминалось, в С4.5 также несколько модифицирован критерий отбора тестирующих процедур по сравнению с оригинальным алгоритмом, использованным в ID3.

Недостатком эвристики, основанной на приросте количества информации, является то, что она отдает предпочтение процедурам с наибольшим числом выходных значений { O₁ , O₂ ,..., O_n }. Возьмем, например, крайний случай, когда практически бесполезные тесты будут разделять исходную обучающую выборку на множество классов с единственным представителем в каждом. Это произойдет, если обучающую выборку с медицинскими данными пациентов классифицировать по именам пациентов. Для oписанной эвристики именно такой вариант получит преимущество перед прочими, поскольку U_T(S) будет равно нулю и, следовательно, разность G_S (T) = U (S) - U_T (S) достигнет максимального значения.

Для заданной тестирующей процедуры Т на множестве данных S, которая характеризуется приростом количества информации G_S (T), теперь возьмем в качестве критерия отбора относительный прирост H_S (T), определяемый соотношением

H_S (T) = G_S (T) / V { S),

где

V { S) = - å _i=1,…,n (| S |/| S_i) ´ log₂(| S |/| S_i).

Важно, в чем состоит отличие величины V (S) от U (S). Величина V (S) определяется множеством сообщений { O₁ , O₂ ,..., O_n } или, что то же самое, множеством подмножеств { S₁, S₂,..., S_n }, связанных с выходными значениями тестовой прооцедуры, а не с множеством классов {C₁, С₂,..., C_k}. Таким образом, при вычислении величины V (S) принимается во внимание множество выходных значений теста, а не множество классов.

Новая эвристика состоит в том, что выбирается та тестирующая процедура, которая максимизирует величину относительного прироста количества формации. Теперь упоминавшиеся выше пустые тесты, которым прежний алгоритм отдал бы преимущество, окажутся в самом "хвосте", поскольку знаменатель будет равен log₂(N), где N – количество элементов в обучающей выборке.

Еще один недостаток оригинального алгоритма формирования дерева состоит в том, что он часто формирует сложное дерево, в котором фиксируются несущественные для классификации отличия в элементах обучающей выборки. Один из способов справиться с этой проблемой – использовать правило "останова", которое прекращало бы процесс дальнейшего разделения ветвей дерева при выполнении определенного условия. Но оказазалось, что сформулировать это условие не менее сложно, поэтому Квинлан решил "обрезать" дерево решений после того, как оно будет сформировано алгоритмом. Можно показать, что такое "обрезание" может привести к тому, что новое дерево будет обрабатывать обучающую выборку с ошибками, но с новыми данными оно обычно справляется лучше, чем полное дерево. Проблема "обрезания" довольно сложна, подробно освещается в работах [Mingers, 1989, b] и [Mitchell, 1997], пoлное описание ее реализации в С4.5 можно найти в [Quintan, 1993, Chapter 4].

Чтобы сделать более понятным результат выполнения алгоритма, в системе С4.5 дерево решений преобразуется в набор порождающих правил. Мы уже рассматривали соответствие между отдельным путем на графе решений от корня к листу и порождающим правилом. Условия в правиле – это тестовые процедуры, выполняемые в промежуточных узлах дерева, а заключение правила – отнесение объекта к определенному классу.

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

Квинлан применил следующую стратегию формирования множества правил из дерева решений.

1. Формирование начального варианта множества правил путем перечисления всех путейоткорнядерева к листьям.

2. Обобщение правил и при этом удаление из них условий, которые представляются излишними.

3. Группирование правил в подмножества в соответствии с тем, к каким классам они имеют отношение, а затем удаление из каждого подмножества тех правила, которые не вносят ничего нового в определение соответствующего класса.

4. Упорядочить множества правил по классам и выбрать класс, который будет являться классом по умолчанию.

Выполняемое на шаге 4 упорядочение правил можно рассматривать как примитивную форму механизма разрешения конфликтов (см. главу 5). Порядок классов внутри определенного подмножества теперь не имеет значения. Назначение класса по умолчанию можно считать своего рода правилом по умолчанию, которое действует в том случае, когда не подходит ни одно другое правило.

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

Квинлан сформулировал условия, при которых система С4.5 может быть использована как подходящий инструмент обучения, позволяющий ожидать удовлетворительных результатов. Подход, основанный на использовании дерева решений, можно применять для решения далеко не всех задач классификации. Определенные ограничения свойственны и конкретным алгоритмам, которые использованы в системе С4.5. Необходимым условием успешного применения системы является выполнение следующих требований.

q Перечень классов, с которыми будет оперировать экспертная система, необходимо сформулировать заранее. Другими словами, алгоритмы, положенные в основу функционирования системы С4.5, не способны формировать перечень классов на основе группировки обучающей последовательности объектов. Кроме того, классы должны быть четко очерченными, а не "расплывчатыми" – некоторый объект либо принадлежит к данному классу, либо нет, промежуточных состояний быть не может и классы не должны перекрываться.

q Применяемые методы обучения требуют использования обучающих выборок большого объема. Чем больше объем выборки, тем лучше. При малой длине обучающей выборки на полученных в результате правилах будут сказываться индивидуальные особенности экземпляров в обучающей выборке, что может привести к неверной классификации незнакомых объектов. Методы "усечения" дерева решений, использованные в С4.5, будут работать некорректно, если длина обучающей выборки слишком мала и выборка содержит нетипичные объекты классов.

q Данные в обучающей выборке должны быть представлены в формате "атрибут-значение", т. е. каждый объект должен быть охарактеризован в терминах фиксированного набора атрибутов и их значений для данного объекта. Существуют методы обработки, которые позволяют справиться и с пропущенными атрибутами, – предполагается, что в таких случаях выход соответствующей тестирующей процедуры в вероятностном смысле распределен по закону, определенному на основе тех объектов, в которых такой атрибут определен.

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

Дата добавления: 2015-07-02