谱聚类
谱聚类概括的说是基于图论的聚类方法，通过样本矩阵的拉普拉斯矩阵的特征向量进行聚类。
谱聚类的想法是将图划分成若干子图，要求同一个子图的点相似度高，不同子图的点相似度低。
顺便复习一下相似度（距离）的度量公式：
闵可夫斯基距离MinKowski(欧氏距离)：(dist(X,Y)=left ( sum_{i=1}^{n}left | x_{i}-y_{i} ight |^p ight )^frac{1}{p})
杰卡德相似系数Jaccard：(J(A,B)=frac{|Acap B|}{|Acup B|})
余弦相似度：(cos( heta)=frac{a^Tb}{||a||cdot||b||})
皮尔逊相似系数Pearson：( ho _{XY}=frac{cov(X,Y)}{sigma _{X} sigma _{Y}}=frac{E[(X-mu _{X})(Y-mu _{Y})]}{sigma _{X} sigma _{Y}})
相对熵：(D(p||q)=sum_{x}{}p(x)logfrac{p(x)}{q(x)}=E_{p(x)}logfrac{p(x)}{q(x)})
相似度图的(G)的建立方法：
- 全连接图：使用高斯相似度函数：(s(x_{i},x_{j})=e^{-frac{||x_{i}-x_{j}||}{2sigma^2}})
- (varepsilon)近邻图：只留下(varepsilon)范围内的边连接。(varepsilon)值得选择可以采用：1、图(G)边权值的均值。2、图(G)的最小生成树的最大边。
- k近邻图和相互k近邻图
损失函数
如果用(cl_{i})来表示点(i)被划分到的子图，即(cl_{i}=left{egin{matrix} c_{1},iin G_{1}\ c_{2},iin G_{2} end{matrix} ight.)。那么(Cut(G_{1},G_{2}))可以写成： $$Cut(G_{1},G_{2})=sum_{iin G_{1},jin G_{2}}w_{ij}=frac{sum_{i=1}{n}sum_{j=1}{n}w_{ij}(cl_{i}-cl_{j}){2}}{2(c_{1}-c_{2})2} $$
对(sum_{i=1}^{n}sum_{j=1}^{n}w_{ij}(cl_{i}-cl_{j})^{2})进行整理：$$sum_{i=1}{n}sum_{j=1}{n}w_{ij}(cl_{i}-cl_{j}){2}=sum_{i=1}{n}sum_{j=1}{n}w_{ij}(cl_{i}2+cl_{j}^2-2cl_{i}cl_{j})$$
其中(D)被叫做度矩阵，它是一个对角矩阵，(D_{ii}=sum_{j=1}^{n}w_{ij})，(W)是邻接矩阵，令(L=D-W)，称(L)为拉普拉斯矩阵。
求(Cut(G_{1},G_{2}))的最小值，由于 (2(c_{1}-c_{2})^2)是常数，只需求(min(cl^TLcl))
(R(cl,L)=frac{cl^TLcl}{cl^Tcl})是瑞利商（Rayleigh quotient），根据Rayleigh商的性质：(R(cl,L))最小值，次最小值，...，最大值分别在(cl)为(L)的最小特征值，次最小特征值，...，最大特征值对应的特征向量时取得。
于是对于(k)聚类，将(L)最小(k)个特征值对应的特征向量组成(n imes k)的矩阵(V_{k})，然后对(V_{k})的行向量进行聚类。
谱聚类相当于先对原数据降维，再进行聚类。
以上是谱聚类的Minimum Cut方法，还有Ratio Cut方法控制子图的顶点数尽量平均，Ncut方法控制子图的权重分布。
参考资料：
对目标函数的求解过程：https://wenku.baidu.com/view/36f06d78a32d7375a5178025.html
http://www.cnblogs.com/sparkwen/p/3155850.html