一種對(duì)K-means算法的改進(jìn)

李光明，李 梁，張建剛

(重慶理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，重慶 400054)

0 引言

數(shù)據(jù)挖掘是指從大量數(shù)據(jù)中提取或“挖掘”知識(shí)［1］。聚類是一種無(wú)監(jiān)督學(xué)習(xí)，它把形式相似的對(duì)象聚集在一起。使得在同一簇中的對(duì)象之間相似度大，不同簇中的對(duì)象之間的相似度小。聚類算法已廣泛應(yīng)用在模式識(shí)別、圖像處理、過(guò)程優(yōu)化、配方設(shè)計(jì)等許多領(lǐng)域中，并取得了良好效果，受到了人們廣泛重視［2］。目前最流行的聚類算法之一就是K-means算法。

部分成果講述了對(duì)K均值初始聚類中心的研究。Duda etal［3］講述了用遞歸的方法初始化簇均值，此方法的另一種形式包括整個(gè)數(shù)據(jù)集的平均值，然后隨機(jī)的用微擾函數(shù)干擾它k次。張玉英［2］提出了基于密度和聚類對(duì)象方向的改進(jìn)算法。算法采取聚類對(duì)象分布密度方法來(lái)確定初始聚類中心，然后根據(jù)對(duì)象的聚類方向來(lái)發(fā)現(xiàn)任意形狀的簇。連鳳娜［4］提出了一種改進(jìn)的K-means算法，主要從數(shù)據(jù)預(yù)處理、初始聚類中心的選擇方面進(jìn)行了改進(jìn)。顧洪博［5］對(duì)近年來(lái)K-means算法的研究現(xiàn)狀與進(jìn)展進(jìn)行總結(jié)。對(duì)較有代表性的初始聚類中心改進(jìn)的算法，從思想、關(guān)鍵技術(shù)和優(yōu)缺點(diǎn)等方面進(jìn)行分析。

提出了一種基于反向最近鄰(RNN)搜索的K均值穩(wěn)定的初始化方案，這是一種與上述研究不同的方法。本方法的主要優(yōu)點(diǎn)是通過(guò)該方法得到的初始劃分比較接近最終解決方案，根據(jù)幾個(gè)評(píng)估標(biāo)準(zhǔn)K均值的性能也得到了顯著的提高。該方法的計(jì)算復(fù)雜度相對(duì)較低，并且樣本集中的離群點(diǎn)也可以通過(guò)該方法檢測(cè)出來(lái)。

1 反向最近鄰搜索初始化方案的基礎(chǔ)

1.1 反向最近鄰(RNN)搜索

最近鄰(NN)搜索是在一個(gè)度量空間中尋找最近點(diǎn)的問題。最近鄰查詢［6］(Nearest Neighbor Query，NNQ):給定一查詢點(diǎn)q和一個(gè)對(duì)象集O，找出O中距離q最近的對(duì)象o，即NNQ(q)={distance(q，o)≤distance(q，p)，o，p∈O};其中距離是采用歐氏距離或者曼哈頓距離。反向最近鄰搜索是最近鄰搜索的一個(gè)變種。最近鄰搜索返回距離查詢點(diǎn)最近的k個(gè)對(duì)象，而反向最近鄰則返回將查詢點(diǎn)作為其最近鄰的對(duì)象集［7］。反向最近鄰搜索［6］(Reverse Nearest Neighbor Search，RNNS):給定一查詢點(diǎn)q和一個(gè)對(duì)象集O，找出O中所有把q作為最近鄰的對(duì)象o，即RNNS(q)={distance(o，q)≤distance(o，p)，o，p∈O}。

圖1 反向最近鄰搜索的定義

因此，反向最近鄰(Reverse Nearest Neighbor，RNN)查詢［11］是在數(shù)據(jù)集中找到以查詢點(diǎn)為最近鄰的對(duì)象點(diǎn)，它可被應(yīng)用到知識(shí)發(fā)現(xiàn)、決策支持、設(shè)施定位、地理信息系統(tǒng)和多媒體數(shù)據(jù)庫(kù)等多種領(lǐng)域。反向最近鄰搜索是檢索給定的數(shù)據(jù)集，其最近鄰的點(diǎn)是一個(gè)給定的查詢點(diǎn)中的所有點(diǎn)。圖1所示的數(shù)據(jù)集包括4個(gè)點(diǎn)p1，p2，p3和p4。假設(shè)用歐氏距離來(lái)表示兩點(diǎn)之間的相似性，給定點(diǎn)q(實(shí)心點(diǎn))的反向最近鄰搜索的返回值是p1和p2。特別是p1是一個(gè)結(jié)果，因?yàn)樗莙的最近鄰點(diǎn)，p1是數(shù)據(jù)集中最接近q的點(diǎn)。重要的是要注意q的最鄰近搜索不一定是q的反向最近鄰搜索。那么反向最遠(yuǎn)鄰居(RFN)定義為如果查詢點(diǎn)q是p的最遠(yuǎn)鄰居之一，那點(diǎn)p就是查詢點(diǎn)q的反向最遠(yuǎn)鄰居。

