周維柏 黃德波 李蓉

[摘要]為解決模糊層次聚類算法無法收斂的問題，提出一種改進的模糊層次聚類算法。算法在分群前先進行數(shù)據(jù)處理，將特征向量相同的群合并成一個新的群，再使用模糊層次聚類算法分群，最后使用Kmeans算法將類簇收斂為想要的數(shù)量。實驗結(jié)果表明，本算法具

有較好的穩(wěn)定性和分群效果，聚類質(zhì)量高。

[關(guān)鍵詞]模糊層次聚類算法;重疊聚類;Kmeans

[中圖分類號]TP 18[文獻標志碼]A[文章編號]10050310（2021）01002906

An Improved Fuzzy Agglomerative Hierarchical

Clustering Algorithm

Zhou Weibai1， Huang Debo2， Li Rong1

（1. Guangzhou College of Commerce， Guangzhou 511363， China; 2. Dongguan Tobacco Monopoly Bureau，

Dongguan Guangdong 523000，China）

Abstract： Aiming at the convergence problem of fuzzy agglomerative hierarchical clustering algorithm， we propose an improved fuzzy hierarchical clustering algorithm. Our algorithm performs data processing before clustering， merges clusters with the same feature vector into a new cluster， and then uses fuzzy hierarchical clustering algorithm to cluster. Finally， our algorithm uses the Kmeans algorithm to converge the clusters to the desired number. Experimental results show that the algorithm has a relatively stable and good clustering effect， and the clustering quality is high.

Keywords： Fuzzy agglomerative hierarchical clustering algorithm; Overlapping clustering; Kmeans

0引言

在生物學(xué)、文字挖掘等領(lǐng)域分群時，有時一個樣本同屬于兩個或幾個群，因此需要進行重疊聚類。在生物學(xué)領(lǐng)域中，Becker等[1]利用重疊聚類將多功能蛋白質(zhì)進行分群，旨在通過將相似的邊分組到一個層次中來捕獲圖的重疊結(jié)構(gòu)，在低邊密度圖的重疊性方面表現(xiàn)很好;在文字挖掘領(lǐng)域中，文獻[2]～[5]對文檔內(nèi)容進行重疊聚類;在信息檢索領(lǐng)域中，Horng等[6]使用模糊概念的重疊聚類，根據(jù)用戶的相關(guān)反饋，修改文檔描述向量的權(quán)重，使模糊信息檢索系統(tǒng)更靈活、更智能，從而提高系統(tǒng)檢索效率。重疊聚類已經(jīng)被廣泛應(yīng)用在不同的領(lǐng)域，成為熱門的研究話題。

Kearns等[7]把分群后的成員隸屬程度分為硬成員和模糊成員。在硬成員的重疊聚類中，Cleuziou等[8]提出重疊Kmeans算法，在傳統(tǒng)的Kmeans算法中加入多指派過程，使一個樣本同屬于多個群，產(chǎn)生重疊聚類結(jié)果，該算法有很好的重疊聚簇的能力，但不容易找到一個合適的門檻值來決定分群的結(jié)果。Pérezsuárez等[4]提出以圓形為基礎(chǔ)的重疊聚類算法，該算法引入了一種新的圖覆蓋策略和一種新的濾波策略，構(gòu)建的簇比以前相關(guān)算法構(gòu)建的簇要少，使得建立重疊聚類的算法更加精確，聚類結(jié)果更接近實際。在模糊成員的重疊聚類中，F(xiàn)uzzy cmeans是最廣泛使用的重疊聚類算法。Horng等[6]結(jié)合層次聚類提出模糊層次聚類算法（FAHC），利用相似度門檻值和相異度門檻值，結(jié)合AHC進行分群，將每個文檔對應(yīng)于各類簇賦予權(quán)重值，并以權(quán)重值作為檢索依據(jù)，大大提高了檢索效率。在文檔分群時，經(jīng)過向量空間模型轉(zhuǎn)換后的特征向量時常會出現(xiàn)完全相同的結(jié)果，這些完全相同的特征向量會導(dǎo)致在分群時，類簇的數(shù)量不斷增加，從而進一步導(dǎo)致分群結(jié)果無法收斂。

