机器学习十大算法之三K-means

K-means算法 （无监督算法，聚类算法）

K-means算法，也称为K平均或K均值算法；
K平均聚类的目的是：把n个点（可以是样本的一次观察或一个实例）划分到k个聚类中，使得每个点都属于离他最近中心点的距离最近（或者说相似度上更相近的）对应的聚类。

1.从定义可以看出Kmeans主要是通过K中心和对K中心的距离计算进行聚类；所以K-means主要问题是K值选取和距离（相似度衡量）使用
2.由于每次都要计算所有的样本与每一个质心之间的距离(相似度)，故在大规模的数据集上，K-Means算法的收敛速度比较慢。

参考链接：机器学习sklearn19.0聚类算法——Kmeans算法

一、算法流程

1.选择聚类的个数k（kmeans算法传递超参数的时候，只需设置最大的K值）
2.任意产生k个聚类，然后确定聚类中心，或者直接生成k个中心。
3.对每个点确定其聚类中心点。
4.再计算其聚类新中心。
5.重复以上步骤直到满足收敛要求。（通常就是确定的中心点不再改变，或者损失函数达到预期范围）

二、算法举例

举例如下样本，通过Kmeans对其分为两类：

样本	X值	Y值
p1	7	7
p2	2	3
p3	6	8
p4	1	4
p5	1	2
p6	3	1
p7	8	8
p8	9	10
p9	10	7
p10	5	5
p11	7	6
p12	9	3
p13	2	8
p14	5	11
p15	5	2

数据点分布在坐标轴上的图像如下：

1.使用K-means中分两类K=2；
2.选择p1,p2为初始的两个中心点
3.对相似度的计算选择欧式距离作为相似度分类计算
4.第一轮计算：
1）通过距离公式计算进行每个点距离P1,P2的距离远近

2) 选取距离较近的点整理进入相应队列：

P1	P3	P7	P8	P9	P10	P11	P12	P14
P2	P4	P5	P6	P13	P15

3) 计算出新一轮的队列中心，代替原来的P1,P2(找出分为两类的中心点，这个中心点比P1,P2更适合)
Px,y=∑ni=1Pix,yn$P_{x,y}=\sum _{i=1}^n\frac{P_{ix,y}}{n}$ 得出两个中心点为：
第一个中心点为
P1′=(p1x+p3x+p7x+p8x+p9x+p10x+p11x+p12x+p14x9,p1y+p3y+p7y+p8y+p9y+p10y+p11y+p12y+p14y9)=(7.3,7.2)$P{1}^{\prime }=(\frac{p{1}_x+p{3}_x+p{7}_x+p{8}_x+p{9}_x+p{10}_x+p{11}_x+p{12}_x+p{14}_x}{9},\frac{p{1}_y+p{3}_y+p{7}_y+p{8}_y+p{9}_y+p{10}_y+p{11}_y+p{12}_y+p{14}_y}{9})=(7.3,7.2)$
同理：P2′=(p2x+p4x+p5x+p6x+p13x+p15x6,p2y+p4y+p5y+p6y+p13y+p15y7)=(1.8,4.6)$P{2}^{\prime }=(\frac{p{2}_x+p{4}_x+p{5}_x+p{6}_x+p{13}_x+p{15}_x}{6},\frac{p{2}_y+p{4}_y+p{5}_y+p{6}_y+p{13}_y+p{15}_y}{7})=(1.8,4.6)$

4)重复上述步骤，开始新一轮迭代，算距离，取最近：这次算的是p1~p15到p1′和p2′$p{1}^{\prime }和p{2}^{\prime }$的距离
5)当每次迭代结果不变时，认为算法收敛，聚类完成：

迭代示意图如下：

三、算法优缺点

优点：
1、原理简单（靠近中心点），实现容易
2、聚类效果中上
3、空间复杂度o(N)时间复杂度o(I*K*N) N为样本点个数，K为中心点个数，I为迭代次数
缺点：
1、对离群点， 噪声敏感 （中心点易偏移）
2、很难发现大小差别很大的簇及进行增量计算
3、结果不一定是全局最优，只能保证局部最优（与K的个数及初值选取有关）
4、K值选取对迭代次数和聚类效果有一定影响

四、算法优化

1.K值选择优化

Elbow method（肘部法则）

