K-Means
聚类算法有很多种（几十种），K-Means是聚类算法中的最常用的一种，**该算法最大的特点是简单，好理解，运算速度快，但是只能应用于连续型的数据，并且一定要在聚类前需要手工指定要分成几类。**
下面，我们描述一下**K-means算法的过程**，为了尽量不用数学符号，所以描述的不是很严谨，大概就是这个意思，**“物以类聚、人以群分”**：
# K-means算法的过程
1. **首先输入k的值**，即我们希望将数据集经过聚类得到k个分组。
2. 从数据集中**随机选择k个数据点作为质心**
3. 对集合中每一个数据点，**计算与每一个质心的距离**（距离的含义后面会讲），离哪个质心距离近，就跟定哪个质心。
4. 这时每一个质心手下都聚集了一票数据点，这时候召开人民代表大会，**各类别通过算法选出新的质心**。
5. 当**新质心和老质心之间的距离小于某一个设置的阈值**（表示重新计算的质心的位置变化不大，趋于稳定，或者说收敛），可以认为我们进行的聚类已经达到期望的结果，算法终止。
6. 如果新质心老质心距离变化很大，需要**迭代3~5步**骤。
## 1 最优k值的选取：
### 1.1 手肘法
#### 1.11 理论
手肘法的核心指标是SSE(sum of the squared errors，误差平方和)：
$$S S E=\sum_{i=1}^{k} \sum_{p \in C_{i}}\left|p-m_{i}\right|^{2}$$
其中，$C_{i}$是第i个簇，$p$是$C_{i}$中的样本点，$m_{i}$是$C_{i}$的质心（$C_{i}$中所有样本的均值），SSE是所有样本的聚类误差，代表了聚类效果的好坏。
手肘法的核心思想是：随着聚类数k的增大，样本划分会更加精细，每个簇的聚合程度会逐渐提高，那么误差平方和SSE自然会逐渐变小。并且，当k小于真实聚类数时，由于k的增大会大幅增加每个簇的聚合程度，故SSE的下降幅度会很大，而当k到达真实聚类数时，再增加k所得到的聚合程度回报会迅速变小，所以SSE的下降幅度会骤减，然后随着k值的继续增大而趋于平缓，也就是说SSE和k的关系图是一个手肘的形状，而这个肘部对应的k值就是数据的真实聚类数。当然，这也是该方法被称为手肘法的原因。
#### 1.12 实践
我们对**预处理后数据.csv**中的数据利用手肘法选取最佳聚类数k。具体做法是让k从1开始取值直到取到你认为合适的上限(一般来说这个上限不会太大，这里我们选取上限为8)，对每一个k值进行聚类并且记下对于的SSE，然后画出k和SSE的关系图（毫无疑问是手肘形），最后选取肘部对应的k作为我们的最佳聚类数。python实现如下：
```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的关系图如下：
显然，肘部对于的k值为4，故对于这个数据集的聚类而言，最佳聚类数应该选4
### 1.2 轮廓系数法
#### 1.21 理论
该方法的核心指标是轮廓系数（Silhouette Coefficient），某个样本点$X_{i}$的轮廓系数定义如下：
$$S=\frac{b-a}{\max (a, b)}$$
其中，$a$是$X_{i}$与同簇的其他样本的平均距离，称为凝聚度，$b$是$X_{i}$与**最近簇**中所有样本的平均距离，称为分离度。而**最近簇的定义**是:
$$C_{j}=\arg \min _{c_{k}} \frac{1}{n_{p \in C_{k}}}\left|p-X_{i}\right|^{2}$$
其中$p$是某个簇$C_{k}$中的样本。事实上，简单点讲，就是用$X_{i}$到某个簇所有样本平均距离作为衡量该点到该簇的距离后，**选择离$X_{i}$最近的一个簇作为最近簇。**
**求出所有样本的轮廓系数后再求平均值就得到了平均轮廓系数**。平均轮廓系数的取值范围为[-1,1]，且簇内样本的距离越近，簇间样本距离越远，平均轮廓系数越大，聚类效果越好。那么，很自然地，平均轮廓系数最大的k便是最佳聚类数。
#### 1.22 实践
我们同样使用2.1中的数据集，同样考虑k等于1到8的情况，对于每个k值进行聚类并且求出相应的轮廓系数，然后做出k和轮廓系数的关系图，选取轮廓系数取值最大的k作为我们最佳聚类系数，python实现如下：
```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，这表示我们的最佳聚类数为2。但是，值得注意的是，从k和SSE的手肘图可以看出，当k取2时，SSE还非常大，所以这是一个不太合理的聚类数，我们退而求其次，考虑轮廓系数第二大的k值4，这时候SSE已经处于一个较低的水平，因此最佳聚类系数应该取4而不是2。
但是，讲道理，k=2时轮廓系数最大，聚类效果应该非常好，那为什么SSE会这么大呢？在我看来，原因在于轮廓系数考虑了分离度$b$，也就是样本与最近簇中所有样本的平均距离。为什么这么说，因为从定义上看，轮廓系数大，不一定是凝聚度$a$（样本与同簇的其他样本的平均距离）小，而可能是$b$和$a$都很大的情况下$b$相对$a$大得多，这么一来，$a$是有可能取得比较大的。$a$一大，样本与同簇的其他样本的平均距离就大，簇的紧凑程度就弱，那么簇内样本离质心的距离也大，从而导致SSE较大。所以，虽然轮廓系数引入了分离度$b$而限制了聚类划分的程度，但是同样会引来最优结果的SSE比较大的问题，这一点也是值得注意的。
### 1.3 总结:
从以上两个例子可以看出，轮廓系数法确定出的最优k值不一定是最优的，有时候还需要根据SSE去辅助选取，这样一来相对手肘法就显得有点累赘。因此，如果没有特殊情况的话，我还是建议首先考虑用手肘法。
转载：[K-means聚类最优k值的选取](https://blog.csdn.net/qq_15738501/article/details/79036255?utm_medium=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-2.channel_param&depth_1-utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-2.channel_param)
## 2 随机选取质心
初始的K个质心怎么选？ 答：**最常用的方法是随机选**，初始质心的选取对最终聚类结果有影响，因此算法一定要多执行几次，哪个结果更reasonable，就用哪个结果。 当然**也有一些优化的方法**，**第一种是**选择彼此距离最远的点，具体来说就是先选第一个点，然后选离第一个点最远的当第二个点，然后选第三个点，第三个点到第一、第二两点的距离之和最小，以此类推。**第二种是**先根据其他聚类算法（如层次聚类）得到聚类结果，从结果中每个分类选一个点。
## 3 计算数据点与每一个质心的距离
**判断每个点归属哪个质心的距离怎么算？**
答：这个问题必须不得不提一下数学了……
**第一种，欧几里德距离**（欧几里德这位爷还是很厉害的，《几何原本》被称为古希腊数学的高峰，就是用5个公理推导出了整个平面几何的结论），这个距离就是平时我们理解的距离，如果是两个平面上的点，也就是（X1，Y1），和（X2，Y2），那这俩点距离是多少初中生都会，就是$\sqrt{\left(x_{2}-x_{1}\right)^{2}+\left(y_{2}-y_{1}\right)^{2}}$ ，如果是三维空间中呢？$\sqrt{\left(x_{2}-x_{1}\right)^{2}+\left(y_{2}-y_{1}\right)^{2}+\left(z_{2}-z_{1}\right)^{2}}$ ；推广到高维空间公式就以此类推。可以看出，欧几里德距离真的是数学加减乘除算出来的距离，因此这就是**只能用于连续型变量的原因**。
**第二种，余弦相似度**，余弦相似度用向量空间中两个向量夹角的余弦值作为衡量两个个体间差异的大小。**相比距离度量，余弦相似度更加注重两个向量在方向上的差异，而非距离或长度上**。下图表示余弦相似度的余弦是哪个角的余弦，A，B是三维空间中的两个向量，这两个点与三维空间原点连线形成的角，如果角度越小，说明这两个向量在方向上越接近，在聚类时就归成一类：
**看一个例子**（也许不太恰当）：歌手大赛，三个评委给三个歌手打分，第一个评委的打分（10，8，9） 第二个评委的打分（4，3，2），第三个评委的打分（8，9，10） 如果采用余弦相似度来看每个评委的差异，虽然每个评委对同一个选手的评分不一样，但第一、第二两个评委对这四位歌手实力的排序是一样的，只是第二个评委对满分有更高的评判标准，说明第一、第二个评委对音乐的品味上是一致的。 因此，用余弦相似度来看，第一、第二个评委为一类人，第三个评委为另外一类。 如果采用欧氏距离， 第一和第三个评委的欧氏距离更近，就分成一类人了，但其实不太合理，因为他们对于四位选手的排名都是完全颠倒的。 总之，如果注重数值本身的差异，就应该用欧氏距离，如果注重的是上例中的这种的差异（我概括不出来到底是一种什么差异……），就要用余弦相似度来计算。
**还有其他的一些计算距离的方法，但是都是欧氏距离和余弦相似度的衍生**，简单罗列如下：明可夫斯基距离、切比雪夫距离、曼哈顿距离、马哈拉诺比斯距离、调整后的余弦相似度、Jaccard相似系数……
## 4 算法选取新质心
**每一轮迭代如何选出新的质心**？
答：**各个维度的算术平均**，比如该类数据点有（X1，Y1，Z1）、（X2，Y2，Z2）、（X3，Y3，Z3）$，那就该类新质心就是{（X1+X2+X3）/3，（Y1+Y2+Y3）/3，（Z1，Z2，Z3）/3 }，这里要注意，**新质心不一定是实际的一个数据点**。
## 5 K-Means优缺点
> **优点：**
>- **算法简单，容易实现** ；
>- 算法**速度很快**；
>- 对处理大数据集，该算法是**相对可伸缩的和高效率的**，因为它的复杂度大约是O(nkt)，其中n是所有对象的数目，k是簇的数目,t是迭代的次数。通常k<<n。这个算法**通常局部收敛**。
>- 算法尝试找出使平方误差函数值最小的k个划分。当簇是密集的、球状或团状的，且簇与簇之间区别明显时，聚类效果较好。
>
> **缺点：**
>- 对数据类型要求较高，适合**数值型数**据；
>- 可能收敛到局部最小值，在**大规模数据上收敛较慢**
>- 分组的数目k是一个输入参数，**不合适的k可能返回较差的结果**。
>- **对初值的簇心值敏感**，对于不同的初始值，可能会导致不同的聚类结果；
>- 不适合于发现非凸面形状的簇，或者大小差别很大的簇。
>- **对于”噪声”和孤立点数据敏感**，少量的该类数据能够对平均值产生极大影响。
## 6 K-Means的细节问题：
- **K-Means会不会陷入一直选质心的过程，永远停不下来？**
答：不会，有数学证明K-Means一定会收敛，大致思路是利用SSE的概念（也就是误差平方和），即每个点到自身所归属质心的距离的平方和，这个平方和是一个函数，然后能够证明这个函数是可以最终收敛的函数。
- **关于离群值？**
答：离群值就是远离整体的，非常异常、非常特殊的数据点，在聚类之前应该将这些“极大”“极小”之类的离群数据都去掉，否则会对于聚类的结果有影响。但是，离群值往往自身就很有分析的价值，可以把离群值单独作为一类来分析。
- **有一个重要的问题是，大家的单位要一致！**
比如X的单位是米，Y也是米，那么距离算出来的单位还是米，是有意义的; 但是如果X是米，Y是吨，用距离公式计算就会出现“米的平方”加上“吨的平方”再开平方，最后算出的东西没有数学意义，这就有问题了。
还有，即使X和Y单位一致，但是如果数据中X整体都比较小，比如都是1到10之间的数，Y很大，比如都是1000以上的数，那么，在计算距离的时候Y起到的作用就比X大很多，X对于距离的影响几乎可以忽略，这也有问题。
因此，如果K-Means聚类中选择欧几里德距离计算距离，数据集又出现了上面所述的情况，就一定要进行数据的标准化（normalization），即将数据按比例缩放，使之落入一个小的特定区间。去除数据的单位限制，将其转化为无量纲的纯数值，便于不同单位或量级的指标能够进行计算和比较。 标准化方法最常用的有两种：
**min-max标准化（离差标准化）**：对原始数据进行线性变换，是结果落到[0，1]区间，转换方法为 X'=（X-min）/（max-min），其中max为样本数据最大值，min为样本数据最小值。
**z-score标准化（标准差标准化）**：处理后的数据符合标准正态分布（均值为0，方差为1），转换公式：X减去均值，再除以标准差。
---
- **聚类分析中业务专家的作用：**
1. 业务专家的作用非常大，主要体现在聚类变量的选择和对于聚类结果的解读：比如要对于现有的客户分群，那么就要根据最终分群的目的选择不同的变量来分群，这就需要业务专家经验支持。如果要优化客户服务的渠道，那么就应选择与渠道相关的数据；如果要推广一个新产品，那就应该选用用户目前的使用行为的数据来归类用户的兴趣。算法是无法做到这一点的
2. 欠缺经验的分析人员和经验丰富的分析人员对于结果的解读会有很大差异。其实不光是聚类分析，所有的分析都不能仅仅依赖统计学家或者数据工程师。
::: hljs-center
**扩展阅读**
:::
[K-means聚类算法的三种改进(K-means++,ISODATA,Kernel K-means)介绍与对比](https://www.cnblogs.com/yixuan-xu/p/6272208.html)
---
转载：[聚类、K-Means、例子、细节](https://www.jianshu.com/p/fc91fed8c77b)