Spectral Grouping Using Nystrom Method

聚类

---

Nystrom extension

Nystrom 方法是用于寻找具有以下格式的特征函数的近似解

$$\int_a^b W(x, y) \phi(y) dy = \lambda \phi(x)$$

在积分区间均匀离散化，得到

$${(b-a)\over n} \sum_{j=1}^{n} W(x,\xi_j) {\hat \phi(\xi_j)} = \lambda {\hat \phi(x)}$$

令$x = \xi_i$

$${(b-a)\over n} \sum_{j=1}^{n} W(\xi_i,\xi_j) {\hat \phi(\xi_j)} = \lambda {\hat \phi(\xi_i)} \quad \forall i \in \{1 \ldots n\}.$$

令$[a, b]$为$[0, 1]$,可以转变为矩阵的特征值问题：

$$A {\hat \Phi} = n {\hat \Phi} \Lambda,$$

其中， $A_{ij} = W(\xi_i,\xi_j)$, $\Phi = [\phi_1, \phi_2, \ldots, \phi_n]$是矩阵A对应特征值的特征向量。

综上，可以得到${\hat \phi_i}$的 Nystrom 扩展表示，

$${\hat \phi_i(x)} = {1\over n \lambda_i}\sum_{j=1}^{n} W(x,\xi_j) {\hat \phi_i(\xi_j)}.$$

表明可以利用采样点的特征向量表示任意点的特征向量。

矩阵实现

如何利用上面的结论实现利用采样点之间的亲密度矩阵A和采样点与测试点之间的亲密度矩阵B，来表示测试点之间的亲密度矩阵？

假设$A=U\Lambda U^T$是$n\times n$的矩阵，B则是$n\times m$的矩阵。利用上面得到的结论，可以得到测试点特征向量的Nystrom扩展矩阵表示：$B^TU\Lambda^{-1}$

将亲密度矩阵表示为：

$$W=\left[\matrix{A&B\cr B^T&C}\right]$$

其特征向量${\bar U}$

$${\bar U} = \left[\matrix{U\cr B^T U\Lambda^{-1} } \right]$$

可利用特征向量表示W的近似

$$\eqalign{{\hat W}&={\bar U}\Lambda{\bar U}^T \cr&=\left[\matrix{U\cr B^T U\Lambda^{-1}}\right] \Lambda [U^T \quad \Lambda^{-1}U^T B] \cr&=\left[\matrix{ U\Lambda U^T & B\cr B^T & B^TA^{-1}B }\right]\cr&=\left[\matrix{A & B\cr B^T & B^TA^{-1}B }\right]\cr&=\left[\matrix{A\cr B^T}\right] A^{-1}[A \quad B].}$$

可看出C的近似为$B^TA^{-1}B$.

此时$\bar U$还不是正交的，需要根据A是否是正定的，进行相应正交化处理。

正交化方法

A正定的情况
定义矩阵$S=A+A^{-1/2}BB^T A^{-1/2}$，其对角化为$S=U_S\Lambda_S U_S^T$
则有$\hat W$可对角化为${\hat W}=V\Lambda_S V^T, V^T V=I$，其中$V$为：

$$V= \left[ \matrix{ A\cr B^T}\right]A^{-1/2}U_S\Lambda_S^{-1/2}$$

给出MATLAB代码

E保存了最后的结果。

A非正定的情况

$$V=ZF\Sigma^{-1/2}$$

$$Z={\bar U}_S\Lambda^{1/2}$$

$${\bar U_S}^T=[U_S^T \quad \Lambda_S^{-1}U_S^T B]$$

$$Z^T Z = F\Sigma F^T$$

Ncut的应用

计算每个节点的度：

$${\hat{ d}}= {\hat W{\bf 1}}= \left[\matrix{A{\bf 1}_n+B{\bf 1}_m\cr B^T{\bf 1}_n+B^TA^{-1}B{\bf 1}_m }\right]=\left[\matrix{{ a}_r+{ b}_r\cr{ b}_c+B^TA^{-1}{ b}_r}\right]$$

其中$a_r, b_r \in {\rm I\kern -2pt R}^m$分别表示矩阵A，B行的和；${ b}_c\in{\rm I\kern -2pt R}^n$表示矩阵B的列的和

对于拉普拉斯矩阵${\hat D}^{-1/2}{\hat W}{\hat D}^{-1/2}$可以从上面的结果中得到：

$$A_{ij} \leftarrow {A_{ij}\over \sqrt{\hat{ d}_i \hat { d}_j}}, \qquad i, j=1,\ldots, n$$

$$B_{ij} \leftarrow {B_{ij}\over \sqrt{\hat {d}_i \hat{ d}_{j+m}}}, \qquad i=1,\ldots, n, j=1,\ldots, m$$

性能

利用Fisher criterion来判断二分图的情况下的分割质量：

$$J({\cal X}_1,{\cal X}_2) = {(\mu_1 - \mu_2)^2\over s_1^2 + s_2^2},$$

其中$\mu_i, s_i^2$分别表示第i类的均值和方差。

efg中的虚线表示dense problem的解的分类效果。可以看出，样本越多，效果越好；距离R越大，效果越好。

从图中可以看出，稀疏方法(前两个)对问题本身可分性非常敏感。Nystrom速度较快，几乎不受影响。虚线是dense solver的时间，仅作为参考。

采样

通过选择两个不同的随机采样集，通过比较两个特征向量的结果来确定到底需要多少样本才能得到一个稳定的结果。

对于不同的特征向量$U, V$计算F范数内积来衡量重复性。

$$\eqalign{&{1\over 2 N_E}\|UR_1R_1^TU^T - VR_2R_2^TV^T\|^2_{\cal F}\cr&= {1\over 2 N_E}\|UU^T - VV^T\|^2_{\cal F} \cr&= {1\over 2 N_E}\|UU^T\|^2_{\cal F} + {1\over 2 N_E}\|VV^T\|^2_{\cal F} - {1\over N_E}\|U^TV\|^2_{\cal F} \cr&= 1 - {1\over N_E}\|U^TV\|^2_{\cal F}.}$$

由上面公式，特征向量的旋转不影响，主要是$U,V$构成的特征向量空间。

对于$240\times 360 = 38400$图片的结果，结果1表明完全相同，那么从上图来看，400个样本点几乎足够了，所需要的样本数几乎在1%左右！

颜色和纹理图片划分

$\chi^2$检验是比较两个直方图的简单而有效的方法，对于颜色和纹理的划分有非常鲁棒的效果。对于归一化直方图$h_i(k), h_j(k)$

$$\chi^2_{ij} = {1\over 2}\sum_{k=1}^K {(h_i(k)-h_j(k))^2\over h_i(k)+h_j(k)},$$

为了防止$h_i(k)=0$的情况出现，每一个空的bin都会加上一个小数$\epsilon$

从而定义亲密度矩阵$W_{ij} = e^{-\chi^2_{ij}/\alpha}$，可以证明这个核是正定的。

参考文献

[1].Fowlkes C, Belongie S, Chung F, et al. Spectral grouping using the Nystrom method[J]. IEEE transactions on pattern analysis and machine intelligence, 2004, 26(2): 214-225.