作者：桂。

時(shí)間：2017-04-13 ?07:43:03

鏈接：http://www.cnblogs.com/xingshansi/p/6702188.html?

聲明：歡迎被轉(zhuǎn)載，不過記得注明出處哦~

---

前言

前面分析了非負(fù)矩陣分解（NMF）的應(yīng)用，總覺得NMF與譜聚類（Spectral clustering）的思想很相似，打算分析對比一下。譜聚類更像是基于圖（Graph）的思想，其中涉及到一個(gè)重要概念就是拉普拉斯矩陣（Laplace matrix），想著先梳理一下這個(gè)矩陣：

　　1）拉普拉斯矩陣基本定義

　　2）拉普拉斯矩陣意義及性質(zhì)

　　3）瑞利熵（Rayleigh quotient）

內(nèi)容為自己的學(xué)習(xí)記錄，很多地方都借鑒了別人，最后一并給出鏈接。

?

一、拉普拉斯矩陣基本定義

對于圖G，一般用點(diǎn)的集合V和邊的集合E來描述：G（V,E）。現(xiàn)在有這樣一個(gè)圖，如何定義拉普拉斯矩陣呢？這里涉及到兩個(gè)常用矩陣：鄰接矩陣、度矩陣。

從最簡單的應(yīng)用入手，不同數(shù)據(jù)點(diǎn)相通權(quán)重為1，不相通權(quán)重為0.

首先求解鄰接矩陣W：

將每一列求和，這個(gè)數(shù)值的對角形式對應(yīng)就是度矩陣D：

$d_i = \sum\limits_{j=1}^{n}w_{ij}$

寫成矩陣形式：

$\mathbf{D} = \left( \begin{array}{ccc} d_1 & \ldots & \ldots \\ \ldots & d_2 & \ldots \\ ? \vdots & \vdots & \ddots \\ ? \ldots & \ldots & d_n \end{array} \right)$

從而得到拉普拉斯矩陣L的定義：

$L= D-W$

?

二、拉普拉斯矩陣意義及性質(zhì)

不失一般性，$v_i$與$v_j$的權(quán)重不再是1而是$w_{ij}$，$f(v_i)$表示節(jié)點(diǎn)$v_i$的函數(shù)，對應(yīng)實(shí)際應(yīng)用它可以是一個(gè)概率值、一個(gè)像素值等等。

對任意向量$f$，

這樣一來，拉普拉斯矩陣的意義就比較明顯了，它是一種基于歐式距離的測度，如果$w_{ij} = 1$，上式對應(yīng)就是多有數(shù)據(jù)點(diǎn)的距離之和，同時(shí)也可以看出：D對應(yīng)二次項(xiàng)，W對應(yīng)不同一次項(xiàng)相乘。拉普拉斯矩陣是半正定的，且對應(yīng)的n個(gè)實(shí)數(shù)特征值都大于等于0，即：$0 =\lambda_1　\leq \lambda_2　 \leq...　 \leq　 \lambda_n$。

?

三、瑞利熵?

提到拉普拉斯矩陣，就不能不提瑞利熵。

　　A-普通瑞利熵

給出定義：

因?yàn)閷幅值進(jìn)行條件，不會(huì)影響R的取值，同時(shí)也不會(huì)改變h向量的方向，對于一般優(yōu)化問題（以max為例，其他類似）：

可以轉(zhuǎn)化為拉格朗日乘子問題：

c為常數(shù)，即：

可以看出：

• R的最大值就是L最大特征值，R的最小值就是L最小特征值
• h的解，就是L對應(yīng)的特征向量

是不是很熟悉啊？

• 簡單回顧一下主成分分析（PCA）算法：

設(shè)p為矩陣A的單位投影矩陣，最大化投影結(jié)果：

?

PCA就是瑞利熵理論的一個(gè)應(yīng)用。

后面分析譜聚類（Spectral clustering），其中RatioCut算法也是瑞利熵的一個(gè)應(yīng)用。

　　B-泛化瑞利熵

?為什么叫泛化呢？對于

可以看到分子是一般形式，而分母是${{h^*}Dh}$在D取單位陣時(shí)的特殊情況，將其一般化：

?同理可以得到：

適當(dāng)變形：

這個(gè)時(shí)候表達(dá)式就是：

?

又回到了普通瑞利熵問題，求解就方便了。

• 簡單回顧一下Fisher線性判別分析（Linear discriminant analysis, LDA）算法：

Fisher判別準(zhǔn)則函數(shù)：

分子分母分別是類內(nèi)、類間距離。這個(gè)準(zhǔn)則函數(shù)就是泛化瑞利熵的形式。

LDA是泛化瑞利熵的一個(gè)應(yīng)用。?

后面分析譜聚類（Spectral clustering），其中NCut算法也是泛化瑞利熵的一個(gè)應(yīng)用。

?

參考：

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

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

總結(jié)

以上是生活随笔為你收集整理的拉普拉斯矩阵（Laplace Matrix）与瑞利熵（Rayleigh quotient）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。