凝集型クラスタリングアルゴリズムとは？仕組みと手順をわかりやすく解説

凝集型クラスタリングの基本概念

凝集型クラスタリング（Agglomerative Clustering）は、ボトムアップ方式のクラスタリング手法の一つです。この手法では、クラスタの中にサブクラスタが含まれ、さらにそのサブクラスタの中にもサブクラスタが存在するといった、階層的な構造が特徴となります。

処理はまず、各データオブジェクトをそれぞれ独立したクラスタとして配置することから始まります。その後、これらの最小単位のクラスタを段階的に統合しながら、より大きなクラスタへと組み上げていきます。すべてのオブジェクトが一つのクラスタにまとまるか、あらかじめ定めた終了条件を満たすまで、この統合プロセスを繰り返します。階層的クラスタリング手法の多くはこのタイプに属しており、手法ごとの違いは主に「クラスタ間の類似度をどう定義するか」の点にあります。

AGNES（Agglomerative Nesting）の例

代表的な手法の一つに、単連結法（single-linkage）を採用したAGNES（Agglomerative Nesting）があります。例えば、長方形の領域内に複数のオブジェクトが配置されている状況を想定してみましょう。初期状態では、各オブジェクトはそれぞれ独自のクラスタに属しています。その後、「クラスタ内の最も近いオブジェクト同士のユークリッド距離が最小となるクラスタ同士を結合する」といった原則に基づいて、クラスタを段階的にマージしていきます。

K-means法との違い

K-means法によるクラスタリングは、最初にクラスタ数を固定値として決定し、すべてのデータをちょうどその数のクラスタに振り分ける方式です。一方、凝集型のアプローチでは、各データポイントが最初は個別のクラスタを形成し、それらを徐々に統合していくことで、最終的にすべてのポイントが一つの大きなクラスタに収束します。つまり、クラスタ数を事前に決める必要がない点が大きな特徴です。

類似度行列の作成

処理の第一ステップは、類似度行列（similarity matrix）の作成です。類似度行列とは、クラスタ間のペアごとの距離や類似度を一覧表にしたものです。初期段階では、個々のレコード（データポイント）同士のペア間の距離が格納されます。

レコード間の類似度を測る尺度には、さまざまな種類があります。代表的なものとしては、ユークリッド距離、ベクトル間の角度（コサイン類似度）、カテゴリカル項目における一致・不一致の比率などが挙げられます。データの性質に応じて適切な尺度を選択することが重要です。

計算量と行列の特性

N個のデータポイントに対してN個の初期クラスタが存在する場合、距離テーブルを作成するには約N²回の計算が必要になります。ただし、類似度の尺度が真の距離計量である場合は、Distance(X, Y) = Distance(Y, X) という対称性が成り立つため、必要な計算量は半分で済みます。

数学的には、このような対称な行列は下三角行列（lower triangular matrix）として表現でき、メモリの節約にもつながります。

クラスタの統合プロセス

次のステップは、行列の中から最小値を探索することです。これにより、互いに最も類似している2つのクラスタが特定されます。その2つのクラスタを新しい1つのクラスタに統合し、元の親クラスタを表していた2つの行を削除して、統合後のクラスタと残りのクラスタとの距離を示す新しい行で置き換えることで、類似度行列を更新します。

この時点で、クラスタの数はN－1個となり、行列の行数もN－1行になります。この統合ステップをN－1回繰り返すことで、すべてのデータが最終的に一つの大きなクラスタに属することになります。各反復処理では、「どのクラスタ同士が統合されたのか」「その際のクラスタ間の距離はどれほどだったのか」が記録されていきます。この履歴情報をもとに、目的に応じて最適なクラスタ数や分割位置を判断することができるのです。