摘 要：針對鄰域粗糙集模型受鄰域參數(shù)影響大、刻畫樣本信息時不夠精細等問題，提出了一種基于最大聯(lián)盟理論的粗糙集模型。在標準化鄰域信息系統(tǒng)后，引入最大聯(lián)盟集來描述鄰域顆粒信息，使得鄰域粗糙集模型對信息的劃分更加精細，從而顯著降低了邊界域的不確定性。將該模型與三支聚類相結合，設計了一種基于最大聯(lián)盟粗糙集的三支聚類算法。在6個UCI公共數(shù)據(jù)集上進行對比實驗，結果表明，所提算法相較于對比算法具有更好的聚類質量，在處理邊界域樣本時具有更高的比較正確率。

關鍵詞：標準化鄰域信息系統(tǒng)； 最大聯(lián)盟集； 領域粗糙集； 邊界域； 三支聚類； 比較正確率

中圖分類號：TP391 文獻標志碼：A

文章編號：1001-3695（2024）08-007-2292-09

doi：10.19734/j.issn.1001-3695.2023.12.0582

Three-way clustering algorithm based on maximum coalition rough set

Chen Zhiqi1， Wan Renxia1， Yue Xiaodong2， Chen Ruidian3

（1.College of Mathematics & Information Science， North Minzu University， Yinchuan 750021， China; 2.School of Computer Engineering & Science， Shanghai University， Shanghai 200444， China; 3.Hongyang Institute for Big Data in Health， Fuzhou 350002， China）

Abstract：In order to address the limnK9/OI5+92Gg3hqxzIj3st+kscQHWd+Vpo2yVP+X3yw=itations of the neighborhood rough set model caused by neighborhood parameters and inadequate sample information representation， this paper proposed a rough set model based on the maximum coalition theory. By normalizing the neighborhood information system and utilizing the maximum coalition set to describe neighborhood granular information， the proposed model enabled finer information division and significant reduction of uncertainty in the boundary region. Combining the model with three-way clustering， this paper designed a three-way clustering algorithm based on maximum coalition rough set. Comparative experiments on six UCI public data sets show that the proposed algorithm has better clustering quality than the comparison algorithms， and has higher comparison accuracy when dealing with boundary region samples.

Key words：standardized neighborhood information system; maximum coalition set; neighborhood rough sets; boundary region; three-way clustering; comparison accuracy

0 引言

粗糙集理論是在1982年由波蘭數(shù)學家Pawlak教授［1］提出的一種用于處理不確定性知識或不一致信息的數(shù)據(jù)推理方法。經典Pawlak粗糙集模型是以等價關系和等價類為基礎的一種粒度計算模型，用于處理名義型數(shù)據(jù)，而無法直接處理數(shù)值型數(shù)據(jù)。為了突破這種限制，一些學者延伸拓展出了更多其他類型的粗糙集模型。Yao等人［2］通過引入條件概率提出了決策粗糙集模型。Azam等人［3］通過權衡策略將邊界域內的樣本劃分給正域或負域時的不確定性，使之達到最佳平衡，提出了博弈粗糙集模型。Lin［4］結合拓撲學中內點和閉包的知識，提出了鄰域模型的概念，該模型將空間中點的鄰域作為基本信息粒子對論域進行粒化。文獻［5，6］分別提出了1-step鄰域和k-step鄰域，并對鄰域信息系統(tǒng)的性質進行了詳細討論。胡清華等人［7］將鄰域的概念引入到粗糙集理論中，用鄰域關系代替嚴格的等價關系，提出了能夠處理混合型數(shù)據(jù)的鄰域粗糙集模型。Lin等人［8］將鄰域粗糙集和多粒度粗糙集相結合，構造了鄰域多粒度粗糙集模型。Wang等人［9］基于鄰域的思想，定義了局部近似集，提出了局部鄰域粗糙集模型。Wang等人［10］結合了δ鄰域和k近鄰顆粒的優(yōu)點，提出了k最近鄰域粗糙集模型。當前，鄰域粗糙集已成為處理數(shù)值數(shù)據(jù)被廣泛使用的粗糙集模型之一。

聚類分析［11］是數(shù)據(jù)挖掘中的一項重要技術，是一種無監(jiān)督的機器學習技術，已經廣泛地應用于多個領域，如模式識別、圖像處理、統(tǒng)計學、生物信息學、信息?；取Ｋ^聚類，就是將數(shù)據(jù)集中相似度高的樣本劃分到相同類簇，相似度低的樣本劃分到不同類簇。大多數(shù)的傳統(tǒng)聚類算法都是硬聚類算法，要求聚類結果具有清晰的邊界，即元素要么屬于一個類，要么不屬于一個類。然而，在處理不確定信息時，考慮到當前可用信息的不充分性，若強制將元素劃分到某個類中，通常會導致較高的錯誤率或決策風險。

目前，已經有許多新的聚類策略被提出，用來解決傳統(tǒng)聚類方法存在的問題。Yao［12］于2010年提出了一種符合人類認知能力的三支決策模型，為粗糙集的正域、負域、邊界域提供了合理的語義解釋。錢文彬等人［13］針對不完備混合決策系統(tǒng)構造了三種決策風險下的三支決策模型。呂艷娜等人［14］通過改變粒度選擇方式重新構建多粒度空間，提出了基于深度置信網絡的代價敏感多粒度三支決策模型。于洪［15］將三支決策思想融入到傳統(tǒng)聚類中，提出了一種基于K-means的三支決策聚類算法，用核心域、邊界域和瑣碎域來表示一個類簇。劉強等人［16］利用元素的鄰域在二支聚類的結果上進行收縮和擴張，提出了一種基于ε鄰域的三支聚類算法。萬仁霞等人［17］考慮分類錯誤的風險代價，將數(shù)據(jù)對象屬于各個類簇的后驗概率作為決策評價函數(shù)，提出了基于三支決策的高斯混合聚類算法?；ㄓ龃旱热耍?8］利用樸素貝葉斯確定兩樣本的共現(xiàn)概率，提出了基于共現(xiàn)概率的三支聚類模型。申秋萍等人［19］通過考慮近鄰的標簽，對二支聚類結果的臨界點和噪聲點進行重新劃分，提出了基于局部半徑的三支DBSCAN算法。相比于傳統(tǒng)的聚類方法，三支聚類在處理不確定性和模糊性較高的數(shù)據(jù)時更具優(yōu)勢，更能適應實際情況中存在的多樣性和交叉性。

