顧洪博 (大慶石油學(xué)院計(jì)算機(jī)與信息技術(shù)學(xué)院,黑龍江 大慶 163318)
張繼懷 (大慶市讓胡路區(qū)政府,黑龍江 大慶 163712)
顧洪博 (大慶石油學(xué)院計(jì)算機(jī)與信息技術(shù)學(xué)院,黑龍江 大慶 163318)
張繼懷 (大慶市讓胡路區(qū)政府,黑龍江 大慶 163712)
介紹了在聚類中廣泛應(yīng)用的經(jīng)典k-均值算法,針對(duì)其隨機(jī)選擇初始質(zhì)心和易受孤立點(diǎn)的影響的不足,給出了一種改進(jìn)的k-均值算法。首先使用距離法移除孤立點(diǎn),然后采用鄰近吸收法對(duì)初始質(zhì)心的選擇上進(jìn)行了改進(jìn),并做了改進(jìn)前后的對(duì)比試驗(yàn)。試驗(yàn)結(jié)果表明,改進(jìn)后的算法比較穩(wěn)定、準(zhǔn)確,受孤立點(diǎn)和隨機(jī)選擇質(zhì)心的影響也有所降低。
k-均值算法;孤立點(diǎn);初始質(zhì)心;距離
聚類(Clustering)是按照某個(gè)特定標(biāo)準(zhǔn)將數(shù)據(jù)集劃分成不同個(gè)簇(Cluster)或類(Class)的過程,同一組內(nèi)的數(shù)據(jù)對(duì)象具有較高的相似度而不同組之間的數(shù)據(jù)對(duì)象相似度較低[1]。聚類的應(yīng)用越來越廣泛,在經(jīng)濟(jì)學(xué)、生物學(xué)、醫(yī)藥學(xué)、信息工程等許多領(lǐng)域都有著十分重要的應(yīng)用[2]。因此,對(duì)聚類的要求也越來越高,提出準(zhǔn)確且又高效的聚類算法刻不容緩。對(duì)于一個(gè)給定的n個(gè)數(shù)據(jù)對(duì)象的數(shù)據(jù)集,采用目標(biāo)函數(shù)最小化的策略,通過把數(shù)據(jù)分成k個(gè)組,每個(gè)組為一個(gè)簇,這就是劃分方法。最著名與最常用的劃分聚類算法是經(jīng)典k-均值(k-menas)算法[3],其基本思想描述如下:
1)隨機(jī)指定k個(gè)聚類中心(C1,C2,…,Ck);
2)對(duì)每一個(gè)樣本Xi,找到離它最近的聚類中心Ci,并將其分配到Ci所標(biāo)明類;
3)將每一個(gè)Cw移動(dòng)到其標(biāo)明的類的中心;
4)計(jì)算偏差D;
5)如果D值收斂,則返回(C1,C2,…,Ck)并終止算法;否則,返回步驟2)。
k-均值算法能對(duì)大型數(shù)據(jù)集進(jìn)行高效分類[4],其計(jì)算復(fù)雜性為O(tkmn),其中,t為迭代次數(shù),k為聚類數(shù),m為特征屬性數(shù),n為待分類的對(duì)象數(shù),通常k、m、t均小于n。但其也存在如下不足:通常會(huì)在獲得一個(gè)局部最優(yōu)值時(shí)終止;僅適合對(duì)數(shù)值型數(shù)據(jù)聚類,且算法的效果受孤立點(diǎn)和初始質(zhì)心的影響很大[5]。為此,筆者給出了一種改進(jìn)的k-均值算法。
經(jīng)典k-均值算法中沒有考慮孤立點(diǎn)。所謂孤立點(diǎn)都是基于距離的,是數(shù)據(jù)U集中到U中最近鄰居的距離最大的對(duì)象[6],換言之,數(shù)據(jù)集中與其最近鄰居的平均距離最大的對(duì)象。
針對(duì)經(jīng)典k-均值算法易受孤立點(diǎn)的影響這一問題,筆者基于距離法移除孤立點(diǎn),具體過程如下:首先掃描一次數(shù)據(jù)集,計(jì)算每一個(gè)數(shù)據(jù)對(duì)象與其臨近對(duì)象的距離,累加求其距離和,并計(jì)算出距離和均值。如果某個(gè)數(shù)據(jù)對(duì)象的距離和大于距離和均值,則視該點(diǎn)為孤立點(diǎn)。把這個(gè)對(duì)象從數(shù)據(jù)集中移除到孤立點(diǎn)集合中,重復(fù)直到所有孤立點(diǎn)都找到。最后得到新的數(shù)據(jù)集就是聚類的初始集合。
經(jīng)典k-均值算法隨機(jī)選取k個(gè)點(diǎn)作為初始聚類中心進(jìn)行操作。由于是隨機(jī)選取,則變化較大,初始點(diǎn)選取不同,獲得聚類的結(jié)果也不同[7]。并且聚類分析得到的聚類的準(zhǔn)確率也不一樣。對(duì)k-均值算法的初始聚類中心選擇方法——隨機(jī)法進(jìn)行改進(jìn),其依據(jù)是聚類過程中相同聚類中的對(duì)象是相似的,相異聚類中的對(duì)象是不相似的。因此提出了一種基于數(shù)據(jù)對(duì)象兩兩間的距離來動(dòng)態(tài)尋找并確定初始聚類中心的思路[8],具體過程如下:
首先整理移除孤立點(diǎn)后的數(shù)據(jù)集U,記錄數(shù)據(jù)個(gè)數(shù)y,令m=1。比較數(shù)據(jù)集中所有數(shù)據(jù)對(duì)象兩兩之間的距離。找出距離最近的2個(gè)數(shù)據(jù)對(duì)象形成集合Am;比較Am中每一個(gè)數(shù)據(jù)對(duì)象與數(shù)據(jù)對(duì)象集合U中每一個(gè)對(duì)象的距離,在U中找出與Am中最近的數(shù)據(jù)對(duì)象,優(yōu)先吸收到Am中,直到Am中的數(shù)據(jù)對(duì)象個(gè)數(shù)到達(dá)一定數(shù)值,然后令m=m+1。再?gòu)腢中找到對(duì)象兩兩間距離最近的2個(gè)數(shù)據(jù)對(duì)象構(gòu)成Am,重復(fù)上面的過程,直到形成k個(gè)對(duì)象集合。這些集合內(nèi)部的數(shù)據(jù)是相似的,而集合間是相異的。
可以看出,這種聚類方法同時(shí)滿足以下2個(gè)條件:①每個(gè)組至少包含一個(gè)數(shù)據(jù)對(duì)象;②每個(gè)數(shù)據(jù)對(duì)象必須屬于且僅屬于一個(gè)組。即數(shù)據(jù)對(duì)象Xi∈Ai,且U={{A1∪A2∪…∪Ak}∪A0},且Ai∩Aj=Φ。最后對(duì)k個(gè)對(duì)象集合分別進(jìn)行算術(shù)平均,形成k個(gè)初始聚類中心。
假設(shè)數(shù)據(jù)對(duì)象集合U有n個(gè)數(shù)據(jù)對(duì)象,要將其分為k類,|ε|≤1E-6。改進(jìn)算法的步驟如下:
輸入:聚類個(gè)數(shù)k,包含n個(gè)數(shù)據(jù)對(duì)象p個(gè)屬性的數(shù)據(jù)樣本集(1≤klt;n);
輸出:k個(gè)聚類和t個(gè)孤立點(diǎn)。
1)初始化。t=0,A0=Φ(0≤tlt;n);其中A0存放孤立點(diǎn)的集合;t為孤立點(diǎn)的個(gè)數(shù);y為移除孤立點(diǎn)后的數(shù)據(jù)對(duì)象個(gè)數(shù);
2)計(jì)算U內(nèi)所有數(shù)據(jù)對(duì)象Xi和Xj之間的距離d(Xi,Xj)(1≤i,j≤n),并計(jì)算U中每個(gè)數(shù)據(jù)對(duì)象的距離和Si與距離和均值H;
3)掃描U,比較每個(gè)數(shù)據(jù)點(diǎn)Xi的距離和Si與H的大小,如Sigt;H則Xi為孤立點(diǎn),t增1,并把Xi加入到A0,并從U中移除Xi;直到所有孤立點(diǎn)都找完,得到t,y=n-t;最后得到新的數(shù)據(jù)集U′=U-A0。循環(huán)t次,輸出孤立點(diǎn);
4)把U′作為新的數(shù)據(jù)中心,有y個(gè)數(shù)據(jù)對(duì)象,其中(1≤y≤n),m=1;
5)計(jì)算U中所有數(shù)據(jù)對(duì)象兩兩之間的距離d(Xi,Xj),找出滿足dmin(Xi,Xj)的2個(gè)數(shù)據(jù)對(duì)象Xi和Xj,令A(yù)m={Xi,Xj},Um=U-Am;
6)計(jì)算Am中每一個(gè)數(shù)據(jù)對(duì)象與U1中每一個(gè)樣本的距離,找出在Um中與Am中最近的數(shù)據(jù)對(duì)象Xa((1≤a≤y),令集合Am={Am,Xa},Um+1=Um-Am,重復(fù)此過程直到Am中的數(shù)據(jù)對(duì)象個(gè)數(shù)大于等于δ*n/k,(0lt;δ≤1),δ是經(jīng)驗(yàn)值;
7)若mlt;k,則m=m+1。再?gòu)腢2中找到樣本兩兩間距離最近的2個(gè)數(shù)據(jù)對(duì)象構(gòu)成Am,重復(fù)5)~7),直到形成k個(gè)對(duì)象集合;
8)對(duì)k個(gè)對(duì)象集合分別進(jìn)行算術(shù)平均,形成k個(gè)初始聚類中心Ci(1≤i≤k),計(jì)算ε;
9)進(jìn)行聚類分析,得到U={{A1∪A2∪…∪Ak}∪A0}。4試驗(yàn)分析
試驗(yàn)采用Iris數(shù)據(jù)集[8]。該數(shù)據(jù)集共有150條記錄,每個(gè)記錄有4個(gè)屬性:sepal length、sepal width、petal length和petal width。為了方便,只選取Iris (petal length、petal width) 作為試驗(yàn)對(duì)象,并隨機(jī)加入10個(gè)孤立點(diǎn):(1.5,61)、(21,0.21)、(0,0)、(48,0)、(0.4,91) 、(0,11)、(121,0.01)、(10,0)、(4.8,0)、(0.4,9.1)。從而U中n=150,k=3,t=10,p=2。試驗(yàn)在VC++6.0下進(jìn)行,試驗(yàn)結(jié)果見表1。
從上面的試驗(yàn)中可以看出,k1到k4的結(jié)果表明原始的k-均值算法可以比較準(zhǔn)確的分類。Iris數(shù)據(jù)集中數(shù)據(jù)是均勻分布,但有2類數(shù)據(jù)有交叉,所以分類效果有所下降。更主要的是因?yàn)殡S機(jī)選取的初始質(zhì)心,也會(huì)影響分類效果。4次試驗(yàn)4次初始質(zhì)心都不一樣,自然分類結(jié)果也就不同。另外,人為加入的孤立點(diǎn),明顯影響了原始的k-均值算法的執(zhí)行效果。對(duì)于把這些孤立點(diǎn)加到那一個(gè)類中,都會(huì)使這類的質(zhì)心有所偏移。因?yàn)槊總€(gè)質(zhì)心的選取都是經(jīng)過計(jì)算平均距離得到的,孤立點(diǎn)的加入會(huì)影響其所在類的質(zhì)心的確定。
表2 改進(jìn)前后的聚類結(jié)果
k5到k6是使用移除孤立點(diǎn)后使用原始k-均值算法得到的數(shù)據(jù)??梢钥闯?,分類效果好于有孤立點(diǎn)的。k7到k8是改進(jìn)初始質(zhì)心后使用原始的k-均值算法獲得的數(shù)據(jù)。試驗(yàn)表明,采用距離法尋找初始聚類中心,分類效果明顯好于原始的k-均值算法。去除了質(zhì)心的隨機(jī)性,分類結(jié)果大大提高。但此時(shí)還有孤立點(diǎn)存在的,所以類的穩(wěn)定性較差。
k9到k10是改進(jìn)算法得到的結(jié)果,分類的準(zhǔn)確率有所提高。這說明改進(jìn)后的算法先移除影響試驗(yàn)結(jié)果的孤立點(diǎn),然后根據(jù)計(jì)算后的初始質(zhì)心來尋找數(shù)據(jù),因而產(chǎn)生的初始聚類中心比較符合數(shù)據(jù)實(shí)際分布,也就更適用于對(duì)實(shí)際數(shù)據(jù)的聚類。
介紹了在聚類中廣泛應(yīng)用的經(jīng)典k-均值算法,針對(duì)其隨機(jī)選擇初始質(zhì)心和易受孤立點(diǎn)的影響的不足,給出了一種改進(jìn)的k-均值算法。試驗(yàn)表明,與傳統(tǒng)隨機(jī)選取初始聚類中心的方法相比,改進(jìn)后的方法可得到更好的劃分效果,尋找較為準(zhǔn)確的k個(gè)聚類中心。
[1]楊小兵.聚類分析中若干關(guān)鍵技術(shù)的研究[D].杭州:浙江大學(xué),2005.
[2]連鳳娜,吳錦林,唐琦.一種改進(jìn)的k-means聚類算法[J].電腦與信息技術(shù),2008,16(1):38~40.
[3]Marques J P,Written,Wu Y F.Trans Pattern Recognition Concepts,Methods and Applications[M]. 2nd ed.Beijing:Tsinghua University Press,2002.51~74.
[4]Huang Z.A fast clustering algorithm to cluster very large categorical data sets in data mining[EB/OL]. http://www.ece.northwestern.edu/~harsha/Clustering/sigmodfn.ps,2008-12-15.
[5]Sambasivam S,Theodosopoulos N.Advanced data clustering methods of mining Web documents[J].Issues in Informing Science and Information Technology,2006,(3):563~579.
[6]Sanjay Chawla,Pei Sun. SLOM: a new measure for local spatial outliers[J].Knowledge and Information Systems, 2006, (4) :412~429.
[7]尹珧人,王德廣.一種改進(jìn)的k-means聚類算法在入侵檢測(cè)中的應(yīng)用[J].科學(xué)技術(shù)與工程,2008,8(16):4701~4705.
[8]Sudipto G,Rajeev R,Kyuseok S.Cure:an effieient Elustering algorithm forlarge databases[J]. Information Systems,2001,261:35~58.
[編輯] 洪云飛
TP301.6
A
1673-1409(2009)01-N060-03
2009-01-07
黑龍江省教育廳科學(xué)技術(shù)研究項(xiàng)目(11521008);黑龍江省自然科學(xué)基金資助項(xiàng)目(F200603)。
顧洪博(1976-),女,1988年大學(xué)畢業(yè),碩士,講師,現(xiàn)主要從事數(shù)據(jù)庫應(yīng)用及數(shù)據(jù)挖掘方面的教學(xué)與研究工作。