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

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

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

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

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

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

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

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