Логический вывод деревьев решения

Основной алгоритм логического вывода дерева

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

На рис. 18.10 показано дерево решения, которое может быть получено путем ло­гического вывода из примеров, приведенных в листинге 18.1 (т.е. объектов, показан­ных на рис, 18.8). Внутренние узлы этого дерева обозначены именами атрибутов. Листья дерева обозначены именами классов или символом "null", который указыва­ет, что этому листу не соответствует ни один учебный пример. Ветви в дереве обо­значены значениями атрибутов. При классификации объекта по дереву прокладыва­ется путь, начинающийся с корневого узла и оканчивающийся в одном из листьев.

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

После прохождения каждого внутреннего узла процедура следует со ветви, обозначен­ной значением атрибута в объекте. Например, объект, описанный следующим образом: [ size - small, shape = compact, holes - 1]

согласно этому дереву должен классифицироваться как nut — гайка (после прохож­дения пути holes = 1, shape = compact). Обратите внимание на то, что в этом случае значение атрибута size = small для классификации объекта не требуется.

null

smell / screw

("") С

1~Л 7

Large long compact other

\ / I \

Key nut null

pen

/

Key

Рис. IS. 10. Дерево решения, полученное с помощью логического вывода на основа­нии примеров, приведенных в листинга 18.1 (и изображенных графически на рис. 18.8)

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

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

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

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

Чтобы сформировать дерево решения Тдляобучающего множества S,

необходимо выполнить следующее;

•если все примеры в S относятся к одному и тому же классу. С, то результат представляет собой дерево, состоящее из единственного узла, который обозначен кэкС,

• в противном случае

- выбрать "самый информативный" атрибут, А, значениями которого являются»,»..^

- разделить множество S наподмножестваЗ.,..., S в соответствии со значениями А;

- сформировать {рекурсивно) поддеревья Т.., Т для S...,S; конечным результатом становится дерево, корнем которого является А, поддеревьями • Т Т, а связи между А и поддеревьями обозначены K3KV,,, v; полученное таким образом дерево решения имеет следующий вид:

 

'1 '2 ■■ S

Рис. 18.11. Основной алгоритм логического вывода дерева решения

Даже в своей простейшей реализации ных уточнений, которые описаны ниже.

этот

основной алгоритм требует определен-

1. Если множество S является пустым, то результат представляет собой дерево с одним узлом, обозначенным как "null".

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

3. Если множество S не пусто, и не все объекты в S принадлежат к одному и то­му же классу, и не осталось атрибутов, доступных для выбора, то результатом становится дерево с одним узлом. Узел такого типа удобно обозначить с помо­щью списка всех классов, представленных в множестве S наряду с их относи­тельными частотами в S. Такое дерево иногда называют деревом вероятностей классов (class probability tree), а не деревом решения. В подобном случае для проведения различия между значениями класса некоторых объектов недоста­точно иметь множество доступных атрибутов (когда объекты, принадлежащие к разным классам, имеют одинаковые значения атрибутов).

4. Необходимо определить критерий выбора наиболее информативного атрибута. Эта тема рассматривается в следующем разделе.

18.5.2. Выбор "наилучшего" атрибута

Значительная часть исследований в области машинного обучения посвящена оп­ределению критериев выбора "наилучшего" атрибута. По сути, эти критерии служат для измерения в множестве примеров количества посторонних включений (impurity) по отношению к классу. Качественный атрибут должен обеспечивать разбиение при­меров на подмножества как можно более безошибочно (охватывая как можно меньше посторонних включений).

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

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

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

V I = - iiplc) log₂ p(c)

где с обозначает классы, а р{с) - вероятность того, что некоторый объект из мно­жества S принадлежит к классу с. Эта формула полностью соответствует интуитив­ному представлению о посторонних включениях. Если множество полностью очище­но от посторонних, включений, то вероятность распознавания одного из его классов равна 1, а для всех других классов равна 0. Для такого множества информация 1 = 0. С другой стороны, информация I является максимальной в том случае, если вероят­ности всех классов равны.

После применения атрибута Л множество S разделяется на подмножества в соот­ветствии со значениями А. Поэтому остаточная информация ':.... равна взвешенной сумме объемов информации для подмножеств:

IresW = - Аа p{v) L p(c I v) log, р(с I v)

где v — значения атрибута А, р (v) — вероятность значения v в множестве S, p(c I v) — условная вероятность класса с, при условии, что атрибут А имеет зна­чение v. Вероятности р (v) и р (с | v) обычно аппроксимируются с помощью стати­стических данных о множестве S.

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

I (A) = -2^p[v) iog_a <p(v> }

Обычно значение I (А) является более высоким для атрибутов с большим количе­ством значений. Коэффициент приращения информации определяется следующим образом:

Gain (A). I - I_res (A)

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

Еще один способ устранения недостатков, связанных с наличием многозначных атрибутов, состоит в использовании метода раздваивания, ил и дихотомизации ат­рибутов (binarization of attributes). Раздваивание атрибута осуществляется путем разбиения множества его значений на два подмножества. В результате этого разбие­ние приводит к созданию нового (двухзначного) атрибута, два значения которого со­ответствуют двум подмножествам. Если такое подмножество содержит больше одного

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

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

Применяются также другие научно обоснованные критерии определения количе­ства посторонних включений, такие как индекс Gird, определяемый следующим об­разом:

Чп

Gini = Zd p(i) p(j)

где i И; обозначают классы. После применения атрибута А формула определения ре­зультирующего индекса Gini принимает следующий вид:

У У

Gini [A) = £j (!(v) ^ p(i | v) p(j | V)

где v — значения атрибута A, p(i | v] — условная вероятность класса i, если дано, что атрибут А имеет значение v.

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

Упражнения

18.1. Рассмотрите задачу обучения на силуэтах объектов (см. листинг 18.1). Рассчи­тайте энтропию для всего множества примеров по отношению к классу, оста­точную информацию для атрибутов "size" и "holes", соответствующие при­ращения информации и коэффициенты приращения. Оцените вероятности, не­обходимые для этих вычислений, с помощью относительных частот, например p(nut) = 3/12илир[пи1 | holes=l) = 3/5.

18.2. Заболевание D возникает в 25% из всех случаев заболеваний. Симптом S на­блюдается у 75% пациентов, страдающих от заболевания С, и только в одном из шести прочих случаев. Предположим, что вы формируете дерево решения для диагностики заболевания Э, состоящее только из двух классов, D (некоторое лицо страдает от заболевания D) и -D (некоторое лицо не имеет за­болевания Э). Симптом S является одним из соответствующих атрибутов. Ка­ковыми являются приращение информации и коэффициент приращения для атрибута S?