Skip to content
検索結果に戻る

K-means クラスタリング

提唱者
MacQueen, J. B.; Lloyd, S. P.
年
1967 (formalized 1982)
種類
Partitional clustering
系統
Machine learning

この文章は機械翻訳で、まだ確認されていません。 英語の原文を読む

文字サイズ

何をする手法か?

K-means は、各観測値を最も近いセントロイドに繰り返し割り当て、割り当てられた点の平均としてセントロイドを更新することにより、データセットを K 個の非重複グループに分割する、古典的な教師なし分割クラスタリングアルゴリズムです。これは、機械学習およびデータ分析において最も広く使用されている探索的ツールの 1 つです。

手法の背後にある直感

データポイントの地図上に K 個の磁石を配置すると想像してください。各点は最も近い磁石に引き寄せられ、次に各磁石は引き寄せた点の重心に移動します。何も動かなくなるまで、この引き寄せと移動のサイクルを繰り返します。磁石は K 個の自然なグループを見つけました。K-means は、クラスター中心からの各点の二乗距離の合計、すなわちクラスター内平方和(WCSS または慣性)を最小化することにより、このアイデアを正確に形式化します。

歴史学

K-means のアイデアは、1967 年に MacQueen によって独立して導入され、用語が考案され、1950 年代に Stuart Lloyd によってベル研究所で効率的な反復アルゴリズムとして形式化されました(1982 年に出版)。2007 年に Arthur と Vassilvitskii による k-means++ 初期化の改善は、局所的最小値感度の問題に対処しました。今日、k-means は事実上すべてのデータサイエンスカリキュラムで教えられている、アンサンブル学習の基盤的な手法であり続けています。

使うべき場面

K-means は、K を事前に指定することに慣れている場合、またはエルボー法やシルエット法で検索する場合に、大規模な純粋に数値データセットの探索的クラスタリングに適しています。顧客セグメンテーション、画像圧縮、ドキュメントトピックグループ化、および教師あり学習前の前処理に役立ちます。クラスターが非球形である場合、サイズや密度が大きく異なる場合、特徴量がカテゴリカルまたは順序データである場合(代わりに k-modes または k-prototypes を使用)、クラスターの数が完全に不明で K の実験が実行できない場合、またはデータに多くの外れ値が含まれる場合(代わりに DBSCAN またはロバストなバリアントを使用)は避けてください。

限界と注意点

  • K を事前に指定する必要がある。K の選択を誤ると、意味のないクラスターが生成される。
  • 球形、同様のサイズのクラスターを想定している。細長い、不規則な、または異なるスケールのクラスターは誤って分割またはマージされる。
  • 外れ値に敏感である。単一の極端な点が、クラスターの大部分からセントロイドを大きく引き離す可能性がある。
  • 数値連続特徴量にのみ機能する。カテゴリカルデータには別のアルゴリズム(k-modes)が必要。
  • 局所的最小値に収束する。異なるランダムシードでの実行では、k-means++ または複数の再起動が使用されない限り、結果が異なる場合がある。

出典に示された条件は、独立した科学的レビューや分析エンジンによる検証の代わりにはなりません。

強み

  • 高速かつスケーラブル:反復あたり O(nKdi)、中程度の K と次元で数百万の観測値に実用的です。
  • 実装が簡単で、すべての主要な ML フレームワークで広く利用可能であり、非技術的な聴衆にも説明しやすいです。
  • 大規模で、よく分離された、ほぼ球形のクラスターで、サイズが似ている場合にうまく機能します。
  • k-means++ 初期化は、ランダム初期化と比較して、開始条件への感度を大幅に低減します。
  • 固定されたランダムシード内では決定論的であり、結果の再現性を保証します。

応用

  • 行動または人口統計学的特徴量に基づくマーケティングおよびパーソナライゼーションのための顧客セグメンテーション。
  • ピクセルカラーを K 個の代表的な値(色量子化)に量子化することによる画像圧縮。
  • ベクトル化後のトピックモデリングパイプラインのステップとしてのドキュメントおよびテキストクラスタリング。
  • セントロイドから遠く離れた点は、候補となる外れ値です。異常検知の前処理。
  • ガウス混合モデルや階層的クラスタリングなどのより複雑なアルゴリズムの初期化ステップ。
  • 遺伝子発現プロファイルが類似した遺伝子またはサンプルをグループ化するための遺伝子発現分析。

使い方

使い方

1

K 個のクラスターセントロイドが特徴空間に配置されます。これは、K 個のデータ点をランダムに選択する(Forgy)か、または悪い局所的最小値の可能性を減らすために初期セントロイドを広げる、より賢い k-means++ 戦略によって行われます。初期化の選択は重要です。k-means++ は通常、より速い収束とより良い最終解をもたらします。

