文档介绍：层次聚类分析算法的思考及实现
对急剧增长的数据加以组织和从数据中学习有价值信息的需要,使得聚类成为一个非常活跃的研究领域。不采用概括技术,人们很难从充斥着大量信息的数据库中发现知识。基本的统计量(如均值、方差)或者直方图可以提供对于数据的初步感觉。然而,聚类分析可以解释对象之间、特征之间以及对象和特征之间错综复杂的关系。它是数据挖掘中研究和应用的一个重要部分。
聚类分析简单来讲就是将数据对象分组成多个类或簇,在同一个簇中的对象之间具有较高的相似度,而不同簇中的对象差别较大。聚类分析是无指导学习。它与数据挖掘中的的分类不同,在分类模块中,对于目标数据库中存在哪些类这一信息我们是知道的,在那里要做的就是将每一条记录属于哪一类标记出来;与此相似但又不同的是,聚类是在预先不知道目标数据库到底有多少类的情况下,希望将所有的纪录组成不同的类或者说“聚类”(cluster)并且使得在这种分类情况下,以某种度量为标准的相异度,在同一聚类之间最小化,而在不同聚类之间最大化。
聚类分析方法主要有以下几种:划分方法,层次方法,基于密度的方法,基于网格的方法和基于模型的方法。本文主要讨论层次聚类方法。
层次聚类方法是聚类分析的一个重要方法。这种方法对给定的数据集合进行层次的分解,根据层次的分解如何形成,它又可分为凝聚法(也称自底向上方法)和分裂法(也称为从上向下方法),而凝聚的层次聚类方法应用得更多,该方法采用自底向上的策略,首先将每个对象作为一个簇,然后合并这些原子簇为越来越大的簇,直到所有的对象都在一个簇中,或者某个终结条件被满足。资格广泛采用的簇间距离度量方法分别为:最小距离、最大距离、平均值的距离、平均距离。本文主要讨论层次聚类算法中的平均距离算法。
层次聚类算法基本思想及其分析:
假定有N个对象被聚类,其距离矩阵大小为N*N,采用平均距离的凝聚层次聚类方法的基本过程如下:
将每一个数据对象视为一类,每类仅一个对象,计算它们之间的最短距离D,类与类之间的距离就是她们所包含对象之间的距离,得到初始化距离矩阵;(或者初始化矩阵作为已知参数给出)
将距离最近的两个类合并成一个新的类;
重新计算所有类之间的距离;
重复2和3步,知道所有类最后合并成一个类或者达到结束条件(该条件可人为指定)
层次聚类算法每合并完一个类后,就必须重新计算合并后类之间的距离,也就是重新计算距离矩阵,对于有大量数据的数据库而言,该计算量是惊人的。假定聚类的对象有N个,那么按照层次聚类算法的思想,第一次合并之前距离矩阵大小为N*N,第二次合并之前必须重新计算类与类之间的距离,距离矩阵大小变为(N-1)*(N-1),依次类推,直至所有类合并为一个类为止,相应的计算量为N*N阶,对于海量数据来说,这需要耗费大量的存储空间和计算时间。为了节省大量的计算时间,需要想办法在计算距离时应用到上次计算的结果,从而提高数据计算效率。
在上述算法中第一步时间复杂度为O(n*n),第二步的时间复杂度为O(n*n)(因为需要对距离矩阵进行检索,找出距离最小的两个类),第三步的时间复杂度同样为O(n*n)(对类之间距离进行更新,二维距离矩阵个数为1/2n*n),第四步的时间复杂度为O(1),第五步为O(1),由于第三步要运行N