基于粒球的三支聚類方法

摘" 要： 針對(duì)硬聚類中樣本均被強(qiáng)制劃分到一個(gè)類簇，沒(méi)有考慮信息具有不確定性而導(dǎo)致決策風(fēng)險(xiǎn)提高的問(wèn)題，將粒球與三支聚類結(jié)合，提出了一種基于粒球的三支聚類算法.通過(guò)對(duì)每一個(gè)數(shù)據(jù)簇建立一個(gè)粒球模型，以自適應(yīng)的方式為每個(gè)粒球?qū)ふ移浣徚Ｇ?根據(jù)近鄰粒球的情況來(lái)將粒球劃分為穩(wěn)定域與活動(dòng)域，以賦予不同的權(quán)重將穩(wěn)定域與活動(dòng)域中的樣本數(shù)據(jù)進(jìn)行更新迭代.穩(wěn)定域被認(rèn)定為該類的核心域，活動(dòng)域?yàn)樵擃惖倪呴g域.采用不同的UCI數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明：所提算法較好的解決了不確定性信息對(duì)于決策風(fēng)險(xiǎn)提高的問(wèn)題，驗(yàn)證了該算法的有效性.

關(guān)鍵詞： 三支聚類；粒球；穩(wěn)定域；活動(dòng)域

中圖分類號(hào)：TP391""" 文獻(xiàn)標(biāo)志碼：A""""" 文章編號(hào)：1673-4807（2024）05-057-06

DOI：10.20061/j.issn.1673-4807.2024.05.009

收稿日期： 2023-07-12""" 修回日期： 2021-04-29

基金項(xiàng)目： 國(guó)家自然科學(xué)基金項(xiàng)目（62076111， 61773012）；江蘇省高校自然科學(xué)基金項(xiàng)目（15KJB110004）

作者簡(jiǎn)介： 韓興雨（2000—），男，碩士研究生

*通信作者： 孟義平（1979—），女，副教授，研究方向?yàn)閼?yīng)用數(shù)學(xué)、三支決策.E-mail：ypmeng@just.edu.cn

引文格式： 韓興雨，朱金，孟義平，等.基于粒球的三支聚類方法［J］.江蘇科技大學(xué)學(xué)報(bào)（自然科學(xué)版），202 38（5）：57-62.DOI：10.20061/j.issn.1673-4807.2024.05.009.

Three-way clustering based on granular-ball

HAN Xingyu1，ZHU Jin2，MENG Yiping 2*， WANG Pingxin2

（1.School of Computer， Jiangsu University of Science and Technology， Zhenjiang 212003， China）

（2.School of Science， Jiangsu University of Science and Technology， Zhenjiang 212100， China）

Abstract：In order to solve the problem of traditional clustering where samples are forcibly divided into one cluster without considering information uncertainty， thereby increasing decision risk. In this paper， a three-way clustering algorithm based on granular-ball is proposed by combining granular-ball with three-way clustering. The algorithm establishes a granular-ball model for each data cluster， and finds its neighboring granular-ball for each granular-ball in an adaptive way. The granular-ball is divided into stable area and active area according to the situation of the neighboring granular-ball， and then the sample data in the stable area and active area are updated and iterated by giving different weights. The stable area is identified as the core region of this class， and the active area is the fringe region of this class. Experiments are conducted using different UCI datasets， and the experimental results show that the proposed algorithm effectively solves the problem of increasing decision risk due to uncertain information， verifying the effectiveness of the algorithm.

Key words：three-way clustering， granular-ball， stable area， active area

聚類分析在數(shù)據(jù)挖掘和機(jī)器學(xué)習(xí)領(lǐng)域有著廣泛的應(yīng)用，如圖像處理［1］、目標(biāo)檢索［2］等.傳統(tǒng)的聚類方法其大多屬于硬聚類，樣本所在的類簇之間有著清晰的邊界，不存在既屬于一個(gè)類簇又屬于另外不同類簇的對(duì)象.在實(shí)際處理中，考慮到不確定性信息的情況，將樣本中的對(duì)象強(qiáng)制劃分到一個(gè)類簇當(dāng)中的決策是抱有風(fēng)險(xiǎn)的.認(rèn)識(shí)到傳統(tǒng)聚類方法的局限性，文獻(xiàn)［3］提出三支決策聚類，通過(guò)將類簇劃分為核心域、邊界域和瑣碎域來(lái)有效的降低信息不充分時(shí)的決策錯(cuò)誤率，有效提高了聚類結(jié)果的可解釋性.

三支聚類［4］用核心域和邊界域來(lái)描述一個(gè)簇.這兩個(gè)域?qū)?shù)據(jù)集分成3個(gè)部分，分別對(duì)應(yīng)了3種隸屬關(guān)系：屬于，不屬于和可能屬于.三支聚類自提出以來(lái)，得到快速發(fā)展取得了大量的成果［5-8］.文獻(xiàn)［9］針對(duì)聚類集成的樣本穩(wěn)定性概念，發(fā)現(xiàn)了穩(wěn)定關(guān)系的樣本集，提出基于樣本穩(wěn)定性的集成聚類方法.文獻(xiàn)［10］將數(shù)學(xué)形態(tài)學(xué)中腐蝕和膨脹思想引入聚類，給出一種基于收縮和膨脹的三支聚類框架，解決了簇類劃分中閾值固定的問(wèn)題.

粒計(jì)算是將信息?；圆煌６冉鉀Q問(wèn)題的方法.?；蓮臉?gòu)建或分解的方向進(jìn)行，將底層的粒合并為更高的粒是構(gòu)建，反之則是分解.文中引入多粒度中粒計(jì)算與聚類中簇構(gòu)成的粒球模型［11-12］，提出基于粒球的三支聚類方法.憑借數(shù)據(jù)簇構(gòu)建的粒球及其近鄰粒球，將通過(guò)近鄰粒球判斷出的粒球穩(wěn)定域定義為核心域，活動(dòng)域則定義為邊界域.

1" 預(yù)備知識(shí)

1.1" 三支聚類

若給定包含n個(gè)樣本對(duì)象的數(shù)據(jù)集U={x1，x2，...，xn}，聚類數(shù)為k，則傳統(tǒng)硬聚類的聚類結(jié)果是C={C1，C2，...，Cn}，其中任意類簇滿足：

Ci≠""" i=1，…，k∪ki=1Ci=UCi∩Cj=i≠j

