国产一级a片免费看高清,亚洲熟女中文字幕在线视频,黄三级高清在线播放,免费黄色视频在线看

Spectral Clustering（譜聚類）是一種基于圖論的聚類方法，它能夠識別任意形狀的樣本空間且收斂于全局最有解，其基本思想是利用樣本數(shù)據(jù)的相似矩陣進(jìn)行特征分解后得到的特征向量進(jìn)行聚類，可見，它與樣本feature無關(guān)而只與樣本個(gè)數(shù)有關(guān)。

一、圖的劃分

圖劃分的目的是將有權(quán)無向圖劃分為兩個(gè)或以上子圖，使得子圖規(guī)模差不多而割邊權(quán)重之和最小。圖的劃分可以看做是有約束的最優(yōu)化問題，它的目的是看怎么把每個(gè)點(diǎn)劃分到某個(gè)子圖中，比較不幸的是當(dāng)你選擇各種目標(biāo)函數(shù)后發(fā)現(xiàn)該優(yōu)化問題往往是NP-hard的。

怎么解決這個(gè)問題呢？松弛方法往往是一種利器（比如SVM中的松弛變量），對于圖的劃分可以認(rèn)為能夠?qū)⒛硞€(gè)點(diǎn)的一部分劃分在子圖1中，另一部分劃分在子圖2中，而不是非此即彼，使用松弛方法的目的是將組合優(yōu)化問題轉(zhuǎn)化為數(shù)值優(yōu)化問題，從而可以在多項(xiàng)式時(shí)間內(nèi)解決之，最后在還原劃分時(shí)可以通過閾值來還原，或者使用類似K-Means這樣的方法，之后會有相關(guān)說明。

二、相關(guān)定義

1、用

表示無向圖，其中和分別為其頂點(diǎn)集和邊集；

2、說某條邊屬于某個(gè)子圖是指該邊的兩個(gè)頂點(diǎn)都包含在子圖中；

3、假設(shè)邊

的兩個(gè)不同端點(diǎn)為和，則該邊的權(quán)重用表示，對于無向無環(huán)圖有且，為方便以下的“圖”都指無向無環(huán)圖；

4、對于圖的某種劃分方案的

定義為：所有兩端點(diǎn)不在同一子圖中的邊的權(quán)重之和，它可以被看成該劃分方案的損失函數(shù)，希望這種損失越小越好，本文以二分無向圖為例，假設(shè)原無向圖被劃分為和，那么有：

三、Laplacian矩陣

假設(shè)無向圖

被劃分為和兩個(gè)子圖，該圖的頂點(diǎn)數(shù)為：，用表示維指示向量，表明該劃分方案，每個(gè)分量定義如下：

于是有：

又因?yàn)椋?/p>

其中，

為對角矩陣，對角線元素為：

為權(quán)重矩陣：

且。

重新定義一個(gè)對稱矩陣

，它便是Laplacian矩陣：

矩陣元素為：

如果所有權(quán)重值都為非負(fù)，那么就有

，這說明Laplacian矩陣是半正定矩陣；而當(dāng)無向圖為連通圖時(shí)有特征值0且對應(yīng)特征向量為，這反映了，如果將無向圖劃分成兩個(gè)子圖，一個(gè)為其本身，另一個(gè)為空時(shí)，為0(當(dāng)然，這種劃分是沒有意義的)。

這個(gè)等式的核心價(jià)值在于：將最小化劃分

的問題轉(zhuǎn)變?yōu)樽钚』魏瘮?shù)；從另一個(gè)角度看，實(shí)際上是把原來求離散值松弛為求連續(xù)實(shí)數(shù)值。

觀察下圖：

圖1

它所對應(yīng)的

矩陣為：

       [,1] [,2] [,3] [,4] [,5] [,6][1,]  0.0  0.8  0.6  0.0  0.1  0.0[2,]  0.8  0.0  0.8  0.0  0.0  0.0[3,]  0.6  0.8  0.0  0.2  0.0  0.0[4,]  0.0  0.0  0.2  0.0  0.8  0.7[5,]  0.1  0.0  0.0  0.8  0.0  0.8[6,]  0.0  0.0  0.0  0.7  0.8  0.0