2

各観測値は、ユークリッド距離に従ってセントロイドが最も近いクラスターに割り当てられます。このハード割り当ては、データの K 個の非重複パーティションを作成します。形式的には、各点 x_i はクラスター c_i = argmin_k ||x_i - mu_k||^2 に割り当てられます。

数式
c_i = \arg\min_k \|x_i - \mu_k\|^2
3

各セントロイドは、現在そのクラスターに割り当てられているすべての点の算術平均として再計算されます。mu_k = (1/|C_k|) × C_k 内のすべての x_i の合計。このステップは、現在の割り当てが与えられた場合、新しいセントロイドが各クラスター内の WCSS を最小化することを保証します。

数式
\mu_k = \frac{1}{|C_k|} \sum_{x_i \in C_k} x_i
4

割り当てステップと更新ステップは、セントロイドの位置が変化しなくなる(または許容誤差閾値未満で変化する)か、最大反復回数に達するまで交互に行われます。アルゴリズムは、WCSS の局所的最小値に収束することが保証されていますが、必ずしも大域的最小値ではありません。

5

解の品質は、総 WCSS(慣性)J = クラスターの合計(割り当てられた点の合計(||x_i - mu_k||^2))によって評価されます。K の選択は、エルボー法、シルエットスコア、またはギャップ統計によって対処される別の問題であり、アルゴリズム自体は K が事前に指定されることを必要とします。

数式
J = \sum_{k=1}^{K} \sum_{x_i \in C_k} \|x_i - \mu_k\|^2

よくある落とし穴

  • 距離計算で大規模なスケールの変数が支配的になるため、クラスタリング前に特徴量を標準化し忘れること。
  • エルボープロットまたはシルエット検証なしで、サンプル内 WCSS のみを検査して K を選択すること。これにより、トリビアリティに小さすぎるか大きすぎる K が選択される。
  • 悪い局所的最小値から保護するために、複数の再起動なしで最初の結果を受け入れ、1 回の初期化のみを実行すること。
  • 適切なエンコーディングなしで、または k-modes に切り替えることなく、特徴量行列にカテゴリカルまたは順序変数をそのまま含めること。
  • 特にクラスターがよく分離されていない場合に、外部検証なしでクラスターラベルを意味のあるグループIDとして扱うこと。

よくある質問

適切なクラスター数 K をどのように選択しますか?

K の範囲に対して k-means を実行し、クラスター内平方和を K に対してプロットし、減少率が急激に鈍化する「エルボー」を探します。各点が自身のクラスターと隣接クラスターにどれだけ似ているかを測定するシルエットスコアでこれを補完します。平均シルエットスコアが高いほど、より明確に定義されたクラスターを示します。

実行ごとに異なる結果が得られるのはなぜですか?

K-means は初期化に敏感であり、WCSS の大域的最小値ではなく局所的最小値に収束します。k-means++ 初期化を使用し、再現性のために固定されたランダムシードを設定してください。異なるシードでアルゴリズムを複数回実行し、最も低い慣性を持つ解を保持することが良い実践です。

k-means はカテゴリカルデータで機能しますか?

いいえ。K-means はユークリッド距離とセントロイド平均に依存しており、これらはカテゴリカル変数に対しては定義されていません。純粋なカテゴリカルデータには k-modes を、数値とカテゴリカルの混合データには k-prototypes を使用してください。

DBSCAN または GMM を k-means より優先すべきなのはいつですか?

クラスターが不規則な形状をしている場合、または K を指定せずに自動的な外れ値検出が必要な場合は、DBSCAN を使用してください。ソフト(確率的)なクラスター割り当て、またはサイズと方向が異なるクラスターを望む場合は、ガウス混合モデル(GMM)を使用してください。ただし、計算コストは高くなります。

特徴量をスケーリングする必要がありますか?

はい、ほぼ常に。K-means はユークリッド距離を使用するため、数値範囲が大きい特徴量がクラスタリングを支配します。すべての特徴量がすでに同じスケールでない限り、k-means を適合させる前に z スコア標準化または min-max スケーリングを適用してください。

関連する手法

参考文献

  1. Lloyd, S. P. (1982). Least squares quantization in PCM. IEEE Transactions on Information Theory, 28(2), 129–137.

    DOI 文献を開く
    コピーしました。
  2. MacQueen, J. B. (1967). Some methods for classification and analysis of multivariate observations. Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability, 1, 281–297.

    出版物の文献を開く
    コピーしました。