在上述條件下，整個(gè)樣本被劃分成的類簇中不存在空集，不同類簇中也不存在公共元素.每個(gè)樣本對(duì)象都被強(qiáng)制劃分到一個(gè)類簇當(dāng)中，其所在的類簇間具有清晰的邊界.但信息具有不確定性，則將樣本對(duì)象強(qiáng)制劃分到一個(gè)類簇當(dāng)中會(huì)降低聚類結(jié)果的質(zhì)量.為了解決傳統(tǒng)聚類方法的弊端，將三支決策思想引入到聚類中，將一定屬于某個(gè)對(duì)象的元素置于核心域Co（Ci）內(nèi)，將不確定的元素置于邊界域Fr（Ci）內(nèi)，瑣碎域Tr（Ci）則代表一定不屬于某個(gè)對(duì)象的元素.由此，一個(gè)類中的樣本對(duì)象與簇的關(guān)系則被分為：一定屬于該類簇、一定不屬于該類簇和可能屬于該類簇.

當(dāng)滿足以下條件：

Co（Ci）∪Tr（Ci）∪Fr（Ci）=U

Co（Ci）∩Tr（Ci）=

Co（Ci）∩Fr（Ci）=

Fr（Ci）∩Tr（Ci）=

數(shù)據(jù)集U的三支聚類表示結(jié)果為：

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

若Fr（Ci）=，則簇類被劃分Co（Ci）和Tr（Ci）=U－Co（Ci）.三支聚類則變成為硬聚類.

1.2" k-means算法

