オンラインクラスタリング - Shinichi0713/AlgorithmChallenges GitHub Wiki

オンラインクラスタリングとは、「データが逐次的（リアルタイム、ストリーム的）に与えられる状況で、その都度クラスタリング（データの自動的なグループ分け）を行う手法」のことです。

オフラインクラスタリングとの違い

  • オフラインクラスタリング
    すべてのデータが最初から手元にある場合、一括してクラスタリング（例：通常のk-meansや階層的クラスタリングなど）を行う方法です。

  • オンラインクラスタリング
    データが次々に到着する状況（例：センサーデータ、Webアクセスログ、リアルタイム動画解析など）で、新しいデータが来るたびにクラスタの割り当てやクラスタ中心の更新などを行います。

主な特徴

  • 逐次処理：データが1つずつ、または小さなバッチで到着するたびにクラスタリングを更新
  • メモリ効率が良い：すべての過去データを保存しておく必要がない
  • リアルタイム性：即時にクラスタリングの結果を得られる
  • 動的対応：クラスタ構造の変化（新しいクラスタの出現、既存クラスタの消滅など）にも対応可能

代表的な手法

  • オンラインk-means
    新しいデータ点が来るたびに、最も近いクラスタ中心を少しだけ新しいデータに寄せて更新する手法です。
    例：
    $$ \mu_{new} = \mu_{old} + \eta (x_{new} - \mu_{old}) $$ ここで $\eta$ は学習率（更新の大きさ）です。

  • Mini-batch k-means
    データを小さなバッチで受け取り、クラスタ中心をバッチごとに更新します。

  • ストリームクラスタリング手法
    例：CluStream, DenStream, DBSTREAM など、データストリームに特化したアルゴリズム。

まとめ

  • オンラインクラスタリング＝データが逐次到着する状況で、その都度グループ分けを更新する手法
  • リアルタイム性やメモリ効率が求められる場面で有効
  • 代表例：オンラインk-means、Mini-batch k-means、ストリームクラスタリング手法など

ご参考になれば幸いです。以上です。