本文内容、数据参考周志华《机器学习》，代码部分为个人实现，如有错误还请指出。
K-means（K均值）算法是最简单的一种聚类算法，它期望最小化平方误差
E = ∑ i = 1 k ∑ x ∈ C i ∣ ∣ x − μ i ∣ ∣ 2 2 E=sumlimits_{i=1}^ksumlimits_{xin C_i}||pmb x-pmbmu_i||_2^2 E=i=1∑k​x∈Ci​∑​∣∣xxx−μ​μ​​μi​∣∣22​
其中 μ i = 1 ∣ C i ∣ ∑ x ∈ C i x pmbmu_i=frac{1}{|C_i|}sum_{x in C_i}pmb x μ​μ​​μi​=∣Ci​∣1​∑x∈Ci​​xxx是簇(cluster) C i C_i Ci​的均值向量， ∣ ∣ x − μ i ∣ ∣ 2 ||pmb x-pmbmu_i||_2 ∣∣xxx−μ​μ​​μi​∣∣2​即一般意义下向量的模长。
K-means算法的一般步骤如下：

输入：样本集 D = { x 1 , x 2 , . . . , x m } ; D={pmb x_1,pmb x_2,...,pmb x_m}; D={xxx1​,xxx2​,...,xxxm​};聚类簇数$k.$
过程：
   1 : 从 D 中 随 机 选 择 k 个 样 本 作 为 初 始 均 值 向 量 { μ 1 , μ 2 , . . . , μ k } 1:从D中随机选择k个样本作为初始均值向量{pmb mu_1, pmb mu_2,...,pmb mu_k}   1:从D中随机选择k个样本作为初始均值向量{μ​μ​​μ1​,μ​μ​​μ2​,...,μ​μ​​μk​}
$2:\text{repeat}$
   3 : 令 C i = ∅ ( 1 ≤ i ≤ k ) 3:hspace{0.5cm}令C_i=varnothing(1le i le k)   3:令Ci​=∅(1≤i≤k)
$4:\text{for}j=1,2,...,m\text{do}$
   5 : 计 算 样 本 x j 与 各 均 值 向 量 μ i ( 1 ≤ i ≤ k ) 的 距 离 ： d j i = ∣ ∣ x − μ i ∣ ∣ 2 ; 5:hspace{1.0cm}计算样本pmb x_j与各均值向量pmb mu_i(1le i le k)的距离：d_{ji}=||pmb x-pmbmu_i||_2;   5:计算样本xxxj​与各均值向量μ​μ​​μi​(1≤i≤k)的距离：dji​=∣∣xxx−μ​μ​​μi​∣∣2​;
   6 : 根 据 距 离 最 近 的 均 值 向 量 确 定 x j 的 簇 标 记 : λ j = argmin i ∈ { 1 , 2 , . . . , k } d j i ; 6:hspace{1.0cm}根据距离最近的均值向量确定x_j的簇标记:lambda_j=texttt{argmin}_{iin {1,2,...,k}}d_{ji};   6:根据距离最近的均值向量确定xj​的簇标记:λj​=argmini∈{1,2,...,k}​dji​;
   7 : 将 样 本 x j 划 入 相 应 的 簇 : C λ j = C λ j ∪ { x j } ; 7:hspace{1.0cm}将样本pmb x_j划入相应的簇:C_{lambda_j}=C_{lambda_j}cup{pmb x_j};   7:将样本xxxj​划入相应的簇:Cλj​​=Cλj​​∪{xxxj​};
