聚类算法-K-means

主要在K-means的理解

1 介绍K-means算法，以及具体的过程

K-means算法是常用的聚类算法之一，属于无监督学习，主要用来将标签未知的数据划分成较少的类/簇，类内的样本差异要小，类间的样本差异要大，这可以帮助我们探索数据结构和分布。

K-means的具体实现过程：（四步）

• 初始化模型参数：聚类的簇数，以及初始聚类中心点；初始中心点的设置可以是随机的，也可以使用自己定义的；
• 计算距离：计算每个样本点与各个簇中心点的距离，常用的距离是欧氏距离，将每个样本点分配到距离它们最近的簇中；
• 更新簇的中心点：计算同一簇中所有样本的均值，作为新的中心点；
• 迭代步骤2和3，直到簇的中心点不在发生变化，或者达到设定的某个中止条件，如最大迭代次数；

最终，确定了每个样本所属类别，以及各类的中心的。

2 一些计算公式

距离的计算公式有哪些：

一个样本点（n维）：\(x=(x_1,...,x_n)\)

一个类中心点：\(\mu=(\mu_1,...,\mu_n)\)

欧式距离：\(d(x,\mu)=\sqrt{\sum_{i=1}^n(x_i-\mu_i)^2}\)

曼哈顿距离：\(d(x,\mu)={\sum_{i=1}^n|x_i-\mu_i|}\)

余弦距离：\(\cos\theta = \frac{\sum_{i=1}^n(x_i*\mu_i)}{\sqrt{\sum_{i=1}^nx_i^2}\sqrt{\sum_{i=1}^n\mu_i^2}}\) 其实就是 向量内积 / 向量长度乘积

在文本挖掘中，常用余弦相似度（Cosine Similarity）来衡量文本之间的相似性，其取值范围也在[0, 1]之间，其中，值为1表示文本完全相似，值为0表示文本没有相似性。余弦距离和余弦相似度的关系为：Cosine Similarity=1−Cosine Distance

3 簇内平方和，整体平方和

衡量差异的指标--样本点到所在簇的中心的距离--簇内误差平方和

在sklearn当中，我们无法选择使用的距离，只能使用欧式距离，欧氏距离求出的中心点---类的均值点。

使用欧式距离计算一个簇中所有样本点到质心的距离平方和（簇内平方和，cluster sum of square）和（整体平方和，Total Cluster Sum of Square，Total Inertia）

共有m个样本点，n维特征，k个簇，第l个簇的簇内平方和\(CSS_l\)，整体的簇内平方和Inertia

$ CSS_l = \sum_{j=0}^m{\sum_{i=1} (x_i - \mu_i)^2} $

$ Inertia = \sum_{l=1}^k{CSS_l} $

4 K-means的收敛问题

Total Inertia越小，代表着每个簇内样本越相似，聚类的效果就越好。

K-means求解的是让Inertia最小化的类中心点。

在K-Means聚类算法中，我们的目标是最小化每个数据点到其所属质心的距离之和，即最小化整体平方和。当整体平方和最小时，意味着质心的位置找到了最佳的位置，即质心不再发生变化。（k-means中质心就是中心点）

目标函数（或者理解为损失函数）就是整体的平方和Inertia。

5 K-means优缺点

优点：

• 原理、操作简单

缺点：

• 收敛慢，耗时，平均的时间复杂度\(O(K*n*T)\)，最坏的情况是\(O(n^{(k+2)/p})\)，K是要分的簇数，n是样本量，T是迭代次数；KNN是\(O(n)\)​
• 不能发现非凸形状的簇
• 需要事先确定超参数K
• 对噪声和离群点敏感，容易受到他们的影响
• 结果不一定是全局最优，只能收敛到局部最优
• 没有最优解，如果不设置随机数，每一次聚类结果都不同
• 最大的缺点！！！收敛情况严重依赖于簇中心的初始化状况！

6 聚类算法的评估指标

聚类结果的评价方法一般分为：内部评估法、外部评估法。

• 外部评估方法：是指在知道真实标签（ground truth ）的情况下来评估聚类结果的好坏。一般来说在做论文，或者是有少量的标注数据时，都可以用外部评估法选择一个相对最优的聚类模型，然后再应用到其它未被标记的数据中。常用的：纯度、F值、兰德系数、调整兰德系数

• 内部评估法：不借助于外部信息，仅仅只是根据聚类结果来进行评估，常见的有轮廓系数（Silhouette Coefficient）、Calinski-Harabasz Index等，这些sklearn中也都有实现可以直接调用。一般来说，在完全没有标记数据的情况下可以通过这种方式来评估聚类结果的好坏。

一般用聚类的都是不知道真实标签的数据，如果知道真实标签，为什么不使用分类呢，但也存在这种知道真实标签但还是使用聚类（比如在写论文，我要验证结果）。

真实标签未知（内部评估法）：

