基于树形重心与割边约束的聚类算法研究

发布时间：2024-12-22 01:01

　　聚类分析是模式识别与数据挖掘等诸多领域的重要技术之一。然而,由于簇的大小、形状、分布各异,目前已有的聚类算法,包括划分式、层次式、基于密度峰值和基于最小生成树等方法都无法令人满意。大量研究发现,相比均值中心和密度中心,使用代表点作为聚类中心的方法具有较好的性能,该方法受噪声、离群点和簇的形状的影响较小。另外,最小生成树的形状并不会随簇边界的变化而变化,因此,基于最小生成树的聚类算法能解决对簇的形状和噪声敏感的问题。本文重点解决了如何在最小生成树上搜索代表点,计算类间距离,以及簇的合并准则,并构建了基于最小生成树的快速聚类算法。本文从在当前研究现状的基础上,主要进行了以下工作:(1)提出了一种基于最小生成树树形重心的类间距离度量方法。该方法的提出主要基于以下几个原因:首先,传统的基于最小生成树的聚类算法,对最小生成树的几何形状利用率不高;其次,使用欧几里德距离的度量方法对类别的形状分布敏感;最后,传统的基于代表点的类别中心选取方法的时间复杂度较高。最小生成树的树形重心作为代表点能够充分利用其几何形状,测地距离可以适应多种形状的簇。通过树链剖分技术和二分算法快速地合并簇,从而大大降低计算代表...

【文章页数】：67 页

【学位级别】：硕士

【文章目录】：
摘要
Abstract
第1章 绪论
    1.1 引言
    1.2 国内外研究现状
    1.3 本文主要工作
    1.4 论文研究及章节安排
第2章 现有聚类算法及相关理论知识
    2.1 划分式聚类算法
        2.1.1 K-means算法
        2.1.2 K-medoids算法
    2.2 基于密度的聚类算法
    2.3 层次式聚类算法
        2.3.1 CURE层次聚类算法
        2.3.2 Chameleon层次聚类算法
    2.4 最小生成树聚类算法
        2.4.1 朴素分裂式最小生成树聚类算法
        2.4.2 SAM算法
        2.4.3 其他最小生成树聚类算法
    2.5 本章小结
第3章 一种基于最小生成树树形重心的类间距离度量方法
    3.1 相似度度量方法及类别中心选取
        3.1.1 欧几里德距离及其推广
        3.1.2 其他经典相似度度量
        3.1.3 测地距离度量
        3.1.4 类别中心及代表点法
    3.2 最小生成树树形重心
    3.3 基于最小生成树树形重心的类间距离度量方法
    3.4 本章小结
第4章 一种基于限制广度优先搜索的预聚类方法
    4.1 广度优先搜索算法
    4.2 一种基于限制广度优先搜索的预聚类算法
    4.3 本章小结
第5章 一种基于割边约束条件的多阶段层次聚类方法
    5.1 阶段Ⅱ:基于割边约束的小类合并过程
    5.2 阶段Ⅲ:最终聚类
    5.3 完整算法
    5.4 整体算法时间复杂度分析
    5.5 本章小结
第6章 算法对比实验
    6.1 聚类评价指标
    6.2 实验环境介绍
    6.3 人工数据集实验结果
    6.4 UCI真实数据集实验结果
    6.5 算法运行时间对比
    6.6 本章小结
第7章 全文总结与展望
    7.1 本文工作总结
    7.2 研究展望
参考文献
攻读硕士学位期间的相关成果
致谢



本文编号：4019193