已经介绍了基于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距离的码字作为标签)。
我的理解是：因为考虑到ECOC,码字应该足够长。ECOC本身码字长度和类别数是没有直接关系的，所以我猜测作者的意思可能是第一个特征向量能够单独区分出一个最小类，第二个也能从剩下的一类中单独划分出一个最小类，这么算的话就是k-1。第一个特征向量如何能保证划分出的就是一个最小类呢？这点尚未想通，如有懂的同学欢迎留言。
算法流程
代码下载
下载地址
参考文献
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.