前述のように、多くのクラスタリング アルゴリズムは、ML で使用されるデータセット（多くの場合数百万個のサンプルを含む）にスケーリングされません。たとえば、アグロマータまたは分割階層クラスタリング アルゴリズムはすべての点のペアを確認し、それぞれ \(O(n^2 log(n))\) と \(O(n^2)\)の複雑さがあります。
このコースでは、 \(O(nk)\)としてスケーリングされる k 平均法に焦点を当てます。ここで、 \(k\)はユーザーが選択したクラスタ数です。このアルゴリズムは、各ポイントとそのクラスタのセントロイド間の距離を最小化することで、ポイントを\(k\) クラスタにグループ化します（図 1 を参照）。
その結果、K 平均法は、データを多数の円形分布で構成されているものとして効果的に扱い、これらの分布に対応するクラスタを見つけようとします。ただし、実際のデータには外れ値と密度ベースのクラスタが含まれており、k 平均法の基盤となる前提と一致しない場合があります。
k 平均法クラスタリング アルゴリズム
アルゴリズムでは、次の手順が実行されます。
\(k\)の初期推定値を指定します。これは後で変更できます。この例では、 \(k = 3\)を選択します。
ランダムに \(k\) 重心を選択します。
図 1: 初期化時の K 平均法。 各点を最も近いセントロイドに割り当てて、 \(k\) 初期クラスタ \(k\) を取得します。
図 2: 初期クラスタ。 クラスタごとに、クラスタ内のすべてのポイントの平均位置を取得して、新しいセントロイドを計算します。図 4 の矢印は、重心位置の変化を示しています。
図 3: 再計算された重心。 各ポイントを最も近い新しい重心に再割り当てします。
図 4: 再割り当て後のクラスタ。 ポイントがクラスタを変更しなくなるまで、手順 4 と 5 を繰り返して、重心とクラスタ メンバーシップを再計算します。大規模なデータセットの場合は、他の条件に基づいて収束前にアルゴリズムを停止できます。
重心の位置は最初にランダムに選択されるため、k 平均法では連続して実行すると結果が大きく異なることがあります。この問題を解決するには、k 平均法を複数回実行し、品質指標が最も優れた結果を選択します。（品質指標については、このコースの後半で説明します）。より適切な初期重心位置を選択するには、高度なバージョンの k 平均法が必要です。
数学を深く理解する必要はありませんが、興味がある方は、k 平均法は期待最大化アルゴリズムの特殊なケースであることを知っておいてください。UPenn のこのトピックに関する講義ノートをご覧ください。