一种改进的模糊层次聚类算法

周维柏 黄德波 李蓉

[摘要]为解决模糊层次聚类算法无法收敛的问题，提出一种改进的模糊层次聚类算法。算法在分群前先进行数据处理，将特征向量相同的群合并成一个新的群，再使用模糊层次聚类算法分群，最后使用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.

（責任编辑白丽媛）