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

层次聚类分析算法的思考及实现一．概述对急剧增长的数据加以组织和从数据中学习有价值信息的需要，使得聚类成为一个非常 活跃的研究领域不采用概括技术，人们很难从充斥着大量信息的数据库中发现知识基本 的统计量（如均值、方差）或者直方图可以提供对于数据的初步感觉然而，聚类分析可以 解释对象之间、特征之间以及对象和特征之间错综复杂的关系它是数据挖掘中研究和应用 的一个重要部分聚类分析简单来讲就是将数据对象分组成多个类或簇，在同一个簇中的对象之间具有较 高的相似度，而不同簇中的对象差别较大聚类分析是无指导学习它与数据挖掘中的的分 类不同，在分类模块中，对于目标数据库中存在哪些类这一信息我们是知道的，在那里要做 的就是将每一条记录属于哪一类标记出来；与此相似但又不同的是，聚类是在预先不知道目 标数据库到底有多少类的情况下，希望将所有的纪录组成不同的类或者说“聚类”（cluster） 并且使得在这种分类情况下，以某种度量为标准的相异度，在同一聚类之间最小化，而在不 同聚类之间最大化二．算法分析1．传统算法介绍聚类分析方法主要有以下几种：划分方法，层次方法，基于密度的方法，基于网格的方 法和基于模型的方法。

本文主要讨论层次聚类方法层次聚类方法是聚类分析的一个重要方法这种方法对给定的数据集合进行层次的分 解，根据层次的分解如何形成，它又可分为凝聚法（也称自底向上方法）和分裂法（也称为从上 向下方法），而凝聚的层次聚类方法应用得更多，该方法采用自底向上的策略，首先将每个 对象作为一个簇，然后合并这些原子簇为越来越大的簇，直到所有的对象都在一个簇中，或 者某个终结条件被满足资格广泛采用的簇间距离度量方法分别为：最小距离、最大距离、 平均值的距离、平均距离本文主要讨论层次聚类算法中的平均距离算法层次聚类算法基本思想及其分析：假定有N个对象被聚类，其距离矩阵大小为N*N,采用平均距离的凝聚层次聚类方法 的基本过程如下：1） 将每一个数据对象视为一类，每类仅一个对象，计算它们之间的最短距离D， 类与类之间的距离就是她们所包含对象之间的距离，得到初始化距离矩阵；（或 者初始化矩阵作为已知参数给出）2） 将距离最近的两个类合并成一个新的类；3） 重新计算所有类之间的距离；4） 重复 2和3步，知道所有类最后合并成一个类或者达到结束条件（该条件可人为指定）层次聚类算法每合并完一个类后，就必须重新计算合并后类之间的距离，也就是重新计 算距离矩阵,对于有大量数据的数据库而言，该计算量是惊人的。

假定聚类的对象有N个， 那么按照层次聚类算法的思想，第一次合并之前距离矩阵大小为N*N,第二次合并之前必 须重新计算类与类之间的距离，距离矩阵大小变为(N-l) *(N-1)，依次类推，直至所有类 合并为一个类为止，相应的计算量为N*N阶，对于海量数据来说，这需要耗费大量的存储 空间和计算时间为了节省大量的计算时间，需要想办法在计算距离时应用到上次计算的结 果，从而提高数据计算效率2．传统算法分析在上述算法中第一步时间复杂度为O(n*n),第二步的时间复杂度为O(n*n)(因为需要 对距离矩阵进行检索，找出距离最小的两个类)，第三步的时间复杂度同样为O(n*n)(对类 之间距离进行更新，二维距离矩阵个数为1/2n*n),第四步的时间复杂度为0(1)，第五步为 0(1)，由于第三步要运行N-1次，因此整个算法的时间复杂度为0(n*n*n)空间复杂度来 看，由于算法需要建一个N阶相异度矩阵，故空间复杂度为0(n*n)可以看出，第三步为 整个算法的瓶颈，要是能降低第三步的时间复杂度，整个算法的性能就能得到提高3．算法的改进对上述算法分析不难看出，算法整个的计算过程实际上就是第二步与第三步的不断重复 过程，因此要想办法在第二步与第三步上尽可能地降低算法的时间复杂度，或者减少计算类 之间距离时不必要的计算量，针对第二步，因为需要找出所有类之间距离的最小值，而为了 寻找最小值传统算法是遍历整个距离矩阵，进而找出，在此步不妨将堆的思想引入进来，首 先为数据集中的所有数据对象建立基于堆的优先队列，优先队列中各个数据对象之间的距离 从小到大排好，这样在找对象之间最小距离的时候便不用遍历，直接取出最小距离即可。

