교대 결정 트리

교대결정트리(ADTree)는 분류를 위한 기계학습방법이다.의사결정 트리를 일반화하고 활성화와 관련이 있습니다.

ADTree는 술어 조건을 지정하는 결정 노드와 단일 번호를 포함하는 예측 노드의 교대로 구성됩니다.인스턴스는 ADTree에 의해 모든 결정 노드가 참인 모든 경로를 추적하고 통과하는 모든 예측 노드를 합계함으로써 분류됩니다.

역사

ADTree는 Yoav Freund와 Llew ^[1]Mason에 의해 도입되었습니다.그러나 제시된 알고리즘에는 몇 가지 오타가 있었습니다.나중에 Bernhard Pahringer, Geoffrey Holmes 및 Richard ^[2]Kirkby가 명확화와 최적화를 발표했습니다.구현은 Weka 및 JBoost에서 이용할 수 있습니다.

동기

원래 승압 알고리즘은 일반적으로 의사 결정 스탬프 또는 의사 결정 트리를 약한 가설로 사용했다.예를 들어 의사 결정 스탬프를 증가시키면 $가중치$ T$($$여기$서$$T(\$displaystyle$ T$)$는 증가 반복 횟수)의 $일련$의 의사 결정 스탬프가 생성되며, T(\$displaystyle$ T)는$$ 가중치에 따라 최종 분류에 투표한다.개별 의사 결정 스탬프는 데이터를 분류하는 능력에 따라 가중치가 부여됩니다.

단순 학습자를 활성화하면 T$(\displaystyle$ T$)$ $가설$이 구조화되지 않아 속성 간의 상관 관계를 추론하기가 어렵다.교대 결정 트리는 이전 반복에서 생성된 가설을 구축하도록 요구함으로써 가설 집합에 구조를 도입합니다.결과 가설 집합은 가설과 그 "부모" 사이의 관계에 기반하여 트리로 시각화할 수 있습니다.

부스트 알고리즘의 또 다른 중요한 특징은 데이터가 각 반복마다 다른 분포를 제공한다는 것입니다.잘못 분류된 인스턴스에는 더 큰 가중치가 부여되지만 정확하게 분류된 인스턴스에는 더 적은 가중치가 부여됩니다.

교대 의사결정 트리 구조

대체 의사결정 트리는 의사결정 노드와 예측 노드로 구성된다.결정 노드는 술어 조건을 지정합니다.예측 노드에는 단일 번호가 포함됩니다.ADTree에는 항상 루트와 리프로 예측 노드가 있습니다.인스턴스는 ADTree에 의해 모든 결정 노드가 참인 모든 경로를 추적하고 통과하는 모든 예측 노드를 합계함으로써 분류됩니다.이는 CART(Classification and Regression Tree) 또는 C4.5와 같은 이진 분류 트리와는 다릅니다.이 트리에서는 인스턴스가 하나의 경로만 따릅니다.

예

다음 트리는 스팸 기반^[3] 데이터 세트의 JBoost를 사용하여 구성되었습니다(UCI 머신 러닝 저장소에서 ^[4]사용 가능).이 예에서 스팸은 1로 코드화되고 일반 전자 메일은 -1로 코드화됩니다.

다음 표에는 단일 인스턴스에 대한 정보의 일부가 포함되어 있습니다.

분류할 인스턴스

특징	가치
char_freq_bang	0.08
word_freq_hp	0.4
capital_run_length_module	4
char_freq_$	0
word_freq_remove	0.9
word_freq_george	0
기타 기능	...

인스턴스는 인스턴스가 통과하는 모든 예측 노드를 합산하여 점수가 매겨집니다.위의 경우 점수는 다음과 같이 계산됩니다.

위 인스턴스의 점수

반복	0	1	2	3	4	5	6
인스턴스 값	—	0.08 < .052 = f	. 4 < .filength =	0 < 0.01 = t	0 < 0.005 = t	—	.9 < .timeout = f
예측	-0.093	0.74	-1.446	-0.38	0.176	0	1.66

