基本的k-means算法流程

1、引言

k-means與kNN雖然都是以k打頭，但卻是兩類算法——kNN為監(jiān)督學(xué)習(xí)中的分類算法，而k-means則是非監(jiān)督學(xué)習(xí)中的聚類算法；二者相同之處：均利用近鄰信息來(lái)標(biāo)注類別。

聚類是數(shù)據(jù)挖掘中一種非常重要的學(xué)習(xí)流派，指將未標(biāo)注的樣本數(shù)據(jù)中相似的分為同一類，正所謂“物以類聚，人以群分”嘛。k-means是聚類算法中最為簡(jiǎn)單、高效的，核心思想：由用戶指定k個(gè)初始質(zhì)心（initial centroids)，以作為聚類的類別（cluster），重復(fù)迭代直至算法收斂。

2、基本算法

在k-means算法中，用質(zhì)心來(lái)表示cluster；且容易證明k-means算法收斂等同于所有質(zhì)心不再發(fā)生變化?；镜膋-means算法流程如下：

選取k個(gè)初始質(zhì)心（作為初始cluster）； repeat： 對(duì)每個(gè)樣本點(diǎn)，計(jì)算得到距其最近的質(zhì)心，將其類別標(biāo)為該質(zhì)心所對(duì)應(yīng)的cluster； 重新計(jì)算k個(gè)cluser對(duì)應(yīng)的質(zhì)心； until 質(zhì)心不再發(fā)生變化

對(duì)于歐式空間的樣本數(shù)據(jù)，以平方誤差和（sum of the squared error, SSE)作為聚類的目標(biāo)函數(shù)，同時(shí)也可以衡量不同聚類結(jié)果好壞的指標(biāo)：

表示樣本點(diǎn)到cluster的質(zhì)心距離平方和；最優(yōu)的聚類結(jié)果應(yīng)使得SSE達(dá)到最小值。

下圖中給出了一個(gè)通過(guò)4次迭代聚類3個(gè)cluster的例子：

k-means存在缺點(diǎn)：

k-means是局部最優(yōu)的，容易受到初始質(zhì)心的影響；比如在下圖中，因選擇初始質(zhì)心不恰當(dāng)而造成次優(yōu)的聚類結(jié)果（SSE較大）：

同時(shí)，k值的選取也會(huì)直接影響聚類結(jié)果，最優(yōu)聚類的k值應(yīng)與樣本數(shù)據(jù)本身的結(jié)構(gòu)信息相吻合，而這種結(jié)構(gòu)信息是很難去掌握，因此選取最優(yōu)k值是非常困難的。

3、優(yōu)化

為了解決上述存在缺點(diǎn)，在基本k-means的基礎(chǔ)上發(fā)展而來(lái)二分 (bisecting) k-means，其主要思想：一個(gè)大cluster進(jìn)行分裂后可以得到兩個(gè)小的cluster；為了得到k個(gè)cluster，可進(jìn)行k-1次分裂。算法流程如下：

初始只有一個(gè)cluster包含所有樣本點(diǎn)； repeat: 從待分裂的clusters中選擇一個(gè)進(jìn)行二元分裂，所選的cluster應(yīng)使得SSE最??； until 有k個(gè)cluster

上述算法流程中，為從待分裂的clusters中求得局部最優(yōu)解，可以采取暴力方法：依次對(duì)每個(gè)待分裂的cluster進(jìn)行二元分裂（bisect）以求得最優(yōu)分裂。二分k-means算法聚類過(guò)程如圖：

從圖中，我們觀察到：二分k-means算法對(duì)初始質(zhì)心的選擇不太敏感，因?yàn)槌跏紩r(shí)只選擇一個(gè)質(zhì)心。