【机器学习基础】机器学习入门核心算法：K均值（K-Means）

1. 算法逻辑

K均值是一种无监督聚类算法，核心目标是将n个数据点划分为k个簇（cluster），使得同一簇内数据点相似度高，不同簇间差异大。算法流程如下：

graph TD
    A[初始化K个质心] --> B[分配数据点到最近质心]
    B --> C[重新计算质心位置]
    C --> D{质心是否变化？}
    D -- 是 --> B
    D -- 否 --> E[输出聚类结果]

2. 算法原理与数学推导

2.1 目标函数

最小化簇内平方和（Within-Cluster Sum of Squares, WCSS）：
$$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.2 数学推导

步骤1：初始化质心
随机选择k个数据点作为初始质心：
$${\mu }_1^{(0)},{\mu }_2^{(0)},...,{\mu }_k^{(0)}\text{其中}{\mu }_j^{(0)}\in {\mathbb{R}}^d$$

步骤2：分配数据点
对每个数据点$x_i$，计算到所有质心的距离，分配到最近质心的簇：
C j ( t ) = { x i : ∥ x i − μ j ( t ) ∥ 2 ≤ ∥ x i − μ l ( t ) ∥ 2   ∀ l } C_j^{(t)} = \{ x_i : \|x_i - \mu_j^{(t)}\|^2 \leq \|x_i - \mu_l^{(t)}\|^2 \ \forall l \} Cj(t)​={xi​:∥xi​−μj(t)​∥2≤∥xi​−μl(t)​∥2 ∀l}

步骤3：更新质心
重新计算每个簇的均值作为新质心：
$${\mu }_j^{(t+1)}=\frac{1}{|C_j^{(t)}|}\sum _{x_i\in C_j^{(t)}}{x}_i$$

步骤4：收敛条件
当满足以下任一条件时停止迭代：
$$\Vert {\mu }_j^{(t+1)}-{\mu }_j^{(t)}\Vert <ϵ\text{或}{J}^{(t)}-J^{(t+1)}<\delta$$

2.3 时间复杂度

• 每次迭代：$O(knd)$
• 总复杂度：$O(tknd)$
  其中k=簇数，n=样本数，d=特征维度，t=迭代次数

3. 模型评估

内部评估指标

1. 轮廓系数（Silhouette Coefficient）
   s ( i ) = b ( i ) − a ( i ) max ⁡ { a ( i ) , b ( i ) } s(i) = \frac{b(i) - a(i)}{\max\{a(i), b(i)\}} s(i)=max{a(i),b(i)}b(i)−a(i)​

   • $a(i)$：样本i到同簇其他点的平均距离
   • $b(i)$：样本i到最近其他簇的平均距离
   • 取值范围：[-1, 1]，越大越好

2. 戴维森堡丁指数（Davies-Bouldin Index）
   $$DB=\frac{1}{k}\sum _{i=1}^k\underset{j\ne i}{\max }\left(\frac{{\sigma }_i+{\sigma }_j}{d({\mu }_i,{\mu }_j)}\right)$$

   • ${\sigma }_i$：簇i内平均距离
   • $d({\mu }_i,{\mu }_j)$：簇中心距离
   • 取值越小越好

外部评估指标（需真实标签）

• 调整兰德指数（Adjusted Rand Index）
• Fowlkes-Mallows 指数
• 互信息（Mutual Information）

4. 应用案例

4.1 客户细分

• 场景：电商用户行为分析
• 特征：购买频率、客单价、浏览时长
• 结果：识别高价值客户群（K=5），营销转化率提升23%

4.2 图像压缩

• 原理：将像素颜色聚类为K种代表色
• 步骤：
  1. 将图像视为RGB点集（n=像素数，d=3）
  2. 设置K=256（256色图像）
  3. 用簇中心颜色代替原始像素
• 效果：文件大小减少85%且视觉质量可接受

4.3 文档聚类

• 场景：新闻主题分类
• 特征：TF-IDF向量（d≈10,000）
• 挑战：高维稀疏数据需先降维（PCA/t-SNE）

5. 面试题及答案

Q1：K均值对初始质心敏感，如何改进？
A：采用K-means++初始化：

1. 随机选第一个质心
2. 后续质心以概率$D(x{)}^2/\sum D(x{)}^2$选择
   （$D(x)$为点到最近质心的距离）

Q2：如何确定最佳K值？
A：常用方法：

• 肘部法则（Elbow Method）：绘制K与WCSS曲线，选拐点

  from sklearn.cluster import KMeans
  distortions = []
  for k in range(1,10):
      kmeans = KMeans(n_clusters=k)
      kmeans.fit(X)
      distortions.append(kmeans.inertia_)
  

• 轮廓系数法：选择使平均轮廓系数最大的K

Q3：K均值能否处理非凸数据？
A：不能。K均值假设簇是凸形且各向同性。解决方案：

• 使用谱聚类（Spectral Clustering）
• 或DBSCAN等基于密度的算法

6. 优缺点分析

优点：

1. 简单高效：时间复杂度线性增长，适合大规模数据
2. 可解释性强：簇中心代表原型特征
3. 易于实现：核心代码仅需10行

   def k_means(X, k):
       centroids = X[np.random.choice(len(X), k)]
       while True:
           labels = np.argmin(np.linalg.norm(X[:,None]-centroids, axis=2), axis=1)
           new_centroids = np.array([X[labels==j].mean(0) for j in range(k)])
           if np.allclose(centroids, new_centroids): break
           centroids = new_centroids
       return labels, centroids
   

缺点：

1. 需预先指定K值：实际应用中K常未知
2. 对异常值敏感：均值易受极端值影响
3. 仅适用于数值数据：需对类别变量编码
4. 局部最优问题：不同初始化可能产生不同结果
5. 假设各向同性：在细长簇或流形数据上效果差

7. 数学证明：为什么均值最小化WCSS？

给定簇$C_j$，优化目标：
$$\underset{{\mu }_j}{\min }\sum _{x_i\in C_j}\Vert x_i-{\mu }_j{\Vert }^2$$
求导并令导数为零：
$$\frac{\partial }{\partial {\mu }_j}\sum \Vert x_i-{\mu }_j{\Vert }^2=-2\sum (x_i-{\mu }_j)=0$$
解得：
$${\mu }_j=\frac{1}{|C_j|}\sum x_i$$
证毕：均值是簇内平方和的最优解。

💡 关键洞察：K均值本质是期望最大化（EM）算法的特例：

• E步：固定质心，分配数据点（期望）
• M步：固定分配，更新质心（最大化）

实际应用时建议：

1. 数据标准化：消除量纲影响
2. 多次运行：取最佳结果（n_init=10）
3. 结合PCA降维：处理高维数据
4. 对分类型数据用K-mode变种