K-means聚类算法

题目描述
K-means是一种经典的无监督聚类算法，用于将数据集划分为K个簇。给定n个数据点和目标簇数K，算法通过迭代计算将每个点分配到最近的质心（簇中心）所在的簇，然后重新计算质心，直到质心不再显著变化。

算法步骤详解

1. 初始化阶段

   • 随机选择K个数据点作为初始质心
   • 质心代表每个簇的中心位置，是算法优化的目标

2. 分配阶段

   • 遍历每个数据点，计算其与所有质心的距离（通常使用欧氏距离）
   • 将每个点分配到距离最近的质心所在的簇
   • 欧氏距离公式：\(d(x, c) = \sqrt{\sum_{i=1}^{n}(x_i - c_i)^2}\)

3. 更新阶段

   • 重新计算每个簇的质心，取簇内所有点的坐标平均值
   • 对于第k个簇，新质心计算公式：\(c_k = \frac{1}{|S_k|}\sum_{x\in S_k}x\)
   • 其中\(S_k\)表示第k个簇的点集合，\(|S_k|\)表示簇的大小

4. 收敛判断

   • 比较新旧质心的变化程度
   • 如果质心变化小于阈值或达到最大迭代次数，算法终止
   • 否则返回步骤2继续迭代

关键参数与细节

1. K值选择

   • 肘部法则：绘制不同K值对应的误差平方和（SSE）曲线，选择拐点
   • 轮廓系数：衡量聚类质量，值越接近1表示聚类效果越好

2. 距离度量

   • 欧氏距离：适用于球形分布的数据
   • 余弦相似度：适用于文本等高维稀疏数据
   • 马氏距离：考虑数据协方差结构

3. 优化策略

   • K-means++：改进的初始化方法，使初始质心尽可能分散
   • 小批量K-means：适用于大规模数据集，每次迭代使用数据子集

复杂度分析

• 时间复杂度：O(n×K×I×d)，其中n是点数，K是簇数，I是迭代次数，d是维度
• 空间复杂度：O(n×d + K×d)，存储数据和质心

Python实现示例

import numpy as np

def k_means(X, K, max_iters=100):
    # 随机初始化质心
    centroids = X[np.random.choice(len(X), K, replace=False)]
    
    for _ in range(max_iters):
        # 分配点到最近质心
        distances = np.linalg.norm(X[:, np.newaxis] - centroids, axis=2)
        labels = np.argmin(distances, axis=1)
        
        # 更新质心
        new_centroids = np.array([X[labels == k].mean(axis=0) for k in range(K)])
        
        # 检查收敛
        if np.allclose(centroids, new_centroids):
            break
        centroids = new_centroids
    
    return labels, centroids

应用场景

1. 客户细分：根据购买行为对客户分组
2. 图像分割：将图像像素按颜色聚类
3. 异常检测：远离所有簇的点可能是异常值

注意事项

• 对初始质心敏感，可能陷入局部最优
• 需要预先指定K值
• 对非球形簇和噪声数据效果较差
• 各簇大小相差较大时效果不佳