Участник:Tolstikhin/Песочница

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

Версия 21:30, 4 января 2009

Решающие деревья - разделение объектов.

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

Напомним, что задачей настройки является получение параметров модели на основе обучающей выборки .

Метод разделения объектов

Для описания метода разделения объектов для начала введём понятие отступа объектов обучающей выборки.

Предположим, что мы имеем алгоритм классификации вида , где x - классифицирумый объект, y - класс из множества классов Y, а - ключевая величина, являющаяся оценкой принадлежности объекта x классу y. В этом случае отступом обекста назовём величину . Здесь - класс, которому принадлежит объект обучающей выборки . Грубо говоря, отсупом объекта является расстояние от него до границы, отделяющей объекты своего класса, от всех остальных.

Понятие отступа лежит в основе метода разделения объектов. Его идеей является максимизация отступа объектов обучающей выборки. Интуитивно ясно, что чем больше отступы объектов, тем надёжнее будет классификация, поскольку это означает, что есть достаточно большой зазор между двумя классами.

Параметры решающих деревьев.

При построении решающих деревьев основными параметрами являются предикаты , соответствующие узлам деревьев, и структура самого дерева. Под структурой в данном случае понимаются свойства дерева, как графа - его высота, число узлов, сбалансированность и так далее.

Настройка параметров решающих деревьев методом разделения объектов.

Как мы знаем, алгоритм классификации, реализуемый бинарными решающими деревьями, может быть записан в виде простого голосования конъюнкций:

.

Поясним буквы, входящие в эту фурмулу. y - по-прежнему класс из множества классов Y. T - множество терминальных (листовых) вершин бинарного дерева, V - вершина дерева, а - класс, соответствующий терминальной вершине v. - конъюнкция всех предикатов на пути от корня дерева к терминальной вершине v.

Понятно, что напрямую воспользоваться методом разделения объектов в данном случае не получается, поскольку из всех конъюнкций, учавствующих в сумме, при фиксированном объекте ровно одна принимает значение 1. Мы немного изменим подход и будем использовать метод разделения объектов для настройки предикатов решающего дерева.

За основу синтеза решающего дерева взят жадный алгоритм, описанный в лекции [1] К.В. Воронцова.

Настройка предикатов.

В каждом узле дерева предлагается строить предикаты вида , где - n-ый признак объекта х. Мы хотим найти одномерное разбиение объектов (по одной координате), которое будет соответствовать максимальным отступам объектов части обучающей выборки, попавшей в данный узел. В данном случае в качестве оценки принадлежности объекта x к классу y можно взять величину , если условиться, что у нас 2 класса - . (При этом в каждом узле элементы класса, среднее значение рассматриваемой координаты которого больше, помечать классом 1, а элементы второго класса - классом -1.)

Максимизация отступов в пределах одного признака сводится к нахождению такого a, что величины расстояний от элементов обучающей выборки до границы a, взятые с соответствующими знаками, максимальны. Как варианты можно максимизировать минимальный из отступов или сумму отступов по всем объектам. После этого остаётся максимизировать отступ по номеру признака - и мы имеем предикат .

Стоит отметить, что выбранный вид предиката осуществляет разбиение выборки на прямоугольники со сторонами параллельными осям координат.

Настройка формы дерева.

Форма дерева настраиватся автоматически при синтезе решающего дерева жадным алгоритмом. Мы будем рекурсивно в каждой вершине дерева делить часть обучающей выборки, попавшую в данный узел, получать предикаты описанным образом и наращивать сыновей вершины, если это надо. Причём условимся, что правым сыновьям вершины будут соответствовать объекты, на которых предикат принял значение 0, а левым - на которых принял значение 1. Так мы будем действовать до тех пор, пока в какую-то из вершин не придут элементы, все принадлежащие классу y. Эту терминальную Вершину мы пометим классом y и закончим наращивание.

После жадного алгоритма можно применять различные эвристики и методы, позволяющие упростить форму дерева, такие как редукция, пост-редукция, заглядывание вперёд и так далее.

Реализация жадного алгоритма и оптимизация отступов.

В рамках изучения вопроса настройки решающих деревьев был написан код программы, реализующей настройку методом разделения объектов, в основу которой лёг жадный алгоритм синтеза деревьев.

Для настройки предикатов и оптимизации отступа по выбранному признаку проводилось несколько этапов. Сначала сортировкой пузырька сортировался массив значений выбранного признака у объектов. Далее составлялся набор узловых точек, которые в дальнейшем использовались в качестве значения порога. Эти точки выбирались посередине между двумя соседними значениями признака в отсортированном массиве. После этого применялся полный пребор по найденным узловым точкам.

Жадный алгоритм реализовывался без досрочных остановов (использующихся для повышения надёжности классификации) и без дальнейших упрощений вида дерева.

Пример настройки решающего дерева.

В качестве обучающей и контрольной выборки использовались точки на плоскости. Предварительной обработки информации не происходило. На рисунке квадратами изображены точки обучающей выборки. Соответственно, в выборке были представлены объекты двух классов. Крестиками обозначены объекты контрольной выборки. На рисунке представлен результат классификации контрольной выборки настроенным по обучающей выборке решающим деревом. На втором рисунке отображено настроенное решающее дерево. Жёлтые линии - пороги предикатов. /*изобразить само дерево и разбиение поузловое*/

Список литературы

[1] К.В. Воронцов, "Логические алгоритмы классификации", лекция, 2007. [2] K. Bennett, N. Cristianini, J. Shawe-Taylor, D. Wu. "Enlarging the margin in perceptron decision trees", Machine Learning, 2000.