Clustering Algorithm
Clustering Algorithm
这篇博文解决了马毅老师《GPCA》新书中第四章的下面的问题：
我把实现如下算法的几个都放在了自己的github主页：代码链接下载地址
函数解释文档解释文档链接地址
Laplacian Eigenmaps (LE)
LE算法的思路就是局部点之间的距离保持不变，进而使投影之后的结果也是保举的，和LPP的思路类似。其优化目标如下：
而对于W公式的构造有三种方法：
K-NN affinity:对于N*N的W矩阵，设置某个点i与其他所有的N个点中距离最小的K个点$W_{ij}$设置为1，其余点设置为0；
Gaussian affinity: $w_{ij}=exp(-||x_i-x_j||_2^2/2\theta ^2)$,并且$\theta$通常设置为1.0；
$\epsilon$-neighborhood:就是将距离小于$\epsilon$的$W_{ij}$设置为1，其余的设置为0；
我们如何分析这个优化问题呢？可以通过以下变形得知：
即最小化问题变成(约束条件由马毅老师的handnotes可知)：
将优化问题改写成为拉格朗日函数：
经过求解可知，$YL=\Lambda YD$,进而推出$YLY^T=\Lambda YDY^T=\Lambda$,所以最优化的解变为$trace(YLY^T)=trace(\Lambda)$。这就是为什么算法流程图里面是求（L,D）的最小的d个特征值对应的特征向量。
算法流程图：
K-means Clustering
K-means算法的思路就是通过最小化所有数据点到离他最近的聚类中心的距离之和，并通过这个来估计聚类中心，并进行聚类。其优化目标如下：
其中，当数据点j的最近的聚类中心点i时，$W_{ij}=1$，其他的为0。$u_i$为聚类中心。
算法流程图：
Spectral Clustering
谱聚类的算法实际上就是基于图论的聚类方法，学习一个合适的非线性的映射，使得映射后的数据点可用k-means进行更好的分类。
对于每一个connected graph，我们都可以写出一个如下的表达式，这也是使得这n个graph聚类的思路。因此我们要找到n个使得$LX=0X$的特征向量。但是实际中，需要找到n个最小的特征值对应的特征向量。
算法流程图：
MinCut问题：
实际上，n个connected graphs之间，也有极其小的连接，因此我们还需要度量不同subgraph之间的连接。优化目标如下：
因此，优化目标可以改写成：
RatioCue问题：
但是我们会发现这样的优化目标最后会导致每一个数据点成了一个subgraph，因此我们需要加一个约束项使得这种情况不会发生。
其中：
因此最终的优化问题又变成了：
Normalized Cut & Normalized Spectral Clustering
用拉格朗日解最后的方程得到$Lf=\lambda Df$,这是一个广义特征值问题，因此我们求这个表达式最小的n个广义特征值对应的广义特征向量。这是NCut问题的解法。
另一种解法是令$T=D^{1/2}F$,因此优化问题变成了解以下目标函数：
即求$D^{-1/2}LD^{-1/2}$的最小的n个特征值对应的特征向量问题。