k-means算法首先隨機(jī)地選擇k個(gè)數(shù)據(jù)對(duì)象，將其作為初始類簇中心.對(duì)剩余的數(shù)據(jù)，依據(jù)每個(gè)數(shù)據(jù)與其類簇中心的的距離，分配給與之距離最近的類簇.接著計(jì)算各個(gè)類簇中數(shù)據(jù)的平均值作為新的聚類中心，不斷重復(fù)以上過(guò)程，其最終結(jié)果是將無(wú)標(biāo)簽的數(shù)據(jù)集自動(dòng)劃分成獨(dú)立且緊湊的k個(gè)類簇.

1.3" 粒球的生成與穩(wěn)定域和活動(dòng)域的劃分

在執(zhí)行k-means算法后，數(shù)據(jù)會(huì)以歐氏距離為相似度指標(biāo)，將每個(gè)數(shù)據(jù)對(duì)象劃分置與其距離最近的類簇內(nèi).每個(gè)數(shù)據(jù)對(duì)象都包含在以聚類中心為形心，距離聚類中心最遠(yuǎn)數(shù)據(jù)到形心的距離為半徑的區(qū)域內(nèi).

定義1" 在包含n個(gè)樣本對(duì)象的數(shù)據(jù)集U={x1，x2，...，xn}中，對(duì)于任意一個(gè)粒球Ci，當(dāng)前粒球的球心定義為：

ci=1Ci∑x∈Cix（1）

式中：|Ci|為當(dāng)前粒球Ci中的樣本數(shù)量；x為當(dāng)前粒球Ci中的樣本.

定義2" 對(duì)于任意一個(gè)粒球Ci，粒球Ci的半徑定義為：

ri=max{dist（x，ci）|x∈Ci}（2）

式中：dist（）為x與ci之間的歐氏距離；x為當(dāng)前粒球Ci中的樣本；ci表示為粒球Ci的球心.具體情況如圖 其中三角形代表粒球球心，圓形代表粒球中的樣本.

定義3" 給定任意兩個(gè)粒球Ci與Cj.其中ci和cj分別表示粒球Ci與Cj的球心，ri表示為粒球Ci的半徑，若滿足以下條件：

rigt;12‖ci－cj‖（3）

則稱Cj為Ci的近鄰粒球.

由定義3可知，若滿足條件rigt;12‖ci－cj‖，則稱Cj為Ci的近鄰粒球.但此近鄰關(guān)系不具備對(duì)稱性.若Cj為Ci的近鄰粒球，但不一定同時(shí)滿足Ci為Cj的近鄰粒球的情況.因此，任意兩個(gè)粒球Ci與Cj的近鄰關(guān)系可分為以下3種：

（1） 粒球Ci與Cj互為近鄰粒球；

（2） 粒球Ci為Cj的近鄰粒球，但Cj不為Ci的近鄰粒球；

（3） 粒球Ci與Cj互不為近鄰粒球；

具體情況如圖2.

圖2中，直線為兩粒球球心的連線，虛線為兩粒球球心連線的中垂線位置.以粒球C1為例，C1與C2互為近鄰粒球；C3為C1的近鄰粒球，但C1不為C3的近鄰粒球；粒球C1與C4互不為近鄰粒球.

定理1" 給定任意兩個(gè)粒球Ci與Cj，ci和cj分別表示粒球Ci與Cj的球心.若Ci為粒球C的近鄰粒球，則粒球C中的數(shù)據(jù)樣本存在被調(diào)整到粒球Ci中的可能性.若Cj不為粒球C的近鄰粒球，則粒球C中的數(shù)據(jù)樣本不存在被調(diào)整到粒球Ci中的可能性.

證明：設(shè)粒球C的半徑為r，球心為c.

（1） 若Ci為粒球C的近鄰粒球，則rgt;12‖c－ci‖.又r=max{dist（x，c）|x∈C}，x為當(dāng)前類簇中的樣本對(duì)象.則必定x∈C，使得‖x-c‖gt;12‖c－ci‖.假設(shè)此數(shù)據(jù)樣本x位于線段cci上，則有‖x-c‖+‖x－ci‖=‖c－ci‖.則‖x-c‖gt;12‖x-c‖+12‖x－ci‖，即‖x-c‖gt;‖x－ci‖.

