机器学习（7）——K均值聚类

1. K均值（K-means）聚类是什么算法？

K均值（K-means）聚类算法是一种广泛使用的无监督学习算法，用于将数据集分成多个簇（clusters）。每个簇代表数据集中的一种内在结构，其中簇内的数据点相似度较高，而簇与簇之间的相似度较低。K均值算法的目标是最小化簇内数据点的平方误差（即簇内的方差）

2. 核心思想

K均值是一种无监督学习算法，用于将数据划分为K个簇（Cluster），目标是最小化簇内样本的平方误差和（Sum of Squared Errors, SSE）。其核心思想是：

簇内相似度高：同一簇的样本尽可能接近。

簇间相似度低：不同簇的样本尽可能远离。

2. 数学目标

最小化损失函数（SSE）：
$$J=\sum _{i=1}^K\sum _{x\in C_i}\Vert x-{\mu }_i{\Vert }^2$$

• $C_i$：第 $i$个簇。
• ${\mu }_i$：第 $i$ 个簇的中心点（质心）。
• $\Vert x-{\mu }_i{\Vert }^2$：样本 $x$到质心的欧氏距离平方。

3. 算法步骤

3.1. 选择K个初始质心：

• 随机选择K个数据点作为初始质心${\mu }_1,{\mu }_2,\dots ,{\mu }_K$。

3.2.迭代优化

• 分配步骤（Assignment）: 分配每个数据点到最近的质心
  • 对于数据集中的每一个点，计算它与K个质心的距离，并将该点分配到距离其最近的质心所对应的簇。
  • C i = { x : ∥ x − μ i ∥ 2 ≤ ∥ x − μ j ∥ 2 , ∀ j } C_i = \{x : \|x - \mu_i\|^2 \leq \|x - \mu_j\|^2, \forall j\} Ci​={x:∥x−μi​∥2≤∥x−μj​∥2,∀j}
• 更新步骤（Update）:重新计算质心
  • 计算每个簇中所有点的均值，将该均值作为新的质心。
  • $${\mu }_i=\frac{1}{|C_i|}\sum _{x\in C_i}x$$

3.3. 重复步骤2和步骤3：

• 迭代分配数据点并更新质心，直到质心不再变化或者变化非常小（通常有设定的最大迭代次数或者误差容忍度）

4. 关键参数

• K值（簇数量）：需预先指定，可通过肘部法则（Elbow Method）或轮廓系数（Silhouette Score）选择。

• 初始化方法：

  • 随机初始化（可能陷入局部最优）。

  • K-Means++（优化初始质心选择，默认方法）。

• 距离度量：通常用欧氏距离，也可用曼哈顿距离等。

5. 优缺点

• ✅ 优点：

  • 简单高效：时间复杂度 $O(n\cdot K\cdot d\cdot t)$，其中 $n$ 是样本数，$d$ 是特征维度，$t$是迭代次数。

  • 可扩展性强：适合大规模数据。

  • 解释性强：簇中心可直接表示簇特征。

• ❌ 缺点：

  • 需预先指定K值。

  • 对初始质心敏感（可能收敛到局部最优）。

  • 仅适用于凸形簇（对非球形簇效果差）。

  • 对噪声和异常值敏感。

6. 改进变种

• K-Means++：优化初始质心选择，减少局部最优风险。

• Mini-Batch K-Means：用数据子集加速计算，适合大数据。

• K-Medoids（PAM）：用实际样本点（而非均值）作为中心，对噪声更鲁棒。

• Fuzzy C-Means：允许样本属于多个簇（软聚类）。

7. K值选择方法

• 肘部法则（Elbow Method）：

  • 绘制不同K值对应的SSE曲线，选择拐点（SSE下降变缓处）

from sklearn.cluster import KMeans
import matplotlib.pyplot as pltsse = []
for k in range(1, 10):kmeans = KMeans(n_clusters=k).fit(X)sse.append(kmeans.inertia_)
plt.plot(range(1, 10), sse, marker='o')
plt.xlabel('K')
plt.ylabel('SSE')
plt.show()

• 轮廓系数（Silhouette Score）：

  • 衡量样本与同簇和其他簇的相似度，值越接近1表示聚类越好。

from sklearn.metrics import silhouette_score
scores = []
for k in range(2, 10):kmeans = KMeans(n_clusters=k).fit(X)scores.append(silhouette_score(X, kmeans.labels_))
plt.plot(range(2, 10), scores, marker='o')

8. Python示例

from sklearn.cluster import KMeans
from sklearn.datasets import make_blobs
import matplotlib.pyplot as plt# 生成模拟数据
X, _ = make_blobs(n_samples=300, centers=4, random_state=42)# 训练K-Means（K=4）
kmeans = KMeans(n_clusters=4, init='k-means++', random_state=42)
kmeans.fit(X)
labels = kmeans.labels_
centers = kmeans.cluster_centers_# 可视化
plt.scatter(X[:, 0], X[:, 1], c=labels, cmap='viridis')
plt.scatter(centers[:, 0], centers[:, 1], c='red', marker='X', s=200)
plt.title("K-Means Clustering")
plt.show()

9. 应用场景

• 客户分群（如电商用户细分）。

• 图像压缩（用簇中心代表颜色）。

• 异常检测（远离簇中心的样本可能是异常值）。

• 文本聚类（如新闻主题分类）。

10. 注意事项

• 数据标准化：K均值对特征尺度敏感，需标准化（如StandardScaler）。

• 处理异常值：可用K-Medoids或DBSCAN替代。

• 非凸簇问题：尝试谱聚类或高斯混合模型（GMM）。

11. 数学推导（质心更新）

质心 ${\mu }_i$的更新是损失函数
$J$ 的最小化过程：
$$\frac{\partial J}{\partial {\mu }_i}=-2\sum _{x\in C_i}(x-{\mu }_i)=0⟹{\mu }_i=\frac{1}{|C_i|}\sum _{x\in C_i}x$$

12. 总结

K均值是聚类任务的基础算法，核心在于迭代优化质心位置。尽管有局限性（如需预设K值），但其高效性和易实现性使其在实践中广泛应用。改进方法（如K-Means++）和评估技巧（肘部法则）可进一步提升效果。