譜聚類的推導(dǎo)

1、譜聚類的推導(dǎo)I 兩類別譜聚類樣本集合，輸入空間到特征空間的映射，對(duì)應(yīng)的核函數(shù)，假設(shè)在特征空間中的樣本為規(guī)范化的樣本，即：。K為對(duì)應(yīng)的核矩陣：定義一個(gè)n維樣本聚類標(biāo)示矢量，對(duì)應(yīng)中元素為-1的樣本標(biāo)示為一個(gè)類別，+1的樣本標(biāo)示為另一個(gè)類別。假定兩個(gè)類別的樣本數(shù)量相等，即：選擇類間離散度準(zhǔn)則進(jìn)行優(yōu)化：此準(zhǔn)則的意義是尋找一種對(duì)樣本集合的劃分（由標(biāo)示矢量確定），使得不同類別之間的樣本距離平方和最大。其中用到，。由于，因此優(yōu)化問(wèn)題等價(jià)于最小化：其中第一項(xiàng)與無(wú)關(guān)，因此優(yōu)化問(wèn)題可以表示為矩陣形式：Subject to ，直接求解上述優(yōu)化問(wèn)題是一個(gè)組合優(yōu)化問(wèn)題，屬于NP難題。這里對(duì)上述問(wèn)題進(jìn)行松弛，首先不再要求

2、的元素必須是-1或者+1，同時(shí)也不再要求兩個(gè)類別的樣本數(shù)相等，而是轉(zhuǎn)而約束的長(zhǎng)度為1，這樣上述問(wèn)題可以轉(zhuǎn)化為一個(gè)無(wú)約束的Raleigh商的優(yōu)化問(wèn)題：參考PCA的推導(dǎo)過(guò)程，最優(yōu)矢量為矩陣對(duì)應(yīng)最大特征值的特征矢量。為了最終得到對(duì)樣本的聚類結(jié)果，可以對(duì)中的元素閾值化，大于閾值的對(duì)應(yīng)樣本為一個(gè)類別，小于閾值的對(duì)應(yīng)樣本為另一個(gè)類別。II 多類別譜聚類令為樣本矩陣，每一行一個(gè)樣本，是一個(gè)的矩陣，n為樣本數(shù)，d為特征維數(shù)（可以是無(wú)窮）；是一個(gè)的指派矩陣，m是聚類的個(gè)數(shù)，A的每一行中只有一個(gè)元素為1，其他元素為0，1的位置表示對(duì)應(yīng)樣本被指派到該類別；是一個(gè)的對(duì)角矩陣，其對(duì)角線元素為被指派到對(duì)應(yīng)類別的樣本數(shù)的倒

3、數(shù)，矩陣依賴于矩陣?？梢则?yàn)證維的矩陣的每一列是對(duì)應(yīng)聚類的均值。而維矩陣的每一列為對(duì)應(yīng)樣本被指派聚類的均值。選擇類內(nèi)離散度平方誤差準(zhǔn)則：其中矩陣的范數(shù)采用的是Frobinus范數(shù)，即所有元素的平方和。這一準(zhǔn)則的目標(biāo)是使的所有的樣本到其被指派的聚類中心距離的平方和最小。令為n維的單位矩陣，則有（見附錄1），因此：上式第1項(xiàng)與無(wú)關(guān)，核矩陣，因此優(yōu)化問(wèn)題可以轉(zhuǎn)化為：可以驗(yàn)證，令，則變成如下優(yōu)化問(wèn)題：Subject to 由于，可以證明（見附錄2）：，因此可以對(duì)進(jìn)行優(yōu)化。分別將和寫成行矢量和列矢量的形式：，因此：約束條件表明的列矢量是單位正交矢量，因此引入拉格朗日乘子，建立優(yōu)化準(zhǔn)則函數(shù)：對(duì)的第k個(gè)列矢量

4、求導(dǎo)：其中：，因此有：，所以最優(yōu)解的m個(gè)列是對(duì)應(yīng)于核矩陣最大m個(gè)特征值的特征矢量。而最大值為，是由大到小排列的的特征值（參見PCA的推導(dǎo)）。上述結(jié)論只是表明可以通過(guò)核矩陣的特征值確定聚類的數(shù)目，樣本的具體類別劃分還需要根據(jù)相應(yīng)的特征矢量采用其他方法得到。III 附錄1證明：矩陣是一個(gè)的矩陣，其主對(duì)角線元素是對(duì)應(yīng)樣本所屬類別（第k類別）樣本數(shù)的倒數(shù)，如果第i個(gè)樣本和第j個(gè)樣本屬于不同類別，則第(i,j)元素為0，否則為所屬類別樣本的倒數(shù)。矩陣的主對(duì)角線元素為，其他的0元素仍為0，非零元素變?yōu)?。矩陣的主?duì)角元素為：其他的0元素仍然是0，非0元素為：因此有：IV 附錄2證明：是一個(gè)維的矩陣，是一個(gè)維的矩陣：，因此：計(jì)算可以得到：其中外層（對(duì)k求和）是在對(duì)角線上