基于局部密度自適應度量的粗糙K-means聚類算法*

馬福民,逯瑞強,張騰飛

(1.南京財經大學信息工程學院,江蘇 南京 210023;2.南京郵電大學自動化學院,江蘇 南京 210023)

1 引言

聚類分析是根據“物以類聚”的原理將物理或者抽象對象所組成的集合進行分類的一種多元統計分析方法，己經成為數據挖掘領域一個非常重要的分支，被廣泛應用于機器學習、圖像分割等眾多領域。按照其特點，聚類算法大致可以分為五類：劃分方法、層次方法、密度方法、柵格方法和模型化方法[1]。K-means算法是最常見的劃分聚類方法之一，于1967年由Queen[2]首次提出，目前依然是眾多數據聚類分析任務首選的經典算法。加拿大學者Lingras[3]在使用K-means算法對Web數據進行挖掘分析時，針對傳統算法所存在的問題，引入了粗糙集理論上、下近似的思想，提出了粗糙K-means聚類算法，在計算數據對象的歸屬關系時，不再是簡單地用屬于或不屬于來表示，而是把確定屬于某一簇的對象歸屬到其相應的下近似集中，不確定是否屬于該簇的對象歸屬到其相應的邊界集中，因此，各個簇可以看作是由下近似集和邊界集兩部分組成。這種對聚類數據對象相對客觀的描述方法，在很大程度上提高了K-means聚類算法的精度。

粗糙K-means算法同其它任何的聚類分析算法一樣，算法的性能也依然受到初始參數、不確定性數據交叉重疊等因素的影響。為此，已經有很多學者陸續提出了進一步的改進算法，從聚類結構的角度來看，這些算法大致可以分為兩類[4]：

(1)粗糙K-means的擴展算法。這類方法沒有改變聚類過程中簇內的數據結構，僅僅是在原有算法的基礎上，對初始參數、聚類指標等進行優化。Peters[5]使用相對距離代替絕對距離，排除粗糙K-means算法中存在的受離群點干擾的問題，并且結合遺傳算法對粗糙K-means算法的初始參數做了優化[6]。

(2)粗糙K-means的衍生算法。這類算法可以認為是對粗糙K-means算法的本質提升，主要是針對均值迭代公式進行修正。聚類對象之間的近似度量得以進一步強化，如結合模糊集理論來構建對象關系。文獻[7]發現了在粗糙K-means聚類結果中存在僅有邊界集非空的情況，并對粗糙K-means均值公式做了修正，對粗糙權值重新進行了定義。文獻[8,9]介紹了粗糙模糊K-means聚類算法，這種方法使用了模糊隸屬度來反映簇間的差異性，提高了算法的精度。文獻[10]提出一種模糊粗糙K-means算法，對模糊隸屬度量進行了修訂，將下近似集中數據對象的隸屬度設置為1，僅對邊界區域不確定的對象采用模糊度量。

現有的粗糙K-means衍生算法在構造近似關系時大多僅關注單個數據對象與多個簇之間的差異性，而忽略了同一簇內對象之間的區別，在同一個近似區域中使用統一的權值來衡量不同對象在均值迭代過程中的影響程度。然而，在一個簇的內部，不同的數據對象點到均值中心的距離不同以及不同數據對象周圍的數據分布疏密程度等都將直接影響著聚類的結果。文獻[11]提出了一種對象點加權的方法，利用類似于方差統計的權值變形，區別簇內對象的差異。文獻[12]利用統計對象點鄰域內的距離總和來反映區域密度，提高了粗糙K-means算法的精度。文獻[13,14]認為密度是一種空間特征，反映了樣本屬性的綜合趨勢和拓撲的不規則構型。文獻[15]綜合考慮了距離和密度的混合度量，但對于密度的度量方法是采用簡單的鄰域范圍數據對象的數量統計，并沒有真正體現數據分布的疏密程度。這些方法利用各個空間特征構建新的近似關系，但是大都缺乏對適應性的考慮，不同的數據聚類可能對不同空間特征的敏感程度不同，基于空間特征的近似關系需要有綜合性的合理度量。

