Альтернативное дерево решений

Переменное дерево решений (ADTree) является машинным обучением метод классификации. Он обобщает деревья решений и связан с бустингом .

ADTree состоит из чередования узлов решения, которые определяют условие предиката, и узлов прогнозирования, которые содержат одно число. Экземпляр классифицируется ADTree, следуя всем путям, для которых все узлы решения истинны, и суммируя все пройденные узлы прогнозирования.

История [ править ]

ADTrees были представлены Йоавом Фройндом и Лью Мэйсоном. ^[1] Однако представленный алгоритм содержал несколько типографских ошибок. Разъяснения и оптимизации были позже представлены Бернхардом Пфарингером, Джеффри Холмсом и Ричардом Киркби. ^[2] Реализации доступны в Weka и JBoost.

Мотивация [ править ]

Оригинальные алгоритмы повышения обычно использовали либо пни решений, либо деревья решений в качестве слабых гипотез. В качестве примера, усиление пней для принятия решения создает набор взвешенных пней для принятия решения (где - количество итераций повышения), которые затем голосуют за окончательную классификацию в соответствии с их весами. Отдельные этапы принятия решений оцениваются в зависимости от их способности классифицировать данные. ${\ displaystyle T}$ ${\ displaystyle T}$

Повышение уровня простого ученика приводит к неструктурированному набору гипотез, что затрудняет вывод корреляций между атрибутами. Чередующиеся деревья решений привносят структуру в набор гипотез, требуя, чтобы они основывались на гипотезе, выдвинутой на более ранней итерации. Результирующий набор гипотез может быть визуализирован в виде дерева на основе взаимосвязи между гипотезой и ее «родителем». ${\ displaystyle T}$

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

Альтернативная древовидная структура решений [ править ]

Чередующееся дерево решений состоит из узлов решений и узлов прогнозирования. Узлы решения определяют условие предиката. Узлы прогноза содержат одно число. ADTrees всегда имеют узлы прогнозирования как корневые, так и конечные. Экземпляр классифицируется ADTree, следуя всем путям, для которых все узлы решения истинны, и суммируя все пройденные узлы прогнозирования. Это отличается от бинарных деревьев классификации, таких как CART ( дерево классификации и регрессии ) или C4.5, в которых экземпляр следует только по одному пути через дерево.

Пример [ править ]

Следующее дерево было построено с использованием JBoost на наборе данных спамбаза ^[3] (доступно в репозитории машинного обучения UCI). ^[4] В этом примере спам кодируется как1, а обычная электронная почта кодируется как−1 .

В следующей таблице содержится часть информации для одного экземпляра.

Экземпляр, подлежащий классификации
Особенность	Ценить
char_freq_bang	0,08
word_freq_hp	0,4
capital_run_length_longest	4
char_freq_dollar	0
word_freq_remove	0,9
word_freq_george	0
Другие свойства	...

Экземпляр оценивается путем суммирования всех узлов прогнозирования, через которые он проходит. В случае, приведенном выше, оценка рассчитывается как

Оценка для приведенного выше экземпляра
Итерация	0	1	2	3	4	5	6
Значения экземпляра	N / A	0,08 <0,052 = f	.4 <.195 = f	0 <0,01 = т	0 <0,005 = т	N / A	.9 <.225 = f
Прогноз	-0,093	0,74	-1,446	-0,38	0,176	0	1,66

Окончательная оценка 0,657 положительный, поэтому экземпляр классифицируется как спам. Величина значения является мерой уверенности в прогнозе. Первоначальные авторы перечисляют три возможных уровня интерпретации набора атрибутов, идентифицированных ADTree:

Отдельные узлы могут быть оценены на предмет их предсказательной способности.
Наборы узлов на одном пути могут интерпретироваться как имеющие совместный эффект.
Дерево можно трактовать как единое целое.

Следует проявлять осторожность при интерпретации отдельных узлов, поскольку оценки отражают повторное взвешивание данных на каждой итерации.

Описание алгоритма [ править ]

Входными данными для алгоритма чередующегося дерева решений являются:

Набор входных данных, где - вектор атрибутов, принимающий значение -1 или 1. Входные данные также называются экземплярами. ${\ displaystyle (x_ {1}, y_ {1}), \ ldots, (x_ {m}, y_ {m})}$ ${\ displaystyle x_ {i}}$ ${\ displaystyle y_ {i}}$
Набор весов, соответствующий каждому экземпляру. ${\ displaystyle w_ {i}}$

Основным элементом алгоритма ADTree является правило. Одно правило состоит из предусловия, условия и двух оценок. Условие - это предикат формы «значение атрибута <сравнение>». Предварительное условие - это просто логическая комбинация условий. Оценка правила включает пару вложенных операторов if:

