一种基于层次聚类的遗传K均值算法研究

摘要

在信息化高度发达的今天，从数据海洋中提取出知识宝藏具有深远的意义。聚类作为数据挖掘的重要方面，被广泛应用于零售业、金融业和生物科学等领域。聚类算法，更是整个聚类分析的核心。聚类算法的各方面性能，将决定整个聚类分析结果的质量，及其对现实生活的指导作用。在保持聚类算法结果稳定性和有效性的前提下，如何减轻用户负担和降低准入门槛，是一个十分有意义的研究课题。 本文对数据挖掘进行了介绍，阐述了数据挖掘中的聚类分析。目前大部分聚类算法都要求预先指定诸如聚类数目、距离阈值或密度阙值等参数，但是这些参数都是和领域知识密切相关的，即使是领域专家也很难直接给出最佳的参数值，更不必说一般的用户了。为了减轻用户的负担和降低聚类分析的准入门槛，本文在深入研究相关算法的基础上，提出了凝聚遗传K均值聚类算法（AGKA）。作为本文的创新点，AGKA算法提供了一种零输入参数、多阶段、自适应确定聚类数和效果较好的聚类算法。本文详细介绍了AGKA算法的总体架构及其流程的四个阶段，即初始化阶段、Extended Ward阶段、最近邻凝聚聚类阶段和遗传K—Means阶段，并且对其进行了细致的分析。AGKA算法有如下几个突出的优点：①AGKA算法是一种零参数聚类算法，完全不需要用户预先输入任何参数，大大地减轻了用户的负担，即使是没有深厚领域知识的普通用户也可以轻松使用此算法；②AGKA算法采用改进的Ward凝聚层次聚类算法来自动确定给定数据集的最佳聚类数目，而且还能给出不同分辨率下的最佳聚类数目，解决了目前大部分聚类算法只能得到唯一聚类数目的问题；③AGKA结合了层次聚类算法和划分聚类算法的优点，并且综合运用遗传算法的全局寻优能力和K—Means算法的局部快速优化能力来对前面层次聚类阶段的结果进行精细化和全局优化，从而使得最终的聚类结果具有更好的稳定性和有效性，进而提高AGKA算法的普适性。本文在Visual C++6.0平台上实现了AGKA算法，并且使用了7个人工数据集和3个标准数据集进行实验；从准确率、类内内聚度和类间相异度三个角度分析实验结果，将AGKA算法与其他算法作比较，从而在实践中检验AGKA算法的稳定性和有效性。

目录

文摘

英文文摘

声明

第1章 绪论

1.1本文的研究背景

1.2本文的主要研究内容

1.3本文的组织结构

第2章 数据挖掘

2.1数据挖掘的产生背景与定义

2.2数据挖掘的功能

2.3数据挖掘的步骤

2.4数据挖掘的应用

2.5本章小结

第3章 聚类

3.1聚类的基本概念

3.2聚类分析中的数据类型

3.3聚类算法的分类

3.4 Ward层次聚类方法

3.5 K-Means算法

3.6本章小结

第4章 遗传算法

4.1遗传算法的概况和基本概念

4.2遗传算法的基本流程

4.3遗传算法的应用及研究进展

4.4本章小结

第5章 凝聚遗传K均值聚类算法

5.1 AGKA的总体架构

5.2初始化

5.3改进的Ward算法—Extended wlard

5.4最近邻凝聚聚类

5.5遗传K-Means算法—GKA

5.6本章小结

第6章AGKA算法的实验分析

6.1实验方法学

6.2人工数据集上的实验

6.3标准数据集上的实验

6.4本章小结

第7章 总结与展望

7.1全文总结

7.2工作展望

参考文献

致 谢