近鄰傳播的文本聚類集成譜算法

盧志茂，李純，2，張琦

(1.哈爾濱工程大學(xué)信息與通信工程學(xué)院，黑龍江哈爾濱150001;2.中國人民解放軍91685部隊，海南陵水572400)

隨著網(wǎng)絡(luò)的迅速發(fā)展，快速有效地獲取信息成為人們的迫切需要，因此，如何提高信息獲取的效率已成為研究人員廣泛關(guān)注的課題.文本作為信息的重要表達(dá)形式之一，針對文本的處理研究顯得尤為必要.文本聚類可以有效地識別無結(jié)構(gòu)文本集中的“潛在概念”，并用這些概念和潛在關(guān)聯(lián)性得到文本集的概要或簇劃分等有意義的模式表達(dá)，這些模式信息對組織、搜索和管理大規(guī)模文本集具有重要意義［1］.

2002年，Strehl等［2］將集成學(xué)習(xí)引入到聚類分析中，提出了聚類集成算法.較之傳統(tǒng)的聚類算法，聚類集成算法具有魯棒性、新穎性、穩(wěn)定性、并行及可擴展性等諸多優(yōu)點［3］.作為傳統(tǒng)聚類算法的重要擴展，聚類集成已經(jīng)引起眾多研究者的關(guān)注，成為機器學(xué)習(xí)領(lǐng)域的研究熱點之一.

譜聚類算法對數(shù)據(jù)集的簇形狀不做強的假設(shè)，且算法不會陷入局部最優(yōu)［4］，是解決非凸數(shù)據(jù)集聚類問題較有效的算法.譜聚類算法的缺點也不容忽視:1)其計算復(fù)雜度為O(n3);2)譜聚類要求對相似度圖的參數(shù)精確設(shè)置，且在參數(shù)設(shè)置方面沒有相應(yīng)的理論指導(dǎo);3)譜聚類雖可有效識別理想分離和接近理想分離的簇，但真實文本數(shù)據(jù)集的簇分布往往與理想狀態(tài)相差甚遠(yuǎn)，多數(shù)真實的文本數(shù)據(jù)集在空間分布上類別邊界不明顯.文獻(xiàn)［5］將聚類集成和譜聚類結(jié)合起來提出了2個聚類集成的譜算法，并在多組數(shù)據(jù)集上獲得了較好的實驗效果.然而，上述算法在對譜分解得到的文本低維嵌入的聚類的過程中使用了K-means算法，由于K-means算法對初始點的敏感性會導(dǎo)致最終的聚類結(jié)果的不穩(wěn)定.針對該問題，本文研究如何進(jìn)一步提高聚類集成譜算法的穩(wěn)定性和聚類質(zhì)量.考慮到造成聚類結(jié)果不穩(wěn)定的原因在于K-means算法對于初始點的敏感性，所以本文引入近鄰傳播聚類思想，設(shè)計了一種新的聚類集成譜算法，并通過多組實驗驗證了本文算法的有效性.

1 近鄰傳播聚類算法

近鄰傳播(affinity propagation，AP)［6］聚類算法與其他基于中心點聚類方法相比，該方法無需指定初始的聚類中心和類別數(shù)，且具有較好的穩(wěn)定性.同時它對相似矩陣的對稱性不作要求，并在處理多類數(shù)據(jù)集時運算速度更快，所以性能更好.

但是，由于AP算法也是基于中心的聚類算法，它和其他的中心聚類算法一樣，僅在緊湊的具有球形分布的數(shù)據(jù)集上具有較好的聚類性能，對于一些簇分布比較復(fù)雜的數(shù)據(jù)集，其空間結(jié)構(gòu)可能非凸，使得AP算法只能收斂于局部最優(yōu)解［7-8］.因此，AP算法并不適合任意空間形狀的聚類問題和具有多重尺度的數(shù)據(jù)［9］，所以直接將AP算法用于結(jié)構(gòu)復(fù)雜的文本數(shù)據(jù)是不可行的，本文的實驗也證明了這一點.對于AP算法存在的不足，學(xué)者分別從半監(jiān)督［7］、偏置參數(shù)控制［8］、指定類別數(shù)［9］、相似度矩陣的構(gòu)造［10］等方面進(jìn)行了改進(jìn).鑒于AP算法的優(yōu)點和存在的問題，本文結(jié)合文獻(xiàn)［5］的思想，從改善數(shù)據(jù)集空間結(jié)構(gòu)角度入手，通過“集成+譜分解”來實現(xiàn)文本的降維和空間結(jié)構(gòu)轉(zhuǎn)化，以得到空間結(jié)構(gòu)更簡單的文本低維嵌入，為AP算法提供更好的輸入，克服了AP算法在復(fù)雜數(shù)據(jù)集上聚類效果不理想的缺點.同時AP算法無須指定初始點，避免了傳統(tǒng)譜聚類算法中由于K-means算法對初始點的敏感性造成聚類結(jié)果不穩(wěn)定的問題.

