譜ふ聚類

有ゆう兩りょう隻せき連れん通どおり元もと件けん嘅圖

譜ふ聚類（英文えいぶん：Spectral clustering）係がかり一いち種しゅ聚類分析ぶんせき方法ほうほう，要よう聚類嘅對象たいしょう着ぎ視し為ため一いち幅ぶく圖ず啲綟，啲對象たいしょう之の間あいだ嘅距離きょり或ある者もの嘸さぞ相似そうじ度ど係がかり着ぎ表示ひょうじ成なり圖ず啲綟之の間あいだ啲加有權ゆうけん嘅檠。譜ふ聚類係がかり基もと於圖ず論ろん對たい於個拉ひしげ氏し矩のり陣じん嘅分析ぶんせき結果けっか，個こ拉ひしげ氏し矩のり陣じん對應たいおう返かえし啲圖係がかり有ゆう$k$隻せき連れん通どおり元もと件けん。由よし於矩陣じん啲特徵とくちょう值亦また都と喊做頻しき譜ふ，所以ゆえん種しゅ方法ほうほう喊做譜ふ聚類。譜ふ聚類嘅圖論ろん理論りろん基礎きそ係がかり由ゆかり Donath & Hoffman (1973) 同どう Fiedler (1973) 奠定嘅。

數學すうがく基礎きそ

圖ず縮減しゅくげん

喺第一いち步ほ，個こ圖ず着ぎ縮減しゅくげん，而個目的もくてき係がかり從したがえ圖ず裏うら便びん鏟走所有しょゆう啲權重じゅう（象徵しょうちょう距離きょり）太ふとし大だい嘅檠。以下いか係かかり啲方法ほう：

εいぷしろん鄰舍圖ず

若わか果はて某ぼう檠嘅權けん重じゅう大過たいか$\epsilon$，就由圖ず度ど鏟走條じょう檠。

k-nn 圖ず

喺 k-nn 圖ず（$k$最近さいきん鄰舍圖ず）裏うら便びん，一粒綟啲所有檠都根據檠嘅權重排序。有ゆう檠個權けん重じゅう大過たいか第だい$k$個こ最さい細ほそ權けん重じゅう嘅（象徵しょうちょう遠とお過か第だい$k$個こ鄰舍），就着從したがえ圖ず度ど鏟走。個こ$k$ -nn 係がかり嘸さぞ對稱たいしょう嘅，即そく隻せき檠權重おも$w_{ij}$可能かのう對たい於$o_{i}$嚟講係がかり細ほそ過か第だい$k$個こ最さい細ほそ檠權重じゅう，之これ對たい於$o_{j}$又また嘸さぞ細ほそ過か佢個第だい$k$個こ最さい細ほそ檠權重じゅう。得とく喊做係がかり k-nn 圖ず只ただ需要じゅよう到いた條じょう檠保留ほりゅう喺圖裏うら便びん嘅，對たい於$o_{i}$或ある者もの$o_{j}$其中至いたり少しょう一いち個こ對象たいしょう，個こ$w_{ij}$細ほそ過か佢第$k$個こ最さい細ほそ檠權重じゅう，即そく係がかり每ごと個こ對象たいしょう至いたり少しょう有ゆう$k$條じょう檠。相反あいはん，一いち個こ「 佮埋嘅 k-nn 圖ず」只ただ包つつみ含有がんゆう啲檠、啲對於兩個りゃんこ對象たいしょう都みやこ有ゆう$w_{ij}$細ほそ過か$k$個こ最さい細ほそ檠權重じゅう嘅，即そく係がかり每ごと個こ對象たいしょう都と最多さいた有ゆう$k$條じょう檠。

全ぜん連接れんせつ圖ず

藉助相似そうじ度ど函數かんすう，檠權重じゅう係がかり根據こんきょ對象たいしょう之の間あいだ啲距離きょり計けい出だし。相似そうじ度ど函數かんすう嘅一個例係高斯相似度函數$s(o_{i},o_{j})=\exp(-{\tfrac {1}{2}}d^{2}(o_{i},o_{j})/\sigma ^{2})$。參まいり數すう$\sigma$控ひかえ制せい鄰舍大だい細ぼそ似に上高かみたか個こ參さん數すう$\epsilon$或ある者もの$k$噉。

