本节主要回顾多粒度粗糙集、粒球粗糙集的相关知识。

1.1 多粒度粗糙集

Qian等将Pawlak粗糙集模型扩展为多粒粗糙集模型，该模型通过论域上的多重等价关系定义集合近似^[

参考文献 12

百度学术    

12]。

以上内容由百度机器翻译自动生成，翻译内容仅供参考。对于因使用本网站翻译内容产生的相关后果，本网站不承担任何商业和法律责任。
The above content is generated by Baidu Machine Translation. The translated content is for reference only. We do not assume any commercial or legal responsibility for any consequences arising from the use of our website with machine translated content.

翻译语言

• English
• Русский язык
• بالعربية
• Français
• Español

译

定义1  ^[

参考文献 12

百度学术    

12]    　设DS＝〈U，AT，V, f〉是一个完备的信息系统，任意B∈2^AT，B＝{B₁，B₂，…，B_m}，B_i⊆AT，i＝1，2，…，m。对于任意X⊆U，则X关于B的上、下近似表示为

(1)

(2)

称 为多粒度粗糙集模型。

以上内容由百度机器翻译自动生成，翻译内容仅供参考。对于因使用本网站翻译内容产生的相关后果，本网站不承担任何商业和法律责任。
The above content is generated by Baidu Machine Translation. The translated content is for reference only. We do not assume any commercial or legal responsibility for any consequences arising from the use of our website with machine translated content.

翻译语言

• English
• Русский язык
• بالعربية
• Français
• Español

译

1.2 粒球粗糙集

Xia等提出粒球计算方法，此方法能够在信息粒化过程中，自适应地生成粒球信息粒^[

参考文献 19

百度学术    

19]。进一步提出粒球粗糙集，从而实现了Pawlak粗糙集和邻域粗糙集的统一表示。

以上内容由百度机器翻译自动生成，翻译内容仅供参考。对于因使用本网站翻译内容产生的相关后果，本网站不承担任何商业和法律责任。
The above content is generated by Baidu Machine Translation. The translated content is for reference only. We do not assume any commercial or legal responsibility for any consequences arising from the use of our website with machine translated content.

翻译语言

• English
• Русский язык
• بالعربية
• Français
• Español

译

定义2  ^[

参考文献 20

百度学术    

20]    　设GB＝{x_i，i＝1，2，…，N}为粒球，x_i表示粒球GB内的样本，N为粒球GB中样本的个数。粒球GB的中心C和半径r分别定义为

(3)

(4)

定义3  ^[

参考文献 20

百度学术    

20]    　设粒球GB＝{x_i，i＝1，2，…，N}，x_i表示粒球GB的样本，N为粒球GB中样本的个数。设M为粒球GB样本标签占比最大的样本数，则可定义粒球GB的纯度为

(5)

在粒球的生成过程中，首先，将整个数据集视为一个粒球；其次，计算粒球纯度，纯度不满足时将粒球均分为2个子球，依次进行迭代，直到所有粒球的纯度满足要求时，边界最清晰且算法收敛。其主要步骤如下：

以上内容由百度机器翻译自动生成，翻译内容仅供参考。对于因使用本网站翻译内容产生的相关后果，本网站不承担任何商业和法律责任。
The above content is generated by Baidu Machine Translation. The translated content is for reference only. We do not assume any commercial or legal responsibility for any consequences arising from the use of our website with machine translated content.

翻译语言

• English
• Русский язык
• بالعربية
• Français
• Español

译

1)假设m表示当前粒球的数量，将论域U初始化为一个粒球，令m＝1；

以上内容由百度机器翻译自动生成，翻译内容仅供参考。对于因使用本网站翻译内容产生的相关后果，本网站不承担任何商业和法律责任。
The above content is generated by Baidu Machine Translation. The translated content is for reference only. We do not assume any commercial or legal responsibility for any consequences arising from the use of our website with machine translated content.

翻译语言

• English
• Русский язык
• بالعربية
• Français
• Español

译

2)利用k-means聚类算法对每个粒球进行聚类，令k＝2，则每个粒球分裂为两个子粒球，此时粒球数量为2m；

以上内容由百度机器翻译自动生成，翻译内容仅供参考。对于因使用本网站翻译内容产生的相关后果，本网站不承担任何商业和法律责任。
The above content is generated by Baidu Machine Translation. The translated content is for reference only. We do not assume any commercial or legal responsibility for any consequences arising from the use of our website with machine translated content.

翻译语言

• English
• Русский язык
• بالعربية
• Français
• Español

译

3)计算所有的子粒球的纯度Purity，若所有的子粒球纯度达到要求或粒球半径r达到指定的阈值，则算法结束；否则，则返回步骤2)。