2 聚類集成算法

聚類集成一般分為2步，首先使用一種或多種聚類算法，對數(shù)據(jù)集進(jìn)行聚類，得到多個聚類結(jié)果(聚類成員)，這一步稱為聚類成員的生成階段;然后把得到的多個聚類成員作為新的輸入，通過集成算法對它們進(jìn)行組合，輸出最終的聚類結(jié)果，這一步稱為成員集成階段.在聚類成員生成的過程中，常用的方法是使用K-means算法［11-13］，隨機選擇初始點運行m次，以獲得m個聚類成員.該方法的優(yōu)點在于其計算復(fù)雜度低，實現(xiàn)起來簡單方便，適合于大規(guī)模數(shù)據(jù)集應(yīng)用.目前聚類集成問題的主要解決方法之一是基于圖劃分的方法.Strehl等［2］提出了3種基于圖劃分的聚類集成算法，基于簇的相似度劃分算法(cluster-based similarity partitioning algorithm，CSPA)、超圖劃分算法(hyper graph partitioning algorithm，HGPA)以及元聚類算法(meta-clustering algorithm，MCLA)算法.CSPA通過聚類成員的共聯(lián)矩陣構(gòu)造超圖，再由圖劃分算法METIS［14］給出聚類結(jié)果，算法的計算復(fù)雜度雖為O(n2)，但是它調(diào)用了高效的METIS算法，極大地提高了算法的效率;HGPA算法先構(gòu)造一個超圖，再由超圖劃分算法HMETIS［15］進(jìn)行聚類，得到最終的聚類結(jié)果;MCLA算法用二元Jaccard系數(shù)來度量超邊之間的相似度，隨后通過METIS算法對超邊進(jìn)行斷裂操作，以獲得最終的簇劃分.此外，F(xiàn)ern等［16］使用二部圖模型建模對點和簇同時建模，提出了混合二部圖模型(hybrid bipartite graph formulation，HBGF)算法.上述4種算法在聚類過程中都使用了圖劃分算法，圖劃分的算法雖然對簇的形狀不做強的假設(shè)，但是為避免算法收斂到平凡解，對簇的規(guī)模做了潛在的平衡性約束，即假定每個簇內(nèi)的樣本點數(shù)大致相等.當(dāng)數(shù)據(jù)集的平衡性不理想時，算法的聚類性能難以得到保證.

3 近鄰傳播的聚類集成譜算法

文獻(xiàn)［17］從矩陣擾動理論角度對譜聚類算法進(jìn)行了解釋，并給出了權(quán)矩陣(相似度矩陣S、正則化拉普拉斯矩陣Lsym和Lrw、非正則化拉普拉斯矩陣L以及圖上的隨機游動對應(yīng)的轉(zhuǎn)移概率矩陣P)的特征值與簇個數(shù)之間的對應(yīng)關(guān)系以及特征向量與簇之間的關(guān)系.當(dāng)數(shù)據(jù)集的各簇理想分離時，以相似度矩陣的前k個單位正交特征向量為列向量組成矩陣的行向量，可以看作是原待聚數(shù)據(jù)集的低維嵌入，根據(jù)各行向量之間的夾角可以用來對原數(shù)據(jù)集進(jìn)行聚類.據(jù)此思想，為進(jìn)一步提高算法性能及穩(wěn)定性，本文在聚類集成譜算法得到的文本低維嵌入聚類階段引入近鄰傳播聚類思想，設(shè)計了一種新的聚類集成算法，本文稱之為近鄰傳播的聚類集成譜算法(affinity propagation based cluster ensemble spectral algorithm，APCESA).

