TKDE-2022《Low-Rank Linear Embedding for Robust Clustering》

---

2. 核心思想

这篇论文的核心思想是提出一种名为 RCLR (Robust Clustering with Low-Rank Linear Embedding) 的端到端（end-to-end）鲁棒聚类方法。

传统的聚类方法（如k-means）通常面临两个主要问题：

1. 两阶段框架的局限性：先降维再聚类，两个阶段独立优化，前一阶段的最优结果未必是后一阶段的最佳初始化，导致整体性能受损。
2. 样本外问题 (Out-of-sample problem)：训练好的模型无法直接处理新出现的、未参与训练的样本。

为了解决这些问题，RCLR方法的核心思想是将聚类、降维、低秩表示和局部流形结构保持等多个目标无缝集成到一个统一的模型中。具体来说：

• 显式投影机制：通过一个投影矩阵 $A$，将原始高维数据 $X$ 和聚类中心 $V$ 同时投影到一个低维子空间。这不仅实现了降维，还解决了样本外问题（新样本 $x_o$ 可通过 $x_{o}A$ 投影并聚类）。
• 低秩嵌入：在投影后的空间中，利用低秩表示来捕捉数据的全局结构信息，增强模型对噪声和异常值的鲁棒性。
• 局部结构保持：通过一个自适应的亲和力矩阵 $W$，在目标函数中加入约束项，以保持数据点的局部邻域属性。
• 端到端学习：所有组件（投影矩阵 $A$、聚类指示矩阵 $D$、聚类中心 $V$ 等）在同一个优化框架下联合学习，确保了整个流程的最优性。

总而言之，RCLR旨在通过一个统一的、端到端的框架，同时实现鲁棒的聚类、有效的降维和良好的泛化能力。

---

3. 目标函数

论文的目标函数（公式6）是整个方法的数学核心，它将多个学习目标融合在一起。其形式如下：

$$\underset{D,V,Z}{\min }{J}_{RCLR}=\Vert XZ-DVZ{\Vert }_{2,1}+\gamma \sum _{ij}\Vert x_i-x_{j}Z{\Vert }_{2,1}{w}_{ij}+\lambda \Vert Z{\Vert }_{2,1},\text{s.t.}:\text{rank}(Z)\le r$$

其中：

• $X\in {\mathbb{R}}^{n\times m}$ 是 $n$ 个样本、$m$ 维特征的原始数据矩阵。
• $Z\in {\mathbb{R}}^{m\times r}$ 是一个关键的投影矩阵（文中也用 $A$ 表示，$Z$ 和 $A$ 是同一个东西），其秩 $\text{rank}(Z)\le r$ 确保了降维到 $r$ 维（$r\ll m$）。
• $D\in {\mathbb{R}}^{n\times k}$ 是聚类指示矩阵，通常为0-1矩阵，表示每个样本属于哪个簇。
• $V\in {\mathbb{R}}^{k\times r}$ 是在低维空间中的聚类中心矩阵（原型）。
• $\Vert \cdot {\Vert }_{2,1}$ 是$L_{2,1}$-范数，对行取$L_2$范数，再对所有行取$L_1$范数。它对异常值（离群点）不敏感，增强了模型的鲁棒性。
• $w_{ij}$ 是亲和力矩阵 $W$ 的元素，表示样本 $i$ 和 $j$ 之间的相似度。
• $\gamma$ 和 $\lambda$ 是平衡各项重要性的超参数。

目标函数的三个组成部分解析：

1. $\Vert XZ-DVZ{\Vert }_{2,1}$：这是核心的聚类项。$XZ$ 是将原始数据投影到低维空间的结果，$DVZ$ 是聚类中心在低维空间的表示。该项衡量了所有样本到其对应聚类中心的距离总和，目标是使其最小化，实现有效聚类。
2. $\gamma {\sum }_{ij}\Vert x_i-x_{j}Z{\Vert }_{2,1}{w}_{ij}$：这是局部结构保持项。它鼓励在原始空间中相似的样本（$w_{ij}$ 大），在投影后的低维空间中也保持相近的距离（$\Vert x_{i}Z-x_{j}Z{\Vert }_{2,1}$ 小）。这有助于保留数据的局部流形结构。
3. $\lambda \Vert Z{\Vert }_{2,1}$：这是正则化项。$L_{2,1}$-范数正则化倾向于产生行稀疏的投影矩阵 $Z$，这意味着某些原始特征对最终的低维表示贡献为零，从而实现了特征选择，增强了模型的可解释性和鲁棒性。

---

4. 目标函数的优化过程

由于目标函数包含多个变量且相互耦合，直接求解困难。论文采用交替优化（Alternating Optimization）策略，即固定其他变量，迭代地优化其中一个变量。根据文中的算法流程，优化过程如下：

1. 初始化：首先，利用原始数据 $X$ 通过k-means等方法初始化聚类中心 $V$ 和聚类指示矩阵 $D$。然后，根据 $D$ 和 $V$ 初始化投影矩阵 $Z$ (或 $A$)。

