近鄰傳播聚類算法研究

李林陽，李高明，劉 祥，李 笑

（1.武警工程大學基礎部，陜西 西安 710086；2.武警工程大學信息學院，陜西 西安 710086）

AP算法是基于距離的聚類算法，F(xiàn)rey等于2007年在《Science》上發(fā)表了一篇論文，首次提出了近鄰傳播聚類算法。該算法具有很多優(yōu)點，比如聚類速度快、精確度高等，同時也存在一些問題。

1 AP算法存在的問題

（1）偏向參數(shù)的選擇問題。偏向參數(shù)往往需要人工設置，然而事實上這種設置未必能找到最合理的聚類結果。因此考慮p值的自適應，避免人工設置的麻煩和因此導致的聚類結果的不合理，從而使算法更加便捷和準確，提升聚類性能。人工設置比較繁瑣，若采用合適的策略，自適應調整阻尼因子，則可以加快算法收斂速度。

（2）相似度函數(shù)的選擇問題。不同結構的數(shù)據(jù)其相似度函數(shù)的選擇也不同，如對于球形數(shù)據(jù)，選擇歐氏距離可以取得好的效果，但對于結構復雜的非球狀簇，選擇基于密度的相似度計算方法的效果會比較理想；對于多重尺度的數(shù)據(jù)，存在奇異數(shù)據(jù)的數(shù)據(jù)集，以及高維數(shù)據(jù)，歐氏距離不能準確刻畫數(shù)據(jù)之間的距離。

（3）相似度函數(shù)的選擇問題。不同結構的數(shù)據(jù)其相似度函數(shù)的選擇也不同，對于多重尺度的數(shù)據(jù)，奇異數(shù)據(jù)，以及高維數(shù)據(jù)，歐氏距離不能準確反映數(shù)據(jù)之間的距離，且相似度矩陣會以根據(jù)維數(shù)的增加而呈幾何倍數(shù)增長。

（4）其他問題。其他問題包括該算法的集成研究較少的問題，半監(jiān)督的問題，對于大規(guī)模數(shù)據(jù)集，該算法的時間復雜度高的問題等。

2 AP算法發(fā)展現(xiàn)狀

近鄰傳播聚類算法（Affinity Propagation Clustering Algorithm，AP）于2007年由Frey等 在《Science》雜志上第一次提出。作為一種有效的聚類算法，AP算法此后得到了較大發(fā)展。2008年，肖宇等 將半監(jiān)督思想與近鄰傳播聚類算法結合在一起，詳細介紹了近鄰傳播算法，根據(jù)成對約束先驗信息提出了基于約束的半監(jiān)督近鄰傳播聚類算法，該研究成果得到了廣泛的認可，該文獻一度被數(shù)百篇論文引用，證實了半監(jiān)督AP算法的科學性和可行性。然而，該算法在聚類過程中存在相似度適用范圍不夠廣泛、偏向參數(shù)和阻尼因子（也叫阻尼系數(shù)或者迭代因子）需要人工篩選、處理大規(guī)模復雜數(shù)據(jù)集時算法復雜度高、不適用于高維數(shù)據(jù)和多尺度數(shù)據(jù)等問題，針對以上問題，專家學者進行了一系列改進。

2.1 AP算法負歐氏距離的問題研究

董俊等 提出了可變相似性度量的方法，其基本思想是根據(jù)數(shù)據(jù)在觀測空間中的流形分布規(guī)律，對不同分布的數(shù)據(jù)采取不同的處理策略；對于全局數(shù)據(jù)，采取函數(shù)變換策略對不同流形分布的數(shù)據(jù)對進行相似度的縮放，而對于局部數(shù)據(jù)，則采取映射的策略，搜索識別數(shù)據(jù)的不同流形分布并將其映射成超球形或超橢球形，再使用AP算法進行處理，從而提出了基于可變相似性度量的AP算法（AP-VSM），取得了良好的聚類效果。周世兵等 構造了樣本聚類距離和樣本離差聚類距離。邢艷等根據(jù)K-最近鄰的內含提出了互近鄰的概念，繼而提出了互近鄰一致性的定義并將其作為相似度度量的調整依據(jù)，最后提出了基于互近鄰一致性的AP算法。同樣采用最近鄰概念和最近鄰的傳遞性的還有蘇亞然等 ，他們提出了近鄰傳播的快速掃描算法，優(yōu)化搜索過程并嘗試簡化最近鄰居的判定過程和計算過程，從而實現(xiàn)了更加快速的聚類。廖予良 通過分析路徑相似度，提出了基于最短路徑的聚類方法，用最短路徑取代傳統(tǒng)的歐氏距離，實現(xiàn)了對不同形狀數(shù)據(jù)集的有效聚類。胡晨曉等 借助稀疏表示來作為樣本數(shù)據(jù)的相似度度量，提出了基于稀疏表示的AP算法。張利 基于模糊函數(shù)提出了將距離貼近度引入相似度函數(shù)的算法，很好解決了奇異樣本數(shù)據(jù)的量綱和過大過小值干擾問題，得到了良好的聚類結果。姬強 通過構造一個采用核低秩表示的優(yōu)化問題，挖掘數(shù)據(jù)的低維度流形結構，從而構造出結構相似度，作為歐氏距離的替代相似度度量，一定程度上解決了復雜結構數(shù)據(jù)的內部結構不易識別和挖掘的問題。唐丹 采用改進的馬氏距離來替代歐氏距離。趙昱 通過求解鄰域半徑得出鄰域密度并最終計算出鄰域相似度，作為近鄰傳播聚類算法的新的相似度度量，不僅提高了算法對復雜數(shù)據(jù)集的適應能力，也提高了算法的自適應特性。房驍 提出了量子近鄰傳播聚類算法，為解決高維數(shù)據(jù)的聚類問題，引進高斯核函數(shù)來構造相似度函數(shù)。

