F－模糊粗糙集及其约简*

邓大勇， 徐小玉， 裴明华

(浙江师范大学数理与信息工程学院，浙江金华 321004)

F－模糊粗糙集及其约简*

邓大勇， 徐小玉， 裴明华

(浙江师范大学数理与信息工程学院，浙江金华 321004)

模糊粗糙集的知识约简是模糊粗糙集理论的核心内容之一，从增量式的数据、海量数据或动态数据中挖掘出人们感兴趣的知识，是数据挖掘研究的一个重点，也是一个难点.首先，给出模糊粗糙集的属性重要度的定义及属性约简的定义;其次，从F－粗糙集及并行约简出发，并结合模糊粗糙集的属性重要度，提出了F－模糊粗糙集及其约简，为增量式或动态模糊决策表的属性约简提供了一种有效的方法;最后，通过实例验证了F－模糊粗糙集及其约简的可行性.

模糊粗糙集;F－粗糙集;属性约简;模糊决策表;属性重要度

0 引言

波兰科学家Pawlak于1982年提出的粗糙集理论［1］是一种处理不相容、不精确或不完全数据的强有力工具.目前，该理论成功地应用于机器学习、模式识别、过程控制等各种领域.粗糙集理论的一个重要应用是对信息系统进行约简.基于粗糙集理论的约简处理具有完整地保留信息系统的分类能力，但约简处理之前必需的离散化过程却会造成某种程度的信息损失，不能保留离散化后具有相同符号表示的属性值在实数值上存在的差异，使得粗糙集属性约简难以完整保留信息内容，且在实际生活中遇到的大都是模糊概念和模糊知识，所以经典粗糙集理论具有较大的局限性.针对这一问题，学者们对粗糙集理论进行了推广，提出了粗糙模糊集理论［2］和模糊粗糙集理论［3］，进一步拓宽了粗糙集理论的应用范围.其中，基于模糊粗糙集的属性约简在近些年备受关注，并取得了一定的研究成果［4－9］.模糊粗糙集利用数据相似度对属性值为实数值的数据集合进行约简，不需要预先对原始数据集合进行离散化，约简结果能更完整地反映原信息系统的分类能力.

知识约简是粗糙集理论的核心内容之一，尤以从增量式数据、海量数据或动态数据中挖掘出人们感兴趣的知识，是数据挖掘研究的一个热点，也是一个难点.粗糙集理论与应用的研究者也试图利用粗糙集理论的方法对增量式数据、海量数据或动态数据进行挖掘或约简，取得了较为丰富的研究成果［10－16］，其中文献［11－12］中提出的F－粗糙集和并行约简算法，是经典粗糙集知识动态约简理论的一种有效算法.F－粗糙集模型和并行约简将粗糙集和属性约简理论从单个决策表或单个信息表推广到多个，从整体和局部中抽象出事物的本质属性.

关于模糊粗糙集属性并行约简方法的研究相对于模糊粗糙集模型上、下近似算子［17－19］的研究及静态的属性约简［4－9］的研究比较少.为此，本文在文献［1，3，6，11－12］等的基础上，给出了模糊粗糙集属性重要度的定义及其相关概念，并且提出了F－模糊粗糙集模型和基于F－模糊粗糙集属性重要度的并行约简算法.可以看到，它是F－粗糙集和并行约简算法的推广，并且通过实例验证了其有效性.

1 F－粗糙集与并行约简、模糊粗糙集的基本知识

1.1 F－粗糙集

设DS=(U，A，d)是一个决策系统，则任何DT=(U'，A，d)(U'⊆U)是DS的决策子系统，P(DS)表示DS的幂集.对于一个决策子系统簇F⊆P(DS)，FIS={ISi}(i=1，2，…，n)表示与决策系统簇F相对应的信息系统簇，其中ISi=(Ui，A)，DTi=(Ui，A，d).

定义1［14］假设X是一个概念，N是一种情形，X|N表示在情形N下的概念X.在一个信息系统簇FIS={IS1，IS2，…，ISn}中，ISi∈FIS，X|ISi=X∩ISi，X|FIS={X|IS1，X|IS2，…，X|ISn}.如果不引起混淆，就可将X|N缩写为X.

假设X是信息系统簇FIS中的一个概念，则X关于属性子集B⊆A的上近似、下近似的定义分别为:

1.2 基于F－属性重要度的并行约简

定义2［14］给定一个决策子系统簇F，DTi=(Ui，A，d)∈F(i=1，2，…，n)，定义F中d依赖于A的程度为

