Реализация процедуры обучения с помощью дерева решения

Наметим структуру процедуры логического вывода деревьев решения следующим образом: induce_tree( Attributes, Examples, Tree)

Часть II. Применение языка Prolog в области искусственного интеллекта

где Tree — дерево решения, полученное путем логического вывода из примеров Examples с помощью атрибутов в списке Attributes. Если рассматриваются приме­ры и атрибуты, приведенные в листинге 18.1, то можно собрать все примеры и дос­тупные атрибуты в списки, применяемые в качестве параметров для рассматривае­мой процедуры логического вывода, следующим образом:

induce tree! Tree) :-

findalK example ( Class, Obj ) , example( Class, Obj ) , Examples), findalK Att, attribute; Att, ), attributes}, induce_tree( Attributes, Examples, Tree).

Форма дерева определяется в соответствии с описанными ниже тремя случаями.

1. Tree = null, если множество примеров является пустым.

2. Tree = leaf ( Class), если все примеры относятся к одному и тому же клас­су Class.

3. Tree = tree{ Attribute, [ Vail : SubTreel, Val2 : SubTree2, ... ]), если примеры относятся больше чем к одному классу, Attribute является корнем дерева, Vail, Val2, ... представляют собой значения атрибута Attribute, aSubTreel, SubTree2, ... - соответствующие поддеревья решения.

Эти три случая учитываются с помощью следующих трех предложений:

% induce tree! Attributes, Examples, Tree) iadtaee_tr~ie (_, [], null) ;- 1.

induce treef , [ example ( Class, i I Examples], leaf С Class)) :-
not ( member t example ( ClassX, ~_), Examples), % Других примеров
classx \== Class), !. % иного класса нет

induce tre«( Attributes, Examples, trees Attribute, SubTrees)) :-

22Б£.Att5&иValues], restAtts, ^... —.,.

Процедура induce trees осуществляет логический вывод решения SubTrees дляподмножеств множества Examples в соответствии со значениями Values атрибута Attribute следующим образом:

% induce trees! Att, Vals, RestAtts, Examples, SubTrees)
induce_tre_es [ -, [], _, _, 111. % Нет ни атрибутов, ни поддеревьев

induce trees( Att, [vail | vals], RestAtts, Exs, [Vail : Treel | Trees]) :-attvll subsetRAtt = ,ailxa ExseS Exam,leSubset!,

Выражениеattval_subset( Attribute = Value, Examples, Subset) являет­ся истинным, если Subset -- это подмножество примеров в множестве Examples, которые удовлетворяют условию Attribute = Value следующим образом:

attval_subsett Attribute Value, Examples, ExampleSubset) :-

Определение предиката satisfy* Object, Description) приведено в листин­ге 18.3. Предикат choose_attribute позволяет выбрать атрибут, который обеспечи­вает наилучшее распознавание отдельных классов. Для этого требуется использовать критерий определения количества посторонних включений. Следующее предложение позволяет свести к минимуму значение выбранного критерия оценки количества по­сторонних включений с помощью предиката setof. Этот предикат упорядочивает доступные атрибуты по возрастанию количества посторонних включений, как пока­зано ниже.

Глава 18.Машинное обучение 431

choose_a-tribute( Atts, Examples, BestAtc) :-setoft Impurity/Att,

(membert Att, Atts), irapurityl . Examples, ktt, Impurity)), [ Hinlmpurity/BestAtt I _)) .

Процедура

impurityl[ Examples, Attribute, Impurity)

реализует выбранный критерий определения количества посторонних включений; где Impurity — это результирующее значение количества посторонних включений для подмножеств примеров после разделения списка Examples в соответствии со значе­ниями атрибута Attribute.

Упражнения

18.3. Реализуйте выбранный критерий определения количества посторонних вклю­
чений, разработав для этого предикат impurity!. В качестве такого критерия
может, например, использоваться остаточное информационное наполнение или
индекс Gini, как описано выше в данном разделе. Для примеров, приведен­
ных в листинге 18.1, и атрибута size применение индекса Gini в качестве
критерия количества посторонних включений позволяет получить следующие
результаты:

