非階層的クラスタリングの完全ガイド：手法の特徴・計算量・前処理・適用事例と実務的な選び方
エバープレイ編集部非階層的クラスタリングとは — 概要と位置づけ
非階層的クラスタリング（non-hierarchical clustering）は、与えられたデータ集合を階層構造に基づいて分割するのではなく、あらかじめ定めた基準やアルゴリズムに応じてデータを直接いくつかのグループ（クラスタ）に分ける手法群を指します。代表的な階層的手法である凝集型（agglomerative）や分割型（divisive）のようにツリー（デンドログラム）を作成するのではなく、パーティショニング（partitioning）や密度ベース、モデルベース、グラフ／分解に基づく方法などが含まれます。
非階層的クラスタリングの主な種類と特徴
パーティショニング法（例：k-means）
k-means は最も広く使われる代表的な手法です。クラスタ数 k を事前に指定し、各クラスタの中心（重心）を反復更新してデータ点を割り当てます。計算は比較的高速で大規模データにも適用しやすい一方、球状（凸）クラスタを仮定し、初期化や k の選び方、外れ値に敏感という欠点があります。
k-medoids（例：PAM、CLARA）
k-medoids は各クラスタの代表点として実際の観測値（メドイド）を用いる手法で、k-means より外れ値に堅牢です。計算コストが高くなるため、CLARA のようなサンプリングを用いたスケーリング手法が実用上使われます。
密度ベース（例：DBSCAN、OPTICS）
DBSCAN は密度に基づいてクラスタを形成し、任意形状のクラスタ検出やノイズ（アウトライア）自動判定が可能です。重要なパラメータは半径 eps と最小点数 min_samples で、これらの選び方により結果が大きく変わります。OPTICS は密度のスケールを可視化して DBSCAN のようなしきい値依存性を緩和します。
Mean Shift
Mean Shift はモード探索に基づく方法で、カーネル密度推定のピークへデータ点をシフトさせることでクラスタを定義します。クラスタ数を事前指定する必要はありませんが、カーネル幅（bandwidth）の設定が結果を左右します。
スペクトラルクラスタリング
グラフ（類似度行列）を作成し、そのラプラシアン行列の固有ベクトルを用いて低次元空間に埋め込み、そこで k-means 等を適用します。クラスタ形状の柔軟性が高い一方、類似度行列や固有値分解の計算コストが課題になります。
カテゴリデータ向け（k-modes、k-prototypes）
k-means は平均を使うため連続値向けですが、k-modes はモード（最頻値）を用い、カテゴリ変数のクラスタリングに適します。k-prototypes は混合データ（連続＋カテゴリ）に対応します。
アルゴリズム的なポイントと計算量
各手法の代表的な計算特性は以下の通りです。
- k-means：反復回数 t、データ数 n、次元 d、クラスタ数 k に対し概算で O(n k d t)。k-means++ 初期化により収束と結果の安定性が改善されます。
- k-medoids（PAM）：典型的には O(k(n − k)^2) とされ、k-means より重い。CLARA などでサンプリングして軽量化。
- DBSCAN：空間インデックス（kd-tree, R-tree）を用いれば平均 O(n log n) 程度。索引なしでは最悪 O(n^2)。
- スペクトラルクラスタリング：類似度行列の構築 O(n^2)、固有値分解 O(n^3)（近似手法あり）。
前処理と距離（類似度）設計の重要性
非階層的クラスタリングは距離や類似度の定義に強く依存します。特徴量のスケーリング（標準化、正規化）は必須で、異なるスケールの変数が混在する場合は歪んだクラスタが得られます。また、カテゴリ変数は適切なエンコーディングや専用アルゴリズム（k-modes）を検討します。距離尺度としてはユークリッド距離のほか、マンハッタン、コサイン類似度、ガウスカーネルなどが利用され、手法やデータの性質に合わせて選びます。
クラスタ数 k の決め方と評価指標
パーティショニング法で最も悩ましいのはクラスタ数 k の選択です。代表的な手法：
- エルボー法：クラスタ数と SSE（総二乗誤差）をプロットし、減少率が緩やかになる「ひじ」を探す。
- シルエットスコア：-1〜1 の範囲でクラスタの分離度を評価。1 に近いほど良好。
- Davies–Bouldin 指数、Calinski–Harabasz 指数：群内と群間の分散比などを用いる尺度。
- 安定性評価：ブートストラップやサブサンプリングでクラスタが再現されるか検証する。
実務上の注意点と落とし穴
- 初期化の依存：k-means は初期中心の選び方で局所最適に陥る。k-means++ を推奨。
- 外れ値の影響：k-means は平均を使うため外れ値に敏感。k-medoids や密度ベース法で回避。
- スケールと次元の呪い：高次元では距離の意味が薄れる。主成分分析（PCA）などで次元削減を検討。
- パラメータ感度：DBSCAN の eps/min_samples、Mean Shift の bandwidth など、パラメータ調整が結果を大きく左右する。
- 解釈性：クラスタ中心や代表点を用いて特徴を説明し、ビジネス文脈で解釈可能にする工夫が必要。
適用事例とユースケース
- 顧客セグメンテーション：購買履歴や行動データから顧客群を抽出（k-means、k-prototypes）。
- 異常検知：DBSCAN で低密度領域をノイズ（異常）として検出。
- 画像処理：色の量子化（k-means）や領域分割。
- 生物情報学：遺伝子発現データのパターン抽出（スペクトラルや密度法）。
- 地理空間分析：位置データのクラスタ検出（DBSCAN が地理座標に適することが多い）。
実装上のヒント（scikit-learn等）
- scikit-learn には k-means、DBSCAN、MeanShift、SpectralClustering、KMeans の派生などが実装されています。k-means では init='k-means++'、n_init を増やすことで安定性が向上します。
- 大規模データではミニバッチ k-means（MiniBatchKMeans）やサンプリング（CLARA）を検討。
- 距離計算がボトルネックになる場合は近傍探索ライブラリ（FAISS, Annoy）や GPU 加速を利用。
- 結果の可視化には t-SNE や UMAP を使った埋め込みとクラスタ色分けが有効。
まとめ — どの手法をいつ使うか
非階層的クラスタリングは、目的・データ特性・スケールに応じて使い分けることが重要です。球状で連続値が中心の大量データなら k-means（あるいは MiniBatchKMeans）が有効。外れ値や任意形状のクラスタを扱うなら DBSCAN や OPTICS。カテゴリデータや混合データには k-modes / k-prototypes。複雑な構造や類似度に基づく場合はスペクトラルクラスタリングを検討します。いずれの場合も前処理、パラメータの検討、評価指標の適用と解釈が不可欠です。
参考文献
- Scikit-learn: Clustering — scikit-learn.org
- K-means clustering — Wikipedia
- Ester, M., Kriegel, H.-P., Sander, J., & Xu, X. (1996). A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise (DBSCAN)
- Ulrik von Luxburg (2007). A tutorial on spectral clustering
- Arthur, D. & Vassilvitskii, S. (2007). k-means++: The Advantages of Careful Seeding
- Fukunaga, K. & Hostetler, L. (1975). The estimation of the gradient of a density function, with applications in pattern recognition (Mean Shift の初期研究)
- Kaufman, L., & Rousseeuw, P. J. (1987). Clustering by means of medoids (PAM)
- Silhouette (clustering) — Wikipedia (Rousseeuw, 1987)
投稿者プロフィール
