データストリームのクラスタリング

コンピュータサイエンスでは、データ ストリーム クラスタリングは、電話記録、マルチメディア データ、金融取引などの継続的に到着するデータのクラスタリングとして定義されます。データ ストリーム クラスタリングは通常、ストリーミング アルゴリズムとして研究され、その目的は、一連のポイントが与えられた場合に、少量のメモリと時間を使用して、ストリームの適切なクラスタリングを構築することです。

データストリームクラスタリングは、大量のストリーミングデータを扱う新しいアプリケーションとして最近注目を集めています。クラスタリングでは、 k-means が広く使用されているヒューリスティックですが、k-medoids、CURE、人気の^[要出典] BIRCHなどの代替アルゴリズムも開発されています。データストリームの場合、最初の結果の 1 つは 1980 年に登場しましたが^[1] 、モデルが正式に定義されたのは 1998 年です。^[2]

データ ストリーム クラスタリングの問題は次のように定義されます。

入力:メトリック空間内のn個のポイントのシーケンスと整数k。
出力: データ ポイントから最も近いクラスター センターまでの距離の合計を最小化する、 n個のポイントのセット内のk 個の中心。

これは k-median 問題のストリーミング バージョンです。

STREAMは、Guha、Mishra、Motwani、O'Callaghan ^{[3]によって説明されたデータストリームをクラスタリングするためのアルゴリズムであり、k-Median問題の}定数係数近似を1回のパスで小さなスペースを使用して実現します。

STREAM を理解するための最初のステップは、クラスタリングが小さなスペースで実行できることを示すことです (パスの数は考慮しません)。Small-Space は、データSをいくつかの部分に分割し、それぞれをクラスタリングし ( k平均法を使用)、得られた中心をクラスタリングする 分割統治アルゴリズムです。${\displaystyle \ell}$

アルゴリズム Small-Space(S)

ここで、ステップ 2 で、コストが最大で最適な k-Median ソリューションのb倍である最大でak 個のメディアンを出力する2基準⁠ ⁠${\displaystyle (a,b)}$近似アルゴリズムを実行し、ステップ 4 でc近似アルゴリズムを実行する場合、Small-Space() アルゴリズムの近似係数は⁠ ⁠です。また、Small-Space を一般化して、重み付けされた中心の連続的に小さいセットに対してi回再帰的に呼び出し、 k -Median 問題に対する定数係数近似を達成することもできます。 ${\displaystyle 2c(1+2b)+2b}$

Small-Space の問題は、 Xの中間中央値をメモリに格納する必要があるため、 S を分割するサブセットの数が限られていることです。したがって、メモリのサイズが M の場合、各サブセットがメモリに収まるように、 ( )、重み付けされた中心もメモリに収まるように、 S をサブセットに分割する必要があります。ただし、このような が常に存在するとは限りません。 ${\displaystyle \ell}$${\displaystyle \ell}$${\displaystyle n/\ell}$${\displaystyle \ell k}$${\displaystyle \ell k<M}$${\displaystyle \ell}$

STREAMアルゴリズムは中間中央値を保存する問題を解決し、実行時間とスペース要件を改善します。アルゴリズムは次のように機能します。^[3]

データ ストリーム クラスタリングに使用されるその他のよく知られたアルゴリズムは次のとおりです。

• BIRCH : ^[5]は 、利用可能なメモリを使用して、必要なI/Oの量​​を最小限に抑えながら、入力ポイントを段階的にクラスタリングするための階層型データ構造を構築します。1回のパスで十分なクラスタリングが得られるため、アルゴリズムの複雑さは⁠ ⁠${\displaystyle O(N)}$です（ただし、複数のパスを許可することで結果を改善できます）。
• COBWEB : ^{[6] [7]は、}階層型クラスタリングモデルを分類ツリーの形で保持する増分クラスタリング手法です。新しいポイントごとに、COBWEBはツリーを下り、途中でノードを更新し、ポイントを配置するのに最適なノードを探します（カテゴリユーティリティ関数を使用）。
• C2ICM: ^[8] は、いくつかのオブジェクトをクラスターシード/イニシエーターとして選択することでフラットパーティショニングクラスタリング構造を構築し、最高のカバレッジを提供するシードに非シードが割り当てられ、新しいオブジェクトが追加されると新しいシードが導入され、既存の古いシードの一部が偽造される可能性があります。増分クラスタリング中に、新しいオブジェクトと偽造されたクラスターのメンバーが既存の新しい/古いシードの1つに割り当てられます。
• CluStream: ^[9]は、 BIRCH ^[5]のクラスター特徴ベクトルの時間的拡張であるマイクロクラスターを使用して、現在のマイクロクラスターのデータポイントとタイムスタンプの二乗和と線形和の分析に基づいて、マイクロクラスターを新しく作成するか、マージするか、忘れるかを決定し、その後、任意の時点で、K-Meansなどのオフラインクラスタリングアルゴリズムを使用してこれらのマイクロクラスタリングをクラスタリングすることにより、マクロクラスターを生成し、最終的なクラスタリング結果を生成できます。