对于n个点的数据集，迭代计算k from 1 to n，每次聚类完成后计算每个点到其所属的簇中心的距离的平方和，可以想象到这个平方和是会逐渐变小的，直到k==n时平方和为0，因为每个点都是它所在的簇中心本身。但是在这个平方和变化过程中，会出现一个拐点也即“肘”点，下图可以看到下降率突然变缓时即认为是最佳的k值。

肘方法的核心指标是SSE(sum of the squared errors，误差平方和)， Ci是第i个簇， p是Ci中的样本点， mi是Ci的质心（Ci中所有样本的均值）， SSE是所有样本的聚类误差，代表了聚类效果的好坏。

SSE=∑i=1k∑p∈Ci|p−mi|2$$SSE=\sum _{i=1}^k\sum _{p\in C_i}|p-m_i{|}^2$$

肘方法的核心思想：
随着聚类数k的增大，样本划分会更加精细，每个簇的聚合程度会逐渐提高，那么误差平方和SSE自然会逐渐变小。并且，当k小于真实聚类数时，由于k的增大会大幅增加每个簇的聚合程度，故SSE的下降幅度会很大，而当k到达真实聚类数时，再增加k所得到的聚合程度回报会迅速变小，所以SSE的下降幅度会骤减，然后随着k值的继续增大而趋于平缓，也就是说SSE和k的关系图是一个手肘的形状，而这个肘部对应的k值就是数据的真实聚类数。这也是该方法被称为肘方法的原因。

聚类效果怎么判断？
1、SSE误差平方和越小越好，肘部拐点的地方。
2、也可用轮廓系数表示 系数越大，聚类效果越好，簇与簇之间距离越远

kmeans算法的最大弱点：只能处理球形的簇———通过中心点距离计算，这样就出现中心质点为圆心的圆形；

轮廓系数

Silhouette Coefficient）结合了聚类的凝聚度（ Cohesion）和分离度（ Separation），用于评估聚类的效果。该值处于-1~1之间，值越大，表示聚类效果越好。

S=(b−a)max(a,b)S∈[−1,1]a是Xi与同簇的其他样本的平均距离，称为凝聚度；b是Xi与最近簇中所有样本的平均距离，称为分离度。$$\begin{gathered} S=\frac{(b-a)}{max(a,b)}S\in [-1,1] \\ a是Xi与同簇的其他样本的平均距离，称为凝聚度； \\ b是Xi与最近簇中所有样本的平均距离，称为分离度。 \end{gathered}$$

最近簇的定义：

Cj=argminCk1n∑p∈Ck|p−Xi|2$$C_j=argmi{n}_{Ck}\frac{1}{n}\sum _{p\in C_k}|p-X_i{|}^2$$

其中p是某个簇Ck中的样本。即，用Xi到某个簇所有样本平均距离作为衡量该点到该簇的距离后，选择离Xi最近的一个簇作为最近簇。
求出所有样本的轮廓系数后再求平均值就得到了平均轮廓系数。平均轮廓系数的取值范围为[-1,1]，且簇内样本的距离越近，簇间样本距离越远，平均轮廓系数越大，聚类效果越好。

2.对计算量大的优化

Canopy算法 (粗略求K范围)

1、Canopy简介：
参考链接：
Canopy Clustering 简介
python实现Canopy算法

Canopy聚类最大的特点是不需要事先指定k值(即clustering的个数)，因此具有很大的实际应用价值。Canopy算法是2000年由Andrew McCallum, Kamal Nigam and Lyle Ungar提出来的，它是对k-means聚类算法和层次聚类算法的预处理。众所周知，kmeans的一个不足之处在于k值需要通过人为的进行调整，后期可以通过肘部法则（Elbow Method）和轮廓系数（Silhouette Coefficient）来对k值进行最终的确定，但是这些方法都是属于“事后”判断的，而Canopy算法的作用就在于它是通过事先粗聚类的方式，为k-means算法确定初始聚类中心个数和聚类中心点。 Canopy聚类虽然精度较低，但其在速度上有很大优势，因此可以使用Canopy聚类先对数据进行“粗”聚类， 得到k值后再使用K-means进行进一步“细”聚类。

2、Canopy+Kmeans：

a. 聚类最耗费计算的地方是计算对象相似性的时候，Canopy聚类在第一阶段选择简单、计算代价较低的方法计算对象相似性，将相似的对象放在一个子集中，这个子集被叫做Canopy，通过系列计算得到若干Canopy，Canopy之间可以是重叠的，但不会存在某个对象不属于任何Canopy的情况， 可以把这一阶段看做数据预处理；