以上内容由百度机器翻译自动生成，翻译内容仅供参考。对于因使用本网站翻译内容产生的相关后果，本网站不承担任何商业和法律责任。
The above content is generated by Baidu Machine Translation. The translated content is for reference only. We do not assume any commercial or legal responsibility for any consequences arising from the use of our website with machine translated content.

翻译语言

• English
• Русский язык
• بالعربية
• Français
• Español

译

定义4  ^[

参考文献 18

百度学术    

18]    　设DS＝〈U，AT，V, f〉是一个完备的信息系统，任意x_i∈U，其中c_j和r_j分别表示粒球GB_j的中心和半径，则粒球GB_j定义为

(6)

其中：Δ(x，c_j)表示任意的对象x∈U与中心c_j的距离度量。本文中 ，f(x, a)表示对象在属性a下的属性值，U′表示为k-means聚类算法每次迭代的类样本。

以上内容由百度机器翻译自动生成，翻译内容仅供参考。对于因使用本网站翻译内容产生的相关后果，本网站不承担任何商业和法律责任。
The above content is generated by Baidu Machine Translation. The translated content is for reference only. We do not assume any commercial or legal responsibility for any consequences arising from the use of our website with machine translated content.

翻译语言

• English
• Русский язык
• بالعربية
• Français
• Español

译

定义5  ^[

参考文献 20

百度学术    

20]    　设DS＝〈U，AT，V, f〉是一个完备的信息系统，任意x，y∈U且B⊆AT，粒球GB基于属性集B下的不可分辨关系定义为INDGB(B)＝{(x，y)∈U²|f(x，a)＝f(y，a)＝GB，∀a∈B}。

以上内容由百度机器翻译自动生成，翻译内容仅供参考。对于因使用本网站翻译内容产生的相关后果，本网站不承担任何商业和法律责任。
The above content is generated by Baidu Machine Translation. The translated content is for reference only. We do not assume any commercial or legal responsibility for any consequences arising from the use of our website with machine translated content.

翻译语言

• English
• Русский язык
• بالعربية
• Français
• Español

译

根据定义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)的元素。

以上内容由百度机器翻译自动生成，翻译内容仅供参考。对于因使用本网站翻译内容产生的相关后果，本网站不承担任何商业和法律责任。
The above content is generated by Baidu Machine Translation. The translated content is for reference only. We do not assume any commercial or legal responsibility for any consequences arising from the use of our website with machine translated content.

翻译语言

• English
• Русский язык
• بالعربية
• Français
• Español

译

定义6  ^[

参考文献 20

百度学术    

20]    　设DS＝〈U，AT∪D，V, f〉是一个完备的决策信息系统，U是非空有限集合，AT是属性集，决策D将论域U划分为L个等价类，表示为U/D＝{X₁，X₂，…，X_L}，任意B⊆AT，在U上存在着相应的等价关系GBR_B。D关于属性集B的上、下近似分别定义为

(7)

(8)

其中，对于任意x∈U，

定义7  ^[

参考文献 20

百度学术    

20]    　设DS＝〈U，AT∪D，V, f〉是一个完备的决策信息系统，任意B⊆AT，DS关于属性集B的正域和边界域定义为

(9)

(10)

在本节内容中，借鉴粒球计算的思想，结合多粒度粗糙集模型，构造多粒度粒球粗糙集模型。

定义8  　设DS＝〈U，AT，V, f〉是一个完备的信息系统，U是非空有限集合，AT是属性集。任意B∈2^AT，B＝{B₁，B₂，…，B_m}，B_i⊆AT，i＝1，2，…，m。在U上存在基于B_i的粒球 相应的等价关系 。对于任意X⊆U，X关于B的上、下近似定义为

(11)

(12)

性质1  　设DS=〈U,AT,V,f〉，是一个完备的信息系统，U是非空有限集合，AT是属性集。任意B∈2^AT,B={B₁,B₂,…,B_m},B_i∈B，在U上存在基于B和B_i的粒球GB和 ，其相应的等价关系为GBR_B、 。对任意X⊆U,X关于B的上、下近似有以下的性质：

1)

2) 。

证明  　1)由定义8得，任意 ，则至少存在i=j(j≤m)，使得 。又因 ，则任意 ，存在X_j(j≤a)⊆GB(B_i)，使得X′_i⊆X_j，则 。综上，有 。

2)由Pawlak粗糙集理论的相关性质可得 ，又根据性质(1)有

性质2  　设DS=〈U,AT,V,f〉是一个完备的信息系统，U是非空有限集合，AT是属性集。任意B∈2^AT,B={B₁,B₂,…,B_m}，在U上存在基于B_i的粒球 相应的等价关系 。假设有X⊆U，则X关于属B的上、下近似的性质有

