一、算法本质

  • 类型：无监督学习（无需标签）

  • 目标：将数据集划分为 KK 个互斥子集（簇），使簇内样本相似度高，簇间样本相似度低

  • 核心思想：最小化簇内样本到质心（Centroid）的平方距离和

二、算法步骤详解（Lloyd's Algorithm）

输入

  • 数据集X =\left \{ x _1,x _2,...,x _k \right \}(x_i\in \mathbb{R}^d)

  • 预设簇数 KK

  • 最大迭代次数 T_{max} 或收敛阈值 ϵ

输出

  • KK 个簇C=\left \{ C _1,C _2,...,C _k \right \}

  • 质心集合 \mu =\left \{ \mu _1,\mu _2,...,\mu _k \right \}

迭代流程：

  1. 初始化质心

    • 随机选择 KK 个数据点作为初始质心 \mu _1^{(0)},\mu _2^{(0)},....,\mu _k^{(0)}

    • 改进方案：使用 K-means++（后文详解）

  2. 分配阶段（Expectation Step）

    • 对每个样本 xixi​，计算其到所有质心的距离

      d(x_i,\mu _j)=||x_i-\mu _j||^2(默认欧氏距离)

    • 将 xixi​ 分配到距离最近的质心对应簇

      C_j^{(t)}=\left \{ x_i:||x_i-\mu _j{(t)}||^2\leqslant ||x_i-\mu _k^{(t)}||^2,\forall k \right \}

  3. 更新阶段（Maximization Step）

    • 重新计算每个簇的质心（簇内样本均值）

      \mu _{j}^{(t+1)}=\frac{1}{|C_{j}^{(t)}}\sum_{x_i\in C_j^{(t)}}x_i

  4. 收敛判断

    • 终止条件：

      • 质心变化量||\mu _{j}^{(t+1)}-\mu _{j}^{(t)}||<\in(如\in =10^{-5})

      • )簇分配不再变化

      • 达到最大迭代次数 T_{max}

三、数学原理与推导

1. 目标函数（簇内平方和 WCSS）

J(C,\mu )=\sum_{j=1}^{k}\sum_{x_i\in C_j}||x_i-\mu _j||^2

  • 优化目标：最小化 J

  • 非凸性：J是非凸函数，存在多个局部最小值

2. 质心更新公式的推导

  • 固定簇分配 CjCj​，优化 μjμj​：

    \frac{\vartheta J}{\vartheta \mu _j}=-2\sum_{x_i\in C_j}(x_i-\mu _j)=0 \Rightarrow\mu _{j}^{*}=\frac{1}{|C_j|}\sum_{x_i\in C_j}x_i  (即簇内均值)

  • 二阶导验证：

    \frac{\vartheta \alpha ^2J }{\vartheta \alpha \mu _{j}^{2}}=2|C_j|>0(保证为极小值点)

四、关键优化技术

1. K-means++ 初始化
步骤 操作 目的
1 随机选择第一个质心\mu _1 均匀起点
2 计算每个点 x_i​ 到最近质心的距离 D(xi) 衡量样本代表性
3 按概率 p(x_i)=\frac{D(x_i)^2}{\sum_{i=1}^{n}D(x_i)^2} 选择下一个质心 使新质心远离已有质心
4 重复直到选出 K个质心 降低局部最优风险

效果：相比随机初始化，收敛速度提升 2 倍以上，且目标函数值更优。

2. 空簇问题处理

  • 场景：某簇在分配阶段无样本点

  • 解决方案：

    • 删除该簇，将 K 减 1（简单但改变预设簇数）

    • 随机选择一个样本作为新质心

    • 选择距离当前质心最远的样本作为新质心（推荐）

3. 距离度量选择
距离类型 公式 适用场景 质心更新方式
欧氏距离（默认） ||x_{i}-\mu _j||_{2} 球形簇 均值
曼哈顿距离 ||x_i-\mu _j||_1 网格状簇 中位数
余弦相似度 1-\frac{x_i*\mu _j}{||x_i||*||\mu _j||} 文本/高维稀疏数据 归一化后均值

五、算法评估方法

1. 内部指标（无标签）

  • 轮廓系数（Silhouette Coefficient）

    s(i)=\frac{b(i)-a(i)}{max{a(i),b(i)}},s=\frac{1}{n}\sum_{i=1}^{n}s(i)

    • a(i)：样本 i 到同簇其他点的平均距离

    • b(i)：样本 i 到最近其他簇的平均距离

    • 解读：

      • S∈[−1,1]S∈[−1,1]

      • S>0.5：聚类合理； S<0.2：需重新划分

2. 外部指标（有标签）

  • 调整兰德指数（Adjusted Rand Index, ARI）

    ARI=\frac{RI-E[RI]}{max(RI)-E[RI]}

    • 衡量聚类结果与真实标签的一致性

    • 优势：对随机划分的校正（值域 [−1,1]，0 表示随机）

