拉普拉斯矩阵（Laplacian Matrix）

系统管理员 2021-09-25 01:38 2012阅读 0赞

### 文章目录 ###

*  1. 无向加权图  G G G
 *  2. 邻接矩阵  W W W
 *  3. 度矩阵  D D D
 *  4. 拉普拉斯矩阵  L L L
 *  参考

# 1. 无向加权图  G G G #

图  G G G，一般用顶点集  V V V 和顶点之间的边集  E E E 表示，  
 G = ( V , E ) . G=(V,E). G=(V,E).  
其中， V = \{ v 1 , v 2 , … , v n \} V=\\\{v\_1,v\_2, \\dots, v\_n\\\} V=\{ v1,v2,…,vn\}， E = \{ ⟨ v i , v j ⟩ ∣ i , j = \[ 1   . .   n \] \} E=\\\{\\langle v\_i, v\_j \\rangle \\mid i, j = \[1 \\text\{ \}.. \\text\{ \}n\] \\\} E=\{ ⟨vi,vj⟩∣i,j=\[1 .. n\]\}， ⟨ v i , v j ⟩ \\langle v\_i, v\_j \\rangle ⟨vi,vj⟩ 表示顶点  v i v\_i vi 和顶点  v j v\_j vj 之间的边。

定义  w i j w\_\{ij\} wij 为边  ⟨ v i , v j ⟩ \\langle v\_i, v\_j \\rangle ⟨vi,vj⟩ 的权重。  
对于有边连接的顶点  v i v\_i vi 和顶点  v j v\_j vj， w i j > 0 w\_\{ij\} > 0 wij>0；对于没有边连接的顶点  v i v\_i vi 和顶点  v j v\_j vj， w i j = 0 w\_\{ij\}=0 wij=0。  
对于无向加权图， w i j = w j i w\_\{ij\}=w\_\{ji\} wij=wji， w i i = 0 w\_\{ii\}=0 wii=0。

# 2. 邻接矩阵  W W W #

将  G G G 使用邻接矩阵来表示，得到  W W W，定义为：  
 W = ( w 11 w 12 … w 1 n w 21 w 22 … w 2 n ⋮ ⋮ ⋱ ⋮ w n 1 w n 2 … w n n ) W=\\begin\{pmatrix\} w\_\{11\} & w\_\{12\} & \\dots & w\_\{1n\} \\\\ w\_\{21\} & w\_\{22\} & \\dots & w\_\{2n\} \\\\ \\vdots & \\vdots & \\ddots & \\vdots \\\\ w\_\{n1\} & w\_\{n2\} & \\dots & w\_\{nn\} \\\\ \\end\{pmatrix\} W=⎝⎜⎜⎜⎛w11w21⋮wn1w12w22⋮wn2……⋱…w1nw2n⋮wnn⎠⎟⎟⎟⎞

# 3. 度矩阵  D D D #

对于  G G G 中任意一个顶点  v i v\_i vi， i ∈ \[ 1   . .   n \] i \\in \[1 \\text\{ \}..\\text\{ \} n\] i∈\[1 .. n\]，它的度定义为和它相连的所有边的权重之和，即  
 d i = ∑ j = 1 n w i j d\_i = \\sum\_\{j=1\}^\{n\} w\_\{ij\} di=j=1∑nwij

利用顶点的度，可以得到一个度矩阵  D D D，定义为：  
 D = ( d 1 … … … d 2 … ⋮ ⋱ ⋮ … … d n ) D=\\begin\{pmatrix\} d\_1 & \\dots & \\dots \\\\ \\dots & d\_2 & \\dots \\\\ \\vdots & \\ddots & \\vdots \\\\ \\dots & \\dots & d\_n \\\\ \\end\{pmatrix\} D=⎝⎜⎜⎜⎛d1…⋮……d2⋱………⋮dn⎠⎟⎟⎟⎞  
 D D D 是一个  n × n n \\times n n×n 的矩阵，并且是一个对角矩阵，只有主对角线的元素非零，其他元素全为零。主对角线上第  i i i 个值对应  d i d\_i di。

