您的当前位置：首页不同知识粒度下粗糙集的不确定性研究

不同知识粒度下粗糙集的不确定性研究

来源：爱go旅游网

第31卷　第9期2008年9月

计　　算　　机　　学　　报

CHINESEJOURNALOFCOMPUTERS

Vol.31No.9

Sept.2008

　不同知识粒度下粗糙集的不确定性研究

王国胤

1)2)

1),2)

　　张清华

1),2)

(西南交通大学信息科学与技术学院　成都　610031)

(重庆邮电大学计算机科学与技术研究所　重庆　400065)

摘　要　粗糙集的不确定性度量方法,目前主要包括粗糙集的粗糙度、粗糙熵、模糊度和模糊熵.在不同知识粒度下,从属性的角度,给出了分层递阶的知识空间链,发现在分层递阶的知识粒度下部分文献中定义的粗糙集的粗糙熵和模糊度随知识粒度的变化规律不一定符合人们的认识规律.从信息熵的角度提出了一种粗糙集不确定性的模糊度度量方法,证明了这种模糊度随知识粒度的减小而单调递减,弥补了现有粗糙熵和模糊度度量粗糙集不确定性的不足.最后,分析了在不同知识粒度下粗糙度和模糊度的变化关系.关键词　粗糙度;粗糙熵;模糊度;知识粒度;商空间中图法分类号TP18

UncertaintyofRoughSetsinDifferentKnowledgeGranularitiesWANGGuo2Yin1

),2)　ZHANGQing2Hua1

),2)

(SchoolofInformationScience&Technology,SouthwestJiaotongUniversity,Chengdu　610031)

(InstituteofComputerScience&Technology,ChongqingUniversityofPostsandTelecommunications,Chongqing　400065)

Abstract　Rougness,roughentropy,fuzziness,andfuzzyentropyaremajormethodsformeasur2ingtheuncertaintyofroughsets.Indifferentknowledgegranularitylevels,ahierarchicalknowl2edgespacechainisproposedbasedontheattributesininformationsystems.Someregularitiesofthechangingofroughentropyandfuzzinessofaroughsetwiththeknowledgegranularityarefoundtobeinconsistentwithhumancognition.Anewmethodformeasuringthefuzzinessofroughsetsisproposedbasedoninformationentropy.Thefuzzinessmeasuredbythenewmethodismonotonouslydecreasingwiththerefiningofknowledgegranularityinapporiximationspaces.Itovercomestheproblemofroughnessandroughentropy.Finally,therelationsofthechangingofroughnessandfuzzinessareanalyzedindifferentknowledgegranularities.

Keywords　roughness;roughentropy;fuzziness;knowledgegranularity;quotientspace

1　引　言

进入21世纪以来,不确定性问题的研究工作受

到越来越多的关注[1].如何对不确定性信息和数据进行更加有效的处理,从而发现不确定性信息中蕴

涵的知识和规律,是一个重要的研究课题[2].Zadeh在1965年提出的模糊集(Fuzzysets)理论[3],Pawlak在1982年提出的粗糙集(Roughsets)理论[4]和张钹、张铃在1990年提出的商空间理论[5]是粒计算(granularcomputing)的三大基础数学理论,是处理不确定性问题的有效方法,已广泛应用于模

收稿日期:2008207214.本课题得到国家自然科学基金(60573068,60773113)、重庆市教委科学技术研究项目(KJ060517)和重庆市自然科学基金重点项目(2008BA2017)资助.王国胤,男,1970年生,博士,教授,博士生导师,主要研究领域为粗糙集理论、粒计算、数据挖掘、知识技术等.E2mail:wanggy@cqupt.edu.cn.张清华,男,1974年生,博士研究生,主要研究方向为智能信息处理、粒计算等.

9期王国胤等:不同知识粒度下粗糙集的不确定性研究15

式识别、知识发现、问题求解以及不确定推理等领域.模糊集作为经典康托集的推广,利用隶属函数来表示对象关于集合的隶属程度,重在区分属于同一集合的不同对象间的隶属程度,其不足之处在于其隶属函数往往需由专家给出,带有一定的主观性;粗糙集理论是处理不完全和不精确信息的一种有效数学工具[6],建立在对论域分类的基础上,将不确定知识用已知知识库中的知识来刻画,对不确定问题的描述和处理比较客观,但粗糙集理论是研究在给定的空间(知识基)上不同概念的表示、转换和相互依存问题的,其论域是点集,元素之间没有拓扑关系;商空间理论基于复杂问题粒化的思想,建立了一种商结构的形式化问题求解理论体系,利用保真、保假原理来高效地获得问题的解或近似解,它不仅针对给定的商空间(知识基)来讨论知识的表达问题,而且利用对象之间的结构(偏序结构或拓扑结构),在所有可能的商空间中找出最合适的商空间,从不同商空间(不同角度)观察同一问题,以便得到对问题不同角度的理解,最终合成对原问题总的解(近似解)[5].可以说,模糊集理论是一种“软”计算方法,粗糙集理论是“硬”计算方法,而商空间理论是介于模糊集和粗糙集之间的一种问题求解(近似解)的计算方法,模糊商空间可以利用分层递阶结构“廉价”地描述问题的不确定性[7].另外,Gau和Buehrer提出的Vague集理论,通过对模糊对象赋予真、假隶属函数来处理模糊性,是模糊集理论的扩充[8].依靠各自的特点和优势,这些方法已经广泛应用于对不确定、不精确、不完整信息的处理以及对大规模海量数据的挖掘和对复杂问题的求解[9].李德毅认为[1]:在主、客观世界普遍存在的不确定性中,随机性和模糊性是最重要的两种形式,不确定性和确定性并非完全对立,在一定程度上可以相互转化.例如,某一层次的不确定性可能是更高层次上的确定性,种种不确定性中还可能隐藏着某些确定的规律等.人工智能研究人员的任务,就是寻找并且能够形式化地表示不确定性中的规律性,至少是在某种程度上的规律性,从而使机器能够模拟人类认识客观世界、认识人类本身的认知过程.当前,对于粗糙集的不确定性度量的方法主要有粗糙度、粗糙熵、模糊度和模糊熵.

