一、简介

当涉及到聚类和分类问题时，K-Means（k均值）和KNN（K最近邻）是两种常用的机器学习算法。K-Means的目标是最小化所有数据样本到其所属簇中心的平方距离之和，即簇内误差平方和（SSE）。该算法适用于密集型数据和簇结构明显的情况，但对于不同大小、不同密度的簇效果可能不佳。KNN通常适用于小规模的数据集，而且对于特征空间的维度较高时效果可能较差。此外，KNN是一种"懒惰学习"算法，它在预测时需要存储全部的训练数据，并且计算复杂度较高。

二、面经

1、请简单介绍一下Kmeans的思想，它的优缺点分别是什么？

2、Kmeans时间、空间复杂度分别为多少？

3、Kmeans聚类如何选择初始点？

4、在你用Kmeans的时候一般是如何调优的？K值你是如何确定的？

5、Kmeans聚类，聚的是样本还是特征，特征的距离如何计算？

6、Kmeans和EM算法的关系？

7、除了Kmeans，你还知道哪些聚类算法？

8、请简单介绍啊一下KNN、以及它的优缺点？

9、KNN中的K值一般是怎么选的？

10、KNN需要数据归一化吗？

11、KNN的三要素是什么？

12、KNN中K值选择过大会有什么问题？

三、面经参考回答

1、请简单介绍一下Kmeans的思想，它的优缺点分别是什么？

参考回答：K-Means算法的基本思想很简单，事先确定常数K，常数K意味着最终的聚类类别数，首先随机选定初始点为质心，并通过计算每一个样本与质心之间的相似度(这里为欧式距离)，将样本点归到最相似的类中，接着，重新计算每个类的质心(即为类中心)，重复这样的过程，直到质心不再改变，最终就确定了每个样本所属的类别以及每个类的质心。由于每次都要计算所有的样本与每一个质心之间的相似度，故在大规模的数据集上，K-Means算法的收敛速度比较慢。一般在算上实现上，我们通过这么几种方式来设置看是否停止：1.设置最大的迭代次数。2.每一个元素的状态不在改变。3.质心的变化 < e，变化小于一个值。

优点：原理简单，容易实现；

缺点：收敛较慢， 算法时间复杂度比较高 O(nkt)，需要事先确定超参数K，对k值比较敏感，对噪声和离群点敏感，结果不一定是全局最优，只能保证局部最优。

2、Kmeans时间、空间复杂度分别为多少？

参考回答：时间复杂度：O(tKmn)，其中t为迭代次数，K 为簇的数目，m 为记录数，n为维数空间复杂度：O((m+K)n)，其中，K 为簇的数目，m 为记录数，n 为维数。

3、Kmeans聚类如何选择初始点？

参考回答：在实际应用中，由于Kmean一般作为数据预处理，或者用于辅助聚类贴标签。所以k一般不会设置很大。可以通过枚举，令k从2到一个固定值如10，在每个k值上重复运行数次kmeans(避免局部最优解)，并计算当前k的平均轮廓系数，最后选取轮廓系数最大的值对应的k作为最终的集群数目。

4、在你用Kmeans的时候一般是如何调优的？K值你是如何确定的？

参考回答：调优主要是对数据归一化和离群点的处理。因为k-means是根据欧式距离来度量数据的划分，均值和方差大的数据会对结果有致命的影响。同时，少量的噪声也会对均值产生较大的影响，导致中心偏移。所以在聚类前一定要对数据做处理。

对于K值的选择，我一般是取几个比较小的k值，然后进行交叉验证。选择合适的k值。或者用k-means++ 的方法。k-means++方法，在一开始确定簇时，让所有簇中心坐标两两距离最远。k-means++算法：K-means++算法选择初始聚类中心的的基本思想就是：初始的聚类中心之间的相互距离