K-means算法虽然简单有效，但在实际应用中存在一些局限性。本文将深入介绍三种重要的优化方法：K-means++、Mini-Batch K-means和核K-means，并通过代码示例展示它们的实现。

---

一、K-means++：更聪明的初始化方法

原理介绍

传统K-means随机初始化质心可能导致：

1. 收敛速度慢
2. 陷入局部最优
3. 聚类结果不稳定

K-means++通过概率选择优化初始化：

1. 随机选择第一个质心
2. 计算每个点到最近质心的距离$D(x)$
3. 按概率$D(x{)}^2$选择下一个质心
4. 重复直到选出k个质心

优势

• 显著提升收敛速度
• 获得更优的聚类结果
• 理论保证：近似比$O(logk)$

代码实现

def kmeans_plusplus_init(points: np.ndarray, k: int) -> np.ndarray:
    """K-means++初始化"""
    n_samples, n_features = points.shape
    
    # 随机选择第一个质心
    centroids = [points[np.random.choice(n_samples)]]
    
    for _ in range(1, k):
        # 计算每个点到最近质心的距离
        distances = np.array([min(np.linalg.norm(p - c) ** 2 for c in centroids) 
                             for p in points])
        
        # 按概率选择下一个质心
        probabilities = distances / distances.sum()
        next_centroid = points[np.random.choice(n_samples, p=probabilities)]
        centroids.append(next_centroid)
    
    return np.array(centroids)

---

二、Mini-Batch K-means：适合大规模数据

原理介绍

传统K-means需要每次迭代计算所有数据点，计算开销大。Mini-Batch K-means通过：

1. 每次迭代随机采样一个小批量（mini-batch）
2. 仅用这批数据更新质心
3. 引入学习率逐步调整质心位置

优势

• 内存效率高
• 适合处理大数据集
• 在线学习能力
• 收敛速度更快

代码实现

def mini_batch_kmeans(points: np.ndarray, k: int, batch_size: int = 100, 
                     max_iter: int = 100) -> np.ndarray:
    """Mini-Batch K-means实现"""
    n_samples = points.shape[0]
    centroids = kmeans_plusplus_init(points, k)
    learning_rate = 1.0
    
    for _ in range(max_iter):
        # 随机采样mini-batch
        batch_indices = np.random.choice(n_samples, batch_size, replace=False)
        batch = points[batch_indices]
        
        # 分配点到最近质心
        distances = np.linalg.norm(batch[:, np.newaxis] - centroids, axis=2)
        labels = np.argmin(distances, axis=1)
        
        # 更新质心
        for i in range(k):
            cluster_points = batch[labels == i]
            if len(cluster_points) > 0:
                centroids[i] = (1 - learning_rate) * centroids[i] + \
                              learning_rate * cluster_points.mean(axis=0)
        
        # 衰减学习率
        learning_rate *= 0.9
    
    return centroids

---

三、核K-means：处理非线性可分数据

原理介绍

传统K-means假设数据是线性可分的，核方法通过：

1. 将数据映射到高维特征空间
2. 在高维空间执行K-means
3. 使用核技巧避免显式计算高维映射

常用核函数：

• 高斯核：$K(x,y)=\exp (-\gamma ||x-y|{|}^2)$
• 多项式核：$K(x,y)=(x^{T}y+c{)}^d$

优势

• 能发现复杂形状的聚类
• 处理非线性可分数据
• 保持K-means的简单性

代码实现

from sklearn.metrics.pairwise import pairwise_kernels

def kernel_kmeans(points: np.ndarray, k: int, kernel: str = 'rbf', 
                 gamma: float = 1.0, max_iter: int = 100) -> np.ndarray:
    """修正后的核K-means实现"""
    n_samples = points.shape[0]
    
    # 计算核矩阵（N x N）
    K = pairwise_kernels(points, metric=kernel, gamma=gamma)
    
    # 初始化分配
    labels = np.random.randint(0, k, size=n_samples)
    
    for _ in range(max_iter):
        # 步骤1：计算聚类中心在特征空间的表示
        centroids = []
        cluster_kernels = []
        
        for i in range(k):
            mask = (labels == i)
            if mask.sum() == 0:  # 处理空簇
                # 随机选择一个样本作为新中心
                new_center = np.random.choice(n_samples)
                centroids.append(K[:, new_center])
                cluster_kernels.append(K[new_center, new_center])
                continue
                
            # 当前簇的样本索引
            cluster_indices = np.where(mask)[0]
            
            # 计算中心点（在核空间的表示）
            centroid = K[:, cluster_indices].mean(axis=1)
            centroids.append(centroid)
            
            # 计算第三项：ΣK(x',x'')/m² （预计算）
            sub_K = K[cluster_indices][:, cluster_indices]
            cluster_kernels.append(sub_K.sum() / (len(cluster_indices)**2))
        
        # 步骤2：重新分配样本
        distances = np.zeros((n_samples, k))
        
        for i in range(k):
            # 第一项：K(x,x)
            term1 = np.diag(K)
            
            # 第二项：-2/m * ΣK(x,x')
            term2 = -2 * centroids[i]
            
            # 第三项：预计算的簇内核和
            term3 = cluster_kernels[i]
            
            # 组合三项
            distances[:, i] = term1 + term2 + term3
        
        new_labels = np.argmin(distances, axis=1)
        
        # 收敛检查
        if np.all(labels == new_labels):
            break
        labels = new_labels
    
    return labels

---

四、方法对比

方法	适用场景	时间复杂度	空间复杂度	优点	缺点
K-means++	中小数据集	O(nkd)	O(n+k)	初始化质量高	初始化耗时
Mini-Batch	大规模数据	O(bkd)	O(b+k)	内存效率高	结果略差
核K-means	非线性数据	O(n^2)	O(n^2)	发现复杂结构	计算开销大

---

五、综合应用示例

# 生成测试数据
from sklearn.datasets import make_moons
X, _ = make_moons(n_samples=1000, noise=0.1)

# K-means++
centers = kmeans_plusplus_init(X, k=2)

# Mini-Batch K-means
mb_centers = mini_batch_kmeans(X, k=2, batch_size=100)

# 核K-means
kernel_labels = kernel_kmeans(X, k=2, kernel='rbf', gamma=1.0)

# 可视化结果
import matplotlib.pyplot as plt

plt.figure(figsize=(15, 5))

plt.subplot(131)
plt.scatter(X[:, 0], X[:, 1], c=np.linalg.norm(X[:, np.newaxis] - centers, axis=2).argmin(axis=1))
plt.title("K-means++")

plt.subplot(132)
plt.scatter(X[:, 0], X[:, 1], c=np.linalg.norm(X[:, np.newaxis] - mb_centers, axis=2).argmin(axis=1))
plt.title("Mini-Batch K-means")

plt.subplot(133)
plt.scatter(X[:, 0], X[:, 1], c=kernel_labels)
plt.title("Kernel K-means")

plt.show()

---

结语

这三种优化方法代表了K-means算法发展的三个重要方向：

1. 初始化优化（K-means++）：提升算法稳定性
2. 计算效率优化（Mini-Batch）：适应大数据时代
3. 表达能力优化（核方法）：突破线性限制