第１９卷　第１５期　Ｖｏｌ＿１９　Ｎｏ．１５　电子设计工程　Ｅｌｅｃｔｒｏｎｉｃ　Ｄｅｓｉｇｎ　Ｅｎｇｉｎｅｅ　２０１１年８月　Ａｕｇ．２０１１　

聚类算法及聚类融合算法研究　

赵向梅，王艳君，刘林　

（西安欧亚学院信息工程学院，陕西西安７１００６５）　

摘要：基于常用聚类算法及聚类融合算法进行了研究。首先阐述了数据挖掘领域的常用聚类算法及特点，接下来对近　

年来聚类融合的方法和研究现状进行了综述，并对如何产生高效的聚类成员和共识函数如何构建才能产生高效的聚　类融合算法进行了说明　运用改进的随机投影算法来生成聚类成员，实验表明随机投影是一个生成聚类成员的很有　

效的方法。最后得出运用聚类融合算法能得到更好的聚类效果的结论。　

关键词：聚类算法：聚类融合；数据挖掘；聚类分析　

中图分类号：ＴＰ３１２　文献标识码：Ａ　文章编号：１６７４—６２３６（２０１１）１５—０００４—０２　

Ｒｅｓｅａｒｃｈ　ｏｎ　ｃｌｕｓｔｅｒｉｎｇ　ａｌｇｏｒｉｔｈｍｓ　ａｎｄ　ｃｌｕｓｔｅｒｉｎｇ　ｅｎｓｅｍｂｌｅ　ａｌｇｏｒｉｔｈｍｓ　

ＺＨＡ０　Ｘｉａｎｇ—ｍｅｉ，ＷＡＮＧ　Ｙａｎ－ｊｕｎ，ＬＩＵ　Ｌｉｎ　

（Ｓｃｈｏｏｌ　ｏｆＩｎｆｏｒｍａｔｉｏｎ　Ｅｎｇｉｎｅｅｒｉｎｇ，Ｘｉ＂ａｎ　Ｅｕｒａｓｉａ　Ｕｎｉｖｅｒｓｉｔｙ，Ｘｉ＂ａｎ　７１００６５，Ｃｈｉｎａ）　

Ａｂｓｔｒａｃｔ：Ｔｈｅ　ｃｏｍｍｏｎ　ｃｌｕｓｔｅｒｉｎｇ　ａｌｇｏｒｉｔｈｍｓ　ａｎｄ　ｃｌｕｓｔｅｒｉｎｇ　ｅｎｓｅｍｂｌｅ　ａｌｇｏｒｉｔｈｍｓ　ａｒｅ　ｓｔｕｄｉｅｄ．Ｉｔ　ｉｎｃｌｕｄｅｓ　ｔｈｅ　ｃｈａｒａｃｔｅｒｉｓｔｉｃｓ　

ｏｆ　ｔｈｅ　ｃｏｍｍｏｎ　ｃｌｕｓｔｅｒｉｎｇ　ａｌｇｏｒｉｔｈｍｓ　ｉｎ　ｄａｔａ　ｍｉｎｉｎｇ　ａｔ　ｆｉｒｓｔ，ｔｈｅｎ　ｍａｋｅｓ　ａｎ　ｏｖｅｒｖｉｅｗ　ａｎｄ　ｔｈｅ　ｒｅｓｅａｒｃｈ　ｓｔａｔｕｓ　ｏｆ　ｔｈｅ　ｃｌｕｓｔｅｒｉｎｇ　

ｅｎｓｅｍｂｌｅ　ａｐｐｒｏａｃｈｅｓ．Ａｎｄ　ｉｔ　ｉｎｃｌｕｄｅｓ　ｈｏｗ　ｔｏ　ｇｅｎｅｒａｔｅ　ｅｆｆｉｃｉｅｎｔ　ｆｕｎｃｔｉｏｎ　ｏｆ　ｔｈｅ　ｃｌｕｓｔｅｒ　ｍｅｍｈｅ￣ａｎｄ　ｈｏｗ　ｔｏ　ｂｕｉｌｄ　ａ　

