核心思想分析

這篇論文的核心思想在于解決線性嵌入（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}+{?}_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 能夠有效地在低維空間中保留數據的本質結構，同時處理噪聲和異常值的影響。