K-means聚类算法（2）

四、簇内误差平方和的定义

• 聚类算法聚出的类有什么含义呢？
  这些类有什么样的性质？

1、含义

• 我们认为，被分在同一个簇中的数据是有相似性的，而不同簇中的数据是不同的，当聚类完毕之后，接下来需要分别研究每个簇中的样本都有什么样的性质，从而根据业务需求制定不同的商业或者科技策略。
• 聚类算法追求“簇内差异小，簇外差异大”。而这个 “差异”便是通过样本点到其簇质心的距离来衡量。

2、性质

• 对于一个簇来说，所有样本点到质心的距离之和越小，便认为这个簇中的样本越相似，簇内差异越小。

• 而距离的衡量方法有多种，令x表示簇中的一个样本点，μ表示该簇中的质心，n表示每个样本点中的特征数目，i表示组成点x的每个特征，则该样本点到质心的距离可以由以下距离来度量：

  
  

• 如采用欧几里得距离，则一个簇中所有样本点到质心的距离的平方和为：

  
  

• 其中，m为一个簇中样本的个数，j是每个样本的编号。
  这个公式被称为簇内平方和（Cluster Sum of Square），又叫做Inertia。
  而将一个数据集中的所有簇的簇内平方和相加，就得到了整体平方和（Total Cluster Sum of Square），又叫做Total Inertia。
  Total Inertia越小，代表着每个簇内样本越相似，聚类的效果就越好。
  因此K-Means追求的是：求解能够让Inertia最小化的质心。
  实际上，在质心不断变化不断迭代的过程中，总体平方和是越来越小的。我们可以通过数学来证明，当整体平方和达到最小值的时候，质心就不再发生变化了。
  如此，K-Means的求解过程，就变成了一个最优化问题。

• 在K-Means中，在一个固定的簇数K条件下，最小化总体平方和来求解最佳质心，并基于质心的存在去进行聚类。
  两个过程十分相似，并且整体距离平方和的最小值其实可以使用梯度下降来求解。

• 大家可以发现， Inertia是基于欧几里得距离的计算公式得来的。
  实际上，也可以使用其他距离，每个距离都有自己对应的Inertia。
  在过去的经验中，已经总结出不同距离所对应的质心选择方法和Inertia，在K-Means中，只要使用了正确的质心和距离组合，无论使用什么距离，都可以达到不错的聚类效果。

  
  

五、K-Means算法的时间复杂度

• K-Means算法是一个计算成本很大的算法。
  K-Means算法的平均复杂度是O(knT)，
  其中k是超参数，即所需要输入的簇数，n是整个数据集中的样本量，T是所需要的迭代次数。
• 在最坏的情况下，KMeans的复杂度可以写作O(n(k+2)/p)，其中n是整个数据集中的样本量，p是特征总数。

六、聚类算法的模型评估指标

• 在分类中，有直接结果（标签）的输出，并且分类的结果有正误之分，所以需要通过使用预测的准确度、混淆矩阵、ROC曲线等指标来进行评估，但无论如何评估，都是在评估“模型找到正确答案”的能力。
  而在回归中，由于要拟合数据，可以通过SSE均方误差、损失函数来衡量模型的拟合程度。
  但这些衡量指标都不能够用于聚类。

• K-Means的目标是确保“簇内差异小，簇外差异大”，所以可以通过衡量簇内差异来衡量聚类的效果。
  肘部法（手肘法）、轮廓系数、卡林斯基-哈拉巴斯指数

七、聚类算法的迭代问题

• sklearn中也可以使用max_iter（最大迭代次数）或者tol两个参数来让迭代提前停下来。
• max_iter：整数，默认300，单次运行的k-means算法的最大迭代次数；
• tol：浮点数，默认1e-4，两次迭代间Inertia下降的量，如果两次迭代之间Inertia下降的值小于tol所设定的值，迭代就会停下。

八、优缺点

（1）K-Means算法的优点

• 原理比较简单，实现也是很容易，收敛速度快；
• 聚类效果较优，算法的可解释度比较强。

（2）K-Means算法的缺点

• K值的选取不好把握；
• 对于不是凸的数据集比较难收敛；
• 如果各隐含类别的数据不平衡，比如各隐含类别的数据量严重失衡，或者各隐含类别的方差不同，则聚类效果不佳；
• 采用迭代方法，得到的结果只是局部最优；
• 对噪音和异常点比较的敏感。

九、结论

• K均值（K-Means）聚类算法原理简单，可解释强，实现方便，可广泛应用在数据挖掘、聚类分析、数据聚类、模式识别、金融风控、数据科学、智能营销和数据运营等多个领域，有着广泛的应用前景。