多粒度粒球粗糙集模型

蔣珊珊 林國平 林藝東 寇毅

摘要 基于粒球計算的粗糙集理論作為知識發現和數據挖掘的重要工具之一，已成功地應用于標記預測、屬性約簡等。而現有的粒球粗糙集模型僅僅是從單粒度出發，無法從多粒度角度對數據進行分析和處理，實際生活中仍有很多應用場景需從多粒度角度進行思考。將粒球計算思想結合到多粒度粗糙集模型，提出了多粒度粒球粗糙集模型，并討論了該模型的相關性質。該模型通過純度的設定對數據進行粒球劃分，能夠有效地刻畫數據之間的內在聯系，以此設計多粒度粒球粗糙集的正域生成算法。實驗分析表明該模型的可行性和有效性。

關鍵詞 粒球計算;粒球粗糙集;多粒度粗糙集;純度

Multi-granulation rough set model based on granular-ball computing

Abstract As one of the important tools for knowledge discovery and data mining， rough set theory based on granular-ball computing has been successfully applied to label prediction and attribute reduction. However， the existing granular-ball rough set models only consider? a single granulation， and cannot analyze and process data from a multi-granulation， and there are still

many application scenarios that need to be considered from the perspective of multi-granulation. Based on this， this paper proposes a multi-granulation rough set based on granular-ball computing by embedding the idea of granular-ball in the multi-granulation rough set model， and discusses the relevant properties of the model. The model divides the data by setting the purity， which can effectively depict the internal relationship between the data， and thus design a position region generation algorithm for multi-granulation granular-ball rough set. Experimental analysis shows the feasibility and effectiveness of this model.

Keywords granular-ball computing; granular-ball rough set; multi-granulation rough set; purity

粗糙集理論是Pawlak［1］于1982年提出的一種能夠有效分析和處理不精確、不一致、不完整信息的數學方法。粗糙集理論［2-7］已經廣泛地應用于模式識別、數據挖掘、機器學習、決策支持系統等領域。為了處理不同類型的信息系統，許多學者將Pawlak粗糙集模型擴充為容差關系、相似關系、限制容差關系、優勢關系和模糊關系粗糙集等［8-11］。然而，經典粗糙集模型基于單個不可分辨二元關系的單一粒度框架，無法從多粒度、多層次的角度對數據進行分析和處理，單一粒度框架下的數據處理方法已經不能滿足實際應用的需求?；诖?，Qian等人從粒計算的角度出發，考慮多個二元關系，將單粒度粗糙集模型拓展至多粒度結構，提出多粒度粗糙集思想，建立基于“求同存異”思想的樂觀多粒度粗糙集和基于“求同排異”思想的悲觀多粒度粗糙集［12-14］。

此外，傳統的粗糙集模型只能處理離散數據，而現實中的數據多為連續數據，離散化不可避免地造成信息的丟失。為了解決這一問題，Hu等提出了鄰域粗糙集，利用鄰域來描述樣本之間的關系，能夠有效地處理連續型數據［15］?；谒闹T多優勢，許多學者對其進行了相關的研究和改進。李和謝提出了一種基于鄰域粗糙集的特征子集增量式更新NRS加速方法［16］。胡和趙等根據樣本的分布提出了基于不確定性和鄰域關系粗糙集的增量屬性約簡方法［17］。彭和劉等設計了一個適應度函數，它結合了數據集和分類器的屬性，從給定的鄰域半徑區間中選擇最優鄰域半徑［18］。

然而，鄰域粗糙集的上下近似是由樣本點組成，而不是等價類，因此使鄰域粗糙集失去了可解釋性?；诖?，Xia等人提出了一種基于粒球計算［19］的粒球粗糙集［20］，通過引入粒球計算來表示鄰域，用等價類來表示上下近似，從而實現Pawlak粗糙集和鄰域粗糙集的統一。Xia等提出的粒球計算是一種基于顆粒認知計算的新型、高效、魯棒的粒計算方法，其核心思想是利用“粒球”覆蓋或部分覆蓋樣本空間［19］。此外，Xia等還將粒球計算進行改進和發展，提出粒球分類器［19］、粒球聚類［21］、粒球鄰域粗糙集［22］和粒球采樣方法［23］。其中，粒球鄰域粗糙集可以自動優化鄰域半徑。粒球計算還拓展到基于偽標簽粒球粗糙集的約簡［24］、粒球生成樹聚類算法［25］等研究。