3.1 AP算法的基本原理

AP算法從相似度矩陣S=［s(i，j)］n×n出發(fā)，并引入了2個重要的信息參量矩陣，分別為代表度矩陣R=［r(i，j)］n×n和適選度矩陣A=［a(i，j)］n×n.算法的迭代過程就是這2個信息量競爭交替更新的過程，2個信息量代表了不同的競爭目的.r(i，j)從點xi指向點xj，它為類代表點xj搜集證據(jù)，表示xj適合作為xi的類代表點的代表程度.a(i，j)是從點xj指向點xi，它為類代表點xi搜集證據(jù)，表示xi選擇xj作為類代表點的合適程度.AP算法的核心步驟為2個信息量的交替更新過程，設(shè)當(dāng)前迭代次數(shù)為t，則更新公式如下:

式中:β為阻尼因子，其作用是防止算法在迭代過程中發(fā)生震蕩.各樣本點通過反復(fù)迭代競爭，迭代結(jié)束后，具有高的r(j，j)+a(j，j)的樣本為競爭得到的最終類代表點.對于任意數(shù)據(jù)點xi，計算所有數(shù)據(jù)點的代表程度r(i，j)和適選程度a(i，j)之和，其類代表點為，依此將各非類代表點樣本點分配給其所屬的類代表點即可得到聚類結(jié)果.

3.2 近鄰傳播的聚類集成譜算法

設(shè)B={b1，b2，…，bn}為文本集，F(xiàn)={F(1)，…，F(xiàn)(m)}為對其劃分得到的m個聚類標(biāo)簽(聚類成員)組成的集合.先把各簇標(biāo)簽F(i)變?yōu)槌瑘D表示H(i)，則超圖的n×t的鄰接矩陣H={H(1)，…，H(r)}，其中n為超圖的頂點數(shù)，t=mk為超邊數(shù).若采用余弦相似度，則相似度矩陣S=［s(i，j)］n×n=HHT/m.其中s(i，j)表示m個聚類成員中樣本點i和樣本點j屬于一個簇的次數(shù)比例，以此作為2個樣本點的相似度，得到超圖的相似度矩陣作為譜聚類的權(quán)矩陣，避免了傳統(tǒng)譜聚類算法中精確參數(shù)設(shè)計.這里m為常數(shù)，對矩陣分解無意義可舍棄不予考慮，則相似度矩陣S可簡化為S=HHT.更重要的是，由此方法得到的相似度矩陣S的特征值分解問題可通過小矩陣Q=HTH進(jìn)行間接求解.APCESA算法的主要步驟概括如下:

輸入:d×n的詞－文本共現(xiàn)矩陣W，(d為文本集的特征詞數(shù)，n為文本集的樣本數(shù))，簇個數(shù)k.

1)對W中的每個行向量(對應(yīng)于文本集中的一個文本)根據(jù)TF-IDF(term frequency-inverse document frequency)加權(quán)，經(jīng)標(biāo)準(zhǔn)化后，隨機選取初始點，運行K-means算法m次，以得到m個聚類成員.由m個聚類成員構(gòu)建超圖的鄰接矩陣H，構(gòu)造相似度矩陣S=［s(i，j)］n×n=HHT.

2)計算S的前k個最大特征值λ1，…，λk對應(yīng)的特征向量u1，…，uk.構(gòu)造矩陣U=［u1，…，uk］，設(shè)ui∈Rk為U的第i個行向量，Y={ui|i=1，…，n}即為文本集B對應(yīng)的低維嵌入.

3)計算低維嵌入的相似度矩陣S'=［s'(i，j)］n×n，設(shè)置初始偏執(zhí)參數(shù)P，初始化代表度矩陣R=［r(i，j)］n×n和適選度矩陣A=［a(i，j)］n×n.

4)按式(1)～(3)進(jìn)行迭代至收斂，得到對應(yīng)的類別數(shù)k'，判斷k'是否等于k，是則輸出聚類結(jié)果，給出對應(yīng)的簇劃分C1，…，Ck;不是則調(diào)節(jié)偏執(zhí)參數(shù)p繼續(xù)搜索.

