目標：
1）創建圖的表征矩陣2）分解：計算矩陣的特征值和特征向量；基于一個或多個特征值，將每個點表示成低維的表征3）分組：基于新的表征，進行聚類

---

例如，二分圖中如何確定好的分類？類間差異大，類內差異小最小割集考慮：1）團外的連接性2）團內的連接性
評價方式：團間的連接性與每個團的密度相關

spectral graph partitioning 譜圖分割
無向圖G的鄰接矩陣Ax是n維的特征向量，可認為是G中每個節點的label或者value那么Ax等到的結果的意義是？yi是節點i的鄰居節點的label的和通過yi生成新的x value譜圖理論：分析G的表征矩陣的spectrumspectrum的意義：圖的特征向量xi，（由特征值大小排序而得）
一個例子：假設G中的所有節點的度都有d，G是連通的。那么，G的特征值和特征向量是？
d是A的最大特征值若G不是完全連通的
矩陣表征鄰接矩陣：對稱矩陣，有n個特征值，特征向量是實數且是正交的
度矩陣：拉普拉斯矩陣：L=D-A對稱矩陣λ=λ1=0 ？？特征值為非負實數特征向量是實數且永遠正交對于對稱矩陣M，λ2的值由一公式可定 為xi--xj的平方和找到最優的x

發現最優的割法
譜聚類算法：1）圖的表征矩陣2）矩陣的特征值和特征向量；基于特征向量生成每個店的低維向量3）分組
例子k-way spectral clustering k聚類1）迭代的二分類2）對eigenvector多聚類如何選擇最優k——從特征值中，挑選間隔最大的兩個相鄰值

---

基于motif的譜聚類
基于連接模式進行聚類~主題1：發現motif的模塊

定義motif conductance生成motif是的cut和volumn

找到節點集S使motif conductance最小， 但找到s較難解決方案：通過譜的方法步驟：1）生成權重矩陣，值為該邊參與生成motif的次數2）譜聚類的方法3）分組兩個例子：食物鏈中未知的motif； 通信網絡中已知的motif未知的——每個motif跑一遍，找最小的

基因管理網絡

來自為知筆記(Wiz)

總結

以上是生活随笔為你收集整理的05-spectral 图机器学习之谱分解的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。