受文獻［12］、［20］的啟發，本文借鑒粒球計算的思想，結合多粒度粗糙集模型，提出 “多粒度粒球粗糙集模型”，將粒球粗糙集從單一粒度拓展為多粒度。此外，討論了該模型的重要性質，給出了多粒度粒球粗糙集正域的生成算法，并通過實驗驗證該模型的可行性和有效性。

1 相關知識

本節主要回顧多粒度粗糙集、粒球粗糙集的相關知識。

1.1 多粒度粗糙集

Qian等將Pawlak粗糙集模型擴展為多粒粗糙集模型，該模型通過論域上的多重等價關系定義集合近似［12］。

1.2 粒球粗糙集

Xia等提出粒球計算方法，此方法能夠在信息?；^程中，自適應地生成粒球信息粒［19］。進一步提出粒球粗糙集，從而實現了Pawlak粗糙集和鄰域粗糙集的統一表示。

定義2［20］ 設GB=｛xi，i=1，2，…，N｝為粒球，xi表示粒球GB內的樣本，N為粒球GB中樣本的個數。粒球GB的中心C和半徑r分別定義為

定義3［20］ 設粒球GB=｛xi，i=1，2，…，N｝，xi表示粒球GB的樣本，N為粒球GB中樣本的個數。設M為粒球GB樣本標簽占比最大的樣本數，則可定義粒球GB的純度為

在粒球的生成過程中，首先，將整個數據集視為一個粒球；其次，計算粒球純度，純度不滿足時將粒球均分為2個子球，依次進行迭代，直到所有粒球的純度滿足要求時，邊界最清晰且算法收斂。其主要步驟如下：

1） 假設m表示當前粒球的數量，將論域U初始化為一個粒球，令m=1;

2） 利用k-means聚類算法對每個粒球進行聚類，令k=2，則每個粒球分裂為兩個子粒球，此時粒球數量為2m;

3） 計算所有的子粒球的純度Purity，若所有的子粒球純度達到要求或粒球半徑r達到指定的閾值，則算法結束;否則，則返回步驟2）。

定義4［18］ 設DS=〈U，AT，V， f 〉是一個完備的信息系統，任意xi∈U，其中cj和rj分別表示粒球GBj的中心和半徑，則粒球GBj定義為

GBj=｛x|x∈U，Δ（x，cj）≤rj｝（6）

定義6［20］ 設DS=〈U，AT∪D，V， f 〉是一個完備的決策信息系統，U是非空有限集合，AT是屬性集， 決策D將論域U劃分為L個等價類，表示為U／D=｛X1，X2，…，XL｝，任意BAT，在U上存在著相應的等價關系GBRB。D關于屬性集B的上、下近似分別定義為

其中，對于任意x∈U，

2 多粒度粒球粗糙集模型

在本節內容中，借鑒粒球計算的思想，結合多粒度粗糙集模型，構造多粒度粒球粗糙集模型。

證明

基于以上性質，將粒球粗糙集模型拓展為多粒度粒球粗糙集模型。其中，該模型的集合近似通過論域上的多個等價關系來定義。

定義9 設DS=〈U，AT∪D，V，f〉是一個完備的決策信息系統，決策屬性D將論域U劃分為L個等價類，表示為U／D=｛X1，X2，…，XL｝。任意B∈2AT，B=｛B1，B2，…，Bm｝，在U上存在基于Bi的粒球GBBi相應的等價關系GBRBi。D關于B的上下近似定義為

與粒球粗糙集相似，可以根據經典粗糙集理論得出粒球粗糙集的正域、邊界域的表示。

和邊界域定義為

