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

孫靜勇，馬福民

（南京財(cái)經(jīng)大學(xué)信息工程學(xué)院，南京 210023）

0 概述

聚類算法根據(jù)數(shù)據(jù)之間的相似度對(duì)數(shù)據(jù)進(jìn)行劃分，使得簇內(nèi)數(shù)據(jù)相似度高，而簇間數(shù)據(jù)相似度低?，F(xiàn)有的聚類技術(shù)主要分為密度聚類、劃分聚類、層次聚類、模型聚類以及網(wǎng)格聚類［1］。K-Means 算法［2］作為劃分聚類算法之一，使用類簇中心點(diǎn)來代表每個(gè)類簇，具有簡(jiǎn)單、高效的特征，是當(dāng)前研究的熱門聚類技術(shù)［3-4］。

為解決不確定信息的劃分問題，文獻(xiàn)［5］將模糊集引入K-Means 算法，提出了模糊K-Means（Fuzzy K-Means，F(xiàn)KM）［6］聚類算法，在處理數(shù)據(jù)對(duì)象時(shí)采用模糊度量。文獻(xiàn)［7-8］將粗糙集理論融入K-Means算法，提出了粗糙K-Means（Rough K-Means，RKM）［9］聚類算法，解決了傳統(tǒng)K-Means 算法不能處理粗糙不可分辨信息的問題。文獻(xiàn)［10-12］將粗糙聚類算法應(yīng)用于林業(yè)、醫(yī)學(xué)成像、Web 挖掘、超級(jí)市場(chǎng)和交通工程等不同領(lǐng)域。文獻(xiàn)［13］使用相對(duì)距離作為粗糙K-Means 算法相似性度量的標(biāo)準(zhǔn)，減少了邊界區(qū)域離群數(shù)據(jù)點(diǎn)的影響。文獻(xiàn)［14］對(duì)粗糙K-Means 算法中上下近似權(quán)重問題進(jìn)行了完善。文獻(xiàn)［15］為驗(yàn)證粗糙聚類算法的有效性，對(duì)粗糙聚類算法和傳統(tǒng)聚類算法進(jìn)行了更進(jìn)一步的對(duì)比討論。

粗糙集和模糊集都是處理不確定信息的有效手段，兩者之間具有一定的互補(bǔ)性。文獻(xiàn)［16］結(jié)合了粗糙集與模糊集，提出粗糙模糊K-Means（Rough-Fuzzy K-Means，RFKM）聚類算法，利用模糊隸屬度對(duì)數(shù)據(jù)點(diǎn)進(jìn)行加權(quán)度量，使得算法在處理不確定信息時(shí)更加合理、準(zhǔn)確。文獻(xiàn)［17］提出的模糊粗糙KMeans（Fuzzy-Rough K-Means，F(xiàn)RKM）則認(rèn)為處于類簇下近似中的數(shù)據(jù)點(diǎn)是確定屬于該類簇的，只有處于邊界區(qū)域的數(shù)據(jù)點(diǎn)與類簇具有不確定關(guān)系。文獻(xiàn)［18］結(jié)合數(shù)據(jù)的空間分布對(duì)邊界交叉區(qū)域的數(shù)據(jù)進(jìn)行局部模糊度量，提出了基于邊界區(qū)域局部模糊增強(qiáng)的πRKM 算法（BF-πRKM），提高了算法處理邊界區(qū)域交叉嚴(yán)重?cái)?shù)據(jù)的準(zhǔn)確性。

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

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

1 相關(guān)聚類算法

1.1 粗糙K-Means 算法

RKM 聚類算法將交叉重疊區(qū)域中難以劃分的數(shù)據(jù)點(diǎn)歸為類簇的邊界區(qū)域，在數(shù)據(jù)點(diǎn)劃分的過程中，需要滿足以下性質(zhì)：

1）數(shù)據(jù)對(duì)象最多屬于某一類簇的下近似。

2）若數(shù)據(jù)對(duì)象不屬于任一類簇的下近似，則該數(shù)據(jù)對(duì)象屬于兩個(gè)及以上類簇的上近似。

3）若一個(gè)數(shù)據(jù)對(duì)象屬于某一類簇的下近似，則該數(shù)據(jù)對(duì)象也屬于該類簇的上近似。

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

