Технологии интеллектуального анализа данных : учебное пособие

100 3) множество Т содержит объекты, относящиеся к разным классам. В этом случае следует разбить данное множество на неко- торые подмножества. Для этого выбирается одна из независимых переменных x h , имеющая два и более отличных друг от друга зна- чений 1 h c , 2 h c , …, n h c . T разбивается на подмножества T 1 , T 2 , …, T n , где каждое подмножество Т i содержит все объекты, имеющие зна- чение i h c для выбранного признака. Эта процедура будет рекурсив- но продолжаться до тех пор, пока в конечном множестве не ока- жутся объекты только одного класса. Очевидно, что при использовании данной методики построе- ние дерева решений будет происходить сверху вниз. Описанная процедура лежит в основе многих алгоритмов построения деревьев решений. Большинство из них являются «жадными» алгоритмами. Это значит, что если один раз переменная была выбрана и по ней было произведено разбиение на подмножества, то алгоритм не мо- жет вернуться назад и выбрать другую переменную, которая дала бы лучшее разбиение. Поэтому на этапе построения нельзя сказать, даст ли выбранная переменная в конечном итоге оптимальное раз- биение. При построении деревьев решений особое внимание уделяет- ся выбору переменной, по которой будет выполняться разбиение. Для построения дерева на каждом внутреннем узле необходимо найти такое условие (проверку), которое бы разбивало множество, ассоциированное с этим узлом, на подмножества. В качестве такой проверки должна быть выбрана одна из независимых переменных. Общее правило для выбора можно сформулировать следующим образом: выбранная переменная должна разбить множество так, чтобы получаемые в итоге подмножества состояли из объектов, принадлежащих к одному классу, или были максимально прибли- жены к этому, т.е. количество объектов из других классов в каждом