一种知识分类能力的量化表示法

一种知识分类能力的量化表示法

1知识的信息熵与划分粒度表示厚存储理论由波兰科学家提出。这是处理不完整、不准确、不确定知识的新数学工具。厚存储理论认为，知识是宇宙的划分，这种分工与等价比是一致的。因此，pawlak根据等价比和集算法提出了知识的代表示。在知识的代表示中，多个元素的描述和操作的直观性较低，难以理解其本质，在这一点上，许多算法的效率也不高。在同一问题的不同知识表的算法复杂性方面，模型理论中的许多概念和操作的直观性较低，难以理解其本质，在这一点上，许多算法的效率也不高。基于此，不同知识表的算法的复杂性是不同的。在此基础上，基于此，苗建谦从一个新的角度重新审视知识。他认为，知识可以看作是由宇宙中的一组组成的干矩阵特征的随机变量。基于信息论，建议使用信息熵来表达知识并表示知识。在知识信息的表达中，知识的信息熵值越高，给人的信息量越大，分类能力越强，反之亦然。这种表示方法从更深层次上揭示了知识的本质。然而，在本文中，我们提出了一种知识表示方法，即粒度表示法。本文直接从划分出发来研究知识.我们知道,每个划分是由若干个划分块组成,而每个划分块又是论域的一个子集,本文称之为一个划分粒.对一个划分粒来说如何度量它的大小呢?自然会想到用集合基数来度量.由粗糙集理论知,一个划分它包含的划分粒越多,它的分类能力就越强(因为论域中元素个数是固定不变的).而粒度是对粒大小的一种平均度量,因此对一个划分来说,可以使用其中划分粒的平均大小来度量它的分类能力.本文将知识看成是定义在由它导出的划分粒基数上的随机变量,并定义了随机变量的概率分布.基于此概率分布定义知识的划分粒度,它是划分粒大小的概率平均,因此建立知识与划分粒度间的关系,从而可使用划分粒度来定量表示知识的分类能力,本文称之为知识的划分粒度表示.与已有的代数、信息表示法相比,划分粒度表示具有形式简单、易于计算且易于理解等特点.2p中的不可区分关系为了证明知识的代数表示与划分粒度表示是等价的,下面先简要回顾一下粗糙集理论中主要概念的代数定义.设R是集合U上的一个等价关系,U/R表示R的所有等价类构成的集合,[x]R表示x∈U的R等价类.一个知识库就是一个关系系统S=(U,A),其中,U是非空有限集,称为论域;A是定义在U上的一簇等价关系.若P⊆A,且P≠∅,则∩P(P中所有等价关系的交集)也是一个等价关系,称为U上的不可区分关系,记为IND(P).不可区分关系将论域U划分为若干个等价类,在同一等价类中的元素关于P是不可区分的,且有[x]ΙΝD(Ρ)=∩R∈Ρ[x]R={y|a(x)=a(y),∀a∈Ρ}.[x]IND(P)=∩R∈P[x]R={y|a(x)=a(y),∀a∈P}.定义1令K=(U,P)和K′=(U,Q)为两个知识库,若IND(P)=IND(Q),即U/P=U/Q,则称K和K′(P和Q)是等价的,记作K≅K′(P≅Q).定义2设U是论域,P是定义在U上的一簇等价关系,R∈P,如果IND(P)=IND(P-{R}),则称R为P中不必要的,否则称R为P中必要的.定义3设U是论域,P是定义在U上的一簇等价关系,如果每个R∈P都为P中必要的,则称P为独立的,否则称P为依赖的.定义4设U是论域,P是定义在U上的一簇等价关系,P中所有必要关系组成的集合称为P的核,记作CORE(P).定义5设U是论域,P是定义在U上的一簇等价关系,且Q⊆P,如果满足:1)Q是独立的;2)IND(Q)=IND(P);则称Q为P的一个约简.3数学期望本文认为论域U上的任一等价关系(划分)可以看成是定义在它导出的划分粒基数上的随机变量,因此可定义随机变量的概率分布及其数学期望.数学期望是随机变量的重要数字特征,它表示随机变量的平均值.在本文中,该值等于由等价关系导出的划分粒的平均长度,本文称之为划分粒度,它可以度量知识的分类能力.3.1[py1循环—划分粒度的定义下面给出随机变量(划分)的概率分布及划分粒度的定义.定义6设U是论域,P是集合U上的等价关系,记P在U上导出的划分为X,其中X={X1,X2,…,Xm},称|Xi|(i=1,2,…,m)为划分粒Xi的长度,符号|·|表示集合的基数.定义7设U是论域,P、Q是U上的两个等价关系,记P、Q在U上导出的划分分别为X、Y.其中X={X1,X2,…,Xm},Y={Y1,Y2,…,Yn},则P、Q在其导出的划分粒长度上的概率分布分别为(X;p)=[|X1||X2|⋯|Xm|p(X1)p(X2)⋯p(Xm)]p)=[|X1|p(X1)|X2|p(X2)⋯⋯|Xm|p(Xm)],(Y;p)=[|Y1||Y2|⋯|Ym|p(Y1)p(Y2)⋯p(Ym)]p)=[|Y1|p(Y1)|Y2|p(Y2)⋯⋯|Ym|p(Ym)],其中p(Xi)=|Xi||U|‚i=1,2,⋯,m;p(Yj)=|Yj||U|‚j=1,2,⋯,n.定义8设U是论域,P、Q是U上的两个等价关系,记P、Q在U上导出的划分分别为X、Y.其中X={X1,X2,…,Xm},Y={Y1,Y2,…,Yn},则P、Q的联合概率分布为(XY;p)=[|X1∩Y1|⋯|Xi∩Yj|⋯|Xm∩Yn|p(X1Y1)⋯p(XiYj)⋯p(XmYn)]‚其中p(XiYj)=|Xi∩Yj||U|,i=1,2,…,m;j=1,2,…,n.定义9设U是论域,P是U上的等价关系,记P在U上导出的划分为X.其中X={X1,X2,…,Xm},称E(Ρ)=m∑i=1|Xi|p(Xi)=m∑i=1|Xi||Xi||U|为知识P的划分粒度.注1对于信息系统而言,它的任意非空属性子集都可看成是论域上的等价关系,因此它会导出对论域的划分,所以可按定义9定义其划分粒度.而我们知道∅不是论域上的等价关系,因而也就不能导出对论域的划分,所以根据定义9,E(∅)是没定义的,为了定义的完备性和计算方便,特约定E(∅)=|U|+1.因此定义9可修正为定义9′.定义9′设U是论域,P是U上的等价关系,记P在U上导出的划分为X.其中X={X1,X2,…,Xm},称E(Ρ)={m∑i=1|Xi|p(Xi)=m∑i=1|Xi||Xi||U|,Ρ≠∅|U|+1,Ρ=∅为知识P的划分粒度.知识的划分粒度是对知识导出的划分中各划分粒“平均”(概率平均)长度的一种度量.它的值越小,表明划分粒的平均长度越短.因为论域中元素个数是固定不变的,所以划分粒就越多,表明该知识能区分开的对象就越多,因此其分类能力就越强.相反,划分粒度越大,其分类能力就越弱.因此可以用知识的划分粒度来度量其分类能力.定义10称E(Ρ∪Q)=∑i,j|Xi∩Yj|p(XiYj)=∑i,j|Xi∩Yj||Xi∩Yj||U|为知识P和Q的联合划分粒度.定义11设R是论域U上的等价关系簇,P,Q∈R是U上的等价关系,若对∀u,v∈U,有uPv⇔uQv,则称P与Q相等,记作P=Q.若对∀u,v∈U,有uPv⇒uQv,则称P比Q细,或Q比P粗,记作P≼Q.若P≼Q且P≠Q,则称P比Q严格细,或Q比P严格粗,记作P≺Q.3.2类目的性质性质1设U是论域,P是U上的一个等价关系,P在U上导出的划分为X={X1,X2,…,Xm},则1≤|U|m≤E(Ρ)≤|U|,其中m为P在U上导出的划分粒的个数.证明记|U|=n,|Xi|=ki,i=1,2,…,m,显然有m≤n,由定义9′有E(Ρ)=∑i|Xi|2|U|=∑ik2in,因为k1+k2+…+km=n,所以n2=(k1+k2+⋯+km)2=k21+k22+⋯+k2m+2∑s＜tkskt≤m(k21+k22+⋯+k2m),(1)所以∑ik2i≥n2m,所以E(Ρ)=∑ik2in≥nm=|U|m≥1,由式(1)知,当且仅当ki=kj(i,j=1,2,…,m)(即所有划分粒的长度均相等)时,E(P)取到最小值n/m.特别地,当m=n(即每个划分粒中均只有一个元素)时,E(P)取到最小值1.又因为k21+k22+…+k2m≤(k1+k2+…+km)2=n2,所以E(Ρ)=∑ik2in≤n=|U|.等号成立当且仅当存在某个ki=|U|=n,其余的kj(j≠i),j=1,2,…,m全为0.证毕.该性质表明,当知识的划分粒度越小时,它的分类能力越强;相反当知识的划分粒度越大时,它的分类能力越弱.特别当m=|U|时,即每个划分粒中只包含一个对象,此时该知识能把所有对象彻底区分开,当然它的分类能力达到最强.这与我们的理解是一致的.性质2设U是论域,P、Q是U上的两个等价关系,记P、Q在U上导出的划分分别为X、Y,其中X={X1,X2,…,Xm},Y={X1,X2,…,Xm-1,X′m,X′m+1},且Xm=X′m∪X′m+1,X′m∩X′m+1=∅,则E(Ρ)=E(Q)+2|X′m||X′m+1||U|.证明由定义9′有E(Q)=m-1∑i=1|Xi|2|U|+|X′m|2|U|+|X′m+1|2|U|,E(Ρ)=m-1∑i=1|Xi|2|U|+|Xm|2|U|.因为Xm=X′m∪X′m+1,且X′m∩X′m+1=∅,所以|Xm|=|X′m|+|X′m+1|,所以|Xm|2=(|X′m|+|X′m+1|)2=|X′m|2+|X′m+1|2+2|X′m|·|X′m+1|,所以E(Ρ)=E(Q)+2|X′m||X′m+1||U|.证毕.该性质表明,随着划分粒的个数增多,知识的划分粒度减小,相应地其分类能力增强.而且可由该性质增量式地计算知识的划分粒度.性质3设U是论域,P、Q是U上的两个等价关系,则有E(P∪Q)≤min(E(P),E(Q)).证明设P、Q在U上导出的划分分别为X、Y.其中X={X1,X2,…,Xm},Y={Y1,Y2,…,Yn},P、Q的概率分布分别为(X;p)=[|X1||X2|⋯|Xm|p(X1)p(X2)⋯p(Xm)],(Y;p)=[|Y1||Y2|⋯|Ym|p(Y1)p(Y2)⋯p(Ym)],由定义10有E(Ρ∪Q)=∑i,j|Xi∩Yj|2|U|=∑i|Xi∩Y1|2+|Xi∩Y2|2+⋯+|Xi∩Yn||U|.而E(Ρ)=∑i|Xi|2|U|,对于每一个i,因为|Xi∩Y1|+|Xi∩Y2|+…+|Xi∩Yn|=|Xi|,所以(|Xi∩Y1|+|Xi∩Y2|+…+|Xi∩Yn|)2=|Xi|2,即|Xi∩Y1|2+|Xi∩Y2|2+⋯+|Xi∩Yn|2+2∑j＜k|Xi∩Yj||Xi∩Yk|=|Xi|2.因为2∑j＜k|Xi∩Yj||Xi∩Yk|≥0,所以|Xi∩Y1|2+|Xi∩Y2|2+…+|Xi∩Yn|2≤|Xi|2,所以∑i∑j|Xi∩Yj|2≤∑i|Xi|2,所以E(P∪Q)≤E(P).且易证等号成立当且仅当对∀Xi∈X,存在唯一的Yj∈Y,使得Xi⊆Yj,即P≼Q.同理可证E(P∪Q)≤E(Q),等号成立当且仅当Q≼P.因此证明了E(P∪Q)≤min(E(P),E(Q)).证毕.该性质表明知识的分类能力是随着知识的增加而增强的.性质4设P、Q是论域U上的两个等价关系,若P≼Q则E(P)≤E(Q);若P≺Q则E(P)<E(Q).证明易由性质2、性质3得到.证毕.该性质表明,知识越细则它的划分粒度越小;相反知识越粗,它的划分粒度越大.这与人们的理解是相一致的.4各条件选取理论依据及上假设以上分析了粗糙集理论中知识与其划分粒度间的关系,可以看出利用划分粒度能定量表示知识的分类能力.就信息系统而言,下面证明知识约简的代数表示与划分粒度表示是等价的.定理1设U是论域,P、Q是U上的两个等价关系簇,若IND(P)=IND(Q),则E(P)=E(Q).证明因为IND(P)=IND(Q),所以P、Q导出的划分相同,所以在它们各自导出的划分块的基数上的概率分布相同,所以E(P)=E(Q).证毕.该定理表明两个代数表示下等价的知识具有相同的分类能力.注2该定理的逆不一定成立.定理2设U是论域,P、Q是U上的两个等价关系簇,且P⊆Q,若E(P)=E(Q),则IND(P)=IND(Q).证明记U/IND(P)={X1,X2,…,Xm},U/IND(Q-P)={Y1,Y2,…,Yn},根据定义知E(Ρ)=∑i|Xi|2|U|‚E(Q)=E(Ρ∪(Q-Ρ))=∑i,j|Xi∩Yj|2|U|=∑i∑j|Xi∩Yj|2|U|‚对每个i,因为|Xi|=∑j|Xi∩Yj|,所以|Xi|2=(∑j|Xi∩Yj|)2=∑j|Xi∩Yj|2+2∑j＜k|Xi∩Yj|⋅|Xi∩Yk|‚因为2∑j＜k|Xi∩Yj|⋅|Xi∩Yk|≥0,所以|Xi|2≥∑j|Xi∩Yj|2,所以∑i|Xi|2≥∑i∑j|Xi∩Yj|2,即E(P)≥E(Q),因此E(Ρ)=E(Q)⇔|Xi|2=∑j|Xi∩Yj|2⇔∑j＜k|Xi∩Yj|⋅|Xi∩Yk|=0⇔对每个j＜k,|Xi∩Yj|⋅|Xi∩Yk|=0.因为Yj、Yk取遍所有的划分块,而n∪j=1Yj=U‚Xi⊆U,所以不可能对每对j<k,都有|Xi∩Yj|=|Xi∩Yk|=0,因此存在j、k使得|Xi∩Yj|=0而|Xi∩Yk|≠0,对|Xi∩Yk|≠0而言,若Xi⊄Yk,则存在正整数l≠k,使得Xi∩Yl≠∅,这是不可能的.因为如果这样的话,将有|Xi∩Yl|·|Xi∩Yk|≠0,因此∑j＜k|Xi∩Yj|⋅|Xi∩Yk|≠0,这与E(P)=E(Q)矛盾,所以对每个Xi,必存在Yk,使得Xi⊂Yk.因此有IND(P)⊆IND(Q-P),所以P⇒Q-P,所以IND(P∪(Q-P))=IND(P),即IND(Q)=IND(P).证毕.该定理表明,当两个知识间存在包含关系时,可由它们的划分粒度相等得出它们在代数表示下是等价的.定理3设U是论域,P是U上的一个等价关系簇,关系R∈P在P中是不必要的(冗余的),当且仅当E(P-{R})-E(P)=0.证明必要性.设R∈P在P中是不必要的,则有IND(P-{R})=IND(P),由定理1知E(P-{R})-E(P)=0.充分性.设E(P-{R})-E(P)=0,因为P-{R}⊆P,所以由定理2知IND(P-{R})=IND(P),以R∈P在P中是不必要的.证毕.该定理表明,给属性子集中添加一个不必要的属性不会改变划分粒度的大小.推论R∈P在P中是必要的当且仅当E(P-{R})-E(P)>0.定理4设U是论域,P是U上的一个等价关系簇,P是独立的当且仅当对任意R∈P,都有E(P-{R})-E(P)>0.证明由独立性的定义和上述推论可得此结论.定理5设U是论域,P是U上的一个等价关系簇,Q⊆P是P的一个约简的充分必要条件为1)E(P)=E(Q),2)对任意的R∈Q,E(Q-{R})-E(Q)>0.证明Q⊆P是P的一个约简的充分必要条件为IND(P)=IND(Q)且Q是独立的.因