而 堆排序的基本思想就是把所有数据元素集合构成一个完全二叉树结构，则每次选择出一个最 大(或最小)的数据元素只需比较完全二叉树的高度此，即logn,则整个堆排序的时间复杂 度为 nlogn在数据存储问题上，也就是选用什么样的数据结构来存储数据，该问题对于算法的最终 实现也是至关重要的最初想到的便是二维数组，因为这种存储结构可以方便的表示出各个 点之间的距离，直观明了，但是考虑到该算法只有第一步初始化的时候是计算各个离群点之 间的距离而后续循环步骤均是对不同的类之间的距离进行计算，而二维数组的行列无法正确 表示出这些对象，所以该方案不可行，经过长时间思考，最终选定一种数据结构，如下图所 示：该存储结构中第一部分为类1，第二部分为类 2，第三部分为两个类之间的距离，而类 1 与类 2 中为一个线性列表，其中每一项为一个点当进行第一步的计算时，两个类中分别 只有一个点，类间距离即为两点之间的距离（由已知给出），有不同的点聚为一类时，在该 类的线性列表中将包含该类中所有的点，类与类间的距离通过平均欧式距离计算得到而第三步中传统算法涉及到计算目前所有类之间的距离问题，在数据量比较大的时候这 个过程是相当麻烦的，因为做了太多的重复计算，我们完全可以利用前一次已经计算好的结 果，对上一循环过程所产生的结果进行部分修改，而不是整体删除，整体重新计算。

如给定 五个点 1、2、3、4可以表示成下表可看出在该表中点3与点4 的距离最短为1，所以将这两个点合并为一类，更新距离列 表，将原来与点3 与点4有关的所有距离项删除（包含点3 与点4）然后添加新类与剩下所 有类的距离，而表中原来未涉及到点3与点4的距离则不用更新，此过程只需计算N次， 而非N*N次更新后的距离列表如下图所示：1233,4133,423三．改进后算法的实现改进后的算法使用 JAVA 语言实现，用 JAVA 语言中 ArrayList 代表上述算法描述中的线 性列表如下表所示：ArrayListlArrayList2类间距离程序运行的主界面如下所示：该程序输入参数有四个1. 考虑到一般的聚类分析都是针对大量数据，所以设置参数的输入为文件输 入，其中可以用TXT格式的记事本文件，也可用EXCEL表格来作为已知参 数，2. “点集个数”用来指出点集的总个数3. “计算过程文件”用来设置计算过程文件的保存，考虑到数据量大时，对每 一次聚类中间结果都显示到主界面中的话，不仅不方便用户查看同时影响界 面美观，故为了清晰记录整个聚类的过程，所以将该过程通过文件的形式保 存，方便用户日后查看。

4. “目标类个数”用来指定将点集聚成多少个类，默认为1其中程序运行的最终结果会显示在主界面中下面通过一个实例来演示该程序1.选择文件（该文件只是用来测试，数据量较小，故用TXT格式），文件内容如下0 4 5 6 7 90 0 1 2 3 50 0 0 2 2 40 0 0 0 3 20 0 0 0 0 20 0 0 0 0 0供包含六个点，点之间距离通过二维数组给出2．设置其他相应参数点集个数”为6，“目标类个数”设置为3计算过程文件” 设置为 D:\234234.TXT3．点击“计算”按钮程序运行结果如下所示：计算过程文件如下所示：⑶[3j [即] [5][1,肌[11][3] 6.6 [町聲]7.6 [町[刃9詡 [3][4] 3.6 [3][5] 2-6 [即][刃2-8 间口，2J 4.5 [3][1, 2] 2-^ [即]口，2J 2-5 [5][1, 2J 4.5[0][即][1,肌[3, 5J[迢[即]gtf[时口，2J 4.5[即]口，2J 2-5[时[3, 5] 7-5|W- 5] 2-5[1, 2][3, 5] 3-25［叫[3, 5]［町1,対[时[3, 5] 7.5[^|[4, 1, 2] 5.333333333333333[3, 5][4, 1, 2J 3.^说明：该过程文件每一步均有分割线作为标记，其中每一步包含两部分，第一部分为当 前总的类数目，第二部分为这些类之间的距离。

四．结束语本文的算法主要从提高距离的检索速度以及应用前一次计算结果数据避免不必要的时 间浪费方面来改善算法性能，从而缩短了时间该程序的设计基于本文提供的算法，完全由 作者本人设计，经过大量数据的测试，程序运行状况良好，对于小规模层次聚类问题提供了 很好的技术支持。