• 
  二に維空間あいだ裏うら便びん8個こ對象たいしょう嘅位置いち。
• 
  全ぜん連接れんせつ圖ず，有ゆう啲帶歐おう氏し距離きょり嘅檠褦住8個こ對象たいしょう。
• 
  8個こ對象たいしょう啲歐氏し距離きょり嘅距離きょり矩のり陣じん。
• 
  $\epsilon$鄰舍圖ず（ $\epsilon =5$） 為ため8個こ對象たいしょう。
• 
  8個こ對象たいしょう個こk-nn 圖ず（$k=2$） 。每まい粒つぶ綟至少しょう有ゆう兩りょう條じょう檠。
• 
  8個こ對象たいしょう個こ普通ふつう k-nn圖ず（ $k=2$）。每まい粒つぶ綟最多た有ゆう兩りょう條じょう檠。數かず據よりどころ集しゅう着ぎ分ぶん成なり三さん隻せき連れん通どおり元もと件けん。
• 
  拉ひしげ氏し矩のり陣じん$L_{rw}$，對たい於8個こ對象たいしょう個こ普通ふつう k-nn 圖ず（$k=2$） 嘅。
• 
  全ぜん連接れんせつ圖ず，有ゆう返かえし啲檠有高ありだか斯相似そうじ度ど函數かんすう值（$\sigma =3$），表示ひょうじ到いた8個こ對象たいしょう。

拉ひしげ氏し矩のり陣じん

透過とうか檠權重おも可か以幫$n$個こ對象たいしょう整せい出で（加か權けん）鄰接矩のり陣じん$W$。次數じすう矩のり陣じん$D$入いれ便びん，對角線たいかくせん上包うわづつみ含有がんゆう通どおり向こう綟啲檠嘅權けん重じゅう總和そうわ（喺圖縮減しゅくげん之これ後ご）。係かかり噉計得とく出で三さん種しゅ拉ひしげ氏し矩のり陣じん：

• 非ひ歸一きいつ化か矩のり陣じん$L=D-W$ ,
• 歸一きいつ化か矩のり陣じん$L_{sym}=D^{-1/2}LD^{-1/2}$
• 歸一きいつ化か矩のり陣じん$L_{rw}=D^{-1}L$ .

對たい於所有しょゆう啲向量りょう$f\in R^{n}$有ゆう：

${\begin{array}{rcll}f^{T}Lf&=&\displaystyle {\tfrac {1}{2}}\sum _{i,j=1}^{n}w_{ij}\left(f_{i}-f_{j}\right)^{2}&\geq 0,\\f^{T}L_{sym}f&=&\displaystyle {\tfrac {1}{2}}\sum _{i,j=1}^{n}w_{ij}\left({\tfrac {f_{i}}{\sqrt {d_{i}}}}-{\tfrac {f_{j}}{\sqrt {d_{j}}}}\right)^{2}&\geq 0.\\f^{T}L_{rw}f&=&\displaystyle {\tfrac {1}{2}}\sum _{i,j=1}^{n}w_{ij}\left(f_{i}-f_{j}\right)^{2}&\geq 0\\\end{array}}$

由よし於拉氏し矩のり陣じん係がかり對稱たいしょう同どう埋うめ半はん正せい定じょう嘅，所有しょゆう特徵とくちょう值都係がかり實じつ值而且大於或者しゃ等とう於零。對たい於拉氏し矩のり陣じん，可か以證明しょうめい至いたり少しょう有ゆう一いち個こ特徵とくちょう值係零れい。若わか果はて個こ圖ず由ゆかり$k$隻せき連れん通どおり元もと件けん整せい出で，係かかり噉拉氏し矩のり陣じん就係一いち個こ壆矩陣じん（Block矩のり陣じん，見上みかみ高だか幅はば圖ず同どう埋うめ矩のり陣じん）。每まい一壆都有一個等於零嘅特徵值。對たい於特徵ちょう值係零れい嘅特徵しるし向むこう量りょう必須ひっす有ゆう$f^{T}Lf=0$。因よし爲ため所有しょゆう啲檠權けん重じゅう$w_{ij}$係かかり正せい嘅，一隻連通元件啲綟所有$f_{i}$都と必須ひっす相しょう同どう（所以ゆえん有ゆう$f_{i}-f_{j}=0$）。對たい於$L_{sym}$都みやこ有ゆう類似るいじ分析ぶんせき，唯ただ有ゆう係がかり特徵とくちょう向むこう量りょう入いれ便びん啲欄係がかり由ゆかり$d_{i}$加か權けん，而對於$L_{rw}$特徵とくちょう向むこう量りょう啲欄$f_{i}$係かかり等とう於1。

