孔令凱　向毅　梁松

摘 要：為了解決進(jìn)行K-means聚類時類數(shù)的自動選擇和Hierarchical聚類在處理大量高維數(shù)據(jù)時時間效率低的問題，在K-means聚類算法的基礎(chǔ)上結(jié)合Hierarchical聚類算法，提出了一種基于集體智慧編程方法的用于處理大量數(shù)據(jù)時動態(tài)選取K值的聚類模型。實(shí)驗(yàn)結(jié)果表明該算法比K-means聚類具有更好的聚類效果，同時解決了Hierarchical聚類方法時間效率低的問題。本模型通過K-means聚類生成適量的類簇，再利用Hierarchical聚類對這些類再進(jìn)行聚類，最后經(jīng)過剪枝得到合適的聚類結(jié)果，以此實(shí)現(xiàn)動態(tài)選取K值。

關(guān)鍵詞：K-means聚類；Hierarchical聚類；降維；剪枝

引言

K-means聚類算法是最為經(jīng)典的基于劃分的聚類算法，該算法的最大優(yōu)勢在與簡潔和快速，但是該算法聚類效果的好壞取決于初始中心的選擇和距離公式。同時，Hierarchical聚類在處理大量數(shù)據(jù)時，會生成一個高維的矩陣，導(dǎo)致時間效率低。

本算法模型正是針對K-means聚類對大量數(shù)據(jù)進(jìn)行降維，以此降低Hierarchical聚類的時間效率，同時利用Hierarchical提高了K-means的聚類效果并實(shí)現(xiàn)k值的選取。

1 結(jié)合Hierarchical聚類和K-means聚類算法的算法模型

本模型主要分為一下幾步：首先對數(shù)據(jù)進(jìn)行預(yù)估，預(yù)設(shè)一個合適的k值（大于目標(biāo)類數(shù)，遠(yuǎn)小于總樣本數(shù)），使用K-means聚類進(jìn)行聚類操作；然后對k個類的平均中心點(diǎn)進(jìn)行Hierarchical聚類操作，生成一棵樹；最后通過判斷k個類的中心點(diǎn)的拐點(diǎn)，對這個樹進(jìn)行剪枝，從而生成newk個子樹，即newk個類。

該模型的算法流程如下：

輸入：k，data[m，n]；

（1）K-means聚類：

1.選擇k個初始中心點(diǎn)，c[k，n]；

2.對于data[m，n]中的每一行m，尋找距離其最近的中心點(diǎn)I （i∈k），標(biāo)記data[m，：]為I；

3.對于所有標(biāo)記為i的點(diǎn)，重新計(jì)算中心點(diǎn)（使用所有標(biāo)記為i的點(diǎn)的平均數(shù)）

4.重復(fù)2，3，直至循環(huán)10次；

（2）Hierarchical聚類：

5.對4中生成的k個中心點(diǎn)計(jì)算兩兩間的距離，生成距離矩陣

6.選擇最近的兩個中心點(diǎn)，合并生成新的中心點(diǎn)，使用兩個類中的所有點(diǎn)的平均值代表新的中心點(diǎn)

7.重新生成距離矩陣

8.重復(fù)6和7，直到合并成一個類為止

（3）剪枝操作：

9.根據(jù)8生成的樹中每一步合并操作時，兩個子節(jié)點(diǎn)之間的距離，計(jì)算拐點(diǎn)

10.根據(jù)計(jì)算的拐點(diǎn)進(jìn)行剪枝，得到newk個子樹

2 實(shí)驗(yàn)評價

本模型中的K-means聚類和Hierarchical聚類使用Python編程實(shí)現(xiàn)，利用了sklearn工具中實(shí)現(xiàn)的聚類算法KMeans和hierarchy數(shù)據(jù)結(jié)構(gòu)。實(shí)驗(yàn)機(jī)器配置為：Intel Core i7-3537U 2.00GHz CPU，8.00 GB 內(nèi)存；Python 2.7.5（32 bit）。

數(shù)據(jù)樣本為900條時：

3 結(jié)束語

本模型通過結(jié)合Hierarchical聚類和K-means聚類算法，實(shí)現(xiàn)了一種新的聚類方式。從實(shí)驗(yàn)結(jié)果可以看出本方法在處理大量高維數(shù)據(jù)時效果明顯，時間效率低且聚類效果更好。本算法仍存在不足：需要預(yù)設(shè)一個合適的較大的k值，此k值不宜過大，太大會導(dǎo)致算法效率的降低；另一方面，此值也不能小于聚類效果最好時的類數(shù)，否則聚類效果不理想。基于此點(diǎn)，需要在使用前根據(jù)數(shù)據(jù)樣本進(jìn)行預(yù)估，然后給出一個較為合適的k值，或者進(jìn)行幾次實(shí)驗(yàn)進(jìn)行探索。本算法已經(jīng)實(shí)現(xiàn)了k值的自動選擇，也大大減小了在探索過程中所需的時間和精力。

參考文獻(xiàn)

[1]王千，王成，馮振元.葉金鳳K-means聚類算法研究綜述[J].電子設(shè)計(jì)工程，2012（7）.

[2]胡偉.改進(jìn)的層次K均值聚類算法[J].計(jì)算機(jī)工程與應(yīng)用，2013，49（2）.

[3]楊燕，靳蕃.KAMEL Mohamed聚類有效性評價綜述[J].計(jì)算機(jī)應(yīng)用研究，2008（1）.