摘要

在本文中，提出了一种新的聚类模型来同时学习数据相似矩阵和聚类结构。新模型通过基于局部距离为每个数据点分配自适应和最优邻居来学习数据相似性矩阵。同时，对数据相似性矩阵的拉普拉斯矩阵施加新的秩约束，使得得到的相似性矩阵中的连接分量完全等于聚类数。

介绍

聚类将数据点划分为不同的组，使得同一个组中的对象具有高度的相似性。

最常用的聚类算法是k-means。

本文中提出新的角度解决聚类问题。通过基于局部连通性为每个数据点分配自适应和最优邻居来学习数据相似矩阵。主要假设是，距离较小的数据点成为邻居的概率较大。更重要的是，对相似矩阵的拉普拉斯矩阵施加秩约束，以实现理想的邻域分配，使得数据中的连接分量与聚类数精确，并且每个连接分量对应于一个聚类。新模型同时学习数据相似度矩阵和聚类结构，以获得最佳聚类结果。

推导了一种新的高效算法来解决这个具有挑战性的问题，并从理论上分析了我们的方法与K均值聚类和谱聚类之间的联系。此外，扩展了所提出的用于投影聚类的聚类模型以处理高维数据。

符号：

整篇论文中所有的符号都是大写：

符号	表示
$m_i$ ， $m_{ij}$	矩阵M的第i行,M的第（i,j）个元素
$∥v∥2\lVert v \rVert_2$	向量v的L2范式
$∥M∥F\lVert M\rVert_F$	矩阵M的Frobenius范数
$I$	单位矩阵
$1\textbf{1}$	列向量，所有元素为1

向量v，矩阵M大于等于0，其中所有的元素均大于等于0

自适应邻域聚类

给定数据集 $x1,x2,...,xn，X∈Rn×d{x_1, x_2, ..., x_n}，X\in \mathbb{R}^{n \times d}$ 作为数据矩阵。

$xi∈Rd×1x_i \in \mathbb{R} ^{d \times 1}$ 的邻居可以定义为数据集中与 $x_i$ 最近的k个数据点，本文中考虑概率邻居，简单起见，使用欧几里得距离作为距离度量。

对于 $x_i$ ，每个数据点可以以概率 $s_{ij}$ 的概率作为邻居连接到 $x_i$

一个较小的距离 $x_i-x_j||_2^2$ 应分配到更大的 $s_{ij}$ ,确定概率 $s_{ij}|_{j=1}^n$ 的自然方法是解决以下问题：
$min⁡siT1=1,0≤si≤1∑j=1n∣∣xi−xj∣∣22sij(1)\mathop{\min}_{s_i^T \textbf{1}=1,0 \leq s_{i} \leq 1} \sum_{j=1}^{n} ||x_i-x_j|| _2 ^2 s_{ij} \tag{1}$
其中 $si∈Rn×1s_i ∈ \mathbb{R}^{n \times 1}$ 是第 j 个元素为 $s_{ij}$ 的向量。

问题（1）有平凡解（例Ax=0中的0解），即只有最近的数据点可以是概率为1的xi的邻居，而所有其他数据点不能是xi的邻居。

在数据中不涉及任何距离信息的情况下解决以下问题：
$min⁡siT1=1,0≤si≤1∑j=1nsij2(2)\mathop {\min}_{s_i^T \textbf{1}=1,0 \leq s_{i} \leq 1} \sum_{j=1} ^n s_{ij} ^2 \tag{2}$
最优解决方案是所有数据点都可以是 $x_i$ 的邻居，其概率为 $1n\frac{1}{n}$

结合(1)和（2）,解决如下问题：
$min⁡siT1=1,0≤si≤1∑j=1n(∣∣xi−xj∣∣22sij+γsij2)(3)\mathop {\min}_{s_i^T \textbf{1}=1,0 \leq s_{i} \leq 1} \sum_{j=1} ^n (||x_i-x_j|| _2 ^2 s_{ij} + \gamma s_{ij} ^2 ) \tag{3}$
上式中第二项是正则化， $γ\gamma$ 是正则化参数，记 $dijx=∣∣xi−xj∣∣22,dix∈Rn×1d_{ij}^x = ||x_i-x_j||_2^2,d_i^x \in \mathbb{R}^{n \times 1}$ 表示为第j个元素为 $d_{ij}^x$ 的向量。问题（3）可以写成向量的形式。
$min⁡siT1=1,0≤si≤1∑j=1n∣∣si+12γdix∣∣22(4)\mathop{\min}_{s_i^T \textbf{1}=1,0 \leq s_{i} \leq 1} \sum_{j=1}^{n} ||s_i+\frac{1}{2 \gamma}d_i^x|| _2 ^2\tag{4}$

