Mathematics-2025《Semi-Supervised Clustering via Constraints Self-Learning》

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

---

2. 核心思想

该论文的核心思想是针对 半监督聚类（semi-supervised clustering）中由于监督信息不足导致的过拟合和性能不稳定的问题，提出了一种通过 自学习约束（constraints self-learning）来增强聚类效果的方法。传统半监督聚类算法主要依赖给定的 必须链接（must-link） 和 不能链接（cannot-link） 约束来寻找满足这些约束的划分，但当约束数量不足或数据具有复杂的非高斯分布（如流形结构）时，性能会显著下降。

论文提出了一种 约束自学习框架（CS-PDS），通过迭代地在 判别特征空间（discriminant feature space） 中挖掘局部邻居结构来生成新的约束，逐步完善约束矩阵，最终实现更准确的聚类。此外，基于自学习的约束，提出了一种 两步约束聚类算法（FC2），通过贪婪搜索纯 must-link 子簇并合并子簇来最小化违反约束的代价。

核心创新点在于：

• 动态约束生成：从局部邻居结构中自学习约束，克服初始约束不足的限制。
• 判别空间探索：通过迭代优化特征空间，使约束在新的空间中更有效。
• 无须预设簇数：聚类算法不依赖于预先知道簇的数量，适用于复杂数据和异常点检测。

3. 目标函数

论文的目标函数旨在最小化违反约束的代价，定义为：

$$\mathcal{J}=\sum _{{\Omega }_{ij}^M=1}w\cdot 1[l_i\ne l_j]+\sum _{{\Omega }_{ij}^C=1}w\cdot 1[l_i=l_j]$$

• 符号说明：
  • ${\Omega }^M$：真实 must-link 约束矩阵，${\Omega }_{ij}^M=1$ 表示实例 $x_i$ 和 $x_j$ 属于同一簇。
  • ${\Omega }^C$：真实 cannot-link 约束矩阵，${\Omega }_{ij}^C=1$ 表示实例 $x_i$ 和 $x_j$ 属于不同簇。
  • $l_i$：实例 $x_i$ 的聚类标签。
  • $1[\cdot ]$：指示函数，$1[\text{true}]=1$，$1[\text{false}]=0$。
  • $w$：违反约束的惩罚权重。

在半监督聚类中，真实的 ${\Omega }^M$ 和 ${\Omega }^C$ 通常是未知的，仅有部分约束矩阵 $M$ 和 $C$ 可用。因此，论文通过自学习生成近似完整的约束矩阵 $M^{\ast }$ 和 $C^{\ast }$，从而将目标函数改写为：

$${\mathcal{J}}^{\ast }=\sum _{M_{ij}^{\ast }=1}w\cdot 1[l_i\ne l_j]+\sum _{C_{ij}^{\ast }=1}w\cdot 1[l_i=l_j]$$

目标是通过优化 ${\mathcal{J}}^{\ast }$，找到一个数据划分，使得违反 must-link（将同一簇的点分到不同簇）和 cannot-link（将不同簇的点分到同一簇）的总代价最小。

4. 目标函数的优化过程

优化目标函数 ${\mathcal{J}}^{\ast }$ 的过程分为两个主要阶段：约束自学习（CS-PDS） 和 约束聚类（FC2），通过 期望最大化（EM） 框架迭代进行。

4.1 约束自学习（CS-PDS）

CS-PDS 框架通过 EM 算法迭代优化，分为 E 步（期望） 和 M 步（最大化）：

1. E 步：探索部分判别空间

   • 目标：找到一个新的特征空间，使得当前约束（$M$ 和 $C$）在该空间中得到更好的满足。

   • 方法：通过线性映射 $y={\omega }^{T}x$ 将数据从原始空间 $x\in {\mathbb{R}}^m$ 投影到新空间 $y$，优化以下目标函数：

     $${\omega }^{\ast }=\arg \max \frac{{\omega }^{T}X{L}^C{X}^T\omega }{{\omega }^{T}X{L}^M{X}^T\omega }$$

     其中：

     • $L^M=D^M-M$，$D^M$ 是 $M$ 的度矩阵，$D_{ii}^M={\sum }_{i\ne j}{M}_{ij}$。
     • $L^C=D^C-C$，$D^C$ 是 $C$ 的度矩阵，$D_{ii}^C={\sum }_{i\ne j}{C}_{ij}$。
     • $X=[x_1,x_2,\dots ,x_N]$ 是数据矩阵。
     • $B=X{L}^C{X}^T$：奖励矩阵，鼓励 cannot-link 点在投影空间中分离更远。
     • $P=X{L}^M{X}^T$：惩罚矩阵，约束 must-link 点在投影空间中更靠近。

   • 优化问题转化为广义特征值分解问题：

     $$B\omega =\lambda P\omega$$

   • 为避免 $P$ 奇异，引入 Tikhonov 正则化：$P=X{L}^M{X}^T+a\cdot I$，其中 $a=0.01$。

