k均值聚类算法（非常详细，附带实例）

k 均值聚类算法是一种迭代求解的聚类分析算法。

在各种聚类算法中，k 均值聚类算法可以说是最简单的。但是简单不代表不好用，k 均值聚类算法绝对是在聚类中用的最多的算法。

k 均值聚类算法的工作原理是，假设数据集中的样本因为特征不同，像小沙堆一样散布在地面上，k 均值算法会在小沙堆上插上旗子。而第一遍插的旗子并不能很完美地代表沙堆的分布，所以 k 均值还要继续，让每个旗子能够插到每个沙堆最佳的位置上，也就是数据点的均值上，这也是k均值聚类算法名字的由来。接下来一直重复上述的动作，直到找不出更好的位置。

k均值聚类算法步骤

k 均值聚类算法的步骤如下：

输入 k 的值，即我们希望将数据集经过聚类得到 k 分组；
从数据集中随机选择 k 个数据点作为初始聚类中心，对任意一个样本点，求其到 k 个聚类中心的距离，将样本点归类到距离最小的中心的聚类，如此迭代 n 次；
每次迭代过程中，利用均值等方法更新各个聚类的中心点；
对 k 个聚类中心，利用步骤 2 和步骤 3 迭代更新后，如果位置点变化很小，则认为达到稳定状态，对不同的聚类块和聚类中心可选择不同的颜色标注。

在实际应用中，由于 k 均值一般用于数据预处理或者用于辅助分类贴标签。所以 k 的值一般不会设置很大。

对于 k 值的选取，一般采用以下两种方法。

1) 手肘法

手肘法的核心指标是 SSE（sum of the squared errors，误差平方和）。聚类数 k 增大，数据划分就会更精细，每个簇的聚合程度也会提高，从而 SSE 会逐渐变小：

当 k 小于真实聚类数时，k 的增大会增加每个簇的聚合程度，因此 SSE 的下降幅度会很大；
当 k 到达真实聚类数时，再增加 k 所得到的聚合程度会迅速变小，所以 SSE 的下降幅度会骤减，然后随着 k 值的继续增大而趋于平缓。

由此可见，SSE 和 k 的关系图是一个手肘的形状，而这个肘部对应的 k 值就是数据的真实聚类数。

具体做法是让 k 从 1 开始取值直到取到你认为合适的上限，对每个 k 值进行聚类并记下对应的 SSE，然后画出 k 和 SSE 的关系图，最后选取肘部对应的 k 作为最佳聚类数。

对葡萄酒数据集 wine.data，用 sklearn 库中自带的 k 均值算法对 k 值的选取进行可视化操作，如下图所示。

图 1 手肘图

2) 轮廓系数法

轮廓系数（silhouette coefficient）是簇的密集与分散程度的评价指标：

计算样本 i 到同一类中其他样本的平均距离 ai。如果 ai 越小，则说明样本 i 与同类中其他样本的距离越近，即越相似。称 ai 为样本 i 的类别内不相似度。
计算样本 i 到其他类别的所有样本的平均距离 bi。如果 bi 越大，说明样本i与其他类之间距离越远，即越不相似。称 bi 为样本 i 与其他类之间的不相似度。

轮廓系数的值在 -1 和 1 之间，该值越接近于 1，簇越紧凑，聚类越好。当轮廓系数接近 1 时，簇内紧凑，并远离其他簇。其中，轮廓系数的计算如下所示：

k均值聚类算法优缺点

经过以上分析，可总结出k均值聚类算法的优缺点。

k 均值聚类算法的优点主要表现在：

k 均值聚类算法原理比较简单，实现起来也很容易，收敛速度较快；
聚类效果相对于其他聚类算法来说较好，算法的可解释度比较强；
参数较少，主要需要调参的参数仅仅是簇数 k。

k均值聚类算法的缺点主要表现在：

不适用字符串等非数值型数据。k 均值聚类算法基于均值计算，首先要求簇的平均值可以被定义和使用。
k 均值的第一步是确定 k（要生成的簇的数目），对于不同的初始值 k，可能会导致不同结果。
应用数据集存在局限性，适用于球状或集中分布数据，不适用于特殊情况数据。