公式（3）到公式（4）的证明：
$min⁡∑j=1n(∣∣xi−xj∣∣22sij+γsij2)=min⁡∑i=1n∑j=1ndijxsij+γ∣∣s∣∣F2=min⁡∑i=1nsiTdix+γ∣∣s∣∣F2=min⁡∑i=1n(siTdix+γsiTsi)=γmin⁡∑i=1n(siTsi+1γsiTdix)=γmin⁡∑i=1n(siTsi+212γsiTdix+dixTdix(2γ)2−dixTdix(2γ)2)最后一项是常数，舍去=γmin⁡∑i=1n(siTsi+212γsiTdix+dixTdix(2γ)2)=γmin⁡∑i=1n∣∣si+12γdix∣∣22\begin{align} &\mathop {\min} \sum_{j=1} ^n (||x_i-x_j|| _2 ^2 s_{ij} + \gamma s_{ij} ^2 ) \\ & = \mathop {\min} \sum_{i=1}^n \sum_{j=1} ^n d_{ij}^x s_{ij} + \gamma ||s||_F ^2 \\ & = \mathop{\min} \sum_{i=1}^n s_i^T d_i^x +\gamma ||s||_F^2 \\ & = \mathop{\min} \sum_{i=1}^n (s_i^T d_i^x + \gamma s_i^Ts_i) \\ & =\gamma \mathop{\min} \sum_{i=1}^n (s_i^Ts_i + \frac{1}{\gamma}s_i^Td_i^x) \\ & = \gamma \mathop{\min} \sum_{i=1}^n (s_i^Ts_i + 2\frac{1}{2\gamma}s_i^Td_i^x + \frac{{d_i^x}^Td_i^x}{(2\gamma)^2}- \frac{{d_i^x}^Td_i^x}{(2\gamma)^2} ) \quad最后一项是常数，舍去 \\ & = \gamma \mathop{\min} \sum_{i=1}^n (s_i^Ts_i + 2\frac{1}{2\gamma}s_i^Td_i^x + \frac{{d_i^x}^Td_i^x}{(2\gamma)^2}) \\ & = \gamma \mathop{\min} \sum_{i=1}^n ||s_i + \frac{1}{2\gamma} d_i^x||_2^2 \end{align}$
对每个数据点 $x_i$ ，可以使用等式（3）分配其邻居，因此可以解决以下问题为所有数据点分配邻居：
$min⁡∀i,siT1=1,0≤si≤1∑j=1n(∣∣xi−xj∣∣22sij+γsij2)(5)\mathop {\min}_{\forall i, s_i^T \textbf{1}=1,0 \leq s_{i} \leq 1} \sum_{j=1} ^n (||x_i-x_j|| _2 ^2 s_{ij} + \gamma s_{ij} ^2 ) \tag{5}$
理想的邻居分配是数据中的连通分量是精确的c。通常对于 $γ\gamma$ 的任意值，等式（5）并不能达到理想情况。多数情况下，所有数据点仅作为一个连通分量作为连接。为了实现理想的分配，（5）中的概率 $s_{ij}|_{j=1}^n$ 应受到约束，使邻域分配成为一个自适应的过程，以使连通分量精确为c。这种对相似性的结构化约束是基本的，但也很难处理。本文中，提出一种新颖但非常简单的方法来实现这一目标。

邻域分配得到的矩阵 $\in \mathbb{R}^{n \times n}$ 可以看成以 n 个数据点为节点的图的相似度矩阵。假设每个节点 i 被分配一个函数值为 $fi∈Rc×1f_i \in \mathbb{R}^{c \times 1}$ ，那么可以验证：
$∑i,j=1n∣∣fi−fj∣∣22sij=2Tr(FTLsF)(6)\sum_{i,j=1}^n ||f_i-f_j||_2^2s_{ij} = 2Tr(F^TL_sF) \tag{6}$
其中 $\in \mathbb{R}^{n \times c}$ 第i行是 $f_i$ , $LS=DS−ST+S2L_S=D_S-\frac{S^T+S}{2}$ 是拉普拉斯矩阵， $D_S$ 是对角矩阵，第i个对角元素是 $∑j(sij+sji)/2\sum_j(s_{ij}+s_{ji})/2$ 。

若相似矩阵S为非负，则拉普拉斯矩阵有如下性质：

定理1：

相似矩阵Ｓ对应的拉普拉斯矩阵 $L_S$ 特征值为０的重数 c 等于相似矩阵Ｓ对应的图中连通分量的个数

