当前位置：首页 > article >正文

【手撕算法】K-Means聚类全解析：从数学推导到图像分割实战

article 2025/3/3 13:52:02

摘要

聚类算法是探索数据内在结构的利器！本文手撕K-Means核心公式，结合Python代码实现与图像分割案例，详解：

✅ 欧氏距离计算 ✅ 簇中心迭代更新 ✅ 肘部法则优化

一、算法核心思想

K-Means通过最小化簇内平方和实现聚类，目标函数为：
$( J = \sum_{i=1}^k \sum_{x \in C_i} |x - \mu_i|^2 )$
其中：

$( k )$ ：预设簇数量
$(mu_i )$ ：第i个簇的中心点
$C_i$ ：第i个簇的数据集合

二、数学原理详解

2.1 初始化阶段

随机选择k个初始质心：
$( mu_1^{(0)}, \mu_2^{(0)}, ..., \mu_k^{(0)} )$

2.2 迭代更新公式

分配样本到最近簇：
$( C_i^{(t)} = { x : |x - \mu_i^{(t)}|^2 \leq |x - \mu_j^{(t)}|^2 \ \forall j } )$
更新簇中心：
$(mu_i^{(t+1)} = \frac{1}{|C_i^{(t)}|} \sum_{x \in C_i^{(t)}} x )$

2.3 收敛条件

当簇中心变化量小于阈值时停止：
$( max_i | mu_i^{(t+1)} - \mu_i^{(t)}| < \epsilon )$

三、Python代码实战

3.1 手写K-Means核心逻辑

import numpy as np

class KMeans:
    def __init__(self, n_clusters=3, max_iter=300):
        self.n_clusters = n_clusters  # 簇数量
        self.max_iter = max_iter      # 最大迭代次数
        
    def fit(self, X):
        # 1. 随机初始化质心
        n_samples, n_features = X.shape
        self.centroids = X[np.random.choice(n_samples, self.n_clusters, replace=False)]
        
        for _ in range(self.max_iter):
            # 2. 计算样本到质心的距离
            distances = np.sqrt(((X - self.centroids[:, np.newaxis])**2).sum(axis=2))
            
            # 3. 分配样本到最近簇
            self.labels = np.argmin(distances, axis=0)
            
            # 4. 更新质心
            new_centroids = np.array([X[self.labels == i].mean(axis=0) 
                                    for i in range(self.n_clusters)])
            
            # 5. 检查收敛
            if np.allclose(self.centroids, new_centroids):
                break
            self.centroids = new_centroids
            
        return self

3.2 图像分割实战案例

from sklearn.datasets import load_sample_image
import matplotlib.pyplot as plt

# 加载示例图片
china = load_sample_image("china.jpg")
X = china.reshape(-1, 3) / 255.0  # 归一化像素值

# 使用K-Means进行颜色量化
kmeans = KMeans(n_clusters=16).fit(X)
compressed_colors = kmeans.centroids[kmeans.labels].reshape(china.shape)

# 可视化对比
fig, (ax1, ax2) = plt.subplots(1, 2, figsize=(12,6))
ax1.imshow(china)
ax2.imshow(compressed_colors)
ax1.set_title("原始图像（16.7万色）")
ax2.set_title("压缩后图像（16色）")

四、算法优化技巧

4.1 K-Means++初始化

初始化方法	优点	实现步骤
随机初始化	简单快速	直接随机选取样本
K-Means++	减少局部最优	按概率分布选择初始点

4.2 肘部法则确定K值

# 计算不同K值的SSE
sse = []
for k in range(1, 10):
    kmeans = KMeans(n_clusters=k).fit(X)
    sse.append(np.sum((X - kmeans.centroids[kmeans.labels])**2))

# 绘制肘部曲线
plt.plot(range(1,10), sse, 'bx-')
plt.xlabel('K值')
plt.ylabel('SSE')