機械学習では、何百万ものサンプルを含むデータセットが見つかることがあります。ML アルゴリズムは、このような大規模なデータセットに効率的にスケールする必要があります。ただし、多くのクラスタリング アルゴリズムは、すべてのポイントのペア間の類似度を計算する必要があるため、スケールされません。つまり、ランタイムは、ポイント数の 2 乗（ \(O(n^2)\)）で増加します。たとえば、集約型または分割型の階層型クラスタリング アルゴリズムは、すべてのポイントのペアを参照し、それぞれ \(O(n^2 log(n))\) と \(O(n^2)\)が複雑です。
このコースでは k 平均法に焦点を当てています。 \(O(nk)\)はクラスタの数で、 \(k\)はクラスタ数です。k 平均法は、点とクラスタの重心の間の距離を最小限に抑えて（ \(k\) 図 1 を参照）、ポイントをクラスタに含めます。クラスタのセントロイドは、クラスタ内のすべてのポイントの平均です。
ここに示すように、K 平均法でほぼ円形のクラスタが見つかります。概念的には、これは、K 平均法により、データがほぼ多数の複数の分布からなる効果的に扱われ、それらの分布に対応するクラスタを見つけようとすることを意味します。実際には、データには外れ値が含まれているため、そのようなモデルには適合しない可能性があります。
K 平均法を実行する前に、クラスタ数（ \(k\)）を選択する必要があります。まず、 \(k\)を推測します。この数値を微調整する方法については、後で説明します。
K 平均法クラスタリング アルゴリズム
データをクラスタにクラスタ化するために、 \(k\) K 平均法は以下の手順で行います。
ステップ 1
このアルゴリズムでは、クラスタごとにセントロイドをランダムに選択します。この例では、3 の \(k\) を選択しているため、アルゴリズムはランダムに 3 つのセントロイドを選択します。
ステップ 2
このアルゴリズムは、各ポイントに最も近いセントロイドを割り当て、 \(k\) 初期クラスタを取得します。
ステップ 3
すべてのクラスタに関して、アルゴリズムはクラスタ内のすべてのポイントの平均値に基づいてセントロイドを再計算します。図 3 では、重心の変化を矢印で示しています。セントロイドが変化すると、アルゴリズムによって最も近いセントロイドにポイントが再割り当てされます。図 4 は、再割り当て後の新しいクラスタを示しています。
ステップ 4
アルゴリズムが重心の計算を繰り返し、ポイントの割り当てがクラスタの変更を停止するまで続きます。大規模なデータセットをクラスタ化する場合は、代わりに他の基準を使用して、収束に達する前にアルゴリズムを停止します。
このコースの K 平均法を使った数学を理解する必要はありません。ただし、興味があれば数学的に証明できます。
セントロイドの位置は最初にランダムに選択されるので、k 平均法は連続実行で大きく異なる結果を返すことができます。この問題を解決するには、K 平均法を複数回実行し、最適な指標で結果を選択します。（品質指標については、このコースで後ほど説明します）。初期セントロイドの位置を選択できるようにするには、K 平均法の高度なバージョンが必要になります。