| k | 您所在的位置：网站首页 › 常见的算法面试题 › k |
k
|
总述
关于K-means在面试中常见的问题先汇总一下，下面分别详细说明。 1、简述一下K-means算法的原理和工作流程 2、K-means中常用的到中心距离的度量有哪些？ 3、K-means中的k值如何选取? 4、K-means算法中初始点的选择对最终结果有影响吗？ 5、K-means聚类中每个类别中心的初始点如何选择？ 6、K-means中空聚类的处理 7、K-means是否会一直陷入选择质心的循环停不下来？ 8、如何快速收敛数据量超大的K-means？ 9、K-means算法的优点和缺点是什么？ 10、如何对K-means聚类效果进行评估？ 一、原理和工作流程见上一篇博客https://blog.csdn.net/qq_38147421/article/details/106467069 流程： 1、首先随机选取样本中的K个点作为聚类中心； 2、分别算出样本中其他样本距离这K个聚类中心的距离，并把这些样本分别作为自己最近的那个聚类中心的类别； 3、对上述分类完的样本再进行每个类别求平均，求解出新的聚类中心； 4、与前一次计算得到的K个聚类中心比较，如果聚类中心发生变化，转过程b，否则转过程e； 5、当质心不发生变化时，停止并输出聚类结果。 二、K-means中常用的到中心距离的度量有哪些？曼哈顿距离和欧氏距离。 详细见博客转自https://blog.csdn.net/qq_15738501/article/details/79036255 主流的确定聚类数k的方法有以下两类。 1、手肘法 1.1 理论 手肘法的核心指标是SSE(sum of the squared errors，误差平方和)， 1.2 实践 我们对预处理后数据.csv 中的数据利用手肘法选取最佳聚类数k。具体做法是让k从1开始取值直到取到你认为合适的上限(一般来说这个上限不会太大，这里我们选取上限为8)，对每一个k值进行聚类并且记下对于的SSE，然后画出k和SSE的关系图（毫无疑问是手肘形），最后选取肘部对应的k作为我们的最佳聚类数。python实现如下： import pandas as pd from sklearn.cluster import KMeans import matplotlib.pyplot as plt df_features = pd.read_csv(r'C:\预处理后数据.csv',encoding='gbk') # 读入数据 '利用SSE选择k' SSE = [] # 存放每次结果的误差平方和 for k in range(1,9): estimator = KMeans(n_clusters=k) # 构造聚类器 estimator.fit(df_features[['R','F','M']]) SSE.append(estimator.inertia_) X = range(1,9) plt.xlabel('k') plt.ylabel('SSE') plt.plot(X,SSE,'o-') plt.show()画出的k与SSE的关系图如下： 2. 轮廓系数法 2.1 理论 该方法的核心指标是轮廓系数（Silhouette Coefficient），某个样本点Xi的轮廓系数定义如下： 附上百度百科的图片： 2.2 实践 我们同样使用2.1中的数据集，同样考虑k等于1到8的情况，对于每个k值进行聚类并且求出相应的轮廓系数，然后做出k和轮廓系数的关系图，选取轮廓系数取值最大的k作为我们最佳聚类系数，python实现如下： import pandas as pd from sklearn.cluster import KMeans from sklearn.metrics import silhouette_score import matplotlib.pyplot as plt df_features = pd.read_csv(r'C:\Users\61087\Desktop\项目\爬虫数据\预处理后数据.csv',encoding='gbk') Scores = [] # 存放轮廓系数 for k in range(2,9): estimator = KMeans(n_clusters=k) # 构造聚类器 estimator.fit(df_features[['R','F','M']]) Scores.append(silhouette_score(df_features[['R','F','M']],estimator.labels_,metric='euclidean')) X = range(2,9) plt.xlabel('k') plt.ylabel('轮廓系数') plt.plot(X,Scores,'o-') plt.show()聚类数k与轮廓系数的关系图： 但是，讲道理，k=2时轮廓系数最大，聚类效果应该非常好，那为什么SSE会这么大呢？在我看来，原因在于轮廓系数考虑了分离度b，也就是样本与最近簇中所有样本的平均距离。为什么这么说，因为从定义上看，轮廓系数大，不一定是凝聚度a（样本与同簇的其他样本的平均距离）小，而可能是b和a都很大的情况下b相对a大得多，这么一来，a是有可能取得比较大的。a一大，样本与同簇的其他样本的平均距离就大，簇的紧凑程度就弱，那么簇内样本离质心的距离也大，从而导致SSE较大。所以，虽然轮廓系数引入了分离度b而限制了聚类划分的程度，但是同样会引来最优结果的SSE比较大的问题，这一点也是值得注意的。 **总结：**从以上两个例子可以看出，轮廓系数法确定出的最优k值不一定是最优的，有时候还需要根据SSE去辅助选取，这样一来相对手肘法就显得有点累赘。因此，如果没有特殊情况的话，我还是建议首先考虑用手肘法。 四、其他问题的解答4、K-means算法中初始点的选择对最终结果有影响吗？ 会有影响的，不同的初始值结果可能不一样 5、K-means聚类中每个类别中心的初始点如何选择？ （1）这k个点的距离尽可能远 （2）可以对数据先进行层次聚类（博客后期会更新这类聚类算法），得到K个簇之后，从每个类簇中选择一个点，该点可以是该类簇的中心点，或者是距离类簇中心点最近的那个点。 6、K-means中空聚类的处理 （1）选择一个距离当前任何质心最远的点。这将消除当前对总平方误差影响最大的点。 （2）从具有最大SSE的簇中选择一个替补的质心，这将分裂簇并降低聚类的总SSE。如果有多个空簇，则该过程重复多次。 （3）如果噪点或者孤立点过多，考虑更换算法，如密度聚类（博客后期会更新这类聚类算法） 7、K-means是否会一直陷入选择质心的循环停不下来？ （1）迭代次数设置 （2）设定收敛判断距离 8、如何快速收敛数据量超大的K-means？ 相关解释可以去这个博客稍做了解https://blog.csdn.net/sunnyxidian/article/details/89630815 9、K-means算法的优点和缺点是什么？ K-Means的主要优点： （1）原理简单，容易实现 （2）可解释度较强 K-Means的主要缺点： （1）K值很难确定 （2）局部最优 （3）对噪音和异常点敏感 （4）需样本存在均值（限定数据种类） （5）聚类效果依赖于聚类中心的初始化 （6）对于非凸数据集或类别规模差异太大的数据效果不好 |
其中，Ci是第i个簇，p是Ci中的样本点，mi是Ci的质心（Ci中所有样本的均值），SSE是所有样本的聚类误差，代表了聚类效果的好坏。 手肘法的核心思想是：随着聚类数k的增大，样本划分会更加精细，每个簇的聚合程度会逐渐提高，那么误差平方和SSE自然会逐渐变小。并且，当k小于真实聚类数时，由于k的增大会大幅增加每个簇的聚合程度，故SSE的下降幅度会很大，而当k到达真实聚类数时，再增加k所得到的聚合程度回报会迅速变小，所以SSE的下降幅度会骤减，然后随着k值的继续增大而趋于平缓，也就是说SSE和k的关系图是一个手肘的形状，而这个肘部对应的k值就是数据的真实聚类数。当然，这也是该方法被称为手肘法的原因。
显然，肘部对于的k值为4，故对于这个数据集的聚类而言，最佳聚类数应该选4。
其中，a是Xi与同簇的其他样本的平均距离，称为凝聚度，b是Xi与最近簇中所有样本的平均距离，称为分离度。而最近簇的定义是：
其中p是某个簇Ck中的样本。事实上，简单点讲，就是用Xi到某个簇所有样本平均距离作为衡量该点到该簇的距离后，选择离Xi最近的一个簇作为最近簇。
求出所有样本的轮廓系数后再求平均值就得到了平均轮廓系数。平均轮廓系数的取值范围为[-1,1]，且簇内样本的距离越近，簇间样本距离越远，平均轮廓系数越大，聚类效果越好。那么，很自然地，平均轮廓系数最大的k便是最佳聚类数。
可以看到，轮廓系数最大的k值是2，这表示我们的最佳聚类数为2。但是，值得注意的是，从k和SSE的手肘图可以看出，当k取2时，SSE还非常大，所以这是一个不太合理的聚类数，我们退而求其次，考虑轮廓系数第二大的k值4，这时候SSE已经处于一个较低的水平，因此最佳聚类系数应该取4而不是2。【本文地址】