k均值聚类算法实战

下面直接通过实例来演示 k 均值的实战过程。

【实例】利用 k 均值聚类算法对给定篮球运动员比赛数据进行聚类。

from sklearn.cluster import Birch　#从sklearn.cluster机器学习聚类包中导入Birch聚类
from sklearn.cluster import KMeans　#从sklearn.cluster机器学习聚类包中导入KMeans聚类
"""
数据集:
X表示二维矩阵数据,篮球运动员比赛数据
总共20行,每行两列数据
第一列表示球员每分钟助攻数:x1
第二列表示球员每分钟得分数:x2
"""
X = [[0.0888,0.5885],[0.1399,0.8291],[0.0747,0.4974],[0.0983,0.5772],[0.1276,0.5703],
[0.1671,0.5835],[0.1906,0.5276],[0.1061,0.5523],[0.2446,0.4007],[0.1670,0.4770],
[0.2485,0.4313],[0.1227,0.4909],[0.1240,0.5668],[0.1461,0.5113],[0.2315,0.3788],
[0.0494,0.5590],[0.1107,0.4799],[0.2521,0.2735],[0.1007,0.6318],[0.1067,0.4326],
[0.1456,0.8280]
]
"""
k均值聚类
clf = KMeans(n_clusters = 3)表示类簇数为3,聚成3类数据,clf即赋值为KMeans
y_pred = clf.fit_predict(X)载入数据集X,并且将聚类的结果赋值给y_pred
"""
clf = KMeans(n_clusters = 3)　#聚类算法,参数n_clusters = 3,聚成3类
y_pred = clf.fit_predict(X)　#直接对数据进行聚类,聚类不需要进行预测
#输出完整k均值函数,包括很多省略参数
print('k均值模型:\n',clf)
#输出聚类预测结果,20行数据,每个y_pred对应X一行或一个球员,聚成3类,类标为0、1、2
print('聚类结果:\n',y_pred)

"""
可视化绘图
Python导入Matplotlib包,专门用于绘图
import matplotlib.pyplot as plt此处as相当于重命名,plt用于显示图像
"""
import numpy as np
import matplotlib.pyplot as plt
% matplotlib inline

plt.rcParams['font.sans-serif'] = ['SimHei']　　#显示中文
#获取第一列和第二列数据使用for循环获取n[0]表示X第一列
x1 = [n[0]for n in X]
x2 = [n[1]for n in X]
#绘制散点图——参数:x横轴y纵轴c = y_pred聚类预测结果marker类型o表示圆点 * 表示
#星形x表示点
plt.scatter(x1,x2,c = y_pred,marker = 'x')
#绘制标题
plt.title("k均值篮球数据")
#绘制x轴和y轴坐标
plt.xlabel("x1")
plt.ylabel("x2")
#显示图形
plt.show()

运行程序，输出如下：

k均值模型:
KMeans(algorithm = 'auto',copy_x = True,init = 'k-means ++ ',max_iter = 300,
    n_clusters = 3,n_init = 10,n_jobs = 1,precompute_distances = 'auto',
    random_state = None,tol = 0.0001,verbose = 0)
聚类结果:
[0 1 0 0 0 0 0 0 2 0 2 0 0 0 2 0 0 2 0 0 1]

效果如下图所示：

图 3 篮球数据聚类效果

小批量k均值算法

小批量 k 均值是 k 均值算法的一个变体，它使用小批量（mini-batch）来减少计算时间，同时仍然尝试优化相同的目标函数。

小批量是输入数据的子集，在每次训练迭代中随机抽样。这些小批量大大减少了融合到本地解决方案所需的计算量。与其他降低 k 均值收敛时间的算法相反，小批量 k 均值产生的结果通常只比标准算法略差。

该算法在两个主要步骤之间进行迭代：

第一步，从数据集中随机抽取 b 样本，形成一个 mini-batch，然后将它们分配到最近的质心（centroid）；
第二步，更新质心。

