多粒度粒球粗糙集模型

蒋珊珊 林国平 林艺东 寇毅

摘要 基于粒球计算的粗糙集理论作为知识发现和数据挖掘的重要工具之一，已成功地应用于标记预测、属性约简等。而现有的粒球粗糙集模型仅仅是从单粒度出发，无法从多粒度角度对数据进行分析和处理，实际生活中仍有很多应用场景需从多粒度角度进行思考。将粒球计算思想结合到多粒度粗糙集模型，提出了多粒度粒球粗糙集模型，并讨论了该模型的相关性质。该模型通过纯度的设定对数据进行粒球划分，能够有效地刻画数据之间的内在联系，以此设计多粒度粒球粗糙集的正域生成算法。实验分析表明该模型的可行性和有效性。

关键词 粒球计算;粒球粗糙集;多粒度粗糙集;纯度

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］。基于它的诸多优势，许多学者对其进行了相关的研究和改进。李和谢提出了一种基于邻域粗糙集的特征子集增量式更新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.