基于连通性的聚类有效性问题研究

论文摘要

聚类分析是机器学习领域中一个非常重要的内容。聚类分析的任务是在数据中发现有意义的数据分类。聚类分析已经成功的应用在很多领域中,如工程领域、商业领域和社会科学领域等。但聚类分析中仍有很多关键问题需要研究,本文重点对聚类有效性问题进行了研究。本文对基于连通性的聚类有效性问题进行了深入的研究,在此基础上指出以往的聚类有效性指标中存在的两个问题：第一,不能很好的评价类形状任意的聚类结果；第二,现有的基于连通性的聚类有效性指标忽略了聚类结果中类内紧致性差异大对有效性指标的影响,从而可能导致错误的评价结果。针对以上两个问题,本文提出了相应的解决方法。首先利用图连通距离对形状和大小的不敏感性对任意形状聚类的类内紧致性进行度量,解决了对任意形状聚类的评价问题。其次,提出了定义聚类有效性指标的一种思路：对整个聚类结果的评价应该首先建立聚类结果中单个类的有效性,之后再对整个聚类结果进行评价。按照上述思路定义的聚类有效性指标可以克服聚类结果类内紧致性差异大对聚类结果评价造成的不利影响。将以上两点相结合,本文定义出一种基于连通性的聚类有效性指标。本文使用人工数据集和真实数据集进行了实验。实验的结果表明该聚类有效性指标是有效的。

论文目录

• 致谢
• 摘要
• ABSTRACT
• 1 引言
• 1.1 课题背景
• 1.2 研究现状
• 1.3 本文完成的工作
• 1.4 论文组织安排
• 2 聚类有效性相关理论概述
• 2.1 聚类分析的基本概念
• 2.1.1 聚类的定义
• 2.1.2 聚类分析的基本步骤
• 2.1.3 聚类算法
• 2.2 聚类结果的评价
• 2.2.1 聚类有效性问题
• 2.2.2 设计聚类有效性指标的基本原则
• 2.2.3 外部指标
• 2.2.4 内部指标
• 2.2.5 相对指标
• 3 基于连通性的聚类有效性指标
• 3.1 一种聚类有效性指标的假设
• 3.2 基于连通性的聚类有效性指标
• 3.3 新的聚类有效性指标对基本公理的满足性
• 4 实验结果分析
• 4.1 实验
• 4.2 结果分析
• 4.2.1 实验的结果分析
• 4.2.2 计算复杂度分析
• 4.2.3 适用性分析
• 5 结论及今后的工作展望
• 5.1 本文总结
• 5.2 今后的工作
• 参考文献
• 作者简历
• 学位论文数据集