(1)盡量選擇距離比較遠(yuǎn)的點(diǎn)(方法：依次計(jì)算出與已確定的點(diǎn)(第一個(gè)點(diǎn)可以隨機(jī)選擇)的距離，并選擇距離最大的點(diǎn))。當(dāng)k比較大時(shí)，這種方法計(jì)算量比較復(fù)雜，適合二分K-均值聚類算法的k值初始化。
(2)采取層次聚類的方式找出k個(gè)簇。 TBD
3. 特征值處理
K-均值聚類算法需要數(shù)值型數(shù)據(jù)來(lái)進(jìn)行相似性度量，也可以將標(biāo)稱型數(shù)據(jù)映射為二值型數(shù)據(jù)再用于度量相似性。
另外，樣本會(huì)有多個(gè)特征，每一個(gè)特征都有自己的定義域和取值范圍，他們對(duì)distance計(jì)算的影響也就不一樣，如取值較大的影響力會(huì)蓋過(guò)取值較小的參數(shù)。為了公平，樣本特征取值必須做一些scale處理，最簡(jiǎn)單的方式就是所有特征的數(shù)值都采取歸一化處置，把每一維的數(shù)據(jù)都轉(zhuǎn)化到0,1區(qū)間內(nèi)，從而減少迭代次數(shù)，提高算法的收斂速度。
4. k值的選取
前面提到，在k-均值聚類中簇的數(shù)目k是一個(gè)用戶預(yù)先定義的參數(shù)，那么用戶如何才能知道k的選擇是否正確?如何才能知道生成的簇比較好呢?與K-近鄰分類算法的k值確定方法一樣,k-均值算法也可采用交叉驗(yàn)證法確定誤差率最低的k值，參考“機(jī)器學(xué)習(xí)經(jīng)典算法詳解及Python實(shí)現(xiàn)–K近鄰(KNN)算法”的2.3節(jié)-k值的確定。
當(dāng)k的數(shù)目低于真實(shí)的簇的數(shù)目時(shí)，SSE(或者平均直徑等其他分散度指標(biāo))會(huì)快速上升。所以可以采用多次聚類，然后比較的方式確定最佳k值。多次聚類，一般是采用 k=1, 2, 4, 8… 這種二分?jǐn)?shù)列的方式，通過(guò)交叉驗(yàn)證找到一個(gè)k在 v/2, v 時(shí)獲取較好聚類效果的v值，然后繼續(xù)使用二分法，在 [v/2, v] 之間找到最佳的k值。
5. K-均值算法的Python實(shí)現(xiàn)
下載地址：TBD
K-均值算法收斂但聚類效果較差的原因是，K-均值算法收斂到了局部最小值，而非全局最小值(局部最小值指結(jié)果還可以但并非最好結(jié)果，全局最小值是可能的最好結(jié)果)。為克服k-均值算法收斂于局部最小值的問(wèn)題，有人提出了另一個(gè)稱為二分k- 均值(bisecting K-means)的算法。
(三)二分K-均值(bisecting k-means)聚類算法
顧名思義，二分K-均值聚類算法就是每次對(duì)數(shù)據(jù)集(子數(shù)據(jù)集)采取k=2的k-均值聚類劃分，子數(shù)據(jù)集的選取則有一定的準(zhǔn)則。二分K-均值聚類算法首先將所有點(diǎn)作為一個(gè)簇，第一步是然后將該簇一分為二，之后的迭代是：在所有簇中根據(jù)SSE選擇一個(gè)簇繼續(xù)進(jìn)行二分K-均值劃分，直到得到用戶指定的簇?cái)?shù)目為止。根據(jù)SSE選取繼續(xù)劃分簇的準(zhǔn)則有如下兩種:
(1)選擇哪一個(gè)簇進(jìn)行劃分取決于對(duì)”其劃分是否可以最大程度降低SSE的值。這需要將每個(gè)簇都進(jìn)行二分劃分，然后計(jì)算該簇二分后的簇SSE之和并計(jì)算其與二分前簇SSE之差(當(dāng)然SSE必須下降)，最后選取差值最大的那個(gè)簇進(jìn)行二分。
該方案下的二分k-均值算法的偽代碼形式如下：
***************************************************************
將所有數(shù)據(jù)點(diǎn)看成一個(gè)簇
當(dāng)簇?cái)?shù)目小于k時(shí)
對(duì)每一個(gè)簇
計(jì)算總誤差
在給定的簇上面進(jìn)行k-均值聚類(k=2)
計(jì)算將該簇一分為二后的總誤差
選擇使得誤差最小的那個(gè)簇進(jìn)行劃分操作
***************************************************************
(2)另一種做法是所有簇中選擇SSE最大的簇進(jìn)行劃分，直到簇?cái)?shù)目達(dá)到用戶指定的數(shù)目為止，算法過(guò)程與(1)相似，區(qū)別僅在于每次選取簇中SSE最大的簇。
二分K-均值聚類算法的Python實(shí)現(xiàn)
下載地址：TBD
End.
作者：Python中文社區(qū)(中國(guó)統(tǒng)計(jì)網(wǎng)特邀認(rèn)證作者)