本文結合數據對象的不同分布對聚類結果的影響，提出一種局部密度自適應度量的方法，并給出基于局部密度自適應度量的粗糙K-means聚類算法，通過統計數據對象點與均值中心的距離以及鄰域內數據分布的疏密程度，來描述簇內數據對象分布的特點，靠近聚類中心且鄰域內數據對象聚集程度高的數據點，將得到更高的自適應迭代權值，從而加快聚類的收斂速度，并提高聚類的效果。最后，通過實例計算分析驗證算法的有效性。

2 粗糙K-means聚類算法

粗糙K-means聚類算法是將粗糙集理論與K-means算法相結合，將具有不確定歸屬關系的數據對象劃入邊界區域，并使用不同的權值度量來降低邊界區域數據對象在迭代過程中的影響。算法實際上是將同一簇分為了兩個部分，即具有確定歸屬關系的下近似區域和具有不確定歸屬關系的邊界區域，通過區分下近似集和邊界集中數據對象的不同貢獻，一定程度上提高了模糊邊界的處理精度。

2.1 傳統的粗糙K-means聚類算法

根據Lingras所提出的粗糙K-means算法，聚類對象的處理具有以下三個特征[16]：

(1) 聚類對象最多只能確定地屬于某一個簇的下近似集；

(2) 聚類對象若不能確定地屬于某一個簇的下近似集，可同時屬于多個簇的上近似集；

(3) 每個簇的下近似集是它的上近似集的子集。

粗糙K-means算法與傳統K-means算法最大的區別主要體現在特征(2)中，將這些不適合硬劃分的數據對象，歸屬到多個簇共有的邊界集中。

(1)

其中，wlow、wup分別為下近似集和上近似集的粗糙權值。

若每一個數據對象的類簇歸屬不再發生變化，說明算法已經收斂，算法終止；否則將新的Ci作為初始化中心，重新計算每一個數據對象到各個類簇中心的距離，并根據當前的距離判斷到各個類簇的歸屬關系。

由于數據對象到各個類簇的劃分是依據其到類簇的均值中心Ci的距離，因此，均值中心的位置直接關系到聚類對象近似關系的判斷。從上述的計算過程不難看出，中心均值的迭代公式是影響最終聚類結果的關鍵因素。另外，粗糙K-means算法將簇分為下近似集和邊界集兩個部分，當wup取值較小時，邊界對象在均值迭代計算過程中影響較小，降低了邊界區域數據對象的不確定性影響。

為評估粗糙K-means算法的收斂性以及聚類質量，Lingras給出了如公式(2)所示的評估函數：

(2)

2.2 粗糙K-means的衍生算法

粗糙K-means聚類的衍生算法很多，其中比較經典的是粗糙模糊K-means算法和模糊粗糙K-means算法。這兩種算法結合了模糊理論，以模糊隸屬度來表達聚類對象與各簇之間的從屬關系，表示對象以多大的程度歸入當前簇。模糊隸屬度的表達式如下所示[8]：

(3)

其中，μij表達對象Xj關于簇Ui的隸屬度，m是模糊指數，dij表示Xj到均值中心Ci的距離，且模糊隸屬度滿足：

(4)

模糊隸屬度是一種簇間關系的表達，通過轉化比較簇間距離的比例關系，來反映對象與各簇的關聯程度。

粗糙模糊K-means算法將模糊隸屬度作為對象聚類的決策標準，將對象歸入隸屬程度最大的簇的下近似集；或者當對象關于多個簇的隸屬程度相近時，則將對象歸入多個簇的上近似集。并且，算法對均值中心的迭代計算公式(1)進行了改進，如公式(5)所示[9]：

(5)

從均值計算公式(5)中可以看出，粗糙模糊K-means強調了對象在簇間和簇內的差異度，與采用固定權值的粗糙K-means算法相比，其聚類過程對邊界的處理更加平滑。

模糊粗糙K-means算法則從另外一個角度對模糊隸屬度量公式進行了改進，即凡是在下近似集中的對象，隸屬度全部賦值為1，表示分配在下近似集中的對象絕對屬于當前簇。模糊粗糙K-means算法還將均值中心的計算公式進行了簡化，省卻了粗糙權值，公式如下[10]：

(6)

其中，N′表示第i個簇當中所包含的對象個數。

粗糙模糊K-means和模糊粗糙K-means算法一定程度上體現了不同的數據對象在計算均值中心時的差異性，但更多的是從對整個簇的度量角度出發，針對同一簇內不同數據對象的不同分布及對聚類結果的影響考慮較少[17,18]，然而這些距離或局部密度分布卻對聚類結果有著不可忽略的影響。