其中，POS(DT，A，d)表示DT的正区域.

定义3［14］给定一个决策子系统簇F，DTi=(Ui，A，d)∈F(i=1，2，…，n)，定义F中属性a∈B或a∈A－B相对于B的重要度为

F－属性重要度有下列性质:

命题1［14］给定一个决策子系统簇F，a∈B⊆A.若σ(B，a)=0或σ'(B，a)=0，则属性a可以被约简.σ(B，a)=0或σ'(B，a)=0表明:若属性a被约简，则F的所有决策子系统都能保持正域不变.

命题2［14］给定一个决策子系统簇F，a∈A.若σ(A，a)＞0，则属性a为F－并行约简的核属性.

基于F－属性重要度的并行约简算法PRAS的基本思想为［15］:通过决策子表簇F中属性集合A下各元素的F－属性重要度找到F－并行约简的属性核，然后再通过F－属性重要度找到并行约简中的其他属性.

1.3 模糊粗糙集

设DS=(U，A，d)是一个模糊决策系统，A是条件属性集，d是决策属性集，且属性对应的是模糊等价关系(或简写为关系).定义4［6］设P是论域U的一个模糊等价关系，则元素u的模糊等价类为μ［u］P(v)=μP(u，v)，∀v∈U.通过定义4求出的是单个属性的模糊等价类的隶属函数.当P={P1，P2，…，Pm}且P⊆A为模糊条件属性集时，它所对应的模糊等价关系为它所包含的单个条件属性的笛卡尔乘积，即［6］

则P所对应的模糊等价类U/IND(P)={E1，E2，…，En}.一般情况下用P代表IND(P)，即U/P= {E1，E2，…，En}.对这种复合模糊等价类的隶属度定义如下［6］:

其中:U/Pi={Eiki|ki=1，2，…，ci};ci是由pi划分论域U所得模糊等价类的数目;Eiki是属性集P中第i个属性的ki个模糊等价类.

定义5［6］GD(P)={E|E∈U/P}为模糊关系簇P对论域U进行划分所得到的基本模糊等价类.本文若未特别说明，属性均表示模糊条件属性.

1.3.1 模糊粗糙集的上下近似

属性子集P⊆A，X表示U上的任意模糊集合，则可通过基本模糊等价类GD(P)来近似X，即用GD(P)中的子集Ei包含在X中的可能度与必然度描述Ei对X的近似程度，这种描述称为在关系P下、在等价类Ei上X的模糊粗糙上下近似(下文中均简写为上近似或下近似)，定义［6］如下:

其中:uEi(x)表示U中对象x包含在Ei中的程度;uX(x)表示x包含在X中的程度;μPX(Ei)表示Ei包含在X中的必然度，即Ei必然包含在X中的程度，∀i∈{1，2，…，n}.

在关系P下通过子集Ei描述X时，x在X中的必然包含程度μPX(x)［6］表示为

同理，可以给出上近似的定义为

1.3.2 模糊粗糙集的属性约简

定义6［6］条件属性P的模糊等价类E的模糊正域为

对象x关于模糊正域的隶属度为

其中，E∈GD(P).

定义7［6］决策属性对条件属性集的依赖度为

显然，0≤γP(d)≤1.

定义8 给定一个模糊决策系统DS=(U，A，d)，定义DS中属性a∈P或a∈A－P相对与P的重要度为σ(P，a)=γ(DS，P，d)－γ(DS，P－{a}，d)或σ'(P，a)=γ(DS，P∪a，d)－γ(DS，P，d).

2 F－模糊粗糙集

2.1 F－模糊粗糙集的上下近似

在模糊子信息表ISi中，设Eij是属于Ui/P的模糊等价类，Ui/P=GD(P|Ui)={Ei1，Ei2，…，Eici}表示论域Ui上的一个模糊划分(j=1，2，…ci，ci是由P划分论域Ui所得模糊等价类的数目).若X是Ui上的任意模糊集合，则可通过模糊条件集GD(P|Ui)来近似X，即用GD(P|Ui)中的子集Eij包含在X中的可能度与必然度描述GD(P|Ui)对X的近似程度，这种描述称为在关系P的等价类Eij对X的模糊粗糙上下近似，定义为

表1 模糊决策表DS

