基于鄰域歸屬信息混合度量的粗糙K-Means 算法

孫靜勇，馬福民

（南京財經大學信息工程學院，南京 210023）

0 概述

聚類算法根據數據之間的相似度對數據進行劃分，使得簇內數據相似度高，而簇間數據相似度低。現有的聚類技術主要分為密度聚類、劃分聚類、層次聚類、模型聚類以及網格聚類［1］。K-Means 算法［2］作為劃分聚類算法之一，使用類簇中心點來代表每個類簇，具有簡單、高效的特征，是當前研究的熱門聚類技術［3-4］。

為解決不確定信息的劃分問題，文獻［5］將模糊集引入K-Means 算法，提出了模糊K-Means（Fuzzy K-Means，FKM）［6］聚類算法，在處理數據對象時采用模糊度量。文獻［7-8］將粗糙集理論融入K-Means算法，提出了粗糙K-Means（Rough K-Means，RKM）［9］聚類算法，解決了傳統K-Means 算法不能處理粗糙不可分辨信息的問題。文獻［10-12］將粗糙聚類算法應用于林業、醫學成像、Web 挖掘、超級市場和交通工程等不同領域。文獻［13］使用相對距離作為粗糙K-Means 算法相似性度量的標準，減少了邊界區域離群數據點的影響。文獻［14］對粗糙K-Means 算法中上下近似權重問題進行了完善。文獻［15］為驗證粗糙聚類算法的有效性，對粗糙聚類算法和傳統聚類算法進行了更進一步的對比討論。

粗糙集和模糊集都是處理不確定信息的有效手段，兩者之間具有一定的互補性。文獻［16］結合了粗糙集與模糊集，提出粗糙模糊K-Means（Rough-Fuzzy K-Means，RFKM）聚類算法，利用模糊隸屬度對數據點進行加權度量，使得算法在處理不確定信息時更加合理、準確。文獻［17］提出的模糊粗糙KMeans（Fuzzy-Rough K-Means，FRKM）則認為處于類簇下近似中的數據點是確定屬于該類簇的，只有處于邊界區域的數據點與類簇具有不確定關系。文獻［18］結合數據的空間分布對邊界交叉區域的數據進行局部模糊度量，提出了基于邊界區域局部模糊增強的πRKM 算法（BF-πRKM），提高了算法處理邊界區域交叉嚴重數據的準確性。

通過加入粗糙集和模糊集，使得K-Means 算法在對邊界區域的數據的處理更加合理、精確，但卻忽略了數據局部密度對聚類結果的影響。文獻［19］通過計算數據點鄰域內的緊湊度來表示數據點的局部密度，使得局部密度越大的數據點獲得的權值越高。文獻［20］使用數據差異性度量數據的空間分布。文獻［21-22］通過衡量數據點與類簇中心的距離，利用合適的映射函數使得距離類簇中心越近的數據點獲得的權重越大。文獻［23-25］結合數據點分布屬性，對聚類算法的初始中心選取進行了改進。文獻［26］結合距離與密度綜合考慮了簇內不平衡問題，使用距離與密度進行綜合度量，使得距離類簇中心越近且密度越高的數據點獲得的權重越大。

上述算法雖考慮了簇內簇間的數據分布情況，卻忽略了處于邊界區域的數據點與各類簇中心的距離往往相差很小，而且相近數據點的鄰域密度也差別不大，難以依據距離、密度進一步區分數據對象更偏向于哪個類簇。本文通過局部密度與鄰域歸屬信息來描述數據點的空間分布，提出一種基于鄰域歸屬信息混合度量的粗糙K-Means 算法（RKM-DN）。對數據點空間分布的衡量參考了數據對象的局部密度與鄰域歸屬信息，下近似集中的數據通過局部密度衡量簇內不平衡分布，使得類簇中心盡可能處于簇內密度最高的區域，邊界區域的數據通過其鄰域歸屬信息衡量數據對象與類簇之間的相似性，以減少邊界數據對類簇中心的位置的敏感度，提高算法對交叉重疊區域數據的劃分能力。

