基于层次与划分方法的聚类算法研究

基于层次与划分方法的聚类算法研究

甄

彤

（华中科技大学控制科学与工程系，武汉４３００７４）（河南工业大学信息科学与工程学院，郑州４５００５２）

Ｅ－ｍａｉｌ：ｚｔ＠ｈａｕｔ．ｅｄｕ．ｃｎ

摘

要

针对在层次聚类算法中，一个分裂或合并被执行，就不能修正，其聚类质量受到限制的缺陷，提出了利用簇间相

异度及基于信息熵或整体相似度的聚类质量评价标准，在簇分裂过程中动态的进行簇的合并与分裂的算法。仿真实验结果证明，该算法具有使结果簇更紧凑和独立的效果，具有更好的聚类质量。关键词

层次聚类

相异度

信息熵

整体相似度

聚类质量

中图分类号ＴＰ３０１．６

文章编号１００２－８３３１－（２００６）０８－０１７８－０３文献标识码Ａ

ＲｅｓｅａｒｃｈｏｆＣｌｕｓｔｅｒｉｎｇＡｌｇｏｒｉｔｈｍＢａｓｅｄｏｎＨｉｅｒａｒｃｈｉｃａｌ

ａｎｄＰａｒｔｉｔｉｏｎｉｎｇＭｅｔｈｏｄ

ＺｈｅｎＴｏｎｇ

（ＤｅｐａｒｔｍｅｎｔｏｆＣｏｎｔｒｏｌＳｃｉｅｎｃｅａｎｄＥｎｇｉｎｅｅｒｉｎｇ，ＨｕａｚｈｏｎｇＵｎｉｖｅｒｓｉｔｙｏｆＳｃｉｅｎｃｅ

ａｎｄＴｅｃｈｎｏｌｏｇｙ，Ｗｕｈａｎ４３００７４）

（ＣｏｌｌｅｇｅｏｆＩｎｆｏｒｍａｔｉｏｎＳｃｉｅｎｃｅａｎｄＥｎｇｉｎｅｅｒｉｎｇ，ＨｅｎａｎＵｎｉｖｅｒｓｉｔｙｏｆＴｅｃｈｎｏｌｏｇｙ，Ｚｈｅｎｇｚｈｏｕ４５００５２）

Ａｂｓｔｒａｃｔ：Ｈｉｅｒａｒｃｈｉｃａｌｍｅｔｈｏｄｓｓｕｆｆｅｒｆｒｏｍｔｈｅｆａｃｔｔｈａｔｏｎｃｅａｍｅｒｇｅｏｒｓｐｌｉｔｉｓｄｏｎｅ，ｉｔｃａｎｎｅｖｅｒｂｅｕｎｄｏｎｅ．Ｔｈｉｓｐａｐｅｒｐｒｅｓｅｎｔｓａｃｌｕｓｔｅｒｉｎｇａｌｇｏｒｉｔｈｍｂａｓｅｄｏｎｈｉｅｒａｒｃｈｉｃａｌａｎｄｐａｒｔｉｔｉｏｎｉｎｇｍｅｔｈｏｄ．Ｄｕｒｉｎｇｔｈｅｓｐｌｉｔｐｒｏｃｅｓｓ，ｃｌｕｓｔｅｒｓａｒｅｍｅｒｇｅｄａｎｄｓｐｌｉｔｄｙｎａｍｉｃａｌｌｙｂｙｕｓｉｎｇｄｉｓｓｉｍｉｌａｒｉｔｙｍｅａｓｕｒｅｂｅｔｗｅｅｎｃｌｕｓｔｅｒｓａｎｄｅｎｔｒｏｐｙｏｒｏｖｅｒａｌｌｓｉｍｉｌａｒｉｔｙｔｏｅｖａｌｕａｔｅｔｈｅｃｌｕｓｔｅｒｑｕａｌｉｔｙ．Ｔｈｅｅｘｐｅｒｉｍｅｎｔｓｈｏｗｓｔｈｅｂｅｔｔｅｒｒｅｓｕｌｔｓｗｉｔｈｍｏｒｅｃｏｍｐａｃｔｎｅｓｓａｎｄｓｅｐａｒａｔｉｏｎ．Ｋｅｙｗｏｒｄｓ：ｈｉｅｒａｒｃｈｉｃａｌｃｌｕｓｔｅｒｉｎｇ，ｄｉｓｓｉｍｉｌａｒｉｔｙｍｅａｓｕｒｅ，ｅｎｔｒｏｐｙ，ｏｖｅｒａｌｌｓｉｍｉｌａｒｉｔｙ，ｃｌｕｓｔｅｒｑｕａｌｉｔｙ

