所以当知识Q依赖于知识P时,即知识Q由知识P导出,那么知识Q在知识库中是“多余”的。可以被删除(约简)掉[17]。
依赖性也可能是部分依赖,也就是从知识P能推导出知识Q的一部分知识,或者说知识Q只是只有一部分依赖于知识P的.此时,知识之间的依赖关系可以用依赖度来进行衡量。
定义2.17[16] 令K=(U,R),P、Q ⊆R,当k=rP(Q)=∣POSP(Q)∣∕∣U∣时,称知识Q是k(0≤k≤1)度依赖于知识P,记作P⟹kQ。
(1)如果k=1,就认为Q完全依赖于P;
(2)如果0<k<1,就认为Q部分依赖于P;
(3)如果k=0,就认为Q完全独立于P。
决策表是一类特殊而重要的知识表达系统[14]。现今,大部分决策问题都可以通过决策表形式地表达出来,因此它在工程应用中特别重要。约简后的决策表与约简前的决策表具有相同的功能,但是约简后的决策表具有更少的条件属性,即同样的决策可通过基于更少量的条件得出。
基于粗糙集理论的知识获取,主要是通过对原始决策表的约简,在保持决策表决策属性和条件属性之间的依赖关系不变的情况下对决策表进行约简,包括属性约简和属性值约简[18]。
3.2信息系统及表示
信息的表达方式在对信息的处理中占有举足轻重的位置。下面简要介绍信息系统和决策表[16]。
一个四元组S=(U,A,V,f)是一个信息系统,其中:
U:非空有限集合,集合里包含要处理的对象;
A:属性集合;
,Va是属性a的值域;
f:U*A→V是一个信息函数,它为每个对象的每个属性给定一个信息值,即∀a∈A,x∈U,f(x,a)∈Va。
定义3.1 [16]S=(U,A,V,f)是一个信息系统,A=C∪D,C∩D=ø,C称为条件属性集,D称为决策属性集。
若D=ø,则称信息系统为数据表,否则称为决策表。若存在一个x∈U,a∈C,f(x,a)未知(记作:f(x,a)=*),则称信息系统是不完备的;否则称信息系统是完备的[2]。
定义3.2[19]设S=(U,C∪D)为决策表,C与D之间的依赖度为r(C,D),属性集P⊆C是C的一个D约简,当且仅当:
(1) r(P,D)=r(C,D);
(2) ∀Pˊ∈P,r(Pˊ,D) ≠r(P,D)。
属性集C中所有D约简记为REDD(C),所有D约简的交集称为C的D核,即:CORED(C)= ∩REDD(C)
3.3属性的依赖性
处理数据的时候,如果要进行决策,那我们就需要分析数据的内在联系,讨论属性的依赖性。这里属性的依赖性和知识依赖性是相对应的。当S中存在一个一致的PQ决策算法时,我们称S中属性集Q全依赖与属性集P,并记作P⟹Q;当S中存在一个不一致的PQ决策算法时,我们称S中属性集Q部分依赖于属性集P[9]。
如前面的知识的依赖性的定义,我们也可以利用正域的概念来定义属性集之间的依赖度,如下所示[12]:
令(P,Q)为S中的一个PQ算法,算法中所有一致的PQ规则的集合称为算法的正域,记为POS(P,Q),决策算法的正域POS(P,Q)是不一致算法的一致部分,显然,当且仅当POS(P,Q)≠(P,Q)或card(POS(P,Q))≠card(P,Q)时,算法是不一致的。
对于一个PQ算法,算法的一致性程度用依赖度k表示,并定义为:
k= r(P , Q)card(POS(P,Q))/ card(P,Q)
显然,0≤k≤1。当k=1时,算法是一致的,即P、Q是完全依赖的;当k≠1时,算法时不一致的。当PQ算法有依赖度k时,我们称属性Q对P的依赖度为k,并记为P⟹kQ
3.4属性约简的算法
决策表属性约简的过程,就是从决策表系统的条件属性中去掉不必要(对得到决策不必要)的条件属性,从而分析所得约简中的条件属性对于决策属性的决策规则。但至今由于属性约简较为困难,甚至到现在为止还没有完全解决。Wong.S.K.M和Ziarko.W已经证明找出一个决策表的最小约简是一个典型的NP- Hard问题[20]。因此它至今是粗糙集理论的研究重点。 基于粗糙集理论的多源信息决策知识约简研究(7):http://www.youerw.com/guanli/lunwen_7823.html