2.2 偏向參數(shù)的選擇問題和阻尼因子的使用問題研究

有關學者也提出了一些解決方案。張利 針對偏向參數(shù)需要人工選擇的問題，提出了基于布谷鳥優(yōu)化算法的自適應尋找最優(yōu)偏向參數(shù)的方法，提出了CS-SAP算法。周治平等 利用Silhouette聚類有效性指標來確定偏向參數(shù)。姬強 針對偏向參數(shù)難以調節(jié)的問題，提出了基于煙花爆炸智能優(yōu)化算法的最佳偏向參數(shù)選擇算法。覃華等 提出采用概率無向圖模型來解決偏向參數(shù)的自適應問題。趙昱 采用聚類有效性指標和下降步幅相結合的方法，實現(xiàn)了偏向參數(shù)的自適應，提出了PGZC-AP算法，提高了算法的運行效率。房驍 采用量子智能優(yōu)化算法對偏向參數(shù)進行優(yōu)化，參數(shù)初始化階段采用量子編碼方法，參數(shù)的更新階段使用旋轉量子門，最后獲得近優(yōu)參數(shù)，將其代入算法運行過程，從而解決了偏向參數(shù)的篩選問題，提高了聚類精度，減少了迭代次數(shù)。鄭凱月 采用布谷鳥優(yōu)化算法對偏向參數(shù)和迭代因子同時進行優(yōu)化，提高了算法的自適應性；還采用人工蜂群智能優(yōu)化算法對偏向參數(shù)進行了自適應計算的優(yōu)化。

2.3 近鄰傳播聚類算法的聚類有效性指標研究

周世兵等 采用近鄰傳播聚類算法作為聚類的研究對象，比較了6中聚類有效性指標，并改進了IGP指標作為最佳聚類數(shù)確定的方法。周世兵等 提出了BWP聚類有效性指標。

2.4 高維數(shù)據(jù)的聚類問題復雜的大數(shù)據(jù)集具有高復雜度的問題研究

多種不同類型的并行近鄰傳播聚類算法、一些與層級聚類相結合的近鄰傳播聚類算法以及多階段近鄰傳播聚類算法等被相關專家學者分別提出。劉曉楠等 提出了專門針對大規(guī)模數(shù)據(jù)集的分層聚類方案，文章將原始數(shù)據(jù)集劃分為多個較小的獨立子集，對各個子集進行算法執(zhí)行，得到每個子集的聚類中心，而后將得到的聚類中心集合再次進行算法執(zhí)行，得到全部數(shù)據(jù)集的類代表點，最后用得到的全局類代表點實現(xiàn)原始數(shù)據(jù)集的劃分，從而解決了大數(shù)據(jù)集聚類效率的優(yōu)化問題。錢雪忠等 根據(jù)先驗約束實現(xiàn)高維數(shù)據(jù)投影矩陣的獲取，在低維空間中進行聚類，從而實現(xiàn)了高維空間數(shù)據(jù)的近鄰傳播聚類。其中，高維數(shù)據(jù)投影到低維數(shù)據(jù)時，要求原來的數(shù)據(jù)集結構不能改變。周治平等 同樣提出了基于局部投影方法實現(xiàn)對復雜結構數(shù)據(jù)和高維數(shù)據(jù)的聚類，減少了信息冗余，保持了數(shù)據(jù)內部的結構。張利 使用熵權法和主成分分析法對高維數(shù)據(jù)進行降維，而后在低維空間中進行聚類。

3 結束語

AP算法還有較大的改進空間。可以與半監(jiān)督方法結合。AP算法針對相似度的改進可以考慮與密度聚類的研究成果相結合，提高算法對于復雜結構數(shù)據(jù)的適應度，采用基于密度的近鄰傳播聚類算法。對于高維數(shù)據(jù)的處理還需要進一步加強。對AP算法聚類集成的研究比較少，可以進一步加強。