2011 [AISTATS] Dimensionality Reduction for Spectral Clustering [cited 72]

在处理大数据时，抽样和降维是两种常用的方法，但是二者的目的的方法却从来都大相径庭。抽样的目的是，在一定的聚类结果准确度的衡量标准下（如 A Tutorial on the Spectral Clustering Section 8中用图的分割理论），以牺牲尽可能小的准确度的代价，换取尽可能大程度的计算代价的减小。而降维是针对高位非线性空间中的数据点作为算法的输入时，输出结果将非常差甚至完全失效的情况。如果高维向量直接作为谱聚类的输入，会出现严重的问题：

1，在一定的数据分布和采用给定的距离函数时，高维向量之间的距离趋于常数，如此，将无法构造近邻相似度图。

参考1999 [ICDT] When is nearest neighbor meaningful（被引用1301次，是近邻图和高维空间方面很重要的研究）

2， 谱聚类对噪声和不重要的维非常敏感，而维度越高，如此影响聚类结果的因素越多。

参考2006 [JMLR] Learning Spectral Clustering, With Application To Speech Separation

2011年发表在AISTATS上的这篇 Dimensionality Reduction for Spectral Clustering介绍了一种无监督的降维方法，并应用到谱聚类上。该算法（USDR）的基础是SDR（Sufficient Dimension Reduction）算法，最初在 2002 [Springer Annals of the Institute of Statistical] Sufficient Dimension Reduction and Graphics in Regression 上被提出，2005年也曾在另一篇文章中详细介绍过。

首先简单看看Sufficient Dimension Reduction的原理。

考虑回归。给定包含数据点X和类标签Y的训练集，要通过回归的方法训练出来一个分类器。给定一个映射$ \beta = ({\beta}_1,{\beta}_2,\cdots,{\beta}_m )$，将X映射到一个子空间里的投影是 ${\beta}X$，可知 $Y$ 和 $X|{\beta}X$ 是独立随机变量。如此，则 $Y|X$ 和 $Y|{\beta}X$ 是一样的（服从相同的概率分布）。因此，使用B作X的映射，并没有让数据集丢失任何预测信息，却达到的降维的目的。

Well，所谓不丢失预测信息，也就是说，实际上，对X作这样的数据压缩，必然导致信息的丢失，但是就分类这个问题上，这种压缩并不会对类标签Y的分布起到任何影响。

于是降维问题就化成了如何求满足以上条件的映射B。

（Question：以上用例子确实能验证，但是理论推导呢？）

有了这个论断，就可以进行监督（Y是已知的）的降维了。但是在谱聚类中，算法的全部过程都是无监督的（此时Y是聚类得到的类标签，在聚类结束前是未知的）。但是可以将SDR的方法用到无监督的降维方法上，得到USDR（Unsupervised SDR）。

1，USDR

对SDR而言，Y是必要的输入。所以在USDR中，通过一定的criterion functions来学习Y。交互信息（mutual information是什么？）是一种衡量随机变量X,Y的标准函数，但是这需要获知X,Y的联合概率分布。USDR使用的是 Hilbert-Schmidt Independence Criterion（HSIC）。

HSIC函数如下：

$HSIC(X,U)=(n-1)^{-2}tracert(K_1HK_2H)$

$K_1$和$K_2$是核格拉姆矩阵，$K_{1,ij}=k_1(x_i, x_j)$，$K_{2,ij}=k_2(u_i, u_j)$，$H$是定心矩阵（centering matrix，上周的日志FASP中有提到）。为计算方便，假设$K_1$,$K_2$已经中心化，并且忽略$(n-1)^{-2}$，于是：

$HSIC(X,U)=tracert(K_1K_2)$

令$K_1=D^{-1/2}WD^{-1/2}$，$K_2=UU^T$，$K$是相似度矩阵，于是：

$HSIC(X,U)=tracert(U^{T}D^{-1/2}WD^{-1/2}U)$

DRSC的目的，是将数据映射到一个线性子空间，然后对投影数据实施谱聚类算法。由于降维和聚类是使用相同目标函数的优化问题，因此可以将两个过程合二为一。

这个过程可以通过一个协调升算法实现（coordinate ascent algorithm是什么？）：

1，固定W，求U

固定W，可得到相似度矩阵K和度矩阵D，如此求得$L_{sym}=I-D^{-1/2}KD^{-1/2}$，U的m个列向量即是Lsym的m个特征向量。

2，固定U，求W

固定U，U的每一行实际上是每个数据点的spectral embedding（因此才作为K-Means算法的输入），我们通过一个升维算法来求得W。首先，令子空间的维度为1，w1。用梯度上升方法优化w1（w1当时归一化向量）；然后将子空间维度设为2，并利用梯度上升方法求w2，w2被随机地初始化，然后映射到一个和w1正交的子空间上，然后归一化。w2的梯度可分解成两部分：

$ \nabla f=\nabla f_{proj}+\nabla f_\bot $

$\nabla f_{proj}$是$\nabla f$在基为w1,w2的子空间上的投影，$ \nabla f_\bot $和$\nabla f_{proj}$正交，且是归一化的。通过以下式子，迭代求解w2：

[{w_{{rm{2,new}}}}{rm{ = }}sqrt {1 - {gamma ^2}} {w_{2,old}}{rm{ + }}gamma nabla {f_ bot }]

用这个式子还可求得w2，w3，...，wq。

算法过程如下：

通过一个迭代的过程，同时求解U和W，随后通过K-Means聚类即可。

此外，文章还提供了相应的高斯核方法。

实验部分：分别用人造数据和真实数据做了实验，和PCA等方法做比较。用人造数据的缘原因是希望更清晰地反映算法的聚类效果。

人造数据实验结果：

真实数据实验结果：

问题： 1，文章对于算法收敛的证明缺失。

2，coordinate ascent algorithm是什么？

3，只清楚梯度下降方法，梯度上升方法是什么？