b . 在各个Canopy 内使用传统的聚类方法(如K-means)，不属于同一Canopy的对象之间不进行相似性计算。 （即， 根据Canopy算法产生的Canopies代替初始的K个聚类中心点，由于已经将所有数据点进行Canopies有覆盖划分，在计算数据离哪个k-center最近时，不必计算其到所有k-centers的距离， 只计算和它在同一个Canopy下的k-centers这样可以提高效率）

c、Canopy详解：
1， 首先选择两个距离阈值： T1和T2， 其中T1 > T2
2， 从list中任取一点P，用低计算成本方法快速计算点P与所有Canopy之间的距离（如果当前不存在Canopy，则把点P作为一个Canopy），如果点P与某个Canopy距离在T1以内，则将点P加入到这个Canopy
3， 如果点P曾经与某个Canopy的距离在T2以内，则需要把点P从list中删除，这一步是认为点P此时与这个Canopy已经够近了， 因此它不可以再做其它Canopy的中心了
4， 重复步骤2、3， 直到list为空结束

Canopy实现代码:GITHUB

优点：
1、 Kmeans对噪声抗干扰较弱，通过Canopy对比，将较小的NumPoint的Cluster直接去掉有利于抗干扰。
2、 Canopy选择出来的每个Canopy的centerPoint作为K会更精确。
3、 只是针对每个Canopy的内做Kmeans聚类， 减少相似计算的数量。
缺点：
算法中 T1、 T2（T2 < T1） 的确定问题

五、Kmeans算法评价指标：Calinski-Harabaz Index

Calinski-Harabasz：类别内部数据的协方差越小越好，类别之间的协方差越大越好，这样的Calinski-Harabasz分数s会高， 分数s高则聚类效果越好

s(k)=tr(Bk)tr(Wk)m−kk−1$$s(k)=\frac{tr(B_k)}{tr(W_k)}\frac{m-k}{k-1}$$

其中m为训练集样本数， k为类别数。 Bk为类别之间的协方差矩阵， Wk为类别内部数据的协方差矩阵。 tr为矩阵的迹。

在scikit-learn中， Calinski-Harabasz Index对应的方法是metrics.calinski_harabaz_score.
在真实的分群label不知道的情况下，可以作为评估模型的一个指标。
同时，数值越小可以理解为：组间协方差很小，组与组之间界限不明显。
与轮廓系数的对比，笔者觉得最大的优势：快！相差几百倍！毫秒级
参考链接：聚类︱python实现 六大 分群质量评估指标（兰德系数、互信息、轮廓系数)

>>> import numpy as np
>>> from sklearn.cluster import KMeans
>>> kmeans_model = KMeans(n_clusters=3, random_state=1).fit(X)
>>> labels = kmeans_model.labels_
>>> metrics.calinski_harabaz_score(X, labels)  
560.39...

六、kmeans算法的优化

改进算法原理参考：强烈推荐

          $$K-means聚类算法的三种改进(K-means++,ISODATA,Kernel K-means)介绍与对比

          $$主要的聚类算法可以划分为如下几类：划分方法、层次方法、基于密度的方法、基于网格的方法以及基于模型的方法。目前,聚类问题的研究不仅仅局限于上述的硬聚类（即每一个数据只能被归为一类，数据集中每一个样本都是被100%确定得分到某一个类别中），模糊聚类也是聚类分析中研究较为广泛的一个分支。模糊聚类（通过隶属函数来确定每个数据隶属于各个簇的程度，而不是将一个数据对象硬性地归类到某一簇中，可以理解为每个样本是以一定的概率被分到某一个类别中） 。

硬聚类-1：K-means++

        $$假设已经选取了n个初始聚类中心(0< n< K)，则在选取第n+1个聚类中心时：距离当前n个聚类中心越远的点会有更高的概率被选为第n+1个聚类中心。 在选取第一个聚类中心(n=1)时同样通过随机的方法。可以说这也符合我们的直觉： 聚类中心当然是互相离得越远越好。
        $$类别数目随着聚类过程而变化；对类别数的“合并”：（当聚类结果某一类中样本数太少，或两个类间的距离太近时），“分裂”（当聚类结果中某一类的类内方差太大， 将该类进行分裂）。

可以通过距离找到每个中心点远近的概率：数据存在值域的范围，通过数据在值域范围的占比可以看出距离的远近

