Алгоритм LISTBB

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

(Различия между версиями)
Перейти к: навигация, поиск
(→Завершение синтеза дерева)
(ссылки, категория)
 
(5 промежуточных версий не показаны.)
Строка 1: Строка 1:
-
== Алгоритм LISTBB ==
+
== Алгоритм LISTBB (Донской В. И., 1980)==
-
Алгоритм строит бинарное решающее дерево по набору примеров - прецедентов. Бинарное решающее дерево – это корневое бинарное дерево, в каждой внутренней вершине которого вычисляется некоторый признаковый предикат. Два ребра, выходящие из каждой внутренней вершины, соответствуют истинному и ложному значениям этого предиката. Концевые вершины помечены метками классов, к которым дерево относит любой классифицируемый объект, если его описание совпадает со значениями предикатов вдоль ветви, заканчивающейся меткой класса. Ошибка соответствует случаю, когда метка класса концевой вершины не совпадает с классом, которому в действительности принадлежит пример.
+
Алгоритм строит бинарное [[решающее дерево]] по набору примеров - прецедентов. Бинарное решающее дерево – это корневое бинарное дерево, в каждой внутренней вершине которого вычисляется некоторый признаковый предикат. Два ребра, выходящие из каждой внутренней вершины, соответствуют истинному и ложному значениям этого предиката. Концевые вершины помечены метками классов, к которым дерево относит любой классифицируемый объект, если его описание совпадает со значениями предикатов вдоль ветви, заканчивающейся меткой класса. Ошибка соответствует случаю, когда метка класса концевой вершины не совпадает с классом, которому в действительности принадлежит пример.
 +
 
 +
Название LISTBB алгоритма синтеза бинарного решающего дерева расшифровывается следующим образом. LIST – списковое представление; Branching (B) – ветвление, а Boolean – второе B – обозначает булевы пометки ребер. Подробнее см.:
 +
 
 +
Donskoy V. I. Binary decision tree synthesis: splitting criteria and the algorithm LISTBB //
 +
Taurida Journal of Computer Science Theory and Mathematics, 2013, 1(22), p. 11-34.
 +
https://www.researchgate.net/publication/250308237_BINARY_DECISION_TREE_SYNTHESIS_SPLITTING_CRITERIA_AND_THE_ALGORITHM_LISTBB
 +
 
== Выбор внутренней вершины дерева для дальнейшего ветвления ==
== Выбор внутренней вершины дерева для дальнейшего ветвления ==
(Для корневой вершины – не требуется). Для ветвления выбирается та концевая вершина дерева, построенного к текущему шагу, для которой определяемое ею подмножество признакового пространства содержит наибольшее число ошибок. Ошибкой считается несовпадение класса обучающего примера с меткой
(Для корневой вершины – не требуется). Для ветвления выбирается та концевая вершина дерева, построенного к текущему шагу, для которой определяемое ею подмножество признакового пространства содержит наибольшее число ошибок. Ошибкой считается несовпадение класса обучающего примера с меткой
Строка 18: Строка 25:
== Завершение синтеза дерева ==
== Завершение синтеза дерева ==
происходит, если получено корректное разбиение или
происходит, если получено корректное разбиение или
-
по одному из следующих правил: достигнуто максимальное заданное число вершин; наращивание вершин уже не уменьшает ошибки и др.
+
по одному из следующих правил: достигнуто максимальное заданное число вершин; наращивание вершин уже не уменьшает среднюю длину описания "модель+данные" по принципу идеального MDL или др.
== Применяемые критерии ==
== Применяемые критерии ==
Строка 29: Строка 36:
<tex> Z_1(k) </tex> – число отделяемых точек в одном из подмножеств разбиения по переменной <tex> k </tex> при условии <tex> S_1(k)=0 </tex>.
<tex> Z_1(k) </tex> – число отделяемых точек в одном из подмножеств разбиения по переменной <tex> k </tex> при условии <tex> S_1(k)=0 </tex>.
-
== Подробно о критериях ветвления и алгоритме LISTBB см. ==
+
== Подробно о критериях ветвления и алгоритме LISTBB см. [http://intellectualarchive.com/getfile.php?file=KbEp3gZPNPX&orig_file=Donskoy%20VI%20Splitting%20criteria.pdf]==
-
http://intellectualarchive.com/getfile.php?file=KbEp3gZPNPX&orig_file=Donskoy%20VI%20Splitting%20criteria.pdf
+
[[Категория:Решающие деревья]]

Текущая версия

Содержание

Алгоритм LISTBB (Донской В. И., 1980)

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

Название LISTBB алгоритма синтеза бинарного решающего дерева расшифровывается следующим образом. LIST – списковое представление; Branching (B) – ветвление, а Boolean – второе B – обозначает булевы пометки ребер. Подробнее см.:

Donskoy V. I. Binary decision tree synthesis: splitting criteria and the algorithm LISTBB // Taurida Journal of Computer Science Theory and Mathematics, 2013, 1(22), p. 11-34. https://www.researchgate.net/publication/250308237_BINARY_DECISION_TREE_SYNTHESIS_SPLITTING_CRITERIA_AND_THE_ALGORITHM_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) , и завершить алгоритм выбора.

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

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

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

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

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

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

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

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

Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_LISTBB»
Личные инструменты