1) ;

2) ; ;

3) ; ;

4) ;

5) 。

证明  

1a)令x, ，且有X/GB(B_i)⊆X，则至少存在一个划分X/GB(B_i)，使得x∈X/GB(B_i)，且y∈X/GB(B_i)；又因x,y∈X，则 。

1b)令x,y∈X，则有x∈X/GB(B_i)∩X，且y∈X/GB(B_i)∩X；又X/GB(B_i)∩X=Ø，所以x, ， 。

2a)根据1)可得 ，又有 (空集是任何集合的子集)，则有 ；假设 ，据定义有 ，而 ，这与假设矛盾，因此有 。

2b)根据1)可得 ，若x∈U， 。则 ， ，因此， 。

3a) 。

3b)根据3a)，令X=~X，则

4)任意x⊆U，如果有X/GB(B_i)⊆X，则 ，若存在y，使

5)根据性质4)可得

性质3  　设DS=〈U,AT,V,f〉是一个完备的信息系统，U是非空有限集合，AT是属性集。任意B∈2^AT,B={B₁,B₂,…,B_m}，在U上存在基于B_i的粒球 相应的等价关系 。假设有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={X₁,X₂,…,X_L}。任意B∈2^AT,B={B₁,B₂,…,B_m}，在U上存在基于B_i的粒球 相应的等价关系 。D关于B的上下近似定义为

(13)

(14)

与粒球粗糙集相似，可以根据经典粗糙集理论得出粒球粗糙集的正域、边界域的表示。

定义10  　设DS＝〈U，AT∪D，V，f〉是一个完备的决策信息系统，∀B⊆AT，D关于B的正域和边界域定义为

(15)

(16)

根据上述定义和性质，基于Xia等的粒球粗糙集模型计算正域的算法^[

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

输入  　DS＝〈U，AT∪{d}，f〉/*完备决策信息系统*/；

k/*DS的类别个数*/；

GBS/*用于临时储存GB_n*/；

size(GB)/*最小粒径*/；

Purity/*纯度阈值*/。

输出  　GBRS_i/*存储满足条件的GB*/。

步骤1  　初始化。

步骤2  　对数据集DS＝〈U, AT∪D, V, f〉进行划分，设AT＝{AT₁, AT₂, …，AT_m}，DS_i＝〈U，AT_i∪D，V，f〉为DS的第i个子信息系统。

步骤3  　对DS_i进行k-means聚类分析。计算各簇心C_n和粒球半径r_n，绘制粒球GB_n。/*将GB_n保存在GBS内*/

步骤4  　if ∃GB_n∈GBS，Purity<1，do

1)生成粒球GB_n内的数据集DS′_n；

2)返回步骤3。

until ∀GB_n∈GBS，Purity＝1 or

size(GB_i)<size(GB)。

GBRS_i←GB_n。

end

步骤5  　输出GBRS_i(i＝1，2，…，m)。

在算法1中，假设论域U被分解为|GBS|个粒球，迭代次数最多为(|U|×|GBS|)。因此，算法1的时间复杂度为O(|U|×|GBS|)。

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

输入  　POS_GBRS_i(i＝1，2，…，m)。

输出  　POS_MGBRST/*多粒度粒球粗糙集正域*/。

步骤1  　for i＝1∶m

if ∃GB∈GBRS_i，Purity<1，do

POS_GBrS_i＝GBRS_i\GB

end

end

步骤2  　对∀POS_GBRS_i，do

POS_MGBRS＝POS_GBRS₁∪

POS_GBRS₂∪…∪POS_GBRS_m。

步骤3  　输出POS_MGBRS。

由算法1可知，在最坏的情况下，多粒度粒球粗糙集在第i个粒度下正域生成所需的迭代次数为O(|U|×|GBS|)。此外，假定在粒度划分时，粒度划分为AT＝{AT₁，AT₂，…，AT_m}。结合算法1可得算法2的时间复杂度为O(|U|×|GBS|×|m|)。

例1  　表1是一个多专家面试学生的决策信息表。其中：U＝{x₁，x₂，x₃，x₄，x₅，x₆}表示6位不同的学生；条件属性集B＝{a₁，a₂，a₃，a₄，a₅，a₆}表示生物、管理领域的专家团队对学生是否通过面试的赞成率；决策属性D＝{d}表示学生能否通过面试。其中：“1”表示通过面试；“0”则表示不通过面试。结合相关性质，可将属性集B分成B₁和B₂。其中B₁表示生物领域，B₂表示管理领域，即B＝{B₁，B₂}＝{{a₁，a₂，a₃}，{a₄，a₅，a₆}}，且设最小粒径size(GB)＝2(决定粒球GB是否继续迭代的最小样本数)。

