Kmeans面试常见问题汇总

**Kmeans面试常见问题汇总

1.K-means的伪代码：

2.K-means中常用的到中心距离的度量有哪些？

3.K-means聚类中每个类别中心的初始点如何选择？

1）随机法 最简单的确定初始类簇中心点的方法是随机选择K个点作为初始的类簇中心点。 2）选择各批次距离尽可能远的k个点，首先随机选择一个点作为第一个初始类簇中心点，然后选择距离该点最远的那个点作为第二个初始类簇中心点，然后再选择距离前两个点的最近距离最大的点作为第三个初始类簇的中心点，以此类推，直到选出k个初始类簇中心。 3）层次聚类或者Canopy预处理，选择中心点。选用层次聚类或者Canopy算法进行初始聚类，然后利用这些类簇的中心点作为Kmeans算法初始类簇中心点。

4.K-means中空聚类的处理

（1）选择一个距离当前任何质心最远的点。这将消除当前对总平方误差影响最大的点。 （2）从具有最大SSE的簇中选择一个替补的质心，这将分裂簇并降低聚类的总SSE。如果有多个空簇，则该过程重复多次。 （3）如果噪点或者孤立点过多，考虑更换算法，如密度聚类（博客后期会更新这类聚类算法）

5.K-means是否会一直陷入选择质心的循环停不下来？

不会，有数学证明Kmeans一定会收敛，大概思路是利用SSE的概念（也就是误差平方和），即每个点到自身所归属质心的距离的平方和，这个平方和是一个凸函数，通过迭代一定可以到达它的局部最优解。（不一定是全局最优解）

6.如何快速收敛数据量超大的K-means？

K-means算法是常用的聚类算法，但其算法本身存在一定的问题。例如，在大数据量下的计算时间过长就是一个重要问题。

Mini Batch Kmeans使用了一种叫做Mini Batch（分批处理）的方法对数据点之间的距离进行计算。Mini Batch的好处是计算过程中不必使用所有的数据样本，而是从不同类别的样本中抽取一部分样本来代表各自类型进行计算。由于计算样本数量少，所以会相应的减少运行时间，但另一方面抽样页必然会带来准确度的下降。

该算法的迭代步骤有两步： 1）从数据集中随机抽取一些数据形成小批量，把他们分配给最近的质心 2）更新质心：与k均值算法相比，数据的更新是在每一个小的样本集上。对于每一个小批量，通过计算平均值得到更新质心，并把小批量里的数据分配给该质心，随着迭代次数的增加，这些质心的变化是逐渐减小的，直到质心稳定或者达到指定的迭代次数，停止计算。

7.K-means算法的优点和缺点是什么？

K-Means的主要优点： （1）原理简单，容易实现 （2）可解释度较强

K-Means的主要缺点： （1）K值很难确定 （2）局部最优 （3）对噪音和异常点敏感 （4）需样本存在均值（限定数据种类） （5）聚类效果依赖于聚类中心的初始化 （6）对于非凸数据集或类别规模差异太大的数据效果不好

8.如何对K-means聚类效果进行评估？

轮廓系数 好的聚类：内密外疏，同一个聚类内部的样本要足够密集，不同聚类之间样本要足够疏远。

轮廓系数计算规则：针对样本空间中的一个特定样本，计算它与所在聚类其它样本的平均距离a，以及该样本与距离最近的另一个聚类中所有样本的平均距离b，该样本的轮廓系数为，将整个样本空间中所有样本的轮廓系数取算数平均值，作为聚类划分的性能指标s。

轮廓系数的区间为：[-1, 1]。 -1代表分类效果差，1代表分类效果好。0代表聚类重叠，没有很好的划分聚类。比较低,内密外不够疏

9.K-Means与KNN有什么区别

1）KNN是分类算法，K-means是聚类算法； 2）KNN是监督学习，K-means是非监督学习 3）KNN喂给它的数据集是带Label的数据，已经是完全正确的数据，K-means喂给它的数据集是无label的数据，是杂乱无章的，经过聚类后才变得有点顺序，先无序，后有序。 4）KNN没有明显的前期训练过程，K-means有明显的前期训练过程 5）K的含义KNN来了一个样本x,要给它分类，即求出它的y,就从数据集中，在X附近找距离它最近的K个数据点，这K个数据点，类别C占的个数最多，就把x的label设为c. K-means中K是人工固定好的数字，假设数据集合可以分为k个簇，由于是依靠人工定好，需要一些先验知识。

10.k-means算法的调优一般可以从以下几个角度（具体描述详见百面机器学习）：

(1)数据归一化和离散点的处理（2）合理选择K值 （3）采用核方法

11.针对K-means算法的缺点， 有哪些改进的模型（详细描述在百面机器学习）：

（1）K-means++ （2）ISODATA算法

（

12. K-means算法和EM算法的关系：

k-means算法与EM算法的关系是这样的：k-means是两个步骤交替进行，可以分别看成E步和M步； M步中将每类的中心更新为分给该类各点的均值，可以认为是在「各类分布均为单位方差的高斯分布」的假设下，最大化似然值； E步中将每个点分给中心距它最近的类（硬分配），可以看成是EM算法中E步（软分配）的近似。

13.用数学方法证明K-means是EM算法的特例？

参考知乎lixinliu回答 https://www.zhihu.com/question/49972233?sort=created

14. Kmeans中K的选取

参考博文：https://blog.csdn.net/qq_15738501/article/details/7903625

仅学习自用， 侵权删 参考资源： https://blog.csdn.net/qq_38147421/article/details/106472422 https://blog.csdn.net/qq_15738501/article/details/79036255 https://blog.csdn.net/qq_38147421/article/details/106472422?utm_medium=distribute.pc_relevant.none-task-blog-baidujs-3 https://zhuanlan.zhihu.com/p/58434325 https://www.zhihu.com/question/49972233?sort=created https://blog.csdn.net/qq_15738501/article/details/7903625