1.2 反向最近鄰搜索的性質(zhì)

定義［9］(刪除操作):設(shè)p是集合D中指定要?jiǎng)h除的點(diǎn)，刪除數(shù)據(jù)集D中所有的點(diǎn)，把p的反向最近鄰搜索的點(diǎn)都放到數(shù)據(jù)集D中，重復(fù)上述過(guò)程。

引理1 迭代的刪除反向最近鄰搜索的點(diǎn)不會(huì)影響其他點(diǎn)的最近鄰搜索。

引理2 每一個(gè)點(diǎn)都將被分配到一個(gè)集合中。

引理3 反向最近鄰搜索可以刪除離群點(diǎn)。

2 原始的K-means算法

2.1 算法步驟

K均值算法是以k作為輸入?yún)?shù)，對(duì)n個(gè)連續(xù)值的對(duì)象樣本集進(jìn)行聚類的過(guò)程。初始從n個(gè)對(duì)象的樣本集中隨機(jī)的選取k各中心作為初始簇中心，然后將其余的數(shù)據(jù)點(diǎn)賦值到離它較近的簇中，然后再重新計(jì)算每個(gè)簇的均值，更新簇中心再計(jì)算剩余對(duì)象與各個(gè)簇均值的距離，將它指派到最相似的簇。不斷地重復(fù)這個(gè)過(guò)程，直到每個(gè)簇不再變化或準(zhǔn)則函數(shù)收斂為止。所以往往K均值的結(jié)果依賴于初始簇中心的選擇，當(dāng)初始簇中心不同時(shí)，聚類的結(jié)果也會(huì)不同。

原K均值算法偽代碼如下:輸入聚類個(gè)數(shù)k，以及包含n個(gè)數(shù)據(jù)對(duì)象的數(shù)據(jù)樣本集;隨機(jī)選取k個(gè)對(duì)象作為初始化k個(gè)聚類中心;設(shè)置迭代計(jì)數(shù)器t=0;while(r≠0)把樣本點(diǎn)分到距離最近的聚類中心所代表的簇內(nèi);計(jì)算聚類目標(biāo)函數(shù)J(t);r=J(t)-J(t-1);重新計(jì)算各個(gè)聚類中心;t=t+1;輸出聚類中心。

2.2 算法不足

算法對(duì)初始聚類中心以及樣本的輸入順序敏感，不同的初始聚類中心及不同的樣本輸入順序，導(dǎo)致不同的聚類結(jié)果。在用距離來(lái)衡量樣本數(shù)據(jù)間的相似度時(shí)，該算法不適合有大小差別很大的簇存在的數(shù)據(jù)集。原算法對(duì)于噪聲和離群點(diǎn)數(shù)據(jù)是敏感的［1］。

2.3 反向最近鄰搜索初始化聚類中心算法

(1)算法描述。首先初始化候選集(CS)，計(jì)算候選集中的每個(gè)點(diǎn)的反向最近鄰搜索，再按照每個(gè)點(diǎn)的反向最近鄰搜索集的對(duì)象個(gè)數(shù)的多少降序排列;然后選擇排序列表中的第一點(diǎn)作為候選質(zhì)心，并從列表中級(jí)聯(lián)的刪除選定點(diǎn)和它的反向最近鄰搜索集(根據(jù)刪除操作)。如果該列表不為空，重做選擇和刪除的操作。每次迭代后讓候選集是選定點(diǎn)的集合，重復(fù)上述過(guò)程，直到候選集中的對(duì)象數(shù)小于給定的U值(U一般是分簇?cái)?shù)K的3倍)。最后，在候選集(選定質(zhì)心點(diǎn)的集合)中按照反向最遠(yuǎn)鄰居(RFN)標(biāo)準(zhǔn)選定k個(gè)質(zhì)心。

(2)算法步驟。根據(jù)引理1，第3步的時(shí)間復(fù)雜度會(huì)得到大大減小;并且離群點(diǎn)也會(huì)被檢測(cè)出來(lái)。詳細(xì)算法如下。

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

在這一節(jié)中，在此用F1度量［10］等評(píng)價(jià)標(biāo)準(zhǔn)來(lái)比較反向最近鄰搜索和傳統(tǒng)的初始化方法對(duì)聚類性能的影響。

3.1 數(shù)據(jù)集來(lái)源

因?yàn)閷?duì)不同的數(shù)據(jù)集聚類的性能有很大的差異，實(shí)驗(yàn)比較了不同的初始化方案對(duì)不同的數(shù)據(jù)集的結(jié)果。試驗(yàn)數(shù)據(jù)用從UCI機(jī)器學(xué)習(xí)庫(kù)中下載的數(shù)據(jù)集。它們是“iris”，“wine”，“balance-scale”3個(gè)樣本集如表1所示。

表1 實(shí)驗(yàn)數(shù)據(jù)集的特征

3.2 評(píng)估度量

