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

论文摘要

随着计算机技术和数据库技术的快速发展,在各个领域里都产生了大量的数据,海量的数据背后隐藏着许多重要信息,人们希望能够分析数据,提取出对人们有用的知识。数据挖掘应运而生,它是目前数据库和信息决策领域最前沿的研究方向之一。聚类分析作为数据挖掘的一个重要分支,其基本目的是通过分析数据间的相似性来发现目标的自然分组特性。本文探讨了基于遗传算法和粗糙集的聚类算法及其增量算法,探讨了针对分类型数据的聚类算法。本文主要研究工作如下:1.分析了现有粗糙K-means聚类算法的优缺点,根据遗传算法的遗传进化以及最大最小距离算法思想,提出了一种优化粗糙K-means的方法,该算法能动态且非随机的确定初始中心点,同时能很好地处理边界对象。实验结果表明了该算法的有效性和正确性。2.分析了现有非增量式粗糙聚类算法的优缺点,根据增量式思想及近邻思想,提出了一种增量式聚类方法。实验表明,该算法能充分利用前次挖掘结果,提高原有聚类信息的利用率及聚类效率,同时也能处理动态环境下和大的数据集。3.提出了一种有效的处理分类型数据的聚类方法,该方法将K-means算法扩展到分类型数据域,克服了传统K-means算法只限于处理数值型数据的缺点。该方法根据与每个分类属性的每个值相关的数据分布信息,同时结合数据的纵向与横向分布来评价数据对象与类之间的差异性,提出了一种新的度量。实验表明,该算法能发现同一属性的不同值间的内在关系,并能有效地度量对象间的差异性。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 研究的背景和意义
• 1.2 数据挖掘的理论和应用
• 1.2.1 数据挖掘的发展背景
• 1.2.2 数据挖掘的研究现状
• 1.2.3 粗糙集与数据挖掘
• 1.2.4 遗传算法与数据挖掘
• 1.2.5 聚类技术研究现状
• 1.2.6 聚类算法面临的挑战
• 1.3 本文的主要工作
• 1.4 本文的组织
• 第二章 聚类分析
• 2.1 聚类的形式化描述
• 2.2 聚类分析中的基本数据结构
• 2.3 聚类分析中的基本数据类型
• 2.4 相似度度量方法
• 2.4.1 距离度量
• 2.4.2 相似性度量
• 2.5 聚类分析中的主要算法及其比较
• 2.5.1 聚类算法介绍
• 2.5.2 聚类算法的比较
• 2.6 K-means 聚类算法概述
• 2.6.1 K-means 聚类简介
• 2.6.2 K-means 算法特点
• 2.7 本章小结
• 第三章 基于遗传算法和粗糙集的聚类算法
• 3.1 粗糙集基本理论
• 3.1.1 不可分辨关系
• 3.1.2 集合的上、下近似
• 3.1.3 粗糙集的基本性质
• 3.2 遗传算法基本理论
• 3.2.1 遗传算法的处理流程
• 3.2.2 遗传算法的特点
• 3.3 最大最小距离算法
• 3.4 基于遗传算法的粗糙K-means 算法设计
• 3.4.1 孤立点预处理
• 3.4.2 编码方案
• 3.4.3 适应度函数设计
• 3.4.4 遗传操作
• 3.4.5 聚类边界和聚类中心的计算
• 3.4.6 算法收敛准则
• 3.4.7 终止条件
• 3.4.8 算法描述
• 3.4.9 算法复杂度分析
• 3.5 算法仿真及结果分析
• 3.5.1 算法仿真
• 3.5.2 结果分析
• 3.6 本章小结
• 第四章 增量式聚类算法
• 4.1 问题提出
• 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 基于K-means 的动态增量聚类算法
• 4.4.1 初始聚类
• 4.4.2 动态的粗糙增量聚类算法描述
• 4.4.3 算法复杂度分析
• 4.5 算法仿真及结果分析
• 4.5.1 算法仿真
• 4.5.2 结果分析
• 4.6 本章小结
• 第五章 字符型数据聚类算法
• 5.1 问题的提出
• 5.2 字符属性知识
• 5.2.1 字符属性的值域
• 5.2.2 字符属性值的距离尺度
• 5.2.3 字符属性值的距离度量
• 5.3 基于K-means 的字符型数据聚类研究
• 5.3.1 相关定义
• 5.3.2 字符属性值之间的距离评价
• 5.3.3 对象与对象的距离
• 5.3.4 聚类中心的表示
• 5.3.5 样本与聚类中心的距离
• 5.3.6 算例分析
• 5.3.7 算法描述
• 5.3.8 算法复杂度分析
• 5.4 算法仿真及分析
• 5.4.1 算法仿真
• 5.4.2 结果分析
• 5.5 本章小结
• 第六章 结论与展望
• 6.1 结论
• 6.2 展望
• 参考文献
• 致谢
• 附录 （攻读硕士学位期间发表论文目录）
• 摘要
• ABSTRACT