（2） 若Cj不為粒球C的近鄰粒球，則r≤12·‖c－cj‖.又在粒球C中，x∈C，‖c－x‖≤r，則有

‖c－x‖≤r≤12‖c－cj‖=12‖c－x+x－cj‖≤

12‖c－x‖+12‖x－cj‖

‖c－x‖≤12‖c－x‖+12‖x－cj‖

‖c－x‖≤‖x－cj‖

由此可知，粒球C中的某些樣本對(duì)象在滿足一定條件下，存在與粒球C相比距離其近鄰粒球更近的情況，而對(duì)于其非近鄰粒球，該情況不會(huì)發(fā)生.在圖3中，對(duì)于粒球C1中的數(shù)據(jù)不存在重新分配到非近鄰粒球C3中的可能性.而對(duì)于近鄰粒球C 粒球C1右上方的數(shù)據(jù)距離C2更近.

定義4" 給定任意一個(gè)粒球Ci，其近鄰粒球球心的集合為{Nci}.若{Nci}≠，則對(duì)于球心集合內(nèi)的所屬任意粒球Cj，球心cj∈{Nci}，有以ci為球心，12min（‖ci－cj‖）cj∈{Nci}為半徑所覆蓋的“穩(wěn)定域”，將粒球Ci中除穩(wěn)定域以外的區(qū)域定義為“活動(dòng)域”.若{Nci}=，則整個(gè)粒球Ci都為“穩(wěn)定域”.具體情況如圖4.

如圖 粒球C1的近鄰粒球球心集合為{Nc1}={c2}，不為空集.則存在以c1為球心，半徑為12c1c2所覆蓋成的“穩(wěn)定域”.

定理2" 在當(dāng)前的迭代輪次中，粒球中穩(wěn)定域所覆蓋的樣本數(shù)據(jù)無(wú)需與其他任意粒球比較到各自球心的距離.

證明：給定任意一個(gè)粒球Ci，其近鄰粒球球心的集合為{Nci}.設(shè)x為粒球Ci穩(wěn)定域中的任意樣本數(shù)據(jù).則有：

‖x-ci‖≤12min（‖ci－cj‖）cj∈{Nci}≤12（‖ci－x‖）+

12min（‖x－cj‖）cj∈{Nci}

‖x-ci‖≤12（‖ci－x‖）+12min（‖x－cj‖）cj∈{Nci}

‖x-ci‖≤min（‖x－cj‖）cj∈{Nci}.

綜上所述，在確定粒球Ci的“穩(wěn)定域”后，其所在范圍內(nèi)的任意數(shù)據(jù)，在本輪的迭代次序中無(wú)需與其他任何粒球中的樣本對(duì)象比較到各自球心的距離.即粒球Ci的“穩(wěn)定域”內(nèi)所覆蓋的樣本對(duì)象距離所屬球心ci是最近的.

2" 基于粒球的三支聚類算法

2.1" 粒球模型的建立與近鄰粒球的搜索

在輸入數(shù)據(jù)集后，由包含n個(gè)樣本對(duì)象的數(shù)據(jù)集U={x1，x2，...，xn}在進(jìn)行一次k-means迭代過(guò)程后，將原本的數(shù)據(jù)集U劃分成k個(gè)簇類：U={V1，V2，...，Vk}，形成初始的聚類結(jié)果.而任意類簇Vi內(nèi)的樣本對(duì)象都被包含在以其聚類中心為形心，距離形心的最遠(yuǎn)數(shù)據(jù)到形心的距離為半徑的覆蓋區(qū)域內(nèi).因此，可將任意類簇Vi轉(zhuǎn)化成粒球Ci，則數(shù)據(jù)集U進(jìn)一步劃分成為由粒球構(gòu)成的k個(gè)簇類：U={C1，C2，...，Ck}.其球心ci的定義如式（1），半徑ri如式（2）.

