张清华，薛玉斌，胡　峰，于　洪

(1.重庆邮电大学理学院，重庆 400065； 2.重庆邮电大学计算智能重庆市重点实验室，重庆 400065)

粗糙集近似集不确定性研究

张清华1，2，薛玉斌1，胡峰2，于洪2

(1.重庆邮电大学理学院，重庆 400065； 2.重庆邮电大学计算智能重庆市重点实验室，重庆 400065)

粗糙集用上、下近似集刻画不确定目标集合,而粗糙集的近似集用0.5-近似集作为不确定目标集合的近似集.本文首先分析了基于粗糙集的0.5-近似集相似度的属性约简算法存在理论不完备的不足，指出这种相似度具有随知识粒度变化不敏感的缺陷.然后进一步给出了多粒度知识空间下相似度的变化规律,提出了粗糙集近似集的模糊度概念,分析了粗糙集近似集的模糊度在多粒度知识空间下的变化规律,进而提出了相应的属性约简算法.从新的视角构建了目标概念与其近似集的差异性度量方法.

粗糙集;近似集;模糊度;不确定性;多粒度

1　引言

Pawlak教授提出的粗糙集是一种处理不精确不完全与不相容知识的数学理论[1].现已广泛应用于模式识别、知识发现、问题求解以及不确定性推理等领域[2,3],成为了一种重要的智能信息处理技术.粗糙集的扩展型主要有变精度粗糙集和更广泛的概率粗糙集.很多学者对此进行了讨论[4～6],如米据生、张贤勇、钱宇华等人讨论了变精度粗糙集,并利用它进行属性约简,取得了较好效果[7～10];Yao和Ziarko等人结合概率论和包含度提出了概率粗糙集,也取得了较好的理论成果[11～13].但不论是概率粗糙集还是变精度粗糙集,它们都只是构建了扩展的Pawlak近似算子,并没有用现有的知识粒来构建目标集合X的近似集.

我们在文献[14]中的研究发现,粗糙集的近似集虽然是一个可定义集,但它与目标概念X相比仍然存在一定的差异,为此我们定义了相似度这一概念来描述近似集与目标概念X的差异性.那么用这种差异性来做属性约简是否能得到更好的结果呢?我们在文献[15]中做了探讨性的实验,发现用0.5-近似集与目标概念X的相似度来做属性约简,得到的结果在识别率和约简时间上都有不同程度的提高.但是,当时我们并没有给出能用相似度做属性约简的合理性证明.另外概念之间的相似度,是近似集与目标概念整体上的差异性,因此它有随粒度变化不敏感的不足,这与我们想得到有用知识的目的相背.针对以上两个问题本文首先分析了不同知识粒度下粗糙集近似集的变化规律,发现当λ在区间[0.5,1]上时,相似度随知识粒度递减而单调递增.这说明了文献[15]中用0.5-近似集与目标概念的相似度作属性约简的合理性.其次定义了粗糙集近似集的模糊度,用熵的观点来描述了粗糙集近似集与目标概念X的差异性,这种表示方法弥补了相似度随粒度变化不敏感的不足,同时我们也分析了模糊度随知识粒度的变化规律,得到的结果与相似度的变化规律类似.最后我们提出了基于0.5-近似集模糊度的属性约简算法.

2　相关基本概念

为更清楚论述本文思想,先介绍近似集、相似度等相关概念,以便于后续定理的证明.

定义1(集合的相似度[14])设A,B是有限论域U上的两个子集,即A⊆U,B⊆U,定义映射;S:U×U→[0,1],即(A,B)→S(A,B).称S(A,B)是集合A,B的相似度,如果S(A,B)满足如下条件:

(1)对任意的A,B∈U,0≤S(A,B)≤1(有界性);

(2)对任意的A,B∈U,S(A,B)=S(B,A)(对称性);

(3)对任意的A,B∈U,S(A,A)=1,S(A,B)=0的充要条件是A∩B=∅.

设U={x1,x2,…,xk}为论域,知识空间为U/IND(R),对象子集X⊆U,则x(x∈U)属于集合X的隶属函数为[16]

(1)

我们通常用如图1来表示近似集：

定义3[17]在格〈P(A),⊆〉对应的Hasse图中,从∅到A的一条路径称为属性链.

例1设论域A={a1,a2,a3},则在格〈P(A),⊆〉对应的Hasse图中∅⊆{a1}⊆{a1,a2}⊆{a1,a2,a3},∅⊆{a1}⊆{a1,a3}⊆{a1,a2,a3},∅⊆{a2}⊆{a1,a2}⊆{a1,a2,a3}等都是属性链.

