原理簡介

對于給定的樣本集，按照樣本之間的距離大小，將樣本集劃分為K個簇。讓簇內(nèi)的點盡量緊密的連在一起，而讓簇間的距離盡量的大。

如果用數(shù)據(jù)表達式表示，假設簇劃分為(C1,C2,...Ck)，則我們的目標是最小化平方誤差E：

其中μi是簇Ci的均值向量，有時也稱為質心，表達式為：

算法描述

1）針對圖a所示的無標簽點集，想要把他分為兩類（即k=2）；

2）隨機分配兩個點作為每個簇的質心，如圖b中的紅色和藍色的‘x’；

3）然后判斷全部點到這兩個質心的距離，與質心距離較近的標志為同種顏色；

4）根據(jù)新劃分的簇，重新計算質心，直到達到一定的要求（比如均方誤差最小等）；

5）重復c和d的過程，即將所有點的類別標記為距離最近的質心的類別并求新的質心。

算法流程

輸入是樣本集D={x1,x2,...xm},聚類的簇樹k,最大迭代次數(shù)N；

輸出是簇劃分C={C1,C2,...Ck}。

1）從數(shù)據(jù)集D中隨機選擇k個樣本作為初始的k個質心向量：{μ1,μ2,...,μk}

2）對于n=1,2,...,N

?? a. 將簇劃分C初始化為Ct=?(t=1,2...k)

?? b. 對于i=1,2...m,計算樣本xi和各個質心向量μj(j=1,2,...k)的距離dij，將xi標記最小的為dij所對應的類別λi。此時更新Cλi=Cλi∪{xi}

? c.對于j=1,2,...,k,對Cj中所有的樣本點重新計算新的質心：

? d. 如果所有的k個質心向量都沒有發(fā)生變化，則轉到步驟3）

3）輸出簇劃分C={C1,C2,...Ck}