K-means算法简述

1. K-means算法，也称为K-平均或者K-均值，一般作为掌握聚类算法的第一个算法。
2. 这里的K为常数，需事先设定，通俗地说该算法是将没有标注的 M 个样本通过迭代的方式聚集成K个簇。
3. 在对样本进行聚集的过程往往是以样本之间的距离作为指标来划分。

• 简单Demo说明
  
  如上图以 K 为2，样本集为M 来描述KMean算法，算法执行步骤如下：

1. 选取K个点做为初始聚集的簇心（也可选择非样本点）;
2. 分别计算每个样本点到 K个簇核心的距离（这里的距离一般取欧氏距离或余弦距离），找到离该点最近的簇核心，将它归属到对应的簇；
3. 所有点都归属到簇之后， M个点就分为了 K个簇。之后重新计算每个簇的重心（平均距离中心），将其定为新的“簇核心”；
4. 反复迭代 2 - 3 步骤，直到达到某个中止条件。

• 注：常用的中止条件有迭代次数、最小平方误差MSE、簇中心点变化率；

由上述Demo可知，对于KMean算法来说有三个比较重要的因素要考虑,分别如下所述；

K-means算法思考

1. K值的选择： k 值对最终结果的影响至关重要，而它却必须要预先给定。给定合适的 k 值，需要先验知识，凭空估计很困难，或者可能导致效果很差。

2. 异常点的存在：K-means算法在迭代的过程中使用所有点的均值作为新的质点(中心点)，如果簇中存在异常点，将导致均值偏差比较严重。 比如一个簇中有2、4、6、8、100五个数据，那么新的质点为24，显然这个质点离绝大多数点都比较远；在当前情况下，使用中位数6可能比使用均值的想法更好，使用中位数的聚类方式叫做K-Mediods聚类(K中值聚类)。

3. 初值敏感：K-means算法是初值敏感的，选择不同的初始值可能导致不同的簇划分规则。为了避免这种敏感性导致的最终结果异常性，可以采用初始化多套初始节点构造不同的分类规则，然后选择最优的构造规则。针对这点后面因此衍生了：二分K-Means算法、K-Means++算法、K-Means||算法、Canopy算法等。

常用的几种距离计算方法

通常情况下，在聚类算法中，样本的属性主要由其在特征空间中的相对距离来表示。
这就使得距离这个概念，对于聚类非常重要。以下是几种最常见的距离计算方法。

• 欧式距离（又称 2-norm 距离）
  在欧几里德空间中，点 x=(x1,…,xn) 和 y=(y1,…,yn) 之间的欧氏距离为：
  
  在欧几里德度量下，两点之间线段最短。

• 余弦距离（又称余弦相似性）
  两个向量间的余弦值可以通过使用欧几里德点积公式求出：
  a⋅b=∥a∥∥b∥cosθ
  所以：
  
  也就是说，给定两个属性向量 A 和 B，其余弦距离（也可以理解为两向量夹角的余弦）由点积和向量长度给出，如下所示：
  
  这里的 Ai 和 Bi 分别代表向量 A 和 B 的各分量。

• 曼哈顿距离（Manhattan Distance, 又称 1-norm 距离）
  曼哈顿距离的定义，来自于计算在规划为方型建筑区块的城市（如曼哈顿）中行车的最短路径。
  假设一个城市是完备的块状划分，从一点到达另一点必须要按照之间所隔着的区块的边缘走，没有其他捷径（如下图）：
  
  因此，曼哈顿距离就是：在直角坐标系中，两点所形成的线段对 x 和 y 轴投影的长度总和。
  从点 (x1,y1) 到点 (x2,y2)，曼哈顿距离为：
  |x1−x2|+|y1−y2|

KMean 简单编码样例

import matplotlib.pyplot as plt
from sklearn.datasets import make_blobs  # 导入产生模拟数据的方法
from sklearn.cluster import KMeans

# 1. 产生模拟数据
k = 5
X, Y = make_blobs(n_samples=1000, n_features=2, centers=k, random_state=1)

# 2. 模型构建
km = KMeans(n_clusters=k, init='k-means++', max_iter=30)
km.fit(X)

