李光明，李 梁，張建剛

(重慶理工大學計算機科學與工程學院，重慶 400054)

0 引言

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

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

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

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

1.1 反向最近鄰(RNN)搜索

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

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

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

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

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

引理1 迭代的刪除反向最近鄰搜索的點不會影響其他點的最近鄰搜索。

引理2 每一個點都將被分配到一個集合中。

引理3 反向最近鄰搜索可以刪除離群點。

2 原始的K-means算法

2.1 算法步驟

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

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

2.2 算法不足

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

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

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

(2)算法步驟。根據(jù)引理1，第3步的時間復雜度會得到大大減小;并且離群點也會被檢測出來。詳細算法如下。

3 實驗結(jié)果

在這一節(jié)中，在此用F1度量［10］等評價標準來比較反向最近鄰搜索和傳統(tǒng)的初始化方法對聚類性能的影響。

3.1 數(shù)據(jù)集來源

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

表1 實驗數(shù)據(jù)集的特征

3.2 評估度量

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

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

3.3 實驗結(jié)果分析

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

表2 F1度量結(jié)果

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

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

4 結(jié)論

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

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

［2］張玉英，孟海東.數(shù)據(jù)挖掘技術(shù)中聚類方法的改進研究［J］.包頭鋼鐵學院學報，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］連鳳娜，吳錦林.一種改進的k-means聚類算法［J］.電腦與信息技術(shù)，2008，16(1):38-40

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

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

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

［8］魏大剛，唐昌杰.基于最優(yōu)投影和動態(tài)閾值的最近鄰搜索算法［J］.四川大學學報，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］劉潤濤，張佳佳.基于Voronoi圖的反向最近鄰查詢［J］.計算機工程，2009，35(19):81-82，85