一種改進(jìn)的K均值聚類算法

孟佳娜，鄧?yán)妫谟窈?，唐品?/p>

（大連民族學(xué)院理學(xué)院，遼寧大連 116605）

一種改進(jìn)的K均值聚類算法

孟佳娜，鄧?yán)?，于玉海，唐品?/p>

（大連民族學(xué)院理學(xué)院，遼寧大連 116605）

針對傳統(tǒng)K均值算法中采取的歐氏距離計(jì)算相似性的不足，提出一種新的相似性計(jì)算方法，并將這種方法與歐氏距離的度量方法進(jìn)行了比較。在UCI基準(zhǔn)數(shù)據(jù)集上的實(shí)驗(yàn)表明，該方法有更穩(wěn)定的聚類結(jié)果，是一種比較有效的聚類度量方法。

聚類分析;K均值算法;相似性

聚類分析廣泛應(yīng)用于模式識別、圖像處理、文本挖掘等領(lǐng)域，是非常重要的數(shù)據(jù)分析方法之一。目前已提出的聚類算法有很多，這些算法可以被分為基于劃分的方法、基于層次的方法、基于密度的方法、基于網(wǎng)格的方法和基于模型的方法［1］。在聚類方法中，K均值算法是最著名和最常用的劃分方法之一。K均值算法由于實(shí)現(xiàn)簡單、收斂速度快，自出現(xiàn)以來，已經(jīng)提出了許多改進(jìn)的算法。文獻(xiàn)［2］提出了一種關(guān)于K均值的局部搜索近似算法;文獻(xiàn)［3］針對初始中心敏感提出了一種選取初始聚類中心的算法。本文針對傳統(tǒng)K均值算法中計(jì)算相似性和選取初始中心點(diǎn)的不足，提出一種改進(jìn)的算法。

1 傳統(tǒng)的K均值聚類算法

K均值法具有經(jīng)典的聚類思想，邏輯簡明清晰。它的主要步驟如下:

步驟1對給定的m×n矩陣X，給出k個(gè)n維向量作為初始中心點(diǎn)。

步驟2比較數(shù)據(jù)集當(dāng)中樣本點(diǎn)與各中心點(diǎn)間的距離，將各點(diǎn)劃分到與其距離最近的類中，形成初始分類。

步驟3計(jì)算步驟2所形成的類的中心，使每類中心點(diǎn)得以更新。

步驟4重復(fù)步驟2和3，直到中心點(diǎn)不再移動，各類所包含的樣本點(diǎn)也不再改變?yōu)橹埂?/p>

2 基于新的相似性度量方法的K均值聚類算法

聚類分析中數(shù)據(jù)結(jié)構(gòu)可分為原始數(shù)據(jù)矩陣和距離矩陣。本文所討論的方法采用原始數(shù)據(jù)矩陣。原始數(shù)據(jù)矩陣X為

式中，xij（i=1，…，m;j=1，…，n）為第i個(gè)樣本的第j個(gè)屬性的觀測數(shù)據(jù)，第i個(gè)樣本為矩陣X的第i行所描述。在進(jìn)行聚類分析時(shí)，通過對原始數(shù)據(jù)矩陣進(jìn)行相應(yīng)操作來刻畫樣本之間的相似性。

本文所提出的K均值算法的改進(jìn)主要體現(xiàn)在初始中心點(diǎn)的選取和相似性度量兩個(gè)方面，下面介紹具體的改進(jìn)方法。

2.1 初始中心點(diǎn)的選取

初始中心點(diǎn)的選擇在K均值算法中非常重要，為了使各類具有一定的區(qū)分度，通常尋找散布較大的點(diǎn)作為初始中心點(diǎn)。在傳統(tǒng)的算法中主要是隨機(jī)選取初始中心點(diǎn)或是以前K個(gè)樣本作為初始中心點(diǎn)，在本文的研究中，將按照如下方法來選取中心點(diǎn):

（1）輸入原始數(shù)據(jù)矩陣。

（2）計(jì)算原始數(shù)據(jù)各維的最大值與最小值，保存為maxj與minj，表示第j維上數(shù)值的最大值與最小值。

（3）利用公式

計(jì)算得到第l類的中心點(diǎn)在第j維上的值，該值始終在開區(qū)間（minj，maxj）內(nèi)，且各中心點(diǎn)之間比較分散。

2.2 數(shù)據(jù)對象之間的相似性度量