数据挖掘是从大量数据中提取出可信、新颖、有效并能被人理解的模式的高级处理过程。其目标是从数据库中发现隐含的、有意义的知识。聚类分析作为一个独立的工具来获得数据所谓聚类，就是分布的情况，是数据挖掘的一个重要研究分支。

将物理或抽象对象的集合分组成为由类似的对象组成的多个类的过程。由聚类所生成的簇是一组数据对象的集合，在同一个类中的对象之间具有较高的相似度，而不同类中的对象差别较大。

迄今为止，人们己经提出了很多聚类算法，它们可以分为如下几类：划分方法（ｐａｒｔｉｔｉｏｎｉｎｇｍｅｔｈｏｄ）、层次方法（ｈｉｅｒａｒ－基于密度的方法（ｄｅｎｓｉｔｙ－ｂａｓｅｄｍｅｔｈｏｄ）、基于ｃｈｉｃａｌｍｅｔｈｏｄ）、

网格的方法（ｇｒｉｄ－ｂａｓｅｄｍｅｔｈｏｄ）和基于模型的方法（ｍｏｄｅｌ－

标准来决定是否取消合并以提高聚类质量。

１相关概念与原理

１．１划分与分层算法基本原理

给定一个包含ｎ个数据对象的数据库，以及要生成的簇的数目ｋ，一个划分算法采用一个划分准则将数据对象划分为ｋ个部分（ｋ≤ｎ），其中每个部分代表一个簇。最著名与最常用的划分方法是ｋ－ｍｅａｎｓ和ｋ－ｍｅｄｏｉｄ。

ｋ－ｍｅａｎｓ算法以一个聚类的重心（ＣｌｕｓｔｅｒＭｅａｎ）来表示一

个簇，所计算出的重心不一定是簇中的一个点。该方法对于“噪声”和孤立点数据是敏感的，少量的该类数据能够对平均值产生极大的影响。ｋ－ｍｅｄｏｉｄ算法以一个聚类的中心（Ｃｌｕｓｔｅｒ

ｂａｓｅｄｍｅｔｈｏｄ），这些算法对于不同的研究对象各有优缺点。

在聚类算法当中，划分方法和层次方法是最常见的两类聚类技术，其中划分方法具有较高的执行效率，而层次方法在算法上比较符合数据的特性，所以相对于划分方法聚类的效果比较好。但是层次聚类算法中，一旦一个分裂或合并被执行，就不能修正，其聚类质量受到限制，而且该算法执行速度相对地较慢。本文结合两者特性，在分裂的层次聚类基础上，在簇的分裂过程中，采用ｋ－ｍｅａｎｓ算法中以簇中对象的重心来表示一个簇的方法，并且在合并最相似的两个簇之后，利用聚类质量评价

基金项目：河南省自然科学基金资助项目（编号：２００４６０１０３６）

：（）男，，，Ｍｅｄｉｏｄ）来表示一个簇，选用簇中位置最中心的对象。当存在

“噪声”和孤立点数据时，ｋ－ｍｅｄｏｉｄ算法比ｋ－ｍｅａｎｓ算法更健壮，这是因为中心点不像平均值那么容易被极端数据影响。但是，ｋ－ｍｅｄｏｉｄ算法的执行代价比ｋ－ｍｅａｎｓ算法高。两种算法虽然在表示簇的方法上不一样，其执行步骤大致上是相同的，而且也都是以点到点的距离作为对象间的相似度。

一个层次的聚类方法将数据对象组成一颗聚类的树。根据层次分解是自底向上还是自顶向下形成，层次的聚类方法可以分为凝聚的和分裂的层次聚类。凝聚的层次聚类采用自底向上

