前述のように、多くのクラスタリング アルゴリズムはデータセットに合わせてスケーリングできません。 多くの場合、数百万のサンプルを持つ ML で使用されています。たとえば 集計または分割階層クラスタリング アルゴリズムでは、すべてのペアが 複雑で \(O(n^2 log(n))\) \(O(n^2)\)
このコースでは \(O(nk)\)としてスケーリングされるため、K 平均法に焦点を当てます。ここで、 \(k\) ユーザーが選択したクラスタの数です。このアルゴリズムは、ポイントを \(k\) クラスタを作成します。各ポイントとその間の距離が 調整できます（図 1 を参照）。
その結果、K 平均法では実質的に、データがおおまかな複数の それに対応するクラスタを見つけようと試みます。 作成しますしかし、実際のデータには外れ値と密度ベースのクラスタが含まれている K 平均法の基礎となる仮定と一致しないことがあります。
K 平均法クラスタリング アルゴリズム
アルゴリズムの手順は次のとおりです。
\(k\)の初期推測を指定します。これは後で修正できます。今回 たとえば、 \(k = 3\)を選択します。
セントロイドを \(k\) ランダムに選択します。
<ph type="x-smartling-placeholder"></ph> 
図 1: 初期化時の K 平均法 各点を最も近いセントロイドに割り当てて、 \(k\) 初期クラスタを取得します。
<ph type="x-smartling-placeholder"></ph> 
図 2: 初期クラスタ クラスタごとに、画像の平均位置を取って新しい重心を計算します。 クラスタ内のすべてのポイントに適用されます。図 4 の矢印は、 重心位置などです
<ph type="x-smartling-placeholder"></ph> 
図 3: 再計算されたセントロイド 各ポイントを最も近い新しいセントロイドに再割り当てします。
<ph type="x-smartling-placeholder"></ph> 
図 4: 再割り当て後のクラスタ セントロイドとクラスタ メンバーシップを再計算して、次のようになるまでステップ 4 と 5 を繰り返します。 クラスタが変更されなくなります。大規模なデータセットの場合は、 他の基準に基づいて収束する前にアルゴリズムを停止する
重心位置は最初はランダムに選択されるため、K 平均法は 連続して実行すると、大きく異なる結果が返されます。この問題を解決するには K 平均法を複数回実行して品質が最も高い結果を選択する できます。（品質指標については、このコースで後ほど説明します）。次が必要です より適切な初期重心位置を選択できるようにしました。
数学の深い理解は必要ありませんが、 K 平均法は、入力シーケンスの 予測最大化アルゴリズム。詳しくは、 このトピックに関するレクチャー メモをご覧ください。