一種基于多層次方法的快速仿射譜聚類算法

蘇州高等職業技術學校 李志偉

?

一種基于多層次方法的快速仿射譜聚類算法

蘇州高等職業技術學校 李志偉

【摘要】快速放射譜聚類具有運行速度快，效率高的優點，目前受到各領域研究人員的普遍關注。本文聯合使用局部距離定義、FAP算法、表征樣本相似度的密度-權值矩陣構造方法，構建一種多級快速彷射譜聚類算法。最后對算法進行有效性分析，并突出本文算法的優勢，為提高彷射譜聚類算法提的研究供參考。

【關鍵詞】快速彷射譜聚類；相似度矩陣；譜聚類

1 快速仿射傳播譜聚類

仿射傳播聚類（AP）［1］是由 Frey 等人提出的一種新的聚類算法，其優勢體現在處理類數很多的聚集時運算速度快、聚類結果有效。在人臉圖像的聚類、“基因外顯子”發現、搜索最優航線等方面得到了應用。該算法首先將數據集的所有樣本點都視為候選的聚類中心，并為每個樣本點建立與其他樣本點的吸引程度的信息，即任意樣本間的相似度或吸引度。然后在循環迭代過程中，各樣本點競爭出最終的聚類中心。在每一輪更新的迭代過程中，若一個樣本點處于其相鄰樣本點的中心位置，則該點與其它樣本點的吸引度之和較大，在競爭中勝出的可能性也較大；反之，處在邊緣位置的樣本點，其吸引度之和較小而勝出的可能性也較小。這樣，在競爭中勝出的聚類中心具有較大的吸引度，則屬于聚類的樣本點到其聚類中心的誤差和比較小。因此，算法的迭代過程使得聚類的適應度函數最大化。當迭代過程收斂時，聚類中心也隨之確定（即類數自動確定），再將每個樣本點分配給最近的聚類中心所屬的聚類，算法結束［3，4］。

從上述可知，AP算法選取了全連接圖的相似矩陣用于樣本的信息傳播，且迭代次數較多。鑒于此，文獻［2］提出了一種快速的仿射傳播聚類方法（簡稱FAP），FAP同時考慮數據集中包含的局部和全局結構信息，是一種高特性多層圖分割方法，可以應實現基于矢量和基于圖的數據分割。首先，在FAP中提出了一種快速取樣算法（簡稱FS），FS用于粗化輸入的稀疏圖并選擇少量的具有代表性的樣本作為樣標，且每個樣標標識一個類簇，然后基于一種定義的密度-權值的矩陣得出一種新的譜聚類方法，該方法采用全局距離對每個類簇劃分成最終具有代表類簇的聚類結果，也即對類簇的合并。最后，通過樣本各自對應的類標（最終的樣標又稱為類標）來完成所有樣本點的類別劃分。

由于在任何一種譜聚類算法中，相似矩陣的構造是個很重要的問題，且該矩陣構造好之后才能進行下一步的譜分解和聚類。而如文獻［2］中所述，密度-權值矩陣也能夠反映出樣本的這種相似程度，且該矩陣的構造步驟如下：

步驟1. 定義樣本點間局部長和全局距離

步驟2. 計算類簇間的距離

步驟3. 構造密度-權值矩陣

該矩陣被定義為：

我們將由上述步驟得到的能夠度量樣本相似程度的密度-權值矩陣視為相似矩陣A，則基于密度-權值相似度度量的譜聚類算法實現步驟如下：

Step3.找出L的最大的K個特征向量構造V矩陣。

Step4.將V矩陣的每一行單位化，構造成Y矩陣，單元元素yij為：

2 結束語

首先，定義出的全局距離能夠相應地放大不同類樣本間的距離，縮小同類樣本間的距離。該距離對于噪聲點和極值點具有較好的魯棒性。能夠克服文獻［5］中最短路徑算法中的短路問題。其次，FAP 算法不僅能夠實現對稀疏圖的粗化，而且能夠對具有代表性標識的樣本點進行提取，且在計算速度上要比AP算法快的多。這是因為AP算法選取了樣本的全連接圖得到的相似矩陣用于信息傳播，且迭代次數較多。而FAP算法選取了有邊-權值信息存在的樣本構造稀疏圖。這樣，FAP算法不需要每次都計算所有樣本的信息傳播，只需要計算部分有邊--權值存在的樣本間的信息進行傳播。另外，FAP算法在樣本點間信息傳播過程中能夠同時考慮數據集中樣本點間的局部和全局結構信息，對多層次圖分割性能較高，且能夠處理大規模聚類問題。

最后，將能夠表征樣本相似度的密度-權值矩陣視作樣本的相似矩陣，得出一種基于密度-權值的譜聚類算法，該算法對標準UCI數據集、MNIST手寫字和人工數據集均具有較好的聚類性能，且加速了運算速度。

參考文獻

［1］Frey B， Dueck D. Clustering by passing messages between data points ［J］. Science， 2007，305（5841）﹕972-976.

［2］Shang F H，Jiao L C，Shi J R，etal.Fast affinity propagation clustering﹕A multilevel approach［J］.Pattern Recognition， 2012，45（1）﹕474-486.

［3］Kaijun Wang，Junying Zhang，Dan Li，Xinna Zhang，Tao Guo. Adaptive Affinity Propagation Clustering［J］.Acta Automatica Sinica，2007，33（12）﹕1242-1246.

［4］王開軍，李健，張軍英，涂重陽.半監督的仿射傳播聚類［J］.計算機工程，2007，33（23）﹕197-198.

［5］Tenenbaum J， Silva V， Langford J. A global geometric framework for nonlinear dimensionality reduction［J］.Science，2000，290（5500）﹕ 2319-2323.