１７８２００６．０８计算机工程与应用

的策略，首先将每个对象作为一个簇，然后合并这些原子簇为越来越大的簇，直到所有的对象都在一个簇中，或者满足某个终止条件。分裂的层次聚类采用自顶向下的策略，首先将所有对象置于一个簇中，然后逐渐细分为越来越小的簇，直到每个对象自成一簇，或者满足某个终止条件。

这里我们将层次聚类和其他的聚类技术（划分方法）进行集成，并进行动态的分裂与合并来提高层次方法的聚类质量。

非常重要的，因为这影响到聚类的结果。对于具有不同数据类型的对象以及混合类型的对象，其相异度的计算方法各不相同。

对象间相异度的计算可以扩充到簇间的相异度评价，各簇的中心点确定之后，就可以按照上述方法来计算簇间相异度。

１．２聚类质量评价标准

对聚类质量进行评价的常用技术有Ｅｎｔｒｏｐｙ和整体相似度。

２改进算法

２．１改进算法概述

层次的聚类方法的缺陷在于，一旦一个步骤（合并或分裂）完成，它就不能被撤销。为了改进层次聚类的结果，我们在分裂的层次聚类中动态的进行簇的分裂与合并，也即是在分裂完成之后，按照一定的准则合并簇，同时评价合并前后的聚类质量，如果合并使得聚类质量下降，就取消合并，从而提高聚类效果。

合并准则：计算当前各簇间的相异度，生成相异度矩阵，合并具有最小相异度的两个簇。

取消合并准则：假设使用Ｅｎｔｒｏｐｙ来评价聚类质量，计算合

ｉ

如果在分类之前已知聚类结果，只是将聚类结果与已知聚类结果进行比较，常使用Ｅｎｔｒｏｐｙ的概念；如果在聚类操作之前对聚类结果一无所知，我们常用整体相似度作为对聚类质量的评价。

１．２．１

Ｅｎｔｒｏｐｙ

Ｓｈａｎｎｏｎ提出信息熵概念的目的是用来解决随机事件或对信号所含信息量大小进行评价。设Ｘ是取有限个值的随机

变量，ｐｉ＝ｐ｛Ｘ＝ｘｉ｝，ｉ＝１，２，…，ｎ，则Ｘ的熵定义为Ｈ（ｘ）＝－

!ｐ

ｉ＝１

ｎ

并前后各簇的熵值和，如果合并之后熵值增大，则取消合并；反之，保留合并。若使用整体相似性来评价聚类质量，可以采用类似方法进行，总是使聚类质量向好的方向发展。

ｌｏｇｐｉ。信息熵是由事物内部属性客观决定的，熵的值是各个概

率值的函数。信息论中还证明当各个概率的值都相同时，信息熵的值最大。这个特性可以用来判断一个簇中同类元素出现的概率。当不同类元素均匀分布且出现概率相等时，其熵值最大；如果某一类元素出现机率较高，则其熵值较小；当集合中只有某一类元素出现时，其熵值为０。假设集合由Ａ和Ｂ两类对象组成，则该集合的熵值随Ａ类对象所占比例的变化曲线如图１所示。

２．２算法流程

输入：包含ｎ个对象的数据库和聚类停止参数（熵阈值）。输出：聚类结果。方法：

（１）将所有对象置于一个簇中；

（２）ｒｅｐｅａｔ

（３）计算当前所有簇的如下值：

ａ．每个簇的平均值（重心）ｗ；

ｂ．在簇中随机选取一对象Ｃｌ（不与簇重心重合）；ｃ．根据公式Ｃｒ＝ｗ－（Ｃｌ－ｗ）计算Ｃｒ；ｄ．将当前簇一分为二：

若｜ｏｉ－Ｃｌ｜＜｜ｏｉ－Ｃｒ｜，则ｏｉ∈左子树，否则ｏｉ∈右子树，其中ｏｉ取遍

当前簇中所有对象；

（４）当聚类数目ｍ≥４时，计算各簇间的相异度及熵值和ｅｂ，ｅｂ＝

１．２．２整体相似度

