CluStream（クラストリーム）とは？進化するデータストリームをリアルタイムにクラスタリングするアルゴリズム

CluStreamは、ユーザーが指定したオンラインのクラスタリングクエリに基づいて、進化し続けるデータストリーム（evolving data stream）のクラスタリングを行うアルゴリズムです。最大の特徴は、クラスタリング処理を「オンライン」と「オフライン」の2つのコンポーネントに分割している点にあります。

オンラインとオフラインの2段階構成

オンラインコンポーネントは、「マイクロクラスタ（micro-cluster）」と呼ばれる要約統計量を計算・保存しながら、データストリームを増分的（インクリメンタル）に処理し、マイクロクラスタの維持・更新をリアルタイムに行います。

一方、オフラインコンポーネントは、保存された要約統計情報をもとにマクロクラスタリングを実行し、ユーザーからのさまざまな問い合わせ（クエリ）に回答します。この仕組みにより、高速なストリーム処理と柔軟な分析要求への対応を両立しています。

傾斜時間枠モデルによるスナップショット管理

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

直感的には、「古い出来事よりも最近の出来事の方が多くの情報が必要になる」という考え方に基づいています。保存された情報は、履歴に関連するユーザー固有のクラスタリングクエリの処理に活用されます。

マイクロクラスタ＝クラスタリング特徴量（CF）

CluStreamにおけるマイクロクラスタは「クラスタリング特徴量（clustering feature）」として定義されます。これは、BIRCHというクラスタリング手法で開発されたクラスタリング特徴量の概念を、時間領域まで拡張したものです。

タイムスタンプ T₁, ..., T_n を持つd次元の点集合 X₁, ..., X_n に対するマイクロクラスタは、(CF2^x, CF1^x, CF2^t, CF1^t, n) という (2d + 3) 個のタプルで定義されます。ここで、CF2^x と CF1^x はd次元ベクトル、CF2^t、CF1^t、n はスカラー値です。

• CF2^x：各次元ごとのデータ値の二乗和 ∑X_i² を保持します。
• CF1^x：各次元ごとのデータ値の総和を保持します。統計的な観点では、CF2^x と CF1^x はそれぞれデータの2次および1次のモーメント（積率）を表します。
• CF2^t：タイムスタンプの二乗和を保持します。
• CF1^t：タイムスタンプの総和を保持します。
• n：マイクロクラスタ内のデータ点の数を保持します。

加法性と減算性による効率的な管理

クラスタリング特徴量には加法性と減算性があり、これがデータストリームのクラスタ分析において非常に有用です。例えば、2つのマイクロクラスタは、それぞれのクラスタリング特徴量を単純に加算するだけでマージできます。また、この特性のおかげで、大量のマイクロクラスタを大きなメモリを消費することなく維持することが可能になります。これらのマイクロクラスタのスナップショットは、傾斜時間枠に基づく重要な時点で保存されます。

オンライン処理の2つのフェーズ

オンラインでのマイクロクラスタ処理は、「統計データの収集」と「マイクロクラスタの更新」という2つのフェーズに分けられます。

第1フェーズ：統計データの収集

合計q個のマイクロクラスタ M₁, ..., M_q が維持されます。qは通常、自然なクラスタ数よりも大幅に大きい値であり、利用可能なメモリ量によって決定されます。

第2フェーズ：マイクロクラスタの更新

各新規データ点は、既存のクラスタのいずれかに追加されるか、新しいクラスタとして登録されます。新しいクラスタが必要かどうかを判断するために、各クラスタには最大境界（maximum boundary）が定義されています。新規データ点が既存クラスタの最大境界内に収まる場合はそのクラスタに割り当てられ、境界を超える場合は新規クラスタが作成されます。