《基于幕图的属性约简搜索式算法》由会员分享，可在线阅读，更多相关《基于幕图的属性约简搜索式算法（16页珍藏版）》请在金锄头文库上搜索。
1、基于幕图的属性约简搜索式算法*陈玉明吧苗夺谦听)。(同济人学计算机科学与技术系上海201804)刁(嵌入式系统与服务计算教育部重点实验室上海201804)摘要：粗糙集理论是一种新的处理不精确、不完全与不一致数据的数学工具。属性约简是粗 糙集理论的重要研究内容之一，己有的属性约简算法主要是基于代数表示与信息表示的方法。 同一问题在不同的知识表示下，其求解难度是不同的。本文从改变屈性约简问题的知识表示入 手，提出了该问题的一种新的表示方式幕图；给出了基于幕图的屈性约简搜索式算法，把 属性约简计算问题转化为在幕图中的搜索问题。理论分析表明新算法是有效的，为属性约简研 究提供了一条新的途径。关键词：粗
2、糙集；屈性约简；幕图；粒计算；知识表示1引言波兰科学家Pawlak乙1982年提出的粗糙集(Rough Sets)是-种新的处理不精确、不完全与 不一致数据的数学理论工。近年來该理论在机器学习、数据挖掘及模式识别等多个领域得到了 广泛的应用X。在基于粗糙集理论的知识获取研究中，属性约简是其中最核心的组成部分之一, 许多学者已对属性约简算法进行了大景的研究*川。现有的属性约简研究主耍是基于代数表示 与信息表示的方法。在代数表示下，人体上可分为基于正区域的属性约简算法、基于差别 矩阵及在此基础上改进的属性约简算法等。在信息表示下,主要有基于信息爛的属性约简算 法化基于互信息的决策表约简算法代和基于
3、条件信息爛的决策表约简算法“等。但这些算法 都不是基于图搜索式的算法。知识表示方式研究是人工智能研究的中心内容之一。对于传统人工智能问题，任何比较复 杂的求解技术都离不开两方面的内容表示与搜索。知识表示方法很多，有图示法、公式法、基金项目:国家自然科学基金(No.60475019, No.60775036),博士学科点专项科研基金(No.20060247039) 作者简介:陈玉明，男，1977年生，江西吉安人，博士生，讲师，主要研究方向为粗糙集理论与模式识别E-mail: cym0620苗夺谦，男，1964年生，山西普中人，教授，博士生导师，主要硏究方向为粗糙集理论、粒计 算、Web智能与模式
4、识别等。作者联系电话:陈玉明,13818540180。结构化方法、陈述式表示和过程式表示等切。徳国数学家Wille R.于1982年首先提岀形式概念 分析(formal concept analysis)用于概念的发现，排序和显示叭 形式概念分析是一种知识表示 方式，国内外学者进行了人量的研究，把形式概念分析应用于属性约简Z中w役 但形式概念 分析理论使知识表示复杂化，不利于问题的求解。因此，有必要研究更简单直观的知识表示方 式。图是一种直观形象的知识表示方式，在此基础上有宽度优先搜索、深度优先搜索和启发式 搜索等算法。图搜索的优势在于带有冋溯机制，保存了搜索路径,因而可以根据L1付出的代价,
5、 搜索下一-步的最佳路径。属性约简研究包拈信息系统的属性约简和决策表的属性约简，本文主 要研究信息系统的属性约简。根据属性的子集之间的包含关系，本文提出一种新的知识表示方 式幕图。把该知识表示方式应用于属性约简之中，给出两种基于幕图的屈性约简搜索武算 法，把属性约简计算问题转化为在幕图中的搜索问题。理论分析表明，本文提出的算法是有效 的。2基本概念及幕图定义厂 称IS=(U,A,VJ)为信息系统，其中(/是非空有限集，称为论域，4是有限 属性集，V = JV(l ,匕表示属性。的值域，/:(/xA-V是一个信息函数，即对 aeAVx w w A ,有/(x,d) e K。任一属性子集BA决定了
6、一个二元不可区分关系IND:IND = (x9y) eUxU/ae BJ(x.a) = f(y,a)。 U / IND(B)构成了 U 的一个划分,称其为t/上的一个知识，其中每个等价类称为一个知识粒。为方便计，有时将U/IND(B)简记为U IB.特别地，如果U/B = co = xIixIi=x,xeU,称其为恒等关系；如果U/B = 3 = xB xB =U,xeU,称其为全域关系。由于等价关系、属性、知识、划分等概念之间是等价的，因此在以下的论述中，将不再对其进行区分。定义2“ 设IS = (U,AyV,f)为信息系统,/A = Xi,X2,X“d，则A的知识粒度定义为gd(a)=工1
7、=1I X I2IFFu GD(B) GD(C).证明参见文献。定义 3 设 /S = (,A,UJ)是一个信息系统，如果 IND(A-a) = IND(A)f则称g是A中不必要的(多余的)属性；否则，称d是4中必要的属性。定义4设=是一个信息系统，属性集A中所有必要的属性组成的集合，称为属性集A的核，记作Core(A)。定义5设/S = (/,AV,/)是一个信息系统，BA是一个属性子集，如果满足1) IND= INDg2) 対PbwB,有IND(B b、)HlND(B)；则称B是4的一个约简。命题2 设=是一个信息系统，是两个属性子集，若IND=/7VD(C),则 GD(B) = GD(C
8、)。证明 令/B = Xi,X2,Xn, C7/C = h,Y2,已知IND=IND ,所 以uib = uic ,即Xi,X2,x,” = h,y2,.,x；由知识粒 度定义 可知，n I y I2GD(B) = 7， GD(C) = Y侖，而Xi,X2,.,X/ = h,*,X,所 匸I U Iy=i I u GD(B) = GD(C)注：该命题的逆未必成立。命题3设Z5 = (t/,A,VJ)是一个信息系统，是两个属性子集，且ByC ,GD(B) = GD(C),则 IND= IND(C)证明 反证法。假设IND(B) = IND(C )不成立，即IND(BIND(C)；由BqC ,IN
9、D(B) o IND(C), 因 为 IND(B) IND(C), 所 以 IND二IND(C)；U /B = X,X2,XN , t/C = h,Y2,X, 由 IND(B) =)IND(C),M I X I2 n I y I2Xi,X2,X,”nYi,Y2,X,所以 工 工丄，由知识粒度定义可知， m lt/1気 11m I V I2“ I y I2GD(B) =工GD(C) =工士，所以GD(B)GD(C)，这和l2GD(B) = GD(C)/=i IU I；=i IU h相矛盾。故命题得证。命题4设7S = (/,A,VJ)是一个信息系统，Vf/eA在A中是不必耍的侈余的)屈性,其充分
10、必要条件是GD(A-a) = GD(A)。证明(必要性)设VawA在A中是不必要的属性，由定义3IND(A-a) = IND(A) 成立；由命题2可知，GD(A-a) = GD(A).(充分性)设 Fa，由 GD(A-a) = GD(A)和命题 3 可知，IND(A-a) = IND(A)成立，故X/aeA在4中是不必要的属性。推论1 VtzeA在A中是必要的属性，即IND(A UIND(A),其充分必要条件是GD(A-a)GD(A)o推论 2 Vae A，且 GD(A-a)GD(A),则 Core(A) = ua o命题5设7S=(C/M,VJ)是一个信息系统，BA是A的一个约简的充分必耍条
11、件为1) GD(B) = GD(A)。2) 对 V/? e B ,有GD(B-b)GD(B)0证明 由定义5、命题2、命题3及推论1可以证明。证明略。定义6设Power(A)为属性集合A的幕集，给定有向图G , G的顶点为Power(A)的元 索，G 的边满足条件：VB,C,DePvver(A),若 Card(B) -1 = CardC) = Card(D) +1 且 (BcD)uCu(BuD),则存在D到C, C到B的有向边，称此有向图6为A的幕图。设属性集合A有加个元素，则其幕集有2个元索，根据幕图定义易知A的幕图有个顶 点，对于任意顶点V e Power(A),根据Card(V)的人小可
12、将幕图分成加+ 1层，设分别为 厶，厶，,厶”，具有相同Card(V)为同一层，Card(V) = fn的顶点组成第厶层， Card(V) = m-的顶点组成第厶层，,Card(V) = 0的顶点纽成第厶“层。例1 属性集A = a,b,c,其幕图为图1所示。图1幕图定义7设G为属性集A的幕图，对G的顶点结点进行扩充，使顶点结点保存两个量，一 个是顶点V e Power(A),另一个是其知识粒度GD(V),称此扩充的幕图为知识粒度幕图。推论3幕图中结点子集的知识粒度具有反单调性。证明： 由命题1与知识粒度幕图的定义可以推论出來。证明略。命题6设/S = (/,AV,/)是一个信息系统，G为其知
13、识粒度幕图，KmeG为G中 层某结点，且GD(KJ = GD(A),如果心的所有邻接卜层厶冲层结点的知识粒度都大于 GD(KJ ,则Kni为该信息系统的约简。证明： 反证法。假设心不是约简，由GD(KJ = GD(A)和命题3,可知IND(KJ = IND(A),所以约简必在心的真子集中；因为心的所有邻接下层厶加层结点的 知识粒度都人于GD(KJ,根据K”,子集知识粒度的反单调性，知K,”真子集的知识粒度都人 于GD(KJ ,因为GD(KJ = GD(A),所以心 真子集的知识粒度都人于GD(A),即， Vk g Kni真子集,有GD伙)GD(A),由推论1,可知/ND伙、工IND(A),所以
14、约简必 不在的真子集中，这与前面推出约简必在的真子集中相矛盾。命题得证。命题1说明对于4的属性子集，随着属性的减少，知识粒度增人，越来越粗；反之，随着 属性的增多，知识粒度减小，越來越细。幕图反映属性的增加与减少关系，知识粒度反映属性 子集的划分即知识的粗细程度，知识粒度幕图则把两者结合起來，既反映属性子集划分的粗细 程度，乂体现其空间拓扑结构。命题6给出了幕图中约简的判定。所以，可以把属性约简问题 转化为在知识粒度幕图中的搜索问题。3基于幕图的属性约简搜索式算法知识表示方法是问题求解所必需的。表示问题是为了进一步解决问题。从问题表示到问题 的解决，有一个求解过程，也就是搜索过程。在这一过程中，采用适当的搜索技术，包括各种 规则，过程和算法等推理技术，力求找到问题的解答。图搜索技术是一种在图中寻找路径的方 法，从初始结点出发到目标结点寻求满足一定要求的路径，可以是最佳路径，也可以是用八要 求的最佳路径。求解数据约简问题实质上是个搜索问题。幕图是一种图的知识表示方式，采用 这种表示方式，可以非常方便地给出求解数据约简问题的图搜索式算法。属性约简可以从两个 方向进行搜索，一个是77?” -down搜索，另一个是Bottom-up搜索。77?”-勿呵 方式搜索 是从幕图的顶层出发，往下搜索，知识粒度由细到粗
