粗糙集理论第3章

《粗糙集理论第3章》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第三章知识的化简第3.1节引言本章讨论如何约减知识库，即如何消除知识库中的冗余知识，分为两种基本类型的约减：•知识(等价关系)的约减；•概念(等价类)的约减；第3.2节知识的简式与核■.设是一个等价关系簇。若有一等价关系；?£/?，使得=IND(Ff-{R}),则称在/?中是不必要的(dispensable),否则称7?在/?中是必要的(indispensable)。若V尺e/?都是必要的，则说是独立的(independent)，否则说是相关的(dependent)。定理3.1如果是独立的，且尸e/?，则尸也是独立的。

2、证明：用反证法。假设尸c/?且尸是相关的，则存在Sc尸使得故有IND{Su(H-P))=/M)(/?)。IND{R)=ny?=n(户u(/?-尸))=(n(/?-^))n(nF)=(n(/^F))n(nS)=n(Su(/^^))=W£>(Su(/?-F))显然又有这与/?是独立的矛盾.■定义3.2如果P，6?是独立的且/2VD(6?)=/7VD(尸)，则称6?为尸的简式。显然，戸可能有多个简式。定义3.3P中所有必要的等价关系的集合称为P的核，记为CORE(P).下面的定理给出了简式与核的关系。定理3.2尸的核(尸)=

3、戶)，其中RED(P)是尸的所有简式的簇。Note:即，对VCfe/?££>(尸)，都有C0/?£(尸)£RED{P)对于V/?，若R&CORE(P)，则從n/?££>(尸)<=>对于V/?，若R芒。/?£D(尸)，则/?茫CORE(P)//*G^H=GvH；iH^-,G=i(，H)v(-iG)=-iGvH=>*//假定存在尺使得r^RE

4、D(P).则一定存在户的某个简式C?使得r芒a即有Qgp-wgpQ是P的简式IND(Q)=IND(P)P-{R}^P^>IND(P-{R})^IND(P)=IND(Q)P-{R}^>IND(G)^IND{P-{R})所以，IND(Q)=IND(P-{R})=IND(P)所以，尺是不必要关系，即R史CORE(P).再证CORE^P^oRED(P)同理，我们只需证明对/從C0/?£(尸)，必有RenRED(P).假设收C0/?£（尸），是尸中不必要的，即IND（P）=IND（P-｛R｝），这意味着尸中存在一个的独立的等价

5、关系子集ScF-｛/?｝,使得且你5（注意此S是尸的不运含的简式）。这意味着如果存在/?芒CORE（尸），则存在一个不包含游户的简式S，这使得所有简式的交集也不包含/?，塚7/?^n/?£D（F）=n｛6?:6?e/?££＞（尸）｝成立。即对//?芒CORE（尸），贝ijnRED（尸）.故有CORE（尸/?££）（尸）｝成立。证毕■讨论：核概念有两个用途第一、它可作为求解简式的基础，因为任意简式都包含核，且核的计算是直截了当的；第二、核是最具特点的知识的集合，在知识化简过程中它不能被除去。例1设/?=｛P，2,/?｝

6、是由下述三个等价关系组成的簇:£/=｛々，x2,x3,x4,x5,x6,x7,仰｝U/P={{x},x4,x5},{x2，x8}，{x3}，{x6,Xj}}U/Q={{x^x^x5},{x6}，{x2，x4，x7，x8}}U/R={{x},X5},{x6}，{又2，又7，又8}，{x3,x4}}于是，具有等价类簇UIIND、R)={{x，x5}，{x2，x8}，{x3}，{x4},U6}，{x7}}P是不可缺少的，Vt///7VD(/?-{P})={{xbx5),x7,x8}{x3},M,M}^U/IND^.2是冗余

7、的，vt///;VD(/?-{2})={{xl,x5}9{x2，x8}，{x3}，U4}，{々)}，［x1}}=U/IND(/?)./?也是冗余的，vt///;vz)(/?-{/?})={{xbx5},{々，々}，{x3},u4}，{々)}，{x,}}=UHND{R).由P是不可缺少的，0是冗余的，尺也是冗佘的，就可知的核是八U/IND({P,2})^U/IND({P,Q}-{P})=U/IND({Q})KU/IND({P,Q}^U/IND{{P,Q}-{Q})=U/IND({P}),因止匕{尸、0是独立的，U/IND

8、({P,Q})=U/IND(Ff)所以{P,Q}是的一个简式。类似地可发现{//?}也是的一个简式。这样，簇的两个简式分别为：{P，2}和{P，/?}，{/2}n{P，尺}={P}为/?的核。第3.3节知识的相对简式和相对核在许多实际应用中，都存在决策属性，因此需要定义相对于决策属性的知识的核和简式。定义3.3设户，2是t/上