為了解決模糊層次聚類算法無法收斂的問題，本文在分群前先進行數(shù)據(jù)預(yù)處理，將特征向量相同的群合并成一個新的群，這樣能使模糊層次聚類算法在進行文檔分群時不會因為相同的特征向量而產(chǎn)生無法收斂的結(jié)果;然后使用模糊層次聚類算法分群;最后使用Kmeans算法將類簇收斂為想要的數(shù)量。實驗結(jié)果表明本算法具有很好的分群結(jié)果。

1模糊層次聚類算法

Horng等提出的模糊層次聚類算法可將文檔分群，利用軟聚類的概念，賦予每篇文檔對應(yīng)簇的權(quán)重，并以權(quán)重作為檢索的依據(jù)。在分群前，先將文檔進行斷詞并將字詞還原為詞條（lemma），計算每個字詞的權(quán)重w，且w∈[0，1]，再以字詞的權(quán)重來表示各文檔的特征向量d，其中di=〈wi1，wi2，…wis〉，并以公式（1）計算文檔之間的相似度。

sim（di，dj）=

k=1，2，…，smin（wik，wjk）max（wik，wjk），

sim（di，dj）

∈[0，1]。（1）

模糊層次聚類算法為：

1） 先給予一個相似度門檻值α和一個相異度門檻值λ，且α，λ∈0，1。

2） 讓每個文檔單獨屬于一個類簇，并將對應(yīng)的簇權(quán)重值設(shè)為1。

3） 利用公式（1）計算兩兩簇之間的相似度，找到一對相似度最高且大于門檻值α的簇Ai，Aj，并將其相似度sim（Ai，Aj）設(shè)為φ，且φ∈[0，1]。

4） 除Ai，Aj之外，再將其余相似度大于門檻值α 的簇對放到一個集合S中，使得S=Am1，An1，Am2，An2，…。

5） 對集合S中所有元素：

若φ-sim（Ak，Al）<λ，且簇對（Ak，Al）與Ai，Aj有共同的類簇As，則：

①復(fù)制Ai，記為A*i。

②將Ai和Aj合并成一個新的簇Aij。

調(diào)整Ai簇內(nèi)的所有文檔dy的權(quán)重值MAi（dy），

新簇的權(quán)重值為

MAij=MAi（dy）×φ/（φ+sim（Ak，Al））。

調(diào)整Aj簇內(nèi)的所有文檔dz的權(quán)重值MAj（dz），

新簇的權(quán)重值為

MAij=MAj（dz）×φ/（φ+sim（Ak，Al））。

③將步驟①中的A*i與Al合并成一個新的簇A*il。

調(diào)整A*i簇內(nèi)的所有文檔dy的權(quán)重值MAi（dy），新簇的權(quán)重值為

M

A*il=MAi（

dy）×φ/（φ+sim（Ak，Al））。

調(diào)整Al簇內(nèi)的所有文檔du的權(quán)重值MAl（du），

新簇的權(quán)重值為MA*il=MAl（du）。

否則，將Ai與Aj合并成為一個新的簇Aij。調(diào)整Ai簇內(nèi)的所有文檔dy的權(quán)重值MAi（dy），新簇的權(quán)重值為MAij=MAi（dy）。調(diào)整Aj簇內(nèi)的所有文檔du的權(quán)重值MAj（dz），新簇的權(quán)重值為MAij=MAi（dz）。

6） 重新計算簇之間的相似度，若相似度都小于α，則算法結(jié)束，否則返回到步驟3）。

2改進的模糊層次聚類算法

Horng等提出模糊層次聚類算法中，使用公式（1）計算兩個內(nèi)容完全相同的向量時：sim（d1，d2）=0.70.7+0.80.8+0.90.9，其結(jié)果不介于[0，1]。同時，若出現(xiàn)完全相同的特征向量，就會導(dǎo)致類簇的數(shù)量無法收斂。因此，本文對其加以改進，在分群前先進行數(shù)據(jù)處理，將特征向量相同的群合并成一個新的群;然后再使用模糊層次聚類算法分群;最后使用Kmeans算法將類簇收斂為想要的數(shù)量。

