决策表的区分能力属性约简算法研究

摘要

粗糙集理论是波兰著名教授Z.Pawlak于20世纪80年代初提出的一种新型数据分析工具，对于海量数据难题，可以有效地分析处理其中不一致、不完备以及不确定的信息，简化数据系统的同时获取有效的决策。属性约简是粗糙集理论的核心内容，也是知识发现和决策研究的重要基础，其基本思想是在保持知识库的分类能力不变的前提下，约去其中冗余、错误或者不需要的知识。SKM.Wong等人已经证明获取信息表的最优约简或全部约简是NP难题，因此如何优化属性约简算法，提高计算效率，降低时空复杂度，获取更优的约简结果，一直是粗糙集的主要研究课题。　　针对现有的基于区分能力属性约简算法的时间复杂度较高的这一问题，本文提出了改进的区分能力启发式约简算法。基于决策表，引入相对知识量的概念对条件属性的区分能力进行量化，通过等价类基数递归计算相对知识量，优化计算过程，最后利用相对知识量作为启发式信息指导属性约简过程。文中提出两种基于区分能力的属性约简启发式算法，一种是以决策表的相对知识量作为结束条件，另一种是以动态约简集的相对知识量改变与否作为结束条件。　　本文首先概要阐述粗糙集理论的研究背景和研究现状以及本文的研究目的意义；其次简单说明Pawlak经典粗糙集模型的基本思想和基本概念；再次系统分析目前经典的属性约简算法，包括基于正区域、属性重要度、信息熵和差别矩阵的四种属性约简算法，并比较它们的优缺点：最后详细介绍本文提出的两种改进的基于区分能力的决策表启发式属性约简算法，主要阐述算法理论背景，介绍算法思想，说明算法原理，描述算法流程，分析算法复杂度，并将算法应用于实例，进行实现和比较。本文的主要工作有：　　(1)引入相对知识量的概念对知识的区分能力进行量化。本文利用等价类基数递归计算相对知识量，首先计算条件属性的等价类划分，再计算其中每个子类相对于决策属性的等价类分类基数，根据相对知识量的概念，计算所有子类的相对知识量，最后叠加即得该条件属性的相对知识量。　　(2)本文利用相对知识量作为启发信息，提出了两种改进属性约简算法，分别为基于区分能力的添加属性约简算法和基于区分能力的更新属性约简算法，提高了算法效率。一是以决策表的相对知识量作为结束条件；一是以约简过程中动态约简集的相对知识量改变与否作为结束条件。　　(3)针对UCI数据集，实现本文两种改进算法，并进行分析比较，说明了本文提出算法的有效性。基于区分能力的添加属性约简算法适应于约简后的条件属性数目与原始条件属性数目差距较大的情况，而更新属性算法适应于数目相差不大的情况。

目录

第一个书签之前