在同一知识粒度的近似空间下,Chakrabarty[10]等人较为详细地讨论了粗糙集的模糊性度量问题;Banerjee[11]和Huynh[12]对模糊集的粗糙度进行了研究;王国胤[13215]等人从信息观的角度分析了决策

信息系统的不确定性,并讨论了代数观和信息观意义下粗糙集的不确定性的异同;梁吉业[16218]等人从信息熵、条件熵、互信息和知识粒度的角度分析了粗糙集的不确定性,并给出了一种新的粗糙集的粗糙熵;苗夺谦[19221]等人从粒计算和信息表示等角度研究了知识的粒度、知识的粗糙度与信息熵之间的关系.

然而,随着属性个数的变化,论域空间形成一个分层递阶结构(金字塔结构,即商空间).当知识空间中的知识粒度严格递减时,一个粗糙集的粗糙度、粗糙熵、模糊度和模糊熵将怎样变化?它们之间的关系又是如何?关于这方面的研究工作,已有一定的研究基础,特别是研究粗糙精度、粗糙度、分类精度、粗糙熵和条件熵在不同知识粒度的近似空间下的变化已经比较详尽[11216,18221].综合分析上述研究工作可以发现,粗糙集的粗糙度随着知识粒度的减小而单调递减,这符合人们的认知直觉.但是,很多实际例子表明,当属于一个集合的正域或负域中的知识颗粒被细分时,粗糙集的粗糙度将不发生变化;而且当属于集合边界域中的知识颗粒被细分时,它的粗糙度可能也不发生变化,这与人们的认知直觉不吻合.为了克服这个问题,有的研究者提出了粗糙熵,如Liang[18]等人定义了一种粗糙熵,它是集合X的粗糙度与近似空间中的知识粒度之积,并得到结论:这种粗糙熵随着知识颗粒的细分严格单调递减.这个结论在一定程度上弥补了用粗糙度度量粗糙集不确定性的不足.但是,我们分析发现,如果对集合X负域的知识颗粒(与X无关)进行细分,粗糙度将不变(符合人们的认知规律),但粗糙熵却严格递减(不符合人们的认知规律).这说明与集合X无关的知识颗粒的变化也会导致X的粗糙熵的变化,这与人们对不确定性问题的认知不符.

为此,需要进一步研究粗糙集不确定性的另一度量方式———粗糙集的模糊度.虽然在同一知识粒度的近似空间下粗糙集的模糊性得到研究者的关注[10,16,18221],但是关于粗糙集的模糊度在不同知识粒度的近似空间(分层递阶的近似空间)下将如何变化的研究工作甚少.粗糙集的模糊度随着近似空间中知识颗粒的细分将如何变化?对这个问题的探索,有利于发现不确定性问题中隐藏的某些确定规律.从认知角度来讲,集合X随着与它有关的知识颗粒的细分,它的不确定性要降低,模糊度也应该降低.但是,文献[10]给出的粗糙集模糊度在知识粒度细化的过程中可能反而会逐渐增加,这与人们认知

1590计　　算　　机　　学　　报2008年

不确定性问题的直觉相悖.

本文从属性空间的角度,主要讨论不同知识粒度的近似空间下(即不同层次的商空间)粗糙集的模糊度的变化问题,提出一种基于信息熵的粗糙集的模糊性度量方法,证明这种模糊度随着知识粒度的减小而单调递减,弥补粗糙度和粗糙熵对粗糙集不确定性度量的不足.这种模糊度的物理背景非常清楚,它既刻画出集合X的边界域中属于X的那部分元素“贡献”的不确定性,也刻画出不属于X的那部分元素“贡献”的不确定性,更精确地描述了粗糙集的不确定性.通过分析发现,如果集合X的边界域中的知识颗粒被“成比例”地细分,这种粗糙集的模糊度不会发生变化;如果集合X的边界域中的知识颗粒被“不成比例”地细分,这种粗糙集的模糊度将严格递减.这个结论克服了现有部分度量粗糙集不确定性方法的不足,与人们对不确定性问题的认知规律非常吻合.

本文第2节介绍相关基本概念;第3节讨论不同知识粒度下粗糙集的不确定性度量问题;第4节提出一种基于信息熵的粗糙集模糊度度量方法;第5节讨论不同知识粒度下粗糙集的粗糙度和模糊度的变化关系;第6节是结束语.

2.2　分层递阶的近似空间

任给一个信息系统S=(U,A,V,f),A={a1,a2,…,am}是属性集,任给一个属性子集B(BΑA),我们可以得到论域U的一个划分U/B.U/B中的每个元素[x]B([x]B表示元素x(x∈U)的等价类)表示近似空间的一个知识颗粒.设P(A)表示集合A={a1,a2,…,am}的幂集.不难得出:代数系统〈P(A),Α〉构成一个完备的偏序格.其中,󰂡是这个偏序格的最小元,A是最大元.

定义2.　在格〈P(A),Α〉对应的Hasse图中,从󰂡到A的一条路径称为属性链.例1.　A={a1,a2,a3}〈,P(A),Α〉对应的Hasse图如图1所示.

图1　格〈P(A),Α〉

2　相关基本概念

2.1　知识的粒度

如󰂡Α{a1}Α{a1,a2}Α{a1,a2,a3},󰂡Α{a1}Α

{a1,a3}Α{a1,a2,a3}和󰂡Α{a3}Α{a1,a3}Α{a1,a2,a3}等都是属性链.

定义1

V,f),其中U={x1,x2,…,xn}是非空有限对象集,称为“论域”,A={a1,a2,…,am}是属性集,V=

a∈C

[6]