?- Examples = ... Примеры, приведенные в листинге 18.1 impurityl ( Examples, size. Impurity). Impurity - 0.647619

А если вероятности аппроксимируются с помощью относительных частот, то значение Impurity вычисляется так:

Impurity = Gini С size)

» р(small)*(р(nut I small)*p(screw | small)+...)+p(large)*(...)

= 7/12 * (3/7 * 2/7 + ...) + 5/12 *(...) = 7/12 * 0.653061 - 5/12 * 0.64 = 0.647619

18.4. Завершите разработку программы логического вывода дерева, приведенной в
этом разделе, и проверьте ее работу на некоторой задаче обучения, например,
показанной в листинге 18.1. Обратите внимание на то, что процедура
choose_attribute, в которой используется предикат setof, является очень
неэффективной и должна быть усовершенствована. Введите также в действие
процедуру

show! DecisionTree!

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

holes none size

small ==> screw large ==> pen 1

shape

long *=> key compact — ■■ nut other ==> null 2

size

small :—> key large —> scissors 3 ==> null many ■="> null

432 Часть II.Применение языка Prolog в области искусственного интеллекта

18.6. Обучение позашумленным данным и отсечение частей деревьев

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

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

В качестве примера рассмотрим ситуацию, в которой необходимо сформировать поддерево дерева решения и текущим подмножеством объектов для обучения являет­ся S. Предположим, что в множестве S имеется 100 объектов, причем 99 из них от­носятся к классу С1, а один — к классу С2. Если известно, что в учебных данных присутствует шум и что все объекты, выбранные до сих пор в дереве решения, име­ют одни и те же значения атрибутов, то можно с полной уверенностью предполо­жить, что появление объекта класса С2 в множестве S является лишь результатом ошибки в данных. Если это действительно так, то лучше всего проигнорировать та­кой объект и просто возвратить лист дерева решения, обозначенный именем класса С1. Поскольку в этой ситуации основной алгоритм логического вывода дерева дол­жен был бы дальше развертывать дерево решения, то, остановившись в этой точке, мы фактически отсекаем одно из поддеревьев полного дерева решения.

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

Отсечение такого рода, осуществляемое путем прекращения развертывания дере­ва, называется предварительным отсечением (forward pruning), в отличие от другого вида отсечения, называемого последующим отсечением (post-pruning). Последующее отсечение выполняется после того, как обучающаяся программа сформирует полное дерево решения. Затем те части дерева, которые кажутся ненадежными, отсекаются. Такой процесс схематически показан на рис. 18.12. После удаления нижних частей дерева точность распознавания новых данных с помощью этого дерева может повы­ситься. Такое утверждение на первый взгляд кажется парадоксальным, ведь при от­сечении фактически отбрасывается часть информации. Почему же в результате мо­жет повыситься точность?

Глава 18.Машинное обучение

Рис. 18JS. Отсечение частей дерева ре­шения. После отсечения точность распо­знавания может повыситься

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

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

Но остается нерешенной важная задача — как точно определить, какие поддере­вья нужно отсекать, а какие — нет. Если будет выполнено слишком обширное отсе­чение, то может быть отброшена также полезная информация и поэтому точность уменьшится. Итак, как определить, охватывает ли выбранный способ отсечения слиш­ком большую или слишком малую часть дерева? Это — сложный вопрос, и существует несколько методов, которые позволяют найти на него разные, более или менее удовле­творительные ответы. Рассмотрим один из методов последующего отсечения, известный под названием отсечение с минимальной ошибкой (minimal error pruning).