3 基于局部密度自適應度量的聚類算法

3.1 局部密度自適應度量

從粗糙K-means及其衍生算法的實現原理，可以總結出粗糙K-means系列算法處理邊界模糊性問題的特點：

(1) 將帶有不確定歸屬關系的聚類對象放在多個簇的共有邊界中；

(2) 距離均值中心越遠的對象在迭代的過程中其權重越小；

(3) 聚類對象無論是在簇內還是簇間，對聚類迭代過程及結果均有不同的影響。

文獻[15]對比分析了粗糙K-means算法、粗糙模糊K-means算法、模糊粗糙K-means算法在一個簇中不同數據分布的權值分配，如圖1～圖3所示，其中wlow=0.7，wup=0.3，m=2。

Figure 1 Weight distribution of rough K-means圖1 粗糙K-means算法的權值分配

Figure 2 Weight distribution of rough fuzzy K-means圖2 粗糙模糊K-means算法的權值分配

Figure 3 Weight distribution of fuzzy rough K-means圖3 模糊粗糙K-means算法的權值分配

可以看出，粗糙K-means的權值顯然比較生硬，只是簡單地對同簇的對象權值二值化，并沒有體現出下近似集和邊界集內部的差異性；粗糙模糊K-means的權值則顯得比較平滑，并且在很大程度上降低了邊界區域對均值中心的影響，但是，由于照搬模糊隸屬度量的原理，使得下近似集當中的對象往往受到虛線部分的簇間影響；模糊粗糙K-means則對下近似集中的對象權重直接賦予1，表示下近似集確定屬于當前簇，但是，依然沒有考慮下近似集對象因分布不均衡而產生的不同影響。

從上述分析不難看出，數據對象的權重系數應當由均值中心向邊界降低，并且越靠近邊界，下降應越快。而且，權值的設置除了體現出與距離的關系，還應和簇內數據對象的聚集程度即空間分布有關。為了充分更好地描述數據對象的這種距離與空間分布，給出一種局部密度自適應度量的方法。

局部密度自適應度量的表達式如下：

(7)

其中，‖Xj-Ci‖表示對象Xj到所在簇的中心Ci的歐氏距離；|L(Xj)|ξ表示距離Xj為ξ的鄰域范圍內數據對象的個數。

公式(7)的第一部分體現了數據對象點到均值中心的距離對權重系數的影響，可以看做是點到點的不同位置特征分布；第二部分則體現了數據對象點鄰域范圍內局部的數據空間分布對權重系數的影響，可以看做是點到面的不同空間特征分布。整體而言，上述局部密度自適應度量的表達式較好地體現了簇內數據對象不同分布的空間特征，并較好地刻畫了不同空間分布的數據對象之間的差異性。

3.2 基于局部密度自適應度量的聚類算法設計

結合上一節局部密度自適應度量的方法，本節進一步給出一種基于局部密度自適應度量的粗糙K-means聚類算法RKM-LDAM(RoughK-means clustering based on Local Density Adaptive Measure)，算法流程如圖4所示。

Figure 4 Flow chart of algorithm圖4 算法流程圖

根據圖4所示的流程，RKM-LDAM算法的詳細描述如下所示：

算法1RKM-LDAM算法：基于局部密度自適應度量的粗糙K-means聚類。

輸入：U：U={Xj|j=1,…,N}，對象數為N的數據集；

k：聚類簇的個數。

輸出：將數據對象集合U劃分為k個簇。

Step1參數設置與初始化，包括：

Ci：聚類均值中心，且i=1,…,k；wlow、wup：分別為下近似集和上近似集的相對粗糙權值系數；Δ：距離判斷閾值；ξ：局部密度統計范圍閾值。

Step2?Xj∈U，計算Xj到各均值中心Ci的距離dij(i=1,…,k)，統計Xj附近ξ范圍內對象個數|L(Xj)|ξ；

(8)

Step5根據公式(1)檢測結果是否收斂，若不收斂，返回Step 2重新進行迭代聚類計算；否則，算法終止，輸出k個類簇。

