K-均值（K-means）聚类算法的原理、实现与优化
字数 1658 2025-12-14 05:04:30

K-均值（K-means）聚类算法的原理、实现与优化

题目描述

K-means聚类是一种经典的无监督机器学习算法，用于将数据点划分为K个不同的簇。该算法通过迭代计算各个簇的中心点（质心），并将每个数据点分配给距离其最近的质心所属的簇，最终使得所有数据点到其所属簇质心的距离平方和最小化。

知识背景

聚类分析的目标是将相似的数据点归为一类，而将不相似的数据点分开。K-means算法需要预先指定簇的数量K，适用于球形、大小相近且密度均匀的簇。它在图像分割、客户细分、文档分类等领域广泛应用。

算法原理详解

核心思想

K-means算法的目标是找到K个簇的质心，并分配每个数据点到最近的质心，从而最小化簇内平方误差（Within-Cluster Sum of Squares, WCSS）：

\[WCSS = \sum_{i=1}^{K} \sum_{\mathbf{x} \in C_i} \|\mathbf{x} - \boldsymbol{\mu}_i\|^2 \]

其中，\(C_i\) 是第 \(i\) 个簇，\(\boldsymbol{\mu}_i\) 是该簇的质心。

基本步骤

  1. 初始化：随机选择K个数据点作为初始质心（或其他初始化方法）。
  2. 分配：将每个数据点分配到与其欧氏距离最近的质心所属的簇。
  3. 更新：重新计算每个簇的质心（取该簇所有数据点的平均值）。
  4. 迭代：重复步骤2和步骤3，直到质心不再变化（或变化小于阈值），或达到最大迭代次数。

逐步实现

假设我们有数据集 \(X = \{\mathbf{x}_1, \mathbf{x}_2, ..., \mathbf{x}_n\}\)，每个数据点是一个d维向量。

步骤1：初始化质心

随机选择K个数据点作为初始质心。这可能导致局部最优解，因此通常需要多次运行并选择最佳结果。

import numpy as np

def initialize_centroids(X, k):
    indices = np.random.choice(len(X), k, replace=False)
    return X[indices]

步骤2：分配数据点到最近质心

对于每个数据点，计算其与所有质心的距离，并分配到距离最小的质心所在的簇。

def assign_clusters(X, centroids):
    distances = np.sqrt(((X - centroids[:, np.newaxis])**2).sum(axis=2))  # 形状 (k, n)
    return np.argmin(distances, axis=0)  # 每个数据点的簇标签

步骤3：更新质心

计算每个簇中所有数据点的平均值作为新质心。

def update_centroids(X, labels, k):
    new_centroids = np.zeros((k, X.shape[1]))
    for i in range(k):
        new_centroids[i] = X[labels == i].mean(axis=0)
    return new_centroids

步骤4：迭代直至收敛

重复分配和更新步骤，直到质心变化小于阈值或达到最大迭代次数。

def kmeans(X, k, max_iters=100, tol=1e-4):
    centroids = initialize_centroids(X, k)
    for _ in range(max_iters):
        labels = assign_clusters(X, centroids)
        new_centroids = update_centroids(X, labels, k)
        if np.linalg.norm(new_centroids - centroids) < tol:
            break
        centroids = new_centroids
    return centroids, labels

算法优化与变体

1. 初始化优化：K-means++

  • 原理：选择第一个质心随机，后续质心从剩余点中选择，概率正比于到已选质心的最小距离平方。
  • 目的：使初始质心更分散，减少局部最优解，加速收敛。
def initialize_centroids_plus(X, k):
    centroids = [X[np.random.randint(len(X))]]
    for _ in range(k - 1):
        distances = np.min([np.linalg.norm(X - c, axis=1)**2 for c in centroids], axis=0)
        prob = distances / distances.sum()
        centroids.append(X[np.random.choice(len(X), p=prob)])
    return np.array(centroids)

2. 距离计算的加速：Elkan K-means

  • 原理：利用三角不等式避免不必要的距离计算，特别适用于高维数据。
  • 做法：维护数据点与质心之间距离的下界，当可以确定最近质心时跳过计算。

3. 处理非球形簇：K-medoids（PAM）

  • 原理：质心必须是实际数据点（medoid），使用曼哈顿距离或其他距离度量，对异常值更鲁棒。
  • 步骤：类似K-means，但更新质心时选择簇内到其他点距离总和最小的点。

4. 确定K值：肘部法则（Elbow Method）

  • 原理：绘制不同K值对应的WCSS曲线，选择曲线拐点（肘部）作为最佳K值。
def elbow_method(X, max_k=10):
    wcss = []
    for k in range(1, max_k + 1):
        centroids, labels = kmeans(X, k)
        wcss.append(sum(np.linalg.norm(X[i] - centroids[labels[i]])**2 for i in range(len(X))))
    # 绘制wcss vs k，寻找肘部

