基于粗糙集和遗传算法的聚类方法研究

论文摘要

数据挖掘技术是机器学习、数据库和统计理论相结合的产物,是从大量的、不完全的、有噪声的、模糊的、随机的实际数据中,提取隐含的、先前未知的并有潜在价值的信息的非平凡过程。在数据挖掘领域中,聚类分析是一项重要的研究课题。与分类不同,聚类的目标是在没有任何先验知识的前提下,根据数据的相似性将数据聚合成不同的簇,使得相同簇中的元素尽可能相似,不同簇中的元素差别尽可能大,因此又被称为非监督分类。聚类分析作为数据挖掘系统中的一个模块,既可以作为一个单独的工具以发现数据库中数据分布的深层信息,也可以作为其他数据挖掘分析算法的一个预处理步骤,因此研究如何提高聚类算法的性能具有重要的意义。遗传算法是基于生物进化的概念设计了一系列过程来达到优化的目的。这些过程包括:基因组合、交叉、变异、自然选择。在这些过程中,通过“优胜劣汰”的原则来淘汰掉解较差的基因,使得解朝着好的方向发展。遗传算法从一组初始可行解出发在只需要目标函数这一信息的条件下实现对可行域的全局高效搜索并以概率1收敛到全局最优解,这种良好的特性使得遗传算法成为组合优化和函数优化的有力工具,并成为计算智能领域的研究热点.粗糙集理论是一种刻画不确定性和不完整性知识的数学工具,由波兰数学家在上世纪八十年代初首先提出的。粗糙集理论善于分析隐藏在数据中的事实而不需要关于数据的任何附加知识。该理论以其独特的优势正赢得越来越多的研究者的关注,并在各个领域获得了广泛的应用。在数据挖掘领域,粗糙集最初主要用于分类,而今有关粗糙集的研究已深入到该领域的各个方面。目前所用的聚类方法大多是基于对数值属性进行处理的,并且对数值进行处理的方法比较多。而聚类算法中针对符号属性的数据处理则比较困难,往往都是使用概念聚类方法,或者将符号属性转化为数值属性的方法。但是前者过于复杂也不成熟,后者对于数据的符号属性选择有局限性。所以目前大部分的聚类算法都面向数值属性,针对符号属性的则比较少。所以本文提出的算法主要是研究符号属性的数据。粗糙集理论适合用于数据之间（精确的或近似的）依赖关系发现、评价某一分类（属性）的重要性、数据相似或差异发现。经典粗糙集模型比较好的解决了符号型数据的机器学习问题,尤其是符号数据的特征选择、属性约简和规则归纳问题。所以说粗糙集特别适合于处理符号属性的数据。在提高聚类算法的性能方面,遗传聚类算法可较好地解决聚类时的优化问题以及满足优化目标的多样性需求。适应度是遗传算法得以进行下去的关键。由于有了适应度,个体之间才存在竞争。遗传算法的目标函数及适应度函数定义具有很大的灵活性,可根据需要进行定义。遗传算法是可调节的、鲁棒的、高效率的随机搜索算法,它具有的并行性、易于和其它模型结合等性质,适用于数据挖掘,但遗传算法较复杂,容易收敛于局部极小值。粗糙集不需要给出数据之外的额外信息,可以简化输入信息的表达空间,算法简单,易于操作,粗糙集处理的对象是类似二维关系表的信息表,也适用于数据挖掘。遗传算法与粗糙集理论具有优势互补的特点,可以将两者结合应用到聚类中。本文将粗糙集思想与遗传算法结合,提出了一种新的聚类方法。聚类算法质量的一个要求就是高类内相似度、低类间相似度,所以在本文中应用类内相似度和类间相似度来定义遗传算法的适应度函数。由于粗糙集的广义近似空间提出了类内不可区分度和类间不可区分度,所以可以将此思想应用到遗传算法中的适应度函数定义中。本文提出了一种新的面向符号属性的聚类算法（RNGACA）。该算法对于每个不同的值,采用自顶向下的分裂式层次聚类策略,利用RAGA算法对数据集进行逐层二分,直到达到预先指定的聚类的个数,然后输出聚类结果。RAGA算法则是将粗糙集思想和自适应遗传算法结合,对数据进行二分。为了验证该算法,做了4部分实验,第一部分是对4组实验数据进行测试,4组数据均是取自UCI机器学习数据库,该部分以聚类准确率为衡量准则,将RAGACA算法同其他3种算法进行比较;第二部分实验测试是根据基于F-measure方法的测试结果来衡量RAGACA算法和其他两种算法;第三部分是分析RAGACA算法中RAGA算法的收敛性,通过比较RAGA算法与使用标准遗传算法和使用普通自适应遗传算法来分析它们的收敛性;第四部分是分析RAGACA算法的时间复杂度和空间复杂度。通过这四部分实验,可以分析出RAGACA对符号属性数据进行聚类的可行性,以及拥有较高的准确率和收敛性,另外时间复杂度和空间复杂度也并不比其他算法差。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 数据挖掘概述
• 1.1.1 数据挖掘概述
• 1.1.2 国内外发展现状及发展趋势
• 1.2 聚类分析概述
• 1.2.1 聚类分析的基本概念和应用
• 1.2.2 聚类分析的研究现状
• 1.3 遗传算法概述
• 1.3.1 遗传算法的基本思想
• 1.3.2 遗传算法的研究现状
• 1.4 粗糙集理论概述
• 1.4.1 粗糙集理论介绍
• 1.4.2 粗糙集的研究现状
• 1.5 粗糙集与遗传算法的结合
• 1.6 论文研究的背景和意义
• 1.7 论文的研究内容和组织结构
• 第二章 聚类分析
• 2.1 聚类分析的形式化描述
• 2.2 聚类算法的要求
• 2.3 聚类分析中的数据类型
• 2.3.1 数据矩阵
• 2.3.2 相似性矩阵
• 2.3.3 区间标度变量
• 2.3.4 相似性度量
• 2.4 聚类分析中的主要算法
• 2.5 本章小结
• 第三章 粗糙集理论
• 3.1 粗糙集理论的基本概念
• 3.1.1 知识与知识库
• 3.1.2 不精确范畴，近似与粗糙集
• 3.1.3 知识约简
• 3.1.4 知识的依赖性
• 3.1.5 知识表达系统
• 3.2 粗糙集与知识发现
• 3.3 粗糙集理论的基本算法
• 3.3.1 不可区分关系
• 3.3.2 正区域
• 3.4 本章小结
• 第四章 遗传算法基本知识
• 4.1 遗传算法的特点与结构
• 4.1.1 遗传算法的特点
• 4.1.2 遗传算法的结构
• 4.2 遗传算法的基本过程
• 4.3 遗传算法的改进
• 4.3.1 分层遗传算法
• 4.3.2 CHC 算法
• 4.3.3 messy GA
• 4.3.4 基于小生境技术的遗传算法
• 4.3.5 混合遗传算法
• 4.3.6 并行遗传算法
• 4.3.7 自适应遗传算法
• 4.4 本章小结
• 第五章 基于粗糙集和遗传算法的聚类方法
• 5.1 用于聚类分析的粗糙集广义近似空间
• 5.2 基于遗传算法的聚类
• 5.3 基于粗糙集和自适应遗传算法的聚类方法
• 5.3.1 算法思想
• 5.3.2 自适应遗传算法
• 5.4 算法流程
• 5.5 算法流程说明
• 5.6 本章小结
• 第六章 实验结果与分析
• 6.1 实验环境
• 6.2 测试数据集
• 6.3 四组数据关于遗传聚类算法的参数设置
• 6.4 算法性能测试
• 6.4.1 以聚类准确率来衡量的测试结果
• 6.4.2 基于F-measure 方法的测试结果
• 6.4.3 RAGACA 算法中遗传算法的收敛性
• 6.4.4 RAGACA 算法的时间复杂度和空间复杂度
• 6.5 本章小结
• 第七章 总结与展望
• 7.1 本文总结
• 7.2 本文展望
• 参考文献
• 读硕士期间公开发表的论文
• 致谢