Иллюстрированный самоучитель по введению в экспертные системы



             

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


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

  • множество целевых непересекающихся классов {С1, С2, ..., Сk};

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

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

    Пусть Т представляет любую тестовую процедуру, имеющую дело с одним из атрибутов, а {О1,O2,...,On} — множество допустимых выходных значений такой процедуры

    при ее применении к произвольному объекту х. Применение процедуры Т к объекту х будем обозначать как Т(х). Следовательно, процедура Т(х) разбивает множество S на составляющие {S1, S2, ..., Sn}, такие, что

    Si= {x|T(x) = Oi}. Такое разделение графически представлено на рис. 20.3.

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

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

    Квинлан (Quinlan) использует для этого заимствованное из теории информации понятие неопределенности. Неопределенность — это число, описывающее множество сообщений M= { m1, т2,..., тn}. Вероятность получения определенного сообщения mi из этого множества определим как р(тi). Объем информации, содержащейся в этом сообщении, будет в таком случае равен

    I(mi) = -logp(mi).



    Содержание  Назад  Вперед