算法复杂度分析

  • 时间复杂度：每次迭代 \(O(n \cdot k \cdot d)\)，其中n为样本数，k为簇数，d为维度。
  • 空间复杂度：\(O((n + k) \cdot d)\)，存储数据和质心。

应用场景与局限性

应用场景

  • 客户细分：根据购买行为将客户分组。
  • 图像压缩：将相似颜色的像素聚类，用质心颜色代替。
  • 异常检测：远离所有簇的点可能为异常值。

局限性

  • 需要预先指定K值。
  • 对初始质心敏感，容易陷入局部最优。
  • 假设簇为凸形且大小相近，对非球形簇效果差。
  • 对异常值敏感。

总结

K-means是一种简单高效的聚类算法，通过迭代优化最小化簇内误差。优化方法如K-means++和Elkan算法可提升性能。在实际应用中，需结合肘部法则确定K值，并根据数据特性选择变体算法。掌握K-means的核心原理、实现细节和优化策略，是应对相关面试问题的关键。

K-均值（K-means）聚类算法的原理、实现与优化 题目描述 K-means聚类是一种经典的无监督机器学习算法，用于将数据点划分为K个不同的簇。该算法通过迭代计算各个簇的中心点（质心），并将每个数据点分配给距离其最近的质心所属的簇，最终使得所有数据点到其所属簇质心的距离平方和最小化。 知识背景 聚类分析的目标是将相似的数据点归为一类，而将不相似的数据点分开。K-means算法需要预先指定簇的数量K，适用于球形、大小相近且密度均匀的簇。它在图像分割、客户细分、文档分类等领域广泛应用。 算法原理详解 核心思想 K-means算法的目标是找到K个簇的质心，并分配每个数据点到最近的质心，从而最小化 簇内平方误差（Within-Cluster Sum of Squares, WCSS） ： \[ WCSS = \sum_ {i=1}^{K} \sum_ {\mathbf{x} \in C_ i} \|\mathbf{x} - \boldsymbol{\mu}_ i\|^2 \] 其中，\( C_ i \) 是第 \( i \) 个簇，\( \boldsymbol{\mu}_ i \) 是该簇的质心。 基本步骤 初始化 ：随机选择K个数据点作为初始质心（或其他初始化方法）。 分配 ：将每个数据点分配到与其欧氏距离最近的质心所属的簇。 更新 ：重新计算每个簇的质心（取该簇所有数据点的平均值）。 迭代 ：重复步骤2和步骤3，直到质心不再变化（或变化小于阈值），或达到最大迭代次数。 逐步实现 假设我们有数据集 \( X = \{\mathbf{x}_ 1, \mathbf{x}_ 2, ..., \mathbf{x}_ n\} \)，每个数据点是一个d维向量。 步骤1：初始化质心 随机选择K个数据点作为初始质心。这可能导致局部最优解，因此通常需要多次运行并选择最佳结果。 步骤2：分配数据点到最近质心 对于每个数据点，计算其与所有质心的距离，并分配到距离最小的质心所在的簇。 步骤3：更新质心 计算每个簇中所有数据点的平均值作为新质心。 步骤4：迭代直至收敛 重复分配和更新步骤，直到质心变化小于阈值或达到最大迭代次数。 算法优化与变体 1. 初始化优化：K-means++ 原理：选择第一个质心随机，后续质心从剩余点中选择，概率正比于到已选质心的最小距离平方。 目的：使初始质心更分散，减少局部最优解，加速收敛。 2. 距离计算的加速：Elkan K-means 原理：利用三角不等式避免不必要的距离计算，特别适用于高维数据。 做法：维护数据点与质心之间距离的下界，当可以确定最近质心时跳过计算。 3. 处理非球形簇：K-medoids（PAM） 原理：质心必须是实际数据点（medoid），使用曼哈顿距离或其他距离度量，对异常值更鲁棒。 步骤：类似K-means，但更新质心时选择簇内到其他点距离总和最小的点。 4. 确定K值：肘部法则（Elbow Method） 原理：绘制不同K值对应的WCSS曲线，选择曲线拐点（肘部）作为最佳K值。 算法复杂度分析 时间复杂度：每次迭代 \( O(n \cdot k \cdot d) \)，其中n为样本数，k为簇数，d为维度。 空间复杂度：\( O((n + k) \cdot d) \)，存储数据和质心。 应用场景与局限性 应用场景 客户细分：根据购买行为将客户分组。 图像压缩：将相似颜色的像素聚类，用质心颜色代替。 异常检测：远离所有簇的点可能为异常值。 局限性 需要预先指定K值。 对初始质心敏感，容易陷入局部最优。 假设簇为凸形且大小相近，对非球形簇效果差。 对异常值敏感。 总结 K-means是一种简单高效的聚类算法，通过迭代优化最小化簇内误差。优化方法如K-means++和Elkan算法可提升性能。在实际应用中，需结合肘部法则确定K值，并根据数据特性选择变体算法。掌握K-means的核心原理、实现细节和优化策略，是应对相关面试问题的关键。