5)依行向量的簇劃分將對應(yīng)的文本歸入到相應(yīng)的簇中，得到最終的聚類結(jié)果B1，…，Bk，其中Bi={bj|zj∈Ci，bj∈B}，1≤i≤k.

輸出:文本簇B1，…，Bk.

本文在求相似度矩陣的特征值分解的過程中使用了近似間接求解的方式.考慮特征值分解方程: Sx=λx，把S=HHT代入方程，得到HHTx=λx.設(shè)H的秩為p=rank(H)≤t，矩陣H的SVD定義如下:

式中:UUT=VVT=I，Σ=diag(σ1，…，σn)，σi為H的奇異值，且有當(dāng)1≤i≤p時，σi=0，當(dāng)i≥p+1時，σi=0.由式(4)可得HT=VΣUT，HHT=UΣ2UT，HTH=VΣVT，因此H的左、右奇異向量分別等于HHT和HTH的p個非0特征值對應(yīng)的特征向量，而奇異值等于HHT和HTH的特征值的非負(fù)平方根.

為降低計算誤差，SVD一般都轉(zhuǎn)化為對稱矩陣的特征值分解，將式(4)兩邊同時右乘VΣ+，其中Σ+為Σ的廣義逆，也稱偽逆或Moore-Penrose逆:

經(jīng)過整理可得U=HVΣ+.依此變換，避免了n階方陣S的特征值分解問題.

APCESA算法的巧妙之處在于:1)該算法先通過聚類集成為譜分解提供有意義的相似度矩陣，避免了譜聚類算法在處理高維數(shù)據(jù)集時由于對數(shù)據(jù)集的簇分布缺乏先驗知識導(dǎo)致相似度圖參數(shù)設(shè)置困難的問題;2)由譜分解得到的文本低維嵌入在空間結(jié)構(gòu)分布上更簡單，以此作為AP算法的輸入，有效的克服了AP算法在空間結(jié)構(gòu)復(fù)雜的數(shù)據(jù)集上聚類不理想的缺點;3)在低維嵌入聚類階段，AP算法由于無需指定初始點，從而避免了傳統(tǒng)譜算法中由于K-means算法對于起始點的敏感性造成的聚類結(jié)果不穩(wěn)定問題，保證了算法的穩(wěn)定性.

4 算法有效性驗證實驗

為驗證APCESA算法的有效性，本文先將APCESA算法與凝聚層次聚類(agglomerative hierarchical clustering:AHC)、K-means算法以及本文引入的原始AP算法進(jìn)行了對比試驗.為使對比實驗更客觀，算法效率更高，實驗中相似度均采用余弦相似度.各樣本點的向量表示經(jīng)歸一化后其模長為1，樣本點xi和xj之間的余弦相似度s(i，j)定義如下式:

此時，2個樣本點間相似度可簡化為2個對應(yīng)向量的點積，這樣就可以有效提高聚類算法的執(zhí)行效率.

為進(jìn)一步證明APCESA算法在聚類集成算法中的優(yōu)越性，本文還將APCESA算法與文獻(xiàn)［5］中提到的5種聚類集成算法進(jìn)行了比較.由于文獻(xiàn)［5］中提出的2種譜聚類集成算法性能大致相當(dāng)，基于相似度矩陣的譜算法 (similarity matrix-based spectral algorithm，SMSA)算法性能略優(yōu)于基于超邊相似度矩陣的譜算法(hyperedges＇similarity matrixbased spectral algorithm，HSMSA)算法，所以在本文的實驗中略去與HSMSA算法的比較.

4.1 實驗數(shù)據(jù)集及評價指標(biāo)