定义4[17]设格〈P(U),⊆〉中任意一条属性链为∅=B0⊂B1⊂…⊂Bm=A,则U/BmU/Bm-1…U/B1U/B0={U}.

定义6[19]∀A∈F(U),若映射d:F(U)→[0,1]满足条件:

(1)d(A)=0当且仅当A∈P(U);

(2)d(A)=1当且仅当∀xi∈UA(xi)=0.5;

(3)∀xi∈U(B(xi)≤A(xi)≤0.5∨B(xi)≥A(xi)≥0.5)→d(B)≤d(A);

(4)d(A)=d(Ac),这里Ac是A的补集.

则称映射d是F(U)上的一个模糊度,记为d(·).这里A(x)表示隶属函数,P(U)表示U上所有精确子集,F(U)表示U上所有模糊子集.

3　多粒度知识空间下相似度的变化关系

在分析相似度的变化规律之前,先给出几个数学上的基本结论,以便于后续定理的证明.

引理1设a,b,c,d,e,f为正实数,且f/e=(b+d)/(a+c),令b+d=f,a+c=e,若b/af/e.

引理2[14]设a,b,c,d为实数,且0

引理3[14]设a,b,c,d为实数,且0

设S=(U,C,D,A,f)为一个决策信息系统,U为论域,C为条件属性集,D为决策属性集.令B⊆C,且U/Bi+1U/Bi,则增量属性ΔBi=Bi+1-Bi一定对U/Bi中的知识粒进行了细分,我们不防设知识空间U/Bi中仅知识粒[xj]Bi(1≤j≤k)被增量属性ΔBi细分为两个部分,令]Bi+1这里中的其它知识粒保持不变.

定理1设U/Bi+1U/Bi,λ∈(0,0.5).若[xj]Bi⊄且,则).

证明∀x∈U,记U/Bi={[x1]Bi,[x2]Bi,…,[xk]Bi},则

故

同理可知,

因此

下面分情况讨论:

综上可知,定理1得证.证毕.

定理2设U/Bi+1U/Bi,λ∈(0,0.5).若[xj]Bi⊂且≥,则).

证明由定理1的证明可知:

综上可知,定理2成立.证毕.

定理3设U/Bi+1U/Bi.若λ≥0.5,则).

证明我们可分以下四种情形加以说明：

综上所述,定理3得证.证毕.

4　多粒度知识空间下模糊度的变化关系

4.1粗糙集近似集的模糊度

相似度从整体上描述了近似集与目标概念的差异性,然而这种差异性度量对知识粒度的变化不敏感,例如:

也就是说此时增量属性ΔBi并没有引起相似度的变化,因此ΔBi对目标概念X来说是不相关的.但很多时候这样的ΔBi是有意义的.那么如何才能体现这样一种变化呢?这里我们利用近似集中元素的隶属度,从熵的角度对近似集与目标集合X的差异性进行度量.

定义7(近似集的模糊度)设S为一个决策信息统,U为论域,C为条件属性集,D为决策属性集,B⊆C,设X为条件属性集B下论域U上的模糊集,记X的近似集为Bλ(X),称

(2)

为粗糙集近似集Bλ(X)的模糊度.

这里定义7中式(2)也满足定义6的条件[17].我们用模糊度来度量了近似集与目标概念的差异性,那么随着λ的变化,模糊度会有怎样的变化规律呢？

证明由定义7中式(2)可知

定理4表明模糊度随λ变化的规律性,比相似度随λ变化的规律性要强很多.那么近似集的模糊度在多粒度知识空间下的变化规律又是怎样的呢?

4.2多粒度知识空间下近似集模糊度的变化关系

容易推断当粗糙集正域和负域部分的知识粒被细分时,模糊度不发生改变.那么当细分发生在边界域上时模糊度会发生变化吗?

