Структура дерева решений

Построение дерева решений и порождающих правил

Характеристика подходов

Машинное обучение экспертных систем

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

Можно выделить три варианта приобретения знаний, которые позволяют обойтись без создания базы знаний вручную объединенными усилиями человека-эксперта и инженера по знаниям.

1. Использование интерактивных программ, которые извлекают знания непосредственно у человека-эксперта в процессе диалога за терминалом. Такой вариант успешно применим на практике в случаях, если диалоговая система обладает некоторым запасом знаний о предметной области.

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

3. Использование программ, способных обучаться под руководством человека-учителя. Один из подходов состоит в том, что учитель предъявляет программе примеры реализации некоторого концепта (образца, обладающего общими свойствами объекта), а задача программы состоит в том, чтобы извлечь из предъявленных примеров набор атрибутов и значений, определяющих этот концепт. Такой подход успешно опробован в ряде исследовательских систем и использованные при этом базовые методы составляют предмет нашего рассмотрения.

Остановим наше внимание на методах формирования знаний на основе машинного обучения, которые имеют прямое отношение к проблематике экспертных систем:

q извлечение множества правил из предъявляемых примеров;

q анализ важности отдельных правил;

q оптимизация производительности правил.

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

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

В работе [Quintan, 1993] дерево решений определенокак структура,которая состоит из:

q узлов-листьев, каждый из которых представляет определенный класс;

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

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

		П		Н
	Н				П

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

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

если наблюдение = облачно

v

наблюдение = солнечно &

влажность = нормально

V

наблюдение = дождливо &

ветрено = нет

то П

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

if наблюдение = облачно

then П

if наблюдение = солнечно &

влажность = нормально

then П

if наблюдение = дождливо &

ветрено = нет

then П

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

В табл. 20.2 показана обучающая выборка, которая использовалась для формирования дерева, приведенного на рис. 20.2.

Таблица 20.2. Обучающая выборка (заимствовано из [Quinlan, 1986, а)

Номер	Наблюдение	Температура	Влажность	Ветрено	Класс
	Солнечно	Жарко	Высокая	Нет	Н
	Солнечно	Жарко	Высокая	Да	Н
	Облачно	Жарко	Высокая	Нет	П
	Дождливо	Умеренно	Высокая	Нет	П
	Дождливо	Холодно	Нормальная	Нет	П
	Дождливо	Холодно	Нормальная	Да	Н
	Облачно	Холодно	Нормальная	Да	П
	Солнечно	Умеренно	Высокая	Нет	Н
	Солнечно	Холодно	Нормальная	Нет	П
	Дождливо	Умеренно	Нормальная	Нет	П
	Солнечно	Умеренно	Нормальная	Да	П
	Облачно	Умеренно	Высокая	Да	П
	Облачно	Жарко	Нормальная	Нет	П
	Дождливо	Умеренно	Высокая	Да	Н

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

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