交互決定木

交代決定木（ADTree）は、分類のための機械学習手法です。これは決定木を一般化し、ブースティングと関連があります。

ADTreeは、述語条件を指定する決定ノードと、単一の数値を含む予測ノードの交互配置で構成されます。インスタンスは、すべての決定ノードが真となるすべてのパスを辿り、通過した予測ノードを合計することでADTreeによって分類されます。

歴史

ADTreeはYoav FreundとLlew Masonによって導入されました。 ^[1] しかし、提示されたアルゴリズムにはいくつかの誤植がありました。その後、Bernhard Pfahringer、Geoffrey Holmes、Richard Kirkbyによって明確化と最適化が行われました。^[2]実装はWekaとJBoost で利用可能です。

モチベーション

従来のブースティングアルゴリズムでは、通常、決定木または決定木のいずれかを弱仮説として使用していました。例えば、ブースティング決定木では、重み付けされた決定木のセット（ここではブースティング反復回数）が作成され、それらの重みに基づいて最終的な分類が投票されます。個々の決定木は、データを分類する能力に応じて重み付けされます。 $T$ $T$

単純な学習器をブースティングすると、構造化されていない仮説集合が生成され、属性間の相関関係を推測することが困難になります。交代型決定木は、以前の反復で生成された仮説に基づいて仮説集合を構築することを必須とすることで、仮説集合に構造を導入します。結果として得られる仮説集合は、仮説とその「親」の関係に基づいてツリー構造で視覚化できます。 $T$

ブースティングアルゴリズムのもう一つの重要な特徴は、反復ごとにデータに異なる分布が与えられることです。誤分類されたインスタンスには大きな重みが与えられ、正しく分類されたインスタンスには小さな重みが与えられます。

交互決定木構造

交代決定木は、決定ノードと予測ノードで構成されます。 決定ノードは述語条件を指定します。 予測ノードには単一の数値が含まれます。ADTreeは常にルートとリーフの両方に予測ノードを持ちます。ADTreeは、すべての決定ノードが真となるすべてのパスを辿り、通過した予測ノードを合計することでインスタンスを分類します。これは、インスタンスがツリー内の1つのパスのみを辿る CART（分類回帰木）やC4.5などの2分分類木とは異なります。

例

以下のツリーは、スパムベースデータセット^[3]（UCI機械学習リポジトリから入手可能）に基づいてJBoostを使用して構築された。^[4] この例では、スパムは次のようにコード化されている。1通常の電子メールは次のようにコード化されます−1。

次の表には、単一インスタンスの情報の一部が含まれています。

分類対象となるインスタンス
特徴	価値
文字頻度バン	0.08
単語頻度	0.4
最長資本ランレングス	4
文字頻度ドル	0
単語頻度削除	0.9
単語頻度ジョージ	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によって識別される属性セットについて、3つの解釈レベルを挙げています。

個々のノードの予測能力を評価できます。
同じパス上のノードのセットは共同効果を持つと解釈される可能性がある
ツリーは全体として解釈できます。

スコアは各反復におけるデータの再重み付けを反映するため、個々のノードを解釈する際には注意が必要です。

アルゴリズムの説明

交互決定木アルゴリズムへの入力は次のとおりです。

入力のセット。は属性のベクトルであり、-1または 1 のいずれかです。入力はインスタンスとも呼ばれます。 $(x_{1},y_{1}),\ldots ,(x_{m},y_{m})$ $x_{i}$ $y_{i}$
各インスタンスに対応する重みのセット。 $w_{i}$

ADTreeアルゴリズムの基本要素はルールです。1つのルールは、前提条件、条件、そして2つのスコアで構成されます。条件は「属性 <比較> 値」という形式の述語です。前提条件は、単に条件の論理積です。ルールの評価は、ネストされたif文のペアによって行われます。

1 if（前提条件）2 if (条件)3 スコア1を返す4 そうでない場合5 score_twoを返す6 終了 if
7 else
8 0を返す9 終了の場合

アルゴリズムではいくつかの補助関数も必要です。

$W_{+}(c)$ 述語を満たすすべての肯定ラベル付き例の重みの合計を返します。 $c$
$W_{-}(c)$ 述語を満たすすべての否定ラベル付き例の重みの合計を返します。 $c$
$W(c)=W_{+}(c)+W_{-}(c)$ 述語を満たすすべての例の重みの合計を返します $c$

アルゴリズムは次のとおりです。

1 関数ad_tree2 入力 $m個$ のトレーニングインスタンスのセット34  $w i$  =すべての i について $1$  $/$  $m$ 
5 6  $R$  $0$  $=スコア$  $a$ と $0$  、前提条件「真」、条件「真」を持つルール。 $a={\frac {1}{2}}{\textrm {ln}}{\frac {W_{+}(true)}{W_{-}(true)}}$ 7 8 すべての可能な条件の集合9 に対して10 を最小化する値を取得する11 12 13 14  $R$  $j$  $=前提条件$  $p$ 、条件 $c$ 、重み $a$  $1$ と $a$  $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})}$

セットは各反復で 2 つの前提条件ずつ増加し、連続する各ルールで使用される前提条件を記録することで、ルールセットのツリー構造を導出できます。 ${\mathcal {P}}$

実証的結果

原著論文^{[1]の図6は、ADTreeがブースト決定木やブースト}決定スタンプと同程度の堅牢性を示すことを示しています。通常、再帰分割アルゴリズムよりもはるかに単純なツリー構造で同等の精度を達成できます。

参考文献

^ ab Freund, Y.; Mason, L. (1999). 「交代決定木学習アルゴリズム」(PDF) . 第16回国際機械学習会議 (ICML '99). Morgan Kaufmann. pp. 124– 133. ISBN 978-1-55860-612-8。
^ Pfahringer, Bernhard; Holmes, Geoffrey; Kirkby, Richard (2001). 「交代決定木の誘導の最適化」(PDF) .知識発見とデータマイニングの進歩. PAKDD 2001.コンピュータサイエンス講義ノート. 第2035巻. Springer. pp. 477– 487. doi :10.1007/3-540-45357-1_50. ISBN 978-3-540-45357-4。
^ 「Spambaseデータセット」UCI機械学習リポジトリ. 1999年。
^ Dua, D.; Graff, C. (2019). 「UCI機械学習リポジトリ」. カリフォルニア大学アーバイン校情報・コンピュータサイエンス学部.

外部リンク

Boosting と ADTrees の紹介 (実際の交互決定木のグラフィカルな例が多数あります)。
ADTree を実装する JBoost ソフトウェア。

[Freund99-1] Freund, Y.; Mason, L. (1999). 「交代決定木学習アルゴリズム」(PDF) . 第16回国際機械学習会議 (ICML '99). Morgan Kaufmann. pp. 124– 133. ISBN 978-1-55860-612-8。

[Pfahringer-2] Pfahringer, Bernhard; Holmes, Geoffrey; Kirkby, Richard (2001). 「交代決定木の誘導の最適化」(PDF) .知識発見とデータマイニングの進歩. PAKDD 2001.コンピュータサイエンス講義ノート. 第2035巻. Springer. pp. 477– 487. doi :10.1007/3-540-45357-1_50. ISBN 978-3-540-45357-4。

[3] 「Spambaseデータセット」UCI機械学習リポジトリ. 1999年。

[4] Dua, D.; Graff, C. (2019). 「UCI機械学習リポジトリ」. カリフォルニア大学アーバイン校情報・コンピュータサイエンス学部.