在迭代過(guò)程當(dāng)中，為了避免當(dāng)k值過(guò)大時(shí)所引發(fā)的大量不必要的距離計(jì)算，根據(jù)式（3）判斷粒球C的近鄰與非近鄰粒球來(lái)對(duì)數(shù)據(jù)進(jìn)行預(yù)處理.由定理1可知，若Ci為粒球C的近鄰粒球，則在粒球C中，可能存在距離Ci更近的數(shù)據(jù)樣本.說(shuō)明粒球C中的數(shù)據(jù)樣本存在被調(diào)入到Ci的可能性，這一部分的數(shù)據(jù)計(jì)算是必要的.但若Cj不為粒球C的近鄰粒球，則位于粒球C中的數(shù)據(jù)樣本到C的距離均小于等于到Cj的距離.即粒球C中的數(shù)據(jù)樣本無(wú)需調(diào)整到非近鄰粒球當(dāng)中去，由此可減少了一部分冗余的計(jì)算量.

2.2" 粒球的更新

將由進(jìn)行一次k-means迭代所生成的初始聚類結(jié)果構(gòu)成相應(yīng)的粒球模型，通過(guò)搜索粒球?qū)?yīng)的近鄰粒球來(lái)避免不必要的冗余計(jì)算與劃分不同區(qū)域.這一步將對(duì)粒球中的樣本數(shù)據(jù)進(jìn)行更新.

對(duì)于以歐式距離作為相似度指標(biāo)所形成的任意粒球Ci，其“活動(dòng)域”中的數(shù)據(jù)可能存在距離相應(yīng)近鄰粒球更近的情況，所以仍需計(jì)算到各個(gè)近鄰粒球球心之間的距離，按就近原則分配到相應(yīng)的粒球當(dāng)中，并且進(jìn)行數(shù)據(jù)更新過(guò)后的粒球也必須按定義1和定義2重新構(gòu)建粒球模型.鑒于其“穩(wěn)定域”內(nèi)的樣本數(shù)據(jù)在本次迭代過(guò)程中不會(huì)調(diào)整到其他粒球內(nèi)，這部分?jǐn)?shù)據(jù)所構(gòu)成的類簇具有較好的獨(dú)立且緊湊的特性，因此賦予較大的權(quán)重wCo（Ci）.而更新后的“活動(dòng)域”中的樣本數(shù)據(jù)則與之相反，賦予較低的權(quán)重wFr（Ci）′，其中wCo（Ci）0. wCo（Ci）+wFr（Ci）′=1.則粒球Ci的球心ci′以及半徑ri′更新具體表示為：

ci′=wCo（Ci）∑x∈Co（Ci）x+wCo（Ci）∑x∈Fr（Ci）′xwCo（Ci）Co（Ci）+wFr（Ci）′Fr（Ci）′（4）

ri′=max{dist（x，ci′）|x∈Co（Ci）∪Fr（Ci）′}（5）

式中：Co（Ci）為粒球Ci“穩(wěn)定域”中的樣本數(shù)量；Fr（Ci）′為原“活動(dòng)域”中的樣本對(duì)象進(jìn)行重新就近分配后的新“活動(dòng)域”中的樣本數(shù)量.

2.3" 粒球區(qū)域的劃分

由定義4可知，給定任意一個(gè)粒球Ci，通過(guò)判斷其近鄰粒球的情況，可以將整個(gè)粒球Ci所覆蓋的區(qū)域分成“活動(dòng)域”與“穩(wěn)定域”.而根據(jù)定理2的證明，在粒球Ci“穩(wěn)定域”中的任意樣本數(shù)據(jù)x到球心ci的距離，均小于等于其到任意近鄰粒球球心的距離.即當(dāng)前迭代過(guò)程中，粒球“穩(wěn)定域”中的樣本無(wú)需進(jìn)行調(diào)整.

由此，為了刻畫(huà)數(shù)據(jù)的不確定性，把粒球Ci“穩(wěn)定域”定義為該類簇的核心域Co（Ci），具體表示為：

