Skip to content
検索結果に戻る

オンラインランダムフォレスト

提唱者
Saffari, A. et al.
年
2009
種類
Incremental ensemble (streaming decision trees)
系統
Machine learning

この文章は機械翻訳で、まだ確認されていません。 英語の原文を読む

文字サイズ

何をする手法か?

Online Random Forest (ORF) は、古典的な Random Forest をストリーミング設定に拡張したもので、訓練セット全体を保存または再再生することなく、新しい観測値が到着するたびに各ツリーを段階的に更新します。Adaptive Random Forests (ARF) のようなアルゴリズムは、データ分布が時間とともに変化した場合にアンサンブルが適応するように、ドリフト検出を追加します。

手法の背後にある直感

古典的な Random Forest は、ツリーを成長させるためにすべてのデータセットを事前に必要とします。Online Random Forest は、バッチブートストラップサンプリングをポアソン重み付きオンラインバギングトリックに置き換えます。各着信観測値はすべてのツリーに渡され、ツリーはポアソンカウントを引くことによって、その例をいくつの新しい訓練ポイントとして扱うかを決定します。ツリーはオンライン分割基準(例:Hoeffdingバウンド)を使用して段階的に成長し、ドリフト検出モジュールがコンセプトドリフトを監視し、古いツリーを新しいツリーに置き換えます。結果として、分散削減のために複数の多様なツリーを組み合わせながら、ストリームから継続的に学習するフォレストが得られます。

歴史学

オンラインバギングは、ブートストラップ集約のポアソン重み付き近似として Oza & Russell (2001) によって形式化されました。Saffari et al. (2009) は、オンラインバギングとランダム特徴量選択およびHoeffdingベースの分割基準をコンピュータビジョンのストリームに組み合わせたOn-line Random Forestsを導入しました。Gomes et al. (2017) は、ADWINによるツリーごとのドリフト検出を追加したAdaptive Random Forests (ARF) を導入し、ベンチマークデータストリーム分類タスクで最先端の精度を実証しました。ARFは、MOA (Massive Online Analysis) フレームワークの標準的なベースラインとなりました。

使うべき場面

データが継続的に、またはメモリに保持できない大きなバッチで到着する場合、コンセプトドリフトが起こりうる場合(例:金融ストリーム、センサーネットワーク、ユーザー行動ログ)、または完全なデータセットが利用可能になる前に低遅延予測が必要な場合に、Online Random Forest を使用します。ラベル付きデータが時間とともに少しずつ入ってくるアプリケーションにも自然に適合します。完全なデータセットがメモリに快適に収まり、再トレーニングが手頃な場合は、それを使用しないでください。その場合、オフラインでトレーニングされた標準的な Random Forest の方が通常、より正確で検証が簡単です。また、安定した再現可能な特徴量の重要度ランキングが必要な場合にも避けてください。オンラインフォレストは、バッチの対応物よりも安定性の低い重要度推定値を生成します。

限界と注意点

  • 少ないデータで早期に行われた分割決定は最適でなく、修正が困難な場合があります。
  • 特徴量の重要度推定値は、バッチ Random Forest よりも安定性が低いです。
  • ハイパーパラメータチューニング(ツリー数、ドリフト検出しきい値)は、ストリーミングコンテキストではより複雑です。
  • 評価には、標準的なクロスバリデーションとは異なる、専用のストリームベースのプロトコル(prequential/test-then-train)が必要です。

出典に示された条件は、独立した科学的レビューや分析エンジンによる検証の代わりにはなりません。

強み

  • ストリーム長に依存しない、ツリーあたりの一定メモリでストリーミングデータから学習します。
  • ADWINのようなドリフト検出メカニズムと組み合わせると、コンセプトドリフトに適応します。
  • オンライン設定でも、アンサンブル集約の分散削減の利点を継承します。
  • ストリームの最初の数個の観測値から使用可能な予測を提供し、時間とともに改善します。
  • 完全な履歴データセットを保存または再再生する必要がありません。

応用

  • ネットワークまたはトランザクションストリームでのリアルタイム不正および侵入検出。
  • 機器の経年劣化とともに分布がシフトするセンサー ストリームからの予知保全。
  • ユーザー行動が日々進化する広告でのクリック率予測。
  • 患者の状態が時間とともに連続的に変化する医療モニタリング。
  • 非定常な季節パターンを持つ環境および気候センシング。

使い方

使い方

1

T個のツリー(またはHoeffdingツリー)のセットが初期化されます。各ツリーは、生の観測値を保存するのではなく、各リーフごとに十分統計量(クラスカウントまたは回帰のための二乗和)を維持するため、ツリーあたりのモデルメモリは一定になります。

2

