粗糙集理论是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[12]　设DS＝〈U，AT，V, f〉是一个完备的信息系统，任意B∈2AT，B＝{B1，B2，…，Bm}，Bi⊆AT，i＝1，2，…，m。对于任意X⊆U，则X关于B的上、下近似表示为(1)(2)称为多粒度粗糙集模型。1.2粒球粗糙集Xia等提出粒球计算方法，此方法能够在信息粒化过程中，自适应地生成粒球信息粒[19]。进一步提出粒球粗糙集，从而实现了Pawlak粗糙集和邻域粗糙集的统一表示。定义2[20]　设GB＝{xi，i＝1，2，…，N}为粒球，xi表示粒球GB内的样本，N为粒球GB中样本的个数。粒球GB的中心C和半径r分别定义为(3)(4)定义3[20]　设粒球GB＝{xi，i＝1，2，…，N}，xi表示粒球GB的样本，N为粒球GB中样本的个数。设M为粒球GB样本标签占比最大的样本数，则可定义粒球GB的纯度为(5)在粒球的生成过程中，首先，将整个数据集视为一个粒球；其次，计算粒球纯度，纯度不满足时将粒球均分为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定义为(6)其中：Δ(x，cj)表示任意的对象x∈U与中心cj的距离度量。本文中，f(x, a)表示对象在属性a下的属性值，U′表示为k-means聚类算法每次迭代的类样本。定义5[20]　设DS＝〈U，AT，V, f〉是一个完备的信息系统，任意x，y∈U且B⊆AT，粒球GB基于属性集B下的不可分辨关系定义为INDGB(B)＝{(x，y)∈U2|f(x，a)＝f(y，a)＝GB，∀a∈B}。根据定义5，存在(x，y)∈INDGB(B)，则x与y等价。论域U在GB下的划分表示为U/GB(B)，粒球GB在不可分辩关系INDGB(B)下的等价类表示为[x]GB(B)＝{y∈U|(x，y)∈INDGB(B)}，[x]GB(B)是U/GB(B)的元素。定义6[20]　设DS＝〈U，AT∪D，V, f〉是一个完备的决策信息系统，U是非空有限集合，AT是属性集，决策D将论域U划分为L个等价类，表示为U/D＝{X1，X2，…，XL}，任意B⊆AT，在U上存在着相应的等价关系GBRB。D关于属性集B的上、下近似分别定义为(7)(8)其中，对于任意x∈U，定义7[20]　设DS＝〈U，AT∪D，V, f〉是一个完备的决策信息系统，任意B⊆AT，DS关于属性集B的正域和边界域定义为(9)(10)2多粒度粒球粗糙集模型在本节内容中，借鉴粒球计算的思想，结合多粒度粗糙集模型，构造多粒度粒球粗糙集模型。定义8　设DS＝〈U，AT，V, f〉是一个完备的信息系统，U是非空有限集合，AT是属性集。任意B∈2AT，B＝{B1，B2，…，Bm}，Bi⊆AT，i＝1，2，…，m。在U上存在基于Bi的粒球相应的等价关系。对于任意X⊆U，X关于B的上、下近似定义为(11)(12)称为多粒度粒球粗糙集，并称为X关于B的正域，为X关于B的边界域。性质1　设DS=〈U,AT,V,f〉，是一个完备的信息系统，U是非空有限集合，AT是属性集。任意B∈2AT,B={B1,B2,…,Bm},Bi∈B，在U上存在基于B和Bi的粒球GB和，其相应的等价关系为GBRB、。对任意X⊆U,X关于B的上、下近似有以下的性质：1) 2) 。证明　1)由定义8得，任意，则至少存在i=j(j≤m)，使得。又因，则任意，存在Xj(j≤a)⊆GB(Bi)，使得X′i⊆Xj，则。综上，有。2)由Pawlak粗糙集理论的相关性质可得，又根据性质(1)有性质2　设DS=〈U,AT,V,f〉是一个完备的信息系统，U是非空有限集合，AT是属性集。任意B∈2AT,B={B1,B2,…,Bm}，在U上存在基于Bi的粒球相应的等价关系。假设有X⊆U，则X关于属B的上、下近似的性质有1) ;2) ;;3) ;;4) ;5) 。证明1a)令x,，且有X/GB(Bi)⊆X，则至少存在一个划分X/GB(Bi)，使得x∈X/GB(Bi)，且y∈X/GB(Bi)；又因x,y∈X，则。1b)令x,y∈X，则有x∈X/GB(Bi)∩X，且y∈X/GB(Bi)∩X；又X/GB(Bi)∩X=Ø，所以x,，。2a)根据1)可得，又有(空集是任何集合的子集)，则有；假设，据定义有，而，这与假设矛盾，因此有。2b)根据1)可得，若x∈U，。则，，因此，。3a) 。3b)根据3a)，令X=~X，则4)任意x⊆U，如果有X/GB(Bi)⊆X，则，若存在y，使则X/GB(Bi)=Ø，所以5)根据性质4)可得性质3　设DS=〈U,AT,V,f〉是一个完备的信息系统，U是非空有限集合，AT是属性集。任意B∈2AT,B={B1,B2,…,Bm}，在U上存在基于Bi的粒球相应的等价关系。假设有X,Y⊆U，则X,Y关于B的上、下近似的性质有1);2);3);4);5);6) ;7) ;8) 。证明　先证明1)。2)与1)类似可以证得。由1)可以得出3)的证明。由2)可得出4)的证明。5)如果X⊆Y, X∩Y=X，则根据性质3)可得则有。6)若X⊆Y,X∪Y=Y，则根据性质4)可得则有。7) X⊆X∪Y且Y⊆X∪Y。则根据性质5)，满足，且有，则有8)根据性质7)，显然X∩Y⊆X,X∩Y⊆Y，根据X∩Y⊆X则有综上所述，基于以上性质，将粒球粗糙集模型拓展为多粒度粒球粗糙集模型。其中，该模型的集合近似通过论域上的多个等价关系来定义。定义9　设DS=〈U,AT∪D,V,f〉是一个完备的决策信息系统，决策属性D将论域U划分为L个等价类，表示为U/D={X1,X2,…,XL}。任意B∈2AT,B={B1,B2,…,Bm}，在U上存在基于Bi的粒球相应的等价关系。D关于B的上下近似定义为(13)(14)与粒球粗糙集相似，可以根据经典粗糙集理论得出粒球粗糙集的正域、边界域的表示。定义10　设DS＝〈U，AT∪D，V，f〉是一个完备的决策信息系统，∀B⊆AT，D关于B的正域和边界域定义为(15)(16)根据上述定义和性质，基于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内*/步骤4　if ∃GBn∈GBS，Purity1，do1)生成粒球GBn内的数据集DS′n；2)返回步骤3。until ∀GBn∈GBS，Purity＝1 orsize(GBi)size(GB)。GBRSi←GBn。end步骤5　输出GBRSi(i＝1，2，…，m)。在算法1中，假设论域U被分解为|GBS|个粒球，迭代次数最多为(|U|×|GBS|)。因此，算法1的时间复杂度为O(|U|×|GBS|)。算法2　多粒度粒球粗糙集正域生成输入　POS_GBRSi(i＝1，2，…，m)。输出　POS_MGBRST/*多粒度粒球粗糙集正域*/。步骤1　for i＝1∶mif ∃GB∈GBRSi，Purity1，doPOS_GBrSi＝GBRSi\GBendend步骤2　对∀POS_GBRSi，doPOS_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是否继续迭代的最小样本数)。10.16152/j.cnki.xdxbzr.2024-02-006.T001表1多专家面试学生评估表Tab. 1Multi-expert interview student assessment form a1a2a3a4a5a6dx10.60.70.70.70.60.70x20.80.80.70.60.60.61x30.70.60.60.70.90.7 0x40.80.70.70.80.70.81x50.60.80.80.60.80.70x60.60.80.80.60.70.80根据定义2可求得在粒度B1和B2下，粒球GBi的球心ci、半径ri。各样本到球心Ci的距离d如表2所示。10.16152/j.cnki.xdxbzr.2024-02-006.T002表2各样本到中心的距离Tab. 2Distance from each sample to center c1c2x10.007 70.015 7x20.019 70.033 7x30.023 70.033 7x40.015 70.023 7x50.025 70.011 7x60.025 70.011 7C1＝(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 71；且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正域为注1　例1中粒球GBi使用的最小粒径是粒球内样本个数为2(样本分为2类)，在实际计算中，最小粒径的取值可以大于类别个数，否则会出现样本都是正域的情况，不利于正确地分类。注2　在k-means聚类算法中，使用的距离度量是Squared Euclidean Distance。因此，例1使用相同的度量。注3　例1中计算簇心的方法是利用对所有f(x，ci)，i＝1，2…，m取均值。实验中可以根据样本的类别标签，分别对所分的簇求均值从而得到簇心和半径。采用多粒度粗糙集模型进行计算过程如表3所示，所得正域的结果与多粒度粒球粗糙集进行对比，结果如表4所示。10.16152/j.cnki.xdxbzr.2024-02-006.T003表3例1在多粒度粗糙集模型下的计算结果Tab. 3Calculation results of example 1 under multi-granulation rough set model 在各属性下的划分下近似 a1{{x1，x5，x6}，{x2，x4}，{x3}}{x3}a2{{x1，x4}，{x2，x5，x6}，{x3}}{x4}a3{{x1，x2，x4}，{x3}，{x5，x6}}{x3，x5，x6}a4{{x1，x3}，{x2，x5，x6}，{x4}}{x1，x3，x4}a5{{x1，x2}，{x3}，{x4，x6}，{x5}}{x3，x5}a6{{x1，x3，x5}，{x2}，{x4，x6}}{x1，x2，x3，x5}d{{x1，x3，x5，x6}，{x2，x4}}{x1，x2，x3，x4，x5，x6}10.16152/j.cnki.xdxbzr.2024-02-006.T004表4例1在两个模型下计算正域的结果Tab. 4Positive region calculating results of example 1 under two models模型POSB(D)MRST{x1，x2，x3，x4，x5，x6}MGBRST{x1，x2，x4，x5，x6}通过对比和分析例1在粒球粗糙集模型(MGRST)和多粒度粒球粗糙集模型(MGBRST)正域生成的结果(见图1)，根据表3，可以得到POSB(D)－MGBRST⊆POSB(D)－MGRST。这是因为MGBRST模型结合了粒球粗糙集更细致的描述能力，更好地刻画了数据之间的内在联系，减少部分目标区域的样本，便于进一步决策。10.16152/j.cnki.xdxbzr.2024-02-006.F001图1例1的多粒度粒球粗糙集的生成过程Fig. 1The generation process of granular-ball rough set model based on multi-granulation in example 1注：红色表示决策属性为“1”；蓝色表示决策属性为“0”。(a)、(b)表示论域U分别在粒度B1和B2下的划分。根据纯度的定义，可以得到(a)中的粒球纯度为1，则表示正域，若粒球纯度不为1，如(b)，则表示边界域。(c)表示对(b)粒球进行迭代，根据定义，最终结果如(d)，可以得到最终多粒度粒球粗糙集的正域。4实验结果与分析对于本文提出的多粒度粒球粗糙集模型生成正域算法，本节通过实验分析验证其可行性和有效性。所有实验硬件环境配置为AMD Ryzen 5 2500U CPU@ 2.00 GHz和8 GB内存的个人计算机，算法运行的软件环境为Matlab R2021b。为了验证所提算法的有效性，在本节中，从UCI中选取了10组基准数据集进行相关的实验对比分析，其中前4组为连续型数据，后6组为离散型数据。数据的具体描述见表5。10.16152/j.cnki.xdxbzr.2024-02-006.T005表5数据集描述Tab. 5Data sets descriptionID数据集名称样本数属性数决策类数1Wine1781332Iris150433Segmentation2 3101974Pima768825Mushroom7 5352226Zoo1011677Lymphography1481848Mushroom18 1242229German1 00021210Anneal7983954.1参数分析在数学实验中，选择最优的参数进行对比实验是一个重要的步骤。多粒度粒球粗糙集模型(MGBRST)生成正域算法中需要考虑的参数为最小粒径size(GB)，即颗粒球GB内的最小样本数，它决定了颗粒球GB是否继续迭代；由于正域生成算法设置纯度阈值为“1”，因此实验不考虑纯度阈值的影响。选取German、Zoo、Lymphography、Anneal进行参数分析，size(GB)的选择范围为2~7。考虑参数对算法的时间消耗/s和包含度/%的影响，可视化结果如图2、3所示。10.16152/j.cnki.xdxbzr.2024-02-006.F002图2参数size(GB)的大小对时间消耗的影响Fig. 2The effect of parameter size (GB) on time consumption10.16152/j.cnki.xdxbzr.2024-02-006.F003图3参数size(GB)的大小对包含度的影响Fig. 3The effect of parameter size (GB) on inclusion包含度的定义如下：在多粒度粒球粗糙集模型(MGBRST)中，由于粒球刻画了数据之间的内在联系和规律，因此生成的正域的样本数从理论上来说将少于多粒度粗糙集(MGRST)，并且可能包含在多粒度粗糙集(MGRST)中。故本文根据梁等提出的思想，即包含度可作为建立粗糙集数据分析中的度量的主要依据[26]，定义在MGBRST模型上正域生成的样本关于MGRST模型的包含度α为(17)其中：XMG表示在MGRST模型下生成正域的样本集；XMGB表示在MGBRST模型下生成正域的样本集；|XMGB|表示集合XMGB的基数。参数越小，迭代的次数越多，时间消耗理论上就越大；除此外，参数的设定还与数据类别有关，且k-means算法具有随机性，因此找到合适的参数是必要的。如图2所示，参数size(GB)的大小对4个数据集的影响不同。数据集Anneal受参数的影响较小，而数据集German受参数的影响较大。参数的大小还影响了包含度的大小，最小粒径越小，迭代的次数越多，理论上得到的粒球就越多，包含度可能就越大；此外，参数过小也可能出现生成单点集的情况，这样也一定程度上减少了正域样本的生成，导致包含度下降。如图3所示数据集Anneal受参数的影响较小，而数据集Lymphography受参数的影响较大，曲线呈大幅度下降趋势。综上所述，结合图2、3，选择最优的参数。如German数据集中选择size(GB)的值为4，能更好地结合时间消耗小和包含度高这两个优点。各数据集的参数大小选择如表6所示。10.16152/j.cnki.xdxbzr.2024-02-006.T006表6各数据集的参数选择Tab. 6Parameter selection for each datasetIDSize(GB)1322364355637385941074.2正域生成的时间消耗对比在本节实验中，将针对钱等提出的多粒度粗糙集模型(MGRST)[12]及本文提出的多粒度粒球粗糙集模型(MGBRST)，进行时间消耗的对比，最终采集的时间消耗为两种方法分别求解正域所需时间的均值，具体结果如表7和图4所示。10.16152/j.cnki.xdxbzr.2024-02-006.T007表7两种模型计算正域的时间消耗Tab. 7Two models calculate the time consumption of positive regionIDMGRST/sMGBRST/s10.541 0910.484 32020.271 8660.179 73433.460 9162.414 93041.596 6701.130 863512.135 10012.522 22063.499 5182.913 09671.882 6623.564 317823.741 60022.754 82393.070 0703.461 867104.122 4453.978 553均值5.429 4945.340 47210.16152/j.cnki.xdxbzr.2024-02-006.F004图4两种算法计算正域的时间消耗Fig. 4Two algorithms calculate the time consumption of positive region在数据的预处理阶段，由于MGRST模型处理的是离散型数据，因此，对前4组数据使用等宽离散化方法进行离散化，再利用MGRST模型计算离散数据。MGBRST模型处理前4组连续数据以及后6组离散数据。观察表7和图4，不难得出如下结论：利用多粒度粒球粗糙集模型(MGBRST)计算正域的时间消耗大多低于传统的多粒度粗糙集模型(MGRST)。这说明粒球与多粒度粗糙集的结合，可以有效地提升计算正域的效率；其次，多粒度粒球粗糙集模型(MGBRST)不仅可以处理连续型数据，还可以处理离散型数据。4.3正域生成的样本数和包含率对比为了更好地对比MGBRST模型和MGBRST模型正域生成的关系，本节主要讨论两种模型在6个数据的正域样本数和包含度，包含度的计算如式(17)所示。实验选取后6个离散型数据，分别利用两种模型对4个数据集求解，可得4个数据集在两种模型下生成的正域的样本个数和包含度α的结果如表8和图5、6所示。10.16152/j.cnki.xdxbzr.2024-02-006.T008表8两种模型生成的正域样本个数和包含度α的值Tab. 8Number and inclusion degree α of positive region samples generated by the two modelsIDMGRSTMGBRSTα53 1511 2640.999 2661381.000 072070.914 484 8963 8840.918 696531100.922 410538961.000 0均值－－0.959 110.16152/j.cnki.xdxbzr.2024-02-006.F005图5两种模型下生成的正域样本个数Fig. 5Number of positive region samples generated under two models10.16152/j.cnki.xdxbzr.2024-02-006.F006图66种数据集下的包含度Fig. 6Inclusion degree under six types of data set观察表8和图5、6可知，6个数据集在MGBRST模型下生成正域的样本个数明显小于MGRST模型下生成正域的样本个数；且包含度α基本上稳定在0.9以上，Zoo数据集和Anneal数据集的包含度α为1。这说明MGBRST模型是MGRST模型的一个拓展模型，它结合了粒球粗糙集更细致的描述能力，更好地刻画了数据之间的内在联系和规律，可以进一步划分正域中不被需要的那一部分。5结语考虑到粒球粗糙集不能处理多粒度数据问题。为了解决该问题，本文将粒球思想与多粒度粗糙集模型结合，提出了多粒度粒球粗糙集模型，并讨论了多粒度粒球粗糙集的相关性质。此外，给出了该模型正域的计算算法。研究发现，多粒度粒球粗糙集能更好地刻画数据之间的内在联系，能进一步划分正域中的样本，减少样本数，便于决策者决策。最后，本文通过实验表明了多粒度粒球粗糙集模型的可行性和有效性。今后将进一步探索多粒度粒球粗糙集的相关研究，着重考虑基于该模型的粒度约简等问题。