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

（1.武警工程大學(xué)基礎(chǔ)部，陜西 西安 710086；2.武警工程大學(xué)信息學(xué)院，陜西 西安 710086）

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

1 AP算法存在的問題

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

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

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

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

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

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

2.1 AP算法負(fù)歐氏距離的問題研究

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

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

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

2.3 近鄰傳播聚類算法的聚類有效性指標(biāo)研究

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

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

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

3 結(jié)束語

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