Hoeffding tree / very fast decision tree (VFDT)

データストリームを対象とした決定木学習アルゴリズム

Hoeffding tree

通常の決定木との違いは

  • Hoeffding限界を使って,ノードの分割に使う特徴を近似的に選ぶ
  • 全部のデータを保持することはせず,ノードを分割するごとにデータを捨てる. そして,ストリームからの新たなデータを使ってその後の学習を行う.

特徴選択の近似手法
幅 \(R\) の区間に生じる値が,\(n\) 個あるとする. このとき,標本平均を \(\bar{x}\) とすると,真の平均が \(\bar{r}-\epsilon\) 以上である確率が \(1-\delta\) 以上になるには, 片側のHoeffdingの不等式から: \[\epsilon=\sqrt{\frac{R^2\ln(1/\delta)}{2 n}}\]

今,ある決定木が仮に得られているとする. ここで,ある葉ノードには幾つか事例が分類されているとする. 全ての特徴に対し,ID3情報量利得やCARTGini係数のような特徴選択規準を計算. データストリームは無限にデータが来るので,全部のデータを見てから最良の特徴を選ぶことはできない. そこで,最良の規準値とその次の規準値の差が \(\epsilon\) 以上になれば,その特徴で分割する.

木の生成はルートだけの決定木から,この方法を用いて再帰的に生成する.

通常の決定木では,分割前の葉ノードにたまっていた事例を,分割後の葉ノードに振り分ける.しかし,それには多量のメモリが必要なので,分割ごとにデータは廃棄し,新たに葉ノードに分類されたデータで次の分割を行う.

VFDT

Hoeffding Treeに対し,特徴の評価規準値の差が少ない場合や,評価規準の計算の高速化といった改良を行ったもの.

-- しましま

関連項目

リンク集

Freeware

関連文献


トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2010-02-11 (木) 16:11:26 (2494d)