到着する各観測値に対して、各ツリーは独立に Poisson(1) 分布から k を引き、その観測値を k 個の仮想レプリケーションとして扱います。k = 0 の場合、ツリーはそのポイントをスキップします(アウトオブバッグサンプルとして機能します)。これは、完全なデータセットを必要とせずにブートストラップサンプリングを近似します。

数式
k \sim \text{Poisson}(\lambda),\; \lambda=1
3

各ツリーは、アクティブなリーフで十分統計量を更新します。統計的に健全な基準(Hoeffdingバウンドなど)が、より多くのデータで最適な分割が変わる可能性が低いことを示した場合、分割がトリガーされ、そのリーフは内部ノードに展開され、新しいリーフが初期化されます。

4

オプションのドリフト検出モジュール(例:ADWIN)は、アウトオブバッグストリームでの各ツリーの予測誤差を監視します。統計的に有意な劣化が検出されると、影響を受けたツリーはリセットされるか、新しくシードされたツリーに置き換えられ、アンサンブルは進化する分布に追従します。

5

任意の時点で、すべてのアクティブなツリーが投票します。分類の場合は多数決、回帰の場合は平均予測です。非常に少ない例を処理したツリーは、信頼できる投票を行うのに十分なデータを蓄積するまで、重み付けを減らしたり除外したりする場合があります。

数式
\hat{y} = \text{mode/mean of active trees}

よくある落とし穴

  • i.i.d.データを仮定し、時間的順序を無視する標準的な k-fold クロスバリデーションを使用した評価。
  • コンセプトドリフトの無視:データ分布が時間とともに変化する場合にドリフト検出コンポーネントを含めないこと。
  • オンラインフォレストの精度を、完全な履歴データセットでトレーニングされたバッチ Random Forest と直接比較すること。後者は本質的に情報優位性を持っています。
  • 各ツリーが信頼できる分割を行うのに十分なデータを見る前に、ストリームの早い段階でツリーが少なすぎること。
  • ポアソン重み付きバギングがブートストラップを近似すること、正確にはバッチブートストラップの統計的特性を再現しないことを忘れている。

よくある質問

Online Random Forest は標準的な Random Forest とどのように異なりますか?

標準的な Random Forest は、ブートストラップサンプリングを使用して、完全なデータセット上で一度にすべてのツリーをトレーニングします。Online Random Forest は、バッチブートストラップをポアソン重み付きオンラインバギングに置き換え、各観測値が到着するたびにツリー分割を段階的に更新し、オプションでコンセプトドリフトを検出して適応します。これらすべてを、過去のデータを保存することなく行います。

ポアソン重み付けトリックとは何ですか?

各着信例は、k が Poisson(1) から引かれる回数だけ、各ツリーに表示されます。k の期待値は 1 であり、k = 0 となる確率は約 37% であるため、これは完全なデータセットをメモリに保持することなく、統計的にブートストラッププロセス(置換ありサンプリング)を近似します。

オンラインランダムフォレストはどのように評価すべきですか?

prequential (test-then-train) プロトコルを使用します。各着信観測値について、まず現在のモデルで予測し、誤差を記録してから、モデルを更新します。これにより、データリークなしで、時間的に順序付けられた予測パフォーマンスのバイアスのない推定値が得られます。

ドリフト検出はいつ追加すべきですか?

データ生成プロセスが時間とともに変化する可能性が高い場合、例えばユーザーの好み、金融市場、または摩耗する機械システムなどです。ドリフト検出がないと、古いツリーが蓄積し、アンサンブルの精度が低下します。ADWINは、一般的で十分にテストされた選択肢です。

Adaptive Random Forest は同じものですか?

ARF は、Online Random Forest の最も広く採用されているバリアントです。オンラインバギング、ランダム特徴量選択、およびツリーごとの ADWIN ドリフト検出を組み合わせ、MOA および scikit-multiflow/River ライブラリで利用可能です。「Online Random Forest」という用語は、多くの場合、ファミリーを一般的に指しますが、ARF は特定の、強く推奨される実装です。

関連する手法

参考文献

  1. Saffari, A., Leistner, C., Santner, J., Godec, M., & Bischof, H. (2009). On-line random forests. In Proceedings of the 3rd IEEE International Workshop on On-Line Learning for Computer Vision (OLCV 2009), pp. 1–8. IEEE.

    出版物の文献を開く
    コピーしました。
  2. Gomes, H. M., Bifet, A., Read, J., Barddal, J. P., Enembreck, F., Pfharinger, B., Holmes, G., & Abdessalem, T. (2017). Adaptive random forests for evolving data stream classification. Machine Learning, 106(9), 1469–1495.

    DOI 文献を開く
    コピーしました。