三角不等式原理对聚类算法的改进

论文摘要

聚类分析是数据挖掘中的一个重要研究领域,面对大规模的、高维的数据,如何建立有效的聚类算法是一个研究热点。聚类将数据对象分组成若干个类或簇,使得在同一个簇中的对象尽可能相似,而不同簇中的对象尽可能相异,是一种无监督的分类方法。对聚类算法的进一步优化研究不仅有助于算法理论的完善,更有助于算法的推广和应用。 顺序聚类算法不需要提前确定聚类个数,并且是一种非常直接和快速的算法。但是当处理海量数据时,时间效率仍然有待提高。针对此问题,本文在两个阈值的顺序聚类算法TTSAS的基础上,提出一种新的顺序算法TITTSAS。该算法应用三角不等式原理,避免了TTSAS算法中冗余的距离计算。实验结果证明TITTSAS算法相对于TTSAS算法,在效率上有很大程度的提高,尤其对于高维的大规模数据集,效果更是显著,随着聚类个数的增加,TITTSAS算法更有优越性。并且聚类效果保持了TTSAS算法的准确性。 三角不等式原理不仅可以改进顺序算法,只要基于欧式距离度量不相似性的聚类算法,都可以通过三角不等式原理避免冗余的距离计算。k-means是一种基于划分的聚类算法,本文同样利用三角不等式原理节省了运行时间。实验结果证明,该原理对k-means算法的改进效果更是显著。

论文目录

• 第一章 绪论
• 1.1 本文选题背景及研究意义
• 1.2 聚类分析
• 1.2.1 聚类的定义
• 1.2.2 数据挖掘对聚类的要求
• 1.3 聚类分析中的数据类型
• 1.3.1 区间标度变量
• 1.3.2 二元变量
• 1.3.3 标称型、序数型和比例标度型变量
• 1.3.4 混合类型的变量
• 1.4 目前主要聚类算法及其存在问题
• 1.4.1 划分方法（partitioning methed）
• 1.4.2 层次方法（hierarchical method）
• 1.4.3 基于密度的方法（density-based method）
• 1.4.4 基于网格的方法（grid-based method）
• 1.4.5 基于模型的方法（model-based method）
• 1.5 本文的研究内容
• 第二章 用三角不等式对顺序聚类算法TTSAS的改进
• 2.1 顺序聚类算法
• 2.1.1 顺序聚类算法三种模式
• 2.1.2 对TTSAS算法改进的理由
• 2.2 三角不等式原理
• 2.2.1 公理（三角不等式原理）
• 2.2.2 定理及其证明
• 2.2.3 推论及其解析
• TTSAS算法解析:寻找最小距离'>2.3 TI_TTSAS算法解析:寻找最小距离
• TTSAS算法核心步骤'>2.3.1 TI_TTSAS算法核心步骤
• 2.3.2 核心步骤解析
• 2.4 实验结果
• 2.4.1 实验数据
• 2.4.2 实验数据分析
• 2.5 局限性与展望
• 第三章 用三角不等式原理加速k-means算法
• 3.1 划分聚类概述:
• 3.2 k-means方法
• 3.3 k-means算法的主要问题
• 3.4 用三角不等式改进的k-means算法
• 3.5 实验结果
• 第四章 全文总结与展望
• 4.1 全文总结
• 4.2 局限性与展望
• 参考文献
• 致谢