10. 无监督学习与聚类

K均值聚类的推导

1. 目标函数

K-Means的目标是最小化所有簇的簇内平方和 (Within-Cluster Sum of Squares, WCSS)。

设样本点为 ，簇的集合为 ，簇的质心为 。目标函数 为：

2. 优化策略

这是一个NP-hard问题。我们采用坐标下降法，交替优化两个变量：

1. 簇分配
2. 质心位置

3. 推导算法两步

第一步：固定质心 ，优化簇分配

当所有质心 固定时，为了让总的 最小，我们只需对每个样本 单独做决策，将其分配到能使其贡献 最小的簇中。

因此，将每个 分配给离它最近的质心 对应的簇。

这就是分配步骤 (Assignment Step)。

第二步：固定簇分配 ，优化质心

当簇分配 固定时，目标函数 可以分解为 个独立的部分。我们对每个簇 单独最小化其内部的平方和：

对 求导并令其为0：

解得：

其中 是簇 中样本的数量。

结果是，最优的质心 就是该簇所有样本点的算术平均值。 这就是更新步骤 (Update Step)。

算法复杂度

设 n 为样本数量，K 为簇的数量，d 为样本维度（特征数量），t 为迭代次数。

• 时间复杂度:
  • 每次迭代都包含两步：
    1. 分配步骤: 对每个样本()，计算其与 个质心的距离（每个距离计算耗时 ），总计 。
    2. 更新步骤: 遍历所有样本()一次，累加求和（耗时 ），然后计算 个质心的均值。
  • 主要耗时在分配步骤，因此单次迭代为 。
• 空间复杂度:
  • 主要需要存储原始数据集()和 个质心()。

由于 , , 通常远小于 ，K-Means 的复杂度可视为对数据量 呈线性关系，因此非常高效。

---

优点

1. 简单高效: 算法原理简单，易于实现，计算速度快，对大规模数据集友好。
2. 可解释性强: 聚类结果以质心为代表，易于理解和解释。
3. 调参简单: 主要参数仅有簇的数量 。

---

缺点

1. K值需要预先指定: 必须手动设定簇的数量 ，但在很多场景下 值是未知的。
2. 对初始质心敏感: 随机选择的初始质心可能导致算法收敛到局部最优解，而非全局最优解。多次运行取最优结果可缓解此问题。
3. 对非球形簇效果不佳: 算法基于距离度量，天然地假设簇是凸面且呈球状（各向同性），对非球形、细长或密度不均的簇识别效果差。
4. 对异常值敏感: 异常值（Outliers）会显著影响质心的计算，从而影响最终的聚类结果。

模糊K均值聚类的推导

1. 目标函数

与K-Means类似，FCM也旨在最小化一个目标函数。但这次，每个样本点到簇中心的距离被其隶属度的m次方加权。

• 设 为样本点，。
• 设 为簇中心，。
• 设 为样本 属于簇 的隶属度，满足 。
• 设 为模糊化系数（fuzzifier），通常取值为2。。

FCM的目标函数 定义为：

我们的目标是找到最优的隶属度矩阵 和簇中心 来最小化 。

2. 优化策略

同样采用迭代优化的策略。但由于有约束条件 ，我们需要使用拉格朗日乘子法来推导隶属度的更新公式。

3. 推导算法两步

第一步：固定簇中心 ，优化隶属度

固定簇中心，我们需要在约束 下最小化 。为每个样本 构建拉格朗日函数：

对 求偏导并令其为0：

解出 :

将此式代入约束条件 可以解出 ，最终得到 的更新公式：

直观解释：一个样本对某个簇的隶属度，与它到该簇中心的距离成反比。距离越近，隶属度越高。

第二步：固定隶属度 ，优化簇中心

固定隶属度，目标函数 对每个簇中心 是独立的。我们对 求偏导并令其为0：

整理后得到：

解出 :

