該文章主要整理自珠穆拉瑪峰的文章《從拉普拉斯矩陣說到譜聚類》溅潜，添加了少部分個(gè)人理解的文字和公式推導(dǎo)

該文章同步發(fā)表于 github 和 github homepage

目錄

• 1. 一堆基礎(chǔ)概念
• 2. 拉普拉斯矩陣
• 3. 拉普拉斯矩陣的性質(zhì)
• 4. 譜聚類
  • 4.1. 算法思想及優(yōu)化目標(biāo)
  • 4.2. 構(gòu)造Laplacian圖
  • 4.3. 用Cut/Ratio Cut分割子圖
    • 4.3.1. 優(yōu)化目標(biāo)
    • 4.3.2. 求解優(yōu)化問題：最小化RatioCut與最小化 f'Lf 等價(jià)
• 補(bǔ)充知識
  • *1. 向量的乘法運(yùn)算
    • *1.1. 向量內(nèi)積（點(diǎn)積）
    • *1.2. 向量內(nèi)積的用途
    • *1.3. 向量外積
    • *1.4. 向量外積的用途

1. 一堆基礎(chǔ)概念

• 單位矩陣

  在矩陣中然遏，n階單位矩陣硼瓣，是一個(gè) nxn 的方形矩陣迁匠，其主對角線元素為1，其余元素為0。單位矩陣以 I_n 表示电湘；如果階數(shù)可忽略每庆，或可由前后文確定的話臼疫，也可簡記為I（或者E）。 如下圖所示扣孟，便是一些單位矩陣：

  單位矩陣中的第i列即為單位向量v_i，單位向量同時(shí)也是單位矩陣的特征向量荣赶，特征值皆為1凤价，因此這是唯一的特征值，且具有重?cái)?shù)n拔创。由此可見利诺，單位矩陣的行列式為1，且跡數(shù)為n剩燥。

• 單位向量

  向量空間中的單位向量就是長度為 1 的向量

  兩個(gè)單位向量的點(diǎn)積就是它們之間角度的余弦（因?yàn)樗鼈兊拈L度都是 1）：

  補(bǔ)充知識——向量的乘法運(yùn)算（見后文補(bǔ)充知識）

  一個(gè)非零向量u^→的正規(guī)化向量（即單位向量）u^{^}就是平行于u^→的單位向量慢逾，記作：

  這里||u^→||是u^→的范數(shù)（長度）

• 正交與正交矩陣

  正交是垂直這一直觀概念的推廣，若內(nèi)積空間中兩向量的內(nèi)積（即點(diǎn)積）為0灭红，則稱它們是正交的侣滩，相當(dāng)于這兩向量垂直，換言之变擒，如果能夠定義向量間的夾角君珠，則正交可以直觀的理解為垂直

  正交矩陣（orthogonal matrix）是一個(gè)元素為實(shí)數(shù)，而且行與列皆為正交的單位向量的方塊矩陣（方塊矩陣娇斑，或簡稱方陣策添，是行數(shù)及列數(shù)皆相同的矩陣）

2. 拉普拉斯矩陣

拉普拉斯矩陣（Laplacian matrix)），也稱為基爾霍夫矩陣毫缆，是表示圖的一種矩陣

給定一個(gè)有n個(gè)頂點(diǎn)的圖 G=(V,E)唯竹，其拉普拉斯矩陣被定義為 L = D-A，D其中為圖的度矩陣苦丁，A為圖的鄰接矩陣

例如給定下圖G=(V,E)

把此“圖”轉(zhuǎn)換為鄰接矩陣的形式浸颓，記為A（假設(shè)每條邊的連接權(quán)重均為1）：

把W的每一列元素加起來得到N個(gè)數(shù)，然后把它們放在對角線上（其它地方都是零）芬骄，組成一個(gè)N×N的對角矩陣猾愿，記為度矩陣D，如下圖所示

根據(jù)拉普拉斯矩陣的定義L = D-A账阻，可得拉普拉斯矩陣L 為：

顯然蒂秘，拉普拉斯矩陣都是對稱

3. 拉普拉斯矩陣的性質(zhì)

介紹拉普拉斯矩陣的性質(zhì)之前，首先定義兩個(gè)概念淘太，如下：

1. 對于鄰接矩陣姻僧，定義圖中A子圖與B子圖之間所有邊的權(quán)值之和如下：

其中规丽，定義 w _ij為節(jié)點(diǎn) i 到節(jié)點(diǎn) j 的權(quán)值，如果兩個(gè)節(jié)點(diǎn)不是相連的撇贺，權(quán)值為零

2. 與某結(jié)點(diǎn)鄰接的所有邊的權(quán)值和定義為該頂點(diǎn)的度d赌莺，多個(gè)d 形成一個(gè)度矩陣（對角陣）

拉普拉斯矩陣L具有如下性質(zhì)：

• L 是對稱半正定矩陣；

• L * v₁^→ = 0 * v₁^→松嘶，即 L 的最小特征值是 0艘狭，相應(yīng)的特征向量是 v₁^→

  證明： L * v₁^→ = (D-W) * v₁^→ = 0 = 0 * v₁^→

  特征值和特征向量的定義：

  若數(shù)字λ和非零向量v^→滿足

  則v^→為A的一個(gè)特征向量，λ是其對應(yīng)的特征值

• L 有n個(gè)非負(fù)實(shí)特征值

• 對于任何一個(gè)屬于實(shí)向量 f∈Rⁿ翠订，有以下式子成立

  其中

  下面巢音，來證明下上述結(jié)論，如下：

4. 譜聚類

4.1. 算法思想及優(yōu)化目標(biāo)

譜聚類本質(zhì)上就是將聚類問題轉(zhuǎn)換為圖論問題