例1 模糊决策系统DS=(U，A，d)(见表1)，U={1，2，…，10}为论域，P1，P2，P3为模糊条件属性，d为模糊决策属性.信息系统簇FIS={IS1，IS2，IS3}.X是一个模糊概念，X= {0，0.50，0.56，0.24，0.64，0.45，0.48，0.80，0，0.64}.下面分别计算在模糊等价关系P2下X在DS和FIS中的上下近似隶属度(即可能度和必然度).

首先，在模糊决策系统DS=(U，A，d)中计算X在关系P2下的上下近似(如表2所示)，并将所得结果与X的原隶属度作柱状图(见图1)进行比较.

其次，计算在信息系统簇FIS={IS1，IS2，IS3}中X关于关系P2的上下近似(即可能度和必然度).其中:ISi={Ui，A，d}(i=1，2，3);U1={1，2，3，4，5};U2={6，7，8，9，10};U3={2，3，4，5，8，9，10}.计算结果如表3～表5，并将各子表所得上下近似与原隶属度作柱状图如图2～图4.由此可以在不同的层次上观察到关系P2对模糊概念X的近似程度，从而可得各元素的上下近似度.以对象3为例，上近似隶属度下近似隶属度:

表2 X在DS中关于关系P2的可能度和必然度

表3 X在IS1中关于关系P2的可能度和必然度

表4 X在IS2中关于关系P2的可能度和必然度

表5 X在IS3中关于关系P2的可能度和必然度

图1 X的原隶属度与X在DS中关于关系P2的可能度、必然度之间对比图

图2 X的原隶属度与X在IS1中关于关系P2的可能度、必然度之间对比图

图3 X的原隶属度与X在IS2中关于关系P2的可能度、必然度之间对比图

图4 X的原隶属度与X在IS3中关于关系P2的可能度、必然度之间对比图

最后，通过上述计算和对图像的比对(还是以对象3为例说明)知，当只在模糊决策表DS中通过关系P2对对象3在模糊概念X中的隶属度进行描述时，上近似度μPX(x)=0.70，下近似度μPX(x)= 0.24，则可看到这种情形下并不能很好地说明关系P2对对象3在模糊概念X中的隶属度的近似.但是，在信息系统簇FIS={IS1，IS2，IS3}下，通过和，以及观察图1～图3，可以更清楚地看到关系P2对对象3在模糊概念X中的隶属度的近似的程度.因此，可以更好地评价关系P2对模糊概念的近似程度.

2.2 F－模糊粗糙集的属性约简

定义9 在ISi中模糊条件属性集为P，d为模糊决策属性，U/d={qj|j=1，2，…，cd}，则模糊等价类qj上下近似分别是:

其中:E∈GD(P|Ui)，j={1，2，…，cj};cj是由d划分论域U所得模糊等价类的数目.

定义10 在ISi中条件属性的模糊等价类E的模糊正域为

x对模糊正域的隶属度为

其中:j={1，2，…，cj};cj是由d划分论域U所得模糊等价类的数目;E∈GD(P|Ui).

定义11 在FIS={ISi}(i=1，2，…，n)中决策属性对条件属性集P的依赖度为

显然，0≤γP(d)≤1.

定义12 给定一个决策子系统簇F，DTi=(Ui，A，d)∈F(i=1，2，…，n)，定义F中属性a∈P或a∈A－P相对于P的重要度分别为

定义12是对模糊决策系统中属性重要度定义的扩展，如果F中只含有一个元素，那么F－属性重要度就为该决策系统的模糊属性重要度.F－模糊粗糙集的属性重要度有下列性质:

命题3 给定一个决策子系统簇F，a∈A.若σ(A，a)＞0，则属性a为F－模糊并行约简的核属性.当然，通常情况下，当σ(A，a)大于某个指定的阈值δ(0≤δ＜1)时，属性a才被认为是核属性.

命题4 给定一个模糊决策子系统簇F，a∈P⊆A.若σ(P，a)≤ξ或σ'(P，a)≤ξ，则表明:若属性a被约简，则F所有模糊决策子系统都能保持模糊条件属性对模糊决策属性的近似程度不变(ξ≥0为给定的阈值.因本文的讨论范围是在模糊粗糙集中，有一定的模糊性，故不能绝对地要求σ'(P，a)=0).因此，属性a可以被约简.

2.3 基于F－属性重要度的模糊并行约简

并行约简是在若干个信息子系统或决策子系统中寻找稳定的、泛化能力强的条件属性约简，以适应增量式数据、海量数据或动态数据.根据F－属性重要度，有如下选择模糊粗糙集属性的算法(算法1).算法1借鉴了文献［6，15］算法的思想，根据属性的重要度来分层识别相关属性，最后可得到一个属性的模糊并行约简.再用约简后的属性集构建粒度，则在该粒度层次上进行各种推理运算的性价比最高.

