通常の決定木との違いは
特徴選択の近似手法
幅 \(R\) の区間に生じる値が,\(n\) 個あるとする.
このとき,標本平均を \(\bar{x}\) とすると,真の平均が \(\bar{r}-\epsilon\) 以上である確率が \(1-\delta\) 以上になるには,
片側のHoeffdingの不等式から:
\[\epsilon=\sqrt{\frac{R^2\ln(1/\delta)}{2 n}}\]
今,ある決定木が仮に得られているとする. ここで,ある葉ノードには幾つか事例が分類されているとする. 全ての特徴に対し,ID3の情報量利得やCARTのGini係数のような特徴選択規準を計算. データストリームは無限にデータが来るので,全部のデータを見てから最良の特徴を選ぶことはできない. そこで,最良の規準値とその次の規準値の差が \(\epsilon\) 以上になれば,その特徴で分割する.
木の生成はルートだけの決定木から,この方法を用いて再帰的に生成する.
通常の決定木では,分割前の葉ノードにたまっていた事例を,分割後の葉ノードに振り分ける.しかし,それには多量のメモリが必要なので,分割ごとにデータは廃棄し,新たに葉ノードに分類されたデータで次の分割を行う.
Hoeffding Treeに対し,特徴の評価規準値の差が少ない場合や,評価規準の計算の高速化といった改良を行ったもの.
-- しましま