Co（Ci）={x∈U|x∈Ci∧dist（x，ci）≤

12min（‖ci－cj‖）cj∈{Nci}}（6）

將“活動(dòng)域”定義為該類簇的邊界域Fr（Ci），具體表示為：

Fr（Ci）={x∈U|x∈Ci∧dist（x，ci）gt;

12min（‖ci－cj‖）cj∈{Nci}}（7）

將其余區(qū)域定義為該類簇的瑣碎域Tr（Ci），具體表示為：

Tr（Ci）=U－Co（Ci）－Fr（Ci）（8）

經(jīng)過(guò)以上操作，得到了該類簇基于粒球Ci所劃分成的核心域、邊界域和瑣碎域.則數(shù)據(jù)集U的三支聚類表示為：

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

2.4" 基于粒球的三支聚類（3WG）算法流程

基于粒球的三支聚類算法基本思想是采用多粒度中粒計(jì)算與聚類中簇構(gòu)成的粒球模型，憑借粒球模型做出不同的區(qū)域劃分以此更新迭代其中的樣本數(shù)據(jù).即對(duì)原始數(shù)據(jù)進(jìn)行粒球建模，由其相應(yīng)的近鄰粒球減少不必要計(jì)算的同時(shí)區(qū)分出粒球中的“穩(wěn)定域”與“活動(dòng)域”.首先對(duì)數(shù)據(jù)進(jìn)行一次k-means迭代，由初始聚類結(jié)果得出相應(yīng)的粒球模型.其次便是通過(guò)粒球模型尋找其近鄰粒球來(lái)劃分出粒球中的不同區(qū)域，無(wú)需重新計(jì)算分配穩(wěn)定域中的數(shù)據(jù).對(duì)于“穩(wěn)定域”中的數(shù)據(jù)樣本賦予較大的權(quán)重，“活動(dòng)域”與之相反，這樣在迭代過(guò)程中可以有效降低活動(dòng)域中的數(shù)據(jù)重新分配與粒球模型的更新對(duì)聚類結(jié)果的影響.為了較好的刻畫(huà)數(shù)據(jù)的不確定性，對(duì)每個(gè)類簇進(jìn)行粒球建模所劃分成的“穩(wěn)定域”與“活動(dòng)域”得到每個(gè)類的核心域和邊界域，由此獲得數(shù)據(jù)集的三支聚類結(jié)果.算法1給出了基于粒球的三支聚類算法流程.

算法1 ： 3WG算法

輸入：" 數(shù)據(jù)集U，簇?cái)?shù)目k，權(quán)重w

輸出：

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

1．完成一次標(biāo)準(zhǔn)的k-means迭代

2．根據(jù)初步的聚類結(jié)果，根據(jù)公式（1）、（2）構(gòu)建出粒球模型

3. 設(shè)置迭代次數(shù)n

4. repeat

5. for i=1... k" ∥ 對(duì)每個(gè)粒球進(jìn)行遍歷

6. 通過(guò)rigt;12‖ci－cj‖判斷粒球Ci的近鄰粒球

7. 對(duì)粒球Ci以12min（‖ci－cj‖）cj∈{Nci}為半徑，ci為球心構(gòu)成“穩(wěn)定域”.其余區(qū)域中的樣本數(shù)據(jù)構(gòu)成“活動(dòng)域”并按距離就近分配到其余粒球

8. 更新除粒球Ci之外，被新分配樣本數(shù)據(jù)的粒球.其球心不變，更新半徑及其所屬數(shù)據(jù).

9. 根據(jù)式（4）、（5）更新粒球Ci的球心與半徑

10. until 所有的球心不再發(fā)生變化或迭代次數(shù)達(dá)到事先設(shè)定的閾值

11. 提取Co（Ci）={x∈U|x∈Ci∧dist（x，ci）≤

12min（‖ci－cj‖）cj∈{Nci}}，得到Ci的核心域

12. 提取Fr（Ci）={x∈U|x∈Ci∧dist（x，ci）gt;12min（‖ci－cj‖）cj∈{Nci}}，得到Ci的邊界域