定理1表明，若 $L_S$ 的秩为 $n - c$ （拉普拉斯矩阵是对称的，实对称矩阵必可相似对角化，可相似对角化的矩阵的秩等于非零特征值的个数）。那么得到的连通分量的个数刚好为ｃ个，这时的邻居分配是理想的分配，并且基于Ｓ将点分成了ｃ个簇类。不需要执行k-means或其他离散化过程。在问题（5）中添加额外的秩约束 $r(L_S)=n-c$ ，以实现具有清晰聚类结构的理想邻居分配。
$Jopt=min⁡S∑i,j=1n(∣∣xi−xj∣∣22sij+γsij2)s.t∀i,siT1=1,0≤si≤1,rank(Ls)=n−c(7)J_{opt} = \mathop{\min}_S \sum_{i,j=1}^n (||x_i-x_j||_2^2s_{ij}+\gamma s_{ij}^2) \tag{7} \\ s.t \quad \forall i,s_i^T \textbf{1} = 1, 0 \leq s_i \leq 1 ,rank(L_s) = n-c$
问题（7）难以解决，因为拉普拉斯矩阵 $L_S$ 以及度矩阵 $D_S$ 依赖于S,秩约束也难以处理。

求解问题（7）的优化算法

$σi(LS)\sigma _i(L_S)$ 是 $L_S$ 的第i个最小特征值， $σi(LS)≥0\sigma _i(L_S) \geq 0$ （ $L_S$ 半正定）对于足够大的 $λ\lambda$ 值，问题（7）等价于：
$min⁡S∑i,j=1n(∣∣xi−xj∣∣22sij+γsij2)+2λ∑i=1cσi(Ls)s.t∀i,siT1=1,0≤si≤1(8)\mathop{\min}_S \sum_{i,j=1}^n (||x_i-x_j||_2^2s_{ij}+\gamma s_{ij}^2) \tag{8} +2 \lambda \sum_{i=1}^c \sigma_i(L_s) \\ s.t \quad \forall i,s_i^T \textbf{1} = 1, 0 \leq s_i \leq 1$
当 $λ\lambda$ 足够大时，由于 $σi≥0\sigma_i \geq0$ ,问题（8）的最优解S将会使第二项 $∑i=1cσi(LS)\sum_{i=1}^c \sigma_i(L_S)$ 变成0。因此可以满足问题（7）中的约束秩n-c

根据相关定理：
$∑i=1cσi(LS)=min⁡F∈Rn×c,FTF=ITr(FTLSF)(9)\sum_{i=1}^c \sigma_i(L_S) = \mathop{\min}_{F \in \mathbb{R}^{n \times c},F^TF=I}Tr(F^TL_SF) \tag{9}$
因此，问题（8）进一步等价于以下问题:
$min⁡S∑i,j=1n(∣∣xi−xj∣∣22sij+γsij2)+2λTr(FTLSF)s.t∀i,siT1=1,0≤si≤1,F∈Rn×c,FTF=I(10)\mathop{\min}_S \sum_{i,j=1}^n (||x_i-x_j||_2^2s_{ij}+\gamma s_{ij}^2) \tag{10} +2 \lambda Tr(F^TL_SF) \\ s.t \quad \forall i,s_i^T \textbf{1} = 1, 0 \leq s_i \leq 1,F \in R^{n \times c},F^TF=I$
相较于问题（7），问题10更容易求解。

当S固定时，问题10 变成：
$min⁡F∈Rn×c,FTF=ITr(FTLSF)(11)\mathop{\min}_{F \in \mathbb{R}^{n \times c},F^TF=I}Tr(F^TL_SF) \tag{11}$
问题（11）的最优解F由 $L_S$ 的c个最小特征值的对应的c个特征向量形成。