1 相關聚類算法

1.1 粗糙K-Means 算法

RKM 聚類算法將交叉重疊區域中難以劃分的數據點歸為類簇的邊界區域，在數據點劃分的過程中，需要滿足以下性質：

1）數據對象最多屬于某一類簇的下近似。

2）若數據對象不屬于任一類簇的下近似，則該數據對象屬于兩個及以上類簇的上近似。

3）若一個數據對象屬于某一類簇的下近似，則該數據對象也屬于該類簇的上近似。

在粗糙K-Means 算法中，待處理數據集D={xk|k=1，2，…，N}，其中，N為數據集中數據的個數，邊域權值、下近似權值分別為wl、wb，wl+wb=1為類簇i的上近似為類簇i的下近似為類簇i的邊域，vi為類簇i的中心點，算法根據數據對象到各類簇中心的距離將其劃分到下近似或者邊域中［9］。在每次迭代中，類簇中心計算公式如下［9］：

由式（1）可見，粗糙K-Means 算法在對類簇中心點進行計算時，將邊界區域的數據整體賦予一個較小的權重wb，減少了邊界不確定信息對類簇中心的影響。

1.2 改進的粗糙K-Means 算法

改進的粗糙K-Means 算法結合模糊集與粗糙集，使得粗糙K-Means 算法在對數據進行劃分上下近似集的同時，還以模糊隸屬度來衡量數據點對某一類簇的歸屬度。該算法在計算類簇中心時不僅考慮了類簇邊界區域的數據點的計算，還兼顧了簇內數據對象分布不均的情況，計算公式如下［16］：

其中，K為聚類的個數，dki為數據點xk與類簇i的中心點的距離，m為模糊指數。

加入了模糊隸屬度的粗糙模糊K-Means（RFKM）算法［16］的類簇中心計算公式如下：

模糊粗糙K-Means 算法則認為處于類簇下近似的數據點是確定屬于該類簇的數據點，因此其權值均為1。而處于類簇邊域的數據點是不確定是否屬于該類簇的數據，其權值使用模糊隸屬度計算，模糊粗糙K-Means 算法的數據點權值計算公式如下［17］：

模糊粗糙K-Means（FRKM）算法對類簇中心的計算進行了改進，在計算類簇中心時不再需要人為設置上下近似參數，計算公式如下［17］：

由式（3）和式（5）可見，粗糙模糊K-Means 算法與模糊粗糙K-Means 算法在處理邊界數據時使用模糊隸屬度來衡量數據點之間的差異。

2 基于鄰域歸屬信息混合度量的RKM 算法

2.1 局部密度和鄰域歸屬信息度量

粗糙聚類算法對邊界區域數據的衡量依賴數據點與類簇中心之間的距離，導致算法對邊界區域的數據劃分效果不佳，且邊界數據對類簇中心的位置較為敏感。根據“簇內數據相似，簇間數據相異”的原則，數據點與其鄰域數據對象具有較高的相似性。在沒有先驗知識的情況下，數據點的鄰域數據包含許多信息。結合粗糙集屬性對數據點鄰域信息進行分析，可以得出以下特征：

1）若數據點xk的鄰域數據均屬于類簇i的下近似，則數據點xk屬于類簇i的概率非常高。

2）若數據點xk的鄰域數據既有屬于類簇i的下近似，又有屬于類簇i的邊域，則屬于類簇i的下近似的鄰域數據占比越高，數據點xk屬于類簇i的概率越大。

3）若數據點xk的鄰域數據沒有屬于類簇i的上近似，則數據點xk屬于類簇i的概率非常低（說明xk幾乎不可能屬于類簇i）。

