From Wikipedia, the free encyclopedia
譜聚類(英文:Spectral clustering)係一種聚類分析方法,要聚類嘅對象着視為一幅圖啲綟,啲對象之間嘅距離或者嘸相似度係着表示成圖啲綟之間啲加有權嘅檠。譜聚類係基於圖論對於個拉氏矩陣嘅分析結果,個拉氏矩陣對應返啲圖係有隻連通元件。由於矩陣啲特徵值亦都喊做頻譜,所以種方法喊做譜聚類。譜聚類嘅圖論理論基礎係由 Donath & Hoffman (1973) 同 Fiedler (1973) 奠定嘅。[1][2]
喺第一步,個圖着縮減,而個目的係從圖裏便鏟走所有啲權重(象徵距離)太大嘅檠。以下係啲方法:
透過檠權重可以幫個對象整出(加權)鄰接矩陣。次數矩陣入便,對角線上包含有通向綟啲檠嘅權重總和(喺圖縮減之後)。係噉計得出三種拉氏矩陣:
對於所有啲向量有:
由於拉氏矩陣係對稱同埋半正定嘅,所有特徵值都係實值而且大於或者等於零。對於拉氏矩陣,可以證明至少有一個特徵值係零。若果個圖由隻連通元件整出,係噉拉氏矩陣就係一個壆矩陣(Block矩陣,見上高幅圖同埋矩陣)。每一壆都有一個等於零嘅特徵值。對於特徵值係零嘅特徵向量必須有。因爲所有啲檠權重係正嘅,一隻連通元件啲綟所有都必須相同(所以有)。對於都有類似分析,唯有係特徵向量入便啲欄係由加權,而對於特徵向量啲欄係等於1。
對於聚類,分析拉氏矩陣啲最細特徵值同埋特徵向量。
嘸同嘅譜聚類演算法有着開發出嚟:
非歸一化譜聚類:
Shi佮Malik嘅歸一化譜聚類:[4]
Ng、Jordan佮Weiss嘅歸一化譜聚類 :[5]
關於過程參數同演算法嘅揀選,Ulrike von Luxburg個教程推薦係: [6]
Iris花數據集,係Sir Ronald Fisher爵士 (1936) 作爲判別分析嘅例使用到嘅。[7]有時,個數據集亦都着喊做「Anderson's Iris花數據集」,因為Edgar Anderson收集唨啲數據嚟量化Iris花嘅形態變化。[8]個數據集由 50 隻標本組成,每隻標本分為三隻物種:Iris setosa、Iris versicolor、Iris virginica。分別有測量到萼片同花瓣嘅長度同埋寬度,所以個數據集包含有150個觀察值同埋4個變量。
就好似喺散佈圖矩陣個左便(第一幅)圖形見到噉,三種類型之一(圖形中啲紅色)戥其他類型顯著嘸同。另外兩個物種互相之間好難分開。中間(第二幅)圖形顯示對象之間啲歐氏距離嘅灰度熱圖。灰色越深,對象離得越近。呢啲對象經已係噉重新排列法,即戥其他對象有相似距離嘅對象互相之間擺近。使用到嘅軟件用層次聚類嘅方法並顯示到個樹狀結構圖(Dendrogram)。右便(第三幅)圖形顯示到譜聚類嘅結果。可以睇得出,啲聚類戥三種類型有一定嘅一致性。
左便兩幅圖像顯示到k-nn 圖或者普通 k-nn 圖裏便係邊啲檠着保留到(黑色)或者嘸着保留到(白色)。對於參數,最長檠首先係喺最細生成樹中着確定到,然之後幫所有觀察值計出對應嘅鄰舍數。平均值大概係 60 個鄰舍,係噉揀。之後計拉氏矩陣同埋矩陣啲特徵值。特徵值圖顯示到喺第二個或者第三個特徵值之後有好大跳躍。然之後對前三枚特徵向量進行3聚類嘅 k平均聚類。
種 | 聚類結果 | ||
---|---|---|---|
1 | 2 | 3 | |
setosa | 0 | 0 | 50 |
versicolor | 43 | 7 | 0 |
virginica | 7 | 43 | 0 |
個混淆矩陣表明到譜聚類喺某種程度上重新發現過啲物種。譜聚類法完全正確噉分出Setosa聚類;喺 Versicolor同Virginica聚類嘅情況下有7 個觀測值各自捱錯誤噉分類到,對應嘅錯誤分類率係。
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.