一種改進(jìn)的模糊層次聚類算法

周維柏 黃德波 李蓉

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

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

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

[中圖分類號(hào)]TP 18[文獻(xiàn)標(biāo)志碼]A[文章編號(hào)]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)域分群時(shí)，有時(shí)一個(gè)樣本同屬于兩個(gè)或幾個(gè)群，因此需要進(jìn)行重疊聚類。在生物學(xué)領(lǐng)域中，Becker等[1]利用重疊聚類將多功能蛋白質(zhì)進(jìn)行分群，旨在通過(guò)將相似的邊分組到一個(gè)層次中來(lái)捕獲圖的重疊結(jié)構(gòu)，在低邊密度圖的重疊性方面表現(xiàn)很好;在文字挖掘領(lǐng)域中，文獻(xiàn)[2]～[5]對(duì)文檔內(nèi)容進(jìn)行重疊聚類;在信息檢索領(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算法中加入多指派過(guò)程，使一個(gè)樣本同屬于多個(gè)群，產(chǎn)生重疊聚類結(jié)果，該算法有很好的重疊聚簇的能力，但不容易找到一個(gè)合適的門檻值來(lái)決定分群的結(jié)果。Pérezsuárez等[4]提出以圓形為基礎(chǔ)的重疊聚類算法，該算法引入了一種新的圖覆蓋策略和一種新的濾波策略，構(gòu)建的簇比以前相關(guān)算法構(gòu)建的簇要少，使得建立重疊聚類的算法更加精確，聚類結(jié)果更接近實(shí)際。在模糊成員的重疊聚類中，F(xiàn)uzzy cmeans是最廣泛使用的重疊聚類算法。Horng等[6]結(jié)合層次聚類提出模糊層次聚類算法（FAHC），利用相似度門檻值和相異度門檻值，結(jié)合AHC進(jìn)行分群，將每個(gè)文檔對(duì)應(yīng)于各類簇賦予權(quán)重值，并以權(quán)重值作為檢索依據(jù)，大大提高了檢索效率。在文檔分群時(shí)，經(jīng)過(guò)向量空間模型轉(zhuǎn)換后的特征向量時(shí)常會(huì)出現(xiàn)完全相同的結(jié)果，這些完全相同的特征向量會(huì)導(dǎo)致在分群時(shí)，類簇的數(shù)量不斷增加，從而進(jìn)一步導(dǎo)致分群結(jié)果無(wú)法收斂。

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

1模糊層次聚類算法

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

sim（di，dj）=

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

sim（di，dj）

∈[0，1]。（1）

模糊層次聚類算法為：

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

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

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

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

5） 對(duì)集合S中所有元素：

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

①?gòu)?fù)制Ai，記為A*i。

②將Ai和Aj合并成一個(gè)新的簇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合并成一個(gè)新的簇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合并成為一個(gè)新的簇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） 重新計(jì)算簇之間的相似度，若相似度都小于α，則算法結(jié)束，否則返回到步驟3）。

2改進(jìn)的模糊層次聚類算法

Horng等提出模糊層次聚類算法中，使用公式（1）計(jì)算兩個(gè)內(nèi)容完全相同的向量時(shí)：sim（d1，d2）=0.70.7+0.80.8+0.90.9，其結(jié)果不介于[0，1]。同時(shí)，若出現(xiàn)完全相同的特征向量，就會(huì)導(dǎo)致類簇的數(shù)量無(wú)法收斂。因此，本文對(duì)其加以改進(jìn)，在分群前先進(jìn)行數(shù)據(jù)處理，將特征向量相同的群合并成一個(gè)新的群;然后再使用模糊層次聚類算法分群;最后使用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)容進(jìn)行斷詞處理后，以TFIDF作為權(quán)重，并轉(zhuǎn)換為特征向量：

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

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

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

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

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

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

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

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

2.1分群預(yù)處理

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

2.2門檻值與群相似度計(jì)算

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

2.3簇間重疊的特性

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

對(duì)S中的所有元素（ck，cl）進(jìn)行下列操作：

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

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

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

2.4以Kmeans算法收斂群

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

3實(shí)驗(yàn)結(jié)果與分析

3.1實(shí)驗(yàn)數(shù)據(jù)

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

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

3.2評(píng)估指標(biāo)

以往的分群基本上是以Precision（準(zhǔn)確率）和Recall（召回率）來(lái)評(píng)價(jià)分群結(jié)果，但都是以單一類別來(lái)計(jì)算分群的正確比例。若某數(shù)據(jù)屬于兩個(gè)以上的類別時(shí)，則該數(shù)據(jù)就被重復(fù)計(jì)算，故其不適合評(píng)價(jià)重疊式分群。本文以文獻(xiàn)[9]的Multiplicity Precision和Multiplicity Recall來(lái)評(píng)價(jià)重疊式分群的結(jié)果，計(jì)算公式分別如式（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é)果。計(jì)算完Multiplicity Precision和Multiplicity Recall后，對(duì)其取平均值，計(jì)算公式分別如式（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度量標(biāo)準(zhǔn)的基礎(chǔ)上再使用F方法，計(jì)算FBCubed，其計(jì)算公式如式（6）：

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

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

3.3實(shí)驗(yàn)設(shè)計(jì)

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

3.4實(shí)驗(yàn)結(jié)果與分析

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

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

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

且較好的分群效果。

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

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

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

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

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

4結(jié)束語(yǔ)

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

[參考文獻(xiàn)]

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

（責(zé)任編輯白麗媛）