ROCKとは？リンクを活用した頑健なクラスタリングアルゴリズムを徹底解説

ROCKとは

ROCK（RObust Clustering using linKs）は、カテゴリ属性を持つデータを対象とした階層型クラスタリングアルゴリズムです。「リンク」と呼ばれる概念、すなわち2つのオブジェクトが共有する共通近傍の数を分析することで、高品質なクラスタを実現します。単純な距離尺度では、カテゴリ情報のクラスタリングにおいて高品質な結果が得られないことが示されています。

従来手法の課題：「局所的」アプローチの限界

多くのクラスタリングアルゴリズムは、クラスタリングの各ステップで類似した点同士を統合していく、いわば「局所的」な手法を採用しています。しかしこの方法には誤りが生じやすいという弱点があります。例えば、本来は別々のクラスタに属する点や外れ値（アウトライヤ）が互いに近い位置に存在する場合、点間の類似性のみに頼ってクラスタリングの判断を行うと、異なる2つのクラスタが誤って統合されてしまう可能性があります。

ROCKのグローバルなアプローチ

ROCKは、個々の点ペアの近傍関係を考慮する、よりグローバルな視点でクラスタリングを行います。2つの類似した点が同じような近傍を持っている場合、その2点は同じクラスタに属している可能性が高いと判断され、統合されるのです。

近傍とリンクの定義

2つの点 p_i と p_j は、sim(p_i, p_j) ≥ θ を満たすとき「近傍」であると定義されます。ここで sim は類似度関数、θ はユーザーが指定する閾値です。sim には距離指標を選ぶこともできますし、0から1の範囲に正規化された非メトリック（値が大きいほど点同士が類似していることを表す）を採用することも可能です。

p_i と p_j 間の「リンク数」は、両者の間の共通近傍の数として表されます。2つの点の間のリンク数が多いほど、それらが同じクラスタに属する可能性が高いといえます。点群全体の関係性の中で近傍データ点を考慮するROCKは、点の類似性のみに着目する標準的なクラスタリング手法よりも優れた性能を発揮します。

マーケットバスケットデータへの適用

カテゴリ属性を含むデータの代表的な例として、マーケットバスケットデータが挙げられます。このデータはトランザクション（取引記録）のデータベースで構成され、各トランザクションはアイテムの集合です。トランザクションはブール（真偽）属性を持つデータとして扱われ、各属性はパンやチーズといった単一のアイテムに対応します。

あるトランザクションのデータにおいて、対応するアイテムが含まれていればその属性は真（true）、含まれていなければ偽（false）となります。同様の方法で扱えるカテゴリ属性を持つデータセットは数多く存在します。2つの「点」すなわちトランザクション T_i と T_j の間の近傍・リンクの概念は、次のジャッカード係数によって表されます。

$$\mathrm{sim(T_{i},T_{j})=\frac{|T_{i} \cap T_{j}|}{|T_{i} \cup T_{j}|}}$$

アルゴリズムの処理の流れ

ROCKはまず、与えられたデータ類似度行列から、類似度閾値と共有近傍の考え方を利用してスパースグラフを生成します。続いて、そのスパースグラフ上で凝集型階層的クラスタリングを実行します。クラスタリングの質は goodness measure（良さの尺度）を用いて評価され、大規模データセットへスケールアップする際にはランダムサンプリングが活用されます。

計算量

ROCKの最悪ケースにおける時間計算量は O(n² + nm_mm_a + n²log n) です。ここで m_m と m_a はそれぞれ近傍数の最大値と平均値、n はオブジェクトの総数を表します。