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

редактировать

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

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

Содержание

1 История
2 Мотивация
3 Древовидная структура альтернативных решений
- 3.1 Пример
4 Описание алгоритма
5 Эмпирические результаты
6 Ссылки
7 Внешние ссылки

История

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

Мотивация

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

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

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

Структура дерева альтернативных решений

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

Пример

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

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

Классифицируемый экземпляр
Feature	Значение
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
Значения экземпляра	Н / Д	.08 <.052 = f	.4 <.195 = f	0 <.01 = t	0 < 0.005 = t	Н / Д	.9 <.225 = f
Прогноз	-0,093	0,74	-1,446	- 0,38	0,176	0	1,66

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

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

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

Описание алгоритма

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

Набор входных данных $(x 1, y 1),…, (xm, ym) {\ displaystyle (x_ {1}, y_ {1}), \ ldots, (x_ {m}, y_ {m})}$ $(x_1,y_1),\ldots,(x_m,y_m)$ где $xi {\ displaystyle x_ {i}}$ $x_ {i}$ - вектор атрибутов, а $yi {\ displaystyle y_ {i}}$ $y_ {i}$ либо -1, либо 1. Входные данные также называются экземплярами.
A набор весов $wi {\ displaystyle w_ {i}}$ $w_ {i}$ , соответствующий каждому экземпляру.

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

1 if(предварительное условие) 2 if (условие) 3 return score_one 4 else 5 return score_two 6 end if 7 else 8 return 0 9 end if

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

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

Алгоритм выглядит следующим образом:

1 function ad_tree 2 input Набор из m обучающих экземпляров 3 4 w i = 1 / m для всех i 5  $a = 1 2 ln W + (true) W - (true) {\ dis playstyle a = {\ frac {1} {2}} {\ textrm {ln}} {\ frac {W _ {+} (true)} {W _ {-} (true)}}}$  $a = \ frac 1 2 \ textrm {ln} \ frac {W _ + (true)} {W _- (true)}$ 6 R 0 = правило с оценками а и 0, предварительным условием «истина» и условием «истина». 7  $P = {true} {\ displaystyle {\ mathcal {P}} = \ {true \}}$  $\ mathcal {P} = \ {true \}$ 8  $C = {\ displaystyle {\ mathcal {C}} =}$  $\ mathcal {C} =$ набор всех возможных условий 9 для $j = 1… T {\ displaystyle j = 1 \ dots T}$  $j = 1 \ dots T$ 10  $p ∈ P, c ∈ C {\ displaystyle p \ in {\ mathcal {P}}, c \ in {\ mathcal {C}}}$  $p \ in \ mathcal {P}, c \ in \ mathcal {C}$ получить значения, которые минимизируют  $z = 2 (W + (p ∧ c) W - ( п ∧ с) + W + (п ∧ ¬ c) W - (п ∧ ¬ c)) + W (¬ p) {\ displaystyle 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)}$  $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)$ 11  $P + = p ∧ c + p ∧ ¬ c {\ displaystyle {\ mathcal {P}} + = p \ wedge c + p \ wedge \ neg c}$  $\ mathcal {P} + = p \ wedge c + p \ wedge \ neg c$ 12  $a 1 = 1 2 ln W + (p ∧ c) + 1 W - (p ∧ c) + 1 {\ displaystyle a_ {1} = {\ frac {1} {2 }} {\ textrm {ln}} {\ frac {W _ {+} (p \ wedge c) +1} {W _ {-} (p \ wedge c) +1}}}$  $a_1 = \ frac {1} {2} \ textrm {ln} \ frac {W _ + (p \ wedge c) +1} {W _- (p \ wedge c) +1}$ 13  $a 2 = 1 2 ln W + (p ∧ ¬ c) + 1 W - (p ∧ ¬ c) + 1 {\ displaystyle a_ {2} = {\ frac {1} {2}} {\ textrm { ln}} {\ frac {W _ {+} (p \ wedge \ neg c) +1} {W _ {-} (p \ wedge \ neg c) +1}}}$  $a_2 = \ frac {1} {2} \ textrm {ln} \ frac {W _ + (p \ wedge \ neg c) +1} {W _- (p \ wedge \ neg c) +1}$ 14 R j = новое правило с предусловием p, условием c и весами a 1 и a 2 15  $wi = wie - yi R j ( xi) {\ displaystyle w_ {i} = w_ {i} e ^ {- y_ {i} R_ {j} (x_ {i})}}$  $w_i = w _i e ^ {-y_i R_j (x_i)}$ 16 конец для 17 return набор R j

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

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

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

Ссылки

Внешние ссылки

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