用F1度量度量方法來(lái)評(píng)估聚類的性能。用N，cnum’和cnum分別來(lái)表示給定數(shù)據(jù)集中實(shí)例的個(gè)數(shù)，實(shí)驗(yàn)得到簇的個(gè)數(shù)和原始數(shù)據(jù)集中簇的個(gè)數(shù)。因此，讓clk(k=1，2，…，cnum’)和classl(l=1，2，…，cnum)分別表示獲得的集群和實(shí)際的集群。并且每個(gè)實(shí)例的類標(biāo)號(hào)是di∈clk，i=1，…，|clk|，它表示的值為cj(j=1，2，…，cnum)。

F1度量措施已經(jīng)是用來(lái)衡量聚類質(zhì)量的方法，特別是聚類使用手動(dòng)標(biāo)記的時(shí)候。F1度量類似于精度度量措施(精度是在統(tǒng)計(jì)學(xué)習(xí)常用的方法)，定義F1度量如下:其中，

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

表2顯示了實(shí)驗(yàn)數(shù)據(jù)用傳統(tǒng)的初始化方法(InitRandomClusters，IRC)與改進(jìn)后的初始化方法即反向最近鄰搜索(RNN)的K均值聚類實(shí)驗(yàn)聚類結(jié)果性能的比較。

表2 F1度量結(jié)果

表3 改進(jìn)算法對(duì)Iris，Wine數(shù)據(jù)集的聚類結(jié)果

表3統(tǒng)計(jì)了Iris和Wine數(shù)據(jù)集分別用傳統(tǒng)初始化方法(IRC)，基于密度的初始化方法，基于兩階段最大最小距離法搜索出最佳初始聚類中心的方法和反向最近鄰搜索(RNN)方法的聚類結(jié)果精確度比較情況。明顯的可以看出反向最近鄰搜索方法初始化聚類中心得到的聚類結(jié)果的準(zhǔn)確率得到了明顯的提高。此外，K均值算法用反向最近鄰搜索比用其他方法運(yùn)行到收斂需要的迭代次數(shù)較少。

4 結(jié)論

K均值算法計(jì)算速度快，資源消耗小，對(duì)于處理大數(shù)據(jù)集是相對(duì)可伸縮的和高效的，但是初始聚類中心的確定會(huì)直接影響聚類結(jié)果，如何取得有效的初始聚類中心是算法的關(guān)鍵。在此利用反向最近鄰搜索提出了一種新的穩(wěn)定的初始化K均值聚類方法，在實(shí)驗(yàn)中對(duì)于不同數(shù)據(jù)集合，用該方法總是較好的選擇初始化中心數(shù)據(jù)。在實(shí)際應(yīng)用中，應(yīng)根據(jù)待聚類數(shù)據(jù)集的數(shù)據(jù)類型、聚類結(jié)構(gòu)選擇好的初始化簇中心的方法。在未來(lái)的應(yīng)用中，該方法將用于更多的數(shù)據(jù)集中。對(duì)于大型的數(shù)據(jù)集，需要使用更復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，例如M-tree結(jié)構(gòu)來(lái)加速反向最近鄰搜索，以更快取得聚類結(jié)果。

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

［2］張玉英，孟海東.數(shù)據(jù)挖掘技術(shù)中聚類方法的改進(jìn)研究［J］.包頭鋼鐵學(xué)院學(xué)報(bào)，2005，24(4):338-341

［3］DUDA R O，HART P E.Pattern Classification and Scene Analysis［M］.New York:John Wiley and Sons，1973

［4］連鳳娜，吳錦林.一種改進(jìn)的k-means聚類算法［J］.電腦與信息技術(shù)，2008，16(1):38-40

［5］顧洪博，張繼懷.聚類算法初始聚類中心的優(yōu)化［J］.西安工程大學(xué)學(xué)報(bào)，2010，24(2):222-226

［6］余海彥，郝忠孝.時(shí)空數(shù)據(jù)庫(kù)中基于TPR一樹的反向最近鄰查詢［J］.哈爾濱理工大學(xué)學(xué)報(bào)，2007，12(3):87-90

［7］王曉輝，曹澤文.移動(dòng)對(duì)象反向最近鄰查詢技術(shù)研究［J］.計(jì)算機(jī)工程，2010，36(20):66-67

［8］魏大剛，唐昌杰.基于最優(yōu)投影和動(dòng)態(tài)閾值的最近鄰搜索算法［J］.四川大學(xué)學(xué)報(bào)，2006，43(4):777-782

［9］XU J L，XU B W.Stable Initialization Scheme for K-Means Clustering［J］.Journal of Natural Sciences，2009，14(1):24-28

［10］JASON D M.RENNIE.Derivation of the F-Measure［Z］.http:∥mathworld.wolfram.com/HarmonicMean.html

［11］劉潤(rùn)濤，張佳佳.基于Voronoi圖的反向最近鄰查詢［J］.計(jì)算機(jī)工程，2009，35(19):81-82，85