定理5设U/Bi+1U/Bi,U/Bi={P1,P2,…,Pr},U/Bi+1={Q1,Q2,…,Qt}(r

证毕.

定理5表明模糊度大于λ的知识粒被细分为两个模糊度均大于λ的知识粒时,近似集的不确定性会减小.

定理6设U/Bi+1U/Bi,U/Bi={P1,P2,…,Pr},U/Bi+1={Q1,Q2,…,Qt}(r

(1)若λ1i<λ,则

然而,

综上可知定理6成立.

证毕.

定理6说明当λ在区间[0.5,1]上以及粗糙集的边界域被细分时,近似集的模糊度也会呈单调性变化,因此也可设计基于近似集模糊度的属性约简方法.

5　基于模糊度的属性约简算法

定义8(决策信息系统的近似模糊度)设S为一个决策信息系统,U为论域,C为条件属性集,D为决策属性集,B⊆C,U/IND(B)={X1,X2,…,Xn}为条件属性集B在U上导出的划分,U/IND(D)={Y1,Y2,…,Ym}为决策属性集D在U上导出的划分,称

(3)

为决策信息系统S的近似模糊度.

显然式(3)也满足定义6中的模糊度公式.

定理7在决策信息系统S中,U为论域,C为条件属性集,D为决策属性集,B⊆C,U/IND(B)={X1,X2,…,Xn}为条件属性集B在U上导出的划分,U/IND(D)={Y1,Y2,…,Ym}为决策属性集D在U上导出的划分.若U/Bi+1U/Bi,则d0.5(DBi+1)≤d0.5(DBi).

显故

即d0.5(DBi+1)≤d0.5(DBi)成立.

证毕.

根据定理7我们可设计基于粗糙集近似集模糊度的属性约简算法.

该算法的时间复杂度主要来源于Step1和Step3.在Step1中的时间复杂度为O(|U|2),Step3中的时间复杂度为O(|U|3),因此该算法总的时间复杂度为O((|U|2)+(|U|3)).这与基于条件信息熵的属性约简算法的时间复杂度相同.我们将在后继的研究中,试图把该结果用到图像的边缘分割中,建立增量式特征选择和属性约简算法等,以希望提高图像边缘分割算法的精确性和容错性.

6　结束语

当前科技的不断发展让不确定性信息的研究变得日渐重要[20,21].粗糙集作为一种能有效处理不确定性信息的理论,其不确定性度量也是目前研究的一个重要内容[22,23].本文主要分析了相似度在多粒度知识空间下的变化规律,定义了近似集的模糊度,同时也分析了模糊度在多粒度知识空间下的变化规律.该研究为用近似集方法进行属性约简提供了理论基础.希望这些工作能够推动不确定信息理论的发展,扩展粗糙集理论模型,促进其应用.

[1]Pawlak Z.Rough sets[J].Information Journal of Computer and Information Science,1982,11(5):341-365.

[2]冯林,王国胤,李天瑞.连续值属性决策表中的知识获取方法[J].电子学报,2009,37(11):2432-2438.

Feng Lin,Wang Guoyin,Li Tianrui.Knowledge acquisition from decision tables containing continuous-valued attributes[J].Acta Electronica Sinica,2009,37(11):2432-2438.(in Chinese)

[3]张腾飞,肖健梅,王锡淮.粗糙集理论中属性相对约简算法[J].电子学报,2005,33(11):2080-2083.

Zhang Tengfei,Xiao Jianmei,Wang Xihuai.Algorithms of attribute relative reduction in rough set theory[J].Acta Electronica Sinica,2005,33(11):2080-2083.(in Chinese)

[4]Inuiguchi M,Yoshioka Y,Kusunoki Y.Variable-precision dominance-based rough set approach and attribute reduction[J].International Journal of Approximate Reasoning,2009,50(8):1199-1214.

[5]Xie G,Zhang J,Lai K K,et al.Variable precision rough set for group decision-making;An application[J].International Journal of Approximate Reasoning,2008,49(2):331-343.

[6]Liu J N K,Hu Y,He Y.A set covering based approach to find the reduct of variable precision rough set[J].Information Sciences,2014,275:83-100.

[7]Mi J S,Wu W Z,Zhang W X.Approaches to knowledge reduction based on variable precision rough set model[J].Information Sciences,2004,159(3):255-272.

[8]Qian Y,Zhang H,Sang Y,et al.Multigranulation decision-theoretic rough sets[J].International Journal of Approximate Reasoning,2014,55(1):225-237.

[9]张仕光,米据生,胡清华.粗糙ε-支持向量回归模型[J].南京大学学报 (自然科学版),2013,49(5):650-654.

Zhang Siguang,Mi Jusheng,Hu Qinghua.Roughε-support vector regression model[J].Journal of Nanjing University (Natural Science),2013,49(5):650-654.(in Chinese)

[10]李顺勇,钱宇华.基于多粒度粗糙决策下的属性约简算法[J].中北大学学报(自然科学版),2013,34(5):589-592.

Li Shunyong,Qian Yuhua.Attribute reduction algorithm based on multi-granularity rough decision[J].Journal of North University of China (Natural Science),2013,34(5):589-592.(in Chinese)

[11]Yao Y.Two semantic issues in a probabilistic rough set model[J].Fundamenta Informaticae,2011,108(3):249-265.

[12]Yao Y.Probabilistic rough set approximations[J].International Journal of Approximate Reasoning,2008,49(2):255-271.

[13]Ziarko W.Probabilistic approach to rough sets[J].International Journal of Approximate Reasoning,2008,49(2):272-284.

[14]张清华,王国胤,肖雨.粗糙集的近似集[J].软件学报,2012,23(7):1745-1759.

Zhang Qinghua,Wang Guoyin,Xiao Yu.Approximation sets and rough set[J].Journal of Software,2012,23(7):1745-1759.(in Chinese)

[15]Zhang Q,Guo Y,Xiao Y.Attribute reduction based on approximation set of rough set[J].Journal of Computational Information Systems,2014,10(16):6859-6866.

[16]Zhang Q,Wang J,Wang G,et al.The approximation set of a vague set in rough approximation space[J].Information Sciences,2015,300:1-19.

[17]王国胤,张清华.不同知识粒度下粗糙集的不确定性研究[J].计算机学报,2008,31(9):1588-1598.

Wang Guoyin,Zhang Qinghua.Uncertainty of rough sets in different knowledge granularities[J].Chinese Journal of Computers,2008,31(9):1588-1598.(in Chinese)

[18]王国胤.Rough集理论与知识获取[M].西安：西安交通大学出版社,2001.

Wang Guoyin.Rough Set Theory and Knowledge Discovery[M].Xi’an：Xi’an Jiaotong University Press,2001.(in Chinese)

[19]杨纶标,高英仪,凌卫新.模糊数学原理及应用[M].广州：华南理工大学出版社,2011.

Yang Lunbiao,Gao Yingyi,Ling Weixin.Principles and Applications of Fuzzy Mathematics[M].Guangzhou：South China University of Technology Press,2011.(in Chinese)

[20]苗夺谦,王国胤,刘清,等.粒计算:过去,现在与展望[M].科学出版社,2007.

Miao Duoqian,Wang Guoyin,Liu Qing,et al.Granular Computing:Past,Present and Future Prospects[M].Beijing:Science Press,2007.(in Chinese)

[21]Zhang Q,Wang J,Wang G,Hu F.Approximation set of the interval set in pawlak’s space[J].The Scientific World Journal,2014,Article ID 317387,1-12.

[22]杨明.决策表中基于条件信息熵的近似约简[J].电子学报,2007,35(11):2156-2160.

Yang Ming.Approximate reduction based on conditional information entropy in decision tables[J].Acta Electronica Sinica,2007,35(11):2156-2160.(in Chinese)

[23]Sun B Z,Ma W M.Uncertainty measure for general relation-based rough fuzzy set[J].Kybernetes,2013,42(6):979-992.

张清华男,1974年11月出生，重庆沙坪坝人.教授，硕士生导师.1998年、2003年和2009年分别在四川大学、重庆邮电大学和西南交通大学获理学学士、工学硕士和工学博士学位.现为中国人工智能学会粗糙集与软计算专委会秘书长，主要从事不确定信息处理、粗糙集与粒计算等方面的研究工作.

E-mail:zhangqh@cqupt.edu.cn

薛玉斌男，1990年5月出生，重庆潼南人.硕士研究生，研究方向为不确定信息处理、粗糙集与粒计算.

Research on Uncertainty of Approximation Set of Rough Set

ZHANG Qing-hua1,2,XUE Yu-bin1,HU Feng2,YU Hong2

(1.School of Science,Chongqing University of Posts and Telecommunications,Chongqing 400065,China; 2.Chongqing Key Laboratory of Computational Intelligence,Chongqing University of Posts and Telecommunications,Chongqing 400065,China)

Rough set describes an uncertain target set with upper and lower approximation sets,and approximation set of rough set uses 0.5-approximation set as an approximation set of the uncertain target set.In this paper,we firstly find that the theory of attribute reduction algorithm based on similarity between target set and its 0.5-approximation set is still incomplete,and this similarity is not sensitive to changing granularities.In order to overcome above shortcomings,the change rule of similarity with changing granularities in a multi-granularity space is analyzed,fuzzy degree of approximation set is defined,and the change rules of this fuzziness with changing granularities are analyzed in detail in a hierarchical space.Finally,a new attribute reduction algorithm is proposed.From a new perspective,a kind of differentiation measure between an uncertain target set and its approximation set is presented.

rough set;approximation set;fuzziness;uncertainty;multi-granularity

2014-12-17；

2015-03-22；责任编辑：李勇锋

国家自然科学基金(No.61472056,No.61309014,No.61379114)；重庆市自然科学基金(No.cstc2012jjA40032,cstc2013jcyjA4006)

TN911.23

A

0372-2112 (2016)07-1574-07

��学报URL:http://www.ejournal.org.cn

10.3969/j.issn.0372-2112.2016.07.008