演算法描述

1.選取$K$個點做爲初始聚集的簇心（也可選擇非樣本點）;
2.分別計算每個樣本點到 $K$個簇核心的距離（這裏的距離一般取歐氏距離或餘弦距離），找到離該點最近的簇核心，將它歸屬到對應的簇；
3.所有點都歸屬到簇之後， $M$個點就分爲了$K$個簇。之後重新計算每個簇的重心（平均距離中心），將其定爲新的「簇核心」；
4.反覆 反復迭代 2 - 3 步驟，直到達到某個中止條件。
注：常用的中止條件有迭代次數、最小平方誤差$MSE$、簇中心點變化率；

優勢

簡單快速，適合常規數據集

劣勢

1.$K$值難以確定
2.對初始簇中心點是敏感的
3.複雜度與樣本成線性關係
4.很難發現任意形狀的簇
5.特殊值(離羣值或稱爲異常值)對模型的影響比較大。

K值選取方法

1.手肘法

通過計算誤差平方和
$SSE=\sum_{i=1}^{k}\sum_{p\in C_{i} }\left | p-m_{i} \right |^{2}$
其中，$C_{i}$是第$i$個簇，$p$是$C_i$中的樣本點，$m_i$是$C_i$的質心（$C_i$中所有樣本的均值），$SSE$是所有樣本的聚類誤差，代表了聚類效果的好壞。

隨着聚類數k的增大，樣本劃分會更加精細，每個簇的聚合程度會逐漸提高，那麼誤差平方和$SSE$自然會逐漸變小。並且，當$k$小於真實聚類數時，由於$k$的增大會大幅增加每個簇的聚合程度，故$SSE$的下降幅度會很大，而當$k$到達真實聚類數時，再增加$k$所得到的聚合程度回報會迅速變小，所以$SSE$的下降幅度會驟減，然後隨着$k$值的繼續增大而趨於平緩，也就是說$SSE$和$k$的關係圖是一個手肘的形狀，而這個肘部對應的$k$值就是數據的真實聚類數。當然，這也是該方法被稱爲手肘法的原因。

2.輪廓係數

通過計算輪廓係數
$S_i=\frac{b_i-a_i}{max\{a_i,b_i\}}$
計算樣本$i$到同簇其他樣本的平均距離$a_i$。$a_i$ 越小，說明樣本$i$越應該被聚類到該簇。將$a_i$ 稱爲樣本i的簇內不相似度。
計算樣本$i$到其他某簇$C_j$的所有樣本的平均距離$b_{ij}$，稱爲樣本$i$與簇$C_j$ 的不相似度。定義爲樣本$i$的簇間不相似度:$b_i =min\{b_{i1}, b_{i2}, ..., b_{ik}\}$。
$s_i$接近1，則說明樣本$i$聚類合理。
$s_i$接近-1，則說明樣本$i$更應該分類到另外的簇。
若si 近似爲0，則說明樣本$i$在兩個簇的邊界上。
求出所有樣本的輪廓係數後再求平均值就得到了平均輪廓係數。平均輪廓係數的取值範圍爲$[-1,1]$，且簇內樣本的距離越近，簇間樣本距離越遠，平均輪廓係數越大，聚類效果越好。那麼，很自然地，平均輪廓係數最大的k便是最佳聚類數。

初始聚類中心選取方法

1.隨機選取

顧名思義，主要有兩種隨機選取的方式：
1.隨機產生數據大小範圍內的$K$個點作爲初始的簇類中心點。
2.隨機選取$K$個原始樣本點作爲初始的聚類中心點。

2.kmeans++

1.從輸入的數據點集合中隨機選擇一個點作爲第一個聚類中心
2.對於數據集中的每一個點$x$，計算它與最近聚類中心(指已選擇的聚類中心)的距離$D(x)$
3.從$D(x)$較大的點中，隨機選取一點作爲聚類中心
4.重複2和3直到$k$個聚類中心被選出來

3.間接選取

選用其它的聚類演算法（如層次聚類或Canopy演算法）進行初始聚類，然後從$k$個類別中分別隨機選取$k$個點，來作爲kmeans的初始聚類中心點