2. M 步：自学习新约束

   • 在新的特征空间 $Y={\omega }^{T}X$ 中，根据局部邻居结构生成新的 must-link 和 cannot-link 约束。

   • Must-link 约束生成：

     • 对每个具有 must-link 的点 $u$，定义 ${\tau }_u$ 为与其 must-link 的点集，${\mu }_u$ 为 $u$ 与 ${\tau }_u$ 中点的平均距离。

     • 选择 $k$ 个最近邻 ${\pi }_u$，满足距离小于 ${\mu }_u$ 且不属于 ${\tau }_u$，更新 must-link 矩阵：

       M u j = min ⁡ { 1 − β , M u j + β } , ∀ j ∈ π u M_{uj} = \min \{1 - \beta, M_{uj} + \beta\}, \quad \forall j \in \pi_u Muj​=min{1−β,Muj​+β},∀j∈πu​

       其中 $\beta =0.2$ 控制学习率。

   • Cannot-link 约束生成：

     • 对每个具有 cannot-link 的点 $v$，定义 ${\kappa }_v$ 为与其 cannot-link 的点集，$\mu$ 为所有 must-link 点对的平均距离。

     • 选择 $k$ 个最近邻 ${\pi }_v$，满足距离小于 $\mu$ 且小于 ${\kappa }_v$ 中点的最小距离，更新 cannot-link 矩阵：

       C i j = min ⁡ { 1 − β , C i j + β } , ∀ i ∈ κ v , ∀ j ∈ π v C_{ij} = \min \{1 - \beta, C_{ij} + \beta\}, \quad \forall i \in \kappa_v, \forall j \in \pi_v Cij​=min{1−β,Cij​+β},∀i∈κv​,∀j∈πv​

   • 冲突解决：当新生成的约束产生冲突（同一对点同时为 must-link 和 cannot-link）时，采用软正则化：

     $$M_{ij}=\{\begin{array}{ll}0& \text{if }{C}_{ij}=1\\ \min \left(M_{ij},\frac{M_{ij}}{M_{ij}+C_{ij}}\right)& \text{if }0<C_{ij}<1\\ M_{ij}& \text{if }{C}_{ij}=0\end{array}$$

     $$C_{ij}=\{\begin{array}{ll}0& \text{if }{M}_{ij}=1\\ \min \left(C_{ij},\frac{C_{ij}}{M_{ij}+C_{ij}}\right)& \text{if }0<M_{ij}<1\\ C_{ij}& \text{if }{M}_{ij}=0\end{array}$$

3. 迭代与收敛：

   • 重复 E 步和 M 步，直到矩阵 $M+C$ 中非零值的比例达到 $P_{full}=20\%$ 或迭代次数达到 $Loops=50$。
   • 输出近似完整的约束矩阵 $M^{\ast }$ 和 $C^{\ast }$。

4.2 约束聚类（FC2）

FC2 算法利用 $M^{\ast }$ 和 $C^{\ast }$ 进行聚类，分为两步：

1. 第一步：贪婪搜索纯 must-link 子簇

   • 从具有最大 must-link 度的点开始，初始化子簇 ${\mathcal{K}}_h$，包含该点及其 must-link 点，并记录 cannot-link 点集 $I_h^C$。
   • 迭代扩展 ${\mathcal{K}}_h$，加入仅与当前子簇点有 must-link 的点，确保子簇内无 cannot-link。
   • 如果某点的 must-link 点大多与 ${\mathcal{K}}_h$ 有 cannot-link，则从 ${\mathcal{K}}_h$ 中移除该点。
   • 重复直到所有点被分配到纯 must-link 子簇。

2. 第二步：合并子簇

   • 计算子簇对之间的 排斥度 $r_{ij}=\frac{|{\mathcal{K}}_i,{\mathcal{K}}_j{|}_{\text{Cannot-link}}}{|{\mathcal{K}}_i,{\mathcal{K}}_j{|}_{\text{Must-link}}}$。
   • 从排斥度最低的子簇对开始，逐步合并子簇，直到形成目标簇数 $k$。
   • 对于孤立点，分配到最近的簇。

FC2 确保 ${\sum }_{C_{ij}^{\ast }=1}w\cdot 1[l_i=l_j]=0$（第一步生成纯 must-link 子簇），并通过最小化排斥度优化 ${\sum }_{M_{ij}^{\ast }=1}w\cdot 1[l_i\ne l_j]$。

5. 主要的贡献点

1. 约束自学习框架（CS-PDS）：

   • 提出了一种通过迭代探索判别特征空间和自学习约束的 EM 框架，显著增强了半监督聚类的鲁棒性。
   • 利用局部邻居结构生成新约束，适用于复杂的非高斯和流形数据。

2. 两步约束聚类算法（FC2）：

   • 提出了一种高效的聚类算法，仅依赖约束信息，无需预设簇数，适合异常点检测。
   • 通过贪婪搜索和子簇合并，最小化违反约束的代价。

3. 理论与实践结合：

   • 提供了目标函数的数学推导和优化过程的理论证明。
   • 实验验证了算法在多种基准数据集上的优越性能，特别是在约束不足的情况下。

4. 高效性与适用性：

   • 相较于基于矩阵补全的方法，CS-PDS 和 FC2 算法运行时间短，适用于大型数据集。
   • 在 UCI 数据集（Iris、Wine 等）和手写字符数据集上均表现出色。

6. 实验结果

6.1 数据集与设置

• 数据集：使用 UCI 档案中的 Iris、Wine、Segmentation，文献中的 Protein，以及手写字符数据集 Digits 和 Letters 的子集。数据集规模从 116 到 2310，特征数从 4 到 20，簇数从 3 到 7。
• 对比算法：包括 8 种算法，分为标签约束算法（FCSC、CSC、GrBias）、成对约束算法（C-K-Means、MPCK-Means、ITML、STSC）和无监督谱聚类基线。
• 评价指标：Rand Index (RI)，通过 10 次随机生成约束重复实验，报告平均 RI 和标准差。
• 约束设置：随机生成标签约束和成对约束，测试不同约束数量下的性能。

6.2 结果分析

• 标签约束实验（图 2）：
  • FC2 在所有数据集上表现优于 FCSC、CSC 和 GrBias，尤其在约束数量增加时性能稳定提升。
• 成对约束实验（图 3）：
  • FC2 随着约束数量增加，性能持续提高，优于 MPCK-Means、ITML、C-K-Means 和 STSC。
  • 传统方法如 C-K-Means 在约束增多时性能不稳定，可能因不适当约束干扰。
  • STSC（基于矩阵补全）在 Wine 数据集上表现良好，但在大型数据集（如 Segmentation）上运行时间过长（超过 24 小时）。
• 运行时间（表 3）：
  • FC2 在所有数据集上的运行时间远低于 STSC，例如在 Segmentation 数据集上为 33.57 秒，而 STSC 无法在 24 小时内完成。
  • FC2 的运行时间与 MPCK-Means 和 ITML 相当，但在 Protein 和 Iris 上更快。
• 约束有效性（图 4）：
  • 通过可视化初始和最终判别空间的距离矩阵，证明自学习约束有效分离了簇，形成了明显的块状结构。

6.3 结论

• FC2 在约束不足的情况下仍能稳定提升聚类性能，优于大多数现有算法。
• 相较于矩阵补全方法，FC2 更高效，适合大规模数据。
• 自学习约束的正确性通过判别空间的块状结构得到验证。

7. 算法的实现过程（详细解释）

以下是对 CS-PDS 和 FC2 算法的详细实现过程，分步骤解析伪代码（Algorithm 1 和 Algorithm 2）。

7.1 CS-PDS 算法实现（Algorithm 1）

输入：

• 数据点集： X = { x i } i = 1 N X = \{x_i\}_{i=1}^N X={xi​}i=1N​，$x_i\in {\mathbb{R}}^m$。
• 初始 must-link 矩阵 $M$ 和 cannot-link 矩阵 $C$。
• 邻居数 $k$（通常设为 1 到 3）。

输出：

• 增强后的约束矩阵 $M^{\ast }$ 和 $C^{\ast }$。

步骤：

1. 初始化：

   • 设置参数：$k=3$，$P_{full}=20\%$，$Loops=50$，$\beta =0.2$，正则化参数 $a=0.01$。
   • 初始化 $M$ 和 $C$ 为稀疏矩阵，仅包含给定的约束。

2. EM 迭代：

   • E 步：探索部分判别空间：
     • 计算拉普拉斯矩阵：$L^M=D^M-M$，$L^C=D^C-C$。
     • 计算矩阵：$B=X{L}^C{X}^T$，$P=X{L}^M{X}^T+a\cdot I$。
     • 求解广义特征值问题 $B\omega =\lambda P\omega$，得到投影向量 ${\omega }^{\ast }$。
     • 投影数据：$Y={\omega }^{T}X$，得到新特征空间。
   • M 步：自学习约束：
     • Must-link 更新：
       • 对每个有 must-link 的点 $u$：
         • 构造 ${\tau }_u$（与 $u$ must-link 的点集），计算平均距离 ${\mu }_u$。
         • 在 $Y$ 中找 $k$ 个最近邻 ${\pi }_u$，满足距离小于 ${\mu }_u$ 且不属于 ${\tau }_u$。
         • 更新 M u j = min ⁡ { 1 − β , M u j + β } M_{uj} = \min \{1 - \beta, M_{uj} + \beta\} Muj​=min{1−β,Muj​+β}，$\forall j\in {\pi }_u$。
     • Cannot-link 更新：
       • 对每个有 cannot-link 的点 $v$：
         • 构造 ${\kappa }_v$（与 $v$ cannot-link 的点集），计算全局 must-link 点对的平均距离 $\mu$。
         • 在 $Y$ 中找 $k$ 个最近邻 ${\pi }_v$，满足距离小于 $\mu$ 且小于 ${\kappa }_v$ 中点的最小距离。
         • 更新 C i j = min ⁡ { 1 − β , C i j + β } C_{ij} = \min \{1 - \beta, C_{ij} + \beta\} Cij​=min{1−β,Cij​+β}，$\forall i\in {\kappa }_v,\forall j\in {\pi }_v$。
     • 软正则化：
       • 对每一对 $(i,j)$，检查 $M_{ij}$ 和 $C_{ij}$ 是否冲突。
       • 应用公式 (15) 和 (16) 调整 $M_{ij}$ 和 $C_{ij}$，确保 $M_{ij}+C_{ij}\le 1$。

3. 收敛检查：

   • 计算 $M+C$ 中非零值的比例，若达到 $P_{full}$ 或迭代次数达到 $Loops$，停止迭代。
   • 返回 $M^{\ast }=M$，$C^{\ast }=C$。

实现细节：

• 使用高效的线性代数库（如 NumPy 或 SciPy）计算矩阵操作和特征值分解。
• 最近邻搜索可通过 KD 树或 Ball 树实现，优化计算效率。
• 软正则化确保约束矩阵的数值稳定性，避免冲突导致的错误传播。

7.2 FC2 算法实现（Algorithm 2）

输入：

• 增强后的约束矩阵 $M^{\ast }$ 和 $C^{\ast }$。
• 数据点集 X = { x i } i = 1 N X = \{x_i\}_{i=1}^N X={xi​}i=1N​。
• 目标簇数 $k$（可选，若未知则通过合并确定）。

输出：

• 聚类结果： { K n } n = 1 k \{\mathcal{K}_n\}_{n=1}^k {Kn​}n=1k​。

步骤：

1. 计算 must-link 度：

   • 对每个点 $x_i$，计算 $d_i={\sum }_j{M}_{ij}^{\ast }$，表示 $x_i$ 的 must-link 数量。

2. 第一步：贪婪搜索纯 must-link 子簇：

   • 初始化子簇集合 $\mathcal{K}=\varnothing$，剩余点集 $X_{\text{remain}}=X$。
   • 循环直到 $X_{\text{remain}}=\varnothing$：
     • 选择 $X_{\text{remain}}$ 中 $d_i$ 最大的点 $x_i$。
     • 初始化子簇 K h = { x i } ∪ { x j ∣ M i j ∗ ≠ 0 } \mathcal{K}_h = \{x_i\} \cup \{x_j \mid M^*_{ij} \neq 0\} Kh​={xi​}∪{xj​∣Mij∗​=0}，cannot-link 点集 I h C = { x j ∣ C i j ∗ ≠ 0 } I_h^C = \{x_j \mid C^*_{ij} \neq 0\} IhC​={xj​∣Cij∗​=0}。
     • 对 ${\mathcal{K}}_h$ 中的每个点 $x_i$：
       • 构造 M i = { x j ∣ M i j ∗ ≥ 0.5 } M_i = \{x_j \mid M^*_{ij} \geq 0.5\} Mi​={xj​∣Mij∗​≥0.5}， C i = { x j ∣ C i j ∗ ≥ 0.5 } C_i = \{x_j \mid C^*_{ij} \geq 0.5\} Ci​={xj​∣Cij∗​≥0.5}。
       • 若 $|M_i\cap I_h^C|\ge |M_i\cap {\mathcal{K}}_h|$，则从 ${\mathcal{K}}_h$ 中移除 $x_i$。
       • 否则，更新 $I_h^C=I_h^C\cup C_i$，${\mathcal{K}}_h=({\mathcal{K}}_h\cup M_i)-I_h^C$。
     • 从 $X_{\text{remain}}$ 中移除 ${\mathcal{K}}_h$，记录 ${\mathcal{K}}_h$，$h=h+1$。

3. 第二步：合并子簇：

   • 对每对子簇 $({\mathcal{K}}_i,{\mathcal{K}}_j)$，计算排斥度：

     $$r_{ij}=\frac{|{\mathcal{K}}_i,{\mathcal{K}}_j{|}_{\text{Cannot-link}}}{|{\mathcal{K}}_i,{\mathcal{K}}_j{|}_{\text{Must-link}}}$$

     其中 $|{\mathcal{K}}_i,{\mathcal{K}}_j{|}_{\text{Cannot-link}}={\sum }_{x\in {\mathcal{K}}_i,y\in {\mathcal{K}}_j}{C}_{xy}^{\ast }$，$|{\mathcal{K}}_i,{\mathcal{K}}_j{|}_{\text{Must-link}}={\sum }_{x\in {\mathcal{K}}_i,y\in {\mathcal{K}}_j}{M}_{xy}^{\ast }$。

   • 从 $r_{ij}$ 最小的一对开始，逐步合并子簇，直到形成 $k$ 个簇。

   • 对孤立点，计算与各簇的平均距离，分配到最近的簇。

实现细节：

• 使用优先队列（如 Python 的 heapq）维护 $d_i$ 的最大值，加速点选择。
• 子簇合并可通过并查集（Union-Find）实现，优化合并效率。
• 排斥度计算需高效遍历 $M^{\ast }$ 和 $C^{\ast }$，可通过稀疏矩阵操作优化。

7.3 参数设置与调优

• CS-PDS：
  • $k\in [1,3]$：控制邻居数量，过大可能引入噪声，过小可能约束不足。
  • $\beta =0.2$：平衡自学习约束与原始约束的权重。
  • $P_{full}=20\%$，$Loops=50$：确保收敛不过早停止。
• FC2：
  • $M_{ij}^{\ast }\ge 0.5$ 和 $C_{ij}^{\ast }\ge 0.5$ 作为阈值，过滤弱约束。
  • 若 $k$ 未知，可通过观察 $r_{ij}$ 的分布确定合并终止条件。

8. 总结

该论文通过提出 CS-PDS 和 FC2 算法，成功解决了半监督聚类中约束不足的问题。CS-PDS 通过 EM 框架自学习约束，FC2 利用增强约束高效聚类。实验结果证明了算法在多种数据集上的优越性能和高效性，特别是在约束稀疏的情况下。算法实现过程清晰，结合理论推导和实践优化，适合复杂数据场景。未来的改进方向包括并行化处理以提升大规模数据集的效率，以及扩展到异常点检测任务。