如圖1 所示，數據點x1與x2處于類簇交叉非常嚴重的邊界區域，x1與x2同時屬于類簇1、類簇2 與類簇3 的邊域。通過觀察x1的鄰域歸屬信息可以發現，x1的鄰域數據點多數分布在類簇1 中，少數分布在類簇3 中，僅有數據點本身處于類簇2 的邊域中。因此，數據點x1屬于類簇1 的概率要遠大于類簇3 與類簇2。同理，數據點x2的鄰域數據點多數分布在類簇2 中，少數分布在類簇3 中，僅有數據點本身處于類簇1 的邊域。因此，數據點x2屬于類簇2 的概率要遠大于類簇3 與類簇1。

圖1 鄰域歸屬信息度量示意圖Fig.1 Schematic diagram of neighborhood ownership information measure

由以上分析可以發現，即使是屬于多個類簇的邊界區域，數據點屬于各類簇的可能性也不一致。在以上的數據分布中，使用距離或者密度對其進行衡量難以達到區分數據的目的，尤其是當數據點處于邊界交叉嚴重的區域。通過觀察數據點鄰域內的數據分布情況，使用數據點的鄰域數據點歸屬信息來衡量該數據點與類簇的相似性可以對數據的劃分給予指導作用，從而提高算法的準確度。

如圖2 所示，數據點x1與x2處于類簇1 的下近似，且x1與x2的鄰域數據點均屬于類簇1 的下近似，此時僅參考鄰域歸屬信息難以區分x1與x2對于類簇中心的重要性。但類簇中心的位置應盡可能處于簇內密度最大的區域，因此，局部密度越高的數據點對類簇中心的貢獻應越大。

圖2 鄰域緊湊示意圖Fig.2 Schematic diagram of neighborhood compact

由圖2 可以看出，數據點x1的鄰域數據點非常緊湊，大多圍繞在x1的周圍，而數據點x2的鄰域數據點較為分散且與x2相距較遠。很明顯，數據點x1對于類簇中心的貢獻更大。

根據局部密度與鄰域歸屬信息度量，定義以下概念：

其中，|L(xk)|ξ代表xk的半徑為ξ的鄰域代表在數據點xk的鄰域|L(xk)|ξ內屬于類簇i的上近似的數據點個數代表在數據點xk的鄰域|L(xk)|ξ內屬于類簇i的下近似的數據點個數。

定義數據點xk與類簇i的相似度衡量公式如下：

2.2 RKM-DN 算法

根據上文的鄰域信息與局部密度分析，本節進一步提出考慮鄰域點歸屬信息混合度量的粗糙KMeans 算法，其流程如圖3 所示。

圖3 RKM-DN 算法流程Fig.3 Procedure of RKM-DN algorithm

類簇中心計算公式如下：

算法具體步驟如下：

步驟1隨機初始化類簇中心v。

步驟2?xk∈D，計算xk到各類簇中心的距離。

步驟3根據距離矩陣計算上下近似集，?xk∈D，將數據對象xk劃分至距離最近的類簇i中｛dki=min（dki｜i=1，2，…，k）｝，若?dki使得dkj-dki≤δ，則將xk劃入類簇j的上近似集，否則將xk劃分至類簇i的下近似集中。

步驟4?xk∈D，統計xk在鄰域范圍ξ內的密度，統計數據點xk的鄰域ξ內屬于類簇i的上近似的數據點的個數，統計數據點xk的鄰域ξ內屬于類簇i的下近似的數據點的個數。計算xk在鄰域范圍ξ內的緊湊度并根據式（10）計算數據點xk的權重。

步驟5根據式（11）更新類簇中心。當算法達到最大迭代次數或者算法收斂時結束算法，輸出劃分結果，否則返回步驟2。

3 實驗結果與分析

為驗證算法的有效性，將本文所提算法在人工模擬數據集和UCI 數據集上進行實驗。并與粗糙KMeans（RKM）［9］、粗糙模糊K-Means（RFKM）［16］、模糊粗糙K-Means（FRKM）［17］等算法在聚類精度和聚類時間方面進行對比。

3.1 人工數據集實驗分析