Наиболее важное решение при использовании метода последующего отсечения со­стоит в том, нужно ли отсекать поддеревья ниже указанного узла или нет. Такая си­туация иллюстрируется на рис. 18.13, где Т — дерево решения, корнем которого яв­ляется узел s, Ть Тг, ... — поддеревья дерева Т, pi — вероятности того, что случай­ный объект будет передан из корня ^ в поддерево Т__. Дерево т, в свою очередь, может оказаться поддеревом более крупного дерева решения. Задача состоит в том, чтобы определить необходимость отсечения поддеревьев ниже узла s (т.е. удаления поддеревьев т., ...). Сформулируем некоторый критерий, основанный на принципе минимизации ожидаемой ошибки классификации. Предполагается, что в поддеревь­ях Т_;, ... уже было выполнено оптимальное отсечение их поддеревьев на основании того же критерия.

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

434 Часть II. Применение языка Prolog в области искусственного интеллекта

Выполнить отсечение?

Рис. 18.13. Принцип принятия ре­шения обвтеттии частей дерева решения

1. Если отсечение поддеревьев дерева Т осуществляется непосредственно ниже
узла б, то s становится листом. В таком случае лист s обозначается именем
наиболее вероятного класса С в листе s и все, что находится в этом листе,
классифицируется как относящееся к классу С. Ошибка классификации в лис­
те а представляет собой вероятность того, что случайно выбранный объект, ко­
торый относится к s, принадлежит классу, отличному от С. Такая ошибка на­
зывается статической ошибкой (static error) в листе s и определяется по сле­
дующей формуле:

e(s) = p(class * С I s)

2. Если отсечение дерева не выполнено непосредственно ниже узла s, то ошибка
в этом узле представляет собой взвешенную сумму ошибок E(Ti), E{Ta), ...
дляподдеревьев Tj, T₂.......... отсечение которых выполнено оптимальным обра­
зом. Эта ошибка определяется по следующей формуле:

Р; E(Ti) + Р2 Е{Т₂) + . . .

Такая ошибка называется зафиксированной ошибкой <backed-up error). Таким образом, правило принятия решения об отсечении ниже узла s состоит в следующем: если статическая ошибка меньше или равна зафиксированной ошибке, то выполнять отсечение, в противном случае не выполнять. В соответствии с этим можно определить ошибку дерева Т, в котором отсечение выполнено оптимальным образом, с помощью формулы

Е(Т)

i(e(s),Zj pi E(Ti) )

Безусловно, если Т не имеет поддеревьев, то эта формула принимает вид Е(Т) = е (s) .

Остается определить, как найти оценку статической ошибки e(s), которая сво­дится к вероятности появления в узле з класса С, который чаще всего встречается в этом узле. Фактические данные, которые можно использовать для такой оценки, представляют собой множество примеров, относящихся к узлу s. Предположим, что это множество обозначено как S, общее количество примеров в 5 равно N, а количе­ство экземпляров класса С равно п. Теперь наиболее сложная задача фактически сво­дится к определению вероятности появления экземпляра класса С в узле s. Боль­шинство людей, которые сталкиваются с этой задачей, сразу же решают, что доста­точно взять для этого отношение а/Ш (относительную частоту) для экземпляров класса С в узле s. Такое предложение является резонным, если количество экземп­ляров в узле s достаточно велико, но, безусловно, становится сомнительным, если это количество мало. Например, предположим, что к узлу s относится только один экземпляр класса С. В таком случае процентная доля наиболее вероятного класса со­ставляет 1/1 * 100 = 100%, а оценка ошибки равна 0/1 = 0. Но если в узле s име­ется только один экземпляр класса, то такая оценка становится статистически пол-

тава 18. Машинное обучение

ностью недостоверной. Допустим, что мы смогли получить еще один учебный пример для узла s и этот пример относится к другому классу. В таком случае единственный дополнительный пример резко снизит вероятность оценки — до 1/2 * 100 = 50%!