本文實驗使用的6個數(shù)據(jù)集都為真實的文本數(shù)據(jù)集，各數(shù)據(jù)集的樣本數(shù)、特征、真實的類別數(shù)如表1所示.其中，數(shù)據(jù)集tr31和tr41分別源于文本集TREC-6［18］和 TREC-7［18］，數(shù)據(jù)集 re0和 re1源于Reuters-21578文本分類測試集［19］;數(shù)據(jù)集hitech和reviews是對San Jose Mercury報紙不同領(lǐng)域的收錄，它們也是TREC［18］文本集其中的一部分(TIPSTER Vol.3);hitech收錄了關(guān)于電子、計算機、健康、醫(yī)療、科技和研究6個方面的文章;reviews包含了關(guān)于電影、美食、音樂、廣播和飯店5個方面的文章.6個文本集中所有文本的類別標(biāo)簽唯一.每個數(shù)據(jù)集，經(jīng)過停用詞表去停用詞，并去掉少于在2個文本中出現(xiàn)的稀有詞，再經(jīng)詞頻統(tǒng)計得到對應(yīng)的詞－文本共現(xiàn)矩陣，以此作為本文實驗的輸入.

表1 實驗數(shù)據(jù)集描述Table 1 Description of experimental datasets

由于各文本集的類別標(biāo)簽已知，且文本集的類別數(shù)k作為算法的已知輸入，本文采用源自信息論中的標(biāo)準(zhǔn)化互信息量(normalized mutual information，NMI)［2］來度量聚類結(jié)果和已知類別標(biāo)簽的匹配程度.相比于純度和熵等指標(biāo)，NMI值對k值的選取無傾向性，可以更客觀地衡量聚類效果的優(yōu)劣，也是近年來使用最多的評價指標(biāo)之一.當(dāng)聚類標(biāo)簽與真實的類別標(biāo)簽完全一致時，NMI值達(dá)到其最大值1.在APCESA算法與5種聚類集成算法的對比中，本文還使用了平均標(biāo)準(zhǔn)互信息量(average normalized mutual information，ANMI)［2］來度量各聚類集成算法的集成性能，ANMI值通過計算最終的聚類結(jié)果和m個聚類成員之間的平均標(biāo)準(zhǔn)互信息量得到，ANMI值越大，表明聚類集成算法搜索識別各聚類成員間一致性的能力越強，ANMI值也是近年來聚類集成算法的一個有效度量指標(biāo).

4.2 實驗結(jié)果及分析

4.2.1 實驗1:與主流聚類算法的對比實驗

APCESA算法與凝聚層次聚類、K-means算法以及AP算法的對比試驗結(jié)果如表2所示(4種算法在各數(shù)據(jù)集上得到的關(guān)鍵值用加粗突出).實驗中K-means算法由于對初始點的選擇的隨機性使得聚類結(jié)果不穩(wěn)定，在實驗中取運行10次指標(biāo)的均值作為實驗的參考指標(biāo);reviews數(shù)據(jù)集在使用AHC算法的過程中，由于AHC算法空間復(fù)雜度過大發(fā)生了內(nèi)存溢出錯誤，沒能得到聚類結(jié)果，在表中用“—”表示.

表2 4種聚類算法的NMI值對比Table 2 Comparison of NMI scores among 4 algorithms

從表2可以看出:

1)APCESA算法在6個數(shù)據(jù)集上都得到了最高的NMI值，且在6個數(shù)據(jù)集上的平均值也比其用于產(chǎn)生聚類成員的K-means算法的平均指標(biāo)提高了8.86%，這體現(xiàn)了該聚類集成算法對用于產(chǎn)生聚類成員的基聚類算法的改善效果，也說明將AP算法用于聚類集成譜算法中解決文本聚類集成問題是可行的.

2)在AHC、K-means和AP這3種單聚類算法的對比中可以看出，各數(shù)據(jù)集上AHC和K-means算法得到的結(jié)果都要優(yōu)于AP算法，這反映了AP算法在空間結(jié)構(gòu)復(fù)雜的文本數(shù)據(jù)集上的聚類性能的不足，所以直接將AP算法用于文本聚類是不合理的.