對たい於聚類るい，分析ぶんせき拉ひしげ氏し矩のり陣じん啲最細ほそ特徵とくちょう值同埋うめ特徵とくちょう向むこう量りょう。

• 
  普通ふつうk-nn圖ず個こ拉ひしげ普ひろし拉ひしげ斯矩陣じん啲特徵ちょう值（ $k=3$），對たい於個8個こ對象たいしょう嘅數據よりどころ。由よし於該圖ず由よし三隻連通元件組成，所以ゆえん存在そんざい有ゆう三さん個こ值為0嘅特徵ちょう值。
• 
  三枚特徵向量啲值、拉ひしげ氏し矩のり陣じん$L_{rw}$啲特徵ちょう值係零れい嘅。啲欄應おう該等於 1，但ただし個こ軟件重おも新しん調整ちょうせい過か啲特徵しるし向むこう量りょう，令れい佢哋長ちょう度ど係がかり 1（即そく表ひょう中ちゅう分別ふんべつ係がかり$-1/{\sqrt {3}}$、$1/{\sqrt {2}}$、$1/{\sqrt {3}}$，等とう啲特徵しるし向むこう量りょう自じ點てん乘じょう會得えとく出で1）。
• 
  3D 散點さんてん圖ず畀特徵ちょう值零嘅三枚特徵向量嘅。8個こ對象たいしょう着ぎ重疊ちょうじょう畫が喺三さん笪埞（overplotting），等とう k平均へいきん聚類可か以完美び噉搵得え到いた三さん隻せき連れん通どおり元もと件けん。

演算えんざん法ほう

各かく式しき演算えんざん法ほう

嘸さぞ同どう嘅譜聚類演算えんざん法ほう有ゆう着ぎ開發かいはつ出で嚟：

非ひ歸一きいつ化か譜ふ聚類：

1. 計けい非ひ歸一きいつ化か嘅拉氏し矩のり陣じん$L$
2. 計けい前まえ$k$枚まい特徵とくちょう向むこう量りょう（係かかり有ゆう$k$最さい細ほそ特徵とくちょう值嘅）
3. 攞$k$枚まい特徵とくちょう向むこう量りょう啲行並なみ用よう分ぶん匹ひき方法ほうほう整せい聚類，譬たとえ如k-平均へいきん演算えんざん法ほう

Shi佮Malik嘅歸一いち化か譜ふ聚類：

1. 計けい歸一きいつ化か嘅拉氏し矩のり陣じん$L_{rw}$
2. 計けい前まえ$k$特徵とくちょう向むこう量りょう（係かかり有ゆう$k$最さい細ほそ特徵とくちょう值嘅）
3. 攞$k$枚まい特徵とくちょう向むこう量りょう啲行並なみ用よう分ぶん匹ひき方法ほうほう整せい聚類

Ng、Jordan佮Weiss嘅歸一いち化か譜ふ聚類 ：

1. 計けい歸一きいつ化か嘅拉氏し矩のり陣じん$L_{sym}$
2. 計けい前まえ$k$特徵とくちょう向むこう量りょう（係かかり有ゆう$k$最さい細ほそ特徵とくちょう值嘅）
3. 攞$k$枚まい特徵とくちょう向むこう量りょう啲行並なみ用よう分ぶん匹ひき方法ほうほう整せい聚類

參まいり數すう揀選

關せき於過程かてい參さん數すう同どう演算えんざん法ほう嘅揀選せん，Ulrike von Luxburg個こ教程きょうてい推薦すいせん係がかり：