根據上述定義和性質，基于Xia等的粒球粗糙集模型計算正域的算法［20］，結合多粒度粗糙集的理論，設計出多粒度粒球粗糙集計算正域的算法如下。

算法1 多粒度粒球粗糙集在第i個粒度下正域生成

輸入 DS=〈U，AT∪｛d｝，f〉／*完備決策信息系統*／;

k／*DS的類別個數*／;

GBS／*用于臨時儲存GBn*／;

size（GB）／*最小粒徑*／;

Purity／*純度閾值*／。

輸出 GBRSi／*存儲滿足條件的GB*／。

步驟1 初始化。

步驟2 對數據集DS=〈U， AT∪D， V， f〉進行劃分， 設AT=｛AT1， AT2， …， ATm｝，DSi=〈U，ATi∪D，V，f〉為DS的第i個子信息系統。

步驟3 對DSi進行k-means聚類分析。計算各簇心Cn和粒球半徑rn，繪制粒球GBn。／*將GBn保存在GBS內*／

步驟5 輸出GBRSi（i=1，2，…，m）。

在算法1中， 假設論域U被分解為|GBS|個粒球， 迭代次數最多為（|U|×|GBS|）。 因此， 算法1的時間復雜度為O（|U|×|GBS|）。

算法2 多粒度粒球粗糙集正域生成

輸入 POS_GBRSi（i=1，2，…，m）。

輸出 POS_MGBRST／*多粒度粒球粗糙集正域*／。

POS_MGBRS=POS_GBRS1∪

POS_GBRS2∪…∪POS_GBRSm。

步驟3 輸出POS_MGBRS。

由算法1可知，在最壞的情況下，多粒度粒球粗糙集在第i個粒度下正域生成所需的迭代次數為O（|U|×|GBS|）。此外，假定在粒度劃分時，粒度劃分為AT=｛AT1，AT2，…，ATm｝。結合算法1 可得算法2的時間復雜度為O（|U|×|GBS|×|m|）。

3 案例的說明與比較分析

例1 表1是一個多專家面試學生的決策信息表。其中：U=｛x1，x2，x3，x4，x5，x6｝表示6位不同的學生；條件屬性集B=｛a1，a2，a3，a4，a5，a6｝表示生物、管理領域的專家團隊對學生是否通過面試的贊成率；決策屬性D=｛d｝表示學生能否通過面試。其中：“1”表示通過面試；“0”則表示不通過面試。結合相關性質，可將屬性集B分成B1和B2。其中B1表示生物領域，B2表示管理領域，即B=｛B1，B2｝=｛｛a1，a2，a3｝，｛a4，a5，a6｝｝，且設最小粒徑size（GB）=2（決定粒球GB是否繼續迭代的最小樣本數）。

根據定義2可求得在粒度B1和B2下，粒球GBi的球心ci、半徑ri。各樣本到球心Ci的距離d如表2所示。

C1=（0.68，0.73，0.68）;

C2=（0.67，0.72，0.72）;

r1=0.019 7;r2=0.021 7。

則根據定義4和表2可以求得粒球GBi的樣本集如下。

GB1=｛x1，x2，x4｝;

GB2=｛x1，x5，x6｝。

根據定義3計算粒球GB1、GB2的純度為

Purity（GB1）=0.666 7，

Purity（GB2）=1。

又因為Purity（GB1）=0.666 7<1;且size（GB1）≥2，因此，對GB1進行第二次迭代，根據定義2計算簇心和半徑可得

C11=（0.73，0.73，0.70），r11=0.01。

同理根據定義4可得

GB11=｛x2，x4｝，

Purity（GB11）=1。

根據定義8，可以求得論域U在屬性集B下近似為

進而，可以得到D關于屬性集B正域為

POSB（D）=｛x1，x2，x4，x5，x6｝。

注1 例1中粒球GBi使用的最小粒徑是粒球內樣本個數為2（樣本分為2類），在實際計算中，最小粒徑的取值可以大于類別個數，否則會出現樣本都是正域的情況，不利于正確地分類。

注2 在k-means聚類算法中，使用的距離度量是Squared Euclidean Distance。因此，例1使用相同的度量。

