层次聚类分析算法的思考及实现

《层次聚类分析算法的思考及实现》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、层次聚类分析算法的思考及实现一．概述对急剧增长的数据加以组织和从数据中学习有价值信息的需要，使得聚类成为一个非常活跃的研究领域。不采用概括技术，人们很难从充斥着大量信息的数据库中发现知识。基本的统计量（如均值、方差）或者直方图可以提供对于数据的初步感觉。然而，聚类分析可以解释对象之间、特征之间以及对象和特征之间错综复杂的关系。它是数据挖掘中研究和应用的一个重要部分。聚类分析简单来讲就是将数据对象分组成多个类或簇，在同一个簇中的对象之间具有较高的相似度，而不同簇中的对象差别较大。聚类分析是无指导学习。它与数据挖掘中

2、的的分类不同，在分类模块中，对于目标数据库中存在哪些类这一信息我们是知道的，在那里要做的就是将每一条记录属于哪一类标记出来；与此相似但又不同的是，聚类是在预先不知道目标数据库到底有多少类的情况下，希望将所有的纪录组成不同的类或者说“聚类”(cluster)并且使得在这种分类情况下，以某种度量为标准的相异度，在同一聚类之间最小化，而在不同聚类之间最大化。二．算法分析1．传统算法介绍聚类分析方法主要有以下几种：划分方法，层次方法，基于密度的方法，基于网格的方法和基于模型的方法。本文主要讨论层次聚类方法。层次聚类方法是

3、聚类分析的一个重要方法。这种方法对给定的数据集合进行层次的分解，根据层次的分解如何形成，它又可分为凝聚法(也称自底向上方法)和分裂法(也称为从上向下方法)，而凝聚的层次聚类方法应用得更多，该方法采用自底向上的策略，首先将每个对象作为一个簇，然后合并这些原子簇为越来越大的簇，直到所有的对象都在一个簇中，或者某个终结条件被满足。资格广泛采用的簇间距离度量方法分别为：最小距离、最大距离、平均值的距离、平均距离。本文主要讨论层次聚类算法中的平均距离算法。层次聚类算法基本思想及其分析：假定有N个对象被聚类，其距离矩阵大小为

4、N*N，采用平均距离的凝聚层次聚类方法的基本过程如下：1）将每一个数据对象视为一类，每类仅一个对象，计算它们之间的最短距离D，类与类之间的距离就是她们所包含对象之间的距离，得到初始化距离矩阵；（或者初始化矩阵作为已知参数给出）2）将距离最近的两个类合并成一个新的类；3）重新计算所有类之间的距离；4）重复2和3步，知道所有类最后合并成一个类或者达到结束条件（该条件可人为指定）层次聚类算法每合并完一个类后，就必须重新计算合并后类之间的距离，也就是重新计算距离矩阵，对于有大量数据的数据库而言，该计算量是惊人的。假定聚类

5、的对象有N个，那么按照层次聚类算法的思想，第一次合并之前距离矩阵大小为N*N，第二次合并之前必须重新计算类与类之间的距离，距离矩阵大小变为（N-1）*(N-1)，依次类推，直至所有类合并为一个类为止，相应的计算量为N*N阶，对于海量数据来说，这需要耗费大量的存储空间和计算时间。为了节省大量的计算时间，需要想办法在计算距离时应用到上次计算的结果，从而提高数据计算效率。2．传统算法分析在上述算法中第一步时间复杂度为O(n*n)，第二步的时间复杂度为O(n*n)（因为需要对距离矩阵进行检索，找出距离最小的两个类），第三

6、步的时间复杂度同样为O(n*n)（对类之间距离进行更新，二维距离矩阵个数为1/2n*n），第四步的时间复杂度为O(1)，第五步为O(1)，由于第三步要运行N-1次，因此整个算法的时间复杂度为O(n*n*n)。空间复杂度来看，由于算法需要建一个N阶相异度矩阵，故空间复杂度为O(n*n)。可以看出，第三步为整个算法的瓶颈，要是能降低第三步的时间复杂度，整个算法的性能就能得到提高。3．算法的改进对上述算法分析不难看出，算法整个的计算过程实际上就是第二步与第三步的不断重复过程，因此要想办法在第二步与第三步上尽可能地降低算

7、法的时间复杂度，或者减少计算类之间距离时不必要的计算量，针对第二步，因为需要找出所有类之间距离的最小值，而为了寻找最小值传统算法是遍历整个距离矩阵，进而找出，在此步不妨将堆的思想引入进来，首先为数据集中的所有数据对象建立基于堆的优先队列，优先队列中各个数据对象之间的距离从小到大排好，这样在找对象之间最小距离的时候便不用遍历，直接取出最小距离即可。而堆排序的基本思想就是把所有数据元素集合构成一个完全二叉树结构，则每次选择出一个最大（或最小）的数据元素只需比较完全二叉树的高度此，即logn，则整个堆排序的时间复杂度为

8、nlogn。在数据存储问题上，也就是选用什么样的数据结构来存储数据，该问题对于算法的最终实现也是至关重要的。最初想到的便是二维数组，因为这种存储结构可以方便的表示出各个点之间的距离，直观明了，但是考虑到该算法只有第一步初始化的时候是计算各个离群点之间的距离而后续循环步骤均是对不同的类之间的距离进行计算，而二维数组的行列无法正确表示出这些对象，所以该方案不可行，经过长时间思