基于压缩决策表的乐观多粒度粗糙集粒度约简算法

王必晴，梁昌勇，齐 平，黄永青

(1.铜陵学院 数学与计算机学院，安徽 铜陵 244000；2.合肥工业大学 管理学院，合肥 230009)

0 引 言

粗糙集理论[1]是一种处理不精确、不一致、不完整信息与知识的数学工具，在决策分析、机器学习、知识发现等领域得到了广泛且成功的应用[2-5]。在此基础上，从粒计算的角度出发，产生了多粒度粗糙集模型[6]，进而使得粗糙集理论针对具体问题有了多视角、多层次分析处理的能力。多粒度粗糙集已发展出乐观多粒度粗糙集和悲观多粒度粗糙集2种模型。目前的多粒度粗糙集粒度约简主要是基于悲观多粒度粗糙集[7-10]，对决策表的全部对象利用粒度重要性进行约简，采取的是“求同排异”的近似策略，即所有决策者使用共同满意的方案进行决策，存在分歧的方案则不能用于决策。随着粒空间的增加，悲观多粒度粗糙集的近似精度反而越小，因此，该策略在一定程度上略显保守和苛刻[11]。同时，决策表中存在的冗余数据会影响粒度约简的效率。本文从另一个角度出发，针对乐观多粒度粗糙集，利用线性时间排序算法，对冗余的决策表进行压缩，引入分布约简的概念[12]，提出一种高效的基于压缩决策表的乐观多粒度粗糙集粒度约简算法，提高粒度约简的效率，采取的是“求同存异”的近似策略，为粒度约简问题的解决提供一个有效的思路。

1 乐观多粒度粗糙集

下面先给出相关的概念。

定义1设S=(U,AT,V,f)是一个信息系统，令A={A1,A2,…,Am}为AT的m个属性子集族，∀X⊆U，则X关于A1,A2,…,Am的乐观多粒度粗糙集下近似集、上近似集分别定义为[6]

(2)式中，～X为X的补集。序偶

(3)

称为X关于属性子集A1,A2,…,Am的乐观多粒度粗糙集。X的乐观多粒度粗糙集的A边界域定义为

(4)

X的乐观多粒度粗糙集的A正域定义为

(5)

X的乐观多粒度粗糙集的A负域定义为

(6)

如果只有一个粒度，乐观多粒度粗糙集就退化成经典的Pawlak粗糙集。

2 粒度约简算法

文献[12]给出了分布约简的概念，本文将其应用到乐观多粒度粗糙集，定义乐观多粒度粗糙集下近似分布粒度约简。

2.1 乐观多粒度粗糙集下近似的分布粒度约简

首先给出乐观多粒度粗糙集下近似集定义。

定义2设S=(U,C∪D,V,f)是一个决策表，令A={A1,A2,…,Am}为C的m个属性子集族，R⊆A，U/D={X1,X2,…,Xk}，则U/D关于R的乐观多粒度粗糙集下近似集定义为

(7)

定义3设S=(U,C∪D,V,f)是一个决策表，令A={A1,A2,…,Am}为C的m个属性子集族，R⊆A，若R满足以下2个条件

ψ(R,D)=ψ(A,D)

(8)

∀R′⊂R,ψ(R,D)⊂ψ(A,D)

(9)

则称R为A相对于D的一个乐观多粒度粗糙集下近似分布粒度约简。

2.2 快速等价类划分算法

在多粒度粗糙集中，下近似的求解是粒度约简算法中的基本操作，而等价类划分又是求下近似的重要步骤；同时，本文后面要介绍的决策表压缩也要计算等价类划分，因此，提高等价类划分的效率是粒度约简的关键问题。文献[7]中最坏情况下需要计算|AT|个划分的时间复杂度是O(|AT||U|2)，因此，该文献计算下近似集的时间复杂度也为O(|AT|·|U|2)。实际上，等价类划分的时间复杂度可进一步降低。

求等价类的一般方法是将对象集U中的个体进行两两比较，判断它们的每个属性取值是否都相同，因而时间复杂度为O(|C||U|2)[13]。文献[14]使用了快速排序，使等价类划分算法的时间复杂度降低为O(|C||U|log|U|)。在以上文献的基础上，本文给出一个利用档位快速排序求解U/C的算法，时间复杂度进一步降低为O(|C||U|)，在此基础上可对决策表进行压缩和下近似求解。