注3 例1中計算簇心的方法是利用對所有f（x，ci），i=1，2…，m取均值。實驗中可以根據樣本的類別標簽，分別對所分的簇求均值從而得到簇心和半徑。

采用多粒度粗糙集模型進行計算過程如表3所示，所得正域的結果與多粒度粒球粗糙集進行對比，結果如表4所示。

4 實驗結果與分析

對于本文提出的多粒度粒球粗糙集模型生成正域算法，本節通過實驗分析驗證其可行性和有效性。所有實驗硬件環境配置為 AMD Ryzen 5 2500U CPU@ 2.00 GHz和8 GB內存的個人計算機，算法運行的軟件環境為 Matlab R2021b。

為了驗證所提算法的有效性，在本節中，從UCI中選取了10組基準數據集進行相關的實驗對比分析，其中前4組為連續型數據，后6組為離散型數據。數據的具體描述見表5。

4.1 參數分析

在數學實驗中，選擇最優的參數進行對比實驗是一個重要的步驟。多粒度粒球粗糙集模型（MGBRST） 生成正域算法中需要考慮的參數為最小粒徑size（GB），即顆粒球GB內的最小樣本數，它決定了顆粒球GB是否繼續迭代;由于正域生成算法設置純度閾值為 “1”，因此實驗不考慮純度閾值的影響。選取German、Zoo、Lymphography、Anneal進行參數分析，size（GB）的選擇范圍為2～7?？紤]參數對算法的時間消耗／s和包含度／％的影響，可視化結果如圖2、3所示。

包含度的定義如下：在多粒度粒球粗糙集模型（MGBRST）中，由于粒球刻畫了數據之間的內在聯系和規律，因此生成的正域的樣本數從理論上來說將少于多粒度粗糙集（MGRST），并且可能包含在多粒度粗糙集（MGRST）中。故本文根據梁等提出的思想，即包含度可作為建立粗糙集數據分析中的度量的主要依據［26］，定義在MGBRST模型上正域生成的樣本關于MGRST模型的包含度α為

其中：XMG表示在MGRST模型下生成正域的樣本集;XMGB表示在MGBRST模型下生成正域的樣本集；|XMGB|表示集合XMGB的基數。

參數越小，迭代的次數越多，時間消耗理論上就越大;除此外，參數的設定還與數據類別有關，且k-means算法具有隨機性，因此找到合適的參數是必要的。如圖2所示，參數size（GB）的大小對4個數據集的影響不同。數據集Anneal受參數的影響較小，而數據集German受參數的影響較大。參數的大小還影響了包含度的大小，最小粒徑越小，迭代的次數越多，理論上得到的粒球就越多，包含度可能就越大;此外，參數過小也可能出現生成單點集的情況，這樣也一定程度上減少了正域樣本的生成，導致包含度下降。如圖3所示數據集Anneal受參數的影響較小，而數據集Lymphography受參數的影響較大，曲線呈大幅度下降趨勢。綜上所述，結合圖2、3，選擇最優的參數。如German數據集中選擇size（GB）的值為4，能更好地結合時間消耗小和包含度高這兩個優點。各數據集的參數大小選擇如表6所示。

4.2 正域生成的時間消耗對比

在本節實驗中，將針對錢等提出的多粒度粗糙集模型（MGRST）［12］及本文提出的多粒度粒球粗糙集模型（MGBRST），進行時間消耗的對比，最終采集的時間消耗為兩種方法分別求解正域所需時間的均值，具體結果如表7和圖4所示。

在數據的預處理階段，由于MGRST模型處理的是離散型數據，因此，對前4組數據使用等寬離散化方法進行離散化，再利用MGRST模型計算離散數據。MGBRST模型處理前4組連續數據以及后6組離散數據。

觀察表7和圖4，不難得出如下結論：利用多粒度粒球粗糙集模型（MGBRST）計算正域的時間消耗大多低于傳統的多粒度粗糙集模型 （MGRST）。這說明粒球與多粒度粗糙集的結合，可以有效地提升計算正域的效率；其次，多粒度粒球粗糙集模型（MGBRST）不僅可以處理連續型數據，還可以處理離散型數據。