由式（1）可見，粗糙K-Means 算法在對(duì)類簇中心點(diǎn)進(jìn)行計(jì)算時(shí)，將邊界區(qū)域的數(shù)據(jù)整體賦予一個(gè)較小的權(quán)重wb，減少了邊界不確定信息對(duì)類簇中心的影響。

1.2 改進(jìn)的粗糙K-Means 算法

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

其中，K為聚類的個(gè)數(shù)，dki為數(shù)據(jù)點(diǎn)xk與類簇i的中心點(diǎn)的距離，m為模糊指數(shù)。

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

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

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

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

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

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

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

1）若數(shù)據(jù)點(diǎn)xk的鄰域數(shù)據(jù)均屬于類簇i的下近似，則數(shù)據(jù)點(diǎn)xk屬于類簇i的概率非常高。

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

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

如圖1 所示，數(shù)據(jù)點(diǎn)x1與x2處于類簇交叉非常嚴(yán)重的邊界區(qū)域，x1與x2同時(shí)屬于類簇1、類簇2 與類簇3 的邊域。通過觀察x1的鄰域歸屬信息可以發(fā)現(xiàn)，x1的鄰域數(shù)據(jù)點(diǎn)多數(shù)分布在類簇1 中，少數(shù)分布在類簇3 中，僅有數(shù)據(jù)點(diǎn)本身處于類簇2 的邊域中。因此，數(shù)據(jù)點(diǎn)x1屬于類簇1 的概率要遠(yuǎn)大于類簇3 與類簇2。同理，數(shù)據(jù)點(diǎn)x2的鄰域數(shù)據(jù)點(diǎn)多數(shù)分布在類簇2 中，少數(shù)分布在類簇3 中，僅有數(shù)據(jù)點(diǎn)本身處于類簇1 的邊域。因此，數(shù)據(jù)點(diǎn)x2屬于類簇2 的概率要遠(yuǎn)大于類簇3 與類簇1。

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

由以上分析可以發(fā)現(xiàn)，即使是屬于多個(gè)類簇的邊界區(qū)域，數(shù)據(jù)點(diǎn)屬于各類簇的可能性也不一致。在以上的數(shù)據(jù)分布中，使用距離或者密度對(duì)其進(jìn)行衡量難以達(dá)到區(qū)分?jǐn)?shù)據(jù)的目的，尤其是當(dāng)數(shù)據(jù)點(diǎn)處于邊界交叉嚴(yán)重的區(qū)域。通過觀察數(shù)據(jù)點(diǎn)鄰域內(nèi)的數(shù)據(jù)分布情況，使用數(shù)據(jù)點(diǎn)的鄰域數(shù)據(jù)點(diǎn)歸屬信息來衡量該數(shù)據(jù)點(diǎn)與類簇的相似性可以對(duì)數(shù)據(jù)的劃分給予指導(dǎo)作用，從而提高算法的準(zhǔn)確度。

如圖2 所示，數(shù)據(jù)點(diǎn)x1與x2處于類簇1 的下近似，且x1與x2的鄰域數(shù)據(jù)點(diǎn)均屬于類簇1 的下近似，此時(shí)僅參考鄰域歸屬信息難以區(qū)分x1與x2對(duì)于類簇中心的重要性。但類簇中心的位置應(yīng)盡可能處于簇內(nèi)密度最大的區(qū)域，因此，局部密度越高的數(shù)據(jù)點(diǎn)對(duì)類簇中心的貢獻(xiàn)應(yīng)越大。

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

由圖2 可以看出，數(shù)據(jù)點(diǎn)x1的鄰域數(shù)據(jù)點(diǎn)非常緊湊，大多圍繞在x1的周圍，而數(shù)據(jù)點(diǎn)x2的鄰域數(shù)據(jù)點(diǎn)較為分散且與x2相距較遠(yuǎn)。很明顯，數(shù)據(jù)點(diǎn)x1對(duì)于類簇中心的貢獻(xiàn)更大。

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

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

定義數(shù)據(jù)點(diǎn)xk與類簇i的相似度衡量公式如下：

2.2 RKM-DN 算法

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

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