# 4. 拉普拉斯矩阵  L L L #

拉普拉斯矩阵  L L L，定义为：  
 L = D − W L = D - W L=D−W

L L L 具有的性质：

1.   D D D 和  W W W 是对称矩阵，因此  L L L 也是对称矩阵；
2.  由于  L L L 是对称矩阵，则它的所有特征值都是实数；
3.  对于任意的向量  f f f，有：  
     f T L f = 1 2 ∑ i , j = 1 n w i j ( f i − f j ) 2 f^\\text\{T\}Lf = \\frac\{1\}\{2\} \\sum\_\{i,j=1\}^\{n\} w\_\{ij\} (f\_i - f\_j)^2 fTLf=21i,j=1∑nwij(fi−fj)2
4.   L L L 是半正定的，且对应的  n n n 个实数特征值都大于 0，即  0 = λ 1 ≤ λ 2 ≤ … λ n 0= \\lambda\_1 \\leq \\lambda\_2 \\leq \\dots \\lambda\_n 0=λ1≤λ2≤…λn，且最小的特征值为 0。

对于第 3 点性质，可以很容易得到。

**推导：**  
 L L L 是一个  n × n n \\times n n×n 的矩阵，则不妨设  
 f = \[ f 1 f 2 … f n \] T f = \\begin\{bmatrix\} f\_1 & f\_2 & \\dots & f\_n \\end\{bmatrix\}^\\text\{T\} f=\[f1f2…fn\]T，则  f T = \[ f 1 f 2 … f n \] f^\\text\{T\} = \\begin\{bmatrix\} f\_1 & f\_2 & \\dots & f\_n \\end\{bmatrix\} fT=\[f1f2…fn\]，  
有  
 ⇒ f T D = \[ f 1 f 2 … f n \] ⋅ \[ d 1 … … … … d 2 … … ⋮ ⋮ ⋱ ⋮ … … … d n \] = \[ f 1 d 1 f 2 d 2 … f n d n \] \\Rightarrow \\begin\{aligned\} f^\\text\{T\}D &= \\begin\{bmatrix\} f\_1 & f\_2 & \\dots & f\_n \\end\{bmatrix\} \\cdot \\begin\{bmatrix\} d\_1 & \\dots & \\dots & \\dots \\\\ \\dots & d\_2 & \\dots & \\dots \\\\ \\vdots & \\vdots & \\ddots & \\vdots \\\\ \\dots & \\dots & \\dots & d\_n \\\\ \\end\{bmatrix\} \\\\ &= \\begin\{bmatrix\} f\_1 d\_1 & f\_2 d\_2 & \\dots & f\_n d\_n \\\\ \\end\{bmatrix\} \\end\{aligned\} ⇒fTD=\[f1f2…fn\]⋅⎣⎢⎢⎢⎡d1…⋮……d2⋮………⋱………⋮dn⎦⎥⎥⎥⎤=\[f1d1f2d2…fndn\]

⇒ f T D f = \[ f 1 d 1 f 2 d 2 … f n d n \] ⋅ \[ f 1 f 2 … f n \] = ( f 1 2 d 1 + f 2 2 d 2 + ⋯ + f n 2 d n ) = ∑ i = 1 n f i 2 d i \\Rightarrow \\begin\{aligned\} f^\\text\{T\}Df &= \\begin\{bmatrix\} f\_1 d\_1 & f\_2 d\_2 & \\dots f\_n d\_n \\end\{bmatrix\} \\cdot \\begin\{bmatrix\} f\_1 \\\\ f\_2 \\\\ \\dots \\\\ f\_n \\\\ \\end\{bmatrix\} \\\\ & = \\left(f\_1^2 d\_1 + f\_2^2 d\_2 + \\dots + f\_n^2 d\_n\\right) \\\\ & = \\sum\_\{i=1\}^\{n\} f\_i^2 d\_i \\end\{aligned\} ⇒fTDf=\[f1d1f2d2…fndn\]⋅⎣⎢⎢⎡f1f2…fn⎦⎥⎥⎤=(f12d1\+f22d2\+⋯\+fn2dn)=i=1∑nfi2di