최종 점수 0.657은 양수이므로 인스턴스는 스팸으로 분류됩니다.값의 크기는 예측에 대한 신뢰의 척도입니다.원저자는 ADTree에 의해 식별된 일련의 속성에 대한 세 가지 잠재적 해석 수준을 열거한다.

• 개별 노드의 예측 능력을 평가할 수 있습니다.
• 같은 경로상의 노드 세트는 접합 효과를 갖는 것으로 해석될 수 있습니다.
• 그 나무는 전체로 해석될 수 있다.

점수는 각 반복에서 데이터의 재 가중치를 반영하므로 개별 노드를 해석할 때 주의해야 한다.

알고리즘 설명

교대 Decision Tree 알고리즘에 대한 입력은 다음과 같습니다.

• 입력$({\displaystyle }$ ${\displaystyle {x\mathrm{}}_{}}$1, ${\displaystyle {}_{}{1\mathrm{}}_{}}$ ${\displaystyle ),}$ ${\displaystyle ...,}$ (${\displaystyle x_{}}$m , ${\displaystyle {}_{}{m}_{}}$ $),$ {$displaystyle (x_{1}),$ \$ldots$, ($x_{m}, y_{m})$ (${\displaystyle x_{}}$ i {$displaystyle x_{$i$$}는 속성의 $벡터$이고, ${\displaystyle y_{}}${$displaystyle y_{i$}는$$ - 1 또는 1 중 하나입니다.입력은 인스턴스라고도 합니다.
• 각 인스턴스에 대응하는 $w_{i}$의 무게 $세트{\displaystyle {}_{}}$.

ADTree 알고리즘의 기본 요소는 규칙입니다.하나의 규칙은 전제조건, 조건 및 2개의 점수로 구성됩니다.조건은 "attribute <comparison> value" 형식의 술어입니다.전제조건은 단순히 조건의 논리적 결합이다.규칙 평가에는 다음 경우 중첩된 쌍이 포함됩니다.

1 if (전제조건) 2 if (조건) 3 return score _ 1 other 4 other 5 return score _ 2 end 7 other 8 return 0 9 end :

알고리즘에는 다음과 같은 보조 기능도 필요합니다.

• ${\displaystyle W_{}}$+ (${\displaystyle c}$) {$displaystyle W_{+}(c)}$은(는) $술어{\displaystyle }$c {$displaystyle$ c$}$를 충족하는 라벨이 지정된 모든 예제의 가중치 합계를 반환합니다.
• ${\displaystyle W_{}}$-${\displaystyle {}_{}}$(${\displaystyle c}$) { $displaystyle$W _ { - $}$( c ) $술어{\displaystyle }$c { $displaystyle$ c$$}를$$ 만족하는 음의 라벨이 붙은 모든 예제의 가중치 합계를 반환합니다.
• $displaystyle$$W_{+}(c)+$$W_{-}(c)}$는 $술어{\displaystyle }$c{$displaystyle$ c$}$를 충족하는 모든 예제의 가중치 합계를 반환합니다.

알고리즘은 다음과 같습니다.

1 function ad_tree 2 input m 트레이닝 인스턴스 세트3 4i w = 모든 i5 ${\displaystyle a\frac{\mathrm{}}{}}$ ${\displaystyle =}$ ${\displaystyle \frac{1}{}}$ ${\displaystyle \text{2}}$ ${\displaystyle LN\frac{{}_{}}{}}$W + ( ${\displaystyle \frac{t}{}}$ ${\displaystyle \frac{r}{u}}$ e${\displaystyle \frac{{}_{}}{}}$)${\displaystyle \frac{{}_{}}{}}$W - ( ${\displaystyle \frac{\mathrm{tru}}{}}$ e$$) { $display$ a =$scfrac {$1} {2} {\$textrm$ {ln} {\$frac$ {$W_+}($true) {\frac {W_} {\frac} {\fru} {\} {\frac} {\frue$}$ {\m} {\m} {\m} {\m} {\m} {\m} {\W_ᆫ(진정한)}}}6R0고 0, 전제 조건"진정한"및 상태"사실."7P){tr우라늄 e}{\displaystyle{{P\mathcal}}=\{true\}}8C={\displaystyle{{C\mathcal}}=}j에게 가능한 모든 조건 9)의 집합 1쭉 펼쳐져 T{\displaystyle j=1\dots T}10p∈ P, c∈ C{\displays 점수에 규칙을 일고 있다.t$yle$ p$\in {mathcal {P}},$ c$$$\in {mathcal$ {$C}},$ c\$in$ {mathcal}의 ${\displaystyle \sqrt{{}_{}}}$ $=$ (${\displaystyle \sqrt{{}_{}W{}_{}}}$+ ( ${\displaystyle \sqrt{pc}}$c${\displaystyle }$)${\displaystyle \sqrt{{}_{}}}$+${\displaystyle \sqrt{{}_{}}W\sqrt{{}_{}}}$+${\displaystyle \sqrt{{}_{}}}$( ${\displaystyle \sqrt{{}_{}\wedge }}$ ${\displaystyle \sqrt{\mathrm{\neg }}}$ ${\displaystyle \sqrt{c}}$)${\displaystyle }$+${\displaystyle W}$ ( ${\displaystyle p}$ ∧ p ) + W ( ${\displaystyle \mathrm{（}}$ ¬ p$$¬ c${\displaystyle \sqrt{}}$） \ $display z2 _$ rt { $rtw$ } { rtw } { rtimep } { left ）$W_{-}(p\wedge c)}}+{\sqrt {W_{+}(p\wedge \neg c)$$W_{-}(p\wedge \neg c)}}\right)+$$W$$(\neg$ p$)$ 11$$${\displaystyle \mathcal{}}$P + ${\displaystyle =}$ ${\displaystyle pc}$c + ${\displaystyle p}$ ${\displaystyle \wedge }$ ${\displaystyle c}$ ∧ c$$ c { $display$ style } = $p$$\wedge$ c+p\$neg c} 12$ a $1$$=$ ${\displaystyle \text{1}}$ ${\displaystyle \frac{2}{}}$$$${\displaystyle Ln}$ + ( ${\displaystyle \frac{p}{c}}$ c${\displaystyle \frac{}{}}$) + ${\displaystyle \frac{{}_{}}{}}$W${\displaystyle \frac{{}_{}}{}}$-${\displaystyle \frac{{}_{}}{}}$( ${\displaystyle \frac{p}{}}$∧${\displaystyle \frac{}{}}$c${\displaystyle \frac{}{}}$) +$$ \ $display style a$_ { { 1$}$(p∧ ¬ c)+1W−(p∧ ¬ c)+1{\displaystyle a_{2}={\frac{1}{2}}{\textrm{ln}}{\frac{W_{+}(\neg cp\wedge)+1}{W_{-}(\neg cp\wedge)+1}}}14Rj=전제 조건 p과 새로운 규칙을 조건으로 c, 그리고 무게 a1과 15wa2 나는 정도 아니 나는 에 들어간다면−는 y나는 Rj()나는){\displaystyle w_{나는}=w_{나는}e^{-y_{나는}R_{j}(x_{.나는})}} R 17개 반환 세트j 16개$$끝

$세트{\displaystyle \mathcal{}}$ P$(\$는 반복마다 2개의 전제조건이 증가하며, 연속되는 각 규칙에서 사용되는 전제조건을 메모하여 규칙 집합의 트리 구조를 도출할 수 있습니다.

경험적 결과

원본^[1] 문서의 그림 6은 ADTree가 일반적으로 증가된 의사결정 트리 및 증가된 의사결정 스탬프만큼 견고하다는 것을 보여줍니다.일반적으로 재귀 분할 알고리즘보다 훨씬 단순한 트리 구조로 동일한 정확도를 달성할 수 있습니다.

레퍼런스

외부 링크

• Boosting 및 ADTree에 대한 소개(실제로 교대로 이루어지는 의사결정 트리의 그래픽 예가 많다).
• ADTree를 구현하는 JBoost 소프트웨어.