K-MeansとDBSCANの違いとは？2大クラスタリング手法を徹底比較

K-Means（K平均法）とは

K-Meansクラスタリングは、代表的な分割最適化型アルゴリズムの一つです。データセット内の各データを、新たに形成された複数のクラスタのうち必ず1つに割り当てます。データポイントは、距離や類似度の尺度を用いて、最も近いクラスタに振り分けられます。

K-Meansでは、各オブジェクトは最も近い中心（セントロイド）に割り当てられるのが基本です。また、cannot-link制約（特定のデータ同士を同じクラスタに含めない制約）を定義することも可能です。この場合、通常の「最近傍の中心への割り当て」プロセスを修正し、制約を満たす適用可能な中心へ割り当てるように変更します。

オブジェクトを順番に中心へ割り当てていく際、各ステップでそれまでの割り当て結果がcannot-link制約に違反しないよう調整を行います。こうすることで、オブジェクトは最も近い中心に割り当てられながらも、cannot-link制約が確実に尊重されることになります。

DBSCANとは

DBSCANは「Density-Based Spatial Clustering of Applications with Noise（ノイズを含むアプリケーションのための密度ベース空間クラスタリング）」の略称で、密度ベースのクラスタリングアルゴリズムです。十分に高い密度を持つ領域をクラスタとして成長させ、ノイズを含む空間データベースから任意の形状のクラスタを発見できます。クラスタを「密度連結な点の最大集合」として定義するのが大きな特徴です。

密度ベースのクラスタとは、「密度到達可能性に関して極大となる、密度連結なオブジェクトの集合」を指します。そして、いずれのクラスタにも属さないオブジェクトはすべてノイズとみなされます。

DBSCANは、データベース内のすべての点についてε近傍（イプシロン近傍）を調べることでクラスタを検出します。ある点pのε近傍にMinPts以上の点が含まれる場合、pをコア要素とする新しいクラスタが生成されます。続いて、これらのコア要素から密度到達可能なオブジェクトを反復的に集めていき、この過程で複数の密度到達可能なクラスタが統合されることもあります。新しい点をどのクラスタにも追加できなくなった時点で、アルゴリズムは終了します。

K-MeansとDBSCANの比較表

まとめ

K-Meansはシンプルで高速な反面、クラスタ形状が球状であることや事前にクラスタ数を指定する必要があるといった制約があります。一方、DBSCANはクラスタ数を事前に指定する必要がなく、任意の形状のクラスタやノイズを含むデータに強いという利点があります。データの性質や目的に応じて、両者を使い分けることが重要です。