基于粗糙集理论的决策表属性约简与规则提取算法的研究与应用

论文摘要

粗糙集理论是波兰数学家Z.Pawlak于1982年提出的一种分析不完整、不精确、不确定数据的数据分析理论。它与其它处理不精确或不确定问题理论的最显著区别是无需提供问题所需处理的数据集合之外的任何先验信息,就可直接对数据进行分析和推理,从中发现隐含的知识,揭示潜在的规律。近年来它在模式识别、机器学习决策支持中取得了好的成果和应用。粗糙集理论作为一种较新的数据分析与处理工具,已越来越受到学术界的重视,其中有效算法的研究及应用是粗糙集理论的一个研究热点,目前主要集中在决策规则提取算法,属性约简算法,粗糙集有关的神经网络和遗传算法等。其中,属性约简算法和规则提取算法是粗糙集理论及应用的重要内容。综合评价问题是一个十分复杂的问题,它涉及评价对象集、评价目标(指标集)、评价方法集、评价人集,综合评价结果由以上诸因素特定组合所决定。常用的综合评价方法有:主成分分析方法,层次分析方法,关联矩阵分析方法,模糊综合评价方法等。这些方法在权重设置与评价矩阵的确定方面存在主观性与模糊性,制约了人们对评价对象的认识,由于粗糙集具有强大的数据分析、处理、加工能力,能对数据对象进行有效的分类,能处理定性、定量因素,有效分析不精确、不一致、不完整等各种不完备信息,因此,将其应用于综合评价中权重系数的确定,可以避免以往方法确定权重系数的局限性,同时,又可根据学习样本中评价指标与评价结果之间的关系,挖掘相应规则,从而对未来对象进行分析、预测。本文对粗糙集理论的基本概念和属性约简算法、决策规则约简算法及其在综合评价问题中的应用进行了初步系统的研究,在此基础上做了以下几个方面的工作:(1)提出了一种基于区分图的属性约简算法,该算法先将不同的决策类分开,进行比较对象时,不必每次判断是不是属于不同的决策类,算法效率较高,可适用于所有的决策表。分析了算法在最坏情况的时间复杂度为max (O(|C|2 ), O(|C||U|2 )),其中|C|表示条件属性的个数,|U|表示论域中对象的个数。给出了该算法相对Pawlak约简完备性的证明和最小属性约简算法的证明,并用实例验证算法的有效性。(2)提出一种决策表全部决策规则提取算法。该算法利用隶属度函数的定义,在不求核值表的情况下,从属性约简后的决策表中,直接获得决策表的所有决策规则。分析了得到的决策规则所对应的隶属度在决策表中的实际意义。另外,在该算法得到的所有规则中,只要将对应同一分类结果的冗余规则去掉,可以提取出各个属性约简下的决策规则。(3)针对一个具体的例子山东省各市居民消费水平综合评价问题,讨论了粗糙集在综合评价问题中的应用。最后,对本论文所研究的内容进行了总结,并对本文将来的研究方向提出了展望。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 引言
• 1.2 粗糙集的由来与发展
• 1.3 粗糙集理论的发展前景
• 1.4 决策表属性约简国内外研究现状
• 1.4.1 求决策表全部属性约简算法的研究现状
• 1.4.2 求决策表最小约简算法的研究现状
• 1.4.3 决策表快速约简算法的研究现状
• 1.5 规则提取算法的研究现状
• 1.6 论文的组织与创新
• 1.6.1 论文的组织
• 1.6.2 论文的创新点
• 第二章粗糙集理论的基础知识
• 2.1 知识、分类与知识库
• 2.2 知识表达系统和决策表
• 2.3 粗糙集的近似与粗糙集
• 2.4 知识的依赖性
• 2.5 约简
• 2.6 本章小结
• 第三章 粗糙集决策表属性约简算法
• 3.1 相关概念
• 3.2 构造区分图
• 3.3 相关性质定理
• 3.4 基于区分图中的最小属性约简算法
• 3.5 算法的完备性证明
• 3.6 算法复杂度分析
• 3.7 算法实例分析
• 3.8 本章小结
• 第四章 决策表规则提取算法
• 4.1 相关概念
• 4.2 规则提取算法
• 4.2.1 规则提取算法思想
• 4.2.2 算法实例分析
• 4.3 本章小结
• 第五章 粗糙集理论在综合评价问题中的应用
• 5.1 综合评价问题的描述
• 5.2 基于粗糙集理论的综合评价过程
• 5.2.1 评价指标值的确定
• 5.2.2 各指标权重的计算
• 5.2.3 全系统的综合评价
• 5.3 应用实例
• 5.4 本章小节
• 第六章 结束语
• 6.1 工作总结
• 6.2 进一步的工作
• 参考文献
• 研究生期间发表论文
• 致谢