Pawlak［20］定義了具有支持、中立、反對評價的三值信息系統(tǒng)，給出了三值信息系統(tǒng)中計算輔助函數(shù)和距離函數(shù)的方法，用于確定不同代理間的沖突、中立和聯(lián)盟關系。然而，在任意聯(lián)盟集中，給定代理與其他代理之間都存在聯(lián)盟關系，但并非所有代理之間都是兩兩聯(lián)盟的。為此，Lang等人［21］在決策粗糙集理論的基礎上，提出了動態(tài)信息系統(tǒng)中的概率沖突集、中立集和聯(lián)盟集的增量構造方法，并給出了最大聯(lián)盟集的概念，使得最大聯(lián)盟集中任意兩代理之間都滿足聯(lián)盟關系。郭淑蓉［22］針對計算最大聯(lián)盟集時運算量較大的問題，通過將參數(shù)β區(qū)間化，把無限多個最大聯(lián)盟集的計算問題減少為有限多個，從而提高了計算效率。羅珺方等人［23］在不完備異構沖突信息系統(tǒng)中，定義了極大一致聯(lián)盟區(qū)間集族，并利用極大團的枚舉算法進行獲取。

使用粗糙集模型刻畫樣本信息時，本文希望通過壓縮邊界域來減少信息的不確定性，以提高分類精度。而最大聯(lián)盟集使得數(shù)據(jù)對象之間的關系更加緊密，且相較于δ鄰域顆粒信息，可以更為細致地刻畫樣本信息，為解決不確定性問題提供了新的思路。本文通過引入最大聯(lián)盟集的相關概念，提出了基于最大聯(lián)盟的鄰域粗糙集模型，并基于該模型設計了一種新的三支聚類算法。

1 預備知識

1.1 鄰域粗糙集

在決策分析中，通常各指標間的計量單位和數(shù)量級不盡相同，從而使得各指標之間不具備綜合性，數(shù)據(jù)標準化旨在消除各指標量綱之間的影響，有助于確保數(shù)據(jù)的質量和一致性。

定義1 設NS=（U，A，V，f，δ）為一個鄰域信息系統(tǒng)，其中論域U={x1，x2，…，xn}，屬性集A=C∪D，C是條件屬性，D是決策屬性，值域V={Va|a∈A}，f：U×A→V為信息函數(shù)，f（x，a）表示對象x在屬性a上的值，δ為鄰域半徑。對于任意實數(shù)p∈［1，+∞），ak∈A，xiU，映射函數(shù)（xi，ak）定義如下：

（xi，ak）=f（xi，ak）-fmin（x，ak）fmax（x，ak）-fmin（x，ak）×1pn

其中：fmax（x，ak）和fmin（x，ak）分別為對象x在屬性ak上的最大值和最小值。

映射函數(shù)將所有數(shù)據(jù)信息縮放到區(qū)間［0，1/pn］上，起到了標準化作用。后文中，本文用NSnorm=（U，A，V，f，δ）表示NS=（U，A，V，f，δ）標準化后的鄰域信息系統(tǒng)。

定義2［7］ 設鄰域信息系統(tǒng)NSnorm=（U，A，V，f，δ），對于ak∈A，xi，xj∈U，則xi和xj之間的距離函數(shù)Δ（xi，xj）為

Δ（xi，xj）=（∑nk=1（xi，ak）-（xj，ak）p）1p

其中：當p=1時，為曼哈頓距離；當p=2時，為歐氏距離;當p=3時，為切比雪夫距離。

性質1 設鄰域信息系統(tǒng)NSnorm=（U，A，V，f，δ），對于xi，xj∈U，有0≤Δ（xi，xj）≤1。

證明 由定義1可知，0≤f（xi，ak）≤1/pn≤1，則0≤f（xi，ak）－f（xj，ak）≤1/pn。對于p∈［1，+∞），有0≤f（xi，ak）－f（xj，ak）p≤1/n，則0≤∑nk=1f（xi，ak）－f（xj，ak）p≤1，故而0≤（∑nk=1f（xi，ak）－f（xj，ak）p）1p≤1。

定義3［7］ 設鄰域信息系統(tǒng)NS=（U，A，V，f，δ），對于xi∈U，特征子集BA，xi在B上的δ鄰域定義如下：δB（xi）={xj|xj∈U，ΔB（xi，xj）≤δ}

其中：ΔB（xi，xj）表示在特征子集B上xi和xj之間的距離，樣本xi的鄰域是由距離函數(shù)Δ、鄰域半徑δ和屬性集合B共同決定的。

定義4［7］ 設鄰域信息系統(tǒng)NS=（U，A，V，f，δ），對于BA，XU，則X關于B的鄰域下近似集、上近似集、正域、負域和邊界域分別為

下近似集：NB（X）={xi|δB（xi）X，xi∈U}

上近似集：B（X）={xi|δB（xi）∩X≠，xi∈U}

正域：POSB（X）=N（X）

負域：NEGB（X）=U-（X）

邊界域：BNB（X）=（X）-N（X）

其中：（NB（X），B（X））稱為δ鄰域粗糙集。

1.2 最大聯(lián)盟集

定義5［21］ 設鄰域信息系統(tǒng)NS=（U，A，V，f，δ），閾值α、β滿足0≤β<α≤1，對于BA，xU，x的概率沖突集、中立集和聯(lián)盟集分別為

a）沖突集：COαβ（x）={y∈U|ΔB（x，y）>α}；

b）中立集：NEαβ（x）={y∈U|α≥ΔB（x，y）≥β}；

c）聯(lián)盟集：ALαβ（x）={y∈U|ΔB（x，y）<β}。