表1  多专家面试学生评估表

Tab. 1  Multi-expert interview student assessment form

	a1	a2	a3	a4	a5	a6	d
x1	0.6	0.7	0.7	0.7	0.6	0.7	0
x2	0.8	0.8	0.7	0.6	0.6	0.6	1
x3	0.7	0.6	0.6	0.7	0.9	0.7	0
x4	0.8	0.7	0.7	0.8	0.7	0.8	1
x5	0.6	0.8	0.8	0.6	0.8	0.7	0
x6	0.6	0.8	0.8	0.6	0.7	0.8	0

下载:  CSV 下载:  表格图片

根据定义2可求得在粒度B₁和B₂下，粒球GB_i的球心c_i、半径r_i。各样本到球心C_i的距离d如表2所示。

表2  各样本到中心的距离

Tab. 2  Distance from each sample to center

	c1	c2
x1	0.007 7	0.015 7
x2	0.019 7	0.033 7
x3	0.023 7	0.033 7
x4	0.015 7	0.023 7
x5	0.025 7	0.011 7
x6	0.025 7	0.011 7

下载:  CSV 下载:  表格图片

C₁＝(0.68，0.73，0.68)；

C₂＝(0.67，0.72，0.72)；

r₁＝0.019 7；r₂＝0.021 7。

则根据定义4和表2可以求得粒球GB_i的样本集如下。

GB₁＝{x₁，x₂，x₄}；

GB₂＝{x₁，x₅，x₆}。

根据定义3计算粒球GB₁、GB₂的纯度为

Purity(GB₁)＝0.666 7，

Purity(GB₂)＝1。

又因为Purity(GB₁)＝0.666 7<1；且size(GB₁)≥2，因此，对GB₁进行第二次迭代，根据定义2计算簇心和半径可得

C₁₁＝(0.73，0.73，0.70)，r₁₁＝0.01。

同理根据定义4可得

GB₁₁＝{x₂，x₄}，

Purity(GB₁₁)＝1。

根据定义8，可以求得论域U在属性集B下近似为

注1  　例1中粒球GB_i使用的最小粒径是粒球内样本个数为2(样本分为2类)，在实际计算中，最小粒径的取值可以大于类别个数，否则会出现样本都是正域的情况，不利于正确地分类。

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

注3  　例1中计算簇心的方法是利用对所有f(x，c_i)，i＝1，2…，m取均值。实验中可以根据样本的类别标签，分别对所分的簇求均值从而得到簇心和半径。

采用多粒度粗糙集模型进行计算过程如表3所示，所得正域的结果与多粒度粒球粗糙集进行对比，结果如表4所示。

表3  例1在多粒度粗糙集模型下的计算结果

Tab. 3  Calculation 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}

下载:  CSV 下载:  表格图片

表4  例1在两个模型下计算正域的结果

Tab. 4  Positive region calculating results of example 1 under two models

模型	POSB(D)
MRST	{x1，x2，x3，x4，x5，x6}
MGBRST	{x1，x2，x4，x5，x6}

下载:  CSV 下载:  表格图片

通过对比和分析例1在粒球粗糙集模型(MGRST)和多粒度粒球粗糙集模型(MGBRST)正域生成的结果(见图1)，根据表3，可以得到POS_B(D)_－MGBRST⊆POS_B(D)_－MGRST。这是因为MGBRST模型结合了粒球粗糙集更细致的描述能力，更好地刻画了数据之间的内在联系，减少部分目标区域的样本，便于进一步决策。

图1  例1的多粒度粒球粗糙集的生成过程

Fig. 1  The generation process of granular-ball rough set model based on multi-granulation in example 1

注：  红色表示决策属性为“1”；蓝色表示决策属性为“0”。(a)、(b)表示论域U分别在粒度B₁和B₂下的划分。根据纯度的定义，可以得到(a)中的粒球纯度为1，则表示正域，若粒球纯度不为1，如(b)，则表示边界域。(c)表示对(b)粒球进行迭代，根据定义，最终结果如(d)，可以得到最终多粒度粒球粗糙集的正域。

下载:  原图 | 高精图 | 低精图

对于本文提出的多粒度粒球粗糙集模型生成正域算法，本节通过实验分析验证其可行性和有效性。所有实验硬件环境配置为AMD Ryzen 5 2500U CPU@ 2.00 GHz和8 GB内存的个人计算机，算法运行的软件环境为Matlab R2021b。

为了验证所提算法的有效性，在本节中，从UCI中选取了10组基准数据集进行相关的实验对比分析，其中前4组为连续型数据，后6组为离散型数据。数据的具体描述见表5。