按照属性集C对U分类，即依次以每个条件属性ai对U排序。为了进一步提高排序速度, 在相关文献[15]的基础上，本文提出利用时间复杂度仅为O(|U|)的档位快速排序来进行等价类划分。档位快速排序是对快速排序的一种推广，基本设计思想如下[15]。对于每个属性ai，根据实际经验按照属性值前m个二进制位的值重新安排所有记录，将待排序序列分割成若干档位，使前面档位的属性值小于后面档位的属性值，然后将记录条数大于等于2的档位中的对象用快速排序法排序。这样，整个序列被排序。然后依次以剩余属性对U排序，分析排序后的U，划分出等价类。

算法1利用档位快速排序求解U/C的算法。

输入:S=(U,C∪D,V,f),U={u1,u2,…,un},C={a1,a2,…,ak};

输出:U/C。

//依次以每个条件属性ai(i=1,2,…,k)对U排序

for(i=1;i<=k;i++)

{//f[2m]初始化为0

for(r=0;r<=2m-1;r++)

f[r]=0;

//计算每个档位记录的条数

for(j=1;j<=n;j++)

{计算uj属性值前m个二进制位的值v[uj];

f[v[uj]]++;}

//计算每个档位的起始地址

a[0]=0;

for(r=1;r<=2m-1;r++)

a[r]=a[r-1]+f[r-1];

//重新放置每条记录

for(j=1;j<=n;j++)

{S′[a[v[uj]]]=Rj;a[v[uj]]++;}

//将记录条数大于等于2的档位用快速排序法排序

for(r=0;r<=2m-1;r++)

if(f[r]>=2)

将S′[a[r]…a[r]+f[r]-1]中的对象按照ai用快速排序法排序;}

//划分等价类

for(j=2;j<=n;j++)

输出H。

由于上述档位快速排序循环次数为|C|，故算法1中排序总的时间复杂度为O(|C||U|)，之后的等价类划分时间复杂度也为O(|C||U|)，从而算法1的时间复杂度为O(|C||U|)。

下面是一个等价类划分的例子。表1是一个冗余决策表，由于根据实际情况可以确定这些数据只需用2位二进制表示，故可取m=2。

表1 一个冗余决策表

利用算法1计算表1的U/{a,b,c}。首先，以属性a对U排序，U被分为3个档位{u3}, {u2,u7,u4,u5}和{u1,u6}。接着，将2档位和3档位用快速排序法排序。这样，通过以属性a排序后，U为{u3,u2,u7,u4,u5,u1,u6}。类似地，我们可以依次以其他条件属性对U排序。通过以属性b排序后，U为{u3,u2,u7,u1,u6,u5,u4}。通过以属性c排序后，U为{u6,u5,u4,u3,u2,u7,u1}。最终，U/{a,b,c}为{{u6}, {u5,u4}, {u3}, {u2,u7}, {u1}}。

2.3 压缩决策表

在决策表S=(U,C∪D,V,f)中，过去的粒度约简算法都是建立在整个对象集U上。实际上经分析，在粒度约简的过程中基于整个对象集U进行计算并不是必要的。针对决策表中存在的冗余对象而造成粒度约简的低效，进一步提高粒度约简算法的效率，本文对决策表中冗余对象进行了处理，降低了决策表的规模，并由此生成压缩决策表，并在此基础上进行粒度约简。下面给出压缩决策表的定义和定理1。

定理1若R是决策表S′=(U′,C∪D,V′,f′)的一个粒度约简，则R一定是决策表S=(U,C∪D,V,f)的一个粒度约简。

依据定义4和定理1，下面给出压缩决策表的生成算法。

算法2压缩决策表生成算法。

输入:S=(U,C∪D,V,f)；

输出:S′=(U′,C∪D,V′,f′)。

U′=∅;

for(i=1;i<=d;i++)

输出S′=(U′,C∪D,V′,f′)。

在算法2中，等价类划分的时间复杂度为O(|C||U|)，求U′的时间复杂度为O(|U|)，输出S′的时间复杂度为O(|U|)，故算法2总的时间复杂度为O(|C||U|)。

根据算法2可求得表1所对应的压缩决策表，如表2所示。

表2 压缩决策表

2.4 下近似算法

在多粒度粗糙集计算中，下近似求解是粒度约简的关键步骤，因此，如何提高计算效率是一个重要问题，下面给出定理2，做为下近似计算算法的理论基础。

证明根据定义1，定理2显然成立。

由定理2，可得以下求下近似集的算法3。

算法3计算X的乐观多粒度粗糙集下近似集的算法。

输入:S=(U,C∪D,V,f)，C的m个属性子集族A={A1,A2,…,Am}，X⊆U；

输出:X关于A的乐观多粒度粗糙集下近似集L。

L=∅;

for(i=0;i<=m;i++) //Ai循环

{调用算法1,计算U/Ai;

//[u]Ai循环

for(j=1;j<=[u]Ai的个数;j++)

{if([u]Ai⊆X)

L=L∪[u]Ai;

if(L==U)

结束循环; }}