由定義5可得，若β=δ，則ALαβ（x）=δ（x），即x的概率聯(lián)盟集就是x的δ鄰域。

定義6［21］ 設鄰域信息系統(tǒng)NS=（U，A，V，f，δ），閾值α、β滿足0≤β<α≤1，BA，XU：

a）若x，y∈X，ΔB（x，y）<β，則稱X為一個聯(lián)盟集；

b）若X為一個聯(lián)盟集，并且不存在聯(lián)盟集Y，使得XY，則稱X為一個最大聯(lián)盟集。

定理1［21］ 設鄰域信息系統(tǒng)NS=（U，A，V，f，δ），XU且0≤β≤α≤1，則X為最大聯(lián)盟集的充要條件為

∩x∈XALαβ（x）=X

命題1［21］ 設鄰域信息系統(tǒng)NS=（U，A，V，f，δ），MC={MC1，MC2，…，MCp}是論域U中全體最大聯(lián)盟集的集合，則

∩1≤i≤pMCi=U

1.3 三支聚類

Yu等人將三支決策引入到聚類算法中，提出了三支聚類方法。給定一個數(shù)據(jù)集U={x1，x2，…，xn}，可獲得聚類結果C={C1，C2，…，Ck}。三支聚類在傳統(tǒng)的二支聚類結果中加入了邊界域的概念，用三個互不相交的集合表示一個類，即Co（Ci）、Fr（Ci）與Tr（Ci），分別稱為類Ci的核心域、邊界域和瑣碎域。其中，核心域中的對象確定屬于這個類，邊界域中的對象可能屬于這個類，瑣碎域中的元素肯定不屬于這個類，它們滿足如下性質：

a）Co（Ci）≠，i=1，2，…，k。

b）∪ki=1（Co（Ci）∪Fr（Ci））=U。

c）Co（Ci）∩Co（Cj）=，i≠j。

其中：性質a）要求每個類簇的核心域不能為空；性質b）確保所有對象都能被有效劃分；性質c）要求不同類簇的核心域之間沒有交集。

三支聚類的結果表示如下：

TC={（Co（C1），F(xiàn)r（C1）），（Co（C2），F(xiàn)r（C2）），…，（Co（Ck），F(xiàn)r（Ck））}

劉強等人［16］利用每個類中元素的δ鄰域進行收縮和擴張，提出了一種基于動態(tài)鄰域的三支聚類算法。該算法的大致流程如下：

a）利用硬聚類算法對U進行聚類，得到聚類結果C={C1，C2，…，Ck}；

b）對于每一類Ci，任取xj∈Ci，若δ（xj）Ci，則xj∈Co（Ci），否則xj∈Fr（Ci）；

c）對于每一類Ci，任取xjCi，若δ（xj）∩Ci≠，則xj∈Fr（Ci）；

d）得到最終聚類結果為

TC={（Co（C1），F(xiàn)r（C1）），（Co（C2），F(xiàn)r（C2）），…，（Co（Ck），F(xiàn)r（Ck））}

2 基于最大聯(lián)盟粗糙集的三支聚類

本章定義了最大聯(lián)盟集的緊致度公式，用于確定每個對象最緊致的最大聯(lián)盟集，并將其作為一種新的鄰域顆粒信息與粗糙集模型相結合，構造了最大聯(lián)盟粗糙集模型，然后將該模型應用于聚類分析中，提出了基于最大聯(lián)盟的三支聚類算法。

2.1 基于最大聯(lián)盟的粗糙集模型

給定鄰域信息系統(tǒng)NSnorm=（U，A，V，f，δ），MC={MC1，MC2，…，MCp}是論域U中全體最大聯(lián)盟集的集合，MC（xi）={MC1（xi），MC2（xi），…，MCt（xi）}是論域U中包含xi的所有最大聯(lián)盟集的集合，其中t≤p。

定義7 樣本點xi的局部密度為

ρ（xi）=MCk（xi）∑xj∈MCk（xi）exp（-dij） if MCk（xi）>10if MCk（xi）=1

其中：|MCk（xi）|表示xi的最大聯(lián)盟集中的樣本點數(shù)量；dij表示樣本點xi與xj之間的距離，樣本點xi的局部密度是由集合的樣本數(shù)量和各點到該樣本點的距離共同決定的。

定義8 x，y∈MCk（xi），最大聯(lián)盟集MCk（xi）的緊致度定義如下：

Euclid Math OneTAp（MCk（xi））=ρ（xi）+12∑x∑yexp（-d（x，y））

分析上式可知，Euclid Math OneTAp反映了最大聯(lián)盟集MCk（xi）在空間中的緊密程度。將MC（xi）按緊致度從大到小依次排列{MC1′（xi），MC2′（xi），…，MCt′（xi）}，得到與xi緊密程度最高的最大聯(lián)盟集MCbest（xi）=MC1′（xi）。

定義9 設NSnorm=（U，A，V，f，δ）是鄰域信息系統(tǒng)，XU，定義X基于最大聯(lián)盟集的下近似集、上近似集、正域、負域和邊界域分別為

下近似集：M（X）={xi|MCbest（xi）X，xi∈U}

上近似集：（X）={xi|MCbest（xi）∩X≠，xi∈U}

正域：MPOS（X）=M（X）

負域：MNEG（X）=U-（X）

邊界域：BM（X）=（X）-M（X）

稱（M（X），（X））為最大聯(lián)盟粗糙集。

如圖1所示，采用δ鄰域和最大聯(lián)盟集分別刻畫樣本x的鄰域信息，其中，實心圓形和實心三角形分別代表兩類樣本，實線圓圈表示x的δ鄰域，虛線圓圈表示x的3個最大聯(lián)盟集，紅色虛線圓則表示與x緊密程度最高的最大聯(lián)盟集（參見電子版）。觀察x的δ鄰域，可以發(fā)現(xiàn)兩種類型的樣本都包含其中，根據(jù)δ鄰域粗糙集的定義，樣本x將被劃分到邊界域中。再分別觀察x的三個最大聯(lián)盟集，根據(jù)最大聯(lián)盟粗糙集的定義，在鄰域粒度MC1（x）下，樣本x將被錯誤地劃分到實心圓類別中；在鄰域粒度MC2（x）下，樣本x將被劃分到邊界域中；而在鄰域粒度MCbest（x）下，樣本x將被劃分到實心三角形類別中，從而得到最正確的劃分。

