一种改进的层次聚类算法

层次聚类算法

第33卷第6期2011年12月

武汉理工大学学报·信息与管理工程版

JOURNALOFWUT（INFORMATION＆MANAGEMENTENGINEERING）

Vol．33No．6Dec．2011文献标志码：A

文章编号：1007－144X（2011）06－0883－04

一种改进的层次聚类算法

靳延安，刘行军

（湖北经济学院信息管理学院，湖北武汉430205）

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

问题，在GN快速算法基础上提出了一种改进的凝聚式层次聚类算法，即网状聚类算法。实验结果表明，该改进算法避免了误差的积累，可以获得更高质量的聚类结果。关键词：聚类算法；网状聚类；模块性函数中图分类号：TP391

DOI：10．3963/j．issn．1007－144X．2011．06．009

聚类是把各不相同的个体分割为有更多相似

性的簇的工作。由聚类所组成的簇是一组数据对象的集合，这些对象与同一簇中的对象彼此类似，

［1］

与其他簇中的对象相异，目前，已有大量的聚类算法。根据数据的类型、目的和应用场景，主要

［2－3］

、的聚类算法通常分为划分方法层次方

［8－9］

、、基于密度的方法基于网格的方［10］［11－12］

。其中层次聚类算法和基于模型的方法

然后用一个凝聚的层次算法反复地合并子类来找

到真正的结果簇。这些算法都需要事先告知簇的数目，但是簇的数目是十分难以确定的，同时又非常敏感。NEWMAN提出了一个称为Newman快速算法的凝聚式聚类算法，该算法最开始用于社会网络图中的社区发现，算法不用事先设定社区的数目，而是通过模块性评价判定最佳聚类效

其所讨论的社区本质上是聚果而停止迭代聚类，

类中的簇。该方法具有较好的可伸缩性和较高的

效率，但同样要遇到合并点选择的困难，一旦其中的某一步有错误，这种错误将会叠加放大，从而降低聚类的效果。

为了解决上述问题，笔者提出了一种改进的Newman快速算法，即网状聚类算法（net－agglom-erativeclusteringalgorithm），并利用该算法在Iris数据集上做了测试。实验结果表明，该算法比传统层次聚类算法有更高的准确率。

［16］

法

［4－7］

法由于其简单，得到了广泛的应用。但该方法经

常会遇到合并或分裂点选择的问题。一旦一组对象被合并或者分裂，下一步的处理将在新生成的

已做的处理不能被撤销，聚类之间也不簇上进行，

能交换对象。若在某一步没有很好地选择合并或

分裂，可能导致低质量的聚类结果。为了改进层次聚类算法的质量，国内外学者

［13－15］

，进行了大量研究其中一个很有希望的改进方向是结合其他聚类技术形成多阶段聚类。LIN-VY等提出了BIRCH算法，该算法首先使用CF树结构对数据对象进行划分，然后采用其他算法

对聚类结果进行求精。该算法具有对数据对象数目的线性伸缩性，并且有较好的聚类质量，但是该算法对于非球形簇效果不是很好。GUHA等采用了随机取样和划分两种方法组合解决了偏好球形和相似大小的问题。KARYPIS等提出了一种基于动态模型的聚类算法，该算法首先通过图划分算法将数据对象聚类为大量相对较小的子聚类，

1

1．1

基于堆结构的Newman快速算法

基本思想

Newman快速算法实际上是基于贪婪算法思

想的一种凝聚算法。在社会网络图中（如图1所示），每两个有联系的节点都有一条边相连。具体思想是：假设起始时刻图中每个节点就是一个社区，依次合并有边相连的社区，并计算合并后的模块性增量。根据贪婪算法的原理，每次合并应

收稿日期：2011－07－01．

作者简介：靳延安（1975－），男，河南郑州人，湖北经济学院信息管理学院博士．

“十一五”基金项目：湖北省教育科学规划科研基金资助项目（2010B039）；湖北省人文社科基金资助项目（2010094）．

层次聚类算法

标记合并后社区的标号为j，更新应的社区i和j，

模块性增量矩阵ΔQ、最大堆H和辅助向量a。ΔQ的更新。删除第i行和第i列的元素，按式（3）更新第j行和第j列的元素： ΔQik+ΔQjk

ΔQik－2ajak

ΔQ'ij=

ΔQjk－2aiak

若社团k同时与社团i和社团j都相连

若社团k仅与社团i相连，不与社团j相连若社团k仅与社团j相不与社团i相连连，

图1社区示意图

该沿着使模块性增大最多或减少最小的方向进

行。每次合并以后，对相应的元素进行更新，不断合并社区，直到整个网络都合并成一个社区。实际上，不需要一直合并到成为一个社区，是由于在只用选择一个对应局部最大模这些社区结构中，块性的社区结构，就能得到最好的网络社区结构。当模块性增量矩阵中最大的元素都小于零以后，模块性的值就只可能一直下降。因此，只要模块性增量矩阵中最大的元素由正变到负以后，就可

并认为此时的社区结构就是网络的以停止合并，社区结构。

1．2数据结构

该算法用到了3种数据结构：

（1）模块性增量矩阵ΔQ。它与网络的连接是一个稀疏矩阵。将它的每一行都矩阵A一样，

存为一个平衡二叉树以及一个最大堆。

（2）最大堆H。该堆中包含了模块性增量矩阵ΔQ中每一行的最大元素，同时包括该元素相应的两个社区的编号i和j。

（3）辅助向量a。1．3

算法描述

（1）初始化。初始化网络为n个社区，即每个节点就是一个独立的社区。初始的模块性Q=

（3）

最大堆H的更新。每一次更新ΔQij后，就要更新最大堆中相应的行和列的最大元素。

辅助向量a的更新：

a'j=ai+aj；a'i=0同时，记录合并后的模块性：

Q=Q+ΔQ

（4）（5）

（3）重复步骤（2）直到网络中所有的节点都归到一个社区内。

Q仅有一个峰值（最大在整个算法过程中，

值）。只要模块性增量矩阵中最大的元素由正变到负以后，就可以停止合并，并认为此时的社区结构就是网络的社区结构（因为此时的模块性Q有最大值）。由于采用了堆数据结构，该算法在速但是该算法在选择合并点时，度上有较大的提高，

仍然存在一些问题。当两个社区合并以后，该算法用新的社区代替时，只计算剩余节点与新合并社区之间合并时模块性增量的变化，而没有再次计算剩余节点与原合并之前的模块性增量的变化，这可能导致合并点选错，当然就会影响最后聚类的结果。

ai满足式（1）：0。初始的eij，eij=

2

（1）

2．1

网状聚类算法

基本思想

笔者提出的网状聚类的算法的基本思想是：

{0

1/（2m）若节点i与j之间有边相连其他ai=ki/（2m）

其中：ki为节点i的度；m为网络中总的边条

数。初始的模块性增量矩阵的元素满足式（2）：ΔQij=

依次合并有边相连的社区并计算合并后的模块性增量。不只是计算新合并形成的社区与各个节点进行合并模块性的增量，还要计算新合并形成的社区内部各个节点与新合并社区之外节点进行合并的模块性的增量，取其中模块性增大最多或减少最小的方向进行下一次合并。每次合并以后，对相应的元素进行更新。这样，就可能存在一个数据对象与其他数据对象进行多次合并的情况，而不像一般层次聚类，每个数据对象可能只合并一次。通过不断合并社区，直到模块性增量矩阵

{

1/（ …… 此处隐藏：8897字，全部文档内容请下载后查看。喜欢就下载吧 ……