算法记录

K-means

K-Means算法是无监督的聚类算法，它实现起来比较简单，聚类效果也不错，因此应用很广泛。K-Means算法有大量的变体，本文就从最传统的K-Means算法讲起，在其基础上讲述K-Means的优化变体方法。包括初始化优化K-Means++, 距离计算优化elkan K-Means算法和大数据情况下的优化Mini Batch K-Means算法。

运行流程：

• 初始化质心：随机选择 K 个样本作为初始质心。
• 分配样本：将每个样本分配到最近的质心（基于距离，如欧氏距离）。
• 更新质心：重新计算每个簇的质心（所有样本的均值）。
• 迭代收敛：重复步骤 2-3，直到质心不再变化或达到最大迭代次数。

例子：学生分组

假设有6 个学生的身高和体重数据：

学生	身高	体重
A	155	45
B	165	55
C	175	65
D	185	75
E	150	40
F	190	80

目标：将学生分为 2 个簇（K=2）。

第一次迭代

• 初始化质心：
  • 随机选择学生 A（155,45）和学生 D（185,75）作为初始质心。
• 分配数据点
  • 计算每个学生到两个质心的距离，分配到最近的簇。比如计算B到A的距离：
  • 结果：
    • 簇 1（质心 A）：学生 A、B、C、E
    • 簇 2（质心 D）：学生 D、F
• 更新质心
  • 簇 1 新质心：
  • 簇 2 新质心：同上

第二次迭代

• 重新计算每个学生到新质心的距离，分配到最近的簇
• 更新质心，如果不变，算法结束；如果变化继续迭代

最终结果

• 簇 1：学生 A、B、C、E（较矮较轻）
• 簇 2：学生 D、F（较高较重）

优缺点

优点：

• 简单高效：适合大规模数据，计算速度快。
• 易于实现：算法逻辑清晰，代码简洁。
• 可解释性强：簇的质心直观反映簇的特征。
  缺点：
• 对初始质心敏感：可能陷入局部最优。
• 需要手动指定 K 值：K 值选择困难。
• 假设簇是球形的：无法处理非凸形状的簇（如月牙形数据）。
• 对噪声敏感：离群点可能显著影响质心位置。