　设一个信息系统是四元组S=(U,A,

∪Va,

Va称为属性a的“值域”,fa:U→Va是信息

定义3[21].　设U={x1,x2,…,xn}为非空有限

论域,P′={P′′′″={P″″″1,P2,…,Pl}和P1,P2,…,Pm}

(ϖP″(P′为U上的两个划分空间,如果ΠP′iΑi∈P′j∈P″

P″′是P″的细划分空间,记为P′ΜP″.j)),则称P

函数.不可分辨关系:IND(B)={(x,y)∈U×U|

Πa∈B(fa(x)=fa(y))}是U上的等价关系,所有等价类的集合记为U/IND(B),简写为U/B.

一个论域的划分构成粗糙集的一个近似空间,划分中的每一个分块称为一个知识颗粒,度量知识粒度的方法很多,这里我们采用Liang等人给出的知识粒度的度量方法[18].设U={x1,x2,…,xn},属性集B(BΑA)对论域的划分U/B={X1,X2,…,Xm},则U/B的知识粒度定义为

1G(U/B)=

|U|

定义4[22].　设U={x1,x2,…,xn}为非空有限论域,P′={P′′′″={P″″1,P2,…,Pl}和P1,P2,…,

P″′ΜP″,且m}为U上的两个划分空间,如果P

(P′ϖP′″′是P″的严格细′(ϖP″i划分空间,记为P′;P″.

定理1.　设格〈P(A),Α〉中的任意一条属性链为󰂡=B0在任何一条属性链下,对象集U被分成不同的划分,这些划分在“Μ”关系下构成一个金字塔结构,称为分层递阶的近似空间.

例2.　一个信息系统U={x1,x2,…,x10},A={a1,a2,a3},如表1所示.

i=1

|X|∑

(1)

容易证明:素个数,下同).

ΦG(U/B)Φ1(|・|表示集合的元

9期王国胤等:不同知识粒度下粗糙集的不确定性研究

表1　一个信息系统

1591

XΑU,则属性集合B的熵定义为

x10

x11

x12

a2a3x2x3x4x5x6x7x8

1001101101101101101112222233343343351|Xi||Xi|

E(B)=-log2

i=1|U|

∑(2)

X在划分U/B上的粗糙熵定义为

EB(X)=ρB(X)E(B)

(3)

如果取属性链󰂡Α{a1}Α{a1,a2}Α{a1,a2,

a3},可得到如下的分层递阶近似空间:

U/󰂡={{x1,x2,…,x10}};

U/{a1}={{x1,x2,x3,x4,x5,x6,x7},

{x8,x9},{x10,x11,x12}};

U/{a1,a2}={{x1},{x2,x3,x4,x5,x6,x7},

{x8,x9},{x10,x11,x12}};

U/{a1,a2,a3}={{x1},{x2,x3,x4,x5,x6},{x7},

{x8},{x9},{x10,x11},{x12}}.

集合X的粗糙熵是粗糙度与属性集合B的熵之积.

2.3.3　粗糙集的模糊度

设U={x1,x2,…,xn}是非空有限集,A是U上的模糊集,A(xi)是模糊集的隶属函数.用P(U)表示集合U上的所有经典集合,F(U)表示集合U上的所有模糊集合.显然,P(U)ΑF(U).

定义8[23].　ΠA∈F(U),若映射d:F(U)→

[0,1]满足条件:

(1)d(A)=0当且仅当A∈P(U);(2)d(A)=1当且仅当Πxi∈UA(xi)=(3)Πxi∈UB(xi)ΦA(xi)Φ在这个分层递阶的近似空间中,随着属性个数的增加,知识颗粒逐渐“细化”.2.3　粗糙集不确定性的几种度量方法2.3.1　粗糙集的粗糙度

1;2

定义5[6].　在一个信息系统中,IND(B)是U上的一个不可分辨关系,[x]B表示对象x的等价类,对象子集XΑU,X的下近似集(BX)、上近似集(B󰁫X)和边界域(BNB(X))分别定义如下:

BX={x∈U|[x]BΑX},B󰁫X={x∈U|[x]B∩X≠󰂡},BNB(X)=B󰁫(X)-B(X).

1∨B(xi)ΕA(xi)Ε2

→d(B)Φd(A);

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

).则称映射d是F(U)上的一个模糊度,记为d(・

设U是非空对象集,对象子集XΑU,则对于任意的x(x∈U),x属于集合X的隶属函数为

μX(x)=

定义6[22].　在一个信息系统中,IND(B)是U上的一个不可分辨关系,[x]B表示对象x的等价类,对象子集XΑU,X的粗糙精度和粗糙度为

粗糙精度:αB(X)=粗糙度:

BNB(X)R(X)

ρ=.B(X)=1-αB(X)=1-R󰁫(X)R󰁫(X)

R(X)

;

R󰁫(X)

|X∩[x]B||[x]B|

(4)

Bμ显然,0ΦX(x)Φ1,它表示任意一个元素属于

集合X的程度.令FBX={μX(x1),μX(x2),…,BBBμX(xn)},则FX是集合U上的一个模糊集(即FX∈

F(U)).由粗糙集上、下近似和边界的概念,不难

得出:

BX={x∈U|μX(x)=1};

α显然,对于任意的XΑU,都有0ΦB(X)Φ1且

ρ0ΦB(X)Φ1.

如果B󰁫(X)=B(X)=X,即ρB(X)=0(或αB(X)=1),称X关于B是精确的;如果B(X)B󰁫X={x∈U|0<μX(x)Φ1}.

模糊度是度量不确定问题的有力工具,很多研究者对粗糙集的模糊度进行了分析,Chakrabarty[10]等人提出粗隶属函数可以导出模糊集,并利用模糊集与它的最邻近清晰集间的距离来度量粗糙集的模糊性.

定义9[10].　设A是U上的模糊集,与A有关的最邻近的清晰集记为A,其定义为

A(xi)=1,

A(xi)<015A(xi)>015.A(xi)=015

关于粗糙集的粗糙熵的定义形式很多,这里我们采用Liang提出的粗糙熵.

定义7[18].　设U={x1,x2,…,xn},属性子集

B(BΑA)对论域的划分U/B={X1,X2,…,Xm},

0或1,

1592计　　算　　机　　学　　报2008年

一般地,当A(xi)=015时,取A(xi)=1,这时

A=A015,这里A015表示A的015截集.

间下,随着知识颗粒的细分,不同层次上的知识粒度有何变化规律?定理2和定理3揭示了这个变化规律.

定理2[21].　设格〈P(A),Α〉中的任意一条链为󰂡=B0G(U/Bi)(i=0,1,2,…,m-1;下同).

Chakrabarty[10]等人利用模糊集FBX和它的最邻

近清晰集FBX之间的距离给出了粗糙集的两种模糊性度量.

(1)线性模糊度:

dKl(F)=

i=1

|μ(x)-μ(x)|∑

BXi

(5)

定理3[21].　设格〈P(A),Α〉中的任意一条链为󰂡=B0U/Bi,则G(U/Bi+1)(2)二次模糊度:dKq(FX)=

2nn

i=1

∑BB2

(μX(xi)-μX(xi))

(6)

在分层递阶的近似空间上,随着知识粒度的减小,粗糙集的粗糙度将如何变化?定理4回答了这个问题.

定理4[6].　设格〈P(A),Α〉中的任意一条链为󰂡=B0ρU,有ρBi+1(X)ΦBi(X).

定理4揭示了集合X的粗糙度随知识粒度减小而单调递减.注意:如果U/Bi+1;U/Bi(严格的

细分关系),不一定有ρBi(X)(严格单调Bi+1(X)<ρ递减).如例2中,X={x1,x2,x3,x4,x5,x6,x7,x8,

x9},取属性链󰂡<{a1}<{a1,a2}<{a1,a2,a3},则U/{a1,a2,a3};U/{a1,a2},而ρ{a1,a2,a3}(X)=

其中,μX(xi)表示xi在模糊集FX中的隶属函数.

2.3.4　粗糙集的模糊熵

定义10[24].　ΠA∈F(U),若映射e:F(U)→

)满足条件:[0,+∞

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

(2)e(A)取得最大值当且仅当Πxi∈UA(xi)=(3)Πxi∈UB(xi)ΦA(xi)Φ1;2

1∨B(xi)ΕA(xi)Ε2

→e(B)Φe(A);

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

ρ{a1,a2}(X).这表明集合X在不同知识粒度的近似空间中可能得到相同的粗糙度.为了克服这个问题,

Liang[18]给出一种粗糙熵EB(X)=ρB(X)E(B),该粗糙熵随着近似空间中知识粒度减小会有何变化规律呢?

定理5[21].　设格〈P(A),Α〉中的任意一条链为󰂡=B0U,若G(U/Bi+1)).则称映射e是F(U)上的一个模糊熵,记为e(・

梁吉业[16218]等人建立了粗糙集的一种模糊熵:

EL(F)=B

i=1

μ(x)(1-μ(x))∑

(7)

并得出了相应的结论:一个精确集的模糊熵等于0,一个粗糙集合与它的补集具有相同的模糊性.2.3.5　信息熵

信息熵是一个非常广泛的概念,1948年Shannon信息熵[25]的提出为信息的不确定度量奠定了理论基础,Klir基于Shannon熵提出了一种度量不确定性的信息熵[26]:

H(F)=-B

定理5表明,随着分层递阶的近似空间中知识粒度的减小,EB(X)严格单调递减.这个结论在一定程度上弥补了粗糙度的缺陷.但是,我们分析发现,当近似空间中知识粒度的减小是由于集合X负域中的知识颗粒(与X无关)被细分时,粗糙度不会改变(符合认知规律),但粗糙熵EB(X)却严格递减

(不符合认知规律).这表明与集合X无关的知识颗

i=1

BXμX(xi)log2∑

Bμ(x)

(8)

)不满足模糊度的定义(定义8),容易验证,H(・

不是模糊度.

粒(X的负域中的知识颗粒)细分时,粗糙集的粗糙熵会减小,与人们的认知规律不吻合.

例3.　设U={x1,x2,…,x10},U/Bi={{x1,

x2,x3},{x4,x5,x6,x7},{x8,x9,x10}},U/Bi+1={{x1,x2,x3},{x4,x5,x6,x7},{x8,x9},{x10}},

3　不同知识粒度下粗糙集的

不确定性度量

目前,度量粗糙集不确定性的方法主要有粗糙度、粗糙熵、模糊度和模糊熵.在分层递阶的近似空

X={x3,x4,x5,x6,x7},则ρBi(X)=ρBi+1(X)=

3;7

9期王国胤等:不同知识粒度下粗糙集的不确定性研究1593

3(3(8+log7298+log1082),EBi+1(X)=2),7070

所以EBi(X)>EBi+1(X).

EBi(X)=

度,我们进一步分析发现:粗糙集的模糊性来自边界域的两个部分,一部分是边界域中属于集合X的元素,一部分是边界域中不属于集合X的元素,而式(8)的信息熵只考虑了前面一部分,没有涉及第二部分.为此,我们提出一种新的基于信息熵的粗糙集的模糊度度量方法:

1BB

μdZ(F)=-[μX(xi)lnX(xi)+nln2i=1

因此,用粗糙熵度量粗糙集的不确定性还是存在一定的局限性.根据商空间理论中解释“模糊”和“清晰”之间粒度变化的关系“模糊在一定粒度下会变得清晰,而清晰在一定粒度下会变得模糊”和李德

]

毅指出的[1“不确定性和确定性并非完全对立,在一定程度上可以相互转化”,本文接下来重点讨论,在分层递阶的近似空间中,粗糙集模糊度随着知识粒度的变化而变化的情况.

设格〈P(A),Α〉中的任意一条链为󰂡=B0FXi与FXi+1的模糊度的大小关系如何呢?对这个问

∑

(1-μX(xi))ln(1-μX(xi))](9)

μ直观上讲,式(9)由μX(xi)lnX(xi)和(1-BB

μX(xi))ln(1-μX(xi))两部分信息熵构成,前者主

要反映属于集合X的元素“贡献”的不确定性,后者主要反映不属于集合X的元素“贡献”的不确定性,这两部分同时考虑才能更精确地刻画粗糙集的不确

)满足定义8.定性.接下来,我们验证dZ(・B

证明.　dZ(FBxi∈U(μX)=0当且仅当ΠX(xi)=BBBμ0∨X(xi)=1),即FX是普通的康托集,FX∈P(U).

题的讨论要比粗糙度和粗糙熵复杂得多.

(1)如果U/Bi=U/Bi+1,对任意的模糊性度量方法,F与F

dKl

BBiX

Bi+1X

的模糊度都相等;

Bi+1X

(2)如果U/Bi+1;U/Bi,容易证明:dKl(F

)Φ

(FXi).但dKq(FXi+1)和dKq(FXi)的大小关系不定义8的条件(1)满足.

对于任意的xi(xi∈U),令μX(xi)=ti(0Φ

确定.

如例2中取X={x6,x7,x8,x9},U/{a1,a2};U/{a1},则

{a}2222222,,,,,,,1,1,0,0,0;FX1=

7777777

{a,a}222222FX12=0,,,,,,,1,1,0,0,0;

666666

{a,a}{a}221×7=dKl(FX12)=dKl(FX1)=;

1273

{a1)2224()dKqFX=×7=;

71273{a1,a2)2224()dKqFX=×6=.

61263)和dKq(・)来测量这个例子说明,如果用dKl(・

)来测量X=粗糙集的模糊度有以下缺陷:用dKl(・

{x6,x7,x8,x9}的模糊度,U/{a1,a2};U/{a1},

6G(U/{a1,a2})7ρ,这表明随着知识粒度的减小,粗糙度{a1}(X)=

{a,a}

在降低,然而X的线性模糊度却不变dKl(FX12)=

dKl(FX1),二次模糊度反而增加dKq(FX1dKq(FX1),这与人们的直觉相悖.

{a}{a}

{a,a2}

tiΦ1),令f(ti)=tilnti+(1-ti)ln(1-ti),易证,函

1数f(ti)在唯一的极值点ti=处取得最小值-ln2.

21B

所以,dZ(FB处取得最大值1.定X)在点μX(xi)=2

义8的条件(2)满足.

对于任意的xi(xi∈U),由于f(ti)=tilnti+

(1-ti)ln(1-ti)在区间

单调递减,在

11,1单调递增,在ti=处取得最小值,所以,2211dZ(F)=-f(ti)在区间0,单调递增,

2nln2i=1

∑

在

11,1单调递减,在ti=处取得最大值.因此,22

1BB′B

当μ或μi=μi=X(xi)=tiΦt′X(xi)ΦX(xi)=tiΕt′21B′B′μ时,有dZ(FBX(xi)ΕX)ΦdZ(FX).定义8的条2

件(3)满足.

BcB

dZ((FX))=dZ(FX)显然成立,定义8的条件

(4)满足.

)是粗糙集的一种模糊度.下面,综上所述,dZ(・

)随近似空间中知识粒度的减我们讨论模糊度dZ(・

4　基于信息熵的粗糙集模糊度

为了能够将信息熵应用来测量粗糙集的模糊

小的变化趋势.

定理6.　设格〈P(A),Α〉中的任意一条链为

1594计　　算　　机　　学　　报2008年

󰂡=B0U/Bi,则对于任意的XΑU,都有dZ(FdZ(FXi).

Bi+1

)Φ

xi∈P1

∑

μXi(xi)-(1-μXi(xi))ln(1-μXi(xi))][-μXi(xi)ln

aa+b

=-aln-bln

ba+b

证明.　设U/Bi={P1,P2,…,Pr},U/Bi+1=

{Q1,Q2,…,Qt}(rxi∈Qi∪Qj

i+1i+1

(1-μ(xi))ln(1-μ(xi))]XX

∑

i+1i+1

(xi)lnμ(xi)-[-μXX

ΔBi=Bi-Bi+1表示属性增量.则属性增量ΔBi一定对U/Bi={P1,P2,…,Pr}中的至少一个元素进行细分.为简化证明,我们不妨设U/Bi中只有P1被

ΔBi分为两个部分(分为多个部分的证明情况类似),P1=Qi∪Qj(Qi,Qj∈U/Bi+1),U/Bi的其它元素不变(其它情况可以根据这种情况进行证明).下面分情况讨论:

(1)当P1∩X=󰂡时,对于任意的x(x∈P1),

BiμX(x)=

xi∈Qj

∑

i+1i+1

(xi)lnμ(xi)-[-μXX

i+1i+1

(1-μ(xi))ln(1-μ(xi))]XX

=-aln

aa+b1

-b1ln

b1a+b1

这里|Qj∩X|=a1=a,|Qj|-|Qj∩X|=b1a+b

-bln

ba+b

,因为

9f=9b

|P1∩X|=0.因为P1=Qi∪Qj(Qi∩Qj=

|P1|

a+b>0,所以f(a,b)关于b是增函数.因为b1aa+b

󰂡),所以,对于任意x(x∈Qi或者x∈Qj),μXi+1(x)=|Qi∩X||Qj∩X|==0.因此,属性增量ΔBi对

|Qi||Qj|

U/Bi={P1,P2,…,Pr}的细分不改变模糊集FXi的B

以-aln-blnba+bΕ-aln

aa+b1

-b1ln

b1a+b1

②如果QjΑX,则|Qi∩X|=a1xi∈Qi∪Qj

i+1

(1-μXi+1(xi))ln(1-μ(xi))]X

隶属函数值,即F=F

dZ(FXi).

XBi+1X

,所以dZ(FXi+1)=

∑

i+1i+1

(xi)lnμ(xi)-[-μXX

(2)当P1ΑX时,对于任意的x(x∈P1),μXi(x)=

|P1∩X|=1.由于P1=Qi∪Qj(Qi∩Qj=󰂡),所

|P1|

以,对于任意的x(x∈Qi或者x∈Qj),μXi+1(x)=

xi∈Qi

∑

i+1

(xi)lnμXi+1(xi)-[-μX

i+1i+1

(1-μ(xi))ln(1-μ(xi))]XX

|Qi∩X||Qj∩X|==1.因此,属性增量ΔBi对

|Qi||Qj|

U/Bi={P1,P2,…,Pr}的细分不改变模糊集FXi的

=-a1ln

a1a1+b

-bln

ba1+b

因为

9fa+b=ln>0,所以f(a,b)关于a是增函9aa

aa+b

隶属函数值,即FXi=FXi+1,即dZ(FXi+1)=dZ(FXi).

(3)当P1∩X≠󰂡,且P1∩X≠P1时,因为P1=Qi∪Qj,则|P1|=|Qi|+|Qj|(Qi∩Qj=󰂡),

BBBB

数.又因为a1a1a1+b

-bln

ba+b

-bln

ba1+b

1BiBi

μdZ(F)=[-μX(xi)lnX(xi)-nln2i=1

∑

③如果Qi∩X≠󰂡且Qi∩X≠Qi,Qj∩X≠󰂡且Qj∩X≠Qj,令|X∩Qi|=a1>0,|X∩Qj|=

a2>0,|Qi|-|X∩Qi|=b1>0,|Qj|-|X∩Qj|=b2>0,此时,a1+a2=a,b1+b2=b.

xi∈P1

(1-μXi(xi))ln(1-μX(xi))]

1nln2

xi∈P1B

∑

μXi(xi)-[-μX(xi)ln

(1-μXi(xi))ln(1-μX(xi))]+

∑

μXi(xi)-(1-μXi(xi))・[-μXi(xi)ln

aa+b

BBB

∑

μXi(xj)-[-μX(xj)ln

ln(1-μXi(xi))]=-aln

-bln

ba+b

;

(1-μXi(xj))ln(1-μXi(xj))],

xi∈Qi∪Qj

i+1

(1-μ(xi))ln(1-μXi+1(xi))]X

∑

i+1

(xi)lnμXi+1(xi)-[-μX

下面分类讨论:

①如果Qi∩X=󰂡,设|P1∩X|=a且|P1|-|P1∩X|=b,则公式

=-a1ln

a1a1+b1

-b1ln

b1a1+b1

9期王国胤等:不同知识粒度下粗糙集的不确定性研究1595

{a,a2}

(a-a1)ln(b-b1)ln

a-a1-a-a1+b-b1b-b1.

a-a1+b-b1

a1a1+b1

由第3节可知,dKq(FX1473-b1ln

b1a1+b1

463>dKq(FX1)=

{a}

)计算得,这与人们的认知相悖.用dZ(・

{a}

又令F(a1,b1)=-a1ln

(a-a1)ln

dZ(FX1)=

-112ln22255ln+ln7777

×7+0

a-a1b-b1-(b-b1)ln,

a-a1+b-b1a-a1+b-b1

dZ(FX1

{a,a2}

1×65188;12ln2-112ln2

2244ln+ln6666

求解F(a1,b1)的最大值.对F(a1,b1)求偏导数,得方程组:

9F=09a19F=09b1

解该方程组得:

)=×6+0

1×45156.12ln2

{a}

{a,a2}

可见,dZ(FX1)>dZ(FX1

度的减小而单调递减.

).这说明二次模糊

)随着知识粒度随着知识粒度的减小反而增加,dZ(・

a1a2aa=.此时,=,这表明函数b1bb2b

a1a2aaF(a1,b1)在==处取得最大值-aln-b1b2ba+bbln

ba+b

.所以,F(a1,b1)Φ-aln

aa+b

续例3.设U={x1,x2,…,x10},U/Bi={{x1,

x2,x3},{x4,x5,x6,x7},{x8,x9,x10}},U/Bi+1={{x1,x2,x3},{x4,x5,x6,x7},{x8,x9},{x10}},X={x3,x4,x5,x6,x7},则ρBi(X)=ρBi+1(X)=EBi(X)=

-bln

ba+b

根据以上①,②和③,有

xi∈P1

3;7

[-μ∑

Xiii

(xi)lnμX(xi)-(1-μX(xi))ln(1-μX(xi))]BB

3(3(

8+log7298+log1082),EBi+1(X)=2),7070

111,,,1,1,1,1,0,0,0),所333

xi∈Qi∪Qj

∑

BBiBi

μ[-μXi(xi)lnX(xi)-(1-μX(xi))・Bi

Bi+1X

所以,EBi(X)>EBi+1(X);而模糊集FXi和FXi+1相

ln(1-μ(xi))].所以,dZ(F)ΦdZ(F).

BiX

等(FXi=FXi+1=

综上所述,定理6得证.证毕.当属性增量ΔBi将P1划分为Qi,Qj(Qi≠󰂡,

Qj≠󰂡,Qi∩Qj≠󰂡)两个细的知识颗粒时,即P1=Qi∪Qj,XΑU,如果

以,dZ(FXi)=dZ(FXi+1).这说明与集合X无关的知

)识颗粒的细化导致粗糙熵严格递减,但模糊度dZ(・

不变.

式(9)依赖两部分信息熵,既利用了度量不确定性的Shannon熵,也结合粗糙集的特点,同时构造集合X的边界域中属于X的那部分元素“贡献”的不确定性和不属于X的那部分元素“贡献”的不确定性,非常直观.随着集合X的边界域上的知识颗粒的“不成比例”的细分,粗糙集的模糊度将严格递减;而集合X边界域上的知识颗粒被“成比例”细分时,粗糙集的模糊度不变.这更加准确地刻画出人们对不确定性问题的认知规律.

|P1∩X||Qi∩X||Qj∩X|==,

|P1|-|P1∩X||Qi|-|Qi∩X||Qj|-|Qj∩X|

则称P1被属性增量ΔB“成比例”细分.特别地,当i

Qi=󰂡或者Qj=󰂡(即P1没有被分解)时,我们视

为一种特殊的“成比例”细分.

推论1.　当且仅当属性增量ΔBi将U/Bi=

{P1,P2,…,Pr}中的每个知识颗粒进行“成比例”细

分时,有dZ(F)=dZ(F).

如果属性增量ΔBi将U/Bi={P1,P2,…,Pr}中的某个知识颗粒进行“不成比例”细分后,粗糙集的模糊性将严格递减.

续例2.　设X={x6,x7,x8,x9},U/{a1,a2};

U/{a1},则

{a}

XBi+1X

5　不同知识粒度下粗糙集的粗糙度和

模糊度的变化关系

)和模糊度dZ(・)在分这里主要讨论粗糙度ρB(・

　FX1=　F

{a1,a2}

2222222,,,,,,,1,1,0,0,0;7777777

222222=0,,,,,,,1,1,0,0,0.

666666

层递阶的近似空间中随知识粒度的变化而变化的关系.

性质1.　设信息系统S=(U,A,V,f)中,BΑ

1596计　　算　　机　　学　　报2008年

A,XΑU,如果X是关于B精确的,则dKl(FX)=

在分层递阶的近似空间中,知识粒度随着粗糙集的粗糙度或模糊度的降低而必然降低.

性质7.　设信息系统S=(U,A,V,f)中,BΑ

A,XΑU,若ρB(X)<1,则dZ(FX)<1.

dKq(FX)=dZ(FX)=0.

这个性质表明,任何关于B的精确集的模糊度都等于0.除了用数值来表示粗糙集的不确定特征外,也可以用拓扑特征[22]来刻画.

(1)如果B(X)≠󰂡,B󰁫(X)≠U,称X是粗糙可

在分层递阶的近似空间中,这些性质刻画了粗糙度、模糊度随知识粒度的变化而变化的规律.本文

)随知识粒度的变化规律给出的粗糙集模糊度dZ(・

定义的;

(2)如果B(X)=󰂡,B󰁫(X)≠U,称X是内不可

更加符合人们的认知规律.

定义的;

(3)如果B(X)≠󰂡,B󰁫(X)=U,称X是外不可

定义的;

(4)如果B(X)=󰂡,B󰁫(X)=U,称X是全不可

6　结束语

粗糙集的粗糙度、粗糙熵、模糊度和模糊熵虽然都是度量粗糙集的不确定性的,但它们之间有一定的联系和区别.粗糙性从集合的边界区域的角度来刻画粗糙集的不确定性,随着知识粒度的减小,如果集合的边界区域变小,粗糙度降低,粗糙集的不确定性下降,具有很好的直观性;而粗糙集的模糊性用元素属于某个集合的隶属函数的大小来刻画粗糙集的不确定性,与集合的边界区域大小和知识粒度的大小有关.粗糙集的粗糙性具有一定的“几何”特点,而模糊性具有一定的“代数”特点,它们从直观和抽象两个方面分别刻画出粗糙集的不确定性,具有一定的互补性.本文从信息熵的角度提出了一种新的粗

),该方法用糙集的模糊性度量方法dZ(・“两个”方

定义的.

性质2.　设信息系统S=(U,A,V,f)中,BΑ

A,XΑU,如果dZ(FX)=1,则ρB(X)=1,且X关于

B是全不可定义的.

这个性质的逆不一定成立.即一个集合X关于

B是全不可定义时,它的粗糙度等于1,但是模糊度不一定等于1.

性质3.　设信息系统S=(U,A,V,f)中,B1<

)>B2ΑA,XΑU,且ρB1(X)>ρB2(X),则dZ(FdZ(FX2).

该性质说明,在一条属性链上,如果粗糙度降低,必然导致粗糙集的模糊度降低.该性质的逆不一

定成立,即如果dZ(FX1)>dZ(FX2)时,ρB1(X)>ρB2(X)不一定成立.这说明粗糙集的模糊度降低时,粗糙度未必降低.

性质4.　设信息系统S=(U,A,V,f)中,B1<ρB2ΑA,XΑU,如果dZ(FX1)=dZ(FX2),则B1(X)=ρB2(X).

随着分层递阶的近似空间中知识粒度的减小,如果粗糙集的模糊度不变,则粗糙集的粗糙度也不变.性质3和性质4表明模糊度比粗糙度对知识粒度的变化更“灵敏”.

性质5.　设信息系统S=(U,A,V,f)中,B1<

ρρB2ΑA,且G(U/B1)>G(U/B2),则B1(X)ΕB2(X),

dZ(FX1)ΕdZ(FX2).

面的信息熵来刻画粗糙集的不确定性,具有非常形象和直观的特点.这种模糊度既有信息熵度量不确定性的优势(是两部分信息熵构成),又能克服粗糙度和Liang[18]定义的粗糙熵对粗糙集不确定性度量的不足,也能弥补Chakrabarty[10]等人提出的粗糙集模糊度随着知识粒度减小反而可能增加的缺陷.在研究中,我们发现不是满足定义8的任意模糊度都会随着知识颗粒的细分而严格单调递减,因此,在构造测量粗糙集的模糊度的测量方法时,除了满足定义8外,还应该增加一个约束条件:随着知识颗粒的细分,粗糙集的模糊度单调递减.

参

[1]

考文献

随着近似空间中的知识粒度的减小,粗糙集的粗糙度、模糊度不一定严格递减.

性质6.　设信息系统S=(U,A,V,f)中,B1<

ρB2ΑA,XΑU,如果B1(X)>ρB2(X)或者dZ(FX)>

LiDe2Yi,LiuChang2Yu,DuYi,HanXu.Artificialintelli2gencewithuncertainty.JournalofSoftware,2004,15(11):158321594(inChinese)

(李德毅,刘常昱,杜鹢,韩旭.不确定性人工智能.软件学报,2004,15(11):158321594)

dZ(F),则G(U/B1)>G(U/B2).

9期

[2]

王国胤等:不同知识粒度下粗糙集的不确定性研究

[15]

1597

LiuJie,ChenXiao2Ping,CaiQing2Sheng,FanYan.Recog2nitionstructureofuncertainty:Aunifiedframeworkforrep2resentation,reasoningandlearning.JournalofSoftware,2002,13(4):92651(inChinese)

(刘洁,陈小平,蔡庆生,范焱.不确定信息的认知结构表示、

ZhaoJun,WangGuo2Yin.Researchonsystemuncertaintymeasuresbasedonroughsettheory//ProceedingsoftheRSKT2006.Chongqing,2006:2272232

[16]LiangJY,ChinKS,DangCY.Anewmethodformeasur2inguncertaintyandfuzzinessinroughsettheory.Interna2tionalJournalofGeneralSystems,2002,31(4):3312342

推理和学习.软件学报,2002,13(4):92651)

[3][4][5]

ZadehLA.Fuzzysets.InformationandControl,1965,8:3382353

PawlakZ.Roughsets.InternationalJournalofComputerandInformationScience,1982,11:3412356

ZhangBo,ZhangLing.TheoryofProblemSolvingandItsApplications.Beijing:TsinghuaUniversityPress,1990(inChinese)

(张钹,张铃.问题求解理论及应用.北京:清华大学出版社,1990)[6]

WangGuo2Yin.RoughSetTheoryandKnowledgeDiscovery.Xi′an:Xi′anJiaotongUniversityPress,2001(inChinese)(王国胤.Rough集理论与知识获取.西安:西安交通大学出

[19][18][17]

LiangJi2Ye,LiDe2Yu.UncertaintyandKnowledgeAcquisi2tioninInformationSystems.Beijing:SciencePress,2005(inChinese)

(梁吉业,李德玉.信息系统中的不确定性与知识获取.北京:

科学出版社,2005)

LiangJY,ShiZZ.Theinformationentropy,roughentropyandknowledgegranulationinroughsettheory.InternationalJournalofUncertainty,FuzzinessandKnowledge2BasedSystems,2004,12(1):37246

MiaoDuo2Qian,FanShi2Dong.Thecalculationofknowledgegranulationanditsapplication.SystemsEngineering2theory&Practice,2002,22(1):48256(inChinese)

(苗夺谦,范世栋.知识的粒度计算及其应用.系统工程理论

版社,2001)

[7]

ZhangLing,ZhangBo.TheTheoryandApplicationsofProblemSolving2QuotientSpaceBasedGranularComputing.2ndVersion.Beijing:TsinghuaUniversityPress,2007(inChinese)

(张铃,张钹.问题求解理论及应用2商空间粒度计算理论及其[20]

与实践,2002,22(1):48256)

MiaoDuo2Qian,WangJue.Aninformationrepresentationoftheconceptsandoperationsinroughsettheory.JournalofSoftware,1999,10(2):1132116(inChinese)

(苗夺谦,王珏.粗糙集理论中概念与运算的信息表示.软件

应用.第2版.北京:清华大学出版社,2007)

[8][9]

GauWL,BuehrerDJ.Vaguesets.IEEETransactionsonSystems,ManandCybernetics,1993,23(2):6102614WangGuo2Yin,ZhangQing2Hua,HuJun.Anoverviewofgranularcomputing.CAAITransactionsonIntelligentSys2tems,2007,2(6):8226(inChinese)

(王国胤,张清华,胡军.粒计算研究综述.智能系统学报,2007,2(6):8226)

[10][11][12][13]

ChakrabartyK,BiswasR,NandaS.Fuzzinessinroughsets.FuzzySetsandSystems,2000,110:2472251

BanerjeeM,PalSK.Roughnessofafuzzyset.InformationSciences,1996,93:2352246

HuynhVH,NakamoriY.Aroughnessmeasureforfuzzysets.InformationSciences,2005,73:2552275

WangGuo2Yin,YuHong,YangDa2Chun.Decisiontablereductionbasedonconditionalinformationentropy.ChineseJournalofComputers,2002,25(7):128(inChinese)(王国胤,于洪,杨大春.基于条件信息熵的决策表约简.计算

[24][23][22][21]

学报,1999,10(2):1132116)

MiaoDuo2Qian,WangGuo2Yin,LiuQingetal.GranularComputing:Past,PresentandFutureProspects.Beijing:SciencePress,2007(inChinese)

(苗夺谦,王国胤,刘清等.粒计算:过去、现在与展望.北京:

科学出版社,2007)

ZhangWen2Xiu,WuWei2Zhi,LiangJi2Ye,LiDe2Yu.The2oryandMethodsofRoughSets.Beijing:SciencePress,2001(inChinese)

(张文修,吴伟志,梁吉业,李德玉.粗糙集理论与方法.北京:

科学出版社,2001)

YangLun2Biao,GaoYi2Ying.FuzzyMathematics:TheoryandApplication.

Guangzhou:SouthChinaUniversityof

TechnologyPress,2004(inChinese)

(杨纶标,高英仪.模糊数学原理及应用.广州:华南理工大学

出版社,2004)

LiuXC.Entropy,distancemeasureandsimilaritymeasureoffuzzysetsandtheirrelations.FuzzySetsSystems,1992,52:3052318

[25][26]

ShannonCE.Amathematicaltheoryofcommunication.TheBellSystemTechnicalJournal,1948,27:3792423KlirGJ,WiermanMJ.UncertaintyBasedInformation.NewYork:Physica2Verlag,1998

机学报,2002,25(7):128)

[14]

WangGuo2Yin,ZhaoJun,AnJiu2Jing,WuYu.Acompara2tivestudyofalgebraviewpointandinformationviewpointinattributereduction.FundamentaInformaticae,2005,68(3):22301

1598计　　算　　机　　学　　报

WANGGuo2Yin,bornin1970,Ph.D.,professor,Ph.D.supervisor.HisresearchinterestsincludeRoughset,granularcomputing,dataminingandknowledgetechnologyetc.

2008年

ZHANGQing2Hua,bornin1974,Ph.D.candidate.Hismainresearchinterestsincludeintelligentinformationprocessingandgranularcomputingetc.

Background

　　Uncertaintyisanimportantpropertyofuncertainset

theories.Roughness,roughentropy,fuzziness,andfuzzyentropyaremajormethodsformeasuringtheuncertaintyofroughsets.However,wefindthattheregularitiesofthechangingofroughentropyandfuzzinessofaroughsetwiththeknowledgegranularityareinconsistentwithhumancogni2tion.

Granularcomputing(GrC)isanewmethodforsimula2tinghumanthinkingandsolvingcomplicatedproblems.Itcouldberegardedasanumbrellacoveringthetheories,methodologiesandtechniquesofgranularity.Fromtheviewofgranularcomputing,theuncertaintyofroughsetshouldvaryindifferentknowledgegranularitylevels.Wefindthereissomelimitationforroughnessandroughentropytomeas2uretheuncertaintyofaroughsetindifferentknowledge

granularitylevels.

Anewmethodformeasuringthefuzzinessofroughsetsisproposedbasedoninformationentropyinthispaper.Thefuzzinessmeasuredbythenewmethodismonotonouslyde2creasingwiththerefiningofknowledgegranularityinap2poriximationspaces.Itovercomestheproblemofroughnessandroughentropy.Inaddition,therelationsofthechangingofroughnessandfuzzinessindifferentknowledgegranulari2tiesareanalyzed.ThisworkispartiallysupportedbytheNationalNaturalScienceFoundationofChina(No160573068andNo160773113),Science&TechnologyResearchProgramoftheMunicipalEducationCommitteeofChongqingofChina(No1KJ060517)andNaturalScienceFoundationofChongqingofChina(No12008BA2017).

因篇幅问题不能全部显示，请点此查看更多更全内容

查看全文