為方便描述，我們先定義所有類簇的集合為C，C=c1，c2，c3，…;所有文檔的集合為D，D=d1，d2，d3，…;所有關(guān)鍵字的集合為K，K=k1，k2，k3，…;sim（ci，cj）表示簇ci與ci之間的相似度。我們先將所有文檔的內(nèi)容進行斷詞處理后，以TFIDF作為權(quán)重，并轉(zhuǎn)換為特征向量：

di=（k11，k12，…，k1c）。

其中，di表示第i篇文檔，kin表示第i篇文檔的第n個關(guān)鍵字的TFIDF。以上述特征向量作為輸入，并加入分群前預(yù)處理，改進的模糊層次聚類算法具體步驟為：

1） 設(shè)定相似度門檻值α和一個相異度門檻值λ，分群數(shù)量K，其中α，λ∈0，1，K∈N。

2） 分群前處理，將特征提取后的內(nèi)容完全相同的文檔先分為一群。

3） 計算類簇之間的相似度，并找出相似度大于門檻值的簇對。

4） 對所有相似度大于門檻值的簇對與相似度最高的兩個簇對分別進行比較，計算兩者相似度的差是否小于相異度門檻值λ，并判斷文檔之間是否有共同簇，將符合條件的簇進行復(fù)制與合并。

5） 重復(fù)3）和4）的步驟，直到所有的簇之間的相似度皆小于門檻值α為止。

6） 利用Kmeans算法將簇收斂至設(shè)定的簇數(shù)量K。

2.1分群預(yù)處理

為避免模糊層次聚類算法在出現(xiàn)完全相同的特征向量時，導(dǎo)致類簇的數(shù)量無法收斂，在分群前先把特征向量完全相同的文檔群聚在同一個群中。這樣在每次分群的迭代中，就不會將原先已經(jīng)有相同特征的類別進行復(fù)制與合并。

2.2門檻值與群相似度計算

本文以相似度門檻值α和相異度門檻值λ 作為合并簇的條件，經(jīng)過預(yù)處理后，將其余的文檔各自獨立成一個簇，并用Ward′s method方法重新計算簇之間的相似度，先找出相似度最高的兩個簇 ci與cj，將sim（ci，cj）設(shè)為ψ，且ψ>α;再將其余相似度大于或等于α的簇組放入集合S中，其中S=sim（ck，cl）|sim（ck，cl）≥α。

2.3簇間重疊的特性

將上一步取得的S中的所有元素與相似度最高的簇進行對比，若符合條件則復(fù)制與合并簇，

對S中的所有元素（ck，cl）進行下列操作：

如果sim（ci，cj）-sim（ck，cl）<λ并且ci=ck或 cl，則復(fù)制一個ci的簇c*i，將ci與cj合并為一個新的簇cij，將c*i與cl或者ck合并為一個新簇ci×l或者ci×k。否則，將ci與cj合并為一個新簇cij。

與傳統(tǒng)模糊層次聚類算法一樣，我們會持續(xù)計算合并后的

ψ與S，以ψ與S來持續(xù)探索簇間重疊的特性，并將符合條件的數(shù)據(jù)合并與復(fù)制，直到所有簇之間的相似度都小于相似度門檻值α。

2.4以Kmeans算法收斂群

在模糊層次聚類算法中，只利用相似度門檻值作為分群收斂條件，無法決定分群數(shù)量。本文對模糊層次聚類算法進行改進，解決無法決定分群數(shù)量的限制，在所有的數(shù)據(jù)都小于門檻值α后，判斷分群結(jié)果的數(shù)量C，若C大于預(yù)期的分群數(shù)量K，則將分群結(jié)果利用Kmeans算法將分群數(shù)量調(diào)整到K。

3實驗結(jié)果與分析