• 鄰舍圖ず嘅揀選せん：k-nn 圖ず，因いん為ため識別しきべつ嘸さぞ同どう密度みつど嘅聚類るい識別しきべつ得とく好こう啲並生成せいせい得とく稀まれ疏拉氏し矩のり陣じん。$k$亦また都と可か以喺大だい啲嘅域いき內變化へんか，而同時じ嘸さぞ會かい改變かいへん到いた個こ聚類分析ぶんせき好こう多た。
• 鄰舍圖ず啲參數すう嘅揀選せん：
  • 對たい於k-nn 圖ず，$k$係かかり噉揀選せん嘅，即そく個こ圖ず啲連通どおり元もと件けん嘸さぞ少しょう過か預あずか期き聚類裏うら便びん應おう有ゆう嘅。
  • 對たい於普通どおり k-nn 圖ず，$k$要よう大過たいかk-nn度ど嘅，因いん爲ため普通ふつうk-nn 圖ず包含ほうがん到いた嘅檠少しょう過かk-nn 圖ず。揀選$k$嘅啟發けいはつ式しき方法ほうほう仲なか未知みち。
  • 對たい於$\epsilon$鄰舍圖ず應おう該揀$\epsilon$係かかり等とう於最長ちょう條じょう檠喺最さい細ほそ生成せいせい樹じゅ（minimum spanning tree）度ど嘅。
  • 對たい於啲全ぜん連接れんせつ圖ず有高ありだか斯相似そうじ度ど函數かんすう嘅應該揀$\sigma$係かかり令れい到いた結果けっか幅はば圖ず對應たいおう返かえし k-nn 圖ず或ある者もの$\epsilon$鄰舍圖ず。經驗けいけん法則ほうそく仲なか有ゆう：$\sigma$等とう於最長ちょう條じょう檠喺最さい細ほそ生成せいせい樹じゅ嘅或者しゃ$\sigma$作爲さくい個こ平均へいきん距離きょり去さ到いた$k$隻せき最近さいきん鄰舍嘅，其中$k=1+\log(n)$ .
• 聚類數すう嘅揀選せん：畫が出で拉ひしげ氏し矩のり陣じん啲特徵ちょう值，照あきら大だい細ほそ排はい序じょ並なみ搵跳躍ちょうやく，譬たとえ如喺上うえ高だか示しめせ意圖いと入いれ便びん8對象たいしょう數すう據よりどころ集しゅう個こ第だい3同どう第だい4特徵とくちょう值之間あいだ嘅。
• 拉ひしげ氏し矩のり陣じん嘅揀選せん：因いん爲ため對たい於$L_{rw}$嚟講，特徵とくちょう向むこう量りょう入いれ便びん啲欄係がかり等とう於1，攞譬如k-means 演算えんざん法ほう嚟聚類るい會かい幾いく好このみ。

例れい

Iris花はな數すう據よりどころ集しゅう，係かかりSir Ronald Fisher爵士 (1936) 作爲さくい判別はんべつ分析ぶんせき嘅例使用しよう到いた嘅。有ゆう時じ，個數こすう據よりどころ集しゅう亦また都と着ぎ喊做「Anderson's Iris花はな數すう據よりどころ集しゅう」，因いん為ためEdgar Anderson收集しゅうしゅう唨啲數すう據よりどころ嚟量化かIris花はな嘅形態けいたい變化へんか。個數こすう據よりどころ集しゅう由よし 50 隻せき標本ひょうほん組成そせい，每まい隻せき標本ひょうほん分ぶん為ため三さん隻せき物種ものだね：Iris setosa、Iris versicolor、Iris virginica。分別ふんべつ有ゆう測量そくりょう到いた萼がく片へん同どう花瓣はなびら嘅長度ど同どう埋うめ寬ひろし度ど，所以ゆえん個數こすう據よりどころ集しゅう包つつみ含有がんゆう150個こ觀察かんさつ值同埋うめ4個こ變量へんりょう。

• 
  Iris花はな數すう據よりどころ集しゅう啲散ち佈圖矩のり陣じん，數かず據點きょてん啲色對應たいおう於三さん種類しゅるい型がた。
• 
  Iris花はな數すう據よりどころ集しゅう裏うら便びん歐おう氏し距離きょり嘅熱ねつ圖ず。色いろ愈いよいよ深ふか，對象たいしょう之の間あいだ啲距離きょり愈いよいよ細ほそ。