$8:\text{end for}$
$9:\text{for}i=1,2,...,k\text{do}$
10 : 计 算 新 均 值 向 量 : μ i ′ = 1 ∣ C i ∣ ∑ x ∈ C i x ; 10:hspace{1.0cm}计算新均值向量:pmb mu_i^{'}=frac{1}{|C_i|}sum_{x in C_i}pmb x; 10:计算新均值向量:μ​μ​​μi′​=∣Ci​∣1​∑x∈Ci​​xxx;
11 : if μ i ′ ≠ μ i then 11:hspace{1.0cm}texttt{if} hspace{0.2cm}pmb mu_i^{'}neqpmb mu_ihspace{0.2cm}texttt{then} 11:ifμ​μ​​μi′​​=μ​μ​​μi​then
12 : 将 当 前 均 值 向 量 μ i 更 新 为 μ i ′ 12:hspace{1.5cm}将当前均值向量pmb mu_i更新为pmb mu_i^{'} 12:将当前均值向量μ​μ​​μi​更新为μ​μ​​μi′​
$13:\text{else}$
$14:保持当前均值向量不变$
$15:\text{end if}$
$16:\text{end for}$
$17:\text{until}当前均值向量均未更新$
输出:簇划分 C = { C 1 , C 2 , . . . , C k } mathcal{C}={C_1,C_2,...,C_k} C={C1​,C2​,...,Ck​}

注：为避免运行时间过长，通常设置一个最大运行轮数或最小调整幅度阈值，若到达最大轮数或调整幅度小于阈值，则停止运行。

下面我们用python来实现一下K-means算法：我们先尝试手动实现这个算法，再用sklearn库中的KMeans类来实现。数据我们采用《机器学习》的西瓜数据(P202表9.1):

# 下面的内容保存在 melons.txt 中
# 第一列为西瓜的密度；第二列为西瓜的含糖率。我们要把这30个西瓜分为3类
0.697 0.460
0.774 0.376
0.634 0.264
0.608 0.318
0.556 0.215
0.403 0.237
0.481 0.149
0.437 0.211
0.666 0.091
0.243 0.267
0.245 0.057
0.343 0.099
0.639 0.161
0.657 0.198
0.360 0.370
0.593 0.042
0.719 0.103
0.359 0.188
0.339 0.241
0.282 0.257
0.748 0.232
0.714 0.346
0.483 0.312
0.478 0.437
0.525 0.369
0.751 0.489
0.532 0.472
0.473 0.376
0.725 0.445
0.446 0.459

手动实现

我们用到的库有matplotlib和numpy，如果没有需要先用pip安装一下。

import random
import numpy as np
import matplotlib.pyplot as plt

下面定义一些数据：

k = 3 # 要分的簇数
rnd = 0 # 轮次，用于控制迭代次数（见上文）
ROUND_LIMIT = 100 # 轮次的上限
THRESHOLD = 1e-10 # 单轮改变距离的阈值，若改变幅度小于该阈值，算法终止
melons = [] # 西瓜的列表
clusters = [] # 簇的列表，clusters[i]表示第i簇包含的西瓜

从melons.txt读取数据，保存在列表中：

f = open('melons.txt', 'r')
for line in f:
	# 把字符串转化为numpy中的float64类型
    melons.append(np.array(line.split(' '), dtype = np.string_).astype(np.float64))

从$m$个数据中随机挑选出$k$个，对应上面算法的第$1$行：

# random的sample函数从列表中随机挑选出k个样本（不重复）。我们在这里把这些样本作为均值向量
mean_vectors = random.sample(melons, k)

下面是算法的主要部分。

# 这个while对应上面算法的2-17行
while True:
    rnd += 1 # 轮次增加
    change = 0 # 把改变幅度重置为0
    
	# 清空对簇的划分，对应上面算法的第3行
    clusters = []
    for i in range(k):
        clusters.append([])
    # 这个for对应上面算法的4-8行
    for melon in melons:
    	'''
    	argmin 函数找出容器中最小的下标，在这里这个目标容器是
    	list(map(lambda vec: np.linalg.norm(melon - vec, ord = 2), mean_vectors)),
    	它表示melon与mean_vectors中所有向量的距离列表。
    	(numpy.linalg.norm计算向量的范数,ord = 2即欧几里得范数，或模长)
    	'''
        c = np.argmin(
            list(map( lambda vec: np.linalg.norm(melon - vec, ord = 2), mean_vectors))
        )

        clusters[c].append(melon)
	
	# 这个for对应上面算法的9-16行
    for i in range(k):
    	# 求每个簇的新均值向量
        new_vector = np.zeros((1,2))
        for melon in clusters[i]:
            new_vector += melon
        new_vector /= len(clusters[i])
        
        # 累加改变幅度并更新均值向量
        change += np.linalg.norm(mean_vectors[i] - new_vector, ord = 2)
        mean_vectors[i] = new_vector
	# 若超过设定的轮次或者变化幅度<预先设定的阈值，结束算法
    if rnd > ROUND_LIMIT or change < THRESHOLD:
        break

print('最终迭代%d轮'%rnd)

最后我们绘图来观察一下划分的结果：

colors = ['red', 'green', 'blue']

# 每个簇换一下颜色，同时迭代簇和颜色两个列表
for i, col in zip(range(k), colors):
    for melon in clusters[i]:
    	# 绘制散点图
        plt.scatter(melon[0], melon[1], color = col)

plt.show()

划分结果（由于最开始的$k$个均值向量随机选取，每次划分的结果可能会不同）:

完整代码：

import random
import numpy as np
import matplotlib.pyplot as plt

k = 3
rnd = 0
ROUND_LIMIT = 10
THRESHOLD = 1e-10
melons = []
clusters = []

f = open('melons.txt', 'r')
for line in f:
    melons.append(np.array(line.split(' '), dtype = np.string_).astype(np.float64))

mean_vectors = random.sample(melons, k)

while True:
    rnd += 1
    change = 0
    clusters = []
    for i in range(k):
        clusters.append([])
    for melon in melons:
        c = np.argmin(
            list(map( lambda vec: np.linalg.norm(melon - vec, ord = 2), mean_vectors))
        )

        clusters[c].append(melon)

    for i in range(k):

        new_vector = np.zeros((1,2))
        for melon in clusters[i]:
            new_vector += melon
        new_vector /= len(clusters[i])

        change += np.linalg.norm(mean_vectors[i] - new_vector, ord = 2)
        mean_vectors[i] = new_vector

    if rnd > ROUND_LIMIT or change < THRESHOLD:
        break

print('最终迭代%d轮'%rnd)

colors = ['red', 'green', 'blue']

for i, col in zip(range(k), colors):
    for melon in clusters[i]:
        plt.scatter(melon[0], melon[1], color = col)

plt.show()

sklearn库中的KMeans

这种经典算法显然不需要我们反复地造轮子，被广泛使用的python机器学习库sklearn已经提供了该算法的实现。sklearn的官方文档中给了我们一个示例：

>>> from sklearn.cluster import KMeans
>>> import numpy as np
>>> X = np.array([[1, 2], [1, 4], [1, 0],
...               [10, 2], [10, 4], [10, 0]])
>>> kmeans = KMeans(n_clusters=2, random_state=0).fit(X)
>>> kmeans.labels_
array([1, 1, 1, 0, 0, 0], dtype=int32)
>>> kmeans.predict([[0, 0], [12, 3]])
array([1, 0], dtype=int32)
>>> kmeans.cluster_centers_
array([[10.,  2.],
       [ 1.,  2.]])

可以看出，X即要聚类的数据(1,2),(1,4),(1,0)等。
KMeans类的初始化参数n_clusters即簇数$k$;
random_state是用于初始化选取$k$个向量的随机数种子;
kmeans.labels_即每个点所属的簇；
kmeans.predict方法预测新的数据属于哪个簇;
kmeans.cluster_centers_返回每个簇的中心。
我们就改造一下这个简单的示例，完成对上面西瓜的聚类。

import numpy as np
import matplotlib.pyplot as plt
from sklearn.cluster import KMeans

X = []
f = open('melons.txt', 'r')
for line in f:
    X.append(np.array(line.split(' '), dtype = np.string_).astype(np.float64))
kmeans = KMeans(n_clusters = 3, random_state = 0).fit(X)

colors = ['red', 'green', 'blue']

for i, cluster in enumerate(kmeans.labels_):
    plt.scatter(X[i][0], X[i][1], color = colors[cluster])
plt.show()

运行结果如下，可以看到和我们手写的聚类结果基本一致。