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

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

Версия 22:17, 13 декабря 2008 (править) Tolstikhin (Обсуждение | вклад) (→Численный эксперимент) ← К предыдущему изменению		Версия 21:11, 4 января 2009 (править) (отменить) Tolstikhin (Обсуждение | вклад) К следующему изменению →
Строка 1:		Строка 1:
-	== Введение ==	+	Решающие деревья - разделение объектов.
-	В этой статье будeт рассматриваться задача поиска совместной подсистемы максимальной мощности	+	В этой статье будет рассмотрен один из возможных вариантов настройки бинарных решающих деревьев, основанный на
-	для систем линейных уравнений и неравенств ([http://risorse.dei.polimi.it/maxfs/index.html MaxFS problem]).	+	''разделении объектов''.
-	На основе таких понятий как узловая подсистема и узловое решение будет получен один из возможных алгоритмов, решающих задачу.	+	Будет рассматриваться задача классификации с двумя классами в n-мерном пространстве объектов.
-	В статье также представлена эвристика, в некоторых случаях позволяющая заметно ускорить решение задачи.	+
-	=== Постановка задачи ===	+	Напомним, что задачей настройки является получение параметров модели на основе обучающей выборки <tex>X^l</tex>.
-	Пусть дана произвольная система линейных неравенств	+	== Метод разделения объектов ==
-	<tex>a_{i1}x_1+\dots+a_{in}x_n\geq b_i,\ i=1,2,\dots,m\ (1),</tex>	+	Для описания метода разделения объектов для начала введём понятие ''отступа'' объектов обучающей выборки.
-	равенств	+	Предположим, что мы имеем алгоритм классификации вида <tex>a(x)=arg\max_{y\in Y}G_y(x)</tex>, где x - классифицирумый объект, y - класс из множества
		+	классов Y, а <tex>G_y(x)</tex> - ключевая величина, являющаяся оценкой принадлежности объекта x классу y. В этом случае ''отступом'' обекста <tex>x_i\in X^l</tex>
		+	назовём величину <tex>M(x_i)=G_{y_i}(x_i)-\max_{y\in Y\\y_i}G_y(x_i)</tex>. Здесь <tex>y_i</tex> - класс, которому принадлежит объект обучающей выборки
		+	<tex>x_i</tex>.
		+	Грубо говоря, отсупом объекта является ''расстояние'' от него до границы, отделяющей объекты ''своего'' класса, от всех остальных.
-	<tex>a_{i1}x_1+\dots+a_{in}x_n = b_i,\ i=1,2,\dots,m,</tex>	+	Понятие отступа лежит в основе метода разделения объектов. Его идеей является максимизация отступа объектов обучающей выборки. Интуитивно ясно, что
		+	чем больше отступы объектов, тем надёжнее будет классификация, поскольку это означает, что есть достаточно большой ''зазор'' между двумя классами.
-	или в более общем случае - смешанная система, содержащая как равенства, так и неравенства.	+	== Параметры решающих деревьев. ==
-	m и n - число строк и число столбцов матрицы системы соответственно.	+
-	Задача MaxFs состоит в нахождении совместной подсистемы данной системы, имеющей максимальную мощность.	+	При построении решающих деревьев основными параметрами являются предикаты <tex>/phi_i(x)</tex>, соответствующие узлам деревьев, и структура самого дерева.
		+	Под структурой в данном случае понимаются свойства дерева, как графа - его высота, число узлов, сбалансированность и так далее.
		+	== Настройка параметров решающих деревьев методом разделения объектов. ==
-	Данная задача часто возникает при решении различных математических задач - в том числе при решении	+	Как мы знаем, алгоритм классификации, реализуемый бинарными решающими деревьями, может быть записан в виде простого голосования конъюнкций:
-	задач прогнозирования и распознавания.	+
-	Примером может служить разделение объектов 2х классов обучающей выборки	+
-	гиперплоскостью.	+
-	В случае, когда эту задачу не удаётся решить точно, мы хотим провести	+
-	гиперплоскость так, чтобы она допускала минимальное число ошибок.	+
-	== Сложность задачи ==	+
-	В книге ([5]) доказывается, что	+	Поясним буквы, входящие в эту фурмулу.
-	''задача выделения максимальной совместной подсистемы является NP-сложной''.	+	y - по-прежнему класс из множества классов Y. T - множество терминальных (листовых) вершин бинарного дерева, V - вершина дерева, а <tex>c_v</tex> -
		+	класс, соответствующий терминальной вершине v. <tex>K_v(x)</tex> - конъюнкция всех предикатов на пути от корня дерева к терминальной вершине v.
-	Посчитаем приблизительно сложность ''простого перебора''.	+	Понятно, что напрямую воспользоваться методом разделения объектов в данном случае не получается, поскольку из всех конъюнкций, учавствующих в сумме,
		+	при фиксированном объекте ровно одна принимает значение 1.
		+	Мы немного изменим подход и будем использовать метод разделения объектов для настройки предикатов решающего дерева.
-	Всего <tex>2^m-1</tex> подсистем.	+	За основу синтеза решающего дерева взят жадный алгоритм, описанный в лекции [1] К.В. Воронцова.
-	Каждую подсистему надо проверить на совместность.	+
-	Например, методы, упомянутые в [3], требуют для определения совместности подсистемы состоящей из	+
-	<tex>l</tex> неравенств и имеющей ранг <tex>r</tex>,	+
-	<tex>\left(^l_r\right)\left(^n_r\right)O((l-r)r^3)</tex> операций.	+
-	Существует другой подход к получению точного решения.	+	=== Настройка предикатов. ===
-	Произвольный булев вектор <tex>(\alpha_1,...,\alpha_m)</tex> однозначно определяет подсистему <tex>Sub_{\alpha}</tex>	+	В каждом узле дерева предлагается строить предикаты вида <tex>\phi(x)=[f_n(x)\leq a]</tex>, где <tex>f_n(x)</tex> - n-ый признак объекта х.
-	системы 1.	+	Мы хотим найти одномерное разбиение объектов (по одной координате), которое будет соответствовать максимальным отступам объектов части обучающей выборки,
-	<tex>i</tex>-е неравенство входит в подсистему <tex>Sub_{\alpha}</tex> тогда и только тогда, когда <tex>\alpha_i=1</tex>.	+	попавшей в данный узел.
		+	В данном случае в качестве оценки принадлежности объекта x к классу y можно взять величину <tex>y(x-a)</tex>, если условиться, что у нас
		+	2 класса - <tex>Y=\{1,-1\}</tex>. (При этом в каждом узле элементы класса, среднее значение рассматриваемой координаты которого больше, помечать классом 1,
		+	а элементы второго класса - классом -1.)
-	Введём булеву функцию <tex>g</tex> на <tex>m</tex>-мерном булевом кубе, принимающую единицу на тех и только тех наборах	+	Максимизация отступов в пределах одного признака сводится к нахождению такого a, что величины расстояний от элементов обучающей выборки до границы a, взятые
-	<tex>\alpha</tex>, которые соответствуют несовместным системам <tex>Sub_{\alpha}</tex>.	+	с соответствующими знаками, максимальны. Как варианты можно максимизировать минимальный из отступов или сумму отступов по всем объектам.
-	Очевидно, что такая булева функция монотонна.	+	После этого остаётся максимизировать отступ по номеру признака - и мы имеем предикат <tex>\phi(x)=[f_n(x)<=a]</tex>.
-	Исходная задача сводится к поиску максимального верхнего нуля монотонной функции <tex>g</tex>.	+
-	В книге [6] приведён алгоритм, решающий эту задачу.	+
-	В худшем случае он делает <tex>\left(2^m/sqrt{m}\right)</tex> шагов, где шаг - вычисление одного значения функции g.	+
-	Этот подход немного ускоряет решение задачи, но по-прежнему работает слишком медленно.	+	Стоит отметить, что выбранный вид предиката гарантирует разбиение выборки на прямоугольники со сторонами параллельными осям координат.
-	В [1] предлагается более эффективный метод решения исходной задачи.	+	=== Настройка формы дерева. ===
-	== Вспомагательные определения и утверждения ==	+	Форма дерева настраиватся автоматически при синтезе решающего дерева жадным алгоритмом.
		+	Мы будем рекурсивно в каждой вершине дерева делить часть обучающей выборки, попавшую в данный узел, получать предикаты описанным образом и наращивать
		+	сыновей вершины, если это надо. Причём условимся, что правым сыновьям вершины будут соответствовать объекты, на которых предикат принял значение 0,
		+	а левым - на которых принял значение 1.
		+	Так мы будем действовать до тех пор, пока в какую-то из вершин не придут элементы, все принадлежащие классу y. Эту
		+	терминальную Вершину мы пометим классом y и закончим наращивание.
-	По-прежнему будем рассматривать систему 1.	+	После жадного алгоритма можно применять различные эвристики и методы, позволяющие упростить форму дерева, такие как редукция, пост-редукция, заглядывание вперёд
-	Допустим, что она совместна и имеет ранг <tex>r</tex>.	+	и так далее.
-	'''Определение 1.''' Решение системы 1 - ''узловое'', если оно обращает в равенства какие-нибудь <tex>r</tex> её	+	== Реализация жадного алгоритма и оптимизация отступов. ==
-	неравенств с линейно независимыми левыми частями.	+
-	'''Определение 2.''' Подсистема системы 1 - ''крайняя'', если, во-первых, её ранг больше нуля и равен числу неравенств в ней,	+	В рамках изучения вопроса настройки решающих деревьев был написан код программы, реализующей настройку методом разделения объектов, в основу которой лёг
-	во-вторых, хотя бы одно её узловое решение удовлетворяет системе 1.	+	жадный алгоритм синтеза деревьев.
-	'''Определение 3.''' Крайняя подсистема - ''узловая подсистема'', если все её узловые решения удовлетворяют системе 1.	+	Для настройки предикатов и оптимизации отступа по выбранному признаку проводилось несколько этапов. Сначала сортировкой пузырька сортировался массив значений
		+	выбранного признака у объектов. Далее составлялся набор ''узловых'' точек, которые в дальнейшем использовались в качестве значения порога. Эти точки выбирались посередине
		+	между двумя соседними значениями признака в отсортированном массиве. После этого применялся полный пребор по найденным ''узловым'' точкам.
-	'''Свойство 1.''' Крайняя подсистема тогда и только тогда является узловой подсистемой системы 1, когда её ранг	+	Жадный алгоритм реализовывался без досрочных остановов (использующихся для повышения ннадёжности классификации) и без дальнейших упрощений вида дерева.
-	совпадает с рангом <tex>r</tex> системы 1.	+
-	'''Теорема 1.''' Каждая совместная система линейных неравенств вида 1 отличного от нуля ранга имеет хотя бы одну узловую	+	== Пример настройки решающего дерева. ==
-	подсистему, а значит, хотя бы одно узловое решение.	+
-	С помощью этих утверждений в [1] доказывается основная лемма, на которой держится следующий алгоритм.	+	В качестве обучающей и контрольной выборки использовались точки на плоскости.
-		+	Предварительной обработки информации не происходило.
-	'''Лемма.''' Ранг максимальной совместной подсистемы (МСП) совпадает с рангом всей системы.	+	На рисунке квадратами изображены точки обучающей выборки. Соответственно, в выборке были представлены объекты двух классов.
-		+	Крестиками обозначены объекты контрольной выборки. На рисунке представлен результат классификации контрольной выборки настроенным по обучающей выборке
-	== Точное решение задачи ==	+	решающим деревом.
-		+	На втором рисунке отображено настроенное решающее дерево. Жёлтые линии - пороги предикатов.
-	=== Изложение алгоритма ===	+	/*изобразить само дерево и разбиение поузловое*/
-		+
-	Алгоритм будет выглядеть следующим образом.	+
-	Будем перебирать одну за другой подсистемы мощности и ранга <tex>r</tex> для данной несовместной системы 1 ранга <tex>r</tex>.	+
-	Среди них обязательно найдутся все узловые подсистемы для искомой МСП, так как по лемме ранг МСП равен <tex>r</tex>.	+
-	Из определения следует, что все узловые решения любой узловой подсистемы МСП удовлетворяют всей МСП.	+
-	Это означает, что достаточно найти хотя бы одно узловое решение любой узловой подсистемы МСП и подставить его в систему 1,	+
-	чтобы выделить саму МСП.	+
-		+
-	Таким образом мы заменяем все неравенства в найденной подсистеме на равенства и находим решение полученной	+
-	системы уравнений (в случае бесконечного числа решений - достаточно найти одно).	+
-	Затем мы подставляем полученное решение в исходную систему 1 и выделяем те неравенства, которым удовлетворяет полученное	+
-	решение.	+
-	Эти неравенства образуют некую совместную подсистему системы 1.	+
-	В какой-то момент мы найдём одну из узловых подсистем МСП и выделим МСП.	+
-		+
-	Трудность заключается в том, что мы не знаем какая из подсистем является узловой для МСП.	+
-	Поэтому приходится перебирать все подсистемы мощности и ранга <tex>r</tex> и находить одно их узловое решение.	+
-	Затем выделять по узловому решению подсистему, соответствующую ему.	+
-	Сравнивая мощности всех систем, полученных таким путём, мы найдём МСП. Также мы найдём одно его решение.	+
-		+
-	Из сказанного следует, что в случае системы равенств, заменив каждое из равенств	+
-		+
-	<tex>a_{i_1}x_1+\dots+a_{i_n}x_n = b_i</tex>	+
-		+
-	на два неравенства	+
-		+
-	<tex>a_{i_1}x_1+\dots+a_{i_n}x_n\leq b_i,</tex>	+
-		+
-	<tex>a_{i_1}x_1+\dots+a_{i_n}x_n\geq b_i.</tex>	+
-		+
-	мы сведём задачу к исходной. (Следует из определения узловой подсистемы и узлового решения).	+
-		+
-	=== Сложность алгоритма ===	+
-		+
-	Общее число операций приведённого алгоритма оценивается сверху выражением:	+
-		+
-	::<tex>K_1mn^2+C^r_m\left(^m_r\right)\left(K_2nr^2+K_3mn\right)</tex>,	+
-		+
-	где <tex>K_1,K_2,K_3</tex> - некоторые действительные числа.	+
-		+
-	''Краткое обоснование полученной оценки.''	+
-	Предположим, что <tex>n < m</tex>.	+
-	Вычисление ранга <tex>r</tex> матрицы исходной системы 1 требует <tex>O(mn^2)</tex> операций	+
-	(приведение к треугольному виду). Число подсистем мощности <tex>r</tex> в системе 1 - <tex>C^r_m</tex>.	+
-	Для найденной подсистемы ранга <tex>r</tex> нахождение одного узлового решения занимает <tex>O(r^2)</tex> операций (обратный ход метода Гаусса).	+
-	Подстановка найденного решения во все неравенства системы 1 - <tex>O(mn)</tex> операций.	+
-		+
-	Эта оценка уже гораздо лучше оценки для полного перебора.	+
-	К сожалению алгоритм всё ещё остаётся неподъёмным на практике при больших значениях <tex>n</tex> и <tex>m</tex>.	+
-		+
-	== Приближённое решение задачи ==	+
-		+
-	Точное решение задачи выделения максимальной совместной подсистемы - NP-полная задача.	+
-		+
-	Однако, если отказаться от нахождения точной МСП и ограничиться нахождением ''приближённой'' МСП, задачу можно решить	+
-	за полиномиальное время.	+
-	Основная идея - перебирать не всевозможные подсистемы, а только часть из них, опираясь на те или иные эвристики.	+
-		+
-	Дело в том, что для нахождения точного решения нам достаточно ''наткнуться'' хотя бы на одну узловую подсистему МСП.	+
-	При малом числе переменных и большом числе неравенств в системе 1 можно рассчитывать на то, что МСП имеет большое число	+
-	узловых подсистем.	+
-	А значит мы с большой вероятностью ''наткнёмся'' на одну из них.	+
-	В противном случае нам не попадётся ни одна из узловых подсистем МСП и мы получим неточное решение.	+
-		+
-	В качестве простейшего примера предлагается совершать лексикографический обход всех подсистем мощностью и ранга <tex>r</tex> с шагом <tex>h</tex>, произвольным образом занумеровав неравенства, входящие в систему.	+
-	Варьируя параметр <tex>h</tex> мы можем для конкретной задачи подобрать устраивающее нас время.	+
-	Для большей надёжности алгоритма параметр <tex>h</tex> надо брать как можно меньшим.	+
-		+
-	=== Численный эксперимент ===	+
-		+
-	В рамках изучения задачи был написан код, реализующий упомянутый выше алгоритм.	+
-		+
-	Для нахождения ранга и решения системы линейных уравнений в нём используется метод Гаусса с выбором главного элемента (в противном случае возможно быстрое накопление численной ошибки).	+
-		+
-	В качестве входных параметров программа принимает матрицу системы, правую часть системы и шаг перебора.	+
-		+
-	На выходе программа даёт вектор с длиной равной числу неравенств в системе, содержащий номера неравенств, вошедших в МСП. Остаток заполнен нулями. Нумерация неравенств в ответе совпадает с нумерацией при вводе матрицы системы.	+
-		+
-	В качестве эксперимента была найдена МСП системы следующих линейных неравенств:	+
-		+
-	<tex>	+
-	\begin{cases}	+
-	(1)\ 2x+y\geq-4\\	+
-	(2)\ -x\geq-3\\	+
-	(3)\ -x+y\geq0\\	+
-	(4)\ y+2x\geq34	+
-	(5)\ x+y\geq-7\\	+
-	(6)\ y\geq0\\	+
-	(7)\ -y\geq-5\\	+
-	(8)\ x\geq-5\\	+
-	\end{cases}	+
-	</tex>	+
-		+
-	с шагом перебора равным 1.	+
-		+
-	В качестве МСП программа выделила неравенства 1,2,3,6,7 и 8, что является правильным ответом.	+
-	Затем была сделана повторная попытка, на этот раз с шагом, равным 5. Таким образом, программа перебирала 9 различных подсистем вместо 28. В результате она нашла ту же самую МСП.	+
-		+
-	=== Возможные эвристики ===	+
-		+
-	Кратко опишем идею одной из возможных эвристик, позволяющих сильно сократить перебор подсистем [4].	+
-		+
-	Сделаем каждую из гиперплоскостей, описанных неравинствами, "подвижной", вводя неотрицательные ''эластичные переменные'' (''elastix variables'') в каждое из неравенств.	+
-	Теперь будем "шевелить" гиперплоскости, пока система не станет совместной.	+
-	Сведём задачу к задаче линейного программирования, минимизируя сумму ''эластичных переменных'' и иксов с заранее подобранными коэффициентами.	+
-	Такой подход также называется ''эластичным программирвоанием''(elastic programming).	+
-		+
-	Предложенная процедура отчасти схожа с методом SVM в случае линейно неразделимой выборки.	+
-		+
-	Решив эту оптимизационную задачу, мы получим некие значения эластичных переменных.	+
-	В случае совместности системы неравенств мы получим нулевые значения эластичных переменных.	+
-	В противном случае большие значения переменных соответствуют "худшим" неравенствам, в том смысле что гиперплоскости, соответствующие этим неравенствам, пришлось "двигать" больше всего для достижения совместности системы.	+
-	Логично предположить, что эти неравенства не будут входить в МСП.	+
-		+
-	Таким образом мы можем перебирать те подсистемы мощности и ранга <tex>r</tex>, которым соответствуют меньшие суммы эластичных переменных.	+
-		+
-	== Заключение ==	+
-		+
-	Нахождение МСП для системы неравенств - NP-сложная задача.	+
-	В случае поиска точного решения так или иначе приходится иметь дело с полным перебором, а как следствие - с огромными затратами времени.	+
-		+
-	При отказе от точного решения программист получает возножность значительно ускорить вычисления.	+
-	При этом, если ему удалось предложить хорошие эвристики, то с большой вероятностью он найдёт МСП системы.	+
	== Список литературы ==		== Список литературы ==
-	1. ''Катериночкина Н.Н.''&nbsp; Методы выделения максимальной совместной подсистемы системы линейных неравенств. Сообщение по прикладной математике. Москва: Вычислительный центр РАН, 1997.
-
-	2. ''J.W. Chinneck.''&nbsp; Fast Heuristics for the Maximum Feasible Subsystem Problem. INFORMS Journal on Computing, vol. 13, no. 3, pp. 210-223, 2001
-
-	3. ''Черников С.Н.''&nbsp; Линейные неравенства. М.: Наука, 1968.
-
-	4. ''J.W. Chinneck.''&nbsp; An effective polynomial-time heuristic for the minimum-cordinality IIS set-covering problem. Annals of Mathematics and Artificial Intelligence, 17, 127-144, 1996.
-
-	5. ''J.K. Sankaran.''&nbsp; A note on resolving infeasibility in linear programs by constraint relaxation. Operations Research Letters, 13, 19-20, 1993.
-
-	6. ''Катериночкина Н.Н.''&nbsp; Поиск максимального верхнего нуля монотонной функции алгебры логики. Докл. АН СССР. Т. 224. №3. С. 557-560, 1975.
-
-	== См. также ==
-	* [[Практикум ММП ВМК, 4й курс, осень 2008]]	+	[1] К.В. Воронцов, "Логические алгоритмы классификации", лекция, 2007.
-	* [[Медиа:MFSubBeta.zip | код алгоритма на C++, 3 Кб]]	+	[2] K. Bennett, N. Cristianini, J. Shawe-Taylor, D. Wu. "Enlarging the margin in perceptron
		+	decision trees", Machine Learning, 2000.

---

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

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

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

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

Содержание 1 Метод разделения объектов 2 Параметры решающих деревьев. 3 Настройка параметров решающих деревьев методом разделения объектов. 3.1 Настройка предикатов. 3.2 Настройка формы дерева. 4 Реализация жадного алгоритма и оптимизация отступов. 5 Пример настройки решающего дерева. 6 Список литературы

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

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

Предположим, что мы имеем алгоритм классификации вида , где 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.