類簇中心計(jì)算公式如下：

算法具體步驟如下：

步驟1隨機(jī)初始化類簇中心v。

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

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

步驟4?xk∈D，統(tǒng)計(jì)xk在鄰域范圍ξ內(nèi)的密度，統(tǒng)計(jì)數(shù)據(jù)點(diǎn)xk的鄰域ξ內(nèi)屬于類簇i的上近似的數(shù)據(jù)點(diǎn)的個(gè)數(shù)，統(tǒng)計(jì)數(shù)據(jù)點(diǎn)xk的鄰域ξ內(nèi)屬于類簇i的下近似的數(shù)據(jù)點(diǎn)的個(gè)數(shù)。計(jì)算xk在鄰域范圍ξ內(nèi)的緊湊度并根據(jù)式（10）計(jì)算數(shù)據(jù)點(diǎn)xk的權(quán)重。

步驟5根據(jù)式（11）更新類簇中心。當(dāng)算法達(dá)到最大迭代次數(shù)或者算法收斂時(shí)結(jié)束算法，輸出劃分結(jié)果，否則返回步驟2。

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

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

3.1 人工數(shù)據(jù)集實(shí)驗(yàn)分析

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

表1 人工數(shù)據(jù)集上的聚類準(zhǔn)確度對(duì)比Table 1 Comparison of clustering accuracy on artificial dataset%

表2 人工數(shù)據(jù)集上的聚類時(shí)間對(duì)比Table 2 Comparison of clustering time on artificial datasets

由表1 可知，RKM-DN 算法在對(duì)人工數(shù)據(jù)集的聚類結(jié)果上最優(yōu)，分別高出RFKM 算法1.33 個(gè)百分點(diǎn)，高出RKM 和FRKM 算法2.66 個(gè)百分點(diǎn)。但是在聚類時(shí)間上，由于RKM-DN 算法一次迭代的時(shí)間復(fù)雜度為，而RKM 等算法一次迭代的時(shí)間復(fù)雜度為O（N2），因此RKM-DN 算法相較于其他3 種算法所需時(shí)間較高。

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

圖4 人工數(shù)據(jù)集分布Fig.4 Distribution of artificial dataset

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

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

在圖5 中所圈出的第2 類簇與第3 類簇的交界處共有13 個(gè)數(shù)據(jù)點(diǎn)，其中屬于第2 類簇的有5 個(gè)，屬于第3 類簇的有8 個(gè)。RKM 算法與FRKM 算法劃分正確的數(shù)據(jù)點(diǎn)有4 個(gè)，劃分錯(cuò)誤的數(shù)據(jù)點(diǎn)有9 個(gè)。RFKM 算法劃分正確的數(shù)據(jù)點(diǎn)有6 個(gè)，劃分錯(cuò)誤的數(shù)據(jù)點(diǎn)有7 個(gè)。RKM-DN 算法劃分正確的數(shù)據(jù)點(diǎn)有8 個(gè)，劃分錯(cuò)誤的數(shù)據(jù)點(diǎn)有5 個(gè)?？梢钥闯觯谶吔鐓^(qū)域交叉重疊嚴(yán)重的地方，RKM-DN 算法相較于其他3 類算法具有較好的分辨能力。

3.2 UCI 數(shù)據(jù)集實(shí)驗(yàn)分析

在UCI 數(shù)據(jù)庫(kù)中選取Iris、Wine、Breast Tissue、Fertility 4 類數(shù)據(jù)集進(jìn)行分析。在對(duì)同一數(shù)據(jù)集進(jìn)行測(cè)試時(shí)使用相同的初始聚類中心與初始參數(shù)。在對(duì)算法參數(shù)進(jìn)行設(shè)置時(shí)選擇最優(yōu)參數(shù)組合，相關(guān)參數(shù)設(shè)置如表3 所示。由于Wine、Breast Tissue 數(shù)據(jù)集不同的特征值存在較大差異，因此在聚類前對(duì)其進(jìn)行歸一化。相關(guān)實(shí)驗(yàn)結(jié)果如表4 和表5 所示。

表3 算法參數(shù)設(shè)置Table 3 Algorithm parameter settings