對于聚類問題，一個(gè)算法產(chǎn)生的簇集可能有許多性質(zhì)，所以說一個(gè)聚類問題中相似性度量［4］的選擇是非常重要的。在傳統(tǒng)的K均值算法中，將每個(gè)樣本看成是高維空間中的一個(gè)點(diǎn)，進(jìn)而定義點(diǎn)與點(diǎn)之間的距離，距離越大說明樣本之間的相似性越小，距離越小說明樣本間的相似性越大，這樣得到的聚類結(jié)果是一些體積相近的球體。本文在傳統(tǒng)的分組規(guī)則上進(jìn)行改進(jìn)，用曼哈頓距離來定義樣本的屬性之間的相似性，再將樣本與樣本之間的相似性用各個(gè)屬性的曼哈頓距離來刻畫。兩個(gè)樣本xa，xb之間的相似性可定義為

兩個(gè)樣本間的相似系數(shù)等于n個(gè)屬性間相似系數(shù)之和，每對屬性間的相似系數(shù)等于每對屬性曼哈頓距離加1的倒數(shù)。式（2）把兩個(gè)對象間每個(gè)屬性的相似系數(shù)都映射到（0，1］區(qū)間，在每個(gè)屬性的貢獻(xiàn)相同的假設(shè)下，有更好的可解釋性，而對于歐氏距離的度量方法，則會出現(xiàn)某個(gè)屬性的影響遠(yuǎn)遠(yuǎn)大于其他屬性甚至其他所有屬性之和的現(xiàn)象，從而降低了其他屬性在相似性度量中的作用，影響了樣本類別的劃分，對最終的聚類效果產(chǎn)生一定的影響。

3 實(shí)驗(yàn)結(jié)果及分析

本文實(shí)驗(yàn)中選擇MyEclipse作為開發(fā)工具，使用java語言對算法進(jìn)行實(shí)現(xiàn)。

3.1 聚類效果的評價(jià)

評價(jià)一項(xiàng)工作的結(jié)果，首先要找出評價(jià)的標(biāo)準(zhǔn)，進(jìn)而根據(jù)標(biāo)準(zhǔn)確定評價(jià)指標(biāo)，利用定量化的方法來實(shí)現(xiàn)科學(xué)的評價(jià)。本文中所用的評價(jià)標(biāo)準(zhǔn)基于準(zhǔn)確率、召回率與F值［5］。對數(shù)據(jù)集中每個(gè)人工標(biāo)注的主題為Pl。假設(shè)在聚類算法形成的類層次結(jié)構(gòu)中存在一個(gè)與之對應(yīng)的簇Cl。為了發(fā)現(xiàn)Cl，遍歷聚類結(jié)果C={C1，C2，…，Ck}，計(jì)算準(zhǔn)確率、召回率和F值，從中挑選最優(yōu)指標(biāo)值及其對應(yīng)的簇，以該最優(yōu)的指標(biāo)值來判定Pl的質(zhì)量。對于任何人工主題Pl和聚類簇Cl:

3.2 實(shí)驗(yàn)結(jié)果

從UCI［6］數(shù)據(jù)集上選取4個(gè)數(shù)據(jù)集Iris，Wine，Soybean（small），Vehicle進(jìn)行聚類分析。UCI數(shù)據(jù)集是一個(gè)專門用于測試機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘算法的公共數(shù)據(jù)集。本文對4個(gè)數(shù)據(jù)集進(jìn)行了標(biāo)準(zhǔn)化和未標(biāo)準(zhǔn)化的對比實(shí)驗(yàn)，圖1列出了本文算法未經(jīng)標(biāo)準(zhǔn)化處理的實(shí)驗(yàn)結(jié)果。

從上述實(shí)驗(yàn)結(jié)果可以看出，改進(jìn)算法對數(shù)據(jù)集Wine和Soybean聚類后值有大幅的提高，提高了20%左右。而另外兩個(gè)數(shù)據(jù)集Iris，Vehicle則有所降低。Wine數(shù)據(jù)集有178個(gè)數(shù)據(jù)，分成3類，每個(gè)數(shù)據(jù)項(xiàng)有13個(gè)屬性，各個(gè)屬性的取值范圍差距較大。Alcohol（屬性1），F(xiàn)lavanoids（屬性8），Color_intensity（屬性11）這3個(gè)屬性對分類最為重要，它們的取值范圍分別為:（0.34～5.08），（1.28～13），（11.03～14.83），而對分類貢獻(xiàn)不大的屬性Proline（屬性13）的取值范圍是（278～1 680），在采用歐式距離計(jì)算相似性時(shí)，屬性Proline起到了絕對的作用，導(dǎo)致使用歐氏距離聚類時(shí)嚴(yán)重降低了效果，而使用本文提出的相似度量方法則明顯地減弱Proline（屬性13）的影響，提高了聚類的結(jié)果。數(shù)據(jù)集Soybean的分布與Wine相似。