13. 得到最終聚類結(jié)果：

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

3" 實(shí)驗(yàn)分析

為了驗(yàn)證3WG算法的有效性，采用了5組UCI數(shù)據(jù)進(jìn)行實(shí)驗(yàn)，數(shù)據(jù)集信息如表 將基于粒球的三支聚類算法與傳統(tǒng)的聚類k-means和譜聚類進(jìn)行SC、DBI和ACC聚類指標(biāo)的對(duì)比.

將每個(gè)類簇的穩(wěn)定域作為核心域，活動(dòng)域作為邊界域獲得數(shù)據(jù)集的三支聚類結(jié)果并計(jì)算聚類指標(biāo)SC、DBI和ACC.SC的范圍為［- 1］，同類別樣本距離越相近不同類別樣本距離越遠(yuǎn)，SC值越高，其中負(fù)值代表該樣本數(shù)據(jù)不應(yīng)被分配到該類的程度，正值則與之相反，零表示樣本剛好位于兩個(gè)不同類簇之間.DBI與ACC指標(biāo)值域?yàn)椋?1］，DBI越小意味著類內(nèi)距離越小，同時(shí)類間距離越大.ACC越大表示算法的聚類結(jié)果與真實(shí)聚類結(jié)果越接近.實(shí)驗(yàn)結(jié)果如表2.

為了進(jìn)一步驗(yàn)證該算法的有效性，將算法得到核心域內(nèi)的數(shù)據(jù)標(biāo)簽與真實(shí)標(biāo)簽做對(duì)比.表3為僅計(jì)算聚類結(jié)果中核心域內(nèi)數(shù)據(jù)的準(zhǔn)確率與整個(gè)類簇準(zhǔn)確率在聚類指標(biāo)SC、DBI和ACC上的對(duì)比結(jié)果.

觀察表2、3的數(shù)據(jù)對(duì)比結(jié)果，通過(guò)比較SC的值可以發(fā)現(xiàn)，算法3WG在大多數(shù)數(shù)據(jù)集上表現(xiàn)出來(lái)的性能都優(yōu)于其他2個(gè)算法.以數(shù)據(jù)集Ionosphere為例，在通過(guò)3WG算法進(jìn)行聚類后SC的值為0.411 2.利用k-means算法和譜聚類算法進(jìn)行聚類后，SC的值分別為0.409 7和0.365 7.輪廓系數(shù)SC的值代表著所有樣本輪廓系數(shù)的平均值，當(dāng)同類別的樣本越近，不同類別的樣本越遠(yuǎn)時(shí)值越大.而3WG算法中通過(guò)構(gòu)建粒球模型劃分類簇，通過(guò)賦予核心域較大權(quán)重，邊界域賦予較小權(quán)重進(jìn)行數(shù)據(jù)更新，使聚類之間的分離程度得到提高，聚類內(nèi)的分散程度得到降低.觀察DBI的值可以發(fā)現(xiàn)，3WG算法在Banknote上沒(méi)有達(dá)到預(yù)期結(jié)果，在其他數(shù)據(jù)集上得到較好的值.這是由于DBI越小則表示類內(nèi)距離越小同時(shí)類間距離越大，而粒球模型中的數(shù)據(jù)是以聚類中心為球心，到球心距離最遠(yuǎn)的樣本到聚類中心的距離為半徑所覆蓋的區(qū)域，其三支聚類結(jié)果的表示在不同粒球間存在重疊區(qū)域.而比較ACC的值不難得出，3WG算法在大多數(shù)數(shù)據(jù)集上的表現(xiàn)都勝于其他2個(gè)算法.再將粒球中的穩(wěn)定域作為整個(gè)類簇計(jì)算聚類評(píng)價(jià)值時(shí)，發(fā)現(xiàn)ACC在大多數(shù)據(jù)集上都有提升.

綜上所述，3WG算法能較好地對(duì)具有不確定信息的數(shù)據(jù)進(jìn)行聚類，其三支聚類的結(jié)果能更好地展現(xiàn)出聚類結(jié)構(gòu)，改善聚類性能.

