基于孤立點(diǎn)和初始質(zhì)心選擇的k均值改進(jìn)算法

顧洪博 (大慶石油學(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-均值算法。

1 對(duì)孤立點(diǎn)的改進(jìn)——基于距離法

經(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ù)集就是聚類的初始集合。

2 對(duì)隨機(jī)選取初始聚類中心的改進(jìn)

經(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è)初始聚類中心。

3 改進(jìn)算法

假設(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ù)的聚類。

5 結(jié) 語

介紹了在聚類中廣泛應(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ù)庫(kù)應(yīng)用及數(shù)據(jù)挖掘方面的教學(xué)與研究工作。