關于最大聯(lián)盟粗糙集，本文有以下一些重要性質。

性質2 設鄰域信息系統(tǒng)NSnorm=（U，A，V，f，δ），對于XU，有：

a）M（X）X（X）；

b）M（）=（）=，M（U）=（U）=U;

c）M（X∩Y）=M（X）∩M（Y），（X∪Y）=（X）∪（Y）;

d）若XY，則M（X）M（Y），（X）（Y）;

e）M（X∩Y）M（X）∩M（Y），（X∩Y）（X）∩（Y）;

f）M（～X）=～（X），（～X）=～M（X）。

證明 a）設xi∈M（X）MCbest（xi）X，因為xi∈MCbest（xi），所以xi∈X，故M（X）X；設xi∈XMCbest（xi）∩X≠xi∈（X），故X（X）。

b）由a）知，M（），而M（），所以M（）=；假設（）≠，則存在xi使得xi∈（），即MCbest（xi）∩≠，而MCbest（xi）∩=與假設矛盾，因此（）=；xi∈UMCbest（xi）Uxi∈M（U）UM（U），由a）知，M（U）U，故M（U）=U；由a）知，U（U），但（U）U，因此（U）=U。

c）對于xi∈M（X∩Y）MCbest（xi）X∩YMCbest（xi）X∧MCbest（xi）Yxi∈M（X）∩M（Y），因此M（X∩Y）=M（X）∩M（Y）;xi∈（X∪Y）MCbest（xi）∩（X∪Y）≠（MCbest（xi）∩X）∪（MCbest（xi）∩Y）≠MCbest（xi）∩X≠∨MCbest（xi）∩Y≠xi∈（X）∨xi∈（Y）xi∈（X）∪（Y），因此（X∪Y）=（X）∪（Y）。

d）設XY，則X∩Y=X，X∪Y=Y，所以M（X∩Y）=M（X），（X∪Y）=（Y），由c）知，M（X）∩M（Y）=M（X），（X）∪（Y）=（Y），故M（X）M（Y），（X）（Y）。

e）因XX∪Y，YX∪Y，所有M（X）M（X∪Y），M（Y）M（X∪Y），故M（X）∩M（Y）M（X∩Y）；因為X∩YX，X∩YY，所以（X∩Y）（X），（X∩Y）（Y），故（X∩Y）（X）∩（Y）。

f）對于xi∈M（X）MCbest（xi）XMCbest（xi）∩～X=xi（～X）xi∈～（～X），因此M（X）=～（～X），故而M（～X）=～（X）。

性質3 設NSnorm=（U，A，V，f，δ）是鄰域信息系統(tǒng)，0≤β<α≤1且β=δ，XU，有：

a）MCbest（xi）δ（xi），xi∈U；

b）N（X）M（X）;

c）（X）（X）;

d）BM（X）BN（X）。

證明 a）由定理1可知，MC（xi）AL（xi）。又當β=δ時，AL（xi）=δ（xi），故MC（xi）δ（xi）。因為MCbest（xi）MC（xi），所以MCbest（xi）δ（xi）。

b）因為xi∈N（X）δ（xi）XMCbest（xi）X，則有xi∈M（X），所以N（X）M（X）。

c）因為xi∈（X）MCbest（xi）∩X≠δ（xi）∩X≠，則有xi∈（X），所以（X）（X）。

d）由b）和c）的證明可知，BM（X）=（X）-M（X）（X）-N（X）=BN（X）。

定義10 設NSnorm=（U，A，V，f，δ）是鄰域信息系統(tǒng)，屬性集A=C∪D，C是條件屬性，D是決策屬性，U/D={D1，D2，…，Dr}為論域U在決策特征D上的等價劃分。決策相對應的屬性子集的正域、負域和邊界域分別定義如下：

正域：MPOS（D）=∪rj=1M（Dj）

負域：MNEG（D）=U-∪rj=1（Dj）

邊界域：BM（D）=∪rj=1（Dj）-∪rj=1M（Dj）

顯然，正域和邊界域是互補的，正域是由所有決策類下近似的并集構成。

2.2 基于最大聯(lián)盟粗糙集的三支聚類算法

相對于經典粗糙集，最大聯(lián)盟粗糙集為數(shù)據(jù)對象提供了更加豐富的鄰域顆粒信息，將最大聯(lián)盟粗糙集模型與三支決策理論相結合，用產生的三支聚類結果代替?zhèn)鹘y(tǒng)的二支聚類結果，有效規(guī)避了直接作出屬于某一類或不屬于某一類決策所帶來的潛在風險，將為分析數(shù)據(jù)對象間的關系提供更可靠的信息支持。

設對象集U的k個聚類結果是C={C1，C2，…，Ck}，則Ci的核心域Co（Ci）和邊界域Fr（Ci）分別表示為Co（Ci）=M（Ci），F(xiàn)r（Ci）=（Ci）-M（Ci）。三支聚類結果可以表示為

TC={（Co（C1），F(xiàn)r（C1）），（Co（C2），F(xiàn)r（C2）），…，（Co（Ck），F(xiàn)r（Ck））}

基于最大聯(lián)盟粗糙集的三支聚類算法具體步驟如下：

輸入：數(shù)據(jù)集U={x1，x2，…，xn}，參數(shù)k、q。

輸出：聚類結果{（Co（C1），F(xiàn)r（C1）），（Co（C2），F(xiàn)r（C2）），…，（Co（Ck），F(xiàn)r（Ck））}。

a）利用硬聚類算法對U進行聚類，得到C={C1，C2，…，Ck}；

b）對于任意xi，xj∈U，根據(jù)定義2計算任意兩點之間的距離Δ（xi，xj），找到每個樣本點xi的δ鄰域集δ（xi）={xj|xj≤q}；