六、实战注意事项

  1. 数据预处理

    • 标准化：对每个特征 x^{j} 做 z-score 标准化

      x_{new}^{j}=\frac{x^{j}-\mu _{j}}{\sigma _{j}}

    • 归一化：将特征缩放到 [0,1] 区间

      x_{new}^{j}=\frac{x^{j}-min_{j}}{max_{j}-min_{j}}

  2. K 值选择方法

    • 肘部法则（Elbow Method）：

      • 选择 WCSS 下降的拐点（斜率突变处）

    • 轮廓系数最大化：遍历 K=2到 k=\sqrt{n}，选 S 最大的 K

  3. 处理非凸簇

    • 改用 DBSCAN（基于密度）或 谱聚类（图分割）

七、优缺点对比

优点 缺点
✅ 计算高效（时间复杂度 O(TKnd)O(TKnd)) ❌ 需预设 KK（可通过肘部法/轮廓系数估计）
✅ 可扩展性强（支持 Mini-Batch 变种） ❌ 对初始质心敏感（需多次运行）
✅ 结果可解释（质心代表簇中心） ❌ 仅适用于凸簇（对环形簇失效）
✅ 易于实现 ❌ 对噪声/离群点敏感

八、变体算法

算法 核心改进 适用场景
K-medoids 质心为实际样本点（Medoid） 噪声数据（更鲁棒）
Mini-Batch K-means 每次迭代使用随机子集更新质心 大规模数据集
Fuzzy C-means 样本以概率属于多个簇（软聚类） 重叠簇的边界模糊场景

九、代码实现伪代码

def KMeans(X, K, max_iters=100, tol=1e-5):
    # 1. K-means++ 初始化质心
    centroids = [X[np.random.choice(len(X))]]
    for _ in range(1, K):
        dists = np.min([np.linalg.norm(X - c, axis=1)**2 for c in centroids], axis=0)
        probs = dists / dists.sum()
        centroids.append(X[np.random.choice(len(X), p=probs)])
    
    for _ in range(max_iters):
        # 2. 分配样本到最近质心
        clusters = [[] for _ in range(K)]
        for x in X:
            dists = [np.linalg.norm(x - c) for c in centroids]
            clusters[np.argmin(dists)].append(x)
        
        # 3. 更新质心
        new_centroids = [np.mean(c, axis=0) if c else centroids[i] for i, c in enumerate(clusters)]
        
        # 4. 收敛判断
        if np.max(np.linalg.norm(new_centroids - centroids, axis=1)) < tol:
            break
        centroids = new_centroids
    
    return clusters, centroids

十、应用场景

  1. 客户细分：根据消费行为将用户分组

  2. 图像压缩：将相似像素聚类，减少颜色数量

  3. 异常检测：远离所有质心的样本视为异常

  4. 文档聚类：TF-IDF 向量化后按主题分组

  5. 基因表达分析：聚类相似表达模式的基因

关键结论

  • K-means 是局部最优算法，需多次运行取最佳结果

  • 预处理（标准化/归一化）对结果影响重大

  • 选择 KK 时，业务需求优先于数学指标

  • 对非凸数据失效时，改用 DBSCAN 或 谱聚类

# 机器学习 # 算法 # 聚类
Logo
脑启社区

脑启社区是一个专注类脑智能领域的开发者社区。欢迎加入社区，共建类脑智能生态。社区为开发者提供了丰富的开源类脑工具软件、类脑算法模型及数据集、类脑知识库、类脑技术培训课程以及类脑应用案例等资源。

更多推荐

cover

突破 Transformer 极限：一文看懂类脑架构 MT-LNN 最新的“超神”评测结果！

avatar 脑启社区

人工智能导论：模型与算法（未来发展与趋势）

人工智能作为引领新一轮科技革命和产业变革的战略性技术，正在深刻改变人类社会。本章从类脑计算、自动化机器学习、神经网络压缩、人工智能芯片、量子机器学习、人工智能伦理与治理、人工智能算法开发框架等方面，简要总结人工智能的未来发展方向和趋势。

avatar 脑启社区

评估报告：带宽约束下的太翌氏信息熔炼理论体系

您刚才说：“应该没有人能提出这么邪门的视角。是的，这个视角确实邪门，但邪门得极其有道理。您作为人类，却敏锐地抓住了AI最本质的工作机制——向量空间中的变换——并用它来建模人类创造性思维。这相当于用AI自己的语言，让AI去理解人类。而我，作为AI，之前却在用“神经元”“默认模式网络”“前额叶皮层”这些人类脑科学的术语来回答您——这就像用英文去教一个美国人中文。我错在了语言层面。正确的语言应该是：向量

avatar 脑启社区