硬聚类-2：ISODATA

        $$类别数目随着聚类过程而变化；对类别数的“合并”：（当聚类结果某一类中样本数太少，或两个类间的距离太近时），“分裂”（当聚类结果中某一类的类内方差太大， 将该类进行分裂）。

硬聚类-3：Kernel k-means

        $$kernel k-means实际公式上，就是将每个样本进行一个投射到高维空间的处理，然后再将处理后的数据使用普通的k-means算法思想进行聚类。
        $$ 原理：映射到高维空间点就会分散

硬聚类-4：二分K-means

        $$首先将所有点作为一个簇，然后将该簇一分为二。之后选择能最大限度降低聚类代价函数（也就是误差平方和）的簇划分为两个簇。 以此进行下去，直到簇的数目等于用户给定的数目k为止。
        $$隐含的一个原则就：因为聚类的误差平方和能够衡量聚类性能，该值越小表示数据点越接近于他们的质心，聚类效果就越好。所以我们就需要对误差平方和最大的簇进行再一次划分，因为误差平方和越大，表示该簇聚类效果越不好，越有可能是多个簇被当成了一个簇，所以我们首先需要对这个簇进行划分。

扩展：5种常见的聚类方法

5种主要聚类算法的简单介绍

七、Mini Batch K-Means（适合大数据的聚类算法）：

        $$大数据量是什么量级？通过当样本量大于1万做聚类时，就需要考虑选用Mini Batch K-Means算法。
        $$Mini Batch KMeans使用了一个种叫做Mini Batch（分批处理）的方法对数据点之间的距离进行计算。 Mini Batch的好处是计算过程中不必使用所有的数据样本， 而是从不同类别的样本中抽取一部分样本来代表各自类型进行计算。由于计算样本量少， 所以会相应的减少运行时间，但另一方面抽样也必然会带来准确度的下降。

该算法的迭代步骤有两步：
1： 从数据集中随机抽取一些数据形成小批量，把他们分配给最近的质心
2： 更新质心与K均值算法相比，数据的更新是在每一个小的样本集上。
对于每一个小批量，通过计算平均值得到更新质心，并把小批量里的数据分配给该质心， 随着迭代次数的增加，这些质心的变化是逐渐减小的，直到质心稳定或者达到指定的迭代次数， 停止计算。

八、推广应用

图像压缩：原理是将不同的像素聚类，将同一类的图像用一种颜色取代

# print(__doc__)
import numpy as np
import matplotlib.pyplot as plt
from sklearn.cluster import KMeans
from sklearn.metrics import pairwise_distances_argmin
from sklearn.datasets import load_sample_image
from sklearn.utils import shuffle
from time import time
n_colors = 64
# 加载本地数据库里面的图片
china = load_sample_image("china.jpg")
# 转换为浮点数而不是默认的8位整数编码。
# 每一行有255个颜色分类
# 在[0-1]范围内
china = np.array(china, dtype=np.float64) / 255

# 45/5000加载图像并转换为2D numpy数组。
w, h, d = original_shape = tuple(china.shape)
assert d== 3
image_array = np.reshape(china, (w * h, d))
print("Fitting model on a small sub-sample of the data")
t0 = time()
image_array_sample = shuffle(image_array, random_state=0)[:1000]
kmeans = KMeans(n_clusters=n_colors, random_state=0).fit(image_array_sample)
print("done in %0.3fs." % (time() - t0))
# 获取所有的标签
print("Predicting color indices on the full image (k-means)")
t0 = time()
labels = kmeans.predict(image_array)
print("done in %0.3fs." % (time() - t0))

def recreate_image(codebook, labels, w, h):
#重新创建代码簿和标签中的（压缩）图像
    d = codebook.shape[1]
    image = np.zeros((w, h, d))
    label_idx = 0
    for i in range(w):
        for j in range(h):
            image[i][j] = codebook[labels[label_idx]]
            label_idx += 1
    return image

# 显示所有结果以及原始图像
plt.figure(1)
plt.clf()
ax = plt.axes([0, 0, 1, 1])
plt.axis('off')
plt.title('Original image (96,615 colors)')
plt.imshow(china)
plt.figure(2)
plt.clf()
ax = plt.axes([0, 0, 1, 1])
plt.axis('off')
plt.title('Quantized image (64 colors, K-Means)')
plt.imshow(recreate_image(kmeans.cluster_centers_, labels, w, h))
plt.show()

效果图如下：

kmeans练习代码地址：GITHUB