c）確定U中滿足條件∩x∈MCkδ（x）=MCk的所有最大聯(lián)盟集MC={MC1，MC2，…，MCp}；

d）對于任意xi∈U，依次遍歷U中所有的最大聯(lián)盟MC，篩選出xi的所有最大聯(lián)盟集的集合MC（xi）={MC1（xi），MC2（xi），…，MCt（xi）}，根據(jù)定義8中的緊致度公式，找到與xi緊密程度最高的最大聯(lián)盟集MCbest（xi）；

e）對于每一類Ci，任取xj∈Ci，若MCbest（xi）Ci，則xj∈Co（Ci），否則xj∈Fr（Ci）；

f）對于每一類Ci，任取xjCi，若MCbest（xi）∩Ci≠，則xj∈Fr（Ci）；

g）通過步驟e）和f）得到Co（Ci）和Fr（Ci）（i=1，2，…，k），返回最終聚類結果{（Co（C1），F(xiàn)r（C1）），（Co（C2），F(xiàn)r（C2）），…，（Co（Ck），F(xiàn)r（Ck））}。

其中，步驟c）可以簡化為：（a）如果δ（x）={x}，則{x}是一個最大聯(lián)盟集，接下來僅需考慮U/{x|δ（x）={x}}；（b）假設δ（x）=X，且X>1，取y∈X/{x}，計算δ（x）∩δ（y）。若δ（x）∩δ（y）={x，y}，則{x，y}是一個最大聯(lián)盟集，否則，取z∈{δ（x）∩δ（y）}/{x，y}。若δ（x）∩δ（y）∩δ（z）={x，y，z}，則{x，y，z}是一個最大聯(lián)盟集，否則，重復上述直至滿足對于YX，∪x∈Yδ（x）=Y。

3 評價指標

3.1 不確定性評價

粗糙集理論中的不確定性度量是評價系統(tǒng)分類能力及提高分類精度的重要工具，國內外眾多學者對此進行了研究。設鄰域信息系統(tǒng)NS=（U，A，V，f，δ）， C是條件屬性，D是決策屬性，A=C∪D，U/D={D1，D2，…，Dm}是對象集U在決策特征D上的等價劃分，本文采取以下三個指標進行評價：

a）鄰域近似精度［24］：

αδB（D）=∑mi=1Di∑mi=1Di

b）鄰域信息熵［24］：

Hδ（B）=1+1U∑|U|i=1nδB（xi）U lgUlg1|nδB（xi）|

c）加權鄰域信息熵［24］：

αH（d，B）=αδB（d）*Hδ（B）

3.2 聚類效果評價

本文選取三個經典的聚類指標準確率（ACC）、戴維森堡丁指數(shù)（DBI）和宏平均（Macro_F1）作為評估聚類算法的標準。

a）準確率（accuracy，ACC）：

ACC=1N∑ki=1Ci

其中：數(shù)據(jù)集的大小為N，被成功劃分到類i的樣本數(shù)記為Ci，聚類數(shù)為k，ACC的取值為［0，1］。ACC值越大，表示聚類效果越好。本文通過計算核心域的樣本數(shù)據(jù)獲得ACC的取值。

b）戴維森堡丁指數(shù)（Davies-Bouldin index，DBI）：

DBI=1k∑ki=1maxi≠j（S（Ci）+S（Cj）‖wi－wj‖2）

其中：S（Ci）表示第i類中的所有樣本元素到聚類中心wi的平均距離；‖wi-wj‖2表示類i與j之間的歐氏距離;k表示聚類數(shù)。DBI評價一個聚類結果好壞的依據(jù)是：要求類內元素相似度高，類間元素相似度低。DBI值越小，表示聚類結果越好，意味著簇內數(shù)據(jù)點更加緊密地聚集在一起，而簇與簇之間的區(qū)別更加明顯。

c）宏平均（Macro_F1）［25］：

Macro_F1=2MacroP×MacroRMacroP+MacroR

其中：MacroP=1k∑ki=1TPCiTPCi+FPCi，MacroR=1k∑ki=1TPCiTPCi+FNCi。TPCi表示core（Ci）中對象被正確分類為該類的數(shù)量，F(xiàn)PCi表示非core（Ci）中對象被錯誤分類為該類的數(shù)量，F(xiàn)NCi表示非core（Ci）中對象被正確分類為不屬于該類的數(shù)量。宏平均F1值綜合了精確率和召回率，用于衡量聚類結果的準確性和完整性。它是通過計算每個簇的F1值并求其平均值得到的，該值越大表示聚類結果越好。

由于三支聚類結果是由兩個區(qū)域近似表示的，所以僅使用硬聚類指標評價無法評估類簇的核心域和邊界域之間的關系，會導致評估結果不夠客觀和全面。因此，本文除選取上述三個常用的評價指標外，還選取了三個軟聚類評價指標對三支聚類效果進行評價：

d）所有正域的平均質量［26］：

γ=1n∑ki=1|Co（Ci）|

e）c個類簇的平均質量［27］：

α=1c∑ki=1|Co（Ci）||Co（Ci）|+|Fr（Ci）|

f）c個類簇的整體質量［27］：

α*=∑cj=1|Co（Ci）|∑cj=1|Co（Ci）|+|Fr（Ci）|

第一個軟聚類評價指標γ是由Maji提出的，用于衡量所有正域的平均質量，該值越大，表示聚類效果越好。在Maji的啟示下，Zhang提出了另外兩個軟聚類評價指標α和α*，分別用于衡量c個類簇的平均質量和整體質量。對于特定的類簇而言，核心域中的數(shù)據(jù)點越多，意味著有更多數(shù)據(jù)點被明確地歸屬于該類簇。也就是說，下近似與上近似中數(shù)據(jù)點數(shù)量的比率可以顯示聚類結果的質量。這兩個指標的數(shù)值越大，表示聚類效果越好。

4 實例分析與實驗驗證

4.1 實例分析

