Roaming about Clustering II Spectral Clustering

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坐标系下为
Cartesian
Hessian矩阵的迹
Hessian
可表现由物质不均引起的物质输送

数学意义

一维空间:
One-dimensional
按照泰勒展开:
taylor
可得: laplace算子是一个使函数取平均的算子

拉普拉斯算子在图像处理的运用

离散形式
离散形式
进行图像锐化:在边缘检测中十分有用,对孤立点或端点更加敏感,增加灰度反差,使模糊图像更加清晰
过程 : 使用拉普拉斯对原图像进行处理再叠加

拉普拉斯矩阵

图的度矩阵-图的邻近矩阵

  • 图的相关概念
  1. 对于临接图A,B W(A,B)=所有i属于A,j属于B的Wij之和(不相交W=0)
  2. 与某节点度d为 其他所有节点与此节点的权重之和
  • 特征
  1. L为对称半正定矩阵
  2. L 1 = 0 1,即最小特征值为0,对应特征向量为1
    important
    问题变成了一个如何分割图的问题(mincut problem)
    mincut
    含义: 要将一个图分为k组,cost即为进行分割时去掉的边的权重的总和(缺点:例如二分类时,导致一个点为一组,其他的点为一组)就要进行改造
    RatioCut
    RatioCut
    含义: 越小的组权重越高,也就是增加一个惩罚因子(缺点:这貌似是一个指数型的问题,需要在转化成多项式复杂度)
    NCut
    ……(详见下方证明之后)
    证明方法
    prove
    (qi-qj为边加权后的权值,statement
    qT q = n
    由瑞利熵的性质得到L的特征值们(最小值,第二小值,……,最大值分别对应矩阵L的最小特征值,第二小特征值,……,最大特征值,且极值q相应的特征向量处取得
    MinCut
    直接得到:Mincut
    NormarlizedCut
    考虑到最小化cut和划分平衡
    RatioCut
    RadioCut2
    Normarlized相似变化
    归一化L矩阵:Normarlized
    L‘的最小特征值与 D(-1/2)ED(1/2)的最大特征值相对应(一般用L’替代L,但min cut和ratio cut不可以)

谱聚类具体步骤

生成邻接矩阵
归一化拉普拉斯矩阵
生成k min 特征值和对应的特征向量
将拉普拉斯矩阵kmeans聚类

意义

将极大的矩阵降维处理,减小了计算量,(个人猜测:同时避免了过拟合??)

钱湦钜<br>方向ML,DL,数学渣<br>爱好骑行,远行<br>Qian Shengju