就上述算法的時間復雜度而言，步驟2的復雜度為O(|U|2)，步驟3的復雜度為O(k|U|)，步驟4在最壞情況下為O(|U|2)，因此本文算法單次迭代計算的時間復雜度為O(|U|2)。

4 實驗仿真與分析

為了驗證算法有效性，采用本文基于密度自適應度量的粗糙K-means算法(RKM-LDAM)對多個UCI數據集進行聚類測試，并與典型的粗糙K-means算法RKM(RoughK-means)、模糊K-means算法FKM(FuzzyK-means)、粗糙模糊K-means算法RFKM(Rough FuzzyK-means)、模糊粗糙K-means算法FRKM(Fuzzy RoughK-means)在聚類精度和運行速度方面進行對比分析。

4.1 實驗環境

本文選取了4個UCI數據集作為實驗對象，分別是Iris、Wine、Fertility和Ionosphere。這4個UCI數據的一些信息和特征描述如下：

Iris是一個最常用的UCI數據集，包含了一些植物特征和鳶尾花分類之間的信息。該數據集包含150個樣本，每個樣本有4個條件屬性和1個決策屬性，其中決策屬性將數據分為3類。

Wine數據集主要是對同一區域的意大利葡萄酒的化學成分分析。數據集包含了178個樣本，每個樣本有13個屬性和1個決策屬性，其中決策屬性將數據分為3類。

Fertility記錄了生育能力和一些生理記錄之間的聯系。數據集包含了100個樣本，每個樣本有9個條件屬性和1個決策屬性，其中決策屬性將數據分為2類。

Ionosphere數據集通過分析電離層結構來判斷電離層的好壞。數據集包含了351個樣本，每個樣本有34個條件屬性和1個決策屬性，其中決策屬性將數據集分為2類。

實驗的計算機平臺使用英特爾酷睿i7(2.90 GHz)處理器，4 GB內存，操作系統是Windows 7 SP1。

4.2 聚類效果分析

為了比較算法聚類效果，實驗在聚類精度和運行速度兩個方面對各個算法進行對比分析。由于所選數據集均有較明確的分類決策，這里聚類精度是指對比原數據集的決策屬性值，被正確聚類的數據對象在數據集中所占的百分比，計算公式為：

(9)

為了便于比較不同算法的性能，實驗過程中對同一數據集使用統一的初始聚類均值中心，對算法中多個參數的設置采用經驗選擇，由于個別的算法會涉及不同的參數，經過測試，這些參數均選取較優的組合，這里暫不考慮最優參數的選取過程。

聚類參數的設置如表1所示。

Table 1 Parameter settings for clustering algorithms

為了更為客觀地對各算法進行對比分析，針對每一個數據集，每種算法均采用十字交叉驗證，表2和表3分別記錄了各個聚類算法平均的精度和運行時間，圖5和圖6直觀地反映了不同算法在各數據集中的聚類效果。

Table 2 Accuracy comparison of differentclustering algorithms on UCI data sets

Table 3 Computational time comparison ofdifferent clustering algorithms on UCI data sets

Figure 5 Accuracy comparison of different algorithms圖5 各算法聚類精度

Figure 6 Computational time of different algorithms圖6 各聚類算法運行時間

從表2和圖5不難看出，本文設計的基于密度自適應度量的粗糙K-means算法(RKM-LDAM)，有著不輸于其它算法的聚類性能，對Iris、Wine、Ionosphere三個數據集都達到了最高的聚類精度，尤其是對Iris和Wine兩個數據集的效果更好；僅僅對Fertility數據集的聚類精度稍低于采用模糊聚類FKM和RFKM方法的聚類結果。而由表3和圖6可以看出，除了Fertility數據集，本文所使用的RKM-LDAM算法的運行速度都比較快，其中對Ionosphere數據集的聚類收斂速度更為突出，相對5種算法的平均耗時下降了15.87%。

綜合上述結果可以看出，基于局部密度自適應度量的粗糙K-means算法(RKM-LDAM)，通過對聚類數據對象的空間特征進行局部密度自適應度量，更有利于提高聚類算法的性能，也驗證了數據對象點在簇內的不同分布會對聚類的結果產生一定的影響。

5 結束語