3)從各數(shù)據(jù)集的對比中可以發(fā)現(xiàn)，在數(shù)據(jù)集tr41上各聚類算法都得到了較好的聚類效果，且AHC、K-means算法以及APCESA算法得到的結(jié)果比較接近，這說明該數(shù)據(jù)集的類別邊界相對明顯.相反，在數(shù)據(jù)集hitech上各算法的聚類結(jié)果都不理想.究其原因，這和該數(shù)據(jù)集本身的空間結(jié)構(gòu)有很大的關(guān)系，hitech收錄了包含計算機、電子、健康、醫(yī)療、研究和科技6個方面的文章，其中計算機、電子、科技文章的相似性極高，而且健康和醫(yī)療2類也相互穿插，這種相似性反映到向量空間模型中則表現(xiàn)為空間結(jié)構(gòu)的復(fù)雜性和簇邊界的模糊.隨著這種復(fù)雜性的增加，必然導(dǎo)致聚類難度的增加和聚類質(zhì)量的下降，這也從側(cè)面說明了聚類分析的困難性.這種空間結(jié)構(gòu)復(fù)雜性的增加使得AP算法的性能下降明顯，然而在該數(shù)據(jù)集上，APCESA算法依然取得了相對較好的聚類結(jié)果，這反映了APCESA算法的魯棒性.

4)在AP算法和APCESA算法的對比中可以看到，AP算法在6個數(shù)據(jù)集上的結(jié)果都很不理想，然而通過與聚類集成譜算法的結(jié)合APCESA算法得到的聚類結(jié)果不但穩(wěn)定，而且聚類質(zhì)量也明顯改善，說明了AP算法和聚類集成譜算法的結(jié)合是有效的.

4.2.2 實驗2:與幾種聚類集成算法的對比實驗

為進(jìn)一步證明APCESA算法的有效性，本文還將APCESA算法與CSPA、HGPA、MCLA、HBGF以及文獻(xiàn)［5］中提出的SMSA這5種聚類集成算法進(jìn)行了對比實驗.6種聚類集成算法在6個數(shù)據(jù)集得到的NMI值和ANMI值如圖1、2所示.因為在HGPA算法中調(diào)用了HMETIS算法，而HMETIS只能得到局部最優(yōu)解，所以HGPA算法獲得的聚類結(jié)果不穩(wěn)定，這里取運行10次評價指標(biāo)的平均值;調(diào)用圖劃分算法METIS的CSPA和MCLA獲得的聚類結(jié)果比較穩(wěn)定;SMSA算法由于在低維嵌入聚類過程中使用了K-means算法，得到的聚類結(jié)果也存在一定的隨機性，同樣取運行10次評價指標(biāo)的平均值.考慮到聚類集成算法的效率，聚類成員的數(shù)量不宜太多，實驗中取5個聚類成員，即算法中m取5.此外，為使實驗更客觀，6種聚類集成算法在各數(shù)據(jù)集上使用相同的聚類成員，以免由于聚類成員的質(zhì)量不統(tǒng)一對算法的性能對比造成干擾.

圖1 6種集成算法的NMI值對比Fig.1 Comparison of NMI scores among 6 algorithms

由圖1和圖2可以看出:

1)本文提出的APCESA算法除了在reviews數(shù)據(jù)集上得到的NMI值和ANMI值與SMSA和HBGF相當(dāng)外，在其他所有數(shù)據(jù)集上都得到了高于其他對比算法的NMI和ANMI值.同時，APCESA算法在6個數(shù)據(jù)集上得到的NMI和ANMI的平均值也是最高的，證明了APCESA算法的有效性.

2)在6種聚類集成算法中，APCESA、SMSA和HBGF在集成過程中都使用了譜聚類算法，上述3個聚類集成算法除了HBGF在hitech上得到的NMI值略低于CSPA算法外，在其他數(shù)據(jù)集上都得到了較好的NMI值和ANMI值，這說明了譜聚類算法對聚類集成算法的性能改進(jìn)效果是明顯的.與SMSA和HBGF2種算法相比，APCESA算法有更好的穩(wěn)定性，且在tr31、tr41、re0和re1這4個數(shù)據(jù)集上的優(yōu)勢明顯，在reviews和hitech上也得到了不低于上述2種譜算法的NMI值和ANMI值，所以在聚類性能和穩(wěn)定性上APCESA算法略優(yōu)于上述2種算法.同時，在CSPA、HGPA、MCLA3種方法的對比中，CSPA得到的聚類結(jié)果最好，而HGPA和MCLA的NMI值互有高低，這一實驗結(jié)果與文獻(xiàn)［2］中的結(jié)論吻合.

