Материал из MachineLearning.
(Различия между версиями)
Версия 17:05, 5 апреля 2013
Алгоритм LISTBB
Выбор переменной (предиката) для ветвления (добавления условной вершины) при синтезе бинарного решающего дерева (splitting)
s1. Вычислить множество \})
номеров переменных, для которых достигается минимум критерия 
.
s2. Если 
, т.е. минимум критерия достигается только для одной переменной, то выбрать эту переменную и завершить алгоритм выбора.
s3. Если  = q )
, где 
– число классов, то выбрать для разбиения любую переменную 
такую, что  )
, и завершить алгоритм выбора.
s4. Если частичная отделимость не имеет места, т.е.=0 ))
, то выбрать для разбиения любую переменную такую, что , и завершить алгоритм выбора.
s5. Если частичная отделимость имеет место и > p )
, где 
– параметр, то выбрать для разбиения любую переменную по максимуму частичной отделимости: такую, что  )
, и завершить алгоритм выбора; иначе – выбрать любую переменную такую, что , и завершить алгоритм выбора.
Завершение синтеза дерева
происходит, если получено корректное разбиение или
по одному из правил: достигнуто максимальное заданное число вершин; наращивание вершин уже не уменьшает ошибки и др.
Применяемые критерии
 )
– число меток разных классов в двух подмножествах разбиения по переменной 
, т.е. суммарное число классов в двух подмножествах.
 )
– число пар примеров разных классов в подмножествах разбиения по переменной .
 )
– характеристический предикат отделимости точек только одного класса в одном из подмножеств разбиения по переменной .
 )
– число отделяемых точек в одном из подмножеств разбиения по переменной при условии =0 )
.
Подробно о критериях ветвления и алгоритме LISTBB см.
http://intellectualarchive.com/getfile.php?file=KbEp3gZPNPX&orig_file=Donskoy%20VI%20Splitting%20criteria.pdf
