グラフベースクラスタリングのアプローチとは？主要な手法と特徴を徹底解説

物理的または抽象的なオブジェクトの集合を、互いに似た性質を持つクラスへと分けていく処理をクラスタリングと呼びます。クラスタとは、同一クラスタ内では互いに類似しており、他のクラスタのオブジェクトとは性質が異なるデータオブジェクトの集まりです。多くの応用分野において、クラスタ全体をひとつのグループとして扱うことができます。クラスタ分析は人間にとって本質的な活動であり、データマイニングの中核技術の一つでもあります。

クラスタリングと外れ値検出の関係

クラスタリングは外れ値（アウトライア）の特定にも役立ちます。類似した値どうしがクラスタとして整理され、そのクラスタから大きく外れた値が外れ値とみなされます。クラスタリング手法では、データタプルをオブジェクトとして扱い、それらを複数のグループ（クラスタ）へ分割します。この際、同一クラスタ内のオブジェクトは互いに「類似」し、他のクラスタのオブジェクトとは「非類似」になるように配置します。この類似性は一般に、距離関数に基づく空間上の「近さ」として定義されるのが一般的です。

グラフベースクラスタリングの代表的なアプローチ

グラフベースのクラスタリングには、以下のような主要なアプローチが存在します。

1. 近傍グラフのスパース化（疎化）

近傍グラフを疎化し、各オブジェクトが最も近い近傍とのリンクのみを保持する方法です。このスパース化は、ノイズや外れ値への対処に有効であるだけでなく、スパースグラフ向けに開発された高性能なグラフ分割アルゴリズムの活用を可能にする点でも大きなメリットがあります。

2. 共有最近傍に基づく類似度の利用

2つのオブジェクト間の類似度を、両者が共有する最近傍の数に基づいて定義する方法です。「あるオブジェクトとその最近傍は、通常同じクラスに属する」という観察に基づいており、高次元データや密度が異なるクラスタが混在するデータへの対応に特に有効とされています。

3. コアオブジェクトを中心としたクラスタ形成

コアオブジェクトを識別し、その周囲にクラスタを構築する方法です。グラフベースクラスタリングでは、近傍グラフまたは疎化した近傍グラフに基づく「密度」の概念を導入することが重要になります。DBSCANと同様に、コアオブジェクトを中心にクラスタを成長させることで、さまざまな形状やサイズのクラスタを発見できる柔軟な手法を実現できます。

4. クラスタ統合判断の高度化

近傍グラフ内のデータを活用し、「2つのクラスタを統合すべきかどうか」をより洗練された計算で判定する方法です。たとえば、統合後のクラスタが元の2つのクラスタと同等の特性を持つ場合にのみ統合を実行する、といった基準を用います。

5. スパース化に基づく具体的手法：MSTとOPOSSUM

近傍グラフのスパース化を出発点とする手法としては、単連結型クラスタリングアルゴリズムに相当するMST（最小全域木）や、OPOSSUMなどが挙げられます。

6. SNN類似度とJarvis-Patrick法

階層型クラスタリングアルゴリズムの中には、クラスタを統合すべきかを判断するために自己類似性（self-similarity）の概念を必要とするものがあります。ここでは、新しい類似度である共有最近傍（SNN：Shared Nearest Neighbor）類似度を定義し、この類似度を用いるJarvis-Patrickクラスタリングアルゴリズムについて紹介します。