K-Means聚类算法

算法思想

K-means算法是一种迭代求解的聚类算法，将数据集中的n个样本划分为K个簇（聚类）。
每个对象到簇中心的距离之和最小。
簇内的对象相似度较高，簇间的对象相似度较低。

算法步骤

1. 选择K个初始聚类中心

随机选择K个样本作为初始聚类中心。

选择对最终的聚类结果有一定影响，因此在实际应用中，通常会采用一些启发式的方法来选择较好的初始聚类中心，如K-means++算法

2. 计算每个样本到聚类中心的距离

对于每个样本，计算其到K个聚类中心的距离，将其划分到距离最近的聚类中心所在的簇中。

通常使用欧式距离：$d(xi, c_j) = \sqrt{\sum{k=1}^{n}(x{ik}-c{jk})^2}$

3. 更新聚类中心

对于每个聚类，重新计算其聚类中心，新的聚类中心是该聚类内所有数据点的均值：$cj = \dfrac{1}{|S_j|}\sum{x_i\in S_j}x_i$

4. 迭代

重复步骤2和3，直到聚类中心不再发生显著变化或者达到最大迭代次数。

算法优缺点

优点：逻辑简单、易于实现、收敛速度快

缺点：需要事先确定聚类数目K，对初始聚类中心敏感，可能收敛到局部最优解

K-Means 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
import random

def k_means(data, k=3, max_iter=100):
    """K-means 聚类算法
    
    Args:
        data: 数据集，list[element]，element是一个list[float]
        k: 聚类数
        max_iter: 最大迭代次数
    """
    # 初始化聚类中心
    centers = random.sample(data, k)
    # 初始化聚类结果
    clusters = [[] for _ in range(k)]
    # 迭代聚类
    for iter in range(max_iter):
        # 分配数据到最近的聚类中心
        for element in data: # 对于每个数据
            min_dist = float('inf') # 最小距离
            min_idx = -1 # 最近聚类
            for i, center in enumerate(centers):
                dist = sum((x-y)**2 for x, y in zip(element, center)) # 计算距离
                if dist < min_dist:
                    min_dist = dist
                    min_idx = i
            clusters[min_idx].append(element)
        # 更新聚类中心
        new_centers = [None] * k
        for i, cluster in enumerate(clusters):
            new_centers[i] = [sum(x)/len(cluster) for x in zip(*cluster)]
        # 判断是否收敛：中心点是否变化小于eps
        eps = 1e-6
        fl = all((sum((x-y)**2 for x, y in zip(a, b)) < eps) for a, b in zip(centers, new_centers))
        if fl or iter == max_iter-1:
            break
        centers = new_centers
        clusters = [[] for _ in range(k)]
    return clusters

# 测试
data = [[random.random() for _ in range(2)] for _ in range(1000)]
clusters = k_means(data, 3)

# 结果可视化
import matplotlib.pyplot as plt
colors = ['r', 'g', 'b', 'y', 'c', 'm']
for i, cluster in enumerate(clusters):
    for element in cluster:
        plt.scatter(element[0], element[1], c=colors[i])
plt.show()

k_means

K-Means++算法

K-Means++算法是K-means算法的改进，优化了初始聚类中心的选择，使得初始聚类中心更有代表性，收敛速度更快。

逐个选取k个簇中心，且离其它簇中心越远的样本点越有可能被选为下一个簇中心

算法步骤（选择K个初始聚类中心的过程）

1. 选择第一个簇中心

随机选择一个样本作为第一个簇中心

2. 选择下一个簇中心

对于样本x，计算其到已有簇中心的最短距离，记为$D(x)$，选取x作为下一个簇中心的概率为$\dfrac{D(x)^2}{\sum_{x\in X}D(x)^2}$

3. 迭代

重复步骤2，直到选取k个簇中心

实现

1
2
3
4
5
6
7
# 选择第一个聚类中心
centers = [random.choice(data)]
# 选择其他聚类中心
for _ in range(k-1):
    dists = [min(sum((x-y)**2 for x, y in zip(element, center)) for center in centers) for element in data]
    probs = [dist**2/sum(dists) for dist in dists]
    centers.append(random.choices(data, probs)[0])