PR-2014《The MinMax K-Means clustering algorithm》

推荐深蓝学院的《深度神经网络加速：cuDNN 与 TensorRT》，课程面向就业，细致讲解CUDA运算的理论支撑与实践，学完可以系统化掌握CUDA基础编程知识以及TensorRT实战，并且能够利用GPU开发高性能、高并发的软件系统，感兴趣可以直接看看链接：深蓝学院《深度神经网络加速：cuDNN 与 TensorRT》

核心思想

MinMax $k$-Means算法的核心思想是通过引入权重机制改进传统$k$-Means算法，以解决其对初始聚类中心的敏感性问题。传统$k$-Means算法通过最小化所有簇的方差之和来划分数据，但初始中心选择不当可能导致陷入较差的局部最优解。MinMax $k$-Means通过优化一个加权的目标函数，重点最小化具有最大方差的簇，从而避免出现方差过大的簇，并使聚类结果在方差上更加均衡。这种方法通过自动调整簇的权重和一个控制参数$p$，在不同初始条件下更稳定地发现高质量的聚类划分，同时保持簇方差的平衡性。

---

目标函数

MinMax $k$-Means的目标函数是对传统$k$-Means目标函数的加权扩展。传统$k$-Means的目标函数为最小化所有簇的方差之和：

$${\mathcal{E}}_{\text{sum}}=\sum _{k=1}^M{\mathcal{V}}_k=\sum _{k=1}^M\sum _{i=1}^N{\delta }_{ik}\Vert {\mathbf{x}}_i-{\mathbf{m}}_k{\Vert }^2$$

其中：

• X = { x i } i = 1 N , x i ∈ R d X = \{\mathbf{x}_i\}_{i=1}^N, \mathbf{x}_i \in \mathbb{R}^d X={xi​}i=1N​,xi​∈Rd 是数据集，$M$ 是簇的数目；
• ${\mathcal{V}}_k={\sum }_{i=1}^N{\delta }_{ik}\Vert {\mathbf{x}}_i-{\mathbf{m}}_k{\Vert }^2$ 是第$k$个簇的方差，${\mathbf{m}}_k=\frac{{\sum }_{i=1}^N{\delta }_{ik}{\mathbf{x}}_i}{{\sum }_{i=1}^N{\delta }_{ik}}$ 是第$k$个簇的中心；
• ${\delta }_{ik}$ 是簇指示变量，若${\mathbf{x}}_i\in {\mathcal{C}}_k$，则${\delta }_{ik}=1$，否则${\delta }_{ik}=0$。

MinMax $k$-Means引入了每个簇的权重$w_k$，并优化一个加权目标函数，旨在最小化最大加权方差：

$${\mathcal{E}}_{\text{max}}=\underset{k=1,\dots ,M}{\max }{w}_k^p{\mathcal{V}}_k$$

其中：

• $w_k$ 是第$k$个簇的权重，满足${\sum }_{k=1}^M{w}_k=1$，$w_k\ge 0$；
• $p\in [0,0.5]$ 是一个用户指定的指数，控制对大方差簇的惩罚力度；
• 当$p=0$时，目标函数退化为传统$k$-Means的${\mathcal{E}}_{\text{sum}}$，因为权重影响消失。

为了使优化问题更易处理，论文提出了一种放松的目标函数：

$$\mathcal{E}=\sum _{k=1}^M{w}_k^p{\mathcal{V}}_k$$

这个目标函数在$w_k$和簇分配${\delta }_{ik}$上进行联合优化，通过迭代地最小化簇分配和最大化权重来实现。

---

目标函数的优化过程

MinMax $k$-Means的优化过程采用交替优化的策略，分为两个主要步骤：最小化步骤和最大化步骤，并引入一个自适应调整$p$的框架。以下是详细的优化过程：

