1、譜聚類：是一種基于圖論的聚類方法，通過對樣本數據的拉普拉拉普拉斯矩陣斯矩陣的特征向量特征向量進行聚類。圖（Graph）：由若干點及連接兩點的線所構成的圖形，通常用來描述某些事物之間的某種關系，用點代表事物，線表示對應兩個事物間具有這種關系。123640.20.7Spectral Clustering 譜聚類概念概念圖的表示圖的表示表示 與 之間的關系，稱作權重，對于無向圖jiijwwijwivjv0 0ijiiww而且表示無向圖， 表示點集，E表示邊集),(EVG,.,2,1nvvvV Spectral Clustering 譜聚類1236450.80.8

2、Spectral Clustering 譜聚類圖的劃分圖的劃分圖劃分是指將圖完全劃分為若干個子圖，各子圖無交集同子圖內的點相似度高不同子圖的點相似度低123640.20.7劃分要求劃分要求G1G2GGGk.1jiGGSpectral Clustering 譜聚類劃分時子圖之間被“截斷”的邊的權重和123640.20.7G1G221,21),(GjGiijwGGCut損失函數損失函數Laplacian矩陣矩陣 Gi Gi 2211ccqi221112,21)( 2)(),(21ccqq

3、wwGGCutninjjiijGjGiij損失函數定義 是一個n維向量，用來表示劃分方案,.,21nqqqq Spectral Clustering 譜聚類假設 G(V，E)被劃分成 兩個子圖（設G有n個頂點）21,GG,222111ccccccq ninjjiijqqw112)(ninjjiijninjjiijqqwqqw112211)(2ninjijininjjiijwqqqw1121122qWDqT)(2其中D為對角矩陣njijiiwD1Spectral Clustering 譜聚類ninjjjiiijqqqqw1122)2(Laplacian矩陣矩陣qWDqqqwTninjjiij)(

4、2)(112再定義一個 L 矩陣WDLL 稱為拉普拉斯矩陣，W 為權重矩陣（也稱鄰接矩陣），D 為度矩陣LqqqqwTninjjiij2)(112Spectral Clustering 譜聚類Laplacian矩陣矩陣0)(21112ninjjiijTqqwLqqL為半正定矩陣（即所有特征值非負值），最小特征值為最小特征值為0， 且對應的特征向量為單位向量且對應的特征向量為單位向量T1.1122121)(),(ccLqqGGCutT損失函數損失函數221112,21)(2)(),(21ccqqwwGGCutninjjiijGjGiijSpectral Clustering 譜聚類Laplaci

5、an矩陣矩陣圖的劃分問題轉化為 條件條件最小值問題LqqTSpectral Clustering 譜聚類22121)(),(ccLqqGGCutT條件條件123640.20.712345610.00.10. 020.80.00.80.00.00.00.20.00.040.00.00.20.00.80.750.10.00.00.80.00.860.00.00.0鄰接矩陣W12345611.50.00.00.00.00. 020.01.60.00.00.00.030.00.01.60.00.00.040.

6、00.00.01.70.00.050.00.00.00.01.70.060.00.00.00.00.01.5度矩陣D舉例舉例Spectral Clustering 譜聚類12345610.00.10. 020.80.00.80.00.00.00.20.00.040.00.00.20.00.80.750.10.00.00.80.00.860.00.00.0鄰接矩陣W12345611.50.00.00.00.00. 020.01.60.00.00.00.030.00.01.60.00.00.040.00.00.01.70.00.050.00.

7、00.00.01.70.060.00.00.00.00.01.5度矩陣D12345611.5-0.8-0.60.0-0.10. 02-0.81.6-0.80.00.00.03-0.6-0.81.6-0.20.00.040.00.0-0.21.7-0.8-0.75-0.10.00.0-0.81.7-0.860.00.00.0-0.7-0.81.5拉普拉斯矩陣L=D-WSpectral Clustering 譜聚類舉例舉例Minimum Cut方法方法 Gi c Gi 21cqi)min(LqqT求：條件：212ncqqqniiTSpectral Clustering 譜聚類)min(LqqT2

8、. .ncqqtsTqqLqqqLRTT),(瑞利商:性質： 的最小值，次小值最大值分別在q為L的最小特征值，次小特征值最大特征值對應的特征向量時取得),(qLR求求L次小次小特征值所對應的特征向量特征值所對應的特征向量Spectral Clustering 譜聚類Minimum Cut方法方法 GG12345611.5-0.8-0.60.0-0.10. 02-0.81.6-0.80.00.00.03-0.6-0.81.6-0.20.00.040.00.0-0.21.7-0.8-0.75-0.10.00.0-0.81.7-0.860.00.00.0-0.7-0.81.5拉普拉斯矩陣L12345

9、60.408-0.408-0.408-0.647-0.306-0.3790.1060.408-0.442-0.4420.0140.3050.7060.2150.408-0.371-0.3710.6380.045-0.388-0.3680.4080.3710.3710.339-0.455-0.0010.6120.4080.4050.405-0.167-0.3050.351-0.6520.4080.4450.445-0.1780.716-0.2890.087-0.408-0.408-0.442-0.442-0.371-0.3710.3710.3710.4050.4050.4450.44512364

10、0.20.7G1G2次小次小特征值的特征向量特征值的特征向量Spectral Clustering 譜聚類舉例舉例231640.770.70.6Minimum Cut劃分不均衡Spectral Clustering 譜聚類Minimum Cut方法方法Ratio Cut 方法方法21212111),(),(nnGGCutGGRcut1n、 劃分到子圖1和子圖2的頂點個數2n),(21GGRcut21,1121nnwGjGiij21221,21nnnnnnwGjGiijnnnnnwGjGiij21221,)(212121

11、,)(21nnnnwGjGiij221222121,21nnnnnnnnwGjGiijSpectral Clustering 譜聚類 212121Gi nnnGinnnqi令niiTqqq1221221,21nnnnnnwGjGiij),(21GGRcutLqqqqwTjiGjGiij2,21),(21GGRcutSpectral Clustering 譜聚類2122GiiGiiqq1212121nnnnnnnnRatio Cut 方法方法)min(LqqT1 . .qqtsTqqLqqqLRTT),(瑞利商Spectral Clustering 譜聚類Ratio Cut 方法方法212121

12、11),(),(ddGGCutGGNcut21dd、子圖1和子圖2的權重和LqqqqwGGNcutTjiGjGiij2,2121),( 212121Gi dddGidddqi令Spectral Clustering 譜聚類Normalized Cut 方法方法njijniiTwqDqq112211212GinjijiGinjijiwqwq1221112dddddddd)min(LqqT1 . .DqqtsTDqqLqqqLRTT),(廣義瑞利商Spectral Clustering 譜聚類Normalized Cut 方法方法DqqLqqqLRTT),(廣義瑞利商qDDLq21212121DD

13、D 2121LDDLqDq212121LDDqD21qD21 規范拉普拉斯矩陣，對角元素全為1LSpectral Clustering 譜聚類DqLq為L的廣義特征值IDD2121Normalized Cut 方法方法Ratio cutNcut與與Ratio cut區別區別頂點數權重和1、同子圖內所有點相似度高2、不同子圖的點相似度低Minimum Cut、Ratio cut只考慮了只考慮了1個要求個要求212111),(ddGGCut212111),(nnGGCutNcutNcut考慮了上面考慮了上面2個要求個要求Spectral Clustering 譜聚類Unnormalized Spe

14、ctral Clustering步驟步驟輸入：樣本及類別數K1、根據樣本建立權重矩陣W；2、根據W，計算度矩陣D，進而計算拉普拉斯矩陣L；3、計算L的特征值及特征向量 ；eneevvvVe,., 214、取出前K小特征值對應的特征向量 并對矩陣 的行向量進行聚類，得到K個ClusterekeeKvvvV,., 21KVSpectral Clustering 譜聚類Normalized Spectral Clustering步驟步驟輸入：樣本及類別數K1、根據樣本建立權重矩陣W；4、取出前K小特征值對應的特征向量 并對矩陣 的行向量進行聚類，得到K個ClusterekeeKvvvV,., 21K

15、V譜聚類可以理解為：降維過程+其他聚類方法，最終對 矩陣的行向量聚類時，仍會用其他聚類方法，比如K-meansKN 2、計算拉普拉斯矩陣L及2121LDDL3、計算 的特征值及特征向量 ；eneevvvVe,., 21LSpectral Clustering 譜聚類圖表示圖像圖表示圖像圖像每個像素對應圖的一個頂點252,.,1vvvV 25,251 ,2525,21 ,225,11 ,1.:.wwwwwwW 222)(,jixxjiew為第i和j像素點的灰度值jixx,Spectral Clustering 譜聚類實例實例1、對圖像進行超像素分割；2、根據各超像素區域灰度平均值的相似度計算矩陣W及L；3、計算L的特征值及特征向量 ；eneevvvVe,., 214、取出次小特征值對應的特征向量 ，并對進行K-means聚類， 得到2個Cluster2evSpectral Clustering 譜聚類Spectral Clustering 譜聚類實例實例附加：松弛問題附加：松弛問題)min(LqqT2 . .ncqqtsTqqLqqqLRTT),(瑞利商原問題是離散問題，而瑞利商計算最小值是連續問題 Gi c Gi 21cqi-0.408-0.442-0.3710.3710.4050.445The reaso