论文部分内容阅读
聚类分析是数据挖掘的一个非常活跃的研究方向。目前在文献中存在大量的聚类算法，算法的选择取决于数据的类型，聚类的目的和应用。迄今为止，主要的聚类算法可以划分为如下几类：1、划分方法，2、层次方法，3、基于密度的方法，4、基于网格的方法，5、基于模型的方法。
基于层次的聚类算法应用非常广泛，在基于层次的聚类算法中，凝聚的层次聚类算法应用的最为广泛。本文将针对传统的凝聚层次聚类算法存在的不足，提出了一种基于网格的凝聚层次聚类算法。改进算法能得到更好的聚类结果，并且时间复杂度比传统的凝聚层次聚类算法低。
首先，针对已存在的凝聚层次聚类算法的簇间距离度量方法的不足之处，提出了一种新的簇间距离度量方法，该方法有别于已存在的凝聚层次聚类算法中广泛应用的最小距离法、最大距离法，平均值的距离法、平均距离法。该簇间度量方法采用簇中权值最高的代表点的最小距离作为簇间的距离，有效消除了噪声对聚类结果的影响。
其次，传统的凝聚层次聚类算法的时间复杂度在最坏情况下为O(n<3>)，由于时间复杂度太高而无法应用到大的数据集。本文针对这一问题，将凝聚的层次聚类算法和基于网格的方法结合起来，先用基于网格的方法进行一次微聚类，然后再用凝聚的层次聚类算法进行聚类。该聚类方法的时间复杂度与基于网格的聚类算法一致，而且聚类效果达到了传统的凝聚层次聚类算法的效果。
最后，对本文提出的一种基于网格的凝聚层次聚类算法的时间和空间复杂度进行了分析，并进行了多次实验，实验结果表明，本文所提出的一种基于网格的凝聚层次聚类算法是正确和有效的。