（1）轮廓系数（Silhouette Coefficient）

先理解a，b：

簇内距离\(a_i\)：样本 i 到同簇其他样本的平均距离；

簇间距离\(b_i\)​：样本 i 到距离自己最临近的簇中所有样本的平均距离；

！！（特别注意：在寻找距离当前样本点最近的簇时，计算的是当前样本点到各个簇中心的最短距离，而不是计算当前样本点所在簇的簇中心到其它每个簇中心的最短距离。因此，对于同一个簇中的每个样本点来说，距离自己最近的簇可能并不是同一个）！！

单个样本\(i\)的轮廓系数计算为：\(s_i = \frac{b_i - a_i}{max(a_i, b_i)}\)

先理解单个样本的轮廓系数，\(s_i\)​的取值范围在[-1, 1]；

第一种情况，当\(a_i\) 很小，\(b_i\) 很大时，这说明样本i和同簇其他样本之间距离比较近、相似度高；样本i和其最邻近簇的距离较远，此时\(s_i\)​的值接近1，聚类效果好，这也正是我们所期待的；

第二种情况，正好相反，当\(a_i\) 很大，\(b_i\) 很小时，这说明样本i和同簇其他样本之间距离比较远、相似度低；样本i和其最邻近簇的距离较近，此时\(s_i\)的值接近-1，聚类效果差；

第三种情况，簇内距离和簇间距离相等，这是什么情况呢？当样本i所在簇只有它自已一个，它属于那个簇不清楚，可以粗略地认为它属于离他最近的簇中，所以有\(a_i\) = \(b_i\)，\(s_i = 0\)​ 是一种中立的情况。

整个聚类结果的轮廓系数为：加在一起求均值.

（2）卡林斯基-哈拉巴斯指数(Calinski-Harabaz Index, CHI )

记住聚类的总的思想：要求簇内差异小，簇间差异大，不同类之间的距离要大，同类之间距离要小，这样聚类效果好。

CHI = 所有簇的簇间距离和 / 所有簇的簇内距离和 （计算过程和方差比类似，所以又称为方差比）--取值范围（0， +∞）

CHI越小，表明簇内距离比簇间距离大，说明簇与簇之间距离较近，聚类效果越差；

CHI越大，表明簇内距离比簇间距离小，簇间距离大于簇内距离，说明簇与簇之间距离较远距离，聚类效果好。

（3）戴维斯-布尔丁指数（Davies-Bouldin）

DB指数的核心思想是计算每个簇与之最相似簇之间相似度，然后再通过求得所有相似度的平均值来衡量整个聚类结果的优劣。

DB指数中，簇与簇之间的相似度定义：两个簇的簇内直径和与簇间距离的比值

7 参数K怎么确定？---调参

常用的确定簇数K的方法，通常是经验指导或者一些启发式方法：

• 手肘法（Elbow Method）

通过绘制不同K值对应的簇内平方和（Inertia）或误差平方和的曲线图，选择肘部或拐点对应的K值作为最佳聚类数量。肘部通常表示在该点之后，簇内平方和的下降速度开始变缓。

• Gap Statistic
• 采用核函数

面对非凸的数据分布形状是，可能需要引入核函数来优化，此时算法称为核K均值算法，是核聚类方法的一种。

核聚类方法的主要思想是通过一个非线性映射，将输入空间中的数据点映射到高位的特征空间中，并在新的特征空间中进行聚类。

非线性映射增加了数据点线性可分的概率，从而在经典的聚类算法失效的情况下，通过引入核函数可以达到更为准确的聚类效果。

8 其他常用的聚类算法的简单介绍

针对K均值的缺点，有哪些改进的模型？

回想K-means的致命缺点：收敛情况依赖于初始簇中心的选择

那么，让我们欢迎 K-means++登场！K-means的进阶版！

K-means++

区别在于：该算法在簇中心的初始化方法上做了改变！

K-means：随机选取K个样本点作为初始的簇中心点；

K-means++具体流程：

（1）先随机选取一个样本作为第一个簇中心，

（2）计算每个样本点与已有簇中心之间的最短距离（\(D(x)\)）；计算每个样本点被选为下一个聚类中心的"概率“（\(P(x)\)）；距离当前簇中心越远的样本点有更高的概率成为下一个簇中心点
\(x\) 是样本空间\(\chi\) 中的样本点

​ \(P(x) = \frac{D(x)}{\sum_{x\in\chi}D(x)}\)

（3）重复第（2）步，直到选出k个聚类中心。

（4）后续聚类方法与k-means相同。

ISODATA算法

迭代自组织数据分析法

当 属于某个类别的样本数过少时，把该类别去除；当属于某个类别的样本 数过多、分散程度较大时，把该类别分为两个子类别。ISODATA算法在K-means均值算法的基础之上增加了两个操作，一是分裂操作，对应着增加聚类中心数；二是合并操作，对应着减少聚类中心数。