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

102 и в целях анализа данных такое правило практически непригодно. Гораздо предпочтительнее иметь дерево, состоящее из малого ко- личества узлов, которым бы соответствовало большое количество объектов из обучающей выборки. Для решения данной проблемы часто применяется так назы- ваемое отсечение ветвей (pruning). Пусть под точностью (распознавания) дерева решений пони- мается отношение правильно классифицированных объектов при обучении к общему количеству объектов из обучающего множест- ва, а под ошибкой – количество неправильно классифицированных. Предположим, что известен способ оценки ошибки дерева, ветвей и листьев. Тогда можно использовать следующее простое правило:  построить дерево;  отсечь или заменить поддеревом те ветви, которые не при- ведут к возрастанию ошибки. В отличие от процесса построения отсечение ветвей проис- ходит снизу вверх, двигаясь с листьев дерева, отмечая узлы как ли- стья либо заменяя их поддеревом. Хотя отсечение не является панацеей, в большинстве практических задач дает хорошие резуль- таты, что позволяет говорить о правомерности использования по- добной методики. Алгоритм ID3. Рассмотрим более подробно критерий выбо- ра переменной, по которой будет выполняться разбиение. Оче- видно, что полный набор вариантов разбиения описывается мно- жеством | Х | (количеством независимых переменных). Рассмотрим проверку переменной x h , (в качестве проверки может быть выбрана любая переменная), которая принимает т значений c h 1 , c h 2 , …, c hm . Тогда разбиение Т по проверке x h даст подмножества T 1 , T 2 , …, T m , при x h , равном соответственно c h 1 , c h 2 , …, c hm . Единственная доступная информация – каким образом