1. 最小化步骤（簇分配和中心更新）：

   • 固定权重$w_k$，优化目标函数$\mathcal{E}$关于簇分配${\delta }_{ik}$和簇中心${\mathbf{m}}_k$。

   • 与传统$k$-Means类似，将每个数据点${\mathbf{x}}_i$分配到加权距离最小的簇：

     $${\delta }_{ik}=\{\begin{array}{ll}1& \text{if }k=\arg {\min }_{j=1,\dots ,M}{w}_j^p\Vert {\mathbf{x}}_i-{\mathbf{m}}_j{\Vert }^2\\ 0& \text{otherwise}\end{array}$$

   • 更新每个簇的中心为分配点的均值：

     $${\mathbf{m}}_k=\frac{{\sum }_{i=1}^N{\delta }_{ik}{\mathbf{x}}_i}{{\sum }_{i=1}^N{\delta }_{ik}}$$

2. 最大化步骤（权重更新）：

   • 固定簇分配${\delta }_{ik}$和中心${\mathbf{m}}_k$，优化权重$w_k$以最大化$\mathcal{E}$，同时满足约束${\sum }_{k=1}^M{w}_k=1$，$w_k\ge 0$。

   • 使用拉格朗日乘子法，权重$w_k$的闭式解为：

     $$w_k=\frac{{\mathcal{V}}_k^{\frac{1}{1-p}}}{{\sum }_{j=1}^M{\mathcal{V}}_j^{\frac{1}{1-p}}}$$

     其中${\mathcal{V}}_k$是当前簇的方差。这种权重分配使得方差较大的簇获得较小的权重，从而在下一轮最小化中优先减少这些簇的方差。

3. 自适应调整$p$的框架：

   • 参数$p$控制对大方差簇的惩罚力度。论文提出了一种自适应方法，从$p=0$开始，逐步增加$p$（步长为$p_{\text{step}}$），直到$p$达到最大值$p_{\text{max}}$或检测到空簇/单点簇。

   • 为了避免$p$变化过快导致的不稳定，引入了记忆因子$\beta$，在每次迭代中平滑权重更新：

     $$w_k^{(t)}=\beta w_k^{(t-1)}+(1-\beta )\frac{{\mathcal{V}}_k^{\frac{1}{1-p}}}{{\sum }_{j=1}^M{\mathcal{V}}_j^{\frac{1}{1-p}}}$$

     其中$\beta \in [0,1)$控制历史权重的保留程度，$\beta =0$表示无记忆。

4. 迭代过程：

   • 初始化：随机选择初始簇中心，设置初始权重$w_k=\frac{1}{M}$，$p=0$。
   • 重复以下步骤直到收敛或达到最大迭代次数$t_{\max }$：
     • 最小化步骤：更新簇分配和中心。
     • 最大化步骤：更新权重$w_k$。
     • 检查是否有空簇或单点簇，若有则停止增加$p$，否则$p\leftarrow p+p_{\text{step}}$。
   • 收敛条件：目标函数$\mathcal{E}$的变化小于阈值$ϵ$。

---

主要的贡献点

1. 提出新的目标函数：通过引入权重$w_k$和指数$p$，MinMax $k$-Means优化加权方差和，重点减少最大方差簇的影响，解决了传统$k$-Means对初始化的敏感性问题。
2. 自动权重学习：通过闭式解自动计算簇权重，使算法自适应地关注高方差簇。
3. 自适应参数调整：开发了一种框架，通过逐步增加$p$和引入记忆因子$\beta$，自适应地调整算法对数据集的偏置。
4. 方差均衡：算法生成的簇在方差上更加均衡，适用于需要均匀划分的应用场景。
5. 初始化鲁棒性：即使从较差的初始中心开始，MinMax $k$-Means也能一致地发现高质量的聚类结果，并可作为$k$-Means的初始化方法。

---

实验结果

实验在九个数据集上进行，包括图像（Coil1-3、Olivetti）、手写数字（Pendigits）、蛋白质（Ecoli）、患者记录（Dermatology）等，与$k$-Means、$k$-Means++$和pifs $k$-Means进行比较。评估指标包括最大簇方差${\mathcal{E}}_{\text{max}}$、方差之和${\mathcal{E}}_{\text{sum}}$、归一化互信息（NMI）以及运行时间。主要结果如下：

1. 最大方差${\mathcal{E}}_{\text{max}}$：

   • MinMax $k$-Means在几乎所有数据集上（除Pendigits外）显著降低了${\mathcal{E}}_{\text{max}}$，优于$k$-Means、$k$-Means++$和pifs $k$-Means，表明其有效抑制了大方差簇。
   • 例如，在Coil1数据集上，MinMax $k$-Means ($\beta =0.3$) 的${\mathcal{E}}_{\text{max}}$为45.04，远低于$k$-Means的66.33和$k$-Means++$的64.92。

2. 方差之和${\mathcal{E}}_{\text{sum}}$：

   • MinMax $k$-Means在多个数据集上表现出与$k$-Means相近或更优的${\mathcal{E}}_{\text{sum}}$，尤其是在初始化$k$-Means时（MinMax+$k$-Means），能显著降低${\mathcal{E}}_{\text{sum}}$，避免了传统$k$-Means因初始化不良导致的高方差解。
   • 例如，在Dermatology数据集上，MinMax+$k$-Means ($\beta =0.3$) 的${\mathcal{E}}_{\text{sum}}$为5548.56，优于$k$-Means的5885.92。

3. 归一化互信息（NMI）：

   • MinMax $k$-Means在NMI上与pifs $k$-Means相当，在部分数据集上（如Coil1-3）显著优于$k$-Means和$k$-Means++$，表明其聚类质量更高。
   • 在Coil1上，MinMax $k$-Means的NMI为0.87-0.88，接近或达到pifs $k$-Means的1.00。

4. 运行时间：

   • MinMax $k$-Means的运行时间较长（比$k$-Means慢3-6倍），主要是因为需要更多迭代来调整$p$和权重。收敛运行的平均时间（括号中）显著低于总平均时间，但仍高于其他方法。
   • 例如，在Coil3数据集上，MinMax $k$-Means ($\beta =0.1$) 的总运行时间为5.46秒，收敛时间为0.81秒，而$k$-Means仅需0.15秒。

5. 记忆因子$\beta$的影响：

   • 随着$\beta$增加（从0到0.3），${\mathcal{E}}_{\text{max}}$通常减小，但${\mathcal{E}}_{\text{sum}}$可能略增。这是因为高$\beta$减少了空簇或单点簇的出现（如表11所示，$\beta =0.3$时91.19%的运行无空簇），使$p$更容易达到$p_{\text{max}}$，从而更严格地惩罚大方差簇。
   • 然而，在某些数据集（如Pendigits）上，$\beta =0.1$导致较差的聚类质量，表明记忆因子的效果因数据集而异。

6. 初始化效果：

   • MinMax $k$-Means作为$k$-Means的初始化方法（MinMax+$k$-Means）在所有数据集上都显著提高了${\mathcal{E}}_{\text{sum}}$和NMI，证明其作为初始化策略的潜力。

---

总结

MinMax $k$-Means通过引入加权目标函数和自适应参数调整，显著改进了$k$-Means的初始化敏感性问题，生成方差均衡的簇，并在多种数据集上表现出色。其主要贡献在于提出了一种新的优化框架，结合权重学习和参数自适应，使算法更鲁棒且适用于多样化的应用场景。尽管运行时间较长，但其高质量的聚类结果和作为初始化策略的潜力使其在聚类任务中具有重要价值。