Алгоритм LISTBB

Материал из MachineLearning.

Версия от 17:05, 5 апреля 2013; Donskoy (Обсуждение | вклад)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Содержание

Алгоритм LISTBB

Выбор переменной (предиката) для ветвления (добавления условной вершины) при синтезе бинарного решающего дерева (splitting)

s1. Вычислить множество  $ K_\Omega = \{ k^*: k^* = argmin_k \Omega(k)\} номеров переменных, для которых достигается минимум критерия  \Omega .

s2. Если  $ |K_\Omega| = 1 , т.е. минимум критерия достигается только для одной переменной, то выбрать эту переменную и завершить алгоритм выбора.

s3. Если  $ min_k \Omega(k) = q , где   q – число классов, то выбрать для разбиения любую переменную  k^*  такую, что  k^* = argmax_{k \in K_\Omega} D(k) , и завершить алгоритм выбора.

s4. Если частичная отделимость не имеет места, т.е. \forall k  \in K_\Omega (S_1(k)=0 ) , то выбрать для разбиения любую переменную такую, что  k^* = argmax_{k \in K_\Omega} D(k) , и завершить алгоритм выбора.

s5. Если частичная отделимость имеет место и  Z_1(k)> p , где   p – параметр, то выбрать для разбиения любую переменную  k^*  по максимуму частичной отделимости: такую, что  k^* = argmax_{k \in K_\Omega} Z_1(k) , и завершить алгоритм выбора; иначе – выбрать любую переменную такую, что  k^* = argmax_{k \in K_\Omega} D(k) , и завершить алгоритм выбора.

Завершение синтеза дерева

происходит, если получено корректное разбиение или по одному из правил: достигнуто максимальное заданное число вершин; наращивание вершин уже не уменьшает ошибки и др.

Применяемые критерии

 \Omega(k) – число меток разных классов в двух подмножествах разбиения по переменной  k , т.е. суммарное число классов в двух подмножествах.

 D(k) – число пар примеров разных классов в подмножествах разбиения по переменной  k .

 S_1(k) – характеристический предикат отделимости точек только одного класса в одном из подмножеств разбиения по переменной  k .

 Z_1(k) – число отделяемых точек в одном из подмножеств разбиения по переменной  k при условии  S_1(k)=0 .

Подробно о критериях ветвления и алгоритме LISTBB см.

http://intellectualarchive.com/getfile.php?file=KbEp3gZPNPX&orig_file=Donskoy%20VI%20Splitting%20criteria.pdf

Личные инструменты