顧洪博 (大慶石油學院計算機與信息技術學院，黑龍江 大慶 163318)

張繼懷 (大慶市讓胡路區(qū)政府，黑龍江 大慶 163712)

顧洪博 (大慶石油學院計算機與信息技術學院，黑龍江 大慶 163318)

張繼懷 (大慶市讓胡路區(qū)政府，黑龍江 大慶 163712)

介紹了在聚類中廣泛應用的經(jīng)典k-均值算法，針對其隨機選擇初始質心和易受孤立點的影響的不足，給出了一種改進的k-均值算法。首先使用距離法移除孤立點，然后采用鄰近吸收法對初始質心的選擇上進行了改進，并做了改進前后的對比試驗。試驗結果表明，改進后的算法比較穩(wěn)定、準確，受孤立點和隨機選擇質心的影響也有所降低。

k-均值算法；孤立點；初始質心；距離

聚類(Clustering)是按照某個特定標準將數(shù)據(jù)集劃分成不同個簇(Cluster)或類(Class)的過程，同一組內的數(shù)據(jù)對象具有較高的相似度而不同組之間的數(shù)據(jù)對象相似度較低[1]。聚類的應用越來越廣泛，在經(jīng)濟學、生物學、醫(yī)藥學、信息工程等許多領域都有著十分重要的應用[2]。因此，對聚類的要求也越來越高，提出準確且又高效的聚類算法刻不容緩。對于一個給定的n個數(shù)據(jù)對象的數(shù)據(jù)集，采用目標函數(shù)最小化的策略，通過把數(shù)據(jù)分成k個組，每個組為一個簇，這就是劃分方法。最著名與最常用的劃分聚類算法是經(jīng)典k-均值(k-menas)算法[3]，其基本思想描述如下：

1)隨機指定k個聚類中心(C1,C2,…,Ck)；

2)對每一個樣本Xi,找到離它最近的聚類中心Ci,并將其分配到Ci所標明類；

3)將每一個Cw移動到其標明的類的中心；

4)計算偏差D；

5)如果D值收斂，則返回(C1,C2,…,Ck)并終止算法；否則,返回步驟2)。

k-均值算法能對大型數(shù)據(jù)集進行高效分類[4]，其計算復雜性為O(tkmn)，其中，t為迭代次數(shù)，k為聚類數(shù)，m為特征屬性數(shù)，n為待分類的對象數(shù)，通常k、m、t均小于n。但其也存在如下不足：通常會在獲得一個局部最優(yōu)值時終止；僅適合對數(shù)值型數(shù)據(jù)聚類，且算法的效果受孤立點和初始質心的影響很大[5]。為此，筆者給出了一種改進的k-均值算法。

1 對孤立點的改進——基于距離法

經(jīng)典k-均值算法中沒有考慮孤立點。所謂孤立點都是基于距離的，是數(shù)據(jù)U集中到U中最近鄰居的距離最大的對象[6]，換言之，數(shù)據(jù)集中與其最近鄰居的平均距離最大的對象。

針對經(jīng)典k-均值算法易受孤立點的影響這一問題，筆者基于距離法移除孤立點，具體過程如下：首先掃描一次數(shù)據(jù)集，計算每一個數(shù)據(jù)對象與其臨近對象的距離，累加求其距離和，并計算出距離和均值。如果某個數(shù)據(jù)對象的距離和大于距離和均值，則視該點為孤立點。把這個對象從數(shù)據(jù)集中移除到孤立點集合中，重復直到所有孤立點都找到。最后得到新的數(shù)據(jù)集就是聚類的初始集合。

2 對隨機選取初始聚類中心的改進

經(jīng)典k-均值算法隨機選取k個點作為初始聚類中心進行操作。由于是隨機選取，則變化較大，初始點選取不同，獲得聚類的結果也不同[7]。并且聚類分析得到的聚類的準確率也不一樣。對k-均值算法的初始聚類中心選擇方法——隨機法進行改進，其依據(jù)是聚類過程中相同聚類中的對象是相似的，相異聚類中的對象是不相似的。因此提出了一種基于數(shù)據(jù)對象兩兩間的距離來動態(tài)尋找并確定初始聚類中心的思路[8]，具體過程如下：

首先整理移除孤立點后的數(shù)據(jù)集U，記錄數(shù)據(jù)個數(shù)y，令m=1。比較數(shù)據(jù)集中所有數(shù)據(jù)對象兩兩之間的距離。找出距離最近的2個數(shù)據(jù)對象形成集合Am；比較Am中每一個數(shù)據(jù)對象與數(shù)據(jù)對象集合U中每一個對象的距離，在U中找出與Am中最近的數(shù)據(jù)對象，優(yōu)先吸收到Am中，直到Am中的數(shù)據(jù)對象個數(shù)到達一定數(shù)值，然后令m=m+1。再從U中找到對象兩兩間距離最近的2個數(shù)據(jù)對象構成Am，重復上面的過程，直到形成k個對象集合。這些集合內部的數(shù)據(jù)是相似的，而集合間是相異的。

可以看出，這種聚類方法同時滿足以下2個條件：①每個組至少包含一個數(shù)據(jù)對象；②每個數(shù)據(jù)對象必須屬于且僅屬于一個組。即數(shù)據(jù)對象Xi∈Ai，且U={{A1∪A2∪…∪Ak}∪A0}，且Ai∩Aj=Φ。最后對k個對象集合分別進行算術平均，形成k個初始聚類中心。