⇒ f T W = \[ f 1 f 2 … f n \] ⋅ \[ w 11 w 12 … w 1 n w 21 w 22 … w 2 n ⋮ ⋮ ⋱ ⋮ w n 1 w n 2 … w n n \] = \[ f 1 w 11 + f 2 w 21 + ⋯ + f n w n 1 f 1 w 12 + f 2 w 22 + ⋯ + f n w n 2 ⋮ f 1 w 1 n + f 2 w 2 n + ⋯ + f n w n n \] T = \[ ∑ i = 1 n f i w i 1 ∑ i = 1 n f i w i 2 ⋯ ∑ i = 1 n f i w i n \] \\Rightarrow \\begin\{aligned\} f^\\text\{T\}W & = \\begin\{bmatrix\} f\_1 & f\_2 & \\dots & f\_n \\end\{bmatrix\} \\cdot \\begin\{bmatrix\} w\_\{11\} & w\_\{12\} & \\dots & w\_\{1n\} \\\\ w\_\{21\} & w\_\{22\} & \\dots & w\_\{2n\} \\\\ \\vdots & \\vdots & \\ddots & \\vdots \\\\ w\_\{n1\} & w\_\{n2\} & \\dots & w\_\{nn\} \\\\ \\end\{bmatrix\} \\\\ &= \\begin\{bmatrix\} f\_1 w\_\{11\} + f\_2 w\_\{21\} + \\dots + f\_n w\_\{n1\} \\\\ f\_1 w\_\{12\} + f\_2 w\_\{22\} + \\dots + f\_n w\_\{n2\} \\\\ \\vdots \\\\ f\_1 w\_\{1n\} + f\_2 w\_\{2n\} + \\dots + f\_n w\_\{nn\} \\\\ \\end\{bmatrix\}^\\text\{T\} \\\\ & = \\begin\{bmatrix\} \\sum\_\{i=1\}^\{n\} f\_i w\_\{i1\} & \\sum\_\{i=1\}^\{n\} f\_i w\_\{i2\} & \\cdots & \\sum\_\{i=1\}^\{n\} f\_i w\_\{in\} \\\\ \\end\{bmatrix\} \\end\{aligned\} ⇒fTW=\[f1f2…fn\]⋅⎣⎢⎢⎢⎡w11w21⋮wn1w12w22⋮wn2……⋱…w1nw2n⋮wnn⎦⎥⎥⎥⎤=⎣⎢⎢⎢⎡f1w11\+f2w21\+⋯\+fnwn1f1w12\+f2w22\+⋯\+fnwn2⋮f1w1n\+f2w2n\+⋯\+fnwnn⎦⎥⎥⎥⎤T=\[∑i=1nfiwi1∑i=1nfiwi2⋯∑i=1nfiwin\]