F－属性重要度的并行约简算法F－PRAS的基本思想为:通过决策子表簇F中属性集合A下各元素的F－属性重要度找到F－并行约简的属性核，然后再通过F－属性重要度找到并行约简中的其他属性.

算法1 基于F－模糊属性重要度的模糊并行约简算法(简称F－PRAS)

输入:F⊆P(DS).

输出:F的一个模糊并行约简.

第1步 P=Ø，

第2步 对于任意a∈A，如果σ(A，a)＞0，那么P=P∪{a}，

第3步 M=A－a，

第4步 重复进行如下步骤，直到M=Ø:

1)对任意a∈M，计算σ'(P，a)//σ'(P，a)=γ(F，P∪a，d)－γ(F，P，d);

2)对任意a∈M，如果σ'(P，a)≤ξ//1＞ξ≥0为给定的阈值(因为本文的讨论范围是在模糊粗糙集中，具有一定的模糊性，所以不能绝对地要求σ'(P，a)=0，一般情况下取ξ=0.05)，那么M=M－{a};

3)选择F－属性重要度非零且最大的元素a∈E，P=P∪{a}，M=M－{a}(添加属性集M中F－属性重要度非零且最大的属性到并行约简P中).

第5步 输出并行约简P.

显然，算法1主要是从整体和局部两方面来构成一个树结构的组合搜索过程.首先，从局部子表上计算出决策属性对条件属性的依赖度;其次，在整体视角下，计算出决策属性对条件属性的依赖度和条件属性的重要度;最后，得到原属性集的一个并行约简.可以看到，这个约简是在局部和整体、微观和宏观均考虑到的前提下得到的，很好地体现了原属性集的特性.下面以一个实例进一步说明并行约简算法.

例2 模糊决策系统DS=(U，A，d)(表1)，U={1，2，…，10}为论域，P1，P2，P3为模糊条件属性，d为模糊决策属性.F={DSi}(i=1，2)是DS的模糊决策子系统，FIS={ISi}(i=1，2)是与F相对应的决策系统簇.如表6和表7所示.

表6 决策子系统IS1

表7 决策子系统IS2

根据相似函数，可计算出论域中各对象对模糊等价类的隶属度，结果如表8和表9所示.计算在子表IS1，IS2中对象对模糊正域的隶属度，结果如表10所示.

表8 IS1中各对象对模糊等价类的隶属度

表9 IS2中各对象对模糊等价类的隶属度

表10 IS1，IS2中各对象对模糊正域的隶属度

可以得出在模糊并行约简算法下决策属性对条件属性的依赖度为

通过上述计算可以得到各属性的依赖度，继而可以得到属性的重要度.下面先计算各属性的依赖度，然后应用基于F－模糊属性重要度的模糊并行约简算法的思想求例2的属性约简.

首先令P=Ø，然后通过计算得 σ(A，P1)=γ(A，d)－γ(A－{P1})=－0.08＜0，同理可得σ(A，P2)=0.10＞0，σ(A，P3)=－0.01＜0.即得到属性集A的核属性为P2，则P=P∪P2=P2，M=A－{P2}={P1，P3}.故可以求出:

于是，M=M－{P1}={P3}.进一步得到P=P∪{P3}={P2，P3}，则M=M－{P3}=Ø，即算法1结束.通过F－模糊属性重要度的模糊并行约简算法得到了例2的属性约简P={P2，P3}.

3 结论与展望

模糊粗糙集是数据分析的一种强有力的理论工具，然而，对模糊粗糙集在并行约简方面的应用研究却鲜有报道.本文首先改写了模糊粗糙集的上、下近似的定义;然后，在此基础上，给出了模糊粗糙集的属性重要度定义，并且提出了一种基于F－模糊属性重要度的模糊知识并行约简的启发式算法;最后，通过实例分析表明了F－模糊粗糙集及其约简的可行性.

本文主要研究了模糊粗糙集的并行约简问题，但是本文的不足之处在于:算法1中更适合实际的阈值ξ的具体取值范围需要进一步地通过实验确定，并且目前只是研究模糊属性不多时的并行约简.因此，下一步的研究方向就是对阈值ξ取值范围的确定和高维属性的并行约简.

［1］Pawlak Z.Rough sets［J］.International Journal of Information and Computer Science，1982，11(5):341－356.