Еще одной наглядной иллюстрацией к тому, насколько сложна задача оценки ве­роятностей, могут служить результаты подбрасывания определенной монеты. Пред­положим, что в первом эксперименте с монетой выпал орел. Итак, в соответствии с предложением об использовании относительной частоты мы должны оценить вероят­ность выпадения орла как 1. Это полностью противоречит здравому смыслу, по­скольку априорно следовало ожидать, что эта вероятность равна 0,5. Даже если это — не совсем "идеальная" монета, вероятность выпадения орла все равно должна быть близка к 0,5, а оценка 1, безусловно, является неприемлемой. Этот пример также показывает, что оценка вероятности должна зависеть не только от результатов экспериментов, но также и от априорных ожиданий в отношении этой вероятности.

Очевидно, что требуется более обоснованная оценка, чем относительная частота. В этом разделе будет представлена одна из таких оценок, называемая т оценкой, ко­торая имеет глубокое математическое обоснование. В соответствии с m-оценкой ожи­даемая вероятность события С состоит в следующем;

Р " N + и

где pi — априорная вероятность С, т — параметр оценки. Эта формула выведена с использованием байесовского подхода к оценке вероятности. Б общем в байесовской процедуре предполагается, что имеется определенное, возможно очень приблизитель­ное априорное представление о вероятности события С. Эти априорные знания рас­сматриваются как предварительное распределение вероятностей для события С. За­тем проводятся эксперименты, дающие дополнительную информацию о вероятности С. Предварительное распределение вероятностей обновляется с использованием этой новой, экспериментальной информации; при этом применяется формула Байеса для условной вероятности. Приведенная выше формула m-оценки позволяет получить ожидаемое значение р этого распределения. Поэтому данная формула дает возмож­ность учитывать предварительные ожидания в отношении вероятности С, а это удоб­но, если кроме заданных примеров имеются также некоторые ранее приобретенные знания о событии С. Такие предварительные ожидания в формуле m-оценки выра­жаются с помощью переменных р_а и га, как описано ниже.

Формула m-оценки может быть представлена также следующим образом: fa г. NР " Ра ' _B;_m+ _N* fj^

Эта формула представляет собой удобную интерпретацию m-оценки; вероятность р равна априорной вероятности р_а, исправленной с учетом тех данных, которые содер­жатся в N дополнительных примерах. Ясли примеров больше нет, то N = 0 и р = р_а. Если количество примеров велико (N — очень большое число), то р к _n/'N. В против­ном случае р находится между этими двумя значениями. Значимость предваритель­ной оценки вероятности изменяется в зависимости от параметра m (m > G) — чем больше га, тем больше относительная значимость предварительной оценки вероятности.

Параметр m имеет особенно удобную интерпретацию при использовании зашум-ленных данных. Если специалист в рассматриваемой проблемной области считает, что данные очень эашужлены и следует больше доверять ранее полученным знаниям, то он может присвоить параметру m высокое значение (например, га = 100) и при­дать тем самым больше веса предварительной оценке вероятности. Если, с другой стороны, заслуживают доверия обучающие данные, а предварительная оценка веро­ятности менее надежна, то можно установить низкое значение га (например, га. = 0.2) и таким образом придать больший вес данным. На практике, чтобы устранить неоп­ределенность в отношении выбора наиболее подходящего значения параметра т, можно опробовать целый ряд его значений. Это позволяет получить последователь­ность деревьев с различной степенью отсечения поддеревьев, каждое из которых яв-

Часть II.Применение языка Prolog в области искусственного интеллекта

ляется оптимальным применительно к определенному значению т. Затем такая по­следовательность деревьев может быть изучена специалистом в проблемной области, который сможет выбрать наиболее подходящие деревья.

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

Pa= *г **/m — k

Поэтому лапласовская оценка вероятности принимаетследующий вид:

П+ ; ^{Р =} N +■ к

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