隨機生成服從正態分布的3 類數據，每個類簇包含50 個數據對象。為保證算法對比分析的公平性，在對同一數據集進行測試時所有算法均使用相同的初始聚類中心。在對算法參數進行設置時選擇最優參數組合。其中，RKM 算法與RFKM 算法的下近似權重wl=0.9，邊域權重wb=0.1，FRKM 算法的模糊指數m=2，RKM-DN 算法的鄰域ξ=0.3，4 種算法的決策距離閾值為0.01，最大迭代次數為100 次。其聚類準確度與聚類時間結果如表1、表2 所示。

表1 人工數據集上的聚類準確度對比Table 1 Comparison of clustering accuracy on artificial dataset%

表2 人工數據集上的聚類時間對比Table 2 Comparison of clustering time on artificial datasets

由表1 可知，RKM-DN 算法在對人工數據集的聚類結果上最優，分別高出RFKM 算法1.33 個百分點，高出RKM 和FRKM 算法2.66 個百分點。但是在聚類時間上，由于RKM-DN 算法一次迭代的時間復雜度為，而RKM 等算法一次迭代的時間復雜度為O（N2），因此RKM-DN 算法相較于其他3 種算法所需時間較高。

為更直觀地展示聚類效果，將4 種算法的聚類結果與原數據分布進行對比，圖4 為人工數據集的分布，人工數據集共分為3 類，每類使用不同符號表示，其中，圓點代表第1 類數據，星號代表第2 類數據，倒三角代表第3 類數據。圖5 給出了4 種算法在人工數據集上的聚類結果，加號為最終類簇中心，符號重疊的數據為類簇邊界區域的數據。

圖4 人工數據集分布Fig.4 Distribution of artificial dataset

圖5 4 種算法聚類結果示意圖Fig.5 Schematic diagram of clustering results of four algorithms

從圖5 可以看出，在對類簇1 和類簇2 邊界區域的數據點劃分時，RKM、RFKM、FRKM、RKM-DN 4 種算法的劃分結果大致相同，均將圖5 中所圈出的10 個數據點劃分到類簇1 中。在對類簇2 和類簇3邊界區域的數據點進行劃分時，RKM、RFKM、FRKM 3 種算法的劃分結果大致相同，而RKM-DN算法由于參考了數據點鄰域內的鄰居歸屬信息，從而誤判率較其他3 種算法相比最低。

在圖5 中所圈出的第2 類簇與第3 類簇的交界處共有13 個數據點，其中屬于第2 類簇的有5 個，屬于第3 類簇的有8 個。RKM 算法與FRKM 算法劃分正確的數據點有4 個，劃分錯誤的數據點有9 個。RFKM 算法劃分正確的數據點有6 個，劃分錯誤的數據點有7 個。RKM-DN 算法劃分正確的數據點有8 個，劃分錯誤的數據點有5 個。可以看出，在邊界區域交叉重疊嚴重的地方，RKM-DN 算法相較于其他3 類算法具有較好的分辨能力。

3.2 UCI 數據集實驗分析

在UCI 數據庫中選取Iris、Wine、Breast Tissue、Fertility 4 類數據集進行分析。在對同一數據集進行測試時使用相同的初始聚類中心與初始參數。在對算法參數進行設置時選擇最優參數組合，相關參數設置如表3 所示。由于Wine、Breast Tissue 數據集不同的特征值存在較大差異，因此在聚類前對其進行歸一化。相關實驗結果如表4 和表5 所示。

表3 算法參數設置Table 3 Algorithm parameter settings

表4 UCI 數據集上的聚類準確度對比Table 4 Comparison of cluster accuracy on UCI dataset %

表5 UCI 數據集上的聚類時間對比Table 5 Comparison of clustering time on UCI dataset s

從實驗結果可以看出，本文所提出的算法在Iris、Breast Tissue 和Wine 3 個數據集上的聚類準確率最高，在Fertility 數據集上的聚類結果與RFKM 算法相同，但在聚類時間上，其聚類所耗費時間較多。