当F固定时问题10变为：
$min⁡S∑i,j=1n(∣∣xi−xj∣∣22sij+γsij2)+2λTr(FTLSF)s.t∀i,siT1=1,0≤si≤1(12)\mathop{\min}_S \sum_{i,j=1}^n (||x_i-x_j||_2^2s_{ij}+\gamma s_{ij}^2) \tag{12} +2 \lambda Tr(F^TL_SF) \\ s.t \quad \forall i,s_i^T \textbf{1} = 1, 0 \leq s_i \leq 1$
根据等式6，问题12可以写为：
$min⁡S∑i,j=1n(∣∣xi−xj∣∣22sij+γsij2+λ∣∣fi−fj∣∣22sij)s.t∀i,siT1=1,0≤si≤1(13)\mathop{\min}_S \sum_{i,j=1}^n (||x_i-x_j||_2^2s_{ij}+\gamma s_{ij}^2 \tag{13} + \lambda ||f_i-f_j||_2^2s_{ij} ) \\ s.t \quad \forall i,s_i^T \textbf{1} = 1, 0 \leq s_i \leq 1$
问题13在不同i之间是独立的，因此可以针对每个i分别解决以下问题：
$min⁡si∑j=1n(∣∣xi−xj∣∣22sij+γsij2+λ∣∣fi−fj∣∣22sij)s.t∀i,siT1=1,0≤si≤1(14)\mathop{\min}_{s_i} \sum_{j=1}^n (||x_i-x_j||_2^2s_{ij}+\gamma s_{ij}^2 \tag{14} + \lambda ||f_i-f_j||_2^2s_{ij} ) \\ s.t \quad \forall i,s_i^T \textbf{1} = 1, 0 \leq s_i \leq 1$
记 $dijx=∣∣xi−xj∣∣22,dijf=∣∣fi−fj∣∣22,di∈Rn×1d_{ij}^x = ||x_i-x_j||_2^2,d_{ij}^f = ||f_i-f_j||_2^2,d_i \in \mathbb{R}^{n \times 1}$ 表示为第j个元素为 $dij=dijx+λdijfd_{ij}=d_{ij}^x+\lambda d_{ij}^f$ 的向量。问题14可以写成向量的形式：
$min⁡siT1=1,0≤si≤1∑j=1n∣∣si+12γdi∣∣22(15)\mathop{\min}_{s_i^T \textbf{1}=1,0 \leq s_{i} \leq 1} \sum_{j=1}^{n} ||s_i+\frac{1}{2 \gamma}d_i|| _2 ^2\tag{15}$

公式14到公式15的证明：
$min⁡si∑j=1n(∣∣xi−xj∣∣22sij+γsij2+∣∣fi−fj∣∣22sij)=min⁡∑i=1n∑j=1n(sijdijx+λijdijf)+λ∣∣S∣∣F2=min⁡∑i=1n(siTdix+γ∣∣si∣∣22+λsiTdif)=min⁡∑i=1n(siT(dix++λdif)+γ∣∣si∣∣22)=min⁡∑i=1n(siTdi+γ∣∣si∣∣22)=min⁡∑i=1n(siTdi+γsiTsi)=γmin⁡∑i=1n(siTsi+1γsiTdi)=γmin⁡∑i=1n(siTsi+212γsiTdi+diTdi4γ2−diTdi4γ2)最后一项常数，舍去=γmin∑i=1n∣∣si+12γdi∣∣22\begin{align} & \mathop{\min}_{s_i} \sum_{j=1}^n (||x_i-x_j||_2^2s_{ij}+\gamma s_{ij}^2 \tag{14} +||f_i-f_j||_2^2s_{ij} ) \\ & = \mathop{\min}\sum_{i=1}^n \sum_{j=1}^n(s_{ij}d_{ij}^x + \lambda_{ij}d_{ij}^f) + \lambda||S||_F^2 \\ & = \mathop{\min}\sum_{i=1}^n (s_i^Td_i^x + \gamma||s_i||_2^2 + \lambda s_i^T d_i^f) \\ & = \mathop{\min}\sum_{i=1}^n (s_i^T(d_i^x + + \lambda d_i^f) + \gamma||s_i||_2^2 ) \\ & = \mathop{\min}\sum_{i=1}^n (s_i^T d_i + \gamma||s_i||_2^2) \\ & = \mathop{\min}\sum_{i=1}^n (s_i^T d_i + \gamma s_i^T s_i )\\ & = \gamma\mathop{\min}\sum_{i=1}^n (s_i^T s_i + \frac{1}{\gamma}s_i^T d_i ) \\ & = \gamma\mathop{\min}\sum_{i=1}^n (s_i^T s_i + 2\frac{1}{2\gamma}s_i^T d_i +\frac{d_i^Td_i}{4\gamma^2}- \frac{d_i^Td_i}{4\gamma^2}) \quad最后一项常数，舍去 \\ & = \gamma \mathop{min} \sum_{i=1}^n||s_i+\frac{1}{2\gamma}d_i||_2^2 \end{align}$

在这里插入图片描述

联系kmeans聚类

中心矩阵：
$H=I−1n11T(16)H=I-\frac{1}{n} \textbf{1}\textbf{1}^T \tag{16}$
$Dx∈Rn×nD^x \in \mathbb{R}^{n \times n}$ 作为距离矩阵，其中第（i,j）个元素是 $d_{ij}^x = ||x_i-x_j||_2^2$ ，为了分析算法1与kmeans的联系，首先需要以下引理：

引理1： $HD^xH=-2HXX^TH$

证明：