На рис. 18.14 показан процесс отсечений поддеревьев дерева решения по методу отсечения с минимальной ошибкой с использованием лапласовской оценки. На этом рисунке самый левый лист неотсеченного поддерева характеризуется частотами классов [3,2]. Это означает, что данному листу соответствуют три объекта класса С1 и два объекта класса С2. Статическая оценка ошибки для частот этих классов, полу­ченная с использованием формулы лапласовской оценки вероятности, может быть представлена следующим образом:

_E(b_ieft) = 1 - ^ТТ = 1 -|-т4 = 0.429

Для правого дочернего узла b оценка вероятности ошибки составляет е (b_right) = 0. 333. Для узла Ь статическая оценка ошибки представляет собой следующее: e(b> = 0.375

Резервированная оценка ошибки для узла Ь может быть представлена таким образом: BackedUpErrorСЬ> = 5 /6 * °-⁴29 + 1/6 * 0.333 == 0.413

Поскольку резервированная оценка выше по сравнению со статической оценкой, поддеревья узла b отсекаются и ошибка в узле Ь после отсечения представляет собой следующее:

Е(Ь)= 0.375

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

Глава 18. Машинное обучение

11(>|н'Д| и ."i- нием

[1. 1] [0, 1] 0.5 03J3

После отсечении:

[1.2][1.0]

Рис. 18.14. Процесс отсечения поддеревьев дерева решения по методу от­сечения С минимальной ошибкой. Пары, чисел в квадратных скобках обо­значают количество примеров классов С1 и С2, которые попадают л со­ответствующие узлы. Другие числа, стоящиерядом с углами,, пред­ставляют собой, оценки ошибок. Для внутренних узлов первое число — это статическая оценка ошибки, а второе — резервированная оценка. Наименьшее из этих двух чисел (обозначенное полужирным шрифтом) передается ид верхний уровень

В методе отсечения с минимальной ошибкой в принципе может использоваться любой подход к оценке ошибок. В любом случае существует возможность свести к минимуму ожидаемую ошибку дерева с отсеченными поддеревьями. Безусловно, по­лученное таким образом усеченное дерево является оптимальным только по отноше­нию к конкретным оценкам ошибок. Один из альтернативных подходов к оценке ошибок состоит в разделении доступных обучающих данных 5 на два подмножест­ва — растущее множество (growing set) и отсекаемое множество (pruning set). Рас­тущее множество используется для формирования полного дерева решения, совмес­тимого с "растущими" данными. Отсекаемое множество применяется только для из­мерения ошибки в узлах дерева, а затем отсечения, выполняемого таким образом, чтобы эта ошибка стала минимальной. Поскольку отсекаемое множество является независимым от растущего множества, появляется возможность классифицировать примеры в отсекаемом множестве с помощью дерева решения и подсчитывать коли-

438 Часть II.Применение языка Prolog в области искусственного интеллекта

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

Упражнения

18.5.Некоторый вулкан выбрасывает лаву полностью случайным образом. Стати­стические данные, накопленные за продолжительное время, показывают, чтоэтот вулкан был в среднем активным в течение одних суток из десяти, в ос­тальные сутки — неактивным. За последние 30 суток он был активным в те­чение 25 суток. Такая активность, проявляющаяся в последнее время, была учтена экспертами в прогнозе на следующие сутки. В новостях, переданных по радио, было сказано, что вероятность активности вулкана на следующие сутки составляет не меньше 30%, а в прогнозе, переданном телевизионной станцией, указано, что эта вероятность составляет 50-60% . Известно, что оба эксперта, работающих на радио и телевидении, используют метод m-оценки. Чем можно объяснить разницу в их оценках?

18.6.Напишите процедуру

prune tree { Tree, PrunedTree)

которая отсекает поддеревья дерева решения Tree в соответствии с методом отсечения с минимальной ошибкой, описанным в данном разделе. Листья де­рева Tree содержат информацию о частоте классов, представленную в виде списков целых чисел. Используйте в этой программе лапласовскую оценку, Допустим, что информация о количестве классов хранится, в программе в виде факта number of classes ( К) .