Multiway Spectral Clustering with Out-of-Sample Extensions through Weighted Kernel PCA

聚类

---

已经介绍了基于WKPCA的谱聚类算法,下面将其推广到多路谱聚类，并给出编码体制。

知识预备

需要先掌握KPCA和Spectral Clustering，这篇文章是博客的进一步延伸和扩展，强烈建议结合上一篇，这篇和上一篇相同或相似的细节不再重复。

算法原理

将度矩阵的逆作为加权矩阵，并引入正则项、特征维向量、偏置项，将导出以下优化问题：

$$\min_{w^{(l)}, e^{(l)}, b_l}\;{1\over 2N} \sum_{l=1}^{n_e}\gamma_l e^{{(l)}^T}D^{-1}e^{(l)}-{1\over 2} \sum_{l=1}^{n_e}w^{{(l)}^T}w^{(l)}$$

$${\rm such\; that}\; \left\{\matrix{ e^{(1)}=\Phi w^{(1)}+b_1 1_N, \cr e^{(2)}=\Phi w^{(2)}+b_2 1_N, \cr \vdots \cr e^{(n_e)}=\Phi w^{(n_e)}+b_{n_e}1_N .}\right.$$

每一个特征维向量$e^{(l)}$根据簇标识$q^{(l)}= sign(e^{(l)})$提供二分类的依据。

类似的，用Lagrangian解最优化问题：

$$\eqalign{{\cal L}(w^{(l)}, e^{(l)}, b_l;\alpha^{(l)})&={1\over 2} \sum_{l=1}^{n_e}\gamma_l e^{{(l)}^T}D^{-1}e^{(l)}-{1\over 2} \sum_{l=1}^{n_e}w^{{(l)}^T}w^{(l)}\cr &\quad -\sum_{l=1}^{n_e}\alpha^{{(l)}^T}\big (e^{(l)}-\Phi w^{(l)}-b_l 1_N\big),}$$

当满足以下条件时最优：

$$\left\{\matrix{ \displaystyle{\partial {\cal L}\over \partial w^{(l)}} =0 \rightarrow w^{(l)}=\Phi^T\alpha^{(l)}, \cr \displaystyle{\partial {\cal L}\over \partial e^{(l)}} =0 \rightarrow \alpha^{(l)}={{\gamma_l}\over{N}} D^{-1}e^{(l)},\cr \displaystyle{\partial {\cal L}\over \partial b_l} =0 \rightarrow 1_N^T\alpha^{(l)}=0\cr \displaystyle{\partial {\cal L}\over \partial \alpha^{(l)}} =0 \rightarrow e^{(l)}=\Phi w^{(l)}+b_l 1_N, }\right.$$

其中$l = 1, ...n_e$

可以计算出偏置项为：

$$b_l=-{1\over 1_N^T D^{-1} 1_N} 1_N^T D^{-1} \Omega \alpha^{(l)}, l=1,\ldots, n_e$$

消除 $w^(l), e^(l), b_l$得到特征值分解问题：

$$D^{-1}M_{D}\Omega \alpha^{(l)}=\lambda_l\alpha^{(l)}$$

其中$\lambda _l = {N \over \gamma _l}, l=1,...,n_e$

$$M_{D}=I_{N}-{1\over 1_N^TD^{-1}1_N} 1_N1_N^TD^{-1}$$

测试数据$x$的特征维基为:

$$z^{(l)}(x)=\sum_{i=1}^{N}\alpha_{i}^{(l)}K(x_{i}, x)+b_{l}, l=1,\ldots, n_{e}.$$

训练数据中的特征维坐标向量的符号和特征方程的特征向量的符号是一致的。即：

$${\rm sign}(e_i^{(l)})={\rm sign}(\alpha_i^{(l)}), i=1,\ldots, N, l=1,\ldots, n_e.$$

对于测试数据，特征维空间的的坐标向量为：

$$z^{(l)}=\Omega_{{\rm test}}\alpha^{(l)}+b_l1_{N_{{\rm test}}}, l=1,\ldots, n_e.$$

其类别划分(需要结合下面的编\解码模块)规则如下：

$${\rm sign}(z^{(l)})={\rm sign}(\Omega_{{\rm test}}\alpha^{(l)}+b_l1_{N_{{\rm test}}}), l=1,\ldots, k-1$$

编\解码

对于不同的簇$A_p, p = 1, ...,k$，使用码字$c_p \in \{-1, 1\}^{n_e}$来实现(码字的长度为$n_e$)。以上就是编码簿的框架。
具体的编码簿是通过训练数据得到的：对于训练数据指示器，通过上面的分析即$[sign(\alpha ^{(1)}), ..., sign(\alpha ^{(n_e)})]$。对于上面引入的偏置项也就是数据均值为0，使得这一步实现非常方便，否则这里是不成立的。
对于特征向量数量 $n_e$ 的选择：原本中的描述是：(因为第一个特征向量实现了二分类，所以为了编码 $k$ 个簇需要特征向量的数量 $n_e= k-1$。解码则是需要计算编码簿的聚类知识器 ，选择最小的Hamming距离的码字作为标签)。
在参考文献2中，给出了更加详细的解释。对偶问题的矩阵$D^{-1}M_{D}\Omega$在特征值为1时，有k-1个分段特征向量。编码簿$CB=\{c_p\}_{p=1}^k$可以从训练过程中获得的投影矩阵的行得到，即$[sign(e ^{(1)}), ..., sign(e ^{(k)})]$,因为$\alpha^{(1)}$已经提供了二分类，所以k-1个投影变量足够编码k个簇。
我的理解是：因为考虑到ECOC,码字应该足够长。ECOC本身码字长度和类别数是没有直接关系的，所以我猜测作者的意思可能是第一个特征向量能够单独区分出一个最小类，第二个也能从剩下的一类中单独划分出一个最小类，这么算的话就是k-1。第一个特征向量如何能保证划分出的就是一个最小类呢？

算法流程

![算法][1]

BLF

利用特征空间的特征相连的分段常量特性，有队验证集$D^v$的划分$\Delta =\{{\cal A}_1,\ldots, {\cal A}_k\}, k>2$平均线性度量

$${\rm linefit}({\cal D}^v, k)={1\over k} \sum_{p=1}^k {k-1\over k-2} \left ({\zeta_1^{(p)}\over \sum_l\zeta_l^{(p)}} -{1\over k-1} \right)$$

其中，$\zeta_1^{(p)}\ge \cdots \ge \zeta_{k-1}^{(p)}$是协方差矩阵的特征值

$$C_{\tilde{Z}}^{(p)}= {1\over \vert {\cal A}_p\vert } \tilde{Z}^{(p)^T}\tilde{Z}^{(p)}, p=1,\ldots, k$$

其中，$\tilde{Z}^{(p)}\in {{\rm \rlap{I}\kern 2.0pt{{\rm R}}}}^{\vert {\cal A}_p\vert \times (k-1)}$，是验证集划分的$p$簇中归一化矩阵。$\zeta_1^{(p)}/\sum_l\zeta_l^{(p)}$表示最大特征值对应的特征向量包含的方差。如果$p$簇的特征向量是共线的，所有的方差就包含在第一个特征向量中，有。$\zeta_1^{(p)}/\sum_l\zeta_l^{(p)}=1$。另一方面，如果方差平均分布在每一个向量中，$\zeta_1^{(p)}/\sum_l\zeta_l^{(p)}=1/(k-1)$,公式中的多余的项是为了使均匀分布在每一向量中时，linefit为0，$k-1 \over k-2$是保证分布在第一个向量中时，linefit为1。最后再取平均即可。
我觉得作者应该是从KPCA出发的，如果正确划分的话，那么对正确划分的簇做KPCA，主成分应该在最大的特征值对应的特征向量之中。
当$k=2$时，为实现二分类，只需要一个特征向量。考虑数据矩阵$\breve{Z}^v\in {{\rm \rlap{I}\kern 2.0pt{{\rm R}}}}^{N_v \times 2}$，其中第m行第一列元素为投影变量$z_m=\sum_{i=1}^N\alpha_i K(x_i, x_m^v)+b$,第m行第二列元素$\sum_{i=1}^N K(x_i, x_m^v)+b$

$${\rm linefit}\;({\cal D}^v, k)\!=\! \left\{\matrix{ \displaystyle\sum_{p=1}^2\left ({\breve{\zeta }_1^{(p)}\over \breve{\zeta }_1^{(p)}+\breve{\zeta }_2^{(p)}} -{1\over 2} \right) & {\rm if }\; k=2, \cr \displaystyle{1\over k} \sum_{p=1}^k {k-1\over k-2} \left ({\zeta_1^{(p)}\over \sum_l\zeta_l^{(p)}} -{1\over k-1} \right) & {\rm if }\; k>2, }\right.$$

簇的均衡性可以通过以下方法：

$${\rm balance}\;({\cal D}^v, k)={{\rm min} \{\vert {\cal A}_1\vert,\ldots, \vert {\cal A}_k\vert \} \over {\rm max} \{\vert {\cal A}_1\vert,\ldots, \vert {\cal A}_k\vert \} }$$

结合balance和linefit，有

$${\rm BLF}({\cal D}^v, k)=\eta \;{\rm linefit}\;({\cal D}^v, k)+(1-\eta)\;{\rm balance}\;({\cal D}^v, k)$$

其中$\eta$是控制linefit和balance之比的用户定义的参数，$0\le \eta \le 1$

实际代码稍有出入。协方差矩阵使用cov函数直接求，这样的结果是$|A_p-1|$。linefit并不是直接求平均，而是根据最大的特征值求加权平均。balance是求的对数之比。

代码下载

下载地址

参考文献

[1]. Alzate C, Suykens J A K. Multiway spectral clustering with out-of-sample extensions through weighted kernel PCA[J]. IEEE transactions on pattern analysis and machine intelligence, 2010, 32(2): 335-347.

[2].soft kernel clustering