• 
  Iris 數すう據よりどころ集しゅう上じょう嘅譜聚類結果けっか。

就好似に喺散佈圖矩のり陣じん個こ左ひだり便びん（第だい一いち幅ぶく）圖形ずけい見み到いた噉，三さん種類しゅるい型がた之の一いち（圖形ずけい中ちゅう啲紅色しょく）戥其他た類型るいけい顯著けんちょ嘸さぞ同どう。另外兩個りゃんこ物種ものだね互相之の間あいだ好こう難なん分ぶん開ひらき。中間ちゅうかん（第だい二に幅ぶく）圖形ずけい顯示けんじ對象たいしょう之の間あいだ啲歐氏し距離きょり嘅灰度ど熱ねつ圖ず。灰色はいいろ越こし深ふかし，對象たいしょう離はなれ得とく越えつ近こん。呢啲對象たいしょう經けい已やめ係がかり噉重新しん排列はいれつ法ほう，即そく戥其他た對象たいしょう有ゆう相似そうじ距離きょり嘅對象たいしょう互相之の間あいだ擺近。使用しよう到いた嘅軟件けん用よう層そう次じ聚類嘅方法ほう並なみ顯示けんじ到いた個こ樹き狀じょう結構けっこう圖ず（Dendrogram）。右みぎ便びん（第だい三さん幅ぶく）圖形ずけい顯示けんじ到いた譜ふ聚類嘅結果けっか。可か以睇得とく出で，啲聚類るい戥三種類型有一定嘅一致性。

• 
  黑色こくしょく：啲對象たいしょう之の間あいだ嘅檠，喺 k-nn 圖ず（ $k=50$ ）度ど保有ほゆう。白色はくしょく：啲捱鏟走嘅檠。
• 
  黑色こくしょく：啲對象たいしょう之の間あいだ嘅檠，喺普通どおり k-nn 圖ず（ $k=50$ ）度ど保有ほゆう。白色はくしょく：啲捱鏟走嘅檠。
• 
  散ち佈圖畀拉氏し矩のり陣じん$L_{rw}$啲特徵ちょう值，對たい於k-nn 圖ず（$k=50$ ）。

左ひだり便びん兩りょう幅はば圖像ずぞう顯示けんじ到いたk-nn 圖ず或ある者もの普通ふつう k-nn 圖ず裏うら便びん係がかり邊あたり啲檠着ぎ保留ほりゅう到いた（黑色こくしょく）或ある者もの嘸さぞ着き保留ほりゅう到いた（白色はくしょく）。對たい於參數すう$k$，最長さいちょう檠首先さき係がかり喺最細ほそ生成せいせい樹じゅ中ちゅう着き確定かくてい到いた，然しか之これ後ご幫所有しょゆう觀察かんさつ值計出で對應たいおう嘅鄰舍しゃ數すう。平均へいきん值大概がい係がかり 60 個こ鄰舍，係かかり噉揀$k=50$。之これ後ご計けい拉ひしげ氏し矩のり陣じん$L_{rw}$同どう埋うめ矩のり陣じん啲特徵ちょう值。特徵とくちょう值圖顯示けんじ到いた喺第二個或者第三個特徵值之後有好大跳躍。然しか之これ後ご對たい前まえ三さん枚まい特徵とくちょう向むこう量りょう進行しんこう3聚類嘅 k平均へいきん聚類。

種たね	聚類結果けっか
	1	2	3
setosa	0	0	50
versicolor	43	7	0
virginica	7	43	0

個こ混淆こんこう矩のり陣じん表明ひょうめい到いた譜ふ聚類喺某種しゅ程度ていど上じょう重おも新しん發現はつげん過か啲物種しゅ。譜ふ聚類法ほう完全かんぜん正確せいかく噉分出でSetosa聚類；喺 Versicolor同どうVirginica聚類嘅情況きょう下か有ゆう7 個こ觀測かんそく值各自かくじ捱錯誤さくご噉分類ぶんるい到いた，對應たいおう嘅錯誤さくご分類ぶんるい率りつ係がかり$14/150\approx 9{,}4\,\%$。