［2］Banerjee M，Pal S K.Roughness of a fuzzy set［J］.Information and Computer Science，1996，93(3/4):235－246.

［3］Dubois D，Prade H.Rough fuzzy sets and fuzzy rough sets［J］.International Journal of General System，1990，17(2/3):191－209.

［4］Fayyard U M，Iran K B.What should be minimized in a decision tree?［C］//AAAI'90 Proceedings of Eighth National Conference on Artificial Intelligence.Boston:AAAI Press，1990:749－754.

［5］Shang C，Barnes D，Shen Q.Facilitating efficient mars terrain image classification with fuzzy－rough feature selection［J］.International Journal of Hybrid Intelligent Systems，2011，8(1):3－13.

［6］Jensen R，Shen Qiang.Fuzzy－rough sets for descriptive dimensionality reduction［C］//Proceedings of 11th Internet Conf on Fuzzy Systems.Hawaii:IEEE，2002:29－34.

［7］程籦，苗夺谦，冯琴荣.基于模糊粗糙集的粒度计算［J］.计算机科学，2007，34(7):142－149.

［8］徐菲菲，苗夺谦，魏莱，等.基于互信息的模糊粗糙集属性约简［J］.电子与信息学报，2008，30(6):1372－1375.

［9］聂作先，刘建成.一种面向连续属性空间的模糊粗糙约简［J］.计算机工程，2005，31(6):163－165.

［10］Bazan G J.A comparison of dynamic non－dynamic rough set methods for extracting laws from decision tables［C］//Polkowski L，Skowron A.Rough sets in knowledge discovery 1:Methodology and applications.Heidelberg:Physica－Verlag，1998:321－365.

［11］Deng Dayong.Comparison of parallel reducts and dynamic reducts in theory［J］.计算机科学，2009，36(8):176－178.

［12］邓大勇，陈林.并行约简与F粗糙集［M］//王国胤，李德毅.云模型与粒计算.北京:科学出版社，2012:210－216.

［13］邓大勇，王基一.并行约简的现状与发展［J］.中国人工智能学会通讯，2011，1(5):16－18.

［14］Deng Dayong，Wang Jiyi，Li Xiangjun.Parallel reducts in a series of decision subsystems［C］//Proceedings of the Second International Joint Conference on Computational Sciences and Optimization(CSO2009).Sanya:IEEE，2009:377－380.

［15］Deng Dayong.Parallel reducts and its properties［C］//2009 IEEE International Conference on Granular Computing.Nanchang:IEEE，2009: 121－125.

［16］张文修，梁怡，吴伟志.信息系统与发现［M］.北京:科学出版社，2003.

［17］Tsang C C，Chen Degang，Lee W T，et al.On the upper approximation of covering generalized rough sets［C］//Proceeding of the Third International Conference on Machine Learning and Cybernetics.Shanghai:IEEE，2004:26－29.

［18］Yeung S，Chen Degang，Tsang C C，et al.On the generalization of fuzzy rough sets［J］.IEEE Trans on Fuzzy System，2005，13(3):343－361.

［19］Wu Weizhi，Mi Jusheng，Zhang Wenxiu.Generalized fuzzy rough sets［J］.Information Science，2003，151(5):263－282.

(责任编辑 陶立方)

F-fuzzy rough sets and its reducts

DENG Dayong， XU Xiaoyu， PEI Minghua

(College of Mathematics，Physics and Information Engineering，Zhejiang Normal University，Jinhua Zhejiang 321004，China)

The fuzzy－rough attribute reduction is one of the important topics in fuzzy－rough set theory.It is a focal difficult point to mine interesting knowledge from incremental data，mass data and dynamic data.It was defined the fuzzy rough set's attribute significance and the concept of attribute reduction;The F－fuzzy rough sets and its reducts were proposed then based on the attribute significance of fuzzy rough sets，F－rough sets and its parallel reducts.The F－fuzzy rough sets's reducts were showed to be an effective methodology for attribute reduction on incremental and dynamic fuzzy decision table;Furthermore the feasibilities of F－fuzzy rough sets and its parallel reducts were confirmed by examples.

fuzzy rough sets;F－rough sets;parallel reducts;fuzzy decision tables;attribute significance

TP311

A

1001－5051(2015)01－0058－09

�:2014－02－12;

2014－05－21

邓大勇(1969－)，男，江西新干人，副教授，博士.研究方向:粗糙集理论及应用.

10.16218/j.issn.1001－5051.2015.01.010