KMeans 聚类算法 Python 实现与深度解析

KMeans 是一种经典的无监督学习算法，其核心目标是通过迭代优化将数据划分为 $K$ 个簇，使得簇内样本距离尽可能小，而簇间距离尽可能大 。以下将从算法原理、代码实现及结果解析三个维度进行详细阐述。

一、 问题解构与方案推演

要实现 KMeans 算法，必须遵循以下逻辑闭环：

1. 数据预处理：加载并标准化数据，消除量纲影响。
2. 初始化质心：随机选择 $K$ 个样本点作为初始聚类中心。
3. 迭代分配：计算每个样本到各质心的距离（通常为欧氏距离），将样本归入距离最近的簇 。
4. 更新质心：计算每个簇内所有样本的均值，作为新的质心。
5. 收敛判断：判断质心是否发生变化或达到最大迭代次数，若满足则结束，否则回到步骤 3 。

二、 Python 代码实现与详细解析

以下代码不依赖 sklearn 等高级库，仅使用 numpy 和 matplotlib 从零实现算法逻辑，以便深入理解其内部机制 。

1. 环境准备与数据加载

首先，我们需要生成模拟数据并进行可视化。为了让聚类效果明显，我们生成几个呈团状分布的数据点。

import numpy as np
import matplotlib.pyplot as plt

# 设置随机种子，保证结果可复现
np.random.seed(42)

# 模拟生成数据：生成3个簇中心
# 簇1
center1 = [2, 2]
# 簇2
center2 = [8, 8]
# 簇3
center3 = [5, 5]

# 在中心点附近生成随机点
data1 = np.random.randn(50, 2) + center1
data2 = np.random.randn(50, 2) + center2
data3 = np.random.randn(50, 2) + center3

# 合并所有数据
data = np.vstack((data1, data2, data3))

# 可视化原始数据分布
plt.figure(figsize=(6, 6))
plt.scatter(data[:, 0], data[:, 1], c='gray', s=20, alpha=0.6)
plt.title("Raw Data Distribution")
plt.show()

2. 核心算法实现

这部分代码封装了距离计算、质心更新和迭代逻辑。

def calculate_distance(point, centroid):
    """
    计算点与质心之间的欧氏距离
    :param point: 单个数据点
    :param centroid: 单个质心
    :return: 欧氏距离
    """
    return np.sqrt(np.sum((point - centroid) ** 2))

def kmeans(dataset, k, max_iters=100):
    """
    KMeans算法实现函数
    :param dataset: 数据集
    :param k: 聚类簇数
    :param max_iters: 最大迭代次数
    :return: 质心列表, 每个点的簇索引
    """
    # 1. 随机初始化质心：从数据集中随机选择k个点作为初始质心
    m, n = dataset.shape
    # 随机生成k个索引
    random_indices = np.random.choice(m, k, replace=False)
    centroids = dataset[random_indices]
    
    # 用于存储每个点的簇分配结果，初始化为全0矩阵
    cluster_assessment = np.zeros((m, 2)) 
    # 第一列存储簇索引，第二列存储误差（距离）
    
    cluster_changed = True
    iter_count = 0
    
    while cluster_changed and iter_count < max_iters:
        cluster_changed = False
        iter_count += 1
        
        # 2. 分配样本：遍历每个点，计算其到所有质心的距离，归入最近的簇
        for i in range(m):
            min_dist = np.inf
            min_index = -1
            
            for j in range(k):
                dist = calculate_distance(dataset[i], centroids[j])
                if dist < min_dist:
                    min_dist = dist
                    min_index = j
            
            # 如果当前点的簇分配发生了变化，标记为True以继续迭代
            if cluster_assessment[i, 0] != min_index:
                cluster_changed = True
            
            # 更新分配结果：簇索引和误差平方
            cluster_assessment[i, :] = min_index, min_dist**2
        
        # 3. 更新质心：计算每个簇的均值，作为新质心
        for j in range(k):
            # 获取属于第j个簇的所有点
            points_in_cluster = dataset[cluster_assessment[:, 0] == j]
            if len(points_in_cluster) > 0:
                # 计算均值作为新质心
                centroids[j] = np.mean(points_in_cluster, axis=0)
                
    print(f"Algorithm converged after {iter_count} iterations.")
    return centroids, cluster_assessment

3. 算法执行与可视化

调用上述函数进行聚类，并绘制结果。

# 定义聚类数量
k = 3

# 执行KMeans算法
final_centroids, final_assessment = kmeans(data, k)

# 提取每个点的簇标签
labels = final_assessment[:, 0].astype(int)

# 可视化聚类结果
plt.figure(figsize=(8, 6))
colors = ['r', 'g', 'b', 'y', 'c']

# 绘制数据点，根据簇标签着色
for i in range(k):
    points = data[labels == i]
    plt.scatter(points[:, 0], points[:, 1], c=colors[i], s=20, label=f'Cluster {i+1}')

# 绘制最终质心
plt.scatter(final_centroids[:, 0], final_centroids[:, 1], c='black', marker='x', s=200, linewidths=3, label='Centroids')

plt.title("KMeans Clustering Results")
plt.legend()
plt.grid(True)
plt.show()

三、 深度解析与算法局限性

1. 核心步骤解析

• 距离度量：代码中采用了欧氏距离来衡量样本与质心的相似度，这是 KMeans 中最常用的度量方式 。
• 质心更新策略：通过计算簇内所有样本坐标的算术平均值来更新质心位置。这种策略能够最小化簇内误差平方和（SSE），即目标函数 $J = \sum \sum ||x_i^{(j)} - c_j||^2$ 。
• 收敛条件：当所有样本的簇归属不再发生变化，或者达到预设的最大迭代次数时，算法停止。这保证了算法在有限时间内结束 。

2. 算法的局限性

尽管 KMeans 简单高效，但在实际应用中存在以下问题：

• 对初始值敏感：由于初始质心是随机选择的，不同的初始点可能导致不同的聚类结果，甚至陷入局部最优解。解决方案是使用 KMeans++ 算法进行初始化 。
• 难以处理非凸簇：KMeans 假设簇是凸形的（即球形），对于环形、月牙形等复杂几何结构的数据，聚类效果往往很差 。
• K 值的选择：算法需要预先指定 $K$ 值，但在无监督学习中，往往并不知道数据应该分成几类。通常需要结合“手肘法”或“轮廓系数”来确定最佳 $K$ 值。

四、 总结

通过上述 Python 代码，我们从底层实现了 KMeans 聚类算法的完整流程，包括数据准备、距离计算、迭代更新和结果可视化。理解这一过程有助于掌握机器学习中“迭代优化”的核心思想。在实际工程中，虽然通常会直接调用 sklearn.cluster.KMeans，但了解其背后的逻辑对于调参和解决异常问题至关重要 。