圖2 6種集成算法的ANMI值對比Fig.2 Comparison of ANMI scores among 6 algorithms

3)6種算法在hitech數(shù)據(jù)集上的NMI值和ANMI值都不太理想，究其原因，這和該數(shù)據(jù)集復(fù)雜的空間結(jié)構(gòu)有很大的關(guān)系，在上文APCESA算法與3種單聚類算法的對比中也體現(xiàn)了這一點.在該數(shù)據(jù)集上，APCESA算法得到的NMI值和ANMI值也略高于5種對比集成算法，這說明了通過聚類集成和譜分解在數(shù)據(jù)空間結(jié)構(gòu)上的轉(zhuǎn)化是有效的，較好地克服了AP算法在結(jié)構(gòu)復(fù)雜數(shù)據(jù)集上的不足，也說明APCESA算法比其他5種算法魯棒性更好.

4)理論上算法的ANMI值和NMI值是一致的，但實驗中存在少數(shù)例外情況.例如CSPA在數(shù)據(jù)集tr31上得到的NMI值比MCLA高，但其ANMI值卻較MCLA低.這從側(cè)面說明了聚類的復(fù)雜性，一個理論上可行的聚類準(zhǔn)則未必能得到最優(yōu)解，而同一個準(zhǔn)則函數(shù)又很難在所有數(shù)據(jù)集上都得到好的聚類結(jié)果.

5)從總體上看，不同算法獲得的NMI值和ANMI值有很大的聯(lián)系，即高的ANMI值一般能得到較高的NMI值，6種算法在6個文本數(shù)據(jù)集上得到的平均NMI值和平均ANMI值的也正是這種對應(yīng)關(guān)系.這正說明了聚類集成的有效性，即聚類集成可以通過融合聚類成員達(dá)到提高聚類質(zhì)量的目的，聚類集成算法發(fā)現(xiàn)聚類成員的一致性能力越強，得到的聚類效果越好.APCESA得到了最高的平均NMI值和平均ANMI值，且在其中4個數(shù)據(jù)集上都得到的NMI值和ANMI值優(yōu)勢明顯，說明了APCESA算法在聚類性能和集成性能上優(yōu)于對比算法，證明了算法的有效性.APCESA算法在文本低維嵌入聚類過程中由于無需指定初始的聚類中心，當(dāng)聚類成員確定后，得到的最終聚類結(jié)果唯一，所以相對SMSA和HBGF2種聚類集成算法，APCESA更穩(wěn)定.同時，由于聚類成員有多個，雖然每個聚類成員由于初始點的不同具有一定的隨機性，但是聚類集成的結(jié)果正好是反映為這多個聚類成員的統(tǒng)計性.且APCESA算法的穩(wěn)定性僅與聚類成員的數(shù)量有關(guān)，在應(yīng)用中可根據(jù)需求進(jìn)行調(diào)節(jié)，不受數(shù)據(jù)集的限制.

5 結(jié)束語

本文引入近鄰傳播思想，設(shè)計了一種APCESA算法.該算法克服了聚類集成譜算法在數(shù)據(jù)集簇分布為非理想分離時由于K-means算法的使用造成聚類結(jié)果不穩(wěn)定的問題，同時，在一定程度上提高了算法的聚類質(zhì)量.該算法通過聚類集成和譜分解得到文本的低維嵌入，間接實現(xiàn)了文本數(shù)據(jù)集的降維和空間結(jié)構(gòu)轉(zhuǎn)化，為AP算法提供較好的輸入，克服了AP算法在復(fù)雜數(shù)據(jù)集上聚類不理想的缺點.在文本低維嵌入的聚類過程中，AP算法由于無需指定初始點，有效的避免了K-means算法由于初始點敏感性造成的算法不穩(wěn)定問題.在TREC和Reuters文本集上的實驗，證明了該算法的有效性.APCESA算法突破了傳統(tǒng)譜算法利用K-means算法得到最終結(jié)果的限制，是對聚類集成譜算法的一種擴展和改進(jìn);從AP算法的角度來看，利用聚類集成和譜分解來優(yōu)化數(shù)據(jù)集的空間結(jié)構(gòu)的思想為AP算法在復(fù)雜數(shù)據(jù)集上的擴展應(yīng)用提供一種的思路.