簇內數據對象與均值中心的不同距離、鄰近范圍內數據分布的疏密程度直接影響著聚類的精度與收斂速度。針對這一問題，本文提出了一種基于局部密度自適應度量的粗糙K-means聚類算法，在聚類的迭代計算過程中，通過對簇內數據對象與均值中心的距離以及局部密度的自適應度量，使得聚類結果簇內相似程度更高、收斂速度更快。通過對多個UCI數據集進行測試計算并與以往的多種算法進行對比分析，說明本文算法具有較好的聚類效果。

[1] Han Jia-wei, Kamber M. Data mining,concepts and techniques [M].3rd Edition. San Francisco:Morgan Kaufmann Publishers,2011.

[2] Queen M. Some methods for classification and analysis of multivariate observation[C]∥Proc of the 5th Berkeley Symposium on Mathematical Statistics and Probability,1967:218-297.

[3] Lingras P,West C.Interval set clustering of web users with roughk-means [J].Journal of Intelligent Information Systems,2004,23(1):5-16.

[4] Peters G,Crespo F,Lingras P,et al.Soft clustering-fuzzy and rough approaches and their extensions and derivatives [J].International Journal of Approximate Reasoning,2013,54(2):307-322.

[5] Peters G.Outliers in roughk-means clustering [C]∥Proc of International Conference on Pattern Recognition and Machine Intelligence,2005:702-707.

[6] Peters G,Lampart M.A partitive rough clustering algorithm [C]∥Proc of International Conference on Rough Sets and Current Trends in Computing,2006:657-666.

[7] Peters G.Some refinements of roughk-means clustering [J].Pattern Recognition,2006,39(8):1481-1491.

[8] Mitra S, Banka H, Pedrycz W.Rough fuzzy collaborative clustering [J].IEEE Transactions on Systems,Man,and Cybernetics,Part B:Cybernetics,2006,36(4):795-805.

[9] Mitra S,Banka H,Pedrycz W.Collaborative rough clustering [C]∥Proc of International Conference on Pattern Recognition and Machine Intelligence,2005:768-773.

[10] Hu Qing-hua,Yu Da-ren.An improved clustering algorithm for information granulation [C]∥Proc of International Conference on Fuzzy Systems and Knowledge Discovery,2005:494-504.

[11] Liu Bing,Xia Shi-xiong,Zhou Yong,et al.A sample-weighted possibilistic fuzzy clustering algorithm [J].Acta Electronica Sinica,2012,40(2):371-375.(in Chinese)

[12] Zheng Chao,Miao Duo-qian,Wang Rui-zhi.Improved roughK-means clustering algorithm with weight based on density [J].Computer Science,2009,36(3):220-222.(in Chinese)

[13] Liu Qi-liang,Deng Min,Shi Yan,et al.A density-based spatial clustering algorithm considering both spatial proximity and attribute similarity [J].Computers & Geosciences,2012,46:296-309.

[14] Azadeh A,Saberi M,Anvari M,et al.An adaptive network based fuzzy inference system-genetic algorithm clustering ensemble algorithm for performance assessment and improvement of conventional power plants [J].Expert Systems with Applications,2011,38(3):2224-2234.

[15] Zhang Teng-fei,Chen Long,Ma Fu-min.A modified roughc-means clustering algorithm based on hybrid imbalanced measure of distance and density [J].International Journal of Approximate Reasoning,2014,55(8):1805-1818.

[16] Lingras P,Peters G.Rough clustering [J].Data Mining and Knowledge Discovery,2011,1(1):64-72.

[17] Zhang Teng-fei,Chen Long,Li Yun.Roughk-means clustering based on unbalanced degree of cluster [J].Control and Decision,2013,28(10):1479-1484.(in Chinese)

[18] Zhang Teng-fei,Ma Fu-min.Improved rough k-means clustering algorithm based on weighted distance measure with Gaussian function [J].International Journal of Computer Mathematics,2017,94(4):663-675.

附中文參考文獻：

[11] 劉兵,夏士雄,周勇,等.基于樣本加權的可能性模糊聚類算法[J].電子學報,2012,40(2):371-375.

[12] 鄭超,苗奪謙,王睿智.基于密度加權的粗糙K-均值聚類改進算法[J].計算機科學,2009,36(3):220-222.

[17] 張騰飛,陳龍,李云.基于簇內不平衡度量的粗糙K-means聚類算法[J].控制與決策,2013,28(10):1479-1484.