Алгоритм LISTBB
Материал из MachineLearning.
(→Алгоритм LISTBB (Донской В. И., 1980)) |
(ссылки, категория) |
||
Строка 1: | Строка 1: | ||
== Алгоритм LISTBB (Донской В. И., 1980)== | == Алгоритм LISTBB (Донской В. И., 1980)== | ||
- | Алгоритм строит бинарное решающее дерево по набору примеров - прецедентов. Бинарное решающее дерево – это корневое бинарное дерево, в каждой внутренней вершине которого вычисляется некоторый признаковый предикат. Два ребра, выходящие из каждой внутренней вершины, соответствуют истинному и ложному значениям этого предиката. Концевые вершины помечены метками классов, к которым дерево относит любой классифицируемый объект, если его описание совпадает со значениями предикатов вдоль ветви, заканчивающейся меткой класса. Ошибка соответствует случаю, когда метка класса концевой вершины не совпадает с классом, которому в действительности принадлежит пример. | + | Алгоритм строит бинарное [[решающее дерево]] по набору примеров - прецедентов. Бинарное решающее дерево – это корневое бинарное дерево, в каждой внутренней вершине которого вычисляется некоторый признаковый предикат. Два ребра, выходящие из каждой внутренней вершины, соответствуют истинному и ложному значениям этого предиката. Концевые вершины помечены метками классов, к которым дерево относит любой классифицируемый объект, если его описание совпадает со значениями предикатов вдоль ветви, заканчивающейся меткой класса. Ошибка соответствует случаю, когда метка класса концевой вершины не совпадает с классом, которому в действительности принадлежит пример. |
Название LISTBB алгоритма синтеза бинарного решающего дерева расшифровывается следующим образом. LIST – списковое представление; Branching (B) – ветвление, а Boolean – второе B – обозначает булевы пометки ребер. Подробнее см.: | Название LISTBB алгоритма синтеза бинарного решающего дерева расшифровывается следующим образом. LIST – списковое представление; Branching (B) – ветвление, а Boolean – второе B – обозначает булевы пометки ребер. Подробнее см.: | ||
Строка 37: | Строка 37: | ||
== Подробно о критериях ветвления и алгоритме LISTBB см. [http://intellectualarchive.com/getfile.php?file=KbEp3gZPNPX&orig_file=Donskoy%20VI%20Splitting%20criteria.pdf]== | == Подробно о критериях ветвления и алгоритме LISTBB см. [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. Вычислить множество номеров переменных, для которых достигается минимум критерия .
s2. Если , т.е. минимум критерия достигается только для одной переменной, то выбрать эту переменную и завершить алгоритм выбора.
s3. Если , где – число классов, то выбрать для разбиения любую переменную такую, что , и завершить алгоритм выбора.
s4. Если частичная отделимость не имеет места, т.е. , то выбрать для разбиения любую переменную такую, что , и завершить алгоритм выбора.
s5. Если частичная отделимость имеет место и , где – параметр, то выбрать для разбиения любую переменную по максимуму частичной отделимости: такую, что , и завершить алгоритм выбора; иначе – выбрать любую переменную такую, что , и завершить алгоритм выбора.
Завершение синтеза дерева
происходит, если получено корректное разбиение или по одному из следующих правил: достигнуто максимальное заданное число вершин; наращивание вершин уже не уменьшает среднюю длину описания "модель+данные" по принципу идеального MDL или др.
Применяемые критерии
– число меток разных классов в двух подмножествах разбиения по переменной , т.е. суммарное число классов в двух подмножествах.
– число пар примеров разных классов в подмножествах разбиения по переменной .
– характеристический предикат отделимости точек только одного класса в одном из подмножеств разбиения по переменной .
– число отделяемых точек в одном из подмножеств разбиения по переменной при условии .