$d_{ij}^x = ||x_i-x_j||_2^2 = x_i^Tx_j+x_j^Tx_i-2x_ix_j$ ， $Dx=Diag(XXT)11T+11TDiag(XXT)−2XXTD^x = Diag(XX^T) \textbf{11}^T+ \textbf{11}^T Diag(XX^T) -2XX^T$ , $Diag(XX^T)$ 是对角矩阵，对角元素是 $XX^T$ ,注意：根据H的定义， $\textbf{1}=\textbf{1}^TH=0$ ，我们有 $HD^xH=-2HXX^TH$

引理2揭示了当 $γ→∞\gamma \rightarrow \infty$ 算法1解决了kmeans问题

引理2:当 $γ→∞\gamma \rightarrow \infty$ ，问题7等价于kmeans问题

证明：

问题7可以写为矩阵的形式：
$min⁡S1=1,S≥0,rank(LS)=n−cTr(STDx)+γ∣∣S∣∣F2(17)\mathop{\min}_{S \textbf{1}=1,S \geq 0,rank(L_S)=n-c} Tr(S^TD^x)+ \gamma||S||_F^2 \tag{17}$
由于约束 $rank(L_s)=n-c,S$ 具有精确的 $c$ 分量（即，s是具有适当置换的块对角）。假设S的第i个分量是 $Si∈Rni×niS_i\in \mathbb{R}^{n_i×ni}$ ， $n_i$ 是组件中数据点的数量，那么解决问题（17）就是解决每个i的以下问题:
$min⁡Si1=1,Si≥0Tr(SiTDix)+γ∣∣Si∣∣F2(18)\mathop{\min}_{S_i \textbf{1}=1,S_i \geq 0} Tr(S_i^TD_i^x)+ \gamma||S_i||_F^2 \tag{18}$
当 $γ→∞\gamma \rightarrow \infty$ ,问题8变成：
$min⁡Si1=1,Si≥0∣∣Si∣∣F2(19)\mathop{\min}_{S_i \textbf{1}=1,S_i \geq 0} ||S_i||_F^2 \tag{19}$
问题19的最优解是 $s_i$ 的所有元素都等于 $1ni\frac{1}{n_i}$ ：

