一种改进的层次聚类算法

针对凝聚式的层次聚类算法在聚类过程中层次化的迭代运算使误差不断累积,导致聚类结果较差的问题,在GN快速算法基础上提出了一种改进的凝聚式层次聚类算法,即网状聚类算法。实验结果表明,该改进算法避免了误差的积累,可以获得更高质量的聚类结果。

第3卷第6 3期 21年 1月 0 2 1

武汉理工大学学报 息与管理工程版信J U N LO T IF R A IN&M N G M N N IE RN ) O R A FWU (N O M TO A A E E TE GN E IG

V 13 . o . 3 No 6 De . 0 1 c 2 1

文章编号：0 7—14 2 1 ) 6— 83—0 10 4 X(0 10 0 8 4

文献标志码： A

一

种改进的层次聚类算法靳延安，刘行军(湖北经济学院信息管理学院，湖北武汉 4 0 0 ) 3 2 5

摘

要：针对凝聚式的层次聚类算法在聚类过程中层次化的迭代运算使误差不断累积，导致聚类结果较差的

问题， G在 N快速算法基础上提出了一种改进的凝聚式层次聚类算法，网状聚类算法。实验结果表明，即该改进算法避免了误差的积累，可以获得更高质量的聚类结果。

关键词：聚类算法；网状聚类；块性函数模中图分类号￣P 9 T 31 D I1.9 3 ji n 10 O:0 3 6/.s . 07—14 2 1.6 0 9 s 4 x.0 10 .0

聚类是把各不相同的个体分割为有更多相似性的簇的工作。由聚类所组成的簇是一组数据对象的集合，这些对象与同一簇中的对象彼此类似， 与其他簇中的对象相异…,目前，已有大量的聚类算法。根据数据的类型、目的和应用场景，主要的聚类算法通常分为划分方法 J层次方、法 J基于密度的方法 - 9、于网格的方、 8基 IJ法和基于模型的方法 。其中层次聚类算卜 J法由于其简单，得到了广泛的应用。但该方法经常会遇到合并或分裂点选择的问题。一旦一组对

然后用一个凝聚的层次算法反复地合并子类来找到真正的结果簇。这些算法都需要事先告知簇的

数目，但是簇的数目是十分难以确定的，同时又非常敏感。N WM N提出了一个称为 Nw a E A e m n快速算法的凝聚式聚类算法，该算法最开始用于社会网络图中的社区发现，算法不用事先设定社区的数目，而是通过模块性评价判定最佳聚类效果而停止迭代聚类，所讨论的社区本质上是聚其

类中的簇。该方法具有较好的可伸缩性和较高的效率，同样要遇到合并点选择的困难，但一旦其中的某一步有错误，这种错误将会叠加放大，从而降低聚类的效果。 为了解决上述问题

,者提出了一种改进的笔

象被合并或者分裂，下一步的处理将在新生成的 簇上进行，已做的处理不能被撤销，聚类之间也不能交换对象。若在某一步没有很好地选择合并或分裂，可能导致低质量的聚类结果。为了改进层次聚类算法的质量，内外学者国进行了大量研究 J其中一个很有希望的改进，

N w a快速算法， em n即网状聚类算法( e— gl— nt ag m o e t e l t i grh )并利用该算法在 Is r i u en a otm, av c s r g l i r i数据集上做了测试。实验结果表明，该算法比传统层次聚类算法有更高的准确率。

方向是结合其他聚类技术形成多阶段聚类。LN I. V Y等提出了 BR H算法，算法首先使用 C IC该 F树结构对数据对象进行划分，然后采用其他算法对聚类结果进行求精。该算法具有对数据对象数目的线性伸缩性，并且有较好的聚类质量，但是该算法对于非球形簇效果不是很好。G H U A等采用了随机取样和划分两种方法组合解决了偏好球形和相似大小的问题。K Y I提出了一种基 AR PS等

1基于堆结构的 N w n快速算法 e ma1 1基本思想 .

Nw a e m n快速算法实际上是基于贪婪算法思想的一种凝聚算法。在社会网络图中 (图 1所如示 )每两个有联系的节点都有一条边相连。具，

体思想是：假设起始时刻图中每个节点就是一个

于动态模型的聚类算法，该算法首先通过图划分

社区，依次合并有边相连的社区，并计算合并后的模块性增量。根据贪婪算法的原理，每次合并应

算法将数据对象聚类为大量相对较小的子聚类，

收稿日期： 1— 7一 1 2 1 0 O. 0 作者简介：安(95一，,靳延 17 )男河南郑州人，湖北经济学院信息管理学院博士.

基金项目：省教育科学“湖北十一五”规划科研基金资助项目(00 09; 21B3 )湖北省人文社科基金资助项目(009 ) 2104

本文来源：https://www.bwwdw.com/article/3r64.html