STREAMアルゴリズムとは？データストリームk-mediansクラスタリングの仕組みと課題を解説

STREAMアルゴリズムの概要

STREAMは、k-medians問題（k-中央値クラスタリング）のために開発された、シングルパス（1回の走査）による定数倍近似アルゴリズムです。k-medians問題とは、N個のデータポイントをk個のクラスタ（グループ）に分割し、各ポイントとそれが割り当てられたクラスタ中心との間の二乗誤差の合計（SSQ：Sum of Squared Error）を最小化する問題を指します。その狙いは、互いに類似したデータポイントを同じクラスタにまとめ、他のクラスタに属するポイントとは区別することにあります。

ストリームデータモデルにおける制約

ストリームデータモデルでは、データポイントは一度しか参照できず、使用できるメモリ量や処理時間にも厳しい制限があります。このような条件下でも高品質なクラスタリングを実現するため、STREAMアルゴリズムはデータストリームをm個のデータポイントからなるバケット（バッチ）単位で処理します。各バケットはメインメモリに収まるサイズに設計されています。

STREAMの処理の流れ

具体的な処理手順は以下の通りです。

1. バケットごとのクラスタリング： 各バケットb_iについて、STREAMはバケット内のポイントをk個のクラスタに分類します。

2. 情報の要約： バケット内の情報は、k個のクラスタ中心に関するデータのみに要約されます。このとき、各クラスタ中心には、そのクラスタに割り当てられたポイント数が重みとして付与されます。

3. 元データの破棄： バケット内の元のポイントは破棄され、中心情報のみが保持されます。

4. 階層的な再クラスタリング： 十分な数の中心が集まると、重み付きの中心同士をさらにクラスタリングし、新たにO(k)個のクラスタ中心のグループを作成します。この処理を繰り返すことで、どの段階においても保持されるポイント数は最大m個に抑えられます。

計算量と近似精度

このアプローチにより、STREAMはデータストリームのk-medians問題に対して、1回の走査（one-pass）で、時間計算量O(kN)、空間計算量O(N^ε)（ε < 1となる定数）を達成する定数倍近似アルゴリズムとなります。つまり、限られたメモリと時間の中で、理論的に保証された品質のクラスタリングを実現できるのです。

STREAMの課題：時間的変化への非対応

STREAMは一定の空間・時間内で高品質なk-mediansクラスタリングを実現できますが、データの時間的な変化（進化）や時間粒度については考慮していません。そのため、クラスタリング結果が古く陳腐化したデータに支配されてしまう可能性があります。

実際、クラスタの特性は「評価する時点」と「測定対象となる期間」の両方によって変化します。例えば、ユーザーは先週、先月、昨年に現れたクラスタをそれぞれ調べたい場合があり、これらの結果は互いに異なるものになります。したがって、データストリームクラスタリングのアルゴリズムには、ユーザーが指定した任意の期間に対して対話形式でクラスタを計算できる柔軟性も求められます。

CluStream：進化するデータストリームのためのクラスタリング

こうした課題に対応するのがCluStreamです。これは、ユーザーが指定するオンラインのクラスタリングクエリに基づき、進化するデータストリームをクラスタリングするためのアルゴリズムです。CluStreamはクラスタリング処理を「オンライン処理」と「オフライン処理」の2つのコンポーネントに分離しています。

オンラインコンポーネント

オンラインコンポーネントは、マイクロクラスタ（micro-clusters）と呼ばれる手法を用いて、データストリームに関する要約統計量を計算・保存します。また、マイクロクラスタの増分的なオンライン計算と保守（メンテナンス）を行います。

オフラインコンポーネント

オフラインコンポーネントは、マクロクラスタリング（macro-clustering）を実行し、保存された要約統計量をもとにユーザーの様々な質問に答えます。これらの処理は傾斜時間フレームモデル（tilted time frame model）に依存しています。

傾斜時間フレームモデル

履歴データと現在のストリームデータの両方の情報に基づいて進化するデータストリームをクラスタリングするため、CluStreamでは傾斜時間フレームモデル（漸進的な対数モデルなど）が採用されています。このモデルは、新しいさに応じて異なる粒度のレベルで、一連のマイクロクラスタのスナップショットを保存する仕組みです。