输出L。

在算法3中，计算U/Ai的时间复杂度是O(|C|·|U|)，计算[u]Ai循环的时间复杂度是O(|U|)。因此,在最坏情况下，算法3的时间复杂度为O(|C|2·|U|)。因为在大数据集的情况下，一般有|C|<<|U|[16]，例如UCI中的mushroom，有8 000多个对象，却只有22个属性，所以O(|C|2|U|)的时间复杂度优于文献[7]中O(|AT||U|2)的时间复杂度，提高了计算下近似集的效率。

2.5 粒度重要性

在粒度约简中，粒度的重要性可以作为启发信息使得被搜索空间以更快的速度减小。所以，下面给出粒度重要性的相关概念。

定义5设S=(U,C∪D,V,f)是一个决策表，令A={A1,A2,…,Am}为C的m个属性子集族，给定粒度G∈A，如果ψ(AG,D) ⊂ψ(A,D)，则称G在A中关于D是必要的；如果ψ(AG,D)=ψ(A,D)，则称G在A中关于D是不必要的。A中所有必要的粒度构成的集合称为A的D核粒度，记为coreD(A)。

记|ψ(A,D)|为ψ(A,D)所含对象的个数，后同。

算法4核粒度求解算法。

输入:S=(U,C∪D,V,f)，C的m个属性子集族A={A1,A2,…,Am}；

输出:coreD(A)。

coreD(A)=∅;

调用算法3,计算ψ(A,D)

for(i=1;i<=m;i++)

{调用算法3, 计算ψ(AAi,D);

if(|ψ(AAi,D)|<|ψ(A,D)|)

coreD(A)=coreD(A)∪Ai;}

输出coreD(A)。

证明根据定义1，定理3显然成立。

通过定理3可知，对于乐观多粒度粗糙集，归入下近似集合的对象数随粒空间的增加而单调增加。这样，我们可以利用这个变化的趋势来刻画粒度的重要性。而且，从算法4和后面的粒度约简算法可看出，粒空间个数的增加还将一步步导致ψ(A,D)、核粒度以至粒度约简计算时间的增加。

定义6设S=(U,C∪D,V,f)是一个决策表，令A={A1,A2,…,Am}为C的m个属性子集族，R⊆A，G∈A-R，则G关于D的粒度重要性定义为

ess(G,R,D)=|ψ(R∪G,D)|-|ψ(R,D)|

(10)

由以上定义可知，当且仅当ess(G,R,D)=0时，粒度G关于D是下近似不重要的。ess(G,R,D)的值越大，说明在已知粒度集A和R的条件下，粒度G对决策D就越重要。本文把ess(G,R,D)作为计算粒度约简时的启发式信息，减少搜索空间，加快搜索速度。

2.6 粒度约简算法

依据上述分析，设计出乐观多粒度粗糙集的下近似粒度约简算法如下。

算法5乐观多粒度粗糙集的下近似粒度约简算法。

输入:S=(U,C∪D,V,f)，C的m个属性子集族A={A1,A2,…,Am}；

输出:决策表S的一个粒度约简R。

调用算法2,计算压缩决策表S′=(U′,C∪D,V′,f′);

//以下所有计算都基于压缩决策表S′

调用算法4,计算核粒度coreD(A);

R=coreD(A);

调用算法3,计算|ψ(R,D)|和|ψ(A,D)|;

while(|ψ(R,D)| < |ψ(A,D)|)

{for(i=1;i<=|A-R|;i++)

计算ess(Ai); //Ai∈A-R

选择具有最大ess(Ai)的Ai;

R=R∪{Ai};

计算|ψ(R,D)|;}

输出R。

在算法5中，计算压缩决策表的时间复杂度为O(|C||U|)，计算核粒度的时间复杂度为O(|C|3·|U/C||U/D|)，计算|ψ(R,D)|的时间复杂度是O(|C|2|U/C||U/D|)，while循环的时间复杂度是O(|C|4|U/C||U/D|)。因此，计算乐观多粒度粗糙集的下近似粒度约简的时间复杂度为O(|C|4·|U/C||U/D|)。由于文献[7]中给出的粒度约简算法时间复杂度为O(|C|3|U|3)，而大数据环境下，一般有|C|<<|U|，故本文算法5的时间复杂度低于文献[7]中的算法时间复杂度，具有较好的粒度约简效率。

3 实例分析