矩陣為：

       [,1] [,2] [,3] [,4] [,5] [,6][1,]  1.5  0.0  0.0  0.0  0.0  0.0[2,]  0.0  1.6  0.0  0.0  0.0  0.0[3,]  0.0  0.0  1.6  0.0  0.0  0.0[4,]  0.0  0.0  0.0  1.7  0.0  0.0[5,]  0.0  0.0  0.0  0.0  1.7  0.0[6,]  0.0  0.0  0.0  0.0  0.0  1.5
Laplacian矩陣為：
       [,1] [,2] [,3] [,4] [,5] [,6][1,]  1.5 -0.8 -0.6  0.0 -0.1  0.0[2,] -0.8  1.6 -0.8  0.0  0.0  0.0[3,] -0.6 -0.8  1.6 -0.2  0.0  0.0[4,]  0.0  0.0 -0.2  1.7 -0.8 -0.7[5,] -0.1  0.0  0.0 -0.8  1.7 -0.8[6,]  0.0  0.0  0.0 -0.7 -0.8  1.5

   Laplacian矩陣是一種有效表示圖的方式，任何一個(gè)Laplacian矩陣都對應(yīng)一個(gè)權(quán)重非負(fù)地?zé)o向有權(quán)圖，而滿足以下條件的就是Laplacian矩陣：
 
1、
為對稱半正定矩陣，保證所有特征值都大于等于0；
2、
矩陣有唯一的0特征值，其對應(yīng)的特征向量為
，它反映了圖的一種劃分方式：一個(gè)子圖包含原圖所有端點(diǎn)，另一個(gè)子圖為空。

四、劃分方法

1、Minimum Cut 方法

考慮最簡單情況，另

，無向圖劃分指示向量定義為:

要優(yōu)化的目標(biāo)為

，由之前的推導(dǎo)可以將該問題松弛為以下問題：

從這個(gè)問題的形式可以聯(lián)想到Rayleigh quotient：

原問題的最優(yōu)解就是該Rayleigh quotient的最優(yōu)解，而由Rayleigh quotient的性質(zhì)可知：它的最小值，第二小值，......，最大值分別對應(yīng)矩陣

的最小特征值，第二小特征值，......，最大特征值，且極值

在相應(yīng)的特征向量處取得，即需要求解下特征系統(tǒng)的特征值和特征向量：

這里需要注意約束條件

，顯然的最小特征值為0,此時(shí)對應(yīng)特征向量為，不滿足這個(gè)約束條件(剔除了無意義劃分)，于是最優(yōu)解應(yīng)該在第二小特征值對應(yīng)的特征向量處取得。

當(dāng)然，求得特征向量后還要考慮如何恢復(fù)劃分，比如可以這樣：特征向量分量值為正所對應(yīng)的端點(diǎn)劃分為

，反之劃分為；也可以這樣：將特征向量分量值從小到大排列，以中位數(shù)為界劃分和；還可以用K-Means算法聚類。

2、Ratio Cut 方法

實(shí)際當(dāng)中，劃分圖時(shí)除了要考慮最小化

外還要考慮劃分的平衡性，為緩解出現(xiàn)類似一個(gè)子圖包含非常多端點(diǎn)而另一個(gè)只包含很少端點(diǎn)的情況，出現(xiàn)了Ratio Cut，它衡量子圖大小的標(biāo)準(zhǔn)是子圖包含的端點(diǎn)個(gè)數(shù)。

定義

為子圖1包含端點(diǎn)數(shù)，為子圖2包含端點(diǎn)數(shù)，，則優(yōu)化目標(biāo)函數(shù)為：

其中：

做一個(gè)簡單變換：

其中：

看吧，這形式多給力，原問題就松弛為下面這個(gè)問題了：

依然用Rayleigh quotient求解其第二小特征值及其特征向量。

3、Normalized Cut 方法

與Ratio Cut類似，不同之處是，它衡量子圖大小的標(biāo)準(zhǔn)是：子圖各個(gè)端點(diǎn)的Degree之和。

定義：

為子圖1Degree之和：

為子圖2Degree之和：

則優(yōu)化目標(biāo)函數(shù)為：

其中：

原問題就松弛為下面這個(gè)問題了：

用泛化的Rayleigh quotient表示為：

那問題就變成求解下特征系統(tǒng)的特征值和特征向量：

——式子1

(注：是一個(gè)對角矩陣，且)

(其中：，) ——式子2

顯然，式子1和式子2有相同的特征值，但是對應(yīng)特征值的特征向量關(guān)系為：