給定一個鄰域信息決策系統(tǒng)NS=（U，A，V，f，δ）［28］，其中對象集U={x1，x2，x3，x4，x5，x6，x7，x8，x9，x10}；條件特征集C={a1，a2，a3，a4};D為決策特征集，論域U在決策特征上等價劃分為U/D={D1，D2，D3}，即D1={x1，x2，x3}，D2={x4，x5，x6}，D3={x7，x8，x9，x10}，鄰域參數(shù)δ=β=0.25。通過鄰域信息決策表1對鄰域粗糙集模型和最大聯(lián)盟粗糙集模型進行不確定性度量。本文中的樣本（對象）的距離均采用歐氏距離進行計算。

a）根據(jù)定義1中的映射函數(shù)，對該鄰域信息系統(tǒng)進行標準化處理，結果如表2所示。

b）找到每個對象的鄰域類δ（xi）和最優(yōu)最大聯(lián)盟集MCbest（xi），結果如表3所示。

c）確定決策特征上等價劃分的上下近似集合，結果如表4所示。

d）不確定性評價的結果如表5所示。

由表5的評價結果可知，最大聯(lián)盟粗糙集的鄰域近似精度、領域信息熵、加權鄰域信息熵均優(yōu)于鄰域粗糙集模型?？梢钥闯?，相較于鄰域粗糙集模型，基于最大聯(lián)盟粗糙集提供了更精細的劃分信息，從而有效降低了邊界域的不確定性。

4.2 數(shù)據(jù)集上的實驗分析

為驗證基于最大聯(lián)盟粗糙集的三支聚類算法的有效性，本文選取了6組UCI數(shù)據(jù)集進行實驗，數(shù)據(jù)集的一些基本描述如表6所示。本次實驗采用Python編寫，在Windows 10企業(yè)版操作系統(tǒng)上運行，計算機配置為Intel CoreTM i5-4200U CPU，內存容量為16 GB，編碼環(huán)境選用Anaconda Spyder。

下面將本文所提出的基于最大聯(lián)盟粗糙集的三支聚類方法與基于k近鄰粗糙集的三支聚類方法［12］（算法1）、基于δ鄰域粗糙集的三支聚類方法［16］（算法2）、基于k最近鄰域粗糙集的三支聚類方法［10］（算法3）進行比較。其中，算法3是將文獻［10］提出的k最近鄰域粗糙集模型引入三支聚類框架所得到的聚類算法。本實驗根據(jù)映射函數(shù)對數(shù)據(jù)進行標準化處理，針對部分實驗數(shù)據(jù)集特征維度較多的問題，采取PCA方法降維之后，選用傳統(tǒng)K-means算法進行初始聚類，算法1和3所用到的近鄰參數(shù)k取值為3，算法2和本文算法中所需鄰域參數(shù)δ取值相同，且取值在0～1。

對實驗數(shù)據(jù)集分別進行三支聚類分析，得到如圖2～7所示的聚類結果對比圖。其中，每種顏色代表一個類簇，黑色五角星表示被劃分在邊界域的對象。在算法1～3和本文算法下，iris數(shù)據(jù)集邊界域內的樣本數(shù)量分別為9個、9個、7個和6個；wine數(shù)據(jù)集邊界域內的樣本數(shù)量分別為12個、15個、3個和1個；seeds數(shù)據(jù)集邊界域內的樣本數(shù)量分別為28個、15個、13個和8個；WDBC數(shù)據(jù)集邊界域內的樣本數(shù)量分別為17個、11個、7個和2個；Pima數(shù)據(jù)集邊界域內的樣本數(shù)量分別為23個、10個、10個和9個；ionosphere數(shù)據(jù)集邊界域內的樣本數(shù)量分別為11個、12個、4個和4個?？梢姡捎帽疚奶岢龅木垲愃惴ㄌ幚砀鱾€實驗數(shù)據(jù)集時，都能成功地將邊界域的樣本數(shù)量減至最少，可以更精確地劃分類與類的邊界域。

基于實驗所得的聚類結果，將本文算法與其他三種算法的評價指標進行對比，評價結果如表7所示。本文提出的基于最大聯(lián)盟粗糙集的三支聚類算法在wine、seed、WDBC和Pima數(shù)據(jù)集上的各個評價指標都有所提升，說明本文算法在這些數(shù)據(jù)集上的聚類效果明顯優(yōu)于其他三種聚類算法。在ACC評價指標方面，本文算法在wine和WDBC數(shù)據(jù)集上表現(xiàn)最為突出，聚類準確率分別為94.94%和92.44%，同時，在其他數(shù)據(jù)集上本文算法的準確率也都是最高的。在DBI評價指標方面，本文算法在wine、seed、WDBC和Pima數(shù)據(jù)集上都具有最小的DBI值，說明對于這四種數(shù)據(jù)集，本文算法所得到的聚類結果相同，簇內數(shù)據(jù)點更加緊密，而不同簇之間的距離更遠，聚類效果更好，然而，本文算法在iris數(shù)據(jù)集上的DBI值略遜于算法3，在ionosphere數(shù)據(jù)集上的DBI值略遜于算法2，但由于差值較小，對聚類效果的影響有限。在宏平均F1評價指標方面，本文算法的F1值都是最高的，表明本文算法相較于其他三種算法在不同類別上的分類性能最好。

在γ評價指標方面，本文算法也表現(xiàn)出極佳的效果，在各個數(shù)據(jù)集上該指標值均達到95%以上，說明本文算法對數(shù)據(jù)集中大部分數(shù)據(jù)點都進行了明確劃分，僅保留較少部分數(shù)據(jù)點于邊界域中，得到的聚類結果中所有正域的平均質量更高。在α和α*評價指標方面，相較于其他三種算法，本文算法在各個數(shù)據(jù)集上的指標值均最高，并且都大于90%，說明本文算法所得到的類簇平均質量和整體質量都更高，聚類效果更好。

4.3 參數(shù)δ分析

邊界域的劃分，是三支聚類效果和質量最直接的反映。本文算法中，鄰域半徑δ的取值直接影響三支聚類邊界域的劃分，在不同的δ取值下，算法得到的邊界域不同，從而影響三支聚類的精度。為了分析參數(shù)δ對邊界域產生的影響，本文針對各個實驗數(shù)據(jù)集，分別考察了鄰域參數(shù)δ在給定取值區(qū)間上產生邊界域對象的情況，并與同為基于δ鄰域技術的算法2進行對比，實驗結果如圖8～13所示。