整体相似度（ＯｖｅｒａｌｌＳｉｍｉｌａｒｉｔｙ）是由簇内的凝聚力来衡量

ｍ

ｉｉ＝１

聚类质量。一个好的聚类其内部对象的分布应该是非常紧密的，当簇内的对象分布非常紧密时，每一对象与簇中心点的距离总和很近。反之，如果对象分布是松散的，簇内各对象到中心点的距离相对较大，簇的紧密程度随之较低。故整体相似度可由如下公式计算：

各对象点与中心点距离总和

整体相似度＝

簇内对象总数

!ｅ；

（５）合并最相似的两个簇，得ｍ－１个簇，计算合并后各簇的熵值

和ｅａ，ｅａ＝

!ｅ；

ｊｊ＝１

ｍ－１

（６）若ｅａ＞ｅｂ，取消合并；

（７）ｕｎｔｉｌｅａ＜ｅ或ｅｂ＜ｅ。

１．３相异度矩阵

存储ｎ个对象两两之间的近似性，其表现形式是一个ｎ×ｎ

３实验

３．１实例比较

我们用两个简单的例子来说明上述算法，在聚类过程中使用熵作为评价聚类质量的标准。

（１）合并后不拆分

假设有１０个数据的集合｛１，２，３，８，９，１０，１１，２０，２１，２２｝，已知该集合有三类数据｛１，２，３｝、｛８，９，１０，１１｝和｛２０，２１，２２｝，按照改进算法可得图３所示的聚类过程。

在第二层分裂为４个簇ｃ１＝｛１，２，３｝，ｃ２＝｛８，９，１０｝，ｃ３＝

维的矩阵，如图２所示。

$

%%%%%%%%%%%&

０ｄ（２，１）ｄ（３，１）

…

０ｄ（３，２）

…

０

……

…

ｄ（ｎ，１）ｄ（ｎ，２）０