［1］TAN P N，STEINBACH M，KUMAR V.Introduction to data mining［M］.Toronto:Addison-Wesley Longman，2005: 20-23.

［2］STREHL A，GHOSH J.Cluster ensemblesdash—a knowledge reuse frame-work for combining partitionings［J］.Journal of Machine Learning Research，2002，3:583-617.

［3］TOPCHY A，JAIN A K，PUNCH W.A mixture model for clustering ensembles［C］//Proceedings of the 4th SIAM International Conference on Data Mining.Florida，2004:379-390.

［4］DING Shifei，ZHANG Liwen，YU Zhang.Research on spectral clustering algorithms and prospects［C］//2010 2nd International Conference on Computer Engineering and Technology.Chengdu，2010:149-153.

［5］徐森，盧志茂，顧國昌.解決文本聚類集成問題的兩個譜算法［J］.自動化學(xué)報，2009，35(7):997-1002.

XU Sen，LU Zhimao，GU Guochang.Two spectral algorithms for ensembling document clusters［J］.Acta Automatica Sinica，2009，35(1):997-1002.

［6］FREY B J，DUECK D.Clustering by passing messages between data points［J］.Science，2007，315(5814):972-976.

［7］肖宇，于劍.基于近鄰傳播算法的半監(jiān)督聚類［J］.軟件學(xué)報，2008，19(11):2803-2813.

XIAO Yu，YU Jian.Semi-supervised clustering based on affinity propagation［J］.Journal of Software，2008，19 (11):2803-2813.

［8］王開軍，張軍英，李丹，等.自適應(yīng)仿射傳播聚類［J］.自動化學(xué)報，2007，33(12):1242-1246.

WANG Kaijun，ZHANG Junying，LI Dan，et al.Adaptive affinity propagation clustering［J］.Acta Automatica Sinica，2007，33(12):1242-1246.

［9］ZHANG Xiangliang，WANG Wei，Kjetil N，et al.K-AP: generation specified k cluster by efficient affinity propagation［C］//2010 IEEE International Conference on Data Mining.Sydney，Australia，2010，107:1187-1192.

［10］董俊，王鎖萍，熊范綸.可變相似性度量的近鄰傳播聚類［J］.電子與信息學(xué)報，2010，32(3):509-514.

DONG Jun，WANG Suoping，XIONG Fanlun.Affinity propagation clustering based on variable-similarity measure［J］.Journal of Electronics＆Information Technology，2010，32(3):509-514.

［11］FRED A L，JAIN A K.Combining multiple clusterings using evidence accumulation［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2005，27(6): 835-850.

［12］AYAD H，BASIR O A，KAMEL M.A probabilistic model using information theoretic measures for cluster ensembles［C］//Proceedings of the 5th International Workshop on Multiple Classifier Systems.Cagliari，Italy，2004:144-153.

［13］FERN X Z，LIN W.Cluster ensemble selection［J］.Statistical Analysis and Data Mining，2008，1(3):128-141.

［14］KARYPIS G，KUMAR V.A fast and high quality multilevel scheme for partitioning irregular graphs［J］.SIAM Journal on Scientific Computing，1998，20(1):359-392.

［15］KARYPIS G，AGGARWAL R，KUMAR V，et al.Multilevel hypergraph partitioning:applications in VLSI domain［J］.IEEE Transactions on Very Large Scale Integration，1999，7(1):69-79.

［16］FERN X Z，BRODLEY C E.Solving cluster ensemble problems by bipartite graph partitioning［C］//Proceedings of the 21st International Conference on Machine Learning.New York:ACM，2004:36.

［17］TIAN Z，LI X B，JU Y W.Spectral clustering based on matrix perturbation theory［J］.Science in China Series F: Information Sciences，2007，50(1):63-81.

［18］National Institute of Stangdards and Technology.Text Retrieval Conference［EB/OL］.［2010-11-20］.http://trec.nist.gov.

［19］LEWIS D D.Reuters-21578 text categorization test collection distribution 1.0［EB/OL］.［2010-11-20］.http:// www.research.att.com/～lewis.