基于粗糙集理论的数据挖掘算法研究

论文摘要

本论文研究课题源于国家973基础研究项目(No．2002CB312006)“Internet环境下基于Agent的软件中间件理论和方法研究”和国家自然基金项目(No．60473077)“水印关系数据库关键技术研究”。 近年来，随着我国信息化建设的快速发展，知识的自动获取已成为一种重要的技术手段。数据挖掘研究如何从大量的数据中智能地自动地抽取出有价值的知识和信息，因而成为当前人工智能研究中非常活跃的研究领域。粗糙集理论是一种有效地处理模糊性和不确定性问题的数学工具，为数据挖掘提供了新的思路和基础。本文的研究工作主要围绕基于粗糙集理论的数据挖掘，重点从基于粗糙集理论的特征选择和连续属性离散化两个方面展开。本文的主要创新性研究工作包括： 1) 提出了基于属性出现频率的属性约简算法，这种算法以条件属性在分辨矩阵中出现的频率作为启发信息，以条件属性所在最小分辨矩阵项的基数作为辅助启发信息，来寻找决策信息系统的最小约简。实验证明，大多数情况下该算法能够找到系统的最优(最小)约简。在没有找到最优约简的情况下，算法能够找到次优约简。 2) 分析属性约简中条件属性之间的关系以及约简集合中条件属性和决策属性之间的关系。在粗糙集理论的基础上给出了属性相关度的定义，并且根据这一定义，提出了基于属性相关度的属性约简算法。实验结果证明，这种算法能够有效地去除属性子集中的无关属性和冗余属性。 3) 提出了基于粗糙集理论的确定候选断点集合的新算法，该方法能够在保证系统分辨关系的前提下，大幅度的降低候选断点的数量，从而大幅度的减少了后继离散化算法的计算量。实验表明，这种确定候选断点集合的办法是切实可行的。 4) 提出了一种基于断点权重的启发式连续属性离散化方法。这种方法将连续属性的候选断点作为一个单个的条件属性，建立新的决策信息系统以考察每个候选断点对信息系统分辨能力的贡献。将断点在分辨矩阵中的出现频率作为断点的权值，寻找系统的最优断点集合。实验结果表明，此算法能在较好地保留原信息系统的分辨能力的同时，有效地解决离散化问题。 5) 提出了一种基于DBSCAN聚类的连续属性离散化算法。这种离散化算法，结合基于密度分布的聚类算法和粗糙集理论中属性依赖度的概念，通过对决策信息系统中的所有实例进行聚类来实现连续属性的离散化。实验表明，这种离散化

论文目录

• 摘要
• Abstract
• 第一章 引言
• 1.1 数据挖掘概述
• 1.1.1 数据清理
• 1.1.2 特征选择
• 1.1.3 连续属性离散化
• 1.1.4 分类算法
• 1.1.5 聚类分析
• 1.1.6 集成学习
• 1.1.7 关联规则
• 1.1.8 时间序列
• 1.1.9 文本挖掘和Web挖掘
• 1.2 粗糙集理论的发展及研究现状
• 1.3 本文的主要研究内容
• 1.4 本文的组织结构
• 第二章 粗糙集及其相关理论
• 2.1 基于粗糙集理论的知识表达系统
• 2.2 粗糙集理论的基本概念
• 2.2.1 基本概念
• 2.2.2 约简和核
• 2.2.3 不精确性测度以及属性重要性的度量
• 2.3 基于粗糙集理论的数据挖掘
• 2.3.1 特征选择和属性约简
• 2.3.2 规则获取——属性值约简
• 2.4 本章小结
• 第三章 基于粗糙集理论的特征选择
• 3.1 特征选择概述
• 3.1.1 特征选择的定义
• 3.1.2 特征选择的基本框架
• 3.1.3 搜索策略
• 3.1.4 评价机制与特征子集选择模型
• 3.2 典型的特征选择方法
• 3.2.1 Branch & Bound算法
• 3.2.2 Focus算法
• 3.2.3 浮动搜索算法
• 3.2.4 LVF算法
• 3.3 基于粗糙集理论的特征选择——属性约简
• 3.3.1 由约简定义得到的朴素属性约简算法
• 3.3.2 基于分辨矩阵和逻辑运算的属性约简算法
• 3.3.3 其它属性约简算法
• 3.4 基于属性出现频率的启发式属性约简算法
• 3.4.1 算法原理
• 3.4.2 基于属性出现频率的启发式属性约简算法
• 3.4.3 算法的实现及复杂度分析
• 3.4.4 实验结果
• 3.5 基于属性相关度的属性约简算法
• 3.5.1 属性相关度的定义
• 3.5.2 算法原理
• 3.5.3 基于属性相关度的属性约简算法
• 3.5.4 算法分析和实验结果
• 3.6 本章小结
• 第四章 基于粗糙集理论的数据离散化
• 4.1 连续属性离散化概述
• 4.1.1 离散化问题的描述
• 4.1.2 离散化方法的分类
• 4.1.3 经典的离散化方法
• 4.2 候选断点集合的确定
• 4.2.1 算法原理
• 4.2.2 候选断点集合确定算法
• 4.2.3 算法复杂度分析
• 4.2.4 实验结果及分析
• 4.3 基于断点权重的启发式属性离散化算法
• 4.3.1 算法原理
• 4.3.2 基于断点权重的连续属性离散化算法
• 4.3.3 算法分析
• 4.3.4 实验结果及分析
• 4.4 基于DBSCAN聚类的连续属性离散化算法
• 4.4.1 DBSCAN算法的相关概念
• 4.4.2 算法原理
• 4.4.3 基于DBSCAN聚类的连续属性离散化算法
• 4.4.3 算法分析和实验结果
• 4.5 本章小结
• 第五章 总结与展望
• 5.1 全文总结
• 5.2 进一步的工作展望
• 参考文献
• 攻读博士学位期间发表的论文
• 攻读博士学位期间参与的科研工作
• 致谢