譜聚類算法

發(fā)布時(shí)間： 2022-05-17 15:08:45

譜聚類算法建立在譜圖理論基礎(chǔ)上，與傳統(tǒng)的聚類算法相比，其具有能在任意形狀的樣本空間上聚類且收斂于全局最優(yōu)解的優(yōu)點(diǎn)?；舅惴ú襟E為：

(1)根據(jù)數(shù)據(jù)構(gòu)造一個(gè)圖，圖的每一個(gè)節(jié)點(diǎn)對(duì)應(yīng)一個(gè)數(shù)據(jù)點(diǎn)，將相似的點(diǎn)連接起來(lái)，并且邊的權(quán)重用于表示數(shù)據(jù)之間的相似度。把這個(gè)圖用鄰接矩陣的形式表示出來(lái)，記為W。

(2)把W的每一列元素加起來(lái)得到N(N為節(jié)點(diǎn)個(gè)數(shù))個(gè)數(shù)，把它們放在對(duì)角線上(其它地方都為0)，組成一個(gè)的矩陣，記為D，并令L=D-W。

(3)求出L的前k個(gè)特征值(按照特征值的大小從小到大的順序)及對(duì)應(yīng)的特征向量。

(4)把這k個(gè)特征(列)向量排列在一起組成一個(gè)N×k的矩陣，將其中每一行看做是k維空間中的一個(gè)向量，并使用k-Means算法進(jìn)行聚類。聚類結(jié)果中的每一行所屬的類別為原來(lái)圖中的節(jié)點(diǎn)，也即最初的N個(gè)數(shù)據(jù)點(diǎn)的類別。

譜聚類算法最初用于計(jì)算機(jī)視覺(jué)、VLSI設(shè)計(jì)等領(lǐng)域，最近才開始用于機(jī)器學(xué)習(xí)中，并迅速成為國(guó)際上機(jī)器學(xué)習(xí)領(lǐng)域的研究熱點(diǎn)。譜聚類算法建立在圖論中的譜圖理論基礎(chǔ)上，其本質(zhì)是將聚類問(wèn)題轉(zhuǎn)化為圖的最優(yōu)劃分問(wèn)題，為一種點(diǎn)對(duì)聚類算法，對(duì)數(shù)據(jù)聚類具有很好的應(yīng)用前景。

您可能也喜歡：