3.1實驗數(shù)據(jù)

實驗的測試集使用Reuters21578數(shù)據(jù)集，數(shù)據(jù)集由21 578篇文檔組成，在TOPICS標簽中共有92個類別，其中有數(shù)篇文檔被分到一個以上的類別中，非常適合用在重疊式分群的研究中。本文使用數(shù)據(jù)集中

的LEWISSSPLIT屬性為ReuTe的2 275篇文檔和ReuTr的6 903篇文檔，以TOPICS類別中的屬性作為正確分群的依據(jù)。

3.2評估指標

以往的分群基本上是以Precision（準確率）和Recall（召回率）來評價分群結(jié)果，但都是以單一類別來計算分群的正確比例。若某數(shù)據(jù)屬于兩個以上的類別時，則該數(shù)據(jù)就被重復(fù)計算，故其不適合評價重疊式分群。本文以文獻[9]的Multiplicity Precision和Multiplicity Recall來評價重疊式分群的結(jié)果，計算公式分別如式（2）和（3）：

MPrecision（e，e′）=

min（C（e）∩C（e′），L（e）∩L（e′））C（e）∩C（e′）。（2）

MRecall（e，e′）=

min（C（e）∩C（e′），L（e）∩L（e′））L（e）∩L（e′）。

（3）

其中，（e，e′）為任意兩數(shù)據(jù)，C（e）為數(shù)據(jù)e分群后的集群集合，L（e）為數(shù)據(jù)e正確的分群結(jié)果。計算完Multiplicity Precision和Multiplicity Recall后，對其取平均值，計算公式分別如式（4）和（5）：

RBCubed=Avge{Avge′

，L（e）∩L（e′）≠ψ

[MRecall（e，e′）]}。

（4）

PBCubed=Avge{Avge′，C（e）∩C（e′）≠ψ

[MPrecision（e，e′）]}。

（5）

本文在BCubed度量標準的基礎(chǔ)上再使用F方法，計算FBCubed，其計算公式如式（6）：

FBCubed=2×PBCubed×RBCubedPBCubed+RBCubed。（6）

FBCubed值越接近1，聚類質(zhì)量越好。

3.3實驗設(shè)計

在進行分群時，先使用JATE將各文檔移除停用詞并將字詞還原成詞條后，再計算字詞的TFIDF，分別取每個文檔的TFIDF排名為前5、10、15、20、25的關(guān)鍵字作為特征值，將其轉(zhuǎn)換為特征向量進行分群，并驗證分群結(jié)果。為找出最好的門檻值組合[α，λ]，我們分兩部分進行實驗，首先針對各文檔分別以5、10、15、20、25個關(guān)鍵字作為特征值，并設(shè)定λ=0.06來測試關(guān)鍵字數(shù)量對于分群結(jié)果的影響;再對上述結(jié)果最好的關(guān)鍵字數(shù)量利用網(wǎng)格搜索法來尋找最合適的相似度門檻值和相異度門檻值，最后與不同的重疊式分群法進行比較。

3.4實驗結(jié)果與分析

本研究首先以Reuters21578數(shù)據(jù)集中的LEWISSSPLIT屬性為ReuTe的數(shù)據(jù)測試各文檔所提取的關(guān)鍵字數(shù)量N對分群結(jié)果的影響。將相異度門檻值λ設(shè)定為0.06，α取0.05～0.30之間的間隔值，N分別取5、10、15、20、25，進行分群比較，結(jié)果如表1所示。

從表1可以看出，當α=0.05時，因集群的關(guān)鍵字太少，使得集群之間相似度太低，導(dǎo)致Kmeans無法收斂。另外，當

α≤0.20時，F(xiàn)BCubed值明顯高于α>0.2時的值，當相似度門檻值α=0.05、0.15、0.20且N=15時，都有最好的分群結(jié)果，所以我們認為對一個文檔取前15個關(guān)鍵字時會有穩(wěn)定

且較好的分群效果。