隨著δ值的增加，算法2中的δ鄰域顆粒信息不斷擴大，使得該算法在三支劃分階段將較多的樣本歸于邊界域中，增大了聚類結果的不確定性。然而，本文算法所使用的鄰域顆粒信息MCbest，相對于鄰域參數(shù)δ的取值大小并不呈現(xiàn)單調關系，受參數(shù)影響較小，從而產生相對穩(wěn)定的三支聚類結果。從圖8～13可以看出，隨著δ值的增加，算法2得到的邊界域樣本個數(shù)呈明顯的上升趨勢，而本文算法得到的邊界域樣本個數(shù)保持相對穩(wěn)定，這表明本文算法在不同鄰域參數(shù)δ下可以得到較為穩(wěn)定的聚類結果，相較于算法2受鄰域參數(shù)δ的影響較小。

為進一步觀測同一類型算法在給定相同參數(shù)下的性能差異，本文給出了比較劃分正確率的概念。針對本文算法和算法2，在給定δ值下的比較正確率（CACCBN）定義如下：

CACCBN=NCPBNB算法2－NB本文算法

其中：NB表示算法產生的邊界域中包含的樣本數(shù)；NCPB表示兩比較算法的邊界域相對補集中被正確劃分到正域的樣本數(shù)。

當CACCBN＜0時，表明本文算法的邊界域包含更多樣本，本文算法性能低于算法2；當CACCBN>0時，表明本文算法的邊界域包含更少樣本，本文算法性能優(yōu)于算法2。CACCBN的絕對值越大，說明兩個算法差異性越大。當NB算法2=NB本文算法時，表明兩個算法產生的邊界域包含的樣本一樣多，算法性能接近，這時計算比較正確率CACCBN失去意義。結果如表8～13所示。

由表8～13的實驗結果可知，對于iris數(shù)據(jù)集，本文算法比較正確率整體較高，且當δ取值為0.022時，所有被處理的樣本均得到了正確的劃分，比較正確率達到100%；對于wine數(shù)據(jù)集，本文算法比較正確率均達到90%以上，且當δ取值為0.036、0.037、0.038和0.039時，比較正確率均達到100%；對于seeds數(shù)據(jù)集，除δ取值為0.012、0.013、0.014和0.015時比較正確率相對較低外，在其余六個取值上比較正確率均達到70%以上；對于WDBC數(shù)據(jù)集，本文算法比較正確率大多穩(wěn)定在60%～70%；對于Pima數(shù)據(jù)集，當δ取值為0.058時，比較正確率最高，達到90%；對于ionosphere數(shù)據(jù)集，本文算法的比較正確率最小值為80.65%，最大值為94.12%。因此，本文算法在處理邊界域樣本時，可以較大程度地將樣本劃分到正確類別。

綜上所述，本文基于最大聯(lián)盟粗糙集的三支聚類算法的聚類效果普遍更好，在保留邊界域信息的同時，有效提高了核心域的精度。

5 結束語

本文在給出標準化鄰域信息系統(tǒng)的定義基礎上，通過引入最大聯(lián)盟集的概念，定義了一種新的鄰域顆粒信息，使得樣本鄰域信息的刻畫更為細致。將該鄰域顆粒信息與粗糙集理論相結合，構造了最大聯(lián)盟粗糙集模型，該模型在一定程度上提高了正域的分類精度，降低了邊界域的不確定性。將最大聯(lián)盟粗糙集模型應用于三支聚類分析中，提出了基于最大聯(lián)盟粗糙集的三支聚類算法。在6個UCI數(shù)據(jù)集上進行對比實驗的結果表明，本文算法有效提高了聚類結果的準確率，所有正域的平均質量均超過95%，類簇的整體質量和平均質量均超過90%。本文算法在不同鄰域參數(shù)δ下邊界域樣本的比較正確率相對較高，可以較大程度地將邊界域樣本劃分到正確類別。

粗糙集理論為解決多屬性決策和不確定性問題提供了重要思路，然而在實際決策中，決策任務通常呈現(xiàn)出多視角、多粒度、多層次等復雜特性，單一結構化的決策方法有時無法應對這類復雜的決策問題。為此，下一步工作將考慮從粒計算的角度出發(fā)，從不同粒度層次中提取有效信息，探索更適用于解決實際決策問題的粗糙集模型和聚類方法。

參考文獻：

［1］Pawlak Z. Rough sets［J］. International Journal of Computer and Information Sciences， 1982， 11（5）： 341-356.

［2］Yao Yiyu， Yan Zhao. Attribute reduction in decision-theoretic rough set models［J］. Information Sciences， 2008， 178（17）： 3356-3373.

［3］Azam N， Yao Jingtao. Interpretation of equilibria in game-theoretic rough sets［J］. Information Sciences， 2015， 295： 586-599.

［4］Lin T Y. Neighborhood systems：a qualitative theory for fuzzy and rough sets［J］. Advances in Machine Intelligence and Soft Computing， 1997， 4： 132-155.

［5］Yao Yiyu. Relational interpretations of neighborhood operators and rough set approximation operators［J］. Information Sciences， 1998， 111（1-4）： 239-259.

［6］Wu Weizhi， Zhang Wenxiu. Neighborhood operator systems and approximations［J］. Information Sciences， 2002， 144（1-4）： 201-217.

［7］胡清華， 于達仁， 謝宗霞. 基于鄰域粒化和粗糙逼近的數(shù)值屬性約簡［J］. 軟件學報， 2008，19（3）： 640-649. （Hu Qinghua， Yu Daren， Xie Zongxia. Numerical attribute reduction based on neighborhood granulation and rough approximation［J］. Journal of Software， 2008，19（3）： 640-649.）

［8］Lin Guoping， Qian Yuhua， Li Jinjin. NMGRS： neighborhood-based multigranulation rough sets［J］. International Journal of Approximate Reasoning， 2012， 53（7）： 1080-1093.