表4 UCI 數(shù)據(jù)集上的聚類準(zhǔn)確度對(duì)比Table 4 Comparison of cluster accuracy on UCI dataset %

表5 UCI 數(shù)據(jù)集上的聚類時(shí)間對(duì)比Table 5 Comparison of clustering time on UCI dataset s

從實(shí)驗(yàn)結(jié)果可以看出，本文所提出的算法在Iris、Breast Tissue 和Wine 3 個(gè)數(shù)據(jù)集上的聚類準(zhǔn)確率最高，在Fertility 數(shù)據(jù)集上的聚類結(jié)果與RFKM 算法相同，但在聚類時(shí)間上，其聚類所耗費(fèi)時(shí)間較多。

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

在類簇2 與類簇3 的邊界區(qū)域所圈出的區(qū)域中共有7 個(gè)數(shù)據(jù)點(diǎn)，其中有6 個(gè)數(shù)據(jù)點(diǎn)屬于類簇2，1 個(gè)數(shù)據(jù)點(diǎn)屬于類簇3。RKM 算法將3 個(gè)數(shù)據(jù)點(diǎn)劃分至類簇2 中，將1 個(gè)數(shù)據(jù)點(diǎn)劃分至類簇2 和類簇3 的邊域中，將3 個(gè)數(shù)據(jù)點(diǎn)劃分至類簇3 中。RFKM 算法將1 個(gè)數(shù)據(jù)點(diǎn)劃分至類簇2 和類簇3 的邊域中，將6 個(gè)數(shù)據(jù)點(diǎn)劃分至類簇3 中。FRKM 與RKM-DN 算法將4 個(gè)數(shù)據(jù)點(diǎn)劃分至類簇2 中，將3 個(gè)數(shù)據(jù)點(diǎn)劃分至類簇3 中?？梢姡陬惔? 與類簇3 的邊界區(qū)域的劃分中，F(xiàn)RKM 與RKM-DN 算法具有更佳的聚類效果。

圖6 Wine 數(shù)據(jù)集分布Fig.6 Distribution of Wine dataset

圖7 Wine 數(shù)據(jù)集聚類結(jié)果示意圖Fig.7 Schematic diagram of clustering results of Wine dataset

通過對(duì)圖7（a）～圖7（d）的分析可知，相較于原有算法，RKM-DN 算法對(duì)邊界區(qū)域數(shù)據(jù)劃分更加準(zhǔn)確。這是因?yàn)樵谂袛噙吔鐢?shù)據(jù)點(diǎn)與類簇相似度時(shí)，通過其鄰域歸屬信息來衡量數(shù)據(jù)點(diǎn)對(duì)于各類簇的權(quán)重，使得算法更傾向于將邊界數(shù)據(jù)點(diǎn)劃分至與該數(shù)據(jù)點(diǎn)有更強(qiáng)的密度聯(lián)通性的類簇中。更近一步，處于下近似區(qū)域的數(shù)據(jù)點(diǎn)與各類簇中心之間的距離差異較大，而邊界區(qū)域的數(shù)據(jù)點(diǎn)與各類簇中心之間的距離差異很小，因此，將邊界區(qū)域的數(shù)據(jù)點(diǎn)簡(jiǎn)單地依賴其與各類簇中心之間的距離進(jìn)行模糊化度量，難以區(qū)分?jǐn)?shù)據(jù)對(duì)象之間的差異性。如圖7（d）所示，類簇2 的中心較其他3 種算法的聚類結(jié)果偏左，而在類簇2 與類簇3 的邊界處，RKM-DN 算法依然能準(zhǔn)確地對(duì)邊界數(shù)據(jù)對(duì)象進(jìn)行劃分。這是因?yàn)镽KM-DN 算法在對(duì)邊界數(shù)據(jù)對(duì)象的權(quán)重進(jìn)行計(jì)算時(shí)綜合了鄰域歸屬信息與局部密度，弱化了邊界數(shù)據(jù)對(duì)類簇中心位置的敏感度，使得算法對(duì)邊界區(qū)域的數(shù)據(jù)點(diǎn)劃分更加合理，從而提高了算法對(duì)邊界數(shù)據(jù)的劃分能力。

4 結(jié)束語(yǔ)

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