# 获取簇心
centroids = km.cluster_centers_
# 获取归集后的样本所属簇对应值
y_kmean = km.predict(X)

# 呈现未归集前的数据
plt.scatter(X[:, 0], X[:, 1], s=50)
plt.yticks(())
plt.show()

plt.scatter(X[:, 0], X[:, 1], c=y_kmean, s=50, cmap='viridis')
plt.scatter(centroids[:, 0], centroids[:, 1], c='black', s=100, alpha=0.5)
plt.show()

代码运行结果：

归集后的数据图：

KMeans类的主要参数有：

1. n_clusters: 即k值，一般需要多试一些值以获得较好的聚类效果。k值好坏的评估标准在下面会讲。
2. max_iter： 最大的迭代次数，一般如果是凸数据集的话可以不管这个值，如果数据集不是凸的，可能很难收敛，此时可以指定最大的迭代次数让算法可以及时退出循环。
3. n_init：用不同的初始化质心运行算法的次数。由于K-Means是结果受初始值影响的局部最优的迭代算法，因此需要多跑几次以选择一个较好的聚类效果，默认是10，一般不需要改。如果你的k值较大，则可以适当增大这个值。
4. init： 即初始值选择的方式，可以为完全随机选择’random’,优化过的’k-means++’或者自己指定初始化的k个质心。一般建议使用默认的’k-means++’。
5. algorithm：有“auto”, “full” or “elkan”三种选择。”full”就是我们传统的K-Means算法， “elkan”是elkan K-Means算法。默认的”auto”则会根据数据值是否是稀疏的，来决定如何选择”full”和“elkan”。一般数据是稠密的，那么就是 “elkan”，否则就是”full”。一般来说建议直接用默认的”auto”
6. random_state:表示产生随机数的方法。默认情况下的缺省值为None，此时的随机数产生器是np.random所使用的RandomState实例。

KMean算法的算法优缺点与适用场景

优点：

• 理解容易，聚类效果不错；
• 处理大数据集的时候，该算法可以保证较好的伸缩性和高效率；
• 当簇近似高斯分布的时候，效果非常不错。

缺点：

• K值是用户给定的，在进行数据处理前，K值是未知的，给定合适的 k 值，需要先验知识，凭空估计很困难，或者可能导致效果很差。
• 对初始簇中心点是敏感的。
• 不适合发现非凸形状的簇或者大小差别较大的簇。
• 特殊值(离群值或称为异常值)对模型的影响比较大。

KMean 衍生算法

KMeans 初始值敏感示例图

二分K-Means算法

• 解决K-Means算法对初始簇心比较敏感的问题，二分K-Means算法是一种弱化初始质心的一种算法，具体思路步骤如下：

  1. 将所有样本数据作为一个簇放到一个队列中；
  2. 从队列中选择一个簇进行K-means算法划分（第一次迭代时就是相当与将所有样本进行K=2的划分），划分为两个子簇，并将子簇添加到队列中循环迭代第二步操作，直到中止条件达到(聚簇数量、最小平方误差、迭代次数等)
  3. 队列中的簇就是最终的分类簇集合。

• 从队列中选择划分聚簇的规则一般有两种方式；分别如下：
  1. 对所有簇计算误差和SSE(SSE也可以认为是距离函数的一种变种)，选择SSE最大的聚簇进行划分操作(优选这种策略)；
  

  2. 选择样本数据量最多的簇进行划分操作。

K-Means++算法

• 解决K-Means算法对初始簇心比较敏感的问题，K-Means++算法和K-Means算法的区别主要在于初始的K个中心点的选择方面，K-Means算法使用随机给定的方式，K-Means++算法采用下列步骤给定K个初始质点：
  1. 从数据集中任选一个节点作为第一个聚类中心；
  2. 对数据集中的每个点x，计算x到所有已有聚类中心点的距离和D(X)，基于D(X)采用线性概率选择出下一个聚类中心点(距离较远的一个点成为新增的一个聚类中心点而不是最远的一个点是由于最远点可能为异常点，这里的选取规则是计算出M个距离团较远的点，然后随机选择出一点)；
  3. 重复步骤2直到找到k个聚类中心点。

