* Hoeffding tree / very fast decision tree (VFDT) [#w54723f2]

//ここには %項目の説明を書いてください.よろしければ署名しておいてください.

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

*** Hoeffding tree [#l813f8f8]

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

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

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

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

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

*** VFDT [#ff076bb3]

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

> -- しましま

** 関連項目 [#j7ab94a1]

//英語や同義語のあとに,#brで区切って関連する項目をリストしてください.
-[[Hoeffding tree]]
#br
-[[データストリーム]]
-[[Hoeffdingの不等式]]
-[[決定木]]
#br
-[[検索:VFDT]]

** リンク集 [#r9057e12]

//関連するWWW資源があればリンクしてください.

*** Freeware [#d1fec748]

-[[VFML (Very Fast Machine Learing)>http://www.cs.washington.edu/dm/vfml/main.html]]:
VFDTを含む幾つかのデータストリーム用の機械学習アルゴリズムの実装コード

** 関連文献 [#edbfe11c]

//この%項目%に関連する書籍や論文を紹介してください.

-基本文献~
P.Domingos and G.Hulten "Mining High-Speed Data Streams" KDD2000 (2000)~
[[GoogleScholarAll:Mining High-Speed Data Streams]]
-VFDTを,データストリームの変化に対応できるように改良したCVFDT~
G.Hulten, L.Spencer, and P.Domingos "Mining Time-Changing Data Streams" KDD2001 (2001)~
[[GoogleScholarAll:Mining Time-Changing Data Streams]]
-[[Book/Data Mining - Concepts and Techniques]] 8.1.4節

トップ   編集 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS