張明微, 吳海濤

(上海師范大學(xué) 信息與機(jī)電工程學(xué)院,上海 200234)

?

一種優(yōu)化初始聚類中心的k-means算法

張明微, 吳海濤

(上海師范大學(xué) 信息與機(jī)電工程學(xué)院,上海 200234)

隨機(jī)選擇初始聚類中心的k-means算法易使聚類陷入局部最優(yōu)解、聚類結(jié)果不穩(wěn)定且受孤立點(diǎn)影響大等問題.針對這些問題,提出了一種優(yōu)化初始聚類中心的方法及孤立點(diǎn)排除法.該算法首先選擇距離最遠(yuǎn)的兩點(diǎn)加入初始化中心,再根據(jù)這兩點(diǎn)將原始簇分成兩個(gè)聚簇,在這兩個(gè)簇中挑選方差較大的簇按照一定的規(guī)則進(jìn)行分裂直至找到k個(gè)中心,初始中心的選擇過程中用到孤立點(diǎn)排除法.在UCI數(shù)據(jù)集及人造含一定比例的噪音數(shù)據(jù)集下,通過實(shí)驗(yàn)比較了改進(jìn)算法與其他算法的優(yōu)劣.實(shí)驗(yàn)表明,改進(jìn)后的算法不僅受孤立點(diǎn)的影響小、穩(wěn)定性好而且準(zhǔn)確度也高.

初始聚類中心; k-means算法; 孤立點(diǎn)排除法; 聚簇; UCI數(shù)據(jù)集

0 引 言

聚類分析是數(shù)據(jù)挖掘研究的一項(xiàng)重要技術(shù),它的誕生為從大量的數(shù)據(jù)中獲取有價(jià)值的知識提供了一種有效的方法.它廣泛地應(yīng)用于文本搜索、模式識別人工智能、圖像分析等領(lǐng)域[1].常用的聚類分析方法包括基于劃分、基于層次、基于密度、基于網(wǎng)格和基于模型等算法[2].k-means是劃分方法中一種應(yīng)用較為廣泛的算法,它有很多優(yōu)點(diǎn)也存在許多不足.針對k-means算法的不足的研究分為兩個(gè)分支:1) 初始聚類中心的個(gè)數(shù)k;2) 初始聚類中心的選擇.本文作者針對后者進(jìn)行了研究,提出了一種新的初始聚類中心算法.實(shí)驗(yàn)結(jié)果表明本算法在準(zhǔn)確性與穩(wěn)定性方面比傳統(tǒng)的聚類效果好,實(shí)驗(yàn)結(jié)果也更接近實(shí)際數(shù)據(jù)分布.

1 k-means算法介紹及研究現(xiàn)狀

1.1 k-means算法介紹

設(shè)有樣本X={x1,x2,x3,…xn},n為樣本數(shù).k-means算法的思想:首先從樣本集x中隨機(jī)選擇k個(gè)數(shù)據(jù)對象作為初始聚類中心,其次根據(jù)每個(gè)數(shù)據(jù)對象與k個(gè)聚類中心的相似程度將其分配到最相似的簇中,然后重新計(jì)算每個(gè)新簇的平均值并將其作為下次迭代的聚類中心,不斷重復(fù)該過程直到更新后的簇中心與更新前一致,也就是準(zhǔn)則函數(shù)E收斂.目標(biāo)是使類內(nèi)對象相似性最大,類間對象相似性最小[3].數(shù)據(jù)之間的相似程度可以通過計(jì)算數(shù)據(jù)兩兩之間的距離來確定.常用的距離測度是歐氏距離.對于n維實(shí)數(shù)向量空間中兩點(diǎn)的歐氏距離定義為:

其中,xi和yi分別是x和y的第i個(gè)屬性值.準(zhǔn)則函數(shù)定義為:

k-means算法描述如圖1所示.

圖1 k-means算法

1.2 研究現(xiàn)狀

針對k-means算法初始聚類中心點(diǎn)的選取問題,眾多學(xué)者從不同角度進(jìn)行了研究.段桂芹[4]采用基于均值與最大距離乘積的方法來優(yōu)化初始聚類中心,該算法首先選擇距離樣本集均值最遠(yuǎn)的數(shù)據(jù)對象加入聚類中心集合,再依次將與樣本集均值和當(dāng)前聚類中心乘積最大的數(shù)據(jù)對象加入聚類中心集合,從而提高了準(zhǔn)確率.翟東海等[5]基于距離最遠(yuǎn)的樣本點(diǎn)最不可能分到同一個(gè)簇中的思想,提出了最大距離法選取初始簇中心的k-means文本聚類算法,同時(shí),也重新構(gòu)造了迭代中的簇中心計(jì)算公式和測度函數(shù).謝娟英等[6]根據(jù)樣本空間分布緊密度信息,提出利用最小方差優(yōu)化初始聚類中心的k-means算法,該算法選擇方差最小且相距一定距離的樣本作為初始聚類中心.劉家星等[7]提出一種基于半徑的k-means+λ算法,在選擇簇的初始中心點(diǎn)時(shí),根據(jù)λ參數(shù)計(jì)算各點(diǎn)間距離比例,并以某個(gè)特定的距離為半徑作圓,在圓內(nèi)根據(jù)距離比例選擇一個(gè)初始化中心點(diǎn),該算法在錯(cuò)誤率和運(yùn)算時(shí)間上具有更高的性能.Habibpour,Khalipour[8]提出k-means和k-近鄰混合算法并用于文本聚類,該算法與傳統(tǒng)k-means算法相比有更好的效率和聚類有效性.王春龍[9]提出一種基于隱含狄利克雷分布主題概率模型的初始聚類中心選擇算法,該算法選擇蘊(yùn)含在文本集中影響程度最大的前m個(gè)主題,并在這m個(gè)主題所在的維度上對文本集進(jìn)行初步聚類,從而找到聚類中心.任江濤[10]提出了一種面向文本聚類的改進(jìn)的K均算法,通過運(yùn)用特征選擇及降維、稀疏向量篩除,基于密度及散布的初始中心點(diǎn)搜索等方法進(jìn)行改進(jìn),該算法在聚類精度、穩(wěn)定性等方面都有提高.張文明[11]根據(jù)密度和最近鄰思想提出了一種優(yōu)化初始中心算法,得到了更好的應(yīng)用于文本聚類的DN-k-means算法.

2 k-means算法改進(jìn)

k-means算法對初始化中心非常敏感,隨機(jī)選擇的初始聚類中心很容易使聚類結(jié)果陷入局部最優(yōu)及受孤立點(diǎn)影響大等問題.本算法基于距離大的樣本點(diǎn)分到同一簇的可能性小[5]及方差最大的簇可分裂成兩個(gè)方差相對較小的簇,提出了初始化中心改進(jìn)算法.除此之外,還提出了孤立點(diǎn)排除的方法.本算法的思想是首先找出樣本點(diǎn)中距離最遠(yuǎn)的兩個(gè)點(diǎn)為初始中心點(diǎn),然后將其他樣本點(diǎn)劃分到距離最近的中心點(diǎn)所屬的簇中,根據(jù)生成的簇內(nèi)點(diǎn)的個(gè)數(shù)判定其對應(yīng)的初始聚類中心是否為孤立點(diǎn),最后根據(jù)簇內(nèi)方差挑選下一個(gè)需要進(jìn)行分裂的對象并按一定規(guī)則更新初始聚類中心,一直循環(huán)上面步驟直至聚類中心個(gè)數(shù)滿足要求.

2.1 初始聚類中心選取算法

設(shè)數(shù)據(jù)集X={x1,x2,x3,…xn},共有n個(gè)對象.d(xi,xj)(i,j∈{1,2…n})表示數(shù)據(jù)點(diǎn)xi,xj之間的歐氏距離,ci(i∈{1,2…k})為聚類中心,W為待分裂的數(shù)據(jù)對象,S為聚類中心個(gè)數(shù).

初始聚類中心選取算法如圖2所示.

圖2 初始聚類中心選取算法

2.2 改進(jìn)后的k-means算法

數(shù)據(jù)集X={x1,x2,x3,…xn},共有n個(gè)對象.Cold,iCold,i表示上一輪的第i個(gè)簇中心,Cnew,i表示本次計(jì)算得到的新的第i個(gè)簇中心.

算法描述如圖3所示.

圖3 改進(jìn)后的k-means算法

3 實(shí)驗(yàn)與分析

3.1 實(shí)驗(yàn)描述

實(shí)驗(yàn)中選取的數(shù)據(jù)集來自UCI數(shù)據(jù)庫中的Iris、Balance-Scale、Wine以及人為添加噪音后的Iris數(shù)據(jù)集.實(shí)驗(yàn)環(huán)境為:Inter(R)Core(TM)i3-2330M,4G內(nèi)存,250G硬盤,win7操作系統(tǒng).

為了驗(yàn)證算法的穩(wěn)定性、有效性,在Iris、Balance-Scale、Wine數(shù)據(jù)集下分別與原始k-means算法、文獻(xiàn)[3]、文獻(xiàn)[4]進(jìn)行了分析比較,其中傳統(tǒng)k-means算法的聚類結(jié)果是執(zhí)行10次的平均值.為了進(jìn)一步驗(yàn)證本算法在處理孤立點(diǎn)問題時(shí)的優(yōu)越性,在人為添加噪音后的Iris數(shù)據(jù)集上將本算法與其他算法做比較.各算法聚類結(jié)果的評價(jià)采用了聚類誤差平方和、聚類時(shí)間、聚類準(zhǔn)確率等評價(jià)方法.

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

3.2.1 UCI數(shù)據(jù)集的聚類結(jié)果與分析

表1、表2、表3分別是在UCI數(shù)據(jù)集下的本算法與文獻(xiàn)[3]、文獻(xiàn)[4]及k-means算法在準(zhǔn)確率、聚類誤差及時(shí)間上的比較結(jié)果.

表1 各算法在UCI數(shù)據(jù)集的準(zhǔn)確率比較

表2 各算法在UCI數(shù)據(jù)集的聚類誤差比較

表3 各算法在人造數(shù)據(jù)集的聚類時(shí)間比較

由表1中各算法在UCI數(shù)據(jù)集上的準(zhǔn)確率比較可見,由于傳統(tǒng)k-means算法是隨機(jī)選擇初始聚類中心且其對聚類結(jié)果影響較大,所以運(yùn)行10次的后的結(jié)果值具有不穩(wěn)定性從而導(dǎo)致平均準(zhǔn)確率比較低,本算法在UCI數(shù)據(jù)集上的準(zhǔn)確率明顯優(yōu)于文獻(xiàn)[3-4]的結(jié)果.由表2可知本算法的聚類誤差明顯優(yōu)于傳統(tǒng)k-means算法且不差于文獻(xiàn)[3-4]中的算法.表3中關(guān)于各算法聚類時(shí)間的比較表明,傳統(tǒng)k-means聚類算法的運(yùn)行時(shí)間最快,本算法速度略低于文獻(xiàn)[3-4]的結(jié)果.

3.2.2 人造數(shù)據(jù)集的聚類結(jié)果與分析

聚類的數(shù)據(jù)可能會存在孤立點(diǎn).由于隨機(jī)選取初始聚類中心可能會將孤立點(diǎn)選為初始聚類中心,這樣會使聚類結(jié)果產(chǎn)生很大的偏差.通過在人造噪音數(shù)據(jù)集下做了算法之間的對比試驗(yàn)并驗(yàn)證了本算法的穩(wěn)定性及有效性.

表4 各算法在人造數(shù)據(jù)集的準(zhǔn)確率比較

表5 各算法在人造數(shù)據(jù)集的聚類誤差比較

表6 各算法在人造數(shù)據(jù)集的聚類時(shí)間比較

由于本算法在處理孤立點(diǎn)問題時(shí)是將孤立點(diǎn)直接從樣本集中刪除,所以在處理含有噪音的Iris數(shù)據(jù)集時(shí)準(zhǔn)確率及聚類誤差與不含噪音時(shí)相比基本不變.由表4、5可知本算法比其他三種算法能夠更好處理孤立點(diǎn)問題.由表6可見本算法在時(shí)間上高于k-means算法、文獻(xiàn)[3-4],但是差距不是很明顯.

4 結(jié) 語