’((((((((((()

图２相异度矩阵

｛１１｝，ｃ４＝｛２０，２１，２２｝。簇间相异度矩阵如图４所示。

图２ｄ（ｉ，ｊ）ｊ，ｉ），ｉ，ｉ）合并有小相异的个簇ｃ２而得三个

计算机工程与应用２００６．０８

１７９

效果。

３．２实验结果

为对该算法进行验证，本实验在二维坐标系中随机生成四

类数据对象，数据点的取样如图６所示。

在图６中的一、二、三、四区域中分别随机选取各不相同的数据对象１００个，５０个，１５０个和２００个。在聚类过程中生成的簇数目及所对应的熵值如表１所示。

表１

簇数量

改进算法中簇数目及熵值

１

２０．７９

３０．１９

６０．０６

１１０

簇：｛１，２，３｝、｛８，９，１０，１１｝和｛２０，２１，２２｝。合并前Ｅｎｔｒｏｐｙ＝

３

３

!!

ｉ＝１

ｊ＝１

４

３

Ｅｎｔｒｏｐｙ１．８５

如果在聚类过程中，每次仅将当前簇一分为二，其簇数目及所对应的熵值如表２所示。

表２

改进前算法中簇数目及熵值

１

２

４０．３８

８０．１１

１６０

－

ｐｉｊｌｏｇ２ｐｉｊ＝０，合并后Ｅｎｔｒｏｐｙ＝!!－ｐｉｊｌｏｇ２ｐｉｊ＝０，ｉ取当前簇

ｉ＝１

ｊ＝１

的数目，ｊ取集合中数据的分类数目，ｐｉｊ表示第ｉ个簇中第ｊ类数据所占的比例。熵为０意味着每个簇中的数据均为同一类数据，根据算法第６步可知，这时保留合并。这个规定是有用的，因为一个好的划分的准则是：在同一个类中的对象之间尽可能“接近”或相关，而不同类中对象之间尽可能“远离”或不同，也即是使生成后的结果簇尽可能地紧凑和独立。

（２）取消合并

假设有１２个数据的集合｛１，２，３，８，９，１０，１１，１５，１６，２０，

簇数量

Ｅｎｔｒｏｐｙ１．８５０．７９

由实验结果可以看出，改进后的层次算法具有更好的聚类效果。

该算法用ＶＣ６．０编写，在ＷｉｎｄｏｗｓＸＰ下运行。实验结果与各数据点的随机分布及各簇中随机选择的值有关。

２１，２２｝，已知该集合有四类数据｛１，２，３｝、｛８，９，１０，１１｝、｛１５，１６｝

和｛２０，２１，２２｝，按照改进算法可得图５所示的聚类过程。

４结论

本文在分裂的分层聚类算法的基础上，在簇分裂过程中采

用，每个簇用该簇中对象的平均值来表示，通过计算各簇间相异度进行簇的合并，并且采用聚类质量评价标准，对合并质量进行评价，动态地进行簇的合并与分裂。通过实验与改进前算法中的方法比较，本文所采用的算法具有更好的聚类效果。（收稿日期：２００５年１２月）

参考文献

１．ＪｉａｗｅｉＨａｎ，ＭｉｃｈｅｌｉｎｅＫａｍｂｅｒ，ＭｏｒｇａｎＫａｕｆｍａｎ．ＤａｔａＭｉｎｉｎｇ：ＣｏｎｃｅｐｔｓａｎｄＴｅｃｈｎｉｑｕｅｓ［Ｍ］．北京：高等教育出版社，２００１

２．王红卫，李琛，刘会新．马尔可夫决策过程复杂性的熵测度［Ｊ］．控制与决策，２００４；１９（９）：９８３￣９８７

计算簇间相异度后将合并具有最小相异度的两个簇Ｃ３和Ｃ４，从而得到三个簇：｛１，２，３｝、｛８，９，１０，１１｝和｛１５，１６，２０，２１，

４

４

３．ＭｉｃｈａｅｌＳｔｅｉｎｂａｃｈ，ＧｅｏｒｇｅＫａｒｙｐｉｓ，ＶｉｐｉｎＫｕｍａｒｅｔａｌ．Ａｃｏｍｐａｒｉｓｏｎｏｆ２０００，ＴｅｃｈｎｉｃａｌｒｅｐｏｒｔｏｆＤｏｃｕｍｅｎｔＣｌｕｓｔｅｒｉｎｇｔｅｃｈｎｉｑｕｅｓ［Ｒ］．Ｉｎ：ＫＤＤ’ＵｎｉｖｅｒｓｉｔｙｏｆＭｉｎｎｅｓｏｔａ．

４．ＣＨＣｈｅｎｇ，ＡＷＦｕ，ＹＺｈａｎｇ．Ｅｎｔｒｏｐｙ－ｂａｓｅｄＳｕｂｓｐａｃｅＣｌｕｓｔｅｒｉｎｇｆｏｒＭｉｎｉｎｇＮｕｍｅｒｉｃａｌＤａｔａ［Ｃ］．Ｉｎ：ＰｒｏｃｅｅｄｉｎｇｓｏｆｔｈｅＦｉｆｔｈＡＣＭｌＣｏｎｆｅｒｅｎｃｅｏｎＫｎｏｗｌｅｄｇｅＤｉｓｃｏｖｅｒｙａｎｄＤａｔａＭｉｎｉｎｇ，ＳＩＧＫＤＤＩｎｔ’１９９９：８４￣９３

５．吴帆，李石君．一种高效的层次聚类分析算法［Ｊ］．计算机工程，２００４；３０（９）：７０￣７１

２２｝。合并前Ｅｎｔｒｏｐｙ＝!!－ｐｉｊｌｏｇ２ｐｉｊ＝０，而在合并后的第三

ｉ＝１

ｊ＝１

个簇｛１５，１６，２０，２１，２２｝中，ｐ３１＝０，ｐ３２＝０，ｐ３３＝０．４，ｐ３４＝０．６，所以合并后Ｅｎｔｒｏｐｙ＝

!!－ｐ

ｉ＝１

ｊ＝１

３４

ｉｊ

ｌｏｇ２ｐｉｊ＝０．９７。由计算的熵值可知，合

并后的聚类质量低于合并前的聚类质量，故取消合并。

以上算法中，同样可以用整体相似度代替熵值来衡量聚类

１８０２００６．０８计算机工程与应用