3 改進算法

假設數(shù)據(jù)對象集合U有n個數(shù)據(jù)對象，要將其分為k類，|ε|≤1E-6。改進算法的步驟如下：

輸入：聚類個數(shù)k，包含n個數(shù)據(jù)對象p個屬性的數(shù)據(jù)樣本集(1≤klt;n)；

輸出：k個聚類和t個孤立點。

1)初始化。t=0，A0=Φ(0≤tlt;n)；其中A0存放孤立點的集合；t為孤立點的個數(shù)；y為移除孤立點后的數(shù)據(jù)對象個數(shù)；

2)計算U內所有數(shù)據(jù)對象Xi和Xj之間的距離d(Xi,Xj)(1≤i,j≤n)，并計算U中每個數(shù)據(jù)對象的距離和Si與距離和均值H；

3)掃描U，比較每個數(shù)據(jù)點Xi的距離和Si與H的大小，如Sigt;H則Xi為孤立點，t增1，并把Xi加入到A0，并從U中移除Xi；直到所有孤立點都找完，得到t，y=n-t；最后得到新的數(shù)據(jù)集U′=U-A0。循環(huán)t次，輸出孤立點；

4)把U′作為新的數(shù)據(jù)中心，有y個數(shù)據(jù)對象，其中(1≤y≤n)，m=1；

5)計算U中所有數(shù)據(jù)對象兩兩之間的距離d(Xi,Xj)，找出滿足dmin(Xi,Xj)的2個數(shù)據(jù)對象Xi和Xj，令Am={Xi,Xj}，Um=U-Am；

6)計算Am中每一個數(shù)據(jù)對象與U1中每一個樣本的距離，找出在Um中與Am中最近的數(shù)據(jù)對象Xa((1≤a≤y)，令集合Am={Am,Xa}，Um+1=Um-Am，重復此過程直到Am中的數(shù)據(jù)對象個數(shù)大于等于δ*n/k，(0lt;δ≤1)，δ是經(jīng)驗值；

7)若mlt;k，則m=m+1。再從U2中找到樣本兩兩間距離最近的2個數(shù)據(jù)對象構成Am，重復5)～7)，直到形成k個對象集合；

8)對k個對象集合分別進行算術平均，形成k個初始聚類中心Ci(1≤i≤k)，計算ε；

9)進行聚類分析，得到U={{A1∪A2∪…∪Ak}∪A0}。4試驗分析

試驗采用Iris數(shù)據(jù)集[8]。該數(shù)據(jù)集共有150條記錄，每個記錄有4個屬性：sepal length、sepal width、petal length和petal width。為了方便，只選取Iris (petal length、petal width) 作為試驗對象，并隨機加入10個孤立點：(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。試驗在VC++6.0下進行，試驗結果見表1。

從上面的試驗中可以看出，k1到k4的結果表明原始的k-均值算法可以比較準確的分類。Iris數(shù)據(jù)集中數(shù)據(jù)是均勻分布，但有2類數(shù)據(jù)有交叉，所以分類效果有所下降。更主要的是因為隨機選取的初始質心，也會影響分類效果。4次試驗4次初始質心都不一樣，自然分類結果也就不同。另外，人為加入的孤立點，明顯影響了原始的k-均值算法的執(zhí)行效果。對于把這些孤立點加到那一個類中，都會使這類的質心有所偏移。因為每個質心的選取都是經(jīng)過計算平均距離得到的，孤立點的加入會影響其所在類的質心的確定。

表2 改進前后的聚類結果

k5到k6是使用移除孤立點后使用原始k-均值算法得到的數(shù)據(jù)?？梢钥闯觯诸愋Ч糜谟泄铝Ⅻc的。k7到k8是改進初始質心后使用原始的k-均值算法獲得的數(shù)據(jù)。試驗表明，采用距離法尋找初始聚類中心，分類效果明顯好于原始的k-均值算法。去除了質心的隨機性，分類結果大大提高。但此時還有孤立點存在的，所以類的穩(wěn)定性較差。

k9到k10是改進算法得到的結果，分類的準確率有所提高。這說明改進后的算法先移除影響試驗結果的孤立點，然后根據(jù)計算后的初始質心來尋找數(shù)據(jù)，因而產(chǎn)生的初始聚類中心比較符合數(shù)據(jù)實際分布，也就更適用于對實際數(shù)據(jù)的聚類。

5 結 語

介紹了在聚類中廣泛應用的經(jīng)典k-均值算法，針對其隨機選擇初始質心和易受孤立點的影響的不足，給出了一種改進的k-均值算法。試驗表明，與傳統(tǒng)隨機選取初始聚類中心的方法相比，改進后的方法可得到更好的劃分效果，尋找較為準確的k個聚類中心。

[1]楊小兵.聚類分析中若干關鍵技術的研究[D].杭州:浙江大學,2005.

[2]連鳳娜,吳錦林,唐琦.一種改進的k-means聚類算法[J].電腦與信息技術,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]尹珧人,王德廣.一種改進的k-means聚類算法在入侵檢測中的應用[J].科學技術與工程,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

黑龍江省教育廳科學技術研究項目(11521008)；黑龍江省自然科學基金資助項目(F200603)。

顧洪博(1976-)，女，1988年大學畢業(yè)，碩士，講師，現(xiàn)主要從事數(shù)據(jù)庫應用及數(shù)據(jù)挖掘方面的教學與研究工作。