スパース化（Sparsification）とは？クラスタリングにおける近接行列のスパース化の基本とメリット

クラスタリングにおいて、m個のデータポイントに対する m×m の近接行列は、密なグラフとして捉えることができます。このグラフでは各ノードが他のノードとリンクで結ばれており、ノード間のエッジの重みはペアごとの近接性（類似度・非類似度）に対応します。

すべてのオブジェクトが強く似ているわけではない

理論上、あるオブジェクトは他のすべてのオブジェクトと何らかの類似性を持っています。しかし実際のほとんどのデータセットでは、オブジェクトはごく少数のオブジェクトとだけ高い類似性を示し、その他の大多数のオブジェクトとは弱い類似性しか持たないという特徴があります。

スパース化の仕組み

この特性を利用すると、実際のクラスタリング処理を開始する前に、類似度の低い（＝非類似度の高い）値を0に設定することで、近接グラフ（近接行列）をスパース化できます。代表的な実装方法は次の2つです。

• しきい値による方法：あらかじめ定めたしきい値を基準に、一定以下の類似度（または一定以上の非類似度）を持つリンクをすべて削除します。
• k最近傍による方法：各ポイントのk個の最近傍へのリンクのみを保持します。この方法で構築されるのが「k最近傍グラフ」です。

スパース化のメリット

1. データサイズの削減

クラスタリングのために処理すべきデータ量が大幅に減少します。スパース化によって近接行列内のエントリの99%以上を削除できることもあり、その結果、扱える問題の規模が大きく拡張されます。

2. クラスタリング精度の向上

スパース化では、オブジェクトの最も近い隣接点へのリンクは保持し、類似性の低い遠いオブジェクトへの接続は切断します。これは「最も近い隣接点はオブジェクト自身と同じクラス（クラスタ）に属する傾向がある」という最近傍の原理と一致しています。そのため、ノイズや外れ値の影響が軽減され、クラスタ間の違いがより明確になります。

3. グラフ分割アルゴリズムの活用

スパースグラフの最小カット分割を見つけるためのヒューリスティックアルゴリズムについては、並列計算や集積回路設計の分野を中心に多くの研究が蓄積されています。近接グラフをスパース化することで、OpossumやChameleonのようにグラフ分割を必要とするクラスタリング手法において、既存のグラフ分割アルゴリズムをクラスタリング段階で活用できるようになります。

スパース化の限界と実務上の注意点

近接グラフのスパース化は、本格的なクラスタリングアルゴリズムを適用する前の前処理ステップと考えるべきです。理想的なスパース化が行えれば、近接行列は目的のクラスタに対応する連結成分へ自然に分割されるはずですが、現実にはそう単純にはいきません。

実際には、単一のエッジが2つのクラスタをまたいで接続してしまったり、逆に単一のクラスタが複数の非連結なサブクラスタに分断されてしまうケースが起こりえます。実際、Jarvis-Patrick法やSNNのような密度ベースのクラスタリングでは、スパース化された近接グラフをさらに変換して新しい近接グラフを生成し、それを再びスパース化するといった処理が行われます。最終的にクラスタリングアルゴリズムは、こうした一連の前処理を経て得られた近接グラフに対して動作するのです。