缺点：
由于聚类中心点选择过程中的内在有序性，在扩展方面存在着性能方面的问题(第k个聚类中心点的选择依赖前k-1个聚类中心点的值)。

K-Means||算法

解决K-Means++算法缺点而产生的一种算法；
主要思路是改变每次遍历时候的取样规则，并非按照K-Means++算法每次遍历只获取一个样本，
而是每次获取K个样本，重复该取样操作O(logn)次，然后再将这些抽样出来的样本聚类出K个点，
最后使用这K个点作为K-Means算法的初始聚簇中心点。
实践证明：一般5次重复采用就可以保证一个比较好的聚簇中心点。

Canopy算法

Canopy算法属于一种“粗”聚类算法，执行速度较快，但精度较低，算法执行
步骤如下：

1. 给定样本列表L=x 1 ,x, 2 …,x m 以及先验值r 1 和r 2 (r 1 >r 2 )
2. 从列表L中获取一个节点P，计算P到所有聚簇中心点的距离(如果不存在聚簇中心，那么此时点P形成一个新的聚簇)，并选择出最小距离D(P,a j )
3. 如果距离D小于r1，表示该节点属于该聚簇，添加到该聚簇列表中
4. 如果距离D小于r2，表示该节点不仅仅属于该聚簇，还表示和当前聚簇中心点非常近，所以将该聚簇的中心点设置为该簇中所有样本的中心点，并将P从列表L中删除
5. 如果距离D大于r1，那么节点P形成一个新的聚簇
6. 直到列表L中的元素数据不再有变化或者元素数量为0的时候，结束循环操作。
   
   Canopy算法常用应用场景

• 由于K-Means算法存在初始聚簇中心点敏感的问题，常用使用Canopy+K-Means算法混合形式进行模型构建
• 先使用canopy算法进行“粗”聚类得到K个聚类中心点
• K-Means算法使用Canopy算法得到的K个聚类中心点作为初始中心点，进行“细”聚类

优点：

• 执行速度快(先进行了一次聚簇中心点选择的预处理)
• 不需要给定K值，应用场景多
• 能够缓解K-Means算法对于初始聚类中心点敏感的问题

Mini Batch K-Means算法

Mini Batch K-Means算法是K-Means算法的一种优化变种，采用小规模的数据子集(每次训练使用的数据集是在训练算法的时候随机抽取的数据子集)减少计算时间，同时试图优化目标函数；
Mini Batch K-Means算法可以减少K-Means算法的收敛时间，而且产生的结果效果只是略差于标准K-Means算法算法步骤如下：

1. 首先抽取部分数据集，使用K-Means算法构建出K个聚簇点的模型；
2. 继续抽取训练数据集中的部分数据集样本数据，并将其添加到模型中，分配给距离最近的聚簇中心点；
3. 更新聚簇的中心点值；
4. 循环迭代第二步和第三步操作，直到中心点稳定或者达到迭代次数，停止计算操作。

K-Means和Mini Batch K-Means算法比较案例

基于scikit包中的创建模拟数据的API创建聚类数据，使用K-means算法和MiniBatch K-Means算法对数据进行分类操作，比较这两种算法的聚类效果以及聚类的消耗时间长度。

import time
import numpy as np
import matplotlib.pyplot as plt
import matplotlib as mpl
from sklearn.cluster import MiniBatchKMeans, KMeans
from sklearn.metrics.pairwise import pairwise_distances_argmin
from sklearn.datasets.samples_generator import make_blobs

# 设置属性防止中文乱码
mpl.rcParams['font.sans-serif'] = [u'SimHei']
mpl.rcParams['axes.unicode_minus'] = False

# 初始化三个中心
centers = [[1, 1], [-1, -1], [1, -1]]
clusters = len(centers)  # 聚类的数目为3
# 产生50000组二维的数据，中心是意思三个中心点，标准差是.7
total_samples = 50000
X, Y = make_blobs(n_samples=total_samples, centers=centers, cluster_std=0.7, random_state=28)

# 构建kmeans算法
k_means = KMeans(init='k-means++', n_clusters=clusters, random_state=28)
t0 = time.time()  # 当前时间
k_means.fit(X)  # 训练模型
km_batch = time.time() - t0  # 使用kmeans训练数据的消耗时间
print("K-Means算法模型训练消耗时间:%.4fs" % km_batch)