为了说明本文提出算法的可行性和有效性，下面通过一个投资决策的实例来具体分析，在表2所示压缩决策表的基础上对其进行粒度约简。假设表2表示一个投资评估决策，3位专家{a,b,c}对5个投资方案{u1,u2,u3,u4,u6}进行评估，每位专家的评估意见互相独立，评价指标有3种{0,1,2}，分别表示{差,中,好}，方案的决策结果为{0,1}，表示{反对,赞成}。将每位专家的评估意见看成一个粒度空间，即粒度集A={a,b,c}，D={d}。在乐观多粒度空间下考虑哪些专家的评估对于目标决策是必要的，哪些是可以忽略的。下面我们利用基于压缩决策表的乐观多粒度粗糙集粒度约简算法对其进行粒度约简。表2对应的投资决策信息表如表3所示。

表3 投资决策信息表

1)首先，计算决策类：U/D={Y1,Y2}={{u1,u4,u6},{u2,u3}}。然后，计算各个粒度空间：U/a={{u1,u6},{u2,u4},{u3}}，U/b={{u1,u2,u3},{u4,u6}}，U/c={{u1,u2},{u3,u4,u6}}。

2)然后，根据算法4计算核粒度：ψ(A,D)={{u1,u4,u6},{u3}}，ψ(Aa,D)={{u4,u6}}，ψ(A,D)={{u1,u6},{u3}}，ψ(Ac,D)={{u1,u4,u6},{u3}}，因为|ψ(Aa,D)|<|ψ(A,D)|而且|ψ(A,D)|<|ψ(A,D)|，故coreD(A)={a,b}。

3)最后，根据算法5计算粒度约简：令R=coreD(A)，因为|ψ(R,D)|=|ψ(A,D)|=4，所以{a,b}即为粒度约简。

从以上结果可以看出, 求得的粒度约简与原始多粒度空间具有同样的的决策能力，在各个粒度互相独立的情况下，专家a和专家b的评估构成最终的粒度约简，而专家c的评估在决策中可以忽略。从而可以在更简洁的粒度空间里解决其他相关问题，为决策分析提供了一个新的理论思考方向。

4 实验结果

为了验证并且比较算法的时间复杂度,选用UCI机器学习数据库中的6个数据集在PC机上进行实验。实验环境为Windows 10, Inter Core i7 CPU，8 GByte内存。数据集的基本信息如表4所示。分别采用文献[17]中的乐观多粒度粗糙集粒度约简算法和本文粒度约简算法计算获得约简所需要的时间，从而比较算法的效率，对本文算法性能进行评估。为了保证粒度约简的准确度，各数据集的属性值进行了相应的预处理。因为粒度约简的时间与2个因素有关，一个是粒空间个数，一个是数据集所含对象数，所以采用以下2组实验分别研究。

4.1 同一数据集不同粒空间个数的约简效果比较

数据集的粒空间划分按以下方法设计。对于表5中的同一数据集，分别以随机选择的1，2，3个条件属性组成一个粒空间，将条件属性集分为若干粒空间。如果条件属性个数不能被2或3整除，则剩下的属性组成一个粒空间。针对不同的情况，分别进行粒度约简，实验结果如图1所示。其中，算法1和算法2分别表示文献[17]中的乐观多粒度粗糙集粒度约简算法和本文粒度约简算法。

表4 UCI数据集

由图1可知，算法2粒度约简的运行时间少于算法1。而且，随着粒空间个数变多，算法1的约简时间较快上升，而算法2的约简时间只是略有增加，这个结果在Sonar数据集上体现得尤其明显，这是算法2平稳性的表现。因此，本文算法在约简效率和平稳性方面相对于算法1都有所提高。

图1 不同粒空间个数的约简时间比较Fig.1 Time of reduction for different granular space number

4.2 相同粒空间基数不同数据集的约简效果比较

粒空间基数即每个粒空间所含属性的个数。图2为粒空间基数等于2时，不同数据集的粒度约简效果比较。因前3个数据集上的约简时间远远小于后3个数据集，二者不在同一个数量级，故分成2个子图显示。

图2 不同数据集上的约简时间比较Fig.2 Time of reduction on different data sets

从图2可以看出，算法2在效率上优于其他算法，而且对象数越多，算法2在效率上的提高就越显著，验证了算法2较好的性能。

5 结 论

本文针对乐观多粒度粗糙集模型，定义了乐观多粒度粗糙集下近似分布粒度约简的概念，分析了快速等价类划分算法，给出了压缩决策表和下近似集的计算方法，讨论了作为启发式信息的粒度重要性的定义方法，最后提出了基于压缩决策表的乐观多粒度粗糙集粒度约简算法，对比其他算法分析了其计算的时间复杂度，并通过实例验证了该算法的可行性。下一步的研究方向是构建基于三支决策的多粒度粗糙集模型，并设计其粒度约简算法。