搜索
大概起源概念例子知识的约简决策表的约简一、起源含糊--模糊集--粗糙集1、在1904年谓词逻辑的创始人G.Frege就提出了含糊(Vague)一词，他把它归结到边界线上，也就是说在全域上存在一些个体既不能在其某个子集上分类，也不能在该子集的补集上分类。2、1965年，Zadeh提出了模糊集，不少理论计算机科学家和逻辑学家试图通过这一理论解决G.Frege的含糊概念，但模糊集理论采用隶属度函数来处理模糊性，而基本的隶属度是凭经验或者由领域专家给出，所以具有相当的主观性。3、20世纪80年代初，波兰的Pawlak针对G.Frege的边界线区域思想提出了粗糙集（RoughSet）﹐他把那些无法确认的个体都归属于边界线区域，而这种边界线区域被定义为上近似集和下近似集之差集。由于它有确定的数学公式描述，完全由数据决定，所以更有客观性。粗糙集理论的主要优势之一是它不需要任何预备的或额外的有关数据信息。二、概念1、粗糙集(RoughSet,也称Rough集、粗集)理论是Pawlak教授于1982年提出的一种能够定量分析处理不精确、不一致、不完整信息与知识的数学工具.2、粗糙集理论最初的原型来源于比较简单的信息模型,它的基本思想：通过关系数据库分类归纳形成概念和规则,通过等价关系的分类以及分类对于目标的近似实现知识发现.3、基本粗糙集理论认为知识就是人类和其他物种所固有的分类能力。4、全域或论域(universe)：即知识必须与具体或抽象世界的特定部分相关的各种分类模式联系在一起，这种特定部分称之为所讨论的全域或论域。5、族集(family)：事实上，知识构成了某一感兴趣领域中各种分类模式的一个族集，这个族集提供了关于现实的显事实，以及能够从这些显事实中推导出隐事实的推理能力。6、一个近似空间(approximatespace)（或知识库）定义为一个关系系统（或二元组）K=(U,R)其中U不为空集，是一个被称为全域或论域(universe)的所有要讨论的个体的集合，R是U上等价关系的一个族集。7、不可区分关系：8、概念(concept)：给定近似空间K=(U,R)，子集X称为U上的一个概念(concept)，形式上，空集也视为一个概念；基本知识(basicknowledge)：非空子族集PR所产生的不分明关系IND(P)的所有等价类关系的集合即U/IND(P)相应的等价类称为基本概念初等知识(elementaryknowledge)：特别地，若关系QR，则关系Q就称为初等知识初等概念(elementaryconcept)：相应的等价类就称为初等概念9、下近似与上近似若边界区域不为空集，则集合X就是一个粗糙概念。其中，下近似包含了所有使用知识R可确切分类到X的元素，上近似则包含了所有那些可能是属于X的元素。概念的边界区域由不能肯定分类到这个概念或其补集中的所有元素组成。10、新型的隶属关系其中R是不分明关系可以看到，这里的隶属关系是根据已有的分类知识客观计算出来的，可以被解释为一种条件概率，能够从全域上的个体加以计算，而不是主观给定的。11、近似度AccuracyofApproximation其中，|X|denotesthecardinality(基数)ofX12、近似性质PropertiesofApproximationswhere-XdenotesU-X.三、例子：。。。四、知识的约简（一）一般约简1、定义1设R是等价关系的一个族集，且设R'R。若IND(R)=IND(R–R')，则称关系R'在族集R之中是可省的(dispensable)﹐否则就是不可省的。若族集R中的每个关系R都是不可省的﹐则称族集R是独立的(independent)﹐否则就是依赖的或非独立的。2、定义2若QP是独立的，并且IND(Q)=IND(P)﹐则称Q是关系族集P的一个约简(reduct)。在族集P中所有不可省的关系的集合称为P的核(core)﹐以CORE(P)来表示。显然，族集P有多个约简（约简的不唯一性）。3、定理1族集P的核等于P的所有约简的交集。即CORE(P)=∩RED(P)4、例子设有一知识库K={U,{p,q,r}}﹐其中U={x1,x2,x3,x4,x5,x6,x7,x8}﹐且U/p={{x1,x4,x5},{x2,x8},{x3},{x6,x7}}U/q={{x1,x3,x5},{x6},{x2,x4,x7,x8}}U/r={{x1,x5},{x6},{x2,x7,x8},{x3,x4}}（1）若P={p,q,r}﹐则IND(P)={{x1,x5},{x2,x8},{x3},{x4},{x6},{x7}}（2）对于U上的子集X1={x1,x4,x7}﹐可得到下近似：P*X1={x4}∪{x7}={x4,x7}上近似：P*X1={x1,x5}∪{x4}∪{x7}={x1,x4,x5,x7}（3）若P={p,q,r}﹐则IND(P)={{x1,x5},{x2,x8},{x3},{x4},{x6},{x7}}﹐IND(P-p})={{x1,x5},{x2,x7,x8},{x3},{x4},{x6}}IND(P)所以p是不可省的﹐同理可得q、r是可省的。也就说，{p,q}和{p,r}就是P的约简﹐而且{p}是P的核﹐也就是说p是绝对不能省的（二）相对约简1、定义3设P和Q是全域U上的等价关系的族集，所谓族集Q的P-正区域(P-positiveregionofQ)，记作族集Q的P-正区域是全域U的所有那些使用分类U/P所表达的知识，能够正确地分类于U/Q的等价类之中的对象的集合。2、定义4设P和Q是全域U上的等价关系的族集，RP。若，则称关系R在族集P中是Q-可省的；否则称为Q-不可省的﹔如果在族集P中的每个关系R都是Q-不可省的﹐则称P关于Q是独立的﹐否则就称为是依赖的。3、定义5SP称为P的Q-约简(Q-reduct)：当且仅当S是P的Q-独立的子族集，且；族集P中的所有Q-不可省的初等关系的集合，称为族集P的Q-核(Q-core)，记作。4、定理2族集P的Q-核等于所有P的Q-约简的交集。即其中是所有P的Q-约简的集合。5、例子设有一知识库K={U,{p,q,r}}﹐其中U={x1,x2,x3,x4,x5,x6,x7,x8}﹐且U/p={{x1,x3,x4,x5x6,x7},{x2,x8}}U/q={{x1,x3,x4,x5}{x2,x6,x7,x8}}U/r={{x1,x5,x6},{x2,x7,x8},{x3,x4}}(1)Q的P-正区域（2）可省（3）Q-约简，Q-核P的Q的核为{p,r},也是P的Q约简（三）知识的依赖性例子：（1）U/P={{x1,x5},{x2,x8},{x3},{x6},{x4},{x7}}U/Q={{x1,x5},{x2,x8,x7},{x3,x6,x4}}U/PU/Q,PQ（2）U={1,2,3,4,5,6,7,8};U/Q={X1,X2,X3,X4,X5},其中X1＝{1},X2={2,7},X3={3,6},X4={4},X5={5,8};U/P={Y1,Y2,Y3,Y4,Y5};其中Y1＝{1,5},Y2={2,8},Y3={3},Y4={4},Y5={6};Y6={7}POSp(Q)={3}U{4}U{6}U{7}={3,4,6,7}rp(Q)=card(POSP(Q))/card(U)=4/8=0.5五、决策表的约简1、决策表，定义S=(U,A)为一信息系统，且C,DA是两个属性子集，分别称为条件属性和决策属性，且CUD=A，CUD=空集，则该信息系统称为决策表，记作T=(U,A,C,D)或简称CD决策表。关系IND(C)和关系IND(D)的等价类分别称为条件类和决策类。2、两个命题命题1当且仅当CÞD，决策表T=(U,A,C,D)是一致的。由命题1，很容易通过计算条件属性和决策属性间的依赖程度来检查一致性。当依赖程度等于1时，我们说决策表是一致的，否则不一致。命题2每个决策表T=(U,A,C,D)都可以唯一分解为两个决策表T1=(U1,A,C,D)和T2=(U2,A,C,D)，这样使得表T1中CÞ1D（完全依赖）和T2中CÞ0D（完全独立）。这里U1=POSC(D)，U2=ÈBNC(X)，XÎU|IND(D)。由命题2可见，假设我们已计算出条件属性的依赖度，若表的结果不一致，即依赖度小于1，则由命题2可以将表分解成两个子表：其中一个表完全不一致，依赖度为0；另一个表则完全一致，依赖度为1。当然，只有依赖度大于0且不等于1时，这一分解才能进行。3、一致决策表的约简一致决策表的约简步骤如下：(1)对决策表进行条件属性的约简，即从决策表中消去某一列；(主要研究点)(2)消去重复的行；(3)消去每一决策规则中属性的冗余值。4、条件属性的约简A.Skowron提出了差别矩阵，使核与约简等概念的计算较为简单，主要思想：设S=(U,A)为一个知识表示系统，其中U={x1,x2,…,xn}，xi为所讨论的个体，i=1,2,…,n，A={a1,a2,…,am}，aj为个体所具有的属性，j=1,2,…,m。知识表达系统S的差别矩阵M(S)=[cij]n×n，其中矩阵项定义如下：cij={a∈A：a(xi)≠a(xj)，i,j=1,2,…,n}因此cij是个体xi与xj有区别的所有属性的集合5、差别矩阵对应的核与约简核就可以定义为差别矩阵中所有只有一个元素的矩阵项的集合，即CORE(A)={a∈A：cij=(a)，对一些i,j}相对于集合包含关系运算而言，若属性集合BÍA是满足下列条件B∩cij≠f，对于M(S)中的任一非空项cij≠f的一个最小属性子集，则称属性集合BÍA是A的一个约简。换言之，约简是这样的最小属性子集，它能够区分用整个属性集合A可区分的所有对象。6、Skowron的约简方法根据差别函数与约简的对应关系，A.Skowron提出了计算信息系统S的约简RED(S)的方法：1）计算信息系统S的差别矩阵M(S)2）计算与差别矩阵M(S)对应的差别函数fM(S)3）计算差别函数fM(S)的最小析取范式，其中每个析取分量对应一个约简7、行的约简对的行要删除，因为它们的条件属性和决策属性都相同决策表中的重复，都表示同一条决策规则。另外，决策规则的列表顺序不是本质性的8、属性值的约简对于决策表而言，属性值的约简就是决策规则的约简。决策规则的约简是利用决策逻辑消去每个决策规则的不必要条件，它不是整体上约简属性，而是针对每个决策规则，去掉表达该规则时的冗余属性值，即要计算每条决策规则的核与约简。9、求最优或次优约简所有约简的计算是NP-hard问题，因此运用启发信息来简化计算以找出最优或次优约简是必要的。现在在求最优或次优约简的算法一般都使用核作为计算约简的出发点，计算一个最好的或者用户指定的最小约简。算法将属性的重要性作为启发规则，按照属性的重要度从大到小逐个加入属性，直到该集合是一个约简为止。10、非一致决策表的约简对于一致的决策表比较容易处理，在进行约简时，只要判断去掉某个属性或某个属性值时是否会导致不一致规则的产生。而对不一致表进行约简时就不能再使用这种方法了，一般采用下面的方法：一种是考虑正域的变化，另外一种是将不一致表分成完全一致表和完全不一致表两个子表。非一致决策表的约简步骤与一致决策表的约简步骤类似。六、粗糙集的扩展模型1、基本粗糙集理论的主要存在的问题1)对原始数据本身的模糊性缺乏相应的处理能力；2)对于粗糙集的边界区域的刻画过于简单；3)粗糙集理论的方法在可用信息不完全的情况下将对象们归类于某一具体的类，通常分类是确定的，但并未提供数理统计中所常用的在一个给定错误率的条件下将尽可能多的对象进行分类的方法，而实际中常常遇到这类问题。2、可变精度粗糙集模型W.Ziarko提出了一种称之为可变精度粗糙集模型，该模型给出了错误率低于预先给定值的分类策略，定义了该精度下的正区域、边界区域和负区域。3、相似模型在数据中存在缺失的属性值的时候（在数据库中很普遍），不分明关系或等价关系无法处理这种情形。为扩展