ｃｏｎｓｅｎｓｕｓ　ｔｏ　ｇｅｎｅｒａｔｅ　ｅｆｆｉｃｉｅｎｔ　ｃｌｕｓｔｅｒｉｎｇ　ｆｕｓｉｏｎ　ａｌｇｏｒｉｔｈｍ．Ｉｍｐｒｏｖｅｄ　ｒａｎｄｏｍ　ｐｒｏｊｅｃｔｉｏｎ　ｉｓ　ｐｒｏｐｏｓｅｄ　ａｎｄ　ｕｓｅｄ　ｉｎ　ｔｈｅ　ｃｌｕｓｔｅｒ　ｅｎｓｅｍｂｌｅ　ａｐｐｒｏａｃｈ，ｔｈｅ　ｅｘｐｅｒｉｍｅｎｔｓ　ｓｈｏｗ　ｔｈａｔ　ｔｈｅ　ｇｅｎｅｒａｔｅｄ　ｒａｎｄｏｍ　ｐｒｏｊｅｃｔｉｏｎ　ｉｓ　ａ　ｍｅｍｂｅｒ　ｏｆ　ｔｈｅ　ｅｆｆｅｃｔｉｖｅ　ｃｌｕｓｔｅｒｉｎｇ　

ｍｅｔｈｏｄ．Ｆｉｎａｌｌｙ，ｉｔ　ｃｏｍｅｓ　ｔｏ　ｔｈｅ　ｃｏｎｃｌｕｓｉｏｎ　ｔｈａｔ　ｔｈｅ　ｕｓｅ　ｏｆ　ｃｌｕｓｔｅｒ　ｆｕｓｉｏｎ　ａｌｇｏｒｉｔｈｍ　ｃａｎ　ｇｅｔ　ｂｅｔｔｅｒ　ｃｌｕｓｔｅｒｉｎｇ　ｒｅｓｕｌｔ．　

Ｋｅｙ　ｗｏｒｄｓ：ｃｌｕｓｔｅｒｉｎｇ　ａｌｇｏｒｉｔｈｍｓ；ｃｌｕｓｔｅｒｉｎｇ　ｅｎｓｅｍｂｌｅ；ｄａｔａ　ｍｉｎｉｎｇ；ｃｌｕｓｔｅｒｉｎｇ　ａｎａｌｙｓｉｓ　

俗话说：“物以类聚，人以群分”．在自然科学和社会科学　

中，存在着大量的分类问题。将物理或抽象对象的集合分组　

成为由类似的对象组成的多个类的过程称为聚类［１１。为了找　

到效率高、通用性强的聚类方法。人们从不同角度提出了许　

多种聚类算法，一般可分为基于层次的，基于划分的，基于密　

度的，基于网格的和基于模型的聚类算法５大类。　

１常用聚类算法介绍　

１．１基于层次的聚类算法　

基于层次的聚类算法对给定数据对象进行层次上的分　

解，直到某种条件满足为止，可分为凝聚算法和分裂算法。例　

如在自底向上的凝聚算法方案中．初始时每一个数据纪录都　

组成一个单独的组，在接下来的迭代中，它把那些相互邻近　

的组合并成一个组。直到所有的记录组成一个分组或者某个　

条件满足为止。代表算法有：ＢＩＲＣＨ算法、ＣＵＲＥ算法、　

ＣＨＡＭＥＬＥ０Ｎ算法等。　

１．２基于划分的聚类算法　

给定一个有Ⅳ个元组或者纪录的数据集，分裂法将构造　个分组，每一个分组就代表一个聚类，Ｋ＜Ｎ。而且这Ｋ个分　

组满足下列条件：１）每一个分组至少包含一个数据纪录；２）　每一个数据纪录属于且仅属于一个分组：对于给定的Ｋ，算　

法首先给出一个初始的分组方法，以后通过反复迭代的方法　

改变分组，使得每一次改进之后的分组方案都较前一次好，　

而所谓好的标准就是：同一分组中的记录越近越好．而不同　

分组中的纪录越远越好。使用这个基本思想的算法有：Ｋ—　

ＭＥＡＮＳ算法、Ｋ—ＭＥＤ０ＩＤＳ算法、ＣＬＡＲＡＮＳ算法。　划分法收敛速度快。在对中小规模的数据库中发现球状　