根據(jù)上述結(jié)果，取每個文檔前15個關(guān)鍵字作為特征向量，并利用網(wǎng)格搜尋法來挖掘合適的相似度門檻值和相異度門檻值。因相似度門檻值為0時算法不收斂，故取0.05為相似度門檻值的最小值，將相異度門檻值λ設(shè)定為0.06，進行第一階段網(wǎng)格搜尋，其結(jié)果如圖1所示。

從圖1可以看出，當α為0.05及0.10時有較好的分群效果，故對α分別取0.05和0.10進行網(wǎng)格搜索，找出最好的相異度門檻值λ，結(jié)果如表2所示。

從表2可知，總體看來，α=0.10的分群結(jié)果比α=0.05的好，且在[α，λ]=[0.10，0.09]時有最高的FBCubed值，為0.538 9。本文算法使用[α，λ]=[0.10，0.09]，與不同算法進行比較，結(jié)果如表3所示。從表3中可看出，本文算法結(jié)果最好。

以Reuters21578數(shù)據(jù)集中的LEWISSSPLIT屬性為ReuTr的數(shù)據(jù)進行試驗，同樣取每個文檔的前15個關(guān)鍵字作為特征向量，不同算法的性能比較如表4所示。

從表4可以看出，本文算法只比文獻[4] 略好一點，這是由于對ReuTr的數(shù)據(jù)進行分群時，因數(shù)據(jù)量較大，使得網(wǎng)格搜索需要更多的時間進行門檻值的挑選，在有限時間內(nèi)找到最佳門檻值比較難，故分群優(yōu)勢沒有充分顯現(xiàn)出來，不過還是好于傳統(tǒng)的重疊式分群算法。

4結(jié)束語

本文通過加入數(shù)據(jù)預(yù)處理，使得在利用模糊層次聚類算法進行文件分群時，不會因為將相同特征值的群復(fù)制與合并而導(dǎo)致數(shù)據(jù)重復(fù)性過高并出現(xiàn)算法無法收斂的現(xiàn)象。改進后的模糊層次聚類算法不僅能設(shè)定分群的數(shù)量，而且具有重疊式分群的特性。實驗結(jié)果表明，本算法比其他重疊式分群算法具有較好的分群效果。

[參考文獻]

[1]BECKER E，ROBISSON B，CHAPPLE CE， et al. Multifunctional proteins revealed by overlapping clustering in protein interaction network[J]. Bioinformatics， 2012， 28（1）：84-90.

[2]BANERJEE A，KRUMPELMAN C，GHOSH J， et al. Modelbased overlapping clustering[C]// Proceedings of the Eleventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Chicago： ACM，2005：532-537.

[3]STEINBACH M， KARYPIS G， KUMAR V. A comparison of document clustering techniques[J]. KDD Workshop on Text Mining，2000，40（1）：525-526.

[4]PREZSUREZ A，MARTNEZTRINIDAD J F， CARRASCOOCHOA J A， et al. OClustR： A new graphbased algorithm for overlapping clustering[J]. Neurocomputing，2013，121 （18）：234-247.

[5]TSOUMAKAS G， KATAKIS I， TANIAR D. Multilabel classification： An overview[J]. International Journal of Data Warehousing and Mining，2009， 3（3）：1-13.

[6]HORNG Y J， CHEN S M， CHANG Y C， et al. A new method for fuzzy information retrieval based on fuzzy hierarchical clustering and fuzzy inference techniques[J]. IEEE Transactions on Fuzzy Systems， 2005， 13（2）：216-228.

[7]KEARNS M， MANSOUR Y， NG A Y. An informationtheoretic analysis of hard and soft assignment methods for clustering[J]. CORR， 2013（2）：495-520.

[8]CLEUZIOU G. An extended version of the kmeans method for overlapping clustering[C]//19th International Conference on Pattern Recognition. Tampa， Florida： IEEE，2008：1-4.

[9]AMIG E， GONZALO J， ARTILES J， et al. A comparison of extrinsic clustering evaluation metrics based on formal constraints[J]. Information Retrieval， 2009， 12（5）：613.

（責任編輯白麗媛）