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

摘要

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

目录

文摘

英文文摘

原创性声明及关于学位论文使用授权的声明

第一章绪论

第二章用三角不等式对顺序聚类算法TTSAS的改进

第三章用三角不等式原理加速k-means算法

第四章全文总结与展望

参考文献

攻读硕士学位期间发表论文情况及与参与项目开发情况

致谢