k 均值聚類算法的工作流程是這樣的：首先選取 k 個點潘酗，作為初始 k 個簇的中心（這個 k 是人為設(shè)定的超參數(shù)），然后將其余的數(shù)據(jù)對象分配到距離自己最近的簇中心所在的簇中卦睹。假設(shè)樣本集中有 l 個樣本错沃，每個樣本都是一個具備 n 個特征跌前，用向量 xi 表示第 i 個樣本。現(xiàn)在我們假設(shè)要把所有樣本劃分為 k 個簇，即：
S={S1, S2, ......, SK}
這里 Sl(1≤l≤k) 表示第 l 個簇圆存，S 是由若干簇構(gòu)成的簇集合叼旋。
那么，最優(yōu)的分配方案就是優(yōu)化如下目標(biāo)函數(shù)的解：
其中沦辙，μi 簇中的均值向量夫植，有的文獻(xiàn)也稱之為質(zhì)心（centroid），共有 k 個怕轿，因此這個算法叫作 k 均值聚類算法偷崩。由于以上公式所示的組合優(yōu)化問題是一個 NP 難題，通常難以求得最優(yōu)解撞羽，只能求得近似解阐斜。因此在實現(xiàn)過程中，通常采用循環(huán)迭代的方式诀紊，逐步收斂到局部最優(yōu)解處谒出。
當(dāng)所有的點均被劃分到某一個簇后，要再對各個簇中心（μi）進(jìn)行更新邻奠。更新的依據(jù)是笤喳，根據(jù)每個聚類對象的均值，計算每個對象到簇中心的距離最小值碌宴，直到滿足一定的條件才停止計算杀狡。這個條件一般為函數(shù)收斂（比如前后兩次迭代的簇中心足夠接近）或計算達(dá)到一定的迭代次數(shù)。
k 均值聚類算法的過程如圖 1 所示贰镣。
圖 1：k 均值聚類算法的過程
在 k 均值聚類算法中呜象，我們主要需要考慮兩個關(guān)鍵問題：初始簇中心（也稱質(zhì)心）的選取及距離的度量。常見的選取初始簇中心的方法是隨機挑選 k 個點碑隆，但這樣形成的簇質(zhì)量往往很差恭陡。
因此，我們采用其他常用方法挑選初始簇中心上煤，具體如下：
- 多次運行調(diào)優(yōu)休玩。每次使用一組不同的隨機初始簇中心，最后從中選取具有最小平方誤差的簇集劫狠。這種方法簡單拴疤，但效果難料，主要取決于數(shù)據(jù)集的大小和簇的個數(shù)k独泞；
- 根據(jù)先驗知識（即歷史經(jīng)驗）來決定 k 值遥赚。
對于另一個因素—如何確定對象之間的距離，根據(jù)問題場景不同阐肤，度量方式也是不同的凫佛。在歐式空間中讲坎，我們可以通過歐氏距離來度量兩個樣本之間的距離，而對于非歐式空間愧薛，可以選擇 Jaccard 距離晨炕、Cosine 距離或 Edit 距離等度量方式。
