聚类分析是指将物理或抽象对象的集合分成由类似对象组成的多个类的过程,它是研究分类问题的一种统计分析方法,同时也是数据挖掘的一种重要方法。矢量量化、图像压缩和空间数据挖掘等领域都会出现聚类问题，聚类分析有着广泛的应用前景。而Lloyd于1982年正式出版的k-means算法[1]有着广泛的应用，凭借其简单而又高效的特点，其已经成为解决聚类问题的十大算法之一[2]。本次课题，主要着眼于k-means算法的对比研究与实现。
简单来说，标准k-means算法主要分为两大步骤：将样本点分配给距离最近的聚类中心的分配步骤以及根据聚类内部样本点重新计算聚类中心的更新步骤。通过迭代地执行上述两个步骤，直到聚类中心稳定。
而标准k-means算法已被证明是NP难问题[3]，这直接造成了大规模的聚类中巨大的时间开销，因此如何优化k-means算法成为一个火热的研究方向。直至今日，k-means算法仍旧迸发着强大的生命力，不少研究者前仆后继地投身于改进k-means算法的领域里发光发热。
而k-means的优化方向大致可分为三类[4]。
一、优化初始聚类中心的选取
k-means 算法是这类优化方向里的佼佼者，Arthur 和 Vassilvitskii提出了一种称为 D2-seeding 的自适应采样方案[5], 并据此选择具有特定概率的随机起始中心，其概率与p对整体势的贡献成正比，算法时间复杂度为 O()，该方案与最优聚类相比具有竞争性。而Bachem、Lucic、Hassani 和 Krause等人通过用马尔可夫链蒙特卡罗（MCMC）抽样方法代替 D2-seeding 来构建 k-means [6]，并在后续工作中进一步消除MCMC假设[7]，从理论上保证了解的质量。
国内方面，李武等人基于平均差异度优选初始聚类中心的改进k-means聚类算法[8]，通过定义样本距离、样本平均差异度和样本集总体平均差异度，再根据平均差异度将每个样本排序,最后选择平均差异度较大且与已选聚类中心的差异度大于样本集总体平均差异度的样本作为初始聚类中心，算法明显减少了迭代次数，提高了算法收敛速度。
二、借助近似方法的加速
Fahim、Salem、Torkey 和 Ramadan 定义了一个排除标准[9]，该排除标准基于两个连续迭代中的样本点与聚类中心的距离，如果点到聚类中心的距离小于上一个迭代中的距离，则将该点排除，不再进行其与剩余聚类中心的距离计算，这使得算法速度显著提高，尤其是在大数据集上表现出众。
Tsai、Yang 和 Chiang 提出了一种高效的算法[10]：在每次迭代中，靠近聚类中心的样本点以及那些在给定迭代次数内保持在同一聚类中的样本点不太可能会被再分配到别的聚类，因此将这些点排除，同时据此计算出一个新的样本点更紧凑地代表这些被排除的样本点。
以上是毕业论文文献综述，课题毕业论文、任务书、外文翻译、程序设计、图纸设计等资料可联系客服协助查找。