1 если (предварительное условие)2 if (условие)3 вернуть score_one4 еще
5 вернуть score_two6 end if
7 else
8 return 09 конец, если

Алгоритму также требуются несколько вспомогательных функций:

${\ Displaystyle W _ {+} (с)}$ возвращает сумму весов всех положительно помеченных примеров, удовлетворяющих предикату ${\ displaystyle c}$
${\ Displaystyle W _ {-} (с)}$ возвращает сумму весов всех отрицательно помеченных примеров, удовлетворяющих предикату ${\ displaystyle c}$
${\ Displaystyle W (с) = W _ {+} (с) + W _ {-} (с)}$ возвращает сумму весов всех примеров, удовлетворяющих предикату ${\ displaystyle c}$

Алгоритм следующий:

1 функция ad_tree2 входа Набор из  $m$  обучающих экземпляров3 4  $w i = 1 / m$  для всех  $i$ 
5
6  $R$  $0$  $=$  правило с оценками  $a$  и  $0$  , предварительным условием «истинно» и условием «истинно». $a={\frac {1}{2}}{\textrm {ln}}{\frac {W_{+}(true)}{W_{-}(true)}}$ 7
8 множество всех возможных условий
9 для
10 значений GET , которые минимизируют
11
12
13
14  $R$  $J$  $=$  новое правило с предпосылкой  $р$  , условием  $С$  , а весовыми коэффициентами  $1$  и  $2$ 
15
16 конца для
17 возврата множество  $R$  $J$  ${\mathcal {P}}=\{true\}$  ${\mathcal {C}}=$   $j=1\dots T$  $p\in {\mathcal {P}},c\in {\mathcal {C}}$   $z=2\left({\sqrt {W_{+}(p\wedge c)W_{-}(p\wedge c)}}+{\sqrt {W_{+}(p\wedge \neg c)W_{-}(p\wedge \neg c)}}\right)+W(\neg p)$  ${\mathcal {P}}+=p\wedge c+p\wedge \neg c$  $a_{1}={\frac {1}{2}}{\textrm {ln}}{\frac {W_{+}(p\wedge c)+1}{W_{-}(p\wedge c)+1}}$  $a_{2}={\frac {1}{2}}{\textrm {ln}}{\frac {W_{+}(p\wedge \neg c)+1}{W_{-}(p\wedge \neg c)+1}}$  $w_{i}=w_{i}e^{-y_{i}R_{j}(x_{i})}$

Набор увеличивается на два предварительных условия в каждой итерации, и можно вывести древовидную структуру набора правил, отметив предварительное условие, которое используется в каждом последующем правиле. ${\mathcal {P}}$

Эмпирические результаты [ править ]

Рисунок 6 в исходной статье ^[1] демонстрирует, что деревья ADTree обычно столь же устойчивы, как и деревья решений с усилением и пни решений с расширением . Как правило, эквивалентной точности можно достичь с помощью гораздо более простой древовидной структуры, чем алгоритмы рекурсивного разделения.

Ссылки [ править ]

^ ^а ^б Йоав Фройнд и Лью Мейсон. Алгоритм чередующегося дерева решений. Труды 16-й Международной конференции по машинному обучению, страницы 124-133 (1999)
^ Бернхард Пфарингер, Джеффри Холмс и Ричард Киркби. Оптимизация индукции чередующихся деревьев решений. Труды пятой Тихоокеанско-азиатской конференции по достижениям в области обнаружения знаний и интеллектуального анализа данных. 2001, стр. 477-487.
^ "Репозиторий машинного обучения UCI" . Ics.uci.edu . Проверено 16 марта 2012 .
^ "Репозиторий машинного обучения UCI" . Ics.uci.edu . Проверено 16 марта 2012 .

Внешние ссылки [ править ]

Введение в Boosting и ADTrees ( содержит множество графических примеров чередования деревьев решений на практике).
Программное обеспечение JBoost, реализующее ADTrees.

[Freund99-1] а ^б Йоав Фройнд и Лью Мейсон. Алгоритм чередующегося дерева решений. Труды 16-й Международной конференции по машинному обучению, страницы 124-133 (1999)

[Pfahringer-2] Бернхард Пфарингер, Джеффри Холмс и Ричард Киркби. Оптимизация индукции чередующихся деревьев решений. Труды пятой Тихоокеанско-азиатской конференции по достижениям в области обнаружения знаний и интеллектуального анализа данных. 2001, стр. 477-487.

[3] "Репозиторий машинного обучения UCI" . Ics.uci.edu . Проверено 16 марта 2012 .

[4] "Репозиторий машинного обучения UCI" . Ics.uci.edu . Проверено 16 марта 2012 .

[1]