，因此我們可以先求式子2的特征值及其特征向量，然后為每個(gè)特征向量乘以就得到式子1的特征向量。

哦，對了，矩陣

叫做Normalized Laplacian，因?yàn)樗鼘蔷€元素值都為1。

五、Spectral Clustering

1、Unnormalized Spectral Clustering算法

3、以圖1為例，取K=2，使用Unnormalized Spectral Clustering算法，此時(shí)聚類的對象其實(shí)就是矩陣L的第二小特征向量(使用R模擬)：

● L矩陣為：
     [,1] [,2] [,3] [,4] [,5] [,6][1,]  1.5 -0.8 -0.6  0.0 -0.1  0.0[2,] -0.8  1.6 -0.8  0.0  0.0  0.0[3,] -0.6 -0.8  1.6 -0.2  0.0  0.0[4,]  0.0  0.0 -0.2  1.7 -0.8 -0.7[5,] -0.1  0.0  0.0 -0.8  1.7 -0.8[6,]  0.0  0.0  0.0 -0.7 -0.8  1.5
● q<-eigen(L) 求得L的特征值和特征向量分別為：
$values[1] 2.573487e+00 2.469025e+00 2.285298e+00 2.084006e+00 1.881842e-01 1.776357e-15$vectors            [,1]          [,2]        [,3]        [,4]       [,5]       [,6][1,] -0.10598786 -0.3788245748 -0.30546656  0.64690880  0.4084006 -0.4082483[2,] -0.21517718  0.7063206485  0.30450981 -0.01441501  0.4418249 -0.4082483[3,]  0.36782805 -0.3884382495  0.04461661 -0.63818761  0.3713186 -0.4082483[4,] -0.61170644 -0.0009962363 -0.45451793 -0.33863293 -0.3713338 -0.4082483[5,]  0.65221488  0.3509689196 -0.30495543  0.16645901 -0.4050475 -0.4082483[6,] -0.08717145 -0.2890305075  0.71581349  0.17786774 -0.4451628 -0.4082483
● q$vectors[,5] 取第二小特征向量：
[1]  0.4084006  0.4418249  0.3713186 -0.3713338 -0.4050475 -0.4451628
● kmeans(q$vectors[,5],2) 利用K-Means算法聚類：
K-means clustering with 2 clusters of sizes 3, 3Cluster means:        [,1]1 -0.40718142  0.4071814Clustering vector:[1] 2 2 2 1 1 1Within cluster sum of squares by cluster:[1] 0.002732195 0.002487796 (between_SS / total_SS =  99.5 %)
從結(jié)果上可以看到頂點(diǎn)1、2、3被聚為一類，頂點(diǎn)4、5、6被聚為一類，與實(shí)際情況相符。

在Mahout中已經(jīng)有相應(yīng)實(shí)現(xiàn)，放在下次學(xué)習(xí)吧。

六、總結(jié)

1、圖劃分問題中的關(guān)鍵點(diǎn)在于選擇合適的指示向量

并將其進(jìn)行松弛化處理，從而將最小化劃分的問題轉(zhuǎn)變?yōu)樽钚』魏瘮?shù)，進(jìn)而轉(zhuǎn)化為求Rayleigh quotient極值的問題；

2、 Spectral Clustering的各個(gè)階段為：

● 選擇合適的相似性函數(shù)計(jì)算相似度矩陣；

●計(jì)算矩陣L的特征值及其特征向量，比如可以用Lanczos迭代算法；
●如何選擇K，可以采用啟發(fā)式方法，比如，發(fā)現(xiàn)第1到m的特征值都挺小的，到了m+1突然變成較大的數(shù)，那么就可以選擇K=m；
● 使用K-Means算法聚類，當(dāng)然它不是唯一選擇；
● Normalized Spectral Clustering在讓Cluster間相似度最小而Cluster內(nèi)部相似度最大方面表現(xiàn)要更好，所以首選這類方法。

六、參考資料

1、Chris Ding.《A Tutorial on Spectral Clustering》、《Data Mining using Matrix and Graphs》

2、Jonathan Richard Shewchuk. 《Spectral and Isoperimetric Graph Partitioning》

3、Denis Hamad、Philippe Biela.《Introduction to spectral clustering》

4、Francis R. Bach、Michael I. Jordan.《Learning Spectral Clustering》

5、丕子.http://www.zhizhihu.com/html/y2010/1141.html