4.3 正域生成的樣本數和包含率對比

為了更好地對比MGBRST模型和MGBRST模型正域生成的關系，本節主要討論兩種模型在6個數據的正域樣本數和包含度，包含度的計算如式（17）所示。

實驗選取后6個離散型數據，分別利用兩種模型對4個數據集求解，可得4個數據集在兩種模型下生成的正域的樣本個數和包含度α的結果如表8和圖5、6所示。

觀察表8和圖5、6可知，6個數據集在MGBRST模型下生成正域的樣本個數明顯小于MGRST模型下生成正域的樣本個數;且包含度α基本上穩定在0.9以上，Zoo數據集和Anneal數據集的包含度α為1。這說明MGBRST模型是MGRST模型的一個拓展模型，它結合了粒球粗糙集更細致的描述能力，更好地刻畫了數據之間的內在聯系和規律，可以進一步劃分正域中不被需要的那一部分。

5 結語

考慮到粒球粗糙集不能處理多粒度數據問題。為了解決該問題，本文將粒球思想與多粒度粗糙集模型結合，提出了多粒度粒球粗糙集模型，并討論了多粒度粒球粗糙集的相關性質。此外，給出了該模型正域的計算算法。研究發現，多粒度粒球粗糙集能更好地刻畫數據之間的內在聯系，能進一步劃分正域中的樣本，減少樣本數，便于決策者決策。最后，本文通過實驗表明了多粒度粒球粗糙集模型的可行性和有效性。今后將進一步探索多粒度粒球粗糙集的相關研究，著重考慮基于該模型的粒度約簡等問題。

參考文獻

［1］ PAWLAK Z. Rough sets［J］. International Journal of Computer ＆ Information Sciences， 1982， 11： 341-356.

［2］ WEI J M， WANG S Q，YUAN X J. Ensemble rough hypercuboid approach for classifying cancers［J］. IEEE Transactions on Knowledge and Data Engineering， 2010， 22（3）： 381-391.

［3］ 馬文萍， 黃媛媛， 李豪， 等. 基于粗糙集與差分免疫模糊聚類算法的圖像分割［J］.軟件學報， 2014， 25（11）： 2675-2689.

MA W P， HUANG Y Y， LI H， et al. Image segmentation based on rough set and differential immune fuzzy clustering algorithm［J］.Journal of Software， 2014， 25（11）： 2675-2689.

［4］ QIAN Y H， XU H， LIANG J Y， et al. Fusing monotonic decision trees［J］. IEEE Transactions on Knowledge and Data Engineering， 2015， 27（10）： 2717-2728.

［5］ QIAN Y H， LIANG X Y， WANG Q， et al. Local rough set： A solution to rough data analysis in big data［J］. International Journal of Approximate Reasoning， 2018， 97： 38-63.

［6］ VIDHYA K A， GEETHA T V. Entity resolution framework using rough set blocking for heterogeneous web of data［J］. Journal of Intelligent ＆ Fuzzy Systems， 2018， 34（1）： 659-675.

［7］ HU M J， YAO Y Y. Structured approximations as a basis for three-way decisions in rough set theory［J］. Knowledge-Based Systems， 2019， 165： 92-109.

［8］ 梁吉業， 錢宇華， 李德玉， 等. 面向大數據的粒計算理論與方法研究進展［J］. 大數據， 2016， 2（4）： 13-23.

LIANG J Y， QIAN Y H， LI D Y， et al. Research development on granular computing theory and method for big data［J］. Big Data research， 2016， 2（4）： 13-23.

［9］ KRYSZKIEWICZ M. Rough set approach to incomplete information systems［J］. Information Sciences， 1998， 112（1/2/3/4）： 39-49.

［10］王國胤.Rough集理論在不完備信息系統中的擴充［J］ 計算機研究與發展，2002，39（10）： 1238-1243.

WANG G Y. Extension of rough set under incomplete information systems［J］.Journal of Computer Research and Development， 2002， 39（10）： 1238-1243.