直观解释：新的簇中心是所有样本点的加权平均值，权重是每个样本对该簇的隶属度的 次方。隶属度越高的点，对中心点的“拉力”越大。

---

算法复杂度

• 时间复杂度:
  • 与K-Means同阶，但常数因子更大。
  • 更新隶属度矩阵需要计算每个点到所有中心的距离，复杂度为 。
  • 更新中心点需要遍历所有点计算加权平均，复杂度为 。
• 空间复杂度:
  • 需要存储隶属度矩阵 （大小为 ）和数据集（大小为 ），比K-Means需要更多的存储空间。

---

优点

1. “软”聚类更灵活: 隶属度的概念更符合许多现实场景，尤其是在簇边界模糊不清时，能提供更丰富的信息。
2. 对异常值鲁棒性更强: 异常值通常会对所有簇有较低的隶属度，因此在计算簇中心时其影响被削弱，不像K-Means那样容易被单个异常点“带偏”。
3. 结果信息更丰富: 提供了每个样本属于各个簇的概率，而不仅仅是一个分类标签。

---

缺点

1. 计算量更大: 每次迭代的计算（尤其是隶属度更新）比K-Means更复杂，导致收敛速度较慢。
2. 需要指定K值和m值: 不仅要预先指定簇数 ，还引入了模糊化系数 ，增加了调参的复杂度。
3. 对初始值敏感: 和K-Means一样，FCM也可能陷入局部最优解，对初始中心点的选择敏感。
4. 仍然假设簇为球形: 尽管是软聚类，其距离度量（欧氏距离）依然隐含了对球形簇的偏好。

问题：模糊K均值聚类与传统的K均值聚类有什么区别？解决了传统方法的什么问题？

模糊K-均值聚类（FCM）与传统K-均值（K-Means）最核心的区别在于样本归属的定义方式：

• K-Means (硬聚类)：每个样本点唯一地、100%地属于一个簇。
• FCM (软聚类)：每个样本点以一定的**隶属度（或概率）**同时属于所有簇。

这个核心区别解决了传统K-Means的两个主要问题：

1. 处理簇边界模糊的样本: 对于处在两个簇边界之间的样本点，K-Means会强制将其划分给某一个簇，这可能不符合实际情况。FCM则允许它以较高的隶属度同时属于这两个簇，描述更加灵活和精确。
2. 降低对异常值的敏感度: 在K-Means中，一个远离中心的异常值会被完全归入某个簇，并极大地影响该簇中心的计算。而在FCM中，异常值对所有簇的隶属度都会很低，因此在计算加权平均的簇中心时，其影响被显著削弱，使得算法更加鲁棒。

简单来说，FCM通过引入“模糊”的隶属度概念，使得聚类结果更能反映现实世界中类别界限不清晰的情况，并提升了算法的抗干扰能力。

问题：模糊K均值聚类中的m为什么要大于1，等于1行不行，为什么？

必须大于1，等于1时算法将退化为标准的K-均值（K-Means），失去“模糊”的意义。

具体原因如下：

1. 当 时: 在隶属度 的更新公式中，包含一个指数项 。当 时，这个指数趋向于无穷大。这会产生一个“赢家通吃”的效应：
   • 对于任何一个样本点，它到最近簇中心的距离比值会是1或小于1。
   • 经过无穷大次方的放大，只有到最近簇中心的隶属度会变成1，而到其他所有簇中心的隶属度都会变成0。 这正是标准K-Means的“硬分配”规则，算法失去了模糊性。
2. 当 时: 作为模糊化系数（fuzzifier），它的值控制着聚类的“模糊”程度。
   • 越接近1（如1.1），聚类结果越接近“硬分配”，边界越清晰。
   • 越大（如2或3），不同簇之间的隶属度差异越小，聚类结果越模糊。

因此，为了保证算法的模糊特性， 必须大于1。在实践中， 是最常用的默认值。