スタンフォードCS229 講義9: K-Meansとガウス混合モデル (Spring 2026)

TL;DR

この講義では、K‑meansをハードアサインメントクラスタリングアルゴリズムとして紹介し、ガウス混合モデル（GMM）をそのソフトアサインメントの確率的対応物として示し、両方が期待最大化（EM）ループでどのように解かれるか、初期化がなぜ重要か、そしてJensenの不等式がEMに対して計算可能な下界をどのように提供するかを説明します。

K‑means algorithm intuition

K‑meansは、各点を最寄りのクラスタ中心に繰り返し割り当て、その後各中心をその割り当てられた点の平均として再計算することにより、データをK個のクラスタに分割しようとします。

アルゴリズムはランダムな初期中心 μ₁ … μ_K から始まり、各点をユークリッド距離で最も近い中心のクラスタに割り当て、各中心をその割り当てられた点の算術平均に更新し、割り当てが変わらなくなるまで繰り返します。

クラスタラベルは任意であるため、すべての μ を交換しても同じ解が得られます；重要なのは、中心が正しい位置に収束することです。

Termination, optimality, and initialization

K‑meansは、クラスター内平方距離の和（L₂目的関数）が単調に減少し下限があるため常に終了し、アルゴリズムは割り当てが変わらない固定点に到達します。

この目的関数の全局最小値を見つけることはNP‑困難であるため、K‑meansは初期中心に依存する最適でない解に収束する可能性があります。

多くの局所最小値が存在し、異なるランダムな初期化が異なる最終クラスタリングを導くため、初期化ステップは重要です。

初期化を改善するため、K‑means++手法は良い近似比を保証する方法で初期中心を選択し、このバリアントはscikit‑learnなどの一般的なライブラリでデフォルトとなっています。

Choosing the number of clusters K

Kを選択することはモデリングの仮定であり、アナリストはデータに何個の異なるグループが存在するかについての事前の信念を表現しなければなりません。

Kを増やすとより細かいパーティションが得られますが、コストが低いからといって自動的に良いモデルとは限らず、より大きいKが本当に有益かどうかを評価するには外部の知識または検証基準が必要です。

したがって、Kを選ぶことは純粋にアルゴリズム的な基準ではなく、問題領域によって導かれる定性的な決定のままです。

From hard to soft assignments: Gaussian mixture models

GMMは、K‑meansのハードクラスタメンバシップを確率的割り当てに置き換えます：各点は未知の平均、共分散、混合重みを持つK個のガウスソースのいずれかから生成されます。

順方向モデルは、点X_iのソースを示す潜在変数Z_iを仮定し、Z_iはK個のソースからなる多項分布からサンプリングされ、その後X_iは対応するガウスからサンプリングされます。

観測された点のみが与えられたとき、目的はデータを最もよく説明するガウスのパラメータと混合重みを推定することです。

Expectation‑maximization for GMM

EMは2つのステップを交互に行います：

  • E‑step: 現在のパラメータ推定値にベイズの規則を適用して、点iがソースjから生じた事後確率w_{ij}を計算します。
  • M‑step: 各ガウスの平均、共分散、混合重みを、点の重み付き平均として更新します。ここでの重みは事後確率w_{ij}です。

事後確率が0または1の場合、M‑stepはK‑meansの更新に正確に簡約されます；それ以外の場合、EMは同じ計算のソフトで重み付きバージョンを実行します。

アルゴリズムはパラメータ推定値が収束するまで繰り返されます。

Jensen’s inequality and the EM lower bound

EMはデータの対数尤度の下界を最大化するものと見なすことができます。

Jensenの不等式は、凸関数φに対して𝔼[φ(X)] ≥ φ(𝔼[X])が成り立ち、凹関数では不等式の方向が逆になります。

E‑stepでは、EMは現在のパラメータにおいて厳密で最適化しやすい surrogate 関数を構築し、対数尤度にJensenの不等式を適用することでこの surrogate を得ます；これにより、各M‑stepは真の尤度を増加させるか、あるいは変化させないことが保証されます。

したがって、EMは尤度の定点に収束することが保証されますが、それが必ずしも大域的最大値とは限りません。

Practical takeaways

  • K‑meansはシンプルで解釈しやすいですが、初期化に敏感で、悪い局所最小に陥りやすいです。
  • K‑means++は、強い理論的保証を持つ中心の初期化の原則的な方法を提供します。
  • GMMは、クラスタメンバシップの不確実性をモデル化し、共分散を通じて楕円形のクラスタ形状を捉えることでK‑meansを拡張します。
  • EMは潜在変数モデルの一般的なフレームワークを提供し、その収束はJensenの不等式に依存して厳密な下界を構築します。
  • 両方のアルゴリズムは、アナリストがクラスター数Kを指定することを要求し、このモデリングの決定はドメイン知識に基づくべきです。

これらの概念は、多くの現代の無教師あり学習手法の基盤を形成し、アルゴリズムの単純さ、計算の困難さ、そして慎重な初期化とモデル選択の必要性の間のトレードオフを示しています。

Sources