聚类分析（三）——层次聚类算法

《聚类分析（三）——层次聚类算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、聚类分析（三）——层次聚类算法12层次聚类算法：前面介绍的K-means算法和K中心点算法都属于划分式（partitional）聚类算法。层次聚类算法是将所有的样本点自底向上合并组成一棵树或者自顶向下分裂成一棵树的过程，这两种方式分别称为凝聚和分裂。凝聚层次算法:初始阶段，将每个样本点分别当做其类簇，然后合并这些原子类簇直至达到预期的类簇数或者其他终止条件。分裂层次算法:初始阶段，将所有的样本点当做同一类簇，然后分裂这个大类簇直至达到预期的类簇数或者其他终止条件。两种算法的代表：传统的凝聚层次聚类算法有AGENES，初始时，AGENES将每个样本点自为一簇，然后这些

2、簇根据某种准则逐渐合并，例如，如果簇C1中的一个样本点和簇C2中的一个样本点之间的距离是所有不同类簇的样本点间欧几里得距离最近的，则认为簇C1和簇C2是相似可合并的。传统的分裂层次聚类算法有DIANA，初始时DIANA将所有样本点归为同一类簇，然后根据某种准则进行逐渐分裂，例如类簇C中两个样本点A和B之间的距离是类簇C中所有样本点间距离最远的一对，那么样本点A和B将分裂成两个簇C1和C2，并且先前类簇C中其他样本点根据与A和B之间的距离，分别纳入到簇C1和C2中,例如，类簇C中样本点O与样本点A的欧几里得距离为2，与样本点B的欧几里得距离为4，因为Distance(

3、A，O)如图所示：算法：AGENES。传统凝聚层次聚类算法输入：K：目标类簇数D：样本点集合输出：K个类簇集合方法：1)将D中每个样本点当做其类簇；2)repeat3)   找到分属两个不同类簇，且距离最近的样本点对；4)   将两个类簇合并；5)util类簇数=K算法：DIANA。传统分裂层次聚类算法输入：K：目标类簇数D：样本点集合输出：K个类簇集合方法：1)12将D中所有样本点归并成类簇；2)repeat3)   在同类簇中找到距离最远的样本点对；4)   以该样本点对为代表，将原类簇中的样本点重新分属到新类簇5)util类簇数=K缺点：传统的层次聚类算法的效

4、率比较低O(tn2)t:迭代次数n:样本点数，最明显的一个缺点是不具有再分配能力，即如果样本点A在某次迭代过程中已经划分给类簇C1，那么在后面的迭代过程中A将永远属于类簇C1，这将影响聚类结果的准确性。改进：一般情况下，层次聚类通常和划分式聚类算法组合，这样既可以解决算法效率的问题，又能解决样本点再分配的问题，在后面将介绍BIRCH算法。首先把邻近样本点划分到微簇(microcluseters)中，然后对这些微簇使用K-means算法。----------------贴上本人实现的AGENES算法，大家有兴趣可以把DIANA算法自己实现下--------------

5、-packagecom.agenes;publicclassDataPoint{StringdataPointName;//样本点名Clustercluster;//12样本点所属类簇privatedoubledimensioin[];//样本点的维度publicDataPoint(){}publicDataPoint(double[]dimensioin,StringdataPointName){this.dataPointName=dataPointName;this.dimensioin=dimensioin;}publicdouble[]getDimensi

6、oin(){returndimensioin;}publicvoidsetDimensioin(double[]dimensioin){this.dimensioin=dimensioin;}publicClustergetCluster(){returncluster;}publicvoidsetCluster(Clustercluster){this.cluster=cluster;}publicStringgetDataPointName(){return12dataPointName;}publicvoidsetDataPointName(Stringdat

7、aPointName){this.dataPointName=dataPointName;}}packagecom.agenes;importjava.util.ArrayList;importjava.util.List;publicclassCluster{privateListdataPoints=newArrayList();//类簇中的样本点privateStringclusterName;publicListgetDataPoints(){returndataPoints;}publicvoidsetDataPoints(ListdataPoints