凝聚层次聚类法

《凝聚层次聚类法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第３２卷第４期吉首大学学报（自然科学版）Ｖｏｌ．３２Ｎｏ．４２０１１年７月ＪｏｕｒｎａｌｏｆＪｉｓｈｏｕＵｎｉｖｅｒｓｉｔｙ（ＮａｔｕｒａｌＳｃｉｅｎｃｅＥｄｉｔｉｏｎ）Ｊｕｌ．２０１１文章编号：１００７２９８５（２０１１）０４００１１０４＊一种改进的凝聚层次聚类法刘文军，游兴中（长沙理工大学数学与计算科学学院，湖南长沙４１００７６）摘要：以实例说明了选用以欧氏距离或明考斯基距离为距离度量的凝聚层次聚类法进行聚类时会出现的问题，并详细分析了用该算法出现问题的原因．结合模糊聚类思想，给出了一种改进算法，通过实例说明该改进算法的合理性和有效性．关键词：数据挖掘；

2、聚类；距离；算法中图分类号：Ｏ１５９文献标志码：Ａ１问题的提出聚类分析是人们认识和探索事物内在联系的一种手段，“物以类聚，人以群分”是这一理念的最朴素和直观的反映，其目的是将一个数据集划分为若干聚类，并使得同一个聚类内的数据对象具有较高的相似［１］度，而不同聚类中的数据对象的相似度尽可能低．在商务上，聚类能帮助市场分析人员从客户基本库中［２３］发现不同的客户群，并且用购买模式来刻画不同的客户群的特征．在生物学上，聚类能用于推导植物和动物的分类，对基因进行分类，获得对种群固有结构的认识．聚类在地球观测数据库在相似地区的确定、汽车保险单持有者的分组，及根据房子的

3、类型、价值和地理位置对一个城市中房屋的分组上也可以发挥作用．聚类也能用于对Ｗｅｂ上的文档进行分类，以发现信息．作为一个数据挖掘的功能，聚类分析能作为一个独立的工具来获得数据分布的情况，观察每个簇的特点，集中对特定的某些簇做进一步的分析．此外，聚类分析可以作为其他算法的预处理步骤，这些算法再在生成的簇上进行处理．数据聚类正在蓬勃发展，在数据挖掘、统计学、机器学习、空间数据库技术、生物学以及市场营销领域［２３］中都取得了很好的应用．［４９］目前在文献中存在大量的聚类算法．算法的选择取决于数据的类型、聚类的目的和应用．大体上，主要的聚类算法可以划分如下几类：（１）

4、划分方法．给定一个ｎ个对象或元组的数据库，一个划分方法构建数据的ｋ个划分，每个划分表示一个簇，并且ｋ≤ｎ．也就是说，它将数据划分为ｋ个组，同时满足每个组至少包含１个对象，每个对象必须属于且只属于一个组．（２）层次的方法．层次的方法给定数据对象集合进行层次的分解．根据层次的分解如何形成，层次的方法可以分为凝聚的和分裂的．凝聚的方法，也称为自底向上的方法，一开始将每个对象作为单独的一个组，然后相继地合并相近的对象或组，直到所有的组合并为一个，或者达到一个终止条件．分裂的方法，也称为自顶向下的方法，一开始将所有的对象置于一个簇中，在迭代的每一步中，一个簇被分裂为更

5、小的簇，直到最终每个对象在单独的一个簇中，或者达到一个终止条件．（３）基于密度的方法．只要临近区域的密度超过某个阈值，就断续聚类．也就是说，对给定类中的每个数据点，在一个给定范围的区域中必须至少包含某个数目的点．（４）基于网格的方法．将对象空间量化为有限数目的单元，形成了一个网格结构，所有的聚类操作都在这个风格结构上进行．这种方法的主要优点是它的处理速度很快，其处理时间独立于数据对象的数目，只与量化空间中每一维的单元数目有关．（５）基于＊收稿日期：２０１１３２４基金项目：湖南省科技厅基金项目（２０１０ＦＪ４１３６）；湖南省教育厅项目基金（１０ｃ０４０３）作者

6、简介：刘文军（１９７１），男，湖南邵东人，长沙理工大学数学与计算科学学院副教授，博士，主要从事粗糙集与数据挖掘研究．１２吉首大学学报（自然科学版）第３２卷模型的方法．此方法为每个簇假定了一个模型，寻找数据对给定模型的最佳拟合．但不管用哪种方法进行聚类，其中都会牵涉到一个给定的度量，例如层次方法就是根据给定的距离度量进行凝聚或是分裂．［１０］在层次聚类法中，用到的距离度量通常是欧氏距离或明考斯基距离．但在实际操作中，直接用这２种距离度量来聚类有时会出问题．下面以层次方法中的凝聚法来说明这个问题．２凝聚层次聚类凝聚算法首先将每一个对象当作一个初始类，然后将这些类

7、合并成一个更粗略的分区，反复合并直到得到比较大的分区．这种聚类的过程是一个自底向上的过程，在凝聚的层次聚类算法中，又分为单链接和全链接算法．这２种基本算法的不同仅在于它们描述一对类的相似度的方法上．在单链接算法中，２个类之间的距离是从２个类中抽取的每对样本的距离中的最小值．在全链接算法中，２个类间的距离是每对样本的距离中的最大值，但它们都是基于最小距离标准将２个类合并成一个更大的类．对于这２种方法，凝聚聚类算法的基本步骤是相同的，如下：（ⅰ）将每一个样本作为一个类，为所有不同的无序样本对的类间距离构造一个序列，然后按升序对这个序列进行排序．（ⅱ）通过已排序的

8、距离序列，对每一个不同的阈值ｄｋ形成一个样本图，图中