ホフディングツリーアルゴリズムとは？ストリームデータ分類の仕組みを解説

ホフディングツリー（Hoeffding Tree）アルゴリズムは、ストリーミングデータの分類に特化した決定木学習手法です。当初はWebクリックストリームの追跡に活用され、ユーザーがどのWebホストやサイトへアクセスする可能性が高いかを予測するモデルの構築に用いられていました。従来のバッチ学習とほぼ同等の決定木を生成しながら、準線形時間（サブリニア時間）で動作できる点が最大の特徴です。

ホフディング境界による分割属性の選択

このアルゴリズムの中核にあるのは、「少量のサンプルでも最適な分割属性を選択できることが多い」というアイデアです。この考え方は、ホフディング境界（Hoeffding bound、加法的チェルノフ境界とも呼ばれます）によって数学的に裏付けられています。

範囲Rを持つ確率変数rについてN回の独立な観測を行うことを考えます。ここでrは属性選択尺度です（確率であればR=1、情報利得であればlog c、cはクラス数）。ホフディングツリーでは、rとして情報利得が採用されます。この標本平均をr′とすると、ホフディング境界は、真の平均が少なくとも r′ − ε 以上になる確率が 1 − δ であることを示します。ここでδはユーザーが指定するパラメータであり、εは次式で計算されます。

$$\varepsilon=\sqrt{\frac{R^{2}ln\frac{1}{\delta}}{2N}} $$

アルゴリズムの入力と処理の流れ

ホフディングツリーアルゴリズムは、ホフディング境界を利用することで、ノードにおける分割属性の選択に必要な最小限の事例数Nを高い確率で特定します。多くの他の境界式と異なり、ホフディング境界は確率分布に依存しない点が重要です。使用する属性選択尺度（例えば情報利得）の確率分布を事前に知ることが困難な場合が多いため、この性質は非常に有用です。

アルゴリズムへの入力は、属性Aで記述された訓練事例のシーケンスSと、精度パラメータδです。また、評価関数G(A_i)が与えられ、情報利得、利得比、ジニ指数など、任意の属性選択尺度を使用できます。決定木の各ノードでは、残りの属性A_iの中からG(A_i)を最大化するものを選択する必要があります。目標は、ホフディング境界が満たされる最小のタプル数Nを見つけることです。

あるノードにおいて、Gが最も大きい属性をA_a、2番目に大きい属性をA_bとします。G(A_a) − G(A_b) > ε が成り立てば、A_aが真に最良の分割属性であることが高い確率で保証されるため、追加データを待つことなく、その時点でノードを分割できます。

維持すべき統計量とメモリ要件

ホフディングツリーアルゴリズムで保持が必要な統計量は、クラスラベルy_kを持つ属性A_iの値v_jの出現回数n_ijkのみです。したがって、属性数をd、任意の属性が取りうる値の最大数をv、クラス数をc、木の最大深さ（レベル数）をlとすると、必要な総メモリ量はO(ldvc)で表されます。