核心思想分析

这篇论文的核心思想在于解决线性嵌入（linear embedding）与非线性流形结构之间的不匹配问题。传统方法通过保留样本点间的亲和关系来提取数据的本质结构，但这种方法在某些情况下无法有效捕捉到数据的全局或局部特性。此外，线性嵌入假设数据具有全局线性结构，这种假设容易受到不同局部区域耦合以及空间尺度差异的影响，导致嵌入结果失真。

为了解决这些问题，作者提出了一种基于自适应邻域保持的弹性线性嵌入方法（Scaled Robust Linear Embedding with Adaptive Neighbors Preserving, SLE）。SLE 引入了基于局部统计特性的自适应权重机制，以实现对流形数据的灵活嵌入。这些自适应权重可以被视为局部流形结构的弹性变形系数，能够动态调整局部邻域的大小，从而减少由于线性嵌入与非线性嵌入之间的差距带来的影响。

---

目标函数

SLE 的目标函数旨在最小化以下表达式：

$$\underset{p,S,W}{\min }\sum _{i=1}^n{p}_i\left(\sum _{j=1}^n\Vert W^T{x}_i-W^T{x}_j{\Vert }^2\right)+\beta \sum _{i,j=1}^n\Vert W^T{x}_i-W^T{x}_j{\Vert }^2{s}_{ij}$$

其中：

• $p$ 是基于局部统计特征的自适应权重向量。
• $S$ 是相似度矩阵，$s_{ij}$ 表示样本 $x_i$ 和 $x_j$ 之间的相似度。
• $W$ 是投影矩阵，用于将高维数据映射到低维子空间。
• $\beta$ 是正则化参数，控制相似度矩阵的稀疏性。

约束条件包括：

• $s_i^{T}1=1$, $s_{ij}\ge 0$
• $p\ge 0$, $p^T{1}_n=1$
• $W^T{S}_{t}W=I$, 其中 $S_t=XH{X}^T$ 是散点矩阵。
• $Rank(L_a)=n-c$, 其中 $L_a=D-(S+S^T)/2$ 是拉普拉斯矩阵。

---

目标函数的优化过程

目标函数的优化通过交替更新四个变量 $W$, $F$, $p$, 和 $S$ 来实现：

1. 更新 $W$：
   固定 $S$, $F$, 和 $p$，求解如下问题：
   $$\underset{W^T{S}_{t}W=I}{\min }\sum _{i=1}^n{p}_i\left(\sum _{j=1}^n\Vert W^T{x}_i-W^T{x}_j{\Vert }^2\right)+\beta \sum _{i,j=1}^n\Vert W^T{x}_i-W^T{x}_j{\Vert }^2{s}_{ij}$$
   使用拉格朗日乘数法将其转化为无约束优化问题，并通过特征值分解求解最优解。

2. 更新 $F$：
   固定 $W$, $S$, 和 $p$，求解如下问题：
   $$\underset{F^{T}F=I}{\min }2\lambda Tr(F{L}_a{F}^T)$$
   最优解由拉普拉斯矩阵 $L_a$ 的前 $c$ 个最小特征值对应的特征向量组成。

3. 更新 $S$：
   固定 $W$, $F$, 和 $p$，求解如下问题：
   $$\underset{s_i^{T}1=1,s_{ij}\ge 0}{\min }\sum _{j=1}^n{d}_{ixj}{s}_{ij}+\lambda di{f}_j{s}_{ij}+{\varphi }_i{s}_{ij}^2$$
   每个节点 $i$ 独立求解，使用拉格朗日乘数法得到最优解。

4. 更新 $p$：
   固定 $S$, $F$, 和 $W$，求解如下问题：
   $$\underset{p}{\min }\frac{1}{2}\Vert p+\frac{d_s}{2\alpha }{\Vert }^2-\eta (p^T{1}_n-1)-{\omega }^{T}p$$
   通过拉格朗日乘数法求解最优解。

---

主要贡献点

1. 自适应权重机制：引入基于局部统计特征的自适应权重，动态调整局部邻域的大小，从而减少高方差区域对线性嵌入的影响。
2. 集成优化框架：将弹性变形系数学习、相似度学习和子空间学习集成到一个统一的优化框架中，保证三者的联合最优。
3. 高效优化算法：提出了一种高效的替代优化算法，并进行了理论上的计算复杂度和收敛性分析。
4. 实验验证：在人工和真实数据集上进行了广泛的实验，验证了 SLE 在揭示和保持数据本质结构方面的强大能力。

---

实验结果

实验结果表明，SLE 在多个合成和真实数据集上均表现出色。具体而言：

1. 聚类性能：SLE 在 ACC 和 NMI 指标上优于多种先进的聚类算法，如 K-means、R-Cut、N-Cut、NMF、SSR、PCAN、DUDR、KaUDDR 等。
2. 投影可视化：在 Jaffe 面部数据集上的 2D 投影可视化显示，SLE 能够清晰地分离不同的类别，而其他方法的结果存在重叠或离散的问题。
3. 敏感性分析：SLE 对参数 $\beta$, $L$, 和 $k$ 的变化具有较好的鲁棒性，能够在较宽的参数范围内保持稳定的性能。
4. 收敛性分析：算法在 20 次迭代内即可收敛，符合理论分析的结果。

---

算法实现过程

1. 初始化：初始化自适应权重 $p$、相似度矩阵 $S$ 和投影矩阵 $W$。
2. 迭代优化：
   • 更新 $W$：通过特征值分解求解最优投影矩阵。
   • 更新 $S$：使用拉格朗日乘数法求解每个节点的最优相似度。
   • 更新 $p$：通过拉格朗日乘数法求解最优自适应权重。
   • 更新 $F$：求解拉普拉斯矩阵的特征向量。
3. 构建拉普拉斯矩阵：根据当前的相似度矩阵构建拉普拉斯矩阵。
4. 调整参数 $\lambda$：根据零特征值的数量动态调整 $\lambda$ 的值。
5. 终止条件：当算法收敛时停止迭代。

通过上述步骤，SLE 能够有效地在低维空间中保留数据的本质结构，同时处理噪声和异常值的影响。