信息系统中知识约简的一种启发式算法.doc

本文由yuerlover1230贡献 pdf文档可能在WAP端浏览体验不佳。建议您优先选择TXT，或下载源文件到本机查看。 第26 卷 第2 期 2004 年4 月 压 电 与 声 光 Vol. 26 No. 2 Apr. 2004 PIEZOELECT2ICS & ACO5STOOPTICS 文章编号： 1004-2474 2004） （ 02-0158-03 不完备信息系统中知识约简的一种启发式算法 何先刚1 ， 黄 兵2 ， 温平川3 （1. 重庆邮电学院 学报编辑部， 重庆 400065； 南京理工大学 自动化系， 2. 南京 210094； 重庆邮电学院 外语学院， 3. 重庆 400065） 摘 要： 不完备信息系统中的知识获取是粗集理论应用的难点。通过引入信息熵和条件信息熵， 对信息系统 中属性的必要性进行了定义； 提出了一种基于条件信息熵的知识约简启发式算法， 并指出该算法的时间复杂度是 多项式的。通过实例说明， 该算法能得到信息表的约简和决策表的最小相对约简。 关键词： 粗糙集；信息熵；启发式算法；知识约简 TP18 文献标识码： A 中图分类号： A Heuristic Algorithm for Reduction of Knowledge under Incomplete Information Systems HE Xian-gang1 ，HUANG Bing2 ， WEN Ping-Chuan3 （1. Editorial Board of Journal of Chongqing University of Posts & Telecommunications，Chongqing 400065， China； 2. Dept. of Automation，Nanjing University of Science & Technology，Nangjing 210094， China； 3. College of Foreign Languages， Chongqing 5niversity of Psots & Telecommunications， Chongqing 400065， China） Abstract： Knowledge acquisition based on rough set theory is an important but difficult task under incomplete information systems. Information entropy and conditional information entropy are defined to express indispensable of attributes under incomplete information systems. A heuristic algorithm based on conditional information entropy for knowledge reduction is proposed，and the complexity of this algorithm is analyzed. Finally，an illustrative example analysis shows that this algorithm can find the minimal reduct for decision tables. Key words rough set；information entropy；heuristic algorithm；knowledge reduction 1 引言 粗集理论是近年来发展起来的一种处理不精 是多项式的， 并通过实例说明该算法能得到决策表 4， 的最小约简； 王国胤 5等人对粗集理论的信息论 观点进行了分析， 对知识约简在信息论观点和代数 观点进行了研究， 以条件熵为启发知识设计了决策 表的知识约简算法， 通过仿真实验验证了该算法的 有效性和约简效果。 以上研究都是以完备信息系统为研究对象的， 在现实中， 信息的不完备 对象的属性值缺损） （ 现象 是广泛存在的， 此时， 经典粗集理论的等价关系不再 6 成立， 于是人们将等价关系放宽为相容关系 （ 自 7 反性、 对称性） 相似关系 （ 自反性、 、 传递性） 甚至 ， 8 为一般二元关系 （ 一般要求满足自反性） 。因此， 确、 不完全信息的软计算方法， 其在保持信息系统分 类能力不变的前提下， 通过知识约简， 导出问题的分 类或决策规则。目前， 粗集理论被成功应用于机器 学习、 人工智能、 模式识别、 数据挖掘及过程控制等 领域。 经典粗集以完备信息系统为研究对象， 以等价 关系 自反性、 （ 对称性、 传递性） 为基础， 通过等价关 系对论域划分成互不相交的等价类， 划分越细， 知识 越丰富， 信息越充分。 知识约简是粗集理论的核心内容之一。对于一 个信息系统， 人们总是期望能找出所有约简或最小 约简。然而， 寻求所有约简或最小约简均为 NP 完 全问题。苗夺谦 1 3 基于一般二元关系的信息系统中知识约简就具有重 要的理论和实际意义。 本文在文献 9 的基础上， 通过定义一种新的 信息熵， 利用条件信息熵为启发知识设计了一般信 息表 无决策） （ 和决策表的启发式知识约简算法， 指 出该算法的时间复杂度是多项式的； 并通过实例说 等人从信息论角度， 对决策表 中属性的重要性给出度量， 提出了一种基于互信息 的知识相对约简启发式算法， 指出该算法的复杂度 收稿日期： 2003-11-06 作者简介： 何先刚 （1969-） 男， ， 四川大竹人， 工程师， 硕士生， 主要从事信号与信息处理、 计算机通信等的研究。 第2 期 何先刚等： 不完备信息系统中知识约简的一种启发式算法 159 明该算法能找到最小 相对） （ 约简。 则称 c 在 B 中是必要的。所有 B 中必要的元素称为 B 的核。 定义 3 表明， 如果从属性集 B 其余属性能完全 那么该属性是多余的 不必要的） （ 。因此， 确定属 c， 我们可以将它作为启发知识来寻求一般信息系统的 约简。 2. 4 定义 4 设 P 为定义在信息系统 S = （5， D， f） C V， 上 的一个关系族 D 是决策属性集） （ 。若 E D | B）= （ E D | B -c ， （ ） 则称属性 c:B C 是 B 相对于 D 不 必要的， 否则称属性 c : B C 是 B 相对于 D 必要 的。 定义 4 表明， 如果将属性 c 从属性子集 B 中去 掉前后对决策属性集的不确定性度量不变， 则可将 该属性约去， 在有决策的信息表中， 可以用条件信息 熵作为启发知识来寻找相对约简。基于此， 我们给 出不完备信息系统知识约简的启发式算法。 2 基本概念 基于等价关系的知识信息熵利用等价关系对论 域的划分进行定义， 如果将等价关系放宽为相容关 系或相似关系后， 相容类或相似类不再构成对论域 的划分而变成覆盖， 即各相容类或相似类之间可能 存在交叠， 在一般二元关系下也存在同样的问题。 因此， 如仍利用分块大小来衡量知识的信息量大小 就不再恰当； 在等价关系下， 将每一个对象单独看 待， 它所在的等价类看作它的邻域， 那么一个对象在 所有邻域中出现的次数即为它所在等价类元素的个 数， 它出现的次数越高， 那么它所在的等价类的对象 就越多， 该等价类所构成的块就越大， 即粒度就越 大， 分辨能力就越弱， 反之亦然。基于这种考虑， 我 们可以利用论域中任一对象在一般二元关系构成的 所有对象的邻域中出现的次数来定义知识的信息 熵。 2. 1 定义 1 设 P 是论域 U = x1 ，2 ， | U | （ x x 上的某二元关 表示在关系 P 下 系 满足自反性， （ 以下同） n P x i ） ，（ 与 x i 满足一般二元关系 P 的 U 中所有对象的全体。 ，i 2 | 由 P 的自反性知：x i : n（ x i ） = 1， ， U | 。n P P （ xi ） 称为 x i 的 P 邻域， | x i | P = |n （ x j ） x i : n P 则 | P （ x j ） 1 &j& | 5 | ， x i 在所有元 x j & j & | 5 | ） ， | 即 （1 的 邻域中出现的次数， 则关系 P 在论域 U 上的信息熵 定义为 E P）= （ | xi | P 1 |5| =log2 |5 | i =1 |5 | 3 3. 1 知识约简的启发式算法 基于条件信息熵的知识约简算法 对于无决策信息表， 无论怎样定义论域上的二 元关系， 只要满足自反性， 即可定义此二元关系的信 息熵， 通过保持信息熵不变的标准， 逐次检查各个属 性是否必要从而确定核， 再根据各非必要属性对核 的条件熵从小到大排序， 逐个加入， 直到信息熵等于 约简前的信息熵， 即得到信息系统的属性约简。 3. 1. 1 算法 1 输入一个信息系统 S = （5， V， ， 为论域， C， f） 5 C 为属性集。输出 S 的一个约简 B。 （1）计算 S 的信息熵 E C） （ ； （2）对每个 c:C， 计算 E C （ C -c ） 令 C0 （ | ）， =c | E C （ C -c ） 0 则 C0 为核； （ | ） ， （3）令 B = C0 ， 对属性集 C - B 重复， 若 （ （ 则终止； E B）= E C） 计算 E （p B） | ； 对每个 p:C - B， （p B） | 最大的属性 p 若有多个 （ 选择使 E 。 属性同时达到最大， 则任选一个） 作 B = B p ， （4）输出 B， 即为信息系统的一个约简。 下面分析 3. 1. 1 的时间复杂度。设 | U | = n， C | | = m，（1） 则 的时间复杂度为 o n2 ） 2） （ ， 的时间复 （ 杂度为 （ mn2 ） 3） o ， 的时间复杂度为 （ m2 n2 ） 故整 （ o ， 个算法的时间复杂度为 （ m2 n2 ） o 。 3. 2 基于条件信息熵的相对约简算法 对于决策表 S = U， D， f） 可以利用每个 （ C V， ， 条件属性对决策属性的条件信息熵大小来判断该条 可以证明， 等价关系下的信息熵是一般二元关 系下信息熵的特殊情形。 信息熵是度量信息量大小的量， 关系的分辨能 力越强， 信息越丰富， 信息熵就越大， 反之亦然。 P、 是论域 U 上的两个二元关系， 1 表示 Q P （ 仍为 U 上的二元关系， U 中任 对 同时满足 P 与 Q） 一元 x（1 & i & | U | ， P Q 下的邻域为： P51 x i ） 在 n （ i = n（ x i ） n（ x i ） 。相应可定义 P Q 的信息熵为 ? 1 P E P 1）= （ 2. 2 定义 2 关系 Q 相对于关系 P 的条件信息熵定义为： E | P）= E P1）- E P） （1 （ （ 2. 3 定义 3 设信息系统 S =（ U， V， ， c : B C， C， f） 对 若 E （c B -c 0， | ）= 则称 c 在 B 中是不必要的， 否 | x i | P1 1 |5| =log2 |5 | i =1 |5 | 160 压 电 与 声 光 2004 年 件属性与决策属性的影响程度： 条件属性对决策属 性的条件信息熵越大， 它对决策属性的影响也就越 小， 该属性就越可能被约简。基于此， 我们给出决策 表的相对约简算法。 3. 2. 1 算法 2 输入： 一个决策表 S = （5， D， f） 其中 C C V， ， 是条件属性集， 是决策属性集。 D 输出： 该决策表的一个相对约简。 （1）计算决策属性 D 相对于条件属性 C 的条 件熵 E D | C） （ ； （2）计算决策属性相对于每个条件属性的条件 熵 E D |a i a i :C） （ ） （ ； 按 （ ） （ 递减的顺 （3）令 B = C， E D |a i a i : C） 序对每个 a i 重复作： （ ） 计算 E D | B -a i ； （ （ ） 若成立， 则 判断 E D | C）= E D | B -a i ， c； 否则 B 不变。 下面分析 3. 2. 1 的时间复杂度： | 5 | = n， C | 设 | = m，（1） 则 的时间复杂度为 O mn2 ） 2） （ ， 的时间复 （ 杂度为 O mn2 ） 3） （ ； 的时间复杂度为 O m2 n2 ） 故 （ （ ， 整个算法的时间复杂度为 O m2 n2 ） （ 。 （ （1）E D | C）= 0. 333 3； （ ）= E ）= （2）E D | c1 1. 528 3；（ D | c2 1. 2516；（ D | c3 E ）= 0. 601 6；（ D | c4 E ）= 0. 666 7； （3） D | C -c1 0. 333 3， E （ ）= 于是： = C B c1 E D | B -c2 0. 333 3，则 B = B -c2 ； （ ）= ； E D | B -c4 E D |c3 0. 601 6 BE D | C） （ ）= （ ）= （ （4）B =c3 ，4 c 为决策表的一个相对约简。 3. 2. 1 得到的结果与文献 6 用区分函数得到 的结果一致， 并且可以验证， 所得相对约简是最小相 对约简。 通过以上实例分析可以看出， 用我们提出的基 于条件信息熵的知识约简 相对约简） （ 算法能找到 信息系统 决策表） （ 最小相对） （ 的 约简， 但该算法对 最小约简的完备性还有待于进一步讨论。 5 结束语 4 实例分析 为说明算法的有效性， 我们利用文献 6 给出 的信息表求最小约简和相对最小约简 见表 1） 其 （ ， 中 D =d 为决策属性集， 表示空值。为说明算 A 法， 假设该二元关系是文献所提出的相容关系。 表1 轿车 1 2 3 4 5 6 价格 高 低 A 高 A 低 里程 高 A A A A 高 粗集理论通过对知识约简， 导出问题的分类或 决策规则， 而知识约简大多是基于完备信息系统的。 提出了各种启发式 人们为解决求约简的 NP 问题， 算法。本文针对基于一般二元关系的信息表， 通过 引入新的信息熵为启发知识， 提出了知识约简算法， 通过实例说明该算法能找到信息表的约简和决策表 的相对最小约简。知识约简包括属性约简和值约 简， 本文仅对属性约简进行了讨论， 关于值约简以及 本文提出的约简算法求最小约简的完备性还有待于 进一步探讨。 参考文献 1 苗夺谦， 王 珏 . 粗糙集理论中知识粗糙性与信息熵 关系的讨论 J 模式识别与人工智能， . 1998， （ 3） 11 ： 34-40. 2 苗夺谦， 珏 . 粗糙集理论中概念与运算的信息表示 王 J 软件学报， . 1999，（ 2） 113-116. 10 ： 3 苗夺谦， 胡桂荣 . 知识约简的一种启发式算法 J 计 . 算机研究与发展， 1999，（ 6） 681-684. 36 ： 4 WANG G Y. Algebra view and information view of rough sets theory C Data Mining and Knowledge Discovery： . Theory，Tools，and Technology ，Proceedings of SPIE， 2001， 384： 4 200-207. 5 王国胤， 于 洪， 杨大春 . 基于条件信息熵的决策表 约简 J 计算机学报， . 2002，（ 7） 759-766. 25 ： 6 KRYSZKIEWICZ M. Ro