K-means聚类算法

零. 说在前面：

什么是特征向量？
用来描述样本点的一组数据，要和我们数学中的向量区别一下，本质来说就是个数组，数组中的每个元素代表从不同角度描述样本点的值。

K-means 是我们最常用的基于欧式距离的聚类算法，其认为两个目标的距离越近，相似度越大。
聚类就是对大量末知标注的数据集，按照数据内部存在的数据特征将数据集划分为多个不同的类别，使类别内的数据比较相似，类别之间的数据相似度比较大，属于无监督学习。
聚类算法的本质就是使得簇类样本尽可能相似，簇于簇间尽可能不同

和分类算法的区别：
分类算法是先有分类在来数据。
聚类算法是先有数据在来分类。

一. 算法步骤

1、首先确定一个k值，即我们希望将数据集经过聚类得到k个集合。

2、从数据集中随机选择k个数据点作为质心。

3、对数据集中每一个点，计算其与每一个质心的距离（如欧式距离），离哪个质心近，就划分到那个质心所属的集合。

4、把所有数据归好集合后，一共有k个集合。然后重新计算每个集合的质心。

5、如果新计算出来的质心和原来的质心之间的距离小于某一个设置的阈值（表示重新计算的质心的位置变化不大，趋于稳定，或者说收敛），我们可以认为聚类已经达到期望的结果，算法终止。

6、如果新质心和原质心距离变化很大，需要迭代3~5步骤。

二. 算法优缺点

优点：

1、原理比较简单，实现也是很容易，收敛速度快。

2、当结果簇是密集的，而簇与簇之间区别明显时, 它的效果较好。

3、主要需要调参的参数仅仅是簇数k。

缺点：

1、K值需要预先给定，很多情况下K值的估计是非常困难的。

2、K-Means算法对初始选取的质心点是敏感的，不同的随机种子点得到的聚类结果完全不同 ，对结果影响很大。

3、采用迭代方法，可能只能得到局部的最优解，而无法得到全局的最优解。

三. 算法实现

算法使用sklearn实现：

step 1 创建数据集合：

首先我们创建一个由500个样本构成的数据集合，我们首先将自定义划分为四类。

from sklearn.datasets import make_blobs
import matplotlib.pyplot as plt
#自己创建一个大小为500的数据集，由两维特征构成
X, y = make_blobs(n_samples=500,n_features=2,centers=4,random_state=1)

具体长这样：

color = ["red","pink","orange","gray"]
fig, ax1 = plt.subplots(1)
for i in range(4):
    ax1.scatter(X[y==i, 0], X[y==i, 1]
                ,marker='o' #点的形状
                ,s=8 #点的大小
                ,c=color[i]
                )
plt.show()

setp 2 基于分布进行聚类

首先，我们要猜测一下，这个数据中有几簇？
先猜测为3簇

from sklearn.cluster import KMeans
n_clusters = 3#首先测试的超参数
cluster = KMeans(n_clusters=n_clusters, random_state=0).fit(X)
y_pred = cluster.labels_
centroid = cluster.cluster_centers_

其中n_clusters代表我们聚类的簇数，y_pred代表对应元素聚类的类别，centroid代表每个类别的中心点。
现在我们打印一下聚类结果：

color = ["red","pink","orange","gray"]
fig, ax1 = plt.subplots(1)
for i in range(n_clusters):
    ax1.scatter(X[y_pred==i, 0], X[y_pred==i, 1]
                ,marker='o'
                ,s=8
                ,c=color[i]
                )#循环画小样本预测点的位置
    ax1.scatter(centroid[:,0],centroid[:,1]
                ,marker="x"
                ,s=18
                ,c="white")#循环画质心的位置
plt.show()

发现效果还不错！
但是我们最开始生成的是四类数据，同样的我们以四类来进行聚类试试？
并且我们顺便打印一下聚类效果

from sklearn.cluster import KMeans
n_clusters = 4#首先测试的超参数
cluster = KMeans(n_clusters=n_clusters, random_state=0).fit(X)
y_pred = cluster.labels_
centroid = cluster.cluster_centers_
color = ["red","pink","orange","gray"]
fig, ax1 = plt.subplots(1)
for i in range(n_clusters):
    ax1.scatter(X[y_pred==i, 0], X[y_pred==i, 1]
                ,marker='o'
                ,s=8
                ,c=color[i]
                )#循环画小样本预测点的位置
    ax1.scatter(centroid[:,0],centroid[:,1]
                ,marker="x"
                ,s=18
                ,c="white")#循环画质心的位置
plt.show()

和我们的原始数据比较一下：

效果不错！
但是这样问题就来了
我们如何去衡量一个K值得选取是否合适呢？

四. 聚类效果测评

被分在同一个簇中的数据是有相似性的，而不同簇中的数据是不同的，当聚类完毕之后，我们就要分别去研究每个簇中的样本都有什么样的性质。
根据聚类效果，我们追求“簇内差异小，簇外差异大”。而这个“差异“，由样本点到其所在簇的质心的距离来衡量。
对于一个簇来说，所有样本点到质心的距离之和越小，我们就认为这个簇中的样本越相似，簇内差异就越小。而距离的衡量方法有多种，令$x$表示簇中的一个样本点，$\mu$表示该簇中的质心，$n$表示每个样本点中的特征数目，$i$表示组成点$x$的每个特征，则该样本点到质心的距离可以由以下距离来度量:

欧几里得距离

$d(x,\mu )=\sqrt{{\sum }_{i=1}^n(x_i-{\mu }_i{)}^2}$

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

$CSS={\sum }_{j=0}^m{\sum }_{i=0}^n(x_i-{\mu }_i{)}^2$

$TotalCSS={\sum }_{l=1}^{k}CS{S}_l$

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

代码实现

inertia = cluster.inertia_

对，就这么简单
然后我们探究一下刚刚数据中k大小与这个$TotalInertia$的关系

x_i,y_i=[],[]
for i in range(1,11):
    n_clusters = int(i)#首先测试的超参数\
    cluster = KMeans(n_clusters=n_clusters, random_state=0).fit(X)
    inertia = cluster.inertia_
    x_i.append(i)
    y_i.append(inertia)
plt.plot(y_i)

由图可知当k取值3到4左右的时候$TotalInertia$是比较小的。

并且我们可以发现k值越大，$TotalInertia$的值越小，也就是模型越好

而这样说明，$TotalInertia$最为评价K值选取的参数使用是不好的，不可能将样本分成任意多的簇

所以使用Inertia用来评估聚类的效果可以，但没必要因为这个指标的缺点太大。

并且使用Inertia作为评估指标，会让聚类算法在一些细长簇，环形簇，或者不规则形状的流形时表现不佳：

所以研究者们往往会采用其他参数来对聚类效果进行衡量

五. 算法评估PLUS

一般我们使用聚类算法进行评估时往往有两种数据情况

1.当标签已知的时候

2.当标签未知的时候

1.当标签已知的时候（不做讨论）

2.当标签未知的时候

当标签未知的时候我们往往会采用轮廓系数进行衡量。

在99%的情况下，我们是对没有真实标签的数据进行探索，也就是对不知道真正答案的数据进行聚类。这样的聚类，是完全依赖于评价**簇内的稠密程度（簇内差异小）和簇间的离散程度（簇外差异大）**来评估聚类的效果。

其中轮廓系数是最常用的聚类算法的评价指标

它是对每个样本来定义的：

1）样本与其自身所在的簇中的其他样本的相似度a，等于样本与同一簇中所有其他点之间的平均距离

2）样本与其他簇中的样本的相似度b，等于样本与下一个最近的簇中的所有点之间的平均距离

根据聚类的要求”簇内差异小，簇外差异大“，我们希望b永远大于a，并且大得越多越好。
轮廓系数计算方法如下：

$s=\frac{b-a}{max(a,b)}$

由公式可知轮廓系数范围是(-1,1)。

其中值越接近1表示样本与自己所在的簇中的样本很相似，并且与其他簇中的样本不相似。

当样本点与簇外的样本更相似的时候，轮廓系数就为负。

当轮廓系数为0时，则代表两个簇中的样本相似度一致，两个簇本应该是一个簇。

可以总结为轮廓系数越接近于1越好，负数则表示聚类效果非常差。越接近1越好；越接近-1越不好。

如果一个簇中的大多数样本具有比较高的轮廓系数，则簇会有较高的总轮廓系数，则整个数据集的平均轮廓系数越高，则聚类是合适的。如果许多样本点具有低轮廓系数甚至负值，则聚类是不合适的，聚类的超参数K可能设定得太大或者太小。

代码如下：

from sklearn.metrics import silhouette_score
x_i,y_i=[],[]
for n_clusters in range(2,11):
    clusterer = KMeans(n_clusters=n_clusters, random_state=10)
    cluster_labels = clusterer.fit_predict(X)
    silhouette_avg = silhouette_score(X, cluster_labels)
    x_i.append(n_clusters)
    y_i.append(silhouette_avg)
    print("For n_clusters =", n_clusters,
          "The average silhouette_score is :", silhouette_avg)
plt.plot(x_i, y_i)

结果如图：

可见我们在k=4左右效果最好，我们数据集生成也是4个类别。可见使用轮廓系数作为k值选取的参考非常合理。

轮廓系数有很多优点，它在有限空间中取值，使得我们对模型的聚类效果有一个“参考”。

并且，轮廓系数对数据的分布没有假设，因此在很多数据集上都表现良好。但它在每个簇的分割比较清洗时表现最好。但轮廓系数也有缺陷，它在凸型的类上表现会虚高，比如基于密度进行的聚类，或通过DBSCAN获得的聚类结果，如果使用轮廓系数来衡量，则会表现出比真实聚类效果更高的分数。

除了轮廓系数是最常用的，我们还有卡林斯基-哈拉巴斯指数（Calinski-Harabaz Index，简称CHI，也被称为方差比标准），戴维斯-布尔丁指数（Davies-Bouldin）以及权变矩阵（Contingency Matrix）可以使用。

六. Referance

[1]Ahmed M, Seraj R, Islam S M S. The k-means algorithm: A comprehensive survey and performance evaluation[J]. Electronics, 2020, 9(8): 1295.
[2]Hartigan J A, Wong M A. Algorithm AS 136: A k-means clustering algorithm[J]. Journal of the royal statistical society. series c (applied statistics), 1979, 28(1): 100-108.
[3]Likas A, Vlassis N, Verbeek J J. The global k-means clustering algorithm[J]. Pattern recognition, 2003, 36(2): 451-461.
[4]Krishna K, Murty M N. Genetic K-means algorithm[J]. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 1999, 29(3): 433-439.