谱类聚
谱类聚是用与解决图的划分问题，将无向图划分为两个或者两个以上的最优子图，使子图内部尽量相似，子图间的距离尽量远，谱类聚的最优目标通常有两个准则：比例割集准则（ratio cut），规范化割集准则（normalized cut）。
R a t i o C u t ( π ) = 1 k ∑ i = 1 k c u t ( c i , c i ‾ ) ∣ c i ∣ Ratio Cut(\pi) =\frac{1}{k}\sum_{i=1}^k \frac{cut(c_i , \overline{c_i} )}{| c_i|} RatioCut(π)=k1i=1∑k∣ci∣cut(ci,ci)
N o r m a l i z e d C u t ( π ) = 1 k ∑ i = 1 k c u t ( c i , c i ‾ ) v o l ( c i ) Normalized Cut(\pi)=\frac{1}{k}\sum_{i=1}^{k} \frac{ cut ( c_i,\overline{c_i} ) }{ vol(c_i) } NormalizedCut(π)=k1i=1∑kvol(ci)cut(ci,ci)
谱类聚的两种划分：
理论基础
对于如下空间向量：
如果要对item进行类聚，使用k-mean时，复杂度为o(t k n m),t为迭代次数，k为分类个数，n为item个数，m为特征数。
图的表示
如果，我们计算出item之间的相似度，便可以得到一个只有item的相似矩阵，把item看作为图中的节点，item之间的相似度.
对于图的表示通常有 邻接矩阵和拉普拉斯矩阵。
拉普拉斯矩阵：L=D-E， 其中D为对角矩阵，di为节点i的度。
特征值与L矩阵
在定义割集准则时我们定义了一个cut函数来表达对分成两个子集造成的损失。cut函数的值为为了分成两个子集所割掉边的加权和。
c u t ( S , T ) = ∑ e e i j cut(S,T)=\sum_{e}e_{ij} cut(S,T)=e∑eij
q为n维向量用来表示i节点的分类，用于类标识
假设二分成两类，S和T，用q(如公式2所示)表示分类情况，且q满足公式3的关系，用于类标识。
那么：
有:
- L为对称半正定矩阵，保证所有特征值都大于等于0；
- L矩阵有唯一的0特征值，其对应的特征向量为1。 L矩阵有唯一的0特征值，其对应的特征向量为1。
离散求解q很困难，如果将问题松弛化为连续实数值，由瑞利熵的性质知其二将你型的最小值就是L的特征值们(最小值，第二小值，…，最大值分别对应矩阵L的最小特征值，第二小特征值，…，最大特征值，且极值q相应的特征向量处取得，请参见瑞利熵(Rayleigh quotient))。
将离散的聚类问题，松弛为连续的特征向量，最小的系列特征向量对应着图最优的系列划分方法。剩下的仅是将松弛化的问题再离散化，即将特征向量再划分开，便可以得到相应的类别，如将图3中的最小特征向量，按正负划分，便得类{A,B,C}和类{D,E,F,G}。在K分类时，常将前K个特征向量，采用kmeans分类。
优化方法
Normalized Cut方法
同时考虑最小化cut 和划分平衡,衡量标准为子图各断电的度的和。
令拉普拉斯矩阵为：
L = I − D − 1 / 2 A D − 1 / 2 L=I-D^{-1/2}AD^{-1/2} L=I−D−1/2AD−1/2
Ratio Cut 方法
Ratio cut的目标是同时考虑最小化cut边和划分平衡，以免像图1中的cut出一个单独的子集。
拉普拉斯矩阵为：
L = D − A L=D-A L=D−A
谱类聚的步骤
- 数据准备，生成图的邻接矩阵；
- 归一化普拉斯矩阵；归一化普拉斯矩阵；
- 生成最小的k个特征值和对应的特征向量；3.生成最小的k个特征值和对应的特征向量；
- 将特征向量kmeans聚类(少量的特征向量)；将特征向量kmeans聚类(少量的特征向量)；