以Wine 數據集為例，通過主成分分析法將Wine數據集映射至二維空間，其數據分布如圖6 所示，第1 類數據使用圓點表示，第2 類數據使用星號表示，第3 類數據使用倒三角表示。圖7 為4 種算法的聚類結果，其中，加號為最終類簇中心，符號重疊的數據為類簇邊界區域的數據。結合圖6 與圖7 對4 種算法的聚類結果進行分析，在類簇1 與類簇2 的邊界區域所圈出的區域中共有5 個數據點，這些數據點均屬于類簇2。RKM 算法將4 個數據點劃分至類簇1 中，將1 個數據點劃分至類簇1 和類簇2 的邊域中。RFKM 算法將4 個數據點劃分至類簇2 中，將1 個數據點劃分至類簇1 和類簇2 的邊域中。FRKM算法將4 個數據點劃分至類簇1 中，將1 個數據點劃分至類簇2 中。RKM-DN 算法將4 個數據點劃分至類簇2 中，將1 個數據點劃分至類簇1 和類簇2 的邊域中。因此，在類簇1 和類簇2 的邊界區域的劃分中，RFKM 與RKM-DN 算法的結果更加精確。

在類簇2 與類簇3 的邊界區域所圈出的區域中共有7 個數據點，其中有6 個數據點屬于類簇2，1 個數據點屬于類簇3。RKM 算法將3 個數據點劃分至類簇2 中，將1 個數據點劃分至類簇2 和類簇3 的邊域中，將3 個數據點劃分至類簇3 中。RFKM 算法將1 個數據點劃分至類簇2 和類簇3 的邊域中，將6 個數據點劃分至類簇3 中。FRKM 與RKM-DN 算法將4 個數據點劃分至類簇2 中，將3 個數據點劃分至類簇3 中。可見，在類簇2 與類簇3 的邊界區域的劃分中，FRKM 與RKM-DN 算法具有更佳的聚類效果。

圖6 Wine 數據集分布Fig.6 Distribution of Wine dataset

圖7 Wine 數據集聚類結果示意圖Fig.7 Schematic diagram of clustering results of Wine dataset

通過對圖7（a）～圖7（d）的分析可知，相較于原有算法，RKM-DN 算法對邊界區域數據劃分更加準確。這是因為在判斷邊界數據點與類簇相似度時，通過其鄰域歸屬信息來衡量數據點對于各類簇的權重，使得算法更傾向于將邊界數據點劃分至與該數據點有更強的密度聯通性的類簇中。更近一步，處于下近似區域的數據點與各類簇中心之間的距離差異較大，而邊界區域的數據點與各類簇中心之間的距離差異很小，因此，將邊界區域的數據點簡單地依賴其與各類簇中心之間的距離進行模糊化度量，難以區分數據對象之間的差異性。如圖7（d）所示，類簇2 的中心較其他3 種算法的聚類結果偏左，而在類簇2 與類簇3 的邊界處，RKM-DN 算法依然能準確地對邊界數據對象進行劃分。這是因為RKM-DN 算法在對邊界數據對象的權重進行計算時綜合了鄰域歸屬信息與局部密度，弱化了邊界數據對類簇中心位置的敏感度，使得算法對邊界區域的數據點劃分更加合理，從而提高了算法對邊界數據的劃分能力。

4 結束語

基于粗糙集的聚類算法及其衍生算法在類簇不平衡時使用距離和密度等進行衡量，但當數據點處于類簇邊域時，使用距離以及密度對數據點進行衡量較難區分數據的類簇。為此，本文提出一種考慮鄰域點歸屬信息混合度量的粗糙K-Means 算法，通過數據點的局部密度以及鄰域歸屬信息衡量數據點與類簇之間的相似性，提高了算法對邊界數據的劃分能力，并降低了邊界數據對類簇中心點位置的敏感度。在人工數據集和UCI 數據集上的實驗結果表明，基于鄰域歸屬信息的混合度量方法可以有效提高粗糙K-Means 算法的聚類精度。