一種改進的模糊層次聚類算法

周維柏 黃德波 李蓉

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

有較好的穩定性和分群效果，聚類質量高。

[關鍵詞]模糊層次聚類算法;重疊聚類;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引言

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

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

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

1模糊層次聚類算法

Horng等提出的模糊層次聚類算法可將文檔分群，利用軟聚類的概念，賦予每篇文檔對應簇的權重，并以權重作為檢索的依據。在分群前，先將文檔進行斷詞并將字詞還原為詞條（lemma），計算每個字詞的權重w，且w∈[0，1]，再以字詞的權重來表示各文檔的特征向量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） 讓每個文檔單獨屬于一個類簇，并將對應的簇權重值設為1。

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

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

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

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

①復制Ai，記為A*i。

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

調整Ai簇內的所有文檔dy的權重值MAi（dy），

新簇的權重值為

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

調整Aj簇內的所有文檔dz的權重值MAj（dz），

新簇的權重值為

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

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

調整A*i簇內的所有文檔dy的權重值MAi（dy），新簇的權重值為

M

A*il=MAi（

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

調整Al簇內的所有文檔du的權重值MAl（du），

新簇的權重值為MA*il=MAl（du）。

否則，將Ai與Aj合并成為一個新的簇Aij。調整Ai簇內的所有文檔dy的權重值MAi（dy），新簇的權重值為MAij=MAi（dy）。調整Aj簇內的所有文檔du的權重值MAj（dz），新簇的權重值為MAij=MAi（dz）。

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

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

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

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

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

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

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

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

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

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

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

6） 利用Kmeans算法將簇收斂至設定的簇數量K。

2.1分群預處理

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

2.2門檻值與群相似度計算

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

2.3簇間重疊的特性

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

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

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

與傳統模糊層次聚類算法一樣，我們會持續計算合并后的

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

2.4以Kmeans算法收斂群

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

3實驗結果與分析

3.1實驗數據

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

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

3.2評估指標

以往的分群基本上是以Precision（準確率）和Recall（召回率）來評價分群結果，但都是以單一類別來計算分群的正確比例。若某數據屬于兩個以上的類別時，則該數據就被重復計算，故其不適合評價重疊式分群。本文以文獻[9]的Multiplicity Precision和Multiplicity Recall來評價重疊式分群的結果，計算公式分別如式（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′）為任意兩數據，C（e）為數據e分群后的集群集合，L（e）為數據e正確的分群結果。計算完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度量標準的基礎上再使用F方法，計算FBCubed，其計算公式如式（6）：

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

FBCubed值越接近1，聚類質量越好。

3.3實驗設計

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

3.4實驗結果與分析

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

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

α≤0.20時，FBCubed值明顯高于α>0.2時的值，當相似度門檻值α=0.05、0.15、0.20且N=15時，都有最好的分群結果，所以我們認為對一個文檔取前15個關鍵字時會有穩定

且較好的分群效果。

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

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

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

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

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

4結束語

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

[參考文獻]

[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.

（責任編輯白麗媛）