与 k 均值相反，这是在每个样本的基础上完成的。对于 mini-batch 中的每个样本，通过取样本的流平均值（streaming average）和分配给该质心的所有先前样本来更新分配的质心。这具有随时间降低质心的变化率的效果。执行这些步骤直到达到收敛或达到预定次数的迭代。

【实例】 k 均值聚类和小批量 k 均值聚类对比实例。

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

# 产生样本数据
np.random.seed(0)
batch_size = 45
centers = [[1, 1], [-1, -1], [1, -1]]  # 三种聚类的中心
n_clusters = len(centers)
X, labels_true = make_blobs(n_samples = 3000, centers = centers, cluster_std = 0.7)  # 生成样本随机数

# k 均值聚类
k_means = KMeans(init = 'k-means++', n_clusters = 3, n_init = 10)
begin_time = time.time()  # 记录训练开始时间
k_means.fit(X)
t_batch = time.time() - begin_time  # 记录训练用时
print('k 均值聚类时长：', t_batch)

# 小批量 k 均值聚类
# batch_size 为每次更新使用的样本数
mbk = MiniBatchKMeans(init = 'k-means++', n_clusters = 3, batch_size = batch_size,
                     n_init = 10, max_no_improvement = 10, verbose = 0)
begin_time = time.time()  # 记录训练开始时间
mbk.fit(X)
t_mini_batch = time.time() - begin_time  # 记录训练用时
print('小批量 k 均值聚类时长：', t_mini_batch)

# 结果可视化
fig = plt.figure(figsize = (16, 6))  # 窗口大小
fig.subplots_adjust(left = 0.02, right = 0.98, bottom = 0.05, top = 0.9)  # 窗口四周留白
colors = ['#4EACC5', '#FF9C34', '#4E9A06']  # 三种聚类的颜色

# 绘制 k-Means
ax = fig.add_subplot(1, 3, 1)
for k, col in zip(range(n_clusters), colors):
    my_members = k_means.labels_ == k
    cluster_center = k_means.cluster_centers_[k]
    ax.plot(X[my_members, 0], X[my_members, 1], 'w', markerfacecolor = col, marker = '.')
    ax.plot(cluster_center[0], cluster_center[1], 'o', markerfacecolor = col, markeredgecolor = 'k', markersize = 6)
ax.set_title('k-Means')
ax.set_xticks(())
ax.set_yticks(())
plt.text(-3.5, 1.8, 'train time: %.2f s\ninertia: %f' % (t_batch, k_means.inertia_))
plt.rcParams['font.sans-serif'] = ['SimHei']  # 显示中文

# 绘制 MiniBatchKMeans
ax = fig.add_subplot(1, 3, 2)
for k, col in zip(range(n_clusters), colors):
    my_members = mbk_means_labels == k
    cluster_center = mbk_means_cluster_centers_[k]
    ax.plot(X[my_members, 0], X[my_members, 1], 'w', markerfacecolor = col, marker = '.')
    ax.plot(cluster_center[0], cluster_center[1], 'o', markerfacecolor = col, markeredgecolor = 'k', markersize = 6)
ax.set_title('MiniBatchKMeans')
ax.set_xticks(())
ax.set_yticks(())
plt.text(-3.5, 1.8, 'train time: %.2f s\ninertia: %f' % (t_mini_batch, mbk.inertia_))

# 初始化两次结果
different = (mbk_means_labels == 4)
ax = fig.add_subplot(1, 3, 3)
for k in range(n_clusters):
    different += ((k_means_labels == k) != (mbk_means_labels == order[k]))
    # 向量取反，也就是聚类结果相同设置为 true，聚类结果不相同设置为 false
    indic = np.logical_not(different)
    # 绘制聚类结果相同的样本点
    ax.plot(X[indic, 0], X[indic, 1], 'w', markerfacecolor = '#bbbbbb', marker = '.')
    ax.plot(X[different, 0], X[different, 1], 'w', markerfacecolor = 'm', marker = '.')
ax.set_title('差别')
ax.set_xticks(())
ax.set_yticks(())
plt.show()