從圖論的角度來說尽超，聚類的問題就相當(dāng)于一個(gè)圖的分割問題官撼。即給定一個(gè)圖G = (V, E)，頂點(diǎn)集V表示各個(gè)樣本似谁，帶權(quán)的邊表示各個(gè)樣本之間的相似度傲绣，譜聚類的目的便是要找到一種合理的分割圖的方法，使得分割后形成若干個(gè)子圖巩踏，連接不同子圖的邊的權(quán)重（相似度）盡可能低秃诵，同子圖內(nèi)的邊的權(quán)重（相似度）盡可能高。物以類聚蛀缝，人以群分顷链，相似的在一塊兒，不相似的彼此遠(yuǎn)離屈梁。

至于如何把圖的頂點(diǎn)集分割/切割為不相交的子圖有多種辦法嗤练，如：

• cut/Ratio Cut

• Normalized Cut

• 不基于圖，而是轉(zhuǎn)換成SVD能解的問題

優(yōu)化目標(biāo)為：讓被割掉各邊的權(quán)值和最小

因?yàn)楸豢车舻倪叺臋?quán)值和越小在讶，代表被它們連接的子圖之間的相似度越小煞抬，隔得越遠(yuǎn)，而相似度低的子圖正好可以從中一刀切斷构哺。

4.2. 構(gòu)造Laplacian圖

（1）先要構(gòu)造相似度矩陣革答，任意兩個(gè)對象x_i和x_j，其相似度基于高斯核函數(shù)（也稱徑向基函數(shù)核）計(jì)算相似度定義為：

距離越大曙强，代表其相似度越小

相似度矩陣就是Laplacian圖的鄰接矩陣W

根據(jù)鄰接矩陣W可以得到度矩陣

最后Laplacian矩陣為L=D-W

（2）子圖A的指示向量如下：

4.3. 用Cut/Ratio Cut分割子圖</a>

4.3.1. 優(yōu)化目標(biāo)

如何切割才能得到最優(yōu)的結(jié)果呢残拐？

要把圖片分割為幾個(gè)區(qū)域（或若干個(gè)組），要求是分割所得的 Cut 值最小碟嘴，相當(dāng)于那些被切斷的邊的權(quán)值之和最小

設(shè) A₁, A₂, ..., A_k 為圖的幾個(gè)子集（它們沒有交集） 溪食，為了讓分割的Cut 值最小，譜聚類便是要最小化下述目標(biāo)函數(shù)：

但很多時(shí)候娜扇，最小化cut 通常會導(dǎo)致不好的分割错沃。以分成2類為例栅组，這個(gè)式子通常會將圖分成了一個(gè)點(diǎn)和其余的n-1個(gè)點(diǎn)。如下圖所示枢析，很明顯玉掸，最小化的smallest cut不是最好的cut，反而把{A醒叁、B司浪、C、H}分為一邊把沼，{D断傲、E、F智政、G}分為一邊很可能就是最好的cut：

為了讓每個(gè)類都有合理的大小，目標(biāo)函數(shù)盡量讓 A₁, A₂, ..., A_k 足夠大箱蝠。改進(jìn)后的目標(biāo)函數(shù)為：

其中| A _i |表示 A _i 組中包含的頂點(diǎn)數(shù)目

或者也可以將優(yōu)化目標(biāo)定義為最小化Ncut：

其中

4.3.2. 求解優(yōu)化問題：最小化RatioCut與最小化 f'Lf 等價(jià)

現(xiàn)在來研究一下將圖劃分為兩個(gè)子圖A和A^-的問題

目標(biāo)函數(shù)：

定義向量 f = (f₁, f2₂, ..., f_m ) ∈ R ⁿ续捂，且

根據(jù)之前得到的拉普拉斯矩陣矩陣的性質(zhì)，已知

現(xiàn)在把 f _i 的定義式代入上式宦搬，我們將得到一個(gè)非常有趣的結(jié)論牙瓢！推導(dǎo)過程如下：

我們竟然從 f'Lf 推出了 RatioCut ，換句話說间校，拉普拉斯矩陣L 和我們要優(yōu)化的目標(biāo)函數(shù)RatioCut 有著密切的聯(lián)系矾克，于是我們的優(yōu)化目標(biāo)變成了：

補(bǔ)充知識

*1. 向量的乘法運(yùn)算

*1.1. 向量內(nèi)積（點(diǎn)積）

使用矩陣乘法并把（縱列）向量當(dāng)作n×1 矩陣，點(diǎn)積還可以寫為：

向量內(nèi)積性質(zhì)

向量內(nèi)積的物理意義

向量內(nèi)積的物理意義是憔足，力通過位移做功

*1.2. 向量內(nèi)積的用途

• 求兩個(gè)非零向量的夾角

• 判斷兩個(gè)非零向量是否垂直

  簡單的對應(yīng)坐標(biāo)相乘再求和胁附，結(jié)果為0就垂直，否則就不垂直

*1.3. 向量外積

通過坐標(biāo)進(jìn)行外積的直接計(jì)算比較復(fù)雜滓彰，寫成行列式的形式控妻，再展開，方便記憶

向量外積的性質(zhì)

向量外積的幾何意義

再除以2的話揭绑，就是以 a弓候，b 為邊的三角形的面積

*1.4. 向量外積的用途

求與三角形面積相關(guān)的問題

參考資料：

(1) CSDN·珠穆拉瑪峰《從拉普拉斯矩陣說到譜聚類》

(2) CSDN·鵝城驚喜師爺《【線性代數(shù)】向量的乘法運(yùn)算》

(3) 行者無疆兮.csdn【圖論】拉普拉斯矩陣（Laplacian matrix）