オンライン決定木
- 提唱者
- Domingos, P. & Hulten, G.
- 年
- 2000
- 種類
- Incremental supervised classifier
- 系統
- Machine learning
この文章は機械翻訳で、まだ確認されていません。 英語の原文を読む
何をする手法か?
オンライン決定木は、過去の例を再訪することなく、連続するデータストリームから段階的に成長する決定木です。支配的なアルゴリズムであるHoeffding Tree(VFDT)は、ノードで十分な例が観測されたかどうかを自信を持って分割するためにHoeffdingバウンドを使用し、無限の可能性のあるデータストリームでのスケーラブルなリアルタイム分類を可能にします。
手法の背後にある直感
標準的な決定木は、最適な分割を見つけるためにデータセット全体を繰り返しスキャンすることによって構築されます。ストリーミング設定では、データが一度に1つずつ到着し、保存できないため、これは不可能です。オンラインアプローチでは、各リーフで実行統計のみを保持します。十分な例が集まると、Hoeffdingバウンド(統計的保証)により、観測された最適な分割が、考えられるすべての例を見たとしても、最適な分割のままであることが確認されます。その時点で初めて、ツリーは実際に分割され、過去のデータを一度も見ることなく、単一のリーフから常に深くなる構造へと成長します。
歴史学
非常に高速な決定木(VFDT)またはHoeffding Treeの基礎となるアルゴリズムは、DomingosとHultenによってKDD 2000で導入されました。Hoeffdingの不等式を適用してデータストリームからの分割属性の選択における誤差を制限し、例を保存することなく漸近的に正しいツリー誘導を可能にしました。Hulten、Spencer、Domingosは2001年にこれをコンセプトドリフトストリームに拡張しました。このアプローチは、MOA(Massive Online Analysis)フレームワークの礎となり、世代のストリーミングアンサンブルメソッドに影響を与えました。
使うべき場面
データが連続ストリームとして到着する場合、データセット全体を保存することが、量またはプライバシーの制約により実行不可能である場合、または各新しい観測でリアルタイムでモデルを更新する必要がある場合に、オンライン決定木を使用します。IoTセンサーのストリーム、クリックストリーム分類、進化するパターンの不正検出、およびコンセプトドリフトが予想され、モデルがゼロから再トレーニングすることなく適応する必要があるあらゆる設定に適しています。データセットが小さく静的な場合は使用しないでください。標準的な決定木またはランダムフォレストの方が実装が速く、より正確になります。また、解釈可能性が重要で、分割しきい値が時間とともに変化することを受け入れない場合は避けてください。
限界と注意点
- 小さなデータセットでの精度は、Hoeffdingバウンドが早期の分割を行う前に多くの例を必要とするため、通常はバッチ決定木よりも低くなります。
- 基本的なアルゴリズムでは、分割の決定は取り消し不可能であり、明示的なサブツリー置換が追加されない限り、早期の不適切な分割が持続する可能性があります。
- 信頼度パラメータδと分割評価間のグラウンド期間の調整には、ドメイン知識が必要です。
- ツリーの解釈可能性は、新しい分割が追加されるにつれて時間とともに変化するため、静的なレポート作成が困難になります。
出典に示された条件は、独立した科学的レビューや分析エンジンによる検証の代わりにはなりません。
強み
- ノードあたりの定数メモリで単一パスでデータを処理し、理論的に無限のストリームにスケーリングします。
- 十分なデータがあれば、バッチツリーと同じ分割になるという理論的保証をHoeffdingバウンドを通じて提供します。
- 完全な再トレーニングなしで非定常分布に適応するために、ドリフト検出器を組み込むことができます。
- バッチメソッドとは異なり、最初の例からすぐに使用可能なモデルを提供します。
- データを保存することが非現実的または法的に制限されている高スループット設定を自然に処理します。
応用
- 金融取引ストリームでのリアルタイム不正検出。
- トラフィック統計が継続的に到着するネットワーク侵入検出。
- メモリ制約のあるエッジデバイスでのIoTおよびセンサーデータ分類。
- データ量が完全なストレージを排除するクリックストリームまたはユーザー行動モデリング。
- 電子メールの言語パターンが時間とともに進化する適応型スパムフィルタリング。
- より複雑なストリーミングアンサンブルのベンチマークとなるベースラインストリーミング分類器。
使い方
使い方
ラベル付けされた各例は、データストリームから一度に1つずつ到着します。ツリーは、ルートから既存の分割を経て適切なリーフまでそれをルーティングし、インスタンスがラベル付けされる前にそのインスタンスの予測を行います。
クラス条件付きカウントやガウス平均・分散など、すべての候補分割属性の十分統計量が、インスタンスを受信したリーフで更新されます。生のデータは保持されず、これらのコンパクトな要約のみが成長します。
Hoeffding(またはChernoff)バウンドε = sqrt(R^2 * ln(1/δ) / (2n))は、少なくとも1 - δの確率で、観測された最適な分割属性と真の最適な分割との間の最大誤差を定量化します。nが増加すると、εはゼロに向かって減少します。
数式
\varepsilon = \sqrt{\frac{R^2 \ln(1/\delta)}{2n}}最良と2番目に良い分割候補の情報利得の差が現在のHoeffdingバウンドを超えた場合、そのリーフは勝った属性での内部分割ノードに置き換えられ、2つの新しいリーフカウンターが初期化されます。それ以外の場合、ノードはより多くのデータを待ちます。
到着するすべてのインスタンスは、そのラベルが更新に使用される前に、現在のツリーからクラス予測を受け取ります。オプションで、ドリフト検出器(例:ADWIN)がリーフのエラー率を監視します。コンセプトドリフトが検出されると、モデルを最新の状態に保つためにサブツリーが置き換えられることがあります。
よくある落とし穴
- Hoeffding信頼度δを緩すぎると、代表性のない早期のデータで時期尚早な分割が発生します。
- コンセプトドリフトの無視。静的なオンラインツリーを分布がシフトするデータで実行すると、サイレントな精度低下につながります。
- 同じストリームの全データでトレーニングされたバッチモデルに対する精度の比較。これはバッチモデルに不公平な利点を与えます。
- 分割される前のリーフは常にこれまでに見た多数派クラスを予測することを忘れている。これは、不均衡なストリームの初期段階では誤解を招く可能性があります。
よくある質問
Hoeffding Treeは標準的なCART決定木とどのように異なりますか?
CARTツリーは、各ノードでデータセット全体をスキャンして、グローバルに最適な分割を見つけます。Hoeffding Treeは代わりに、例が1つずつ到着するのを監視し、統計理論が、より多くのデータがあっても、観測された勝者が引き続き勝つことを保証する場合にのみ分割をコミットします。生の例は保存されません。
オンライン決定木はコンセプトドリフトを処理しますか?
基本的なHoeffding Treeはドリフトを自動的に検出しません。Concept-adapting Very Fast Decision Tree(CVFDT)や、ADWINまたはPage-Hinkleyドリフト検出器と組み合わせたバージョンなどの拡張機能は、ドリフトが検出されたときに古いサブツリーを置き換えることができます。
グラウンド期間とは何ですか?どのように設定すべきですか?
グラウンド期間とは、連続する分割評価の間でリーフに到着する例の数です。値が大きいほど計算は削減されますが、分割は遅延します。値が小さいほど、CPUコストが高くなりますが、分割はより頻繁に評価されます。典型的なデフォルトは200から1000例の範囲です。
オンライン決定木は、小さく静的なデータセットに適していますか?
いいえ。小さく完全に利用可能なデータセットの場合、標準的なバッチ決定木またはランダムフォレストは、はるかに少ない複雑さで、ほぼ常に優れた精度を達成します。オンラインツリーは、ストリーミング、大規模、またはリソース制約のあるレジームに特化して設計されています。
固定データセットでのバッチメソッドとの精度の比較はどうですか?
十分なデータがあれば、Hoeffding Treeはバッチ学習者が生成するツリーと同じものに収束するため、精度は最終的に一致します。ストリームの初期段階では、リーフが多くの例を見ていない前に、精度はこれまでに見た同じデータでトレーニングされたバッチツリーよりも低くなります。
関連する手法
参考文献
Domingos, P., & Hulten, G. (2000). Mining very fast data streams. In Proceedings of the 6th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (pp. 71–80). ACM.
出版物の文献を開くコピーしました。Hulten, G., Spencer, L., & Domingos, P. (2001). Mining time-changing data streams. In Proceedings of the 7th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (pp. 97–106). ACM.
DOI 文献を開くコピーしました。