k均值（K-means）聚类算法是一种经典的非监督型机器学习算法。算法简单快速。
一. 算法步骤
（1）首先确定聚类的个数K，初始化K个质心，可以随机定位，也可以和现有数据点重合
（2）对剩余的每个数据测量其到每个质心的欧式距离，并把它归到最近的质心的类
（3）重新计算已经得到的各个类的质心
（4）迭代直至新的质心与原质心相等或小于指定阈值，算法结束
（5）若迭代次数达到预先设置的最大迭代次数，算法结束
二. 算法评价
优点：
（1）算法快速、简单
（2）对大数据集有较高的效率并且是可伸缩性的
（3）时间复杂度近于线性，而且适合挖掘大规模数据集。K-Means聚类算法的时间复杂度是$O(n_t^k)$ ,其中n代表数据集中对象的数量，$t$代表着算法迭代的次数，$k$代表着簇的数目
缺点：
（1）在K-means算法中K是事先给定的，这个K值的选定是非常难以估计的
（2）K-means算法首先需要根据初始聚类中心来确定一个初始划分，然后对初始划分进行优化。这个初始聚类中心的选择对聚类结果有较大的影响，一旦初始值选择的不好，可能无法得到有效的聚类结果，这也成为 K-means算法的一个主要问题。对于该问题的解决，许多算法采用遗传算法（GA），例如文献 中采用遗传算法（GA）进行初始化，以内部聚类准则作为评价指标
（3）该算法需要不断地进行样本分类调整，不断地计算调整后的新的聚类中心，因此当数据量非常大时，算法的时间开销是非常大的。所以需要对算法的时间复杂度进行分析、改进，提高算法应用范围。在文献中从该算法的时间复杂度进行分析考虑，通过一定的相似性准则来去掉聚类中心的侯选集。而在文献中，使用的 K-means 算法是对样本数据进行聚类，无论是初始点的选择还是一次迭代完成时对数据的调整，都是建立在随机选取的样本数据的基础之上，这样可以提高算法的收敛速度。