一种基于随机决策信息系统的属性约简算法.pdfVIP

第4卷第2期 南 阳 理 工 学 院 学 报 Vo1．4No．2 2012年 3月 JOURNAL OF NANYANG INSTITUTE OF TECHNOL0GY Mar． 2012 一 种基于随机决策信息系统的属性约简算法 刘克成 ，陈小玉 (南 阳理工学院计算机与信息工程学院 河南 南 阳 473004) 摘 要 ：研究基于随机决策信息系统的属性约简算法 ，发现现有文献存在着运算量大、找到的不是约简或仅找到核 的缺陷，本文提出了一种属性约减递归算法。该算法能够计算所有约简和核 ，而且算法时间复杂度少，运算效率 高。经实例验证，该算法有很强的可行性和有效性。 关键词 ：粗糙集 ；决策表 ；属性约简；依赖度 性集 ，而不是约简 ；文献 [9—12]的属性减去法 ，只 0 前言 是求核 ，没有求出所有 的属性约简。本文提 出了一 种新算法 ，该算法能计算所有 的属性约简和核，且算 1982年 ，波兰华沙理工大学 的科学家帕拉卡 法复杂度大大减少 。 (Z．Pawlak)开创性 地提 出了粗糙集理论 (rough sets)¨。粗糙集理论是一种处理含糊性 (vague- 1 基本概念 ness)、不精确 (imprecision)和不确定性 (uncertain- ty)问题的新型软计算 (softcomputing)数学工具 ，它 定义 1(不可分辨关系) 论域 上的一簇等价 不需要任何先验知识 ，能有效地分析不精确、不一 关系5，若 PCS，且 P≠ ，则nP(P中所有等价关 致、不完整等各种不完备的信息 ，并从中发现隐含的 系的交集)仍然是 U上的一个等价关系，称为 P上 知识 ，揭示潜在 的规律 。它对人工智能和认 知 的不可分辨关系IND(P)，常记为P。而且 ， 科学非常重要 ，为机器学习、数据挖掘、知识获取 、决 V ∈u，[ (，)=[x3 = [] (1) 策支持系统、模式识别和粒度计算等领域 的信息处 定义 2(决策系统) 决策系统是一个 四元组 理提供了一种有效 的理论框架 ，在医学 、金融 、气象 、 DT=(u，GuD，， 。其 中U={。，2，…， }是论 图像处理 、语音识别等方面得到了广泛应用 。 域 ，C称为条件属性集 ，D称为决策属性集 ，属性值 粗糙集理论 的核心问题之一就是约简 ，如何在 域厂： — ， 是一信息函数 ，它指定 中的每一个 保持信息系统或知识库分类能力不变的条件下，删 对象在每个属性下的取值。 除其 中不必要 的、不重要或不相关的属性 ，是信息系 定义3(下近似和正域) 知识库 K=( ，S)， 统属性约简算法要解决的关键问题 。目前主要的属 其 中 为论域 ，S为论域 上 的等价关系簇 ，则对 性约简算法有 ：基于差别矩阵的属性约简算法、基于 VX U，U上的一个等价关系 REIND(K)，定义子 信息表示 的属性约简算法 、基于正区域 的属性约简 集 关于知识 R的下近似和正域分别为 算法和基于粒计算 的属性约简算法 。文献[6]提 显(X)={ (V ∈U)A([] )} (2) 出了计算条件属性所有子集的信任 函数和似真函数 pos=R(X) (3) 判断其值进行约简 ，缺点是计算量为 2“，很难投入 定义4(依赖度) 知识库 K=(u，S)，其中 实际应用；文献 [7]对以上缺点进行了