針對傳統(tǒng)k-means 算法初始聚類中心隨機(jī)選取帶來的聚類結(jié)果不穩(wěn)定,以及孤立點(diǎn)對聚類結(jié)果影響的問題,本文作者根據(jù)“距離大的樣本點(diǎn)分到同一簇的可能性小及方差最大的簇可分裂成兩個(gè)方差相對較小的簇”這一事實(shí),提出了一種優(yōu)化初始聚類中心的k-means 聚類算法.在UCI數(shù)據(jù)集以及帶有同比例噪音的人工數(shù)據(jù)集下的仿真實(shí)驗(yàn)表明,本算法與傳統(tǒng)k-means 算法以及其他兩種優(yōu)化初始中心算法相比,在準(zhǔn)確率及聚類誤差上有所提高.但是本算法初始化中心算法有點(diǎn)繁雜,在選取中心問題上耗時(shí)過多.在今后的工作中,將進(jìn)一步完善,試使其在各方面都優(yōu)于其他算法.

[1] Zhou A W,Yu Y F.The research about clustering algorithm of K-Means [J].Computer Technology and Development,2011,21(2):62-65.

[2] Lei X F,Xie K Q,Lin F,et al.An effidient clustering algorithm based on local optimality of K-Means [J].Journal of Software,2008,19(7):1683-1692.

[3] Duan G Q.Auto generation cloud optimization based on genetic algorithm [J].Computer and Digital Engineering,2015,43(3):379-382.

[4] Zhai D H,Yu J,Gao F,et al.k-means text clustering algorithm based oninitial cluster centers selection according to maximum distance [J].Application Research of Computers,2014,31(3):379-382.

[5] Xie J Y,Wang Y E.k-means Algorithm based on minimum deviation initialized clustering centers [J].Computer Engineering,2014,40(8):205-211.

[6] Liu J X,Zhu G H,Xi M.A k-means Algorithm based on the radius [J].Journal of Guilin University of Electronic Technology,2013,33(2):134-138.

[7] Habibpour R,Khalipour K.A new hybrid k-means and K-nearest-neighbor algorithms for text document clustering [J].International Journal of Academic Reserch Part A,2014,6(3):79-84.

[8] Wang C L,Zhang J X.Improved k-means algorithm based on latent Dirichlet allocation for text clustering [J].Journal of Computer Applications,2014,34(1):249-254.

[9] Ren J T,Sun J H.An effidient clustering algorithm based on local optimality of K-Means [J].Journal of Computer Applications,2006,26:73-75.

[10] Zhang W M,Wu J,Yuan X J.k-means text clustering algorithm based on density and nearestneighbor [J].Journal of Computer Applications,2010,30(7):1932-1935.

[11] Zhu M.Data mining [M].Hefei:University of Science and Technology of China Press,2002.

(責(zé)任編輯：包震宇,馮珍珍)

A k-means algorithm to optimize the initial cluster centers

ZHANG Mingwei, WU Haitao

(College of Information,Mechanical and Electrical Engineering,Shanghai Normal University,Shanghai 200234,China)

k-means algorithm,when its initial center is dependent on to be chosen randomly,can incur the local optimum of the clustering and the instability of the clustering results which may be affected much by isolated points.Aiming at solving those problems,a kind of k-means algorithm to be able to optimize initial cluster center and eliminate isolated points are put forward.Firstly,the farthest two points are chosen to join the cluster set.Then according to those two points,the original cluster is divided into two clusters.Find one of the clusters which has the largest variance and then split it according to certain rules until k centers are found.Isolated points elimination is also put forward in the process of choosing the initial center.The proposed k-means algorithm is tested on UCI data sets and on synthetic data sets with some proportional noises．The experimental results show that the proposed novel k-means algorithm can not only achieve a very promising and stable clustering,but also obtain a small influence of isolated points.

initialization center; k-means algorithm; isolated points elimination; clustering; UCI database

2015-09-14

吳海濤,中國上海市徐匯區(qū)桂林路100號,上海師范大學(xué)信息與機(jī)電工程學(xué)院,郵編:200234,E-mail:ht.wu@163.com

TP 301

A

1000-5137(2016)05-0599-05

10.3969/J.ISSN.1000-5137.2016.05.014