# 构建MiniBatchKMeans算法
batch_size = 100
mbk = MiniBatchKMeans(init='k-means++', n_clusters=clusters, batch_size=batch_size, random_state=28)
t0 = time.time()
mbk.fit(X)
mbk_batch = time.time() - t0
print("Mini Batch K-Means算法模型训练消耗时间:%.4fs" % mbk_batch)

# 预测结果
km_y_hat = k_means.predict(X)
mbkm_y_hat = mbk.predict(X)

# print(km_y_hat[:10])
# print(mbkm_y_hat[:10])
# print(k_means.cluster_centers_)
# print(mbk.cluster_centers_)

#获取聚类中心点并聚类中心点进行排序
k_means_cluster_centers = k_means.cluster_centers_  # 输出kmeans聚类中心点
mbk_means_cluster_centers = mbk.cluster_centers_  # 输出mbk聚类中心点
# print("K-Means算法聚类中心点:\ncenter=", k_means_cluster_centers)
# print("Mini Batch K-Means算法聚类中心点:\ncenter=", mbk_means_cluster_centers)
# 方便后面画图
order = pairwise_distances_argmin(k_means_cluster_centers, mbk_means_cluster_centers)

# 画图
plt.figure(figsize=(12, 6), facecolor='w')
plt.subplots_adjust(left=0.05, right=0.95, bottom=0.05, top=0.9)
cm = mpl.colors.ListedColormap(['#FFC2CC', '#C2FFCC', '#CCC2FF'])
cm2 = mpl.colors.ListedColormap(['#FF0000', '#00FF00', '#0000FF'])
# 子图1：原始数据
plt.subplot(221)
plt.scatter(X[:, 0], X[:, 1], c=Y, s=6, cmap=cm, edgecolors='none')
plt.title(u'原始数据分布图')
plt.xticks(())
plt.yticks(())
plt.grid(True)
# 子图2：K-Means算法聚类结果图
plt.subplot(222)
plt.scatter(X[:, 0], X[:, 1], c=km_y_hat, s=6, cmap=cm, edgecolors='none')
plt.scatter(k_means_cluster_centers[:, 0], k_means_cluster_centers[:, 1], c=range(clusters), s=60, 
           cmap=cm2,edgecolors='none')
plt.title(u'K-Means算法聚类结果图')
plt.xticks(())
plt.yticks(())
plt.text(-3.8, 3, 'train time: %.2fms' % (km_batch * 1000))
plt.grid(True)
# 子图三Mini Batch K-Means算法聚类结果图
plt.subplot(224)
plt.scatter(X[:, 0], X[:, 1], c=mbkm_y_hat, s=6, cmap=cm, edgecolors='none')
plt.scatter(mbk_means_cluster_centers[:, 0], mbk_means_cluster_centers[:, 1], c=range(clusters), s=60, 
       cmap=cm2, edgecolors='none')
plt.title(u'Mini Batch K-Means算法聚类结果图')
plt.xticks(())
plt.yticks(())
plt.text(-3.8, 3, 'train time: %.2fms' % (mbk_batch * 1000))
plt.grid(True)

#
different = list(map(lambda x: (x != 0) & (x != 1) & (x != 2), mbkm_y_hat))
for k in range(clusters):
    different += ((km_y_hat == k) != (mbkm_y_hat == order[k]))
identic = np.logical_not(different)
different_nodes = len(list(filter(lambda x: x, different)))

plt.subplot(223)
# 两者预测相同的
plt.plot(X[identic, 0], X[identic, 1], 'w', markerfacecolor='#bbbbbb', marker='.')
# 两者预测不相同的
plt.plot(X[different, 0], X[different, 1], 'w', markerfacecolor='m', marker='.')
plt.title(u'Mini Batch K-Means和K-Means算法预测结果不同的点')
plt.xticks(())
plt.yticks(())
plt.text(-3.8, 2, 'total nodes %d and different nodes: %d' % (total_samples, different_nodes))

plt.show()

• 注：主要整理自
  北风网机器学习教程
  李烨机器学习极简入门教程