因此，当 $γ→∞\gamma \rightarrow \infty$ 问题17的最优解应该是以下形式：
$sij={1nkxi和xj在同一分量k中0其他情况(20)s_{ij} = \begin{cases} \frac{1}{n_k} & x_i和x_j在同一分量k中 \\ 0 & 其他情况 \\ \end{cases} \tag{20}$

用 $V$ 表示满足等式20 的解集。对于c分量任意可能的划分，s具有等式20中的形式。 $S||_F^2$ 有相同的值，即 $S||_F^2=c$ ,问题17变成：
$min⁡S∈VTr(STDx)(21)\mathop{\min}_{S \in V}Tr(S^TD^x) \tag{21}$

根据21中S的约束，S是对称的并且 $S1=1TS=1S\textbf{1}=\textbf{1}^TS=1$ ,所以： $Tr(HDxHS)=Tr(DxS)−1n1TDx1Tr(HD_xHS)=Tr(D_xS)- \frac{1}{n} \textbf{1}^T D_x \textbf{1}$ 并且因此问题21等价于解决以下问题：
$min⁡S∈VTr(HDxHS)(22)\mathop{\min}_{S \in V}Tr(HD^xHS) \tag{22}$
定义标签矩阵 $\in \mathbb{R}^{n \times c}$ ,第（i，j)个元素是：
$yij={1nksi属于第k个分量0其他情况(23)y_{ij}= \begin{cases} \frac{1}{\sqrt{n_k}} & s_i属于第k个分量 \\ \tag{23} 0 & 其他情况 \end{cases}$

根据等式22和引理1，可以得到：
$min⁡S∈VTr(HDxHS)⟺max⁡S∈VTr(HXXTHSS)⟺max⁡S∈VTr(XTHSHX)⟺min⁡S∈VTr(XTH(I−S)HX)⟺min⁡YTr(XTH(I−YYT)HX)⟺min⁡YTr(Sw)\begin{align} & \mathop{\min}_{S\in V}Tr(HD_xHS) \\ & \iff \mathop{\max}_{S\in V}Tr(HXX^THSS) \\ & \iff \mathop{\max}_{S\in V}Tr(X^THSHX)\\ & \iff \mathop{\min}_{S\in V}Tr(X^TH(I-S)HX) \\ & \iff \mathop{\min}_Y Tr(X^TH(I-YY^T)HX) \\ & \iff \mathop{\min}_Y Tr(S^w) \tag{24} \end{align}$

这正是kmeans问题，在经典线性判别分析（LDA）中，当给定数据的标签Y时，矩阵Sw称为类内散布矩阵。K-均值是找到最佳标记Y，使得类内散射矩阵tr（Sw）的轨迹最小化。

我们将在下一小节中看到，算法1中提出的方法与谱聚类密切相关。因此，当 $γ→∞\gamma \rightarrow \infty$ 虽然新算法是为了解决K-means问题（只能分割球形数据），当 $γ\gamma$ 不是很大时，它可以分割任意形状的数据。我们还将在实验中看到，即使在 $γ\gamma$ 不是很大的情况下，该新算法也可以找到更好的K-均值问题的解。

与谱聚类的联系

给定图的相似矩阵S，谱聚类是为了解决如下问题：
$min⁡F∈Rn×c,FTF=ITr(FTLSF)(25)\mathop{\min}_{F\in R^{n \times c},F^TF=I}Tr(F^TL_SF) \tag{25}$
通常，由于具有S的图不具有精确的c连通分量，因此不能直接用于聚类。应在F上执行K均值或其他离散化程序，以获得最终聚类结果

在算法1的收敛过程中，我们还获得了问题（25）的最优解F，不同之处在于，相似性S也是通过算法学习的。注意，在收敛过程中，问题（10）中的最后一项 $2 λ T r (FT L SF)$ 将近似为零，学习的S主要通过求解问题5来实现。

由于秩约束，S有c个联通分量，因此最优解F,由 $L_S$ 的c个最小特征值对应的特征向量组成，可以写为：
$F = Y Q$
$\in \mathbb{R}^{n \times c}$ 是23中定义的标签矩阵， $\in \mathbb{R}^{n \times c}$ 是任意正交矩阵。也就是说，可以直接使用获得的F来获得最终的聚类结果，而无需像传统的谱聚类那样使用K均值或其他离散化过程。

可以看出，所提出的算法同时学习相似矩阵S和标签矩阵F，而传统的谱聚类仅在给定相似矩阵S的情况下学习F。因此，新算法在实践中可以获得更好的性能，因为它还学习用于聚类的自适应图。

确定 $γ\gamma$ 的值

实际上正则化参数比较难以调整，因为其值可能从0到无穷大。本节提出有效的方法确定问题7中的 $γ\gamma$

对于每个i，问题7中的目标函数等同于问题4中的一个，问题4中的拉格朗日函数为：
$L(si,η,βi)=12∣∣si+dix2γi∣∣22−η(siT1−1)−βiTsi(27)\mathcal{L}(s_i,\eta,\beta_i) = \frac{1}{2}||s_i+\frac{d_i^x}{2\gamma^i}||_2^2 -\eta(s_i^T \textbf{1}-1)-\beta_i^Ts_i \tag{27}$
其中 $η$ 和 $β_i≥ 0$ 是拉格朗日乘数。

根据kkt条件，可以验证最优解 $s_{i}$ 应为：
$sij=(−dijx2γi+η)+(28)s_{ij}=(-\frac{d_{ij}^x}{2 \gamma_i} + \eta)_+ \tag{28}$
在实践中，如果我们关注数据的局部性，通常可以获得更好的性能。因此，最好学习稀疏si，即只有xi的k个最近邻居有机会连接到xi。学习稀疏相似矩阵S的另一个好处是，可以大大减轻后续处理的计算负担。

在不损失一般性的情况下，假设 $di1x、di2x、…、dinxd^x_{i1}、d^x_{i2}、…、d^x_{in}$ 从小到大排序。如果最优si仅有k个非零元素，则根据等式28有 $s_{ik}>0 ,s_{i,k+1}=0$ 。因此，我们有：
${−dijx2γi+η>0−dijx2γi+η≤0(29)\begin{cases} & -\frac{d_{ij}^x}{2 \gamma_i} + \eta >0 \\ & -\frac{d_{ij}^x}{2 \gamma_i} + \eta \leq 0 \tag{29} \end{cases}$
根据等式28 以及约束 $siT1=1s_i^T \textbf{1}=1$ 可以得到：
$∑j=1k(−dijx2γi+η)=1⇒η=1k+12kγi∑j=1kdijx(30)\sum _{j=1}^k(-\frac{d_{ij}^x}{2 \gamma_i} + \eta) =1\\ \Rightarrow \eta = \frac{1}{k}+\frac{1}{2k \gamma_i}\sum_{j=1}^k d_{ij}^x \tag{30}$
因此，根据 29和 30，对于 i，我们有以下不等式:
$k2dikx−12∑j=1kdijx≤γi≤k2di,k+1x−12∑j=1kdijx(31)\frac{k}{2} d_{ik}^x - \frac{1}{2} \sum_{j=1}^k d_{ij}^x \leq \gamma_i \leq \frac{k}{2} d_{i,k+1}^x - \frac{1}{2} \sum_{j=1}^k d_{ij}^x \tag{31}$
因此，为了获得具有精确k个非零值的问题4的最优解 $s_i$ ，我们可以设置 $γi\gamma_i$
$γi=k2di,k+1x−12∑j=1kdijk(32)\gamma_i = \frac{k}{2}d_{i,k+1}^x - \frac{1}{2} \sum_{j=1}^k d_{ij}^k \tag{32}$
总 $γ\gamma$ 可以设置为 $γ1,γ2,…,γn\gamma_1,\gamma_2,\dots,\gamma_n$ 的平均值，我们可以将 $γ\gamma$ 设置为：
$γi=1n∑i=1n(k2di,k+1x−12∑j=1kdijk)(33)\gamma_i = \frac{1}{n} \sum_{i=1}^n (\frac{k}{2}d_{i,k+1}^x - \frac{1}{2} \sum_{j=1}^k d_{ij}^k) \tag{33}$
邻域数k比正则化参数γ更容易调整，因为k是一个整数，具有明确的含义。

计算 $s_{ij}$ 过程：
$(28):sij=(−dijx2γi+η)+(30):η=1k+12kγi∑j=1kdijx(32):γi=k2di,k+1x−12∑j=1kdijk\begin{align} & (28):s_{ij}=(-\frac{d_{ij}^x}{2 \gamma_i} + \eta)_+ \\ & (30): \eta = \frac{1}{k}+\frac{1}{2k \gamma_i}\sum_{j=1}^k d_{ij}^x \\ & (32):\gamma_i = \frac{k}{2}d_{i,k+1}^x - \frac{1}{2} \sum_{j=1}^k d_{ij}^k \end{align}$
32带入30：
$η=1k+∑j=1kdijxk2di,k+1x−k∑j=1xdijx=1k(1+∑j=1kdijxkdi,k+1x−∑j=1xdijx),括号里面求和后再乘1k=di,k+1xkdi,k+1x−∑j=1xdijx\begin{align} & \eta = \frac{1}{k} + \frac{\sum_{j=1}^k d_{ij}^x}{k^2 d_{i,k+1}^x-k\sum_{j=1}^xd_{ij}^x} \\ & = \frac{1}{k}(1 + \frac{\sum_{j=1}^k d_{ij}^x}{k d_{i,k+1}^x-\sum_{j=1}^xd_{ij}^x}) ,括号里面求和后再乘\frac{1}{k}\\ & = \frac{ d_{i,k+1}^x}{k d_{i,k+1}^x-\sum_{j=1}^xd_{ij}^x} \end{align}$
将上式以及32带入28可得：
$sij={di,k+1x−dijxkdi,k+1x−∑j=1kdijx,j≤k0,j>ks_{ij}= \begin{cases} \frac{d_{i,k+1}^x-d_{ij}^x}{kd_{i,k+1}^x-\sum_{j=1}^kd_{ij}^x} ,& j \leq k\\ 0, & j>k \end{cases}$

自适应领域投影聚类

目标是找到一个最优子空间，在该子空间上执行自适应邻域，以便在数据中有精确的c连通分量。

总散射矩阵 $S_t=X^T H X$ ，H是16中定义的中心矩阵，假设我们要学习一个投影矩阵 $\in \mathbb{R}^{d \times m}$

我们用 $W^TS_tW=I$ 约束子空间，使得子空间上的数据在统计上不相关。

如等式（5）所示，我们通过解决以下问题为每个数据分配邻居：
$∀i,siT1=1,0≤si≤1,WTStW=I\begin{align} &\min _{S, W} \sum_{i, j=1}^n\left(\left\|W^T x_i-W^T x_j\right\|_2^2 s_{i j}+\gamma s_{i j}^2\right) \tag{34} \\ &\text { s.t. } \quad \forall i, s_i^T \mathbf{1}=1,0 \leq s_i \leq 1, W^T S_t W=I \end{align}$
类似地，为了使邻域分配是自适应的，使得数据中的连通分量是精确的c，我们对秩的S施加约束rank（LS）＝n− c

因此，我们提出了同时学习投影W和聚类的以下问题：
$∀i,siT1=1,0≤si≤1,WTStW=I,rank⁡(LS)=n−c\begin{align} &\min _{S, W} \sum_{i, j=1}^n\left(\left\|W^T x_i-W^T x_j\right\|_2^2 s_{i j}+\gamma s_{i j}^2\right) \tag{35}\\ &\text { s.t. } \quad \forall i, s_i^T \mathbf{1}=1,0 \leq s_i \leq 1, W^T S_t W=I, \operatorname{rank}\left(L_S\right)=n-c \end{align}$

对问题35的优化

使用与2.1小节相同的技巧，我们知道解决问题（35）等同于解决以下问题
$i,siT1=1,0≤si≤1,WTStW=I,F∈Rn×c,FTF=I\begin{align} \min _{S, W, F} & \sum_{i, j=1}^n\left(\left\|W^T x_i-W^T x_j\right\|_2^2 s_{i j}+\gamma s_{i j}^2\right) +2 \lambda T r\left(F^T L_S F\right) \tag{36} \\ \text { s.t. } \quad & \quad i, s_i^T \mathbf{1}=1,0 \leq s_i \leq 1, W^T S_t W=I, F \in R^{n \times c}, F^T F=I \end{align}$
交替优化法：

S,W固定：

问题（36）变成问题（11），最优解F由对应于c个最小特征值的LS的c个特征向量构成。

F固定，36变成：
$∀i,siT1=1,0≤si≤1,WTStW=I\begin{align} \min _{S, W, F} & \sum_{i, j=1}^n\left(\left\|W^T x_i-W^T x_j\right\|_2^2 s_{i j}+\gamma s_{i j}^2\right) +2 \lambda \operatorname{Tr}\left(F^T L_S F\right) \tag{37} \\ \text { s.t. } \quad & \forall i, s_i^T \mathbf{1}=1,0 \leq s_i \leq 1, W^T S_t W=I \end{align}$

在37中，s固定：问题变为：
$min⁡WTStW=I∑i,j=1n∥WTxi−WTxj∥22sij(38)\min _{W^T S_t W=I} \sum_{i, j=1}^n\left\|W^T x_i-W^T x_j\right\|_2^2 s_{i j} \tag{38}$
根据等式6 可重写为：
$min⁡WTStW=ITr⁡(WTXTLSXW)(39)\min _{W^T S_t W=I} \operatorname{Tr}\left(W^T X^T L_S X W\right) \tag{39}$
问题（39）的最优解W由S的m个特征向量构成 $S_t^{-1} X^T L_S X$ (约束中有个 $S_t$ 所以左边要加上逆)对应于m个最小特征值（我们假设数据X的零空间被移除，即St是可逆的）
在37中，w固定：问题变为：
$∀i,siT1=1,0≤si≤1,WTStW=I\begin{align} \min _{S, W, F} & \sum_{i, j=1}^n\left(\left\|W^T x_i-W^T x_j\right\|_2^2 s_{i j}+\gamma s_{i j}^2\right) + \lambda \sum_{i, j=1} ^n||f_i-f_j||_2^2s_{ij} ) \tag{40} \\ \text { s.t. } \quad & \forall i, s_i^T \mathbf{1}=1,0 \leq s_i \leq 1, W^T S_t W=I \end{align}$
请注意，问题（40）在不同的i之间是独立的，因此我们可以针对每个i分别解决以下问题：
$∀i,siT1=1,0≤si≤1,WTStW=I\begin{align} \min _{S, W, F} & \sum_{ j=1}^n\left(\left\|W^T x_i-W^T x_j\right\|_2^2 s_{i j}+\gamma s_{i j}^2\right) + \lambda \sum_{ j=1} ^n||f_i-f_j||_2^2s_{ij} ) \tag{41} \\ \text { s.t. } \quad & \forall i, s_i^T \mathbf{1}=1,0 \leq s_i \leq 1, W^T S_t W=I \end{align}$
记 $dijwx=∣∣xi−xj∣∣22,dijf=∣∣fi−fj∣∣22,diw∈Rn×1d_{ij}^{wx} = ||x_i-x_j||_2^2,d_{ij}^f = ||f_i-f_j||_2^2,d_i^w \in \mathbb{R}^{n \times 1}$ 表示为第j个元素为 $dijw=dijwx+λdijfd_{ij}^w=d_{ij}^{wx}+\lambda d_{ij}^f$ 的向量。问题14可以写成向量的形式：
$min⁡siT1=1,0≤si≤1∑j=1n∣∣si+12γdiw∣∣22(42)\mathop{\min}_{s_i^T \textbf{1}=1,0 \leq s_{i} \leq 1} \sum_{j=1}^{n} ||s_i+\frac{1}{2 \gamma}d_i^w|| _2 ^2\tag{42}$
这与等式（15）中的问题相同，可以用闭式解求解。

算法2中总结了解决问题（35）的详细算法。我们还可以使用等式（33）来确定正则化参数 $γ\gamma$