簇很适用。缺点是它倾向于识别凸形分布大小相近、密度相　

近的聚类，不能发现分布形状比较复杂的聚类，还要求用户　

预先指定聚类个数。　１．３基于密度的聚类算法　

基于密度的聚类算法．其指导思想是：只要一个区域中　

的点的密度（对象或数据点的数目）大过某个阈值，就把它加　

到与之相近的聚类中去。该法从数据对象的分布密度出发，　

把密度足够大的区域连接起来，从而可发现任意形状的簇，　

并可用来过滤“噪声”数据。常见算法有ＤＢＳＣＡＮ，ＤＥＮＣＬＵＥ　

算法等。　收稿日期：２０１１－０３—３１　稿件编号：２０１１０３１７９　

基金项目：西安欧亚学院科研基金项目资助（ＺＫＢ一１０—０８）；西安欧亚学院资助陕西省教育厅科学研究计划项目（１１ＪＫ１０５６）　

作者简介：赵向梅（１９８０一），女，陕西凤翔人，硕士，讲师。研究方向：计算机应用研究。　

－

４－　赵向梅，等聚类算法及聚类融合算法研究　

１Ａ基于网格的聚类算法　首先将数据空间划分为有限个单元的网格结构。然后对　

划分后的单个的单元为对象进行聚类。该算法优点是处理速　

度快，处理时间与数据对象的数目无关，一般由网格单元的　

数目决定。缺点是只能发现边界是水平或垂直的聚类，不能　

检测到斜边界，该类算法也不适用于高维情况。典型的算法　

有ＳＴＩＮＧ，ＣＬＩＱＵＥ等。　１．５基于模型的聚类算法　

基于模型的方法给每一个聚类假定了一个模型．然后去　

寻找能够很好满足这个模型的数据集。这个模型可能是数据　

点在空间中的密度分布函数，它由一系列的概率分布决定，　

也可能通过基于标准的统计数字自动决定聚类的数目。它的　

一个潜在假定是：目标数据集是由一系列的概率分布所决定　

的。通常有２种尝试方向：统计的方案和神经网络的方案。　

２聚类融合　

处理很多现实问题时。需要将数据聚类。例如银行根据　

客户的个人属性、交易行为等对客户进行风险评估，其数据　

集不但海量，而且数据属性包括数值属性和类属性田。以上列　

出的５种常用聚类算法不能有效处理这类数据集，无法对类　

属性和混合型属性的数据集进行聚类。　

聚类融合方法是近年聚类分析的研究趋势，其基本思想　

是用若干独立的聚类器分别对原始数据进行聚类，然后对这　

些结果进行组合，最终获得对原始数据进行的聚类结果。详细　

说明如下所示：设有Ⅳ个样本的样本集　，对数据集　进行Ｈ　

次不同聚类算法得到Ｈ次聚类结果圆。通过共识函数Ｇ，把Ｈ　

次聚类得到的聚类成员融合得到Ｃ　，融合过程如图１所示。　

圈１聚类融合过程图　Ｆｉｇ．１　Ｐｒｏｃｅｄｕｒｅ　ｃｈａｒｔ　ｏｆ　ｃｌｕｓｔｅｒｉｎｇ　ｆｕｓｉｏｎ　

聚类融合算法比单一聚类算法具有鲁棒性、稳定性和适　

用型等优势。因此，目前聚类融合研究的重点一般是：如何产　

生高效的聚类成员；共识函数如何构建才能产生高效的聚类　

融合算法。　

２．１聚类成员产生　

可以通过选择不同的算法，对同一个算法选择不同的初　

始值、选择不同的对象子集及选择不同的特征子集投影到数　

据子空间等来产生聚类成员。　

Ｔｏｐｃｈｙ￣等主要研究了由“弱”聚类组成的聚类成员对聚　

类融合的影响。“弱”聚类指比随机划分好一点的聚类。他们　

用实验结果表明，由“弱”聚类组成聚类成员实现的聚类融合　

算法，其结果普遍好于单一的经典聚类算法。　Ｆｅｒｎ和Ｂｒｏｄｌｅｙｔ￣通过实验说明，在不同的随机投影下得　