圖1 原始數(shù)據(jù)未標(biāo)準(zhǔn)化的實(shí)驗(yàn)結(jié)果

由于數(shù)據(jù)集Iris的兩個(gè)重要屬性1（sepal length），屬性2（sepal width）的取值都較屬性3 （petal length）和屬性4（petal width）大或相當(dāng)，所以在這個(gè)數(shù)據(jù)集上并沒有體現(xiàn)出本文提出的度量方法的優(yōu)勢。數(shù)據(jù)集Vehicle的分布跟Iris相似，故聚類結(jié)果沒有大的變化。圖2列出了標(biāo)準(zhǔn)化后的實(shí)驗(yàn)結(jié)果。

圖2 原始數(shù)據(jù)標(biāo)準(zhǔn)化后的實(shí)驗(yàn)結(jié)果

從圖2結(jié)果可以看出，在4個(gè)數(shù)據(jù)集上用改進(jìn)算法都較原算法得到較好的聚類結(jié)果。

綜合圖1、圖2及實(shí)驗(yàn)中得到數(shù)據(jù)可以得到如下結(jié)論:

（1）數(shù)據(jù)未標(biāo)準(zhǔn)化采用本文算法進(jìn)行聚類，在數(shù)據(jù)集Wine，Soybean上的聚類效果好于原始的K均值算法，而在數(shù)據(jù)集Vehicle和Iris上，則效果有所下降。

（2）數(shù)據(jù)標(biāo)準(zhǔn)化和數(shù)據(jù)不標(biāo)準(zhǔn)化采用本文算法進(jìn)行聚類，在大多數(shù)數(shù)據(jù)集上聚類效果波動不大，故改進(jìn)算法相對于原算法有較為穩(wěn)定的聚類結(jié)果。

4 結(jié)語

本文提出了一種新的相似性度量方法。由于它把每個(gè)屬性的相似系數(shù)都映射到（0，1］之間，對于傳統(tǒng)的聚類算法把對象中每個(gè)屬性在聚類過程中的貢獻(xiàn)看作是相同的假設(shè)，有更好的可解釋性。在本文改進(jìn)的K均值算法中，對于初始中心點(diǎn)的選取，只是盡量取各維數(shù)上的稀疏點(diǎn)，從根本上講也是基于距離因素的選取。實(shí)際上，對于初始中心點(diǎn)，除了希望分布的盡量分散之外，還希望這些中心點(diǎn)具有一定的代表性，而本文改進(jìn)的算法中并沒有考慮到該因素，所以在初始中心點(diǎn)的選取上本文方法還有待進(jìn)一步完善。

［1］HAN Jiawei，MICHELINE K.數(shù)據(jù)挖掘概念與技術(shù)［M］.北京:機(jī)械工業(yè)出版社，2005.

［2］KANUNGO T，MOUNT D M.A local search approximation algorithm for k－means clustering［J］.Computational Geometry，2004，28:89－112.

［3］BRADLEY P S，F(xiàn)AYYAD U M.Refining initial points for k－means clustering［C］//Proceedings of the 15th International Conference on Machine Learning，Morgan Kaufmann，San Francisco，CA，1998.

［4］史金成.基于相關(guān)性的數(shù)據(jù)流聚類及其應(yīng)用研究［D］.合肥:合肥工業(yè)大學(xué)，2007.

［5］張堯庭，方開泰.多元統(tǒng)計(jì)分析引論［M］.北京:科學(xué)出版社，1982.

［6］http://archive.ics.uci.edu/ml/index.html.

An Improved K－Means Clustering Algorithm

MENG Jia－na，DENG Li－ling，YU Yu－h(huán)ai，TANG Pin－zhong
（College of Science，Dalian Nationalities University，Dalian Liaoning 116605，China）

According to the disadvantages of calculating similarity based on traditional Euclidean distance of K－Means algorithm，a new similarity metrics method is presented.The given method is compared with the Euclidean distance of the K－Means clustering algorithm.The experiments based on UCI benchmark data sets showed that the method has more stable clustering results，and is an effective clustering metrics method.

cluster analysis;K－Means;similarity

TP18

A

1009－315X（2011）03－0274－03

2010－12－17;最后

2011－01－14

中央高?；究蒲袠I(yè)務(wù)專項(xiàng)資金資助項(xiàng)目（DC10040118）;大連民族學(xué)院教學(xué)改革項(xiàng)目（Y－09－2009－03）。

孟佳娜（1972－），女，吉林四平人，副教授，主要從事數(shù)據(jù)挖掘、自然語言處理研究。

（責(zé)任編輯 鄒永紅）