2. 迭代优化：在每一次迭代中，依次优化以下变量：

   • 优化 $B$ (或 $\Phi$)：文中提到优化 $B$，这通常与计算亲和力矩阵 $W$ 或其相关矩阵有关。根据公式推导，$B$ 的优化涉及计算 $\Phi =(A^T{X}^T\tilde{W}XA+\lambda I{)}^{-1}$ 等步骤，其中 $\tilde{W}$ 与 $W$ 相关。这是一个中间变量，用于后续 $A$ 的更新。
   • 优化 $A$ (即 $Z$)：这是最关键的一步。在固定 $D,V,B$ 后，优化投影矩阵 $A$。根据文中描述，这一步依赖于特征值分解（eigendecomposition）。具体来说，最优的 $A$ 通常是某个矩阵（如 ${\Phi }^{-1}{A}^T{X}^T\tilde{W}X$）的前 $r$ 个最大特征值对应的特征向量。这个过程将数据投影到能最好地满足聚类和局部保持目标的低维子空间。
   • 优化 $D$：在固定 $A,V$ 后，$D$ 的更新等价于一个标准的k-means聚类步骤。对于每个样本 $x_i$，计算其在低维空间 $x_{i}A$ 到所有聚类中心 $v_{k}A$ 的距离，并将其分配给距离最近的簇。即 $j=\arg {\min }_k\Vert x_{i}A-v_{k}A{\Vert }_2$。
   • 优化 $V$：在固定 $A,D$ 后，聚类中心 $V$ 的更新是其对应簇内所有样本在低维空间投影的均值。

3. 收敛：重复上述步骤，直到目标函数 $J_{RCLR}$ 的值变化小于预设阈值，或达到最大迭代次数。文中提到，RCLR算法通常能在少数几次迭代内收敛。

---

5. 主要贡献点

根据论文的摘要和引言部分，其主要贡献可以总结为以下四点：

1. 提出了一个端到端的鲁棒聚类框架 (RCLR)：将聚类、降维、低秩表示和局部结构保持集成到一个统一模型中，克服了传统两阶段方法的局限性。
2. 解决了样本外问题：通过显式的线性投影机制 $A$，新样本可以直接通过 $x_{o}A$ 投影到低维空间并进行聚类，无需重新训练整个模型。
3. 增强了模型的鲁棒性：在整个模型中使用$L_{2,1}$-范数作为损失和正则化项，有效降低了噪声和异常值对聚类结果的影响。
4. 实现了特征选择：$L_{2,1}$-范数正则化使得投影矩阵 $Z$ 具有行稀疏性，自动选择对聚类任务最重要的特征。

---

6. 算法实现过程详解

基于上述分析，RCLR算法的实现过程可以详细描述如下：

输入：原始数据矩阵 $X\in {\mathbb{R}}^{n\times m}$，簇的数量 $k$，降维维度 $r$，超参数 $\gamma ,\lambda$。

输出：聚类结果（聚类指示矩阵 $D$），投影矩阵 $A$。

步骤：

1. 初始化：

   • 对 $X$ 进行k-means聚类，得到初始的聚类中心 $V^{(0)}\in {\mathbb{R}}^{k\times m}$ 和聚类指示矩阵 $D^{(0)}$。
   • 计算初始的投影矩阵 $A^{(0)}$。这可以通过对 $X$ 进行PCA降维到 $r$ 维，取前 $r$ 个主成分作为 $A^{(0)}$ 的列向量。

2. 迭代循环（令 $t$ 为迭代次数，从1开始）：

   • Step 1: 更新亲和力矩阵 $W$。根据当前的聚类结果 $D^{(t-1)}$ 或投影后的数据 $X{A}^{(t-1)}$，计算一个自适应的亲和力矩阵 $W$，衡量样本间的局部相似性。
   • Step 2: 更新中间变量 $B$ (或 $\Phi$)。根据当前的 $A^{(t-1)}$ 和 $W$，计算 $\Phi =(A^{(t-1)T}{X}^T\tilde{W}X{A}^{(t-1)}+\lambda I{)}^{-1}$。
   • Step 3: 更新投影矩阵 $A$。求解一个广义特征值问题，找到矩阵 ${\Phi }^{-1}{A}^{(t-1)T}{X}^T\tilde{W}X$ 的前 $r$ 个最大特征值对应的特征向量，将这些特征向量按列排列构成新的投影矩阵 $A^{(t)}$。
   • Step 4: 更新聚类指示矩阵 $D$。将所有样本投影到低维空间：$Y=X{A}^{(t)}$。对 $Y$ 执行k-means聚类，得到新的聚类分配结果 $D^{(t)}$。
   • Step 5: 更新聚类中心 $V$。根据新的聚类结果 $D^{(t)}$，计算每个簇在低维空间 $Y$ 中的均值，得到新的聚类中心 $V^{(t)}$。
   • Step 6: 收敛判断。计算当前目标函数值 $J_{RCLR}^{(t)}$，并与上一次的值 $J_{RCLR}^{(t-1)}$ 比较。如果差值小于阈值 $ϵ$，则停止迭代；否则，$t=t+1$，返回 Step 1。

3. 输出结果：

   • 最终的聚类结果由 $D^{(t)}$ 给出。
   • 最终的投影矩阵为 $A^{(t)}$。

对于新样本 $x_o$ 的处理（解决样本外问题）：
当有一个新的样本 $x_o\in {\mathbb{R}}^{1\times m}$ 需要聚类时，无需重新训练模型。只需：

1. 将其投影到已学习的低维空间：$y_o=x_o{A}^{(t)}$。
2. 计算 $y_o$ 与所有已学习的聚类中心 $V^{(t)}$ 的距离。
3. 将其分配给距离最近的簇：$j=\arg {\min }_k\Vert y_o-v_k^{(t)}{\Vert }_2$。

这个过程高效且实用，是RCLR方法的一大优势。