Введение   Главы  1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24   Приложения  1  2  

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



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

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

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

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

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

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



- Начало - - Назад - - Вперед -