Алгоритм LISTBB
Материал из MachineLearning.
(→Выбор переменной (предиката) для ветвления (добавления условной вершины) при синтезе бинарного решающего дерева (splitting)) |
(→Завершение синтеза дерева) |
||
| Строка 18: | Строка 18: | ||
== Завершение синтеза дерева == | == Завершение синтеза дерева == | ||
происходит, если получено корректное разбиение или | происходит, если получено корректное разбиение или | ||
| - | по одному из правил: достигнуто максимальное заданное число вершин; наращивание вершин уже не уменьшает ошибки и др. | + | по одному из следующих правил: достигнуто максимальное заданное число вершин; наращивание вершин уже не уменьшает ошибки и др. |
| + | |||
== Применяемые критерии == | == Применяемые критерии == | ||
<tex> \Omega(k) </tex> – число меток разных классов в двух подмножествах разбиения по переменной <tex> k </tex>, т.е. суммарное число классов в двух подмножествах. | <tex> \Omega(k) </tex> – число меток разных классов в двух подмножествах разбиения по переменной <tex> k </tex>, т.е. суммарное число классов в двух подмножествах. | ||
Версия 07:47, 6 апреля 2013
Алгоритм LISTBB
Алгоритм строит бинарное решающее дерево по набору примеров - прецедентов. Бинарное решающее дерево – это корневое бинарное дерево, в каждой внутренней вершине которого вычисляется некоторый признаковый предикат. Два ребра, выходящие из каждой внутренней вершины, соответствуют истинному и ложному значениям этого предиката. Концевые вершины помечены метками классов, к которым дерево относит любой классифицируемый объект, если его описание совпадает со значениями предикатов вдоль ветви, заканчивающейся меткой класса. Ошибка соответствует случаю, когда метка класса концевой вершины не совпадает с классом, которому в действительности принадлежит пример.
Выбор внутренней вершины дерева для дальнейшего ветвления
(Для корневой вершины – не требуется). Для ветвления выбирается та концевая вершина дерева, построенного к текущему шагу, для которой определяемое ею подмножество признакового пространства содержит наибольшее число ошибок. Ошибкой считается несовпадение класса обучающего примера с меткой рассматриваемой концевой вершины, которая ошибочно классифицирует этот пример..
Выбор переменной (предиката) для ветвления (добавления условной вершины) при синтезе бинарного решающего дерева (splitting)
s1. Вычислить множество номеров переменных, для которых достигается минимум критерия
.
s2. Если , т.е. минимум критерия достигается только для одной переменной, то выбрать эту переменную и завершить алгоритм выбора.
s3. Если , где
– число классов, то выбрать для разбиения любую переменную
такую, что
, и завершить алгоритм выбора.
s4. Если частичная отделимость не имеет места, т.е. , то выбрать для разбиения любую переменную такую, что
, и завершить алгоритм выбора.
s5. Если частичная отделимость имеет место и , где
– параметр, то выбрать для разбиения любую переменную
по максимуму частичной отделимости: такую, что
, и завершить алгоритм выбора; иначе – выбрать любую переменную такую, что
, и завершить алгоритм выбора.
Завершение синтеза дерева
происходит, если получено корректное разбиение или по одному из следующих правил: достигнуто максимальное заданное число вершин; наращивание вершин уже не уменьшает ошибки и др.
Применяемые критерии
– число меток разных классов в двух подмножествах разбиения по переменной
, т.е. суммарное число классов в двух подмножествах.
– число пар примеров разных классов в подмножествах разбиения по переменной
.
– характеристический предикат отделимости точек только одного класса в одном из подмножеств разбиения по переменной
.
– число отделяемых точек в одном из подмножеств разбиения по переменной
при условии
.
