孔令凱　向毅　梁松

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

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

引言

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

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

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

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

該模型的算法流程如下：

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

（1）K-means聚類：

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

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

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

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

（2）Hierarchical聚類：

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

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

7.重新生成距離矩陣

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

（3）剪枝操作：

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

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

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

本模型中的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條時(shí)：

3 結(jié)束語(yǔ)

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

參考文獻(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聚類有效性評(píng)價(jià)綜述[J].計(jì)算機(jī)應(yīng)用研究，2008（1）.