［11］STEFANOWSKI J， TSOUKIAS A. Incomplete information tables and rough classification［J］ Computational Intelligence， 2001，17（3）： 545-566.

［12］QIAN Y H， LIANG J Y， YAO Y Y， et al. MGRS： A multi-granulation rough set［J］.Information Sciences，2010， 180（6）： 949-970.

［13］QIAN Y H， LIANG J Y， DANG C Y. Incomplete multigranulation rough set［J］.IEEE Transactions on Systems Man and Cybernetics-Part A： Systems and Humans， 2010，40（2）： 420-431.

［14］QIAN Y H， LI S Y， LIANG J Y， et al. Pessimistic rough set based decisions： A multigranulation fusion strategy［J］.Information Sciences，2014，264： 196-210.

［15］HU Q H， YU D R， XIE Z X. Neighborhood classifiers［J］.Expert Systems with Applications，2008，34（2）： 866-876.

［16］李楠， 謝娟英. 基于鄰域粗糙集的增量特征選擇［J］.計算機技術與發展， 2011， 21（11）： 149-152.

LI N， XIE J Y. A feature subset selection algorithm based on neighborhood rough set for incremental updating datasets［J］.Computer Technology and Development， 2011，21（11）： 149-152.

［17］胡清華，趙輝，于達仁. 基于鄰域粗糙集的符號與數值屬性快速約簡算法［J］.模式識別與人工智能， 2008， 21（6）： 732-738.

HU Q H， ZHAO H， YU D R. Efficient symbolic and numerical attribute reduction with neighborhood rough sets［J］.Pattern Recognition and Artificial Intelligence， 2008， 21（6）：732-738.

［18］彭瀟然， 劉遵仁， 紀俊. 自適應的鄰域粗糙集鄰域大小取值方法［J］.計算機應用研究， 2019， 36（1）： 144-147.

PENG X R， LIU Z R， JI J. Adaptable method for determining neighborhood size of neighborhood rough set［J］.Application Research of Computers，2019，36（1）： 144-147.

［19］XIA S Y， LIU Y S， DING X， et al. Granular ball computing classifiers for efficient scalable and robust learning［J］.Information Sciences，2019，483（1）： 136-152.

［20］XIA S Y， WANG C， WANG G Y， et al.GBRS： An unified model of Pawlak rough set and neighborhood rough set［EB/OL］.（2022-01-10）［2023-06-01］.http：∥arxiv.org/abs/2201.03349.

［21］XIA S Y， PENG D W， MENG D Y， et al. Ball k-means： Fast adaptive clustering with no bounds［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence， 2022， 44（1）： 87-99.

［22］XIA S Y， ZHANG H， LI W H， et al. GBNRS： A novel rough set algorithm for fast adaptive attribute reduction in classification［J］.IEEE Transactions on Knowledge and Data Engineering ，2022， 34（3）： 1231-1242.

［23］XIA S Y， ZHENG S Y， WANG G Y， et al.Granular ball sampling for noisy label classification or imbalanced classification［J］.IEEE Transactions on Neural Networks and Learning Systems， 2023， 34（4）： 2144-2155.

［24］陳中華， 巴婧， 徐泰華，等.一種面向粒球粗糙集的快速約簡求解方法［J］.小型微型計算機系統， 2023， 44（1）： 24-29.

CHEN Z H， BA J， XU T H， et al. Quick strategy for searching granular ball rough set based reduct［J］.Journal of Chinese Computer Systems，2023， 44（1）： 24-29.

［25］XIE J， XIA S Y， WANG G Y， et al. GBMST： An efficient minimum spanning tree clustering based on granular-ball computing［EB/OL］.（2023-03-02）［2023-06-01］.http：∥arxiv.org/abs/2303.01082.

［26］梁吉業，徐宗本，李月香.包含度與粗糙集數據分析中的度量［J］.計算機學報，2001，24（5）： 544-547.

LIANG J Y， XU Z B， LI Y X. Inclusion degree and measures of rough set data analysis［J］.Chinese Journal of Computers， 2001，24（5）： 544-547.