到的不同的聚类结果是互补的，由此可以推测基于随机投影　

的方法是一个获得聚类成员的很好方法。　

２．２改进的随机投影聚类方法　

下面对一种改进的随机投影方法［６１进行说明，算法具体　步骤如下：　

１）在原始数据集　中随机选择ｋ个初始聚类中心：　

２）计算原始记录中每个属性Ａ　所有类别取值ｔｔ　对应的　

频率，将频率满足条件　）　的记录保存在二维数组中；　

３）根据得到的二维数组选择保存与聚类中心关系密切　

的维向量　１　≥ｍ；扫描目标数据集，寻找与每条记录最相　

似的聚类中心实现聚类，对小于界限值的记录进行归类：　

４）从初始的随机聚类中心中选择并保存好的聚类中心，　

删除无效的聚类中心，算法的选择标准为若该聚类中的所有　

记录所属类别相同，则将相关记录从待测数据集　中移除。　

若记录数大于界限值，返回步骤１）；　

５）对于未被聚类的数据对象作为异常点处理。　

运用该方法生成聚类成员．实验表明问它能够得到更多　

类别的基本聚类成员，融合性能好。　

２．３共识函数的构建　

共识函数的设计方法主要有共联矩阵法、投票法、信息　

论方法、超图法和混合模型法。　

Ｔｏｐｃｈｙ等用一个多项式分布的混合模型构建共识函数。　

然后使用ＥＭ算法求解最终的聚类。这种方法完全避免了标　

志匹配的问题，而且能够处理丢失的数据。　

３结　论　

本文研究了常用聚类算法及聚类融合算法。并对如何产　

生高效的聚类成员和共识函数如何构建才能产生高效的聚　

类融合算法进行了说明。运用改进的随机投影算法来生成聚　

类成员，实验表明随机投影是一个生成聚类成员的很有效的　

方法。最后得出运用聚类融合算法能得到更好的聚类效果的　

结论。如何把聚类融合方法运用到具体问题上，是下一步研　

究的方向。　

参考文献：　

【１】ＨＡＮ　Ｊｉａ—ｗｅｉ．Ｄａｔａ　ｍｉｎｉｎｇ：ｃｏｎｃｅｐｔｓ　ａｎｄ　ｔｅｃｈｎｉｑｕｅｓ【Ｍ】．Ｓａｎ　Ｆｒａｎｃｉｓｃｏ：Ｍｏｒｇａｎ　Ｋａｕｆｍａｎｎ　Ｐｕｂｌｉｓｈｅｒｓ．２０Ｏ１．　【２］赵宁，李兵，李秀，等．混合属性数据聚类融合算法【Ｊ］．清华　

大学学报：自然科学版，２００６，４６（１０）：１６７３—１６７６．　

ＺＨＡＯ　Ｙｕ，ＬＩ　Ｂｉｎｇ，ＬＩ　Ｘｉｕ，ｅｔ　ａ１．Ｃｌｕｓｔｅｒ　ｅｎｓｅｍｂｌｅ　ｍｅｔｈｏｄ　

ｆｏｒ　ｄａｔａｂａｓｅｓ　ｗｉｔｈ　ｍｉｘｅｄ　ｎｕｍｅｒｉｃ　ａｎｄ　ｃａｔｅｇｏｒｉｃａｌ　ｖ￣ｕｅｓ叫．　

Ｊｏｕｒｎａｌ　ｏｆ　Ｔｓｉｎｇｈｕａ　Ｕｎｉｖｅｒｓｉｔｙ：Ｓｃｉｅｎｃｅ　ａｎｄ　Ｔｅｃｈｎｏｌｏｇｙ，　

２００６，４６（１０）：１６７３—１６７６．　

［３】秦锋，陈奇明，程泽凯．聚类融合算法研究［Ｊ］．计算机技术与　

发展，２０１０，２０（７）：１０６—１０８。ｌｌ３．　

ＱＩＮ　Ｆｅｎｇ，ＣＨＥＮ　Ｑｉ—ｍｉｎｇ，ＣＨＥＮＧ　Ｚｅ—ｋａｉ．Ａｎ　ｏｖｅｒｖｉｅｗ　ｏｆ　

（下转第１２页）　

－

５－