COBWEBアルゴリズムの仕組みとは？動作原理と限界を解説

COBWEBの基本的な仕組み

COBWEBは、オブジェクトを分類木（classification tree）へ段階的に追加していく増分クラスタリング手法です。COBWEBは木を適切な経路に沿って下降しながら、途中でカウント値を更新し、オブジェクトを分類するのに最も適したノード、すなわち「最良ホスト（best host）」を探索します。

この判断は、オブジェクトを一時的に各ノードに配置し、その結果得られる分割の「カテゴリユーティリティ（category utility）」を計算することによって行われます。最も高いカテゴリユーティリティをもたらす配置こそが、そのオブジェクトにとっての最良ホストとなります。

さらにCOBWEBは、オブジェクト用の新しいノードを作成した場合に得られる分割についてもカテゴリユーティリティを計算します。そして、最も高いカテゴリユーティリティ値を持つ分割に基づいて、オブジェクトを既存のクラスに配置するか、新しいクラスを生成するかを決定します。

このようにCOBWEBは、分割内のクラス数を自動的に調整する能力を備えています。つまり、クラス数などのパラメータをユーザーが事前に指定する必要はありません。

マージとスプリットという2つの操作

COBWEBには、入力データの順序による影響を受けにくくするための2つの操作があります。それが「マージ（統合）」と「スプリット（分割）」です。

オブジェクトが処理される際、2つの最良ホスト候補は単一のクラスへの統合対象として評価されます。同時にCOBWEBは、最良ホストの子ノードを現在のカテゴリ間で分割することも検討します。これらの判断はすべてカテゴリユーティリティに基づいて行われます。

マージ操作とスプリット操作により、COBWEBは双方向の探索を実現できます。例えば、マージによって以前のスプリットを取り消すことも可能です。

COBWEBの限界

COBWEBには以下のような限界があります。

属性間の独立性の仮定

COBWEBは、各属性の確率分布が互いに統計的に独立であるという前提に依存しています。しかし実際には属性間に相関関係が存在することが多く、この仮定は必ずしも正しいとは言えません。

更新・保存のコスト

クラスタを確率分布で記述する方式は、クラスタの更新や保存にかかるコストが非常に高くなります。これは属性が取りうる値の種類が多い場合に特に顕著です。時間計算量および空間計算量は、属性の数だけでなく、各属性の値の数にも依存するためです。

木のバランスの偏り

入力レコードに偏りがある場合、分類木は高さ方向にバランスが取れなくなります。その結果、時間・空間計算量が大幅に悪化する恐れがあります。

連続値データへの拡張：CLASSIT

CLASSITは、連続値（実数値）データの増分クラスタリングのためにCOBWEBを拡張した手法です。CLASSITは各ノードの各属性について連続的な正規分布（平均と標準偏差）を保持します。また、COBWEBのように離散属性に対して総和を取るのではなく、連続属性に対して積分を行う修正版のカテゴリユーティリティ尺度を使用します。