基于相對距離的密度聚類算法
2009-01-01 00:00:00何孝金傅彥陳安龍
計算機應用研究 2009年4期
(電子科技大學 計算機科學與工程學院， 成都 610054)
摘 要：
首先介紹傳統距離計算方法在聚類應用中的不足，并針對這點提出一種基于權重向量的相對距離計算方法。在應用DBSCAN算法的基礎上，融入相對距離的計算及k-d樹的范圍查找的應用。該算法不僅能得到很好的聚類效果，而且消除了數據的度量單位對聚類結果的影響。
關鍵詞：相對距離； DBSCAN算法； 多維二進制搜索樹； 聚類
中圖分類號：TP301.6文獻標志碼：A
文章編號：1001-3695(2009)04-1335-03
Density of clustering algorithm based on relative distance
HE Xiao-jin， FU Yan， CHEN An-long
(School of Computer Science Engineering， University of Electronic Science Technology of China， Chengdu 610054， China)
Abstract:
This paper firstly introduced the shortage of the traditional method in calculating the deficiencies in the application of clustering. To address this shortcoming， put forward a relative distance calculation method based on the weighted vector. The algorithm was based on the DBSCAN algorithm， and integrated of the calculation of relative distance and the application of the scope finding of the k-d tree. The algorithm can not only be good clustering effect， and the elimination of the unit of measurement data on the impact of cluster results.
Key words：relative distance; DBSCAN algorithm; k-d tree; clustering
0 引言
聚類分析作為活躍的數據挖掘分支，專家們進行了大量的研究，提出了很多算法[1]。其中有以CURE算法[2]為代表的層次聚類，也有以DBSCAN算法[3]為代表的密度聚類。CURE算法將層次算法與劃分算法結合在一起來克服傾向于發現球形簇的缺陷，在計算簇間的距離時，它既不是用一個質心，也不是用所有的點，而是用一組代表點。DBSCAN算法是一種基于密度的聚類算法，算法具備挖掘任意形狀聚類及處理噪聲數據等方面的優勢性能。該算法的基本思想是：每個簇的內部點的密度比簇外點的密度要高得多，它定義為密度相連的最大對象集。但是現有的聚類算法多是在討論如何改善聚類結果，以及如何降低算法的時間復雜度，在任意兩個對象間的相似度度量上多采用現成的距離公式[4]（如歐幾里德距離）。這種距離表示法能很好地表示兩個對象間實際距離。理論上用它來進行聚類能得到很好的效果，但實際應用中的數據并不像想象中的那樣有規律。在實際數據中，不僅有數值還有單位，現有聚類算法都只是針對數據的數值進行聚類，對數據的度量單位沒有作任何討論。但實際上數據的度量單位對聚類結果有很大影響，假設要對某校學生的信息（包括身高、體重、年齡、考分等）進行聚類，那么身高應該是取米還是厘米來做單位？其數據相差100倍，用通常的算法聚類結果具有天壤之別 。
本文將針對現有聚類算法在這個問題上的不足，提出一種根據輸入數據自動計算各維度上的權值的方法；然后對每一維的數據都乘上其相應權值，用新生成的數據對象進行聚類。這樣算出的兩個對象間的距離不是其實際距離，可稱之為相對距離。用此距離進行聚類同樣能得到很好的效果，并且不受數據度量單位的影響。
1 基于權值向量的相對距離
1.1 數據矩陣與相異度
設聚類問題中有n個對象：xi(i=1，2，…，n)，對每個對象選擇了p個變量，用間隔尺度測定后，第i個對象的第j個變量的觀測值用xij表示，則這n個對象的所有p個變量的觀測值可以看成是如下的n×p矩陣[4]：
X=x11x12…x1p
x21x22…x2p
xn1xn2…xnp
（1）
式(1)常被稱為數據矩陣，它是對象—變量結構的數據表達方式。其中第i個對象的p個變量的觀測值可以記為向量：
xi=(xi1，xi2，…，xip)（2）
聚類中為了求兩個對象之間的相異度，需要定義一些聚類統計量，用做聚類分析的數量指標，從而可以定量地進行聚類分析。計算對象間的距離是經常采用的求相異度的方法。可以采用多種形式的距離來度量它們的相異度，最常用的是歐幾里德距離：
d2(xi，xj)=‖xi-xj‖2=(∑pk=1|xik-xjk|2)1/2（3）
1.2 維度權值的計算方法
設n個對象中第i維上的數據為
xi=(xij，x1i，…，xni)T（4）
則第i維的平均值為
Ei=1/n∑nj=1xji（5）
第i維的均方差為
δi=1/(n-1)∑nj=1(xji-Ei)2（6）
用第i維上每個值與平均值的偏差來進行聚類可得到理想的效果。因此對每個值的變換如下：
x′ji=xji-Ei/δi(j=1，2，…，n)（7）
但上式中對同一維的值做相同的差實際就是將所有的對象在該維上進行平移，對聚類結果并無影響，故式（7）可簡化為
x′ji=xji/δi(j=1，2，…，n)（8）
定理1 若對第i維的數據向量xi同時乘上一個常數k，由式（8）計算出的xji′不會產生變化。
證明 對xi乘上一個常數k，則kxi=(kx1i，kx1i，…，kxni)T，由式（5）第i維的平均值為1/n∑nj=1kxji=kEi，由式（6）第i維的均方差為1/n-1∑nj=1(kxji-kEi)2=kδi，將其代入式（8）x′ij=kxji/kδi=xji/δi=x′ji(j=1，2，…，n)。定理得證。
由定理1可知如果對第i維數據進行同時擴大（或縮小），由式（8）變換得到的新數據不會發生變化，也就是說新的數據將與第i維的度量單位無關。
式（8）實際上是對一維上的所有點乘上一個相同的數，也就是本文要求的維度權值，設第i維的維度權值為wi，則
wi=1/δi（9）
由式（9）計算出各維度上的維度權值，組成維度權值向量為
W=(w1，w2，…，wp)（10）
求出維度權值向量之后就可以對這n個對象作一個相對變換：
Xn=X×WT（11）
由此得到的一個新的n×p矩陣Xn。其中的任意兩個對象之間的距離可由式（3）計算得出。這樣計算出來的距離并不是兩個對象之間的實際距離，而只是適合于本文的聚類的一種相對距離。
1.3 數據取樣
上述的維度權值計算方法需要訪問數據集中的每一個對象，這樣固然可以得到準確的結果，但會大大增加計算的時間，因此本文采用隨機取樣的數據來代替整個數據集。取樣數據庫應能夠有效代表原數據庫，若取樣率太低，必然會丟失原數據庫的某些特質，導致聚類效果失真。取樣率必須不小于某一閾值。本文選取Chernoff bounds確定的最小取樣數據量[5]：
minNs=f/N+N/|unum|log(1/σ)+N/|unum|(log(1/σ))2+2f|unum|log(1/σ)（12）
其中：N為整個數據庫包含的數據量；unum 為最小類包含的數據量。式(8)表示當取樣數據量不少于minNs時，unum中被取到f|unum|個數據的概率不低于σ，0≤f≤1。
2 基于相對距離的DBSCAN算法
2.1 k-d樹的范圍查找
k-d樹又稱為多維二進制搜索樹[6]，其中k表示搜索空間的維數。假設節點P的k個維為K0(P)，…，Kk-1(P)，兩個指針為LOSON(P)、HISON(P)，指示器為DISC(P)，則k-d樹的定義為：對于k-d樹中的任一節點P，假設DISC(P)為j，對于LOSON(P)中的任何節點Q，總有Kj(Q)
有關k-d樹的描述（如插入、刪除等）在文獻[6]中有詳細介紹，但該文對范圍查找算法的描述并不清楚。本文采用DBSCAN算法進行聚類，在該算法中需要查找一個點的鄰域半徑中所包含的點的數目，這個操作也正是k-d樹的范圍查找。下面的算法描述查找以P點為中心，R為半徑的區域中的點的集合：
算法SearchRigon(P，R)
輸入：P（查找的中心點）和R（要查找的鄰域半徑）
輸出：set（在范圍中的點的集合）
begin
for i:=0 to k-1 do
B_max[i]:= Ki(P)+R；
B_min[i]:= Ki(P)-R；
Stack.push(root)
while Stack.empty=1 do
Q:=Stack.pop()；
j:= DISC(Q)；
if Kj(Q) Stack.push(HISON(Q))； else if Kj(Q)>B_max[j] then Stack.push(LOSON(Q))； else D:= distance(P，Q)； Stack.push(HISON(Q))； Stack.push(LOSON(Q))； if D≤R then add(Q，set)； return set； end 其中:k為樹的維度；B_max和B_min為所查詢的點各維的上下界；Ki(P)為P在i維上的值；Stack為用于遍歷樹的臨時存放節點的棧；Q為當前訪問節點。 2.2 算法描述 DBSCAN算法能夠識別各種復雜形狀的聚類，并能有效排除噪聲的干擾，并且聚類結果不受輸入順序的影響。本文采用基于相對距離的DBSCAN算法進行聚類，并應用k-d樹減小時間復雜度。 具體算法描述如下： a）對輸入的對象集按第1章所描述的方法計算維度權值向量，并按式（11）變換得出新的對象集。 b）從新的對象集中隨機選一個點P。 c）找到與P點密度可達的所有點，根據輸入參數ε和 minPts（ε為給定半徑對象，minPts為核心對象至少包含的點數，此過程用k-d樹的范圍查找輔助完成）。 d）如果P是一個核心對象，則形成一個新簇，然后反復尋找從這些核心對象直接密度可達的對象，這個過程可能涉及一些密度可達簇的合并。當沒有新的對象可以被添加到任何簇時，該過程終止。 e）如果P是一個邊界點，沒有其他點對其密度可達，那么跳過P點。 f）重復上述過程至到所有點訪問完畢。 g）用式（11）的逆運算將所有的對象還原成為原來的對象，并標志它們所在的類別，完成聚類。 2.3 算法分析 上述算法與其他算法相比最大的優勢就是聚類結果不受某一維數據的異常而有所影響。比如將某一維的數據同時縮小100或1 000倍，對其他算法來說結果自會發生巨大的變化，而使用上述算法所得到的結果卻不會發生任何變化，這一點將會在第3章予以證明。 算法的時間復雜度：算法步驟 a）中計算Ei需掃描一遍數據，計算δi也需掃描一遍數據，所需時間為2n，時間復雜度為O(n)；DBSCAN算法在應用k-d樹的情況下時間復雜度為O(n log n)[3]。因此總的算法時間復雜度為O(n log n)。 3 仿真實驗 本文的測試數據集是仿照Dr.JSrg Sander提供的DBSCAN中Database2生成的數據集(DB2)[7]，數據量為1 300（圖1）。將采用傳統距離公式的DBSCAN算法與采用本文描述的相對距離的DBSCAN算法進行比較： 第一次，對原始數據進行聚類，兩者得到相同結果。 第二次，將所有點的y值縮小10倍，兩者得出截然不同的結果，見圖2和3（其中的縱坐標有一定放大，為方便觀看效果，對結果并無影響）。算法的參數取值為：取樣率=30%，Eps=5，minPts=4。 第三次，將所有點的y值縮小100倍，采用相對距離的聚類結果依然沒有變化。本文使用的聚類有效性指標函數Q(C)取以下形式[8]： Q(C)=1/M(scat(C)+sep(c))（3） 其中：scat(C)衡量的是簇內的緊湊度；sep(C)對應的是簇間的分離度。Q(C)的值越小，表示聚類的效果越好。表1描述了三次聚類實驗的結果對比。 表1 采用傳統距離公式的結果與采用本文描述的相對距離的結果對比 y值縮小倍數采用傳統距離的Q(C)值采用相對距離的Q(C)值 10.1370.137 100.6570.137 1000.8200.137 從表1中可以看出：對原始數據即數據較規范的情況下，采用相對距離能得到與傳統距離相同的令人滿意的結果；但對將數據的一維進行縮放之后的維度之間差異較大的數據，采用傳統距離則不能得到期望的結果，而采用相對距離則能得出較好的結果。這便是采用相對距離的優勢。 4 結束語 聚類分析是數據挖掘中廣為研究的課題之一。本文針對傳統距離計算方法在聚類算法中的局限性，創新性地提出一種計算相對距離的方法，有效地解決了數據度量單位對聚類效果的影響問題。本文的實驗結果證明了這一點。同時本文針對DBSCAN算法中的范圍查找，提出應用k-d樹來減小時間復雜度。但是密度聚類還是有對參數過分依賴的問題，如何解決這個問題仍有待進一步研究。 參考文獻: [1]BERKHIN P. Survey of clustering data mining techniques[R]. San Jose: Accrue Software， 2002：6-23. [2]GUHA S， RASTOGI R， SHIM K.CURE: an efficient clustering algorithm for large databases[C]//Proc of ACM SIGMOD International Conference on Management of Data. New York: ACM Press， 1998:73-84. [3]ESTER M， KRIEGEL H P， SANDER J， et al. A density-based algorithm for discovering clusters in large spatial databases[C]//Proc of the 2nd Intl Conference on Knowledge Discovery and Data Mining. Portland:AAAI Press，1996:226-231. [4]楊小兵．聚類分析中若干關鍵技術的研究[D]．杭州：浙江大學，2005:20-22． [5]周水庚，周傲英，金文，等. FDBSCAN:一種快速DBSCAN算法[J].軟件學報，2000，11(6):735-744. [6]BENTLEY J L. Multidimensional binary search trees used for associative searching[J]. Communications of the ACM，1975，18（9）：509-517． [7]陳卓，孟慶春，魏振鋼，等.一種基于網格和密度凝聚點的快速聚類算法[J].哈爾濱工業大學學報，2005，37(12):1654-1657. [8]陳黎飛，姜青山，王聲瑞. 基于層次劃分的最佳聚類數確定方法[J].軟件學報， 2008，19(1):62-72.