⇒ f T W f = \[ ∑ i = 1 n f i w i 1 ∑ i = 1 n f i w i 2 … ∑ i = 1 n f i w i n \] ⋅ \[ f 1 f 2 … f n \] = f 1 ∑ i = 1 n f i w i 1 + f 2 ∑ i = 1 n f i w i 2 + … f n ∑ i n f i w i n = ∑ j = 1 n f j ∑ i = 1 n f i w i j = ∑ j = 1 n ∑ i = 1 n f i f j w i j = ∑ i = 1 n ∑ j = 1 n f i f j w i j \\Rightarrow \\begin\{aligned\} f^\\text\{T\}Wf &= \\begin\{bmatrix\} \\sum\_\{i=1\}^\{n\} f\_i w\_\{i1\} & \\sum\_\{i=1\}^\{n\} f\_i w\_\{i2\} & \\dots & \\sum\_\{i=1\}^\{n\} f\_i w\_\{in\} \\end\{bmatrix\} \\cdot \\begin\{bmatrix\} f\_1 \\\\ f\_2 \\\\ \\dots \\\\ f\_n \\\\ \\end\{bmatrix\} \\\\ & = f\_1 \\sum\_\{i=1\}^\{n\} f\_i w\_\{i1\} + f\_2 \\sum\_\{i=1\}^\{n\} f\_i w\_\{i2\} + \\dots f\_n \\sum\_\{i\}^\{n\} f\_i w\_\{in\} \\\\ &= \\sum\_\{j=1\}^\{n\} f\_j \\sum\_\{i=1\}^\{n\} f\_i w\_\{ij\} \\\\ & = \\sum\_\{j=1\}^\{n\} \\sum\_\{i=1\}^\{n\} f\_i f\_j w\_\{ij\} \\\\ & = \\sum\_\{i=1\}^\{n\} \\sum\_\{j=1\}^\{n\} f\_i f\_j w\_\{ij\} \\\\ \\end\{aligned\} ⇒fTWf=\[∑i=1nfiwi1∑i=1nfiwi2…∑i=1nfiwin\]⋅⎣⎢⎢⎡f1f2…fn⎦⎥⎥⎤=f1i=1∑nfiwi1\+f2i=1∑nfiwi2\+…fni∑nfiwin=j=1∑nfji=1∑nfiwij=j=1∑ni=1∑nfifjwij=i=1∑nj=1∑nfifjwij

因此，  
 ⇒ f T L f = f T ( D − W ) f = f T D f − f T W f = ∑ i = 1 n f i 2 d i − ∑ j = 1 n ∑ i = 1 n f i f j w i j = 1 2 ( ∑ i n f i 2 d i − 2 ∑ i = 1 n ∑ j = 1 n f i f j w i j + ∑ j = 1 n f j 2 d j ) = 1 2 ∑ i = 1 n ∑ j = 1 n w i j ( f i − f j ) 2 \\Rightarrow \\begin\{aligned\} f^\\text\{T\} L f & = f^\\text\{T\}(D - W) f \\\\ &= f^\\text\{T\} D f - f^\\text\{T\} W f \\\\ &= \\sum\_\{i=1\}^\{n\} f\_i^2 d\_i - \\sum\_\{j=1\}^\{n\} \\sum\_\{i=1\}^\{n\} f\_i f\_j w\_\{ij\} \\\\ & = \\frac\{1\}\{2\} \\left(\\sum\_\{i\}^\{n\} f\_i^2 d\_i - 2 \\sum\_\{i=1\}^\{n\}\\sum\_\{j=1\}^\{n\} f\_i f\_j w\_\{ij\} + \\sum\_\{j=1\}^\{n\} f\_j^2 d\_j\\right) \\\\ & = \\frac\{1\}\{2\} \\sum\_\{i=1\}^\{n\} \\sum\_\{j=1\}^\{n\} w\_\{ij\} (f\_i - f\_j)^2 \\end\{aligned\} ⇒fTLf=fT(D−W)f=fTDf−fTWf=i=1∑nfi2di−j=1∑ni=1∑nfifjwij=21(i∑nfi2di−2i=1∑nj=1∑nfifjwij\+j=1∑nfj2dj)=21i=1∑nj=1∑nwij(fi−fj)2

# 参考 #

1.  [刘建平Pinard：谱聚类（spectral clustering）原理总结][Pinard_spectral clustering]
2.  [文墨：谱聚类算法(Spectral Clustering)][Spectral Clustering]

[Pinard_spectral clustering]: https://www.cnblogs.com/pinard/p/6221564.html
[Spectral Clustering]: https://www.cnblogs.com/sparkwen/p/3155850.html