［9］Wang Qi， Qian Yuhua， Liang Xinyan， et al. Local neighborhood rough set［J］. Knowledge-Based Systems， 2018， 153： 53-64.

［10］Wang Changzhong， Shi Yunpeng， Fan Xiaodong， et al. Attribute reduction based on k-nearest neighborhood rough sets［J］. Internatio-nal Journal of Approximate Reasoning， 2019， 106： 18-31.

［11］賀玲， 吳玲達， 蔡益朝. 數(shù)據(jù)挖掘中的聚類算法綜述［J］. 計算機應用研究， 2007， 24（1）： 10-13. （He Ling， Wu Lingda， Cai Yichao. Survey of clustering algorithms in data mining［J］. Application Research of Computers， 2007， 24（1）： 10-13.）

［12］Yao Yiyu. Three-way decisions with probabilistic rough sets［J］. Information Sciences， 2010， 180 （3）： 341-353.

［13］錢文彬， 彭莉莎， 王映龍， 等. 不完備混合決策系統(tǒng)的三支決策模型與規(guī)則獲取方法［J］. 計算機應用研究， 2020， 37（5）： 1421-1427. （Qian Wenbin， Peng Lisha， Wang Yinglong， et al. Three-way decisions model and rule acquisition method for incomplete decision systems［J］. Application Research of Computers， 2020， 37（5）： 1421-1427.）

［14］呂艷娜， 茍光磊， 張里博， 等. 深度置信網絡的代價敏感多粒度三支決策模型研究［J］. 計算機應用研究， 2023， 40（3）： 833-838. （Lyu Yanna， Gou Guanglei， Zhang Libo， et al. Research on cost-sensitive multi-granularity three-way decision model for deep belief network［J］. Application Research of Computers， 2023， 40（3）： 833-838.）

［15］于洪. 三支聚類分析［J］. 數(shù)碼設計， 2016， 5（1）： 31-35. （Yu Hong. Three-way cluster analysis［J］. Peak Data Science， 2016， 5（1）： 31-35.）

［16］劉強， 施虹， 王平心， 等. 基于鄰域的三支決策聚類分析［J］. 計算機工程與應用， 2019， 55（6）： 140-144. （Liu Qiang， Shi Hong， Wang Pingxin， et al. Three-way clustering analysis based on neighborhood［J］. Computer Engineering and Applications， 2019， 55（6）： 140-144.）

［17］萬仁霞， 王大慶， 苗奪謙. 基于三支決策的高斯混合聚類研究［J］. 重慶郵電大學學報：自然科學版， 2021， 33（5）： 806-815. （Wan Renxia， Wang Daqing， Miao Duoqian. Gaussian mixture clustering based on three-way decision［J］. Journal of Chongqing University of Posts and Telecommunications：Natural Science Edition， 2021， 33（5）： 806-815.）

［18］花遇春， 趙燕， 馬建敏. 基于共現(xiàn)概率的三支聚類模型［J］. 西北大學學報：自然科學版， 2022， 52（5）： 797-804. （Hua Yuchun， Zhao Yan， Ma Jianmin. Three-way clustering model based on co-occurrence probability［J］. Journal of Northwest University：Natural Science Edition， 2022， 52（5）： 797-804.）

［19］申秋萍， 張清華， 高滿， 等. 基于局部半徑的三支DBSCAN算法［J］. 計算機科學， 2023， 50（6）： 100-108.（Shen Qiuping， Zhang Qinghua， Gao Man， et al. Three-way DBSCAN algorithm based on local eps［J］. Computer Science， 2023， 50（6）： 100-108.）

［20］Pawlak Z. An inquiry into anatomy of conflicts［J］. Information Sciences， 1998， 109（1-4）： 65-78.

［21］Lang Guoming， Miao Duoqian， Cai Mingjie. Three-way decision app-roaches to conflict analysis using decision-theoretic rough set theory［J］. Information Sciences， 2017， 406： 185-207.

［22］郭淑蓉. 基于區(qū)間直覺模糊信息系統(tǒng)的三支沖突分析［D］. 太原： 山西師范大學， 2022. （Guo Shurong. Three-way conflict analysis based on interval-valued intuitionistic fuzzy information system［D］. Taiyuan： Shanxi Normal University， 2022.）

［23］羅珺方， 張碩， 胡夢君. 不完備異構沖突信息系統(tǒng)中的極大一致聯(lián)盟區(qū)間集族［J］. 計算機科學與探索， 2023， 11（3）： 1-12. （Luo Junfang， Zhang Shuo， Hu Mengjun. A family of maximum consistent alliances interval sets in an incomplete heterogeneous conflict information systems［J］. Computer Science and Exploration， 2023， 11（3）： 1-12.）

［24］陳玉明， 曾志強， 田翠華. 鄰域粗糙集中不確定性的熵度量方法［J］. 計算機科學與探索， 2016，10（12）： 1793-1800. （Chen Yuming， Zeng Zhiqiang， Tian Cuihua. Uncertainty measures using entropy and neighborhood rough sets［J］. Computer Science and Technology， 2016， 10（12）： 1793-1800.）

［25］Uysal A K. On two-stage feature selection methods for text classification［J］. IEEE Access， 2018， 6： 43233-43251.

［26］Maji P， Pal S K. RFCM： a hybrid clustering algorithm using rough and fuzzy sets［J］. Fundamenta Informaticae， 2007， 80（4）： 475-496.

［27］Zhang Kai. A three-way C-means algorithm［J］. Applied Soft Computing Journal， 2019， 82： 105536.

［28］梁海龍， 謝珺， 續(xù)欣瑩， 等. 新的基于區(qū)分對象集的鄰域粗糙集屬性約簡算法［J］. 計算機應用， 2015，35（8）： 2366-2370. （Liang Hailong， Xie Jun， Xu Xinying， et al. New attribute reduction algorithm of neighborhood rough set based on distinguished object set［J］. Journal of Computer Applications， 2015，35（8）： 2366-2370.）