Ng大神等人提出的Spectral CLustering非常有意思，证明看得我很惊…
巧妙地利用了矩阵的特征，实现了降维，这是一个启发，如何应用好那些简单基础的数学模型
虽然现在paper里的模型越来越复杂，但我们是不是可以换个角度来思考，从最基础的层面重新想一想？
可惜数学基础还不够好orz 233,这篇就当是补一下线代的知识，顺便证明下这个谱聚类
当然，我觉得这个证明中最重要的，是运用矩阵特征值这一点，值得学一蛤
说到矩阵
矩阵基础
- 矩阵是线性空间里的变换的描述，相似矩阵是对同一个线性变换的不同描述
- 基：坐标系
- 相似矩阵即对一个线性变换在不同基下的不同描述
- 矩阵可以描述线性变换，还可以描述基
- Ma=b，a经过M变换或者由基的变换,单位坐标系即为（I）
- b在I坐标系为Ib ，a 在M坐标系里是Ma
- 逆矩阵
- 点积（直接对应相乘）+ 几何定义
- 特征值: A v = X v （v为A的一个特征向量，X对应特征值)
- 迹（各个特征值之和）
拉普拉斯
拉普拉斯方程
解为调和函数(?)
即为算子右边为0,为laplace方程，此时解为调和函数，右边是一个函数，则为泊松方程
拉普拉斯算子
Laplace算子的定义为梯度的散度
在Cartesian坐标系下为
Hessian矩阵的迹
可表现由物质不均引起的物质输送
数学意义
一维空间：
按照泰勒展开:
可得: laplace算子是一个使函数取平均的算子
拉普拉斯算子在图像处理的运用
离散形式
进行图像锐化：在边缘检测中十分有用,对孤立点或端点更加敏感,增加灰度反差,使模糊图像更加清晰
过程 : 使用拉普拉斯对原图像进行处理再叠加
拉普拉斯矩阵
图的度矩阵-图的邻近矩阵
- 图的相关概念
- 对于临接图A，B W(A,B)=所有i属于A，j属于B的Wij之和（不相交W=0）
- 与某节点度d为 其他所有节点与此节点的权重之和
- 特征
- L为对称半正定矩阵
- L 1 = 0 1，即最小特征值为0，对应特征向量为1
问题变成了一个如何分割图的问题(mincut problem)
含义： 要将一个图分为k组,cost即为进行分割时去掉的边的权重的总和(缺点：例如二分类时，导致一个点为一组，其他的点为一组)就要进行改造
RatioCut
含义： 越小的组权重越高，也就是增加一个惩罚因子（缺点：这貌似是一个指数型的问题，需要在转化成多项式复杂度）
NCut
……（详见下方证明之后）
证明方法：
（qi-qj为边加权后的权值，
）
qT q = n
由瑞利熵的性质得到L的特征值们(最小值，第二小值，……，最大值分别对应矩阵L的最小特征值，第二小特征值，……，最大特征值，且极值q相应的特征向量处取得
MinCut
直接得到:
NormarlizedCut
考虑到最小化cut和划分平衡
RatioCut
Normarlized相似变化
归一化L矩阵:
L‘的最小特征值与 D（-1/2）ED（1/2）的最大特征值相对应(一般用L’替代L，但min cut和ratio cut不可以)
谱聚类具体步骤
生成邻接矩阵
归一化拉普拉斯矩阵
生成k min 特征值和对应的特征向量
将拉普拉斯矩阵kmeans聚类
意义
将极大的矩阵降维处理,减小了计算量,（个人猜测：同时避免了过拟合？？)