拉普拉斯矩阵(Laplace Matrix)与瑞利熵(Rayleigh quotient)

时间:2024-03-26 08:41:36

前言

前面分析了非负矩阵分解(NMF)的应用,总觉得NMF与谱聚类(Spectral clustering)的思想很相似,打算分析对比一下。谱聚类更像是基于图(Graph)的思想,其中涉及到一个重要概念就是拉普拉斯矩阵(Laplace matrix),想着先梳理一下这个矩阵:

  1)拉普拉斯矩阵基本定义

  2)拉普拉斯矩阵意义及性质

  3)瑞利熵(Rayleigh quotient)

内容为自己的学习记录,很多地方都借鉴了别人,最后一并给出链接。

 

一、拉普拉斯矩阵基本定义

对于图G,一般用点的集合V和边的集合E来描述:G(V,E)。现在有这样一个图,如何定义拉普拉斯矩阵呢?这里涉及到两个常用矩阵:邻接矩阵、度矩阵。

拉普拉斯矩阵(Laplace Matrix)与瑞利熵(Rayleigh quotient)

从最简单的应用入手,不同数据点相通权重为1,不相通权重为0.

首先求解邻接矩阵W

拉普拉斯矩阵(Laplace Matrix)与瑞利熵(Rayleigh quotient)

将每一列求和,这个数值的对角形式对应就是度矩阵D

di=∑j=1nwijdi=∑j=1nwij

写成矩阵形式:

D=⎛⎝⎜⎜⎜⎜⎜d1…⋮……d2⋮………⋱dn⎞⎠⎟⎟⎟⎟⎟D=(d1………d2…⋮⋮⋱……dn)

拉普拉斯矩阵(Laplace Matrix)与瑞利熵(Rayleigh quotient)

从而得到拉普拉斯矩阵L的定义:

L=D−WL=D−W

拉普拉斯矩阵(Laplace Matrix)与瑞利熵(Rayleigh quotient)

 

二、拉普拉斯矩阵意义及性质

不失一般性,vivi与vjvj的权重不再是1而是wijwij,f(vi)f(vi)表示节点vivi的函数,对应实际应用它可以是一个概率值、一个像素值等等。

对任意向量ff,

拉普拉斯矩阵(Laplace Matrix)与瑞利熵(Rayleigh quotient)

这样一来,拉普拉斯矩阵的意义就比较明显了,它是一种基于欧式距离的测度,如果wij=1wij=1,上式对应就是多有数据点的距离之和,同时也可以看出:D对应二次项,W对应不同一次项相乘。拉普拉斯矩阵是半正定的,且对应的n个实数特征值都大于等于0,即:0=λ1 ≤λ2 ≤... ≤ λn0=λ1 ≤λ2 ≤... ≤ λn。

 

三、瑞利熵 

提到拉普拉斯矩阵,就不能不提瑞利熵。

  A-普通瑞利熵

给出定义:

拉普拉斯矩阵(Laplace Matrix)与瑞利熵(Rayleigh quotient)

因为对h幅值进行条件,不会影响R的取值,同时也不会改变h向量的方向,对于一般优化问题(以max为例,其他类似):

拉普拉斯矩阵(Laplace Matrix)与瑞利熵(Rayleigh quotient)

可以转化为拉格朗日乘子问题:

拉普拉斯矩阵(Laplace Matrix)与瑞利熵(Rayleigh quotient)

c为常数,即:

拉普拉斯矩阵(Laplace Matrix)与瑞利熵(Rayleigh quotient)

可以看出:

  • R的最大值就是L最大特征值,R的最小值就是L最小特征值
  • h的解,就是L对应的特征向量

是不是很熟悉啊?

  • 简单回顾一下主成分分析(PCA)算法

设p为矩阵A的单位投影矩阵,最大化投影结果:

 拉普拉斯矩阵(Laplace Matrix)与瑞利熵(Rayleigh quotient)

PCA就是瑞利熵理论的一个应用

后面分析谱聚类(Spectral clustering),其中RatioCut算法也是瑞利熵的一个应用。

  B-泛化瑞利熵

 为什么叫泛化呢?对于

拉普拉斯矩阵(Laplace Matrix)与瑞利熵(Rayleigh quotient)

可以看到分子是一般形式,而分母是h∗Dhh∗Dh在D取单位阵时的特殊情况,将其一般化:

拉普拉斯矩阵(Laplace Matrix)与瑞利熵(Rayleigh quotient)

 同理可以得到:

拉普拉斯矩阵(Laplace Matrix)与瑞利熵(Rayleigh quotient)

适当变形:

拉普拉斯矩阵(Laplace Matrix)与瑞利熵(Rayleigh quotient)

这个时候表达式就是:

 拉普拉斯矩阵(Laplace Matrix)与瑞利熵(Rayleigh quotient)

又回到了普通瑞利熵问题,求解就方便了。

  • 简单回顾一下Fisher线性判别分析(Linear discriminant analysis, LDA)算法

Fisher判别准则函数:

拉普拉斯矩阵(Laplace Matrix)与瑞利熵(Rayleigh quotient)

分子分母分别是类内、类间距离。这个准则函数就是泛化瑞利熵的形式。

LDA是泛化瑞利熵的一个应用。 

后面分析谱聚类(Spectral clustering),其中NCut算法也是泛化瑞利熵的一个应用。

 

参考:

瑞利熵:https://en.wikipedia.org/wiki/Rayleigh_quotient

拉普拉斯矩阵:http://www.cnblogs.com/pinard/p/6221564.html