关于决策表简化的进一步研究-基础数学专业论文.docxVIP

摘要 摘要 摘 要 基于 Pawlak 粗糙集理论的决策表的简化方法是一种典型的方法 本文首 先讨论了这种方法的三个重要问题 给出了计算决策表的所有规则的所有约 简的一种算法 以此为基础从三个不同的角度即最小算法包含的约简数最 少 或其中每个约简所含合取项最少 或其中所有约简的合取项数之和最少 讨论了最小算法的优化问题 分别证明它们是 NP-hard 问题 给出了最小算 法三种优化问题的启发式算法 并对其时间复杂度进行了 分析 最后 本文 还在 Pawlak 对决策算法的概率性质研究的基础上 对最小算法的的概率性质 进行了讨论 建立了基于最小算法的粗糙推理模式 关键词 决策表 粗糙集 约简 NP-hard 问题 启发式算法 I Abstract Abstract Abstract Rough-set-based -method to simplify a decision table is of great importance. In this paper, firstly, a deep discussion on the method is made, and an algorithm for computing all reducts of every decision rule in a decision table is proposed and performed. Secondly, three optimal problems of the minimal algorithms of a decision table are investigated and their NP-hard nature is proved, and three heuristic algorithms for the three optimal problems are presented and performed. Thirdly, an investigation to probabilistic characters of the minimal algorithms is made. Key Words: decision tables, rough sets, reducts, NP-hardness, heuristic algorithms II 第 第 1 章 前言 PAGE PAGE 1 第 1 章 前言 1.1 课题研究的背景 决策表是一种特殊的信息系统 是没有经过加工的 原始的数据库 它 包含着很多冗余数据 是 丰富的信息与贫乏的知识 的典型表现 人们希 望从中识别出有效的 潜在有用的 可理解的模式 并创立了很多数据挖掘 的方法[1] 基于粗糙集的方法是其中比较成功的方法 粗糙集理论是由波兰数学家 Pawlak 于 20 世纪 80 年代提出的 可用于数 据挖掘的数学理论[2] 其主要优势是它不需要任何预备的或额外的有关数据信 息 比如统计学中的概率分布 Dempster-Shafer 理论中的基本概率赋值 或 者模糊集理论中的隶属度等 基于粗糙集理论的对决策表的数据挖掘在于对决策表的简化 即先对属 性进行约简 再对规则进行值约简 删去多余的规则 最后得到所谓最小算 法 但是 最小算法按其定义来说是不唯一的 比如得到了 n 个最小算法 这些最小算法是否包含了所有可能的结果 能否通过某种方法得出一个不含 在这 n 个中的结果 对于决策表 是否存在这样的最小算法 它包含的规则的约简最少且每 个约简所含的原子公式最少 如果这样的最小算法不存在 怎样修改它 使 得符合新标准的最小算法存在 如何求出这些最小算法 Pawlak 指出决策算法具有某些熟知的概率性质 特别是决策算法满足全 概率公式和贝叶斯定理[3] 这些性质为从数据中抽取结论的新方法提供了依 据 这种新方法不象经典的贝叶斯推理那样需要用到先验概率和后验概率 那么 在决策表被简化为最小算法后 这些性质是否还成立 河北大学理学硕士学位论文 河北大学理学硕士学位论文 1.2 本课题的工作 结果和意义 本课题在以下几方面展开工作并取得了一些结果 1 讨论了 Pawlak 简化方法的不完备性 澄清了 Pawlak 约简过程中的 两个问题 2 设计了一个算法 实现了 Pawlak 技术求决策表所有规则的所有约 简的方法 3 探索了决策表最小算法的三类优化问题 证明了它们是 NP-hard 问题 利用启发式信息提出了它们的启发式算法 并予以实现 4 证明了最小算法的概率性质 由于 Pawlak 约简技术是以粗糙集理论为基础的 所以它的不完备性折射 出基本粗糙集理论