4" 結(jié)論

文中將多粒度中粒計(jì)算與聚類中簇構(gòu)成的粒球模型與三支聚類進(jìn)行結(jié)合，給出了一種基于粒球的三支聚類方法，通過(guò)構(gòu)建的粒球模型尋找其近鄰粒球，在減少了冗余計(jì)算的同時(shí)憑借近鄰粒球的情況將粒球劃分成不同區(qū)域.粒球的“穩(wěn)定域”作為核心域，“活動(dòng)域”作為邊界域，從而獲得類簇的三支聚類結(jié)果.實(shí)驗(yàn)結(jié)果表明，通過(guò)賦予不同區(qū)域不同的權(quán)重，以加權(quán)平均值的方式迭代球心及其樣本數(shù)據(jù)，使聚類之間的分離程度得到提高，并且聚類內(nèi)的分散程度得到降低，提升了聚類的各項(xiàng)性能.該算法中仍存在需要改進(jìn)的地方，如三支聚類結(jié)果的表示在不同粒球間存在重疊區(qū)域，這種情況會(huì)使不同類簇間的聚集程度得到提高，降低了聚類結(jié)果的質(zhì)量.另外，如何豐富參數(shù)的設(shè)置來(lái)更好地提取數(shù)據(jù)的特征也是未來(lái)研究的內(nèi)容之一.

參考文獻(xiàn)（References）

［1］" DING W， LIU Z， ZHANG F， et al. Research on visual image processing and edge detection method of micro flapping wing flying robot based on cluster analysis［C］∥Seventh Asia Pacific Conference on Optics Manufacture and 2021 International Forum of Young Scientists on Advanced Optical Manufacturing （APCOM and YSAOM 2021）. USA：SPIE， 2022， 12166： 493-500.

［2］" LAO G， LIU S， TAN C， et al. Three degree binary graph and shortest edge clustering for re-ranking in multi-feature image retrieval［J］. Journal of Visual Communication and Image Representation，2021，80：103282.

［3］" YAO Y. Three-way decisions with probabilistic rough sets ［J］. Information Sciences，2010，180（3）：341-353.

［4］" YU H. A framework of three-way cluster analysis［C］∥Proceedings of the Rough Sets. Poland： Springer， 2017：300-312.

［5］" YU H， ZHANG C， WANG G. A tree-based incremental overlapping clustering method using the three-way decision theory ［J］. Knowledge-Based Systems， 2016， 91： 189-203.

［6］" 施虹， 楊鑫，王平心.改進(jìn)的均值插補(bǔ)不完備數(shù)據(jù)聚類算法［J］.江蘇科技大學(xué)學(xué)報(bào)（自然科學(xué)版），2020，34（4）： 51-56.

［7］" YU H， CHEN L Y， YAO J T. A three-way density peak clustering method based on evidence theory［J］. Knowledge-Based Systems， 2021， 211：106532.

［8］" 凡嘉琛， 王平心， 楊習(xí)貝. 基于三支決策的密度敏感譜聚類［J］. 山東大學(xué)學(xué)報(bào)（理學(xué)版），2022， 57（11）：10-17.

［9］" 李飛江，錢(qián)宇華，王婕婷，等.基于樣本穩(wěn)定性的聚類方法［J］.中國(guó)科學(xué)：信息科學(xué)，2020，50（8）：1239-1254.

［10］" WANG P， YAO Y. CE3： A three-way clustering method based on mathematical morphology ［J］. Knowledge-Based Systems， 2018， 155： 54-65.

［11］" JI X， PENG J H， ZHAO P， et al. Extended rough sets model based on fuzzy granular ball and its attribute reduction［J］. Information Sciences，202 640：119071.

［12］" PENG X， WANG P， XIA S， et al. VPGB： A granular-ball based model for attribute reduction and classification with label noise［J］. Information Sciences， 2022， 611： 504-521.

（責(zé)任編輯：曹莉）