06聚类分析方法与操作.doc

技术资料6： 聚类分析方法与操作 聚类是一种应用非常广泛的数据分析方法，它是统计学的一个分支，目前在诸多领域，包括数据挖掘、图像处理、市场研究等，都能凸显出其重要性。聚类是将一个对象的集合分成不同的类，从而描述数据。通过这种方式，人们能够将密集的和稀疏的区域区分开来，从而发现全局的分布模式，以及数据属性之间有趣的相互关系。 很久以前人们就对聚类方法有所研究。传统的聚类方法主要是基于距离的聚类，例如欧氏距离、切比雪夫距离、马氏距离[1]等。 在今天，聚类分析也是数据挖掘和知识发现领域中的重要课题。迄今为止，人们已经提出了许多数据聚类的算法，试图解决各种领域的聚类问题。 从目前来看，对数据挖掘中聚类方法的研究大都集中于计算机科学领域，更多注重聚类算法的研究，或者对现有聚类方法进行算法上的改进，而很少真正从统计学角度出发对数据挖掘中的聚类问题进行深入分析。若尝试从统计学视角出发，以统计理论为基础，以统计方法与算法相结合为基本思路，将一些现有的优秀统计方法，如因子分析、对应分析等引入数据挖掘领域，则能够使其应用于海量数据的聚类分析。 （一）聚类分析的基本概念 聚类是指将一群物理的或抽象的对象，根据它们之间的相似程度，分为若干组，并使得同一个组内的数据对象具有较高的相似度，而不同组中的数据对象则是不相似的。一个聚类就是由彼此相似的一组对象所构成的集合。在很多应用中，我们可以把同一个类的数据对象当做一个整体来处理。 聚类的严格数学描述如下：假设被研究的样本集为，类定义为的一个非空子集，即： ，且 聚类就是满足以下两个条件的类，，…，的集合： (1) … (2) = (对任意) 由第一个条件可知，样本集中的每个样本必定属于某一个类；由第二个条件可知，样本集中的每个样本最多只属于一个类。 （二）几种主要的聚类方法 如今各种各样的聚类方法层出不穷，我们在选用聚类方法时也会依据不同的标准，例如数据的类型、数据的大小等等。目前主要的聚类方法有：划分的方法、层次的方法、基于密度的方法、基于网格的方法等。 （1） 划分的方法 划分的方法是指将一个给定个数据对象的数据集合，构建数据的个划分，每个划分表示一个聚类，这个分组必须满足：每个组至少包含一个对象；每个对象必须属于且只属于一个组。给定要构建的划分的数目，划分方法首先创建一个初始划分，然后采用一种迭代的重定位技术，通过对象在划分间的移动来改进划分[3]。好的划分的一般准则是：同一分组中的距离越近越好，而不同分组中的距离越远越好，即使得下列的准则函数最小： 上式中是类的均值，是数据空间中的数据对象。属于该类的聚类方法有k-均值(k-means)算法、k-中心点(k-medoids)算法、PAM、CLARA、CLARANS等 。 （2）层次方法 将给定的数据对象集合进行层次的分解，这就是层次聚类法。我们可根据层次分解的形成方式不同，把层次方法分为凝聚的和分裂的。凝聚的方法首先把每个对象作为单独的一个组，然后相继地合并相近的对象或组，直到所有的组合并为一个(层次的最上层)，或者达到一个终止条件；分裂的方法首先把所有的对象置于一个聚类中，在每步迭代里，一个簇被分裂成更小的簇，直到最后每个对象在单独的一个簇中，或者达到一个终止条件[4]。 层次方法的缺陷在于，执行合并或分裂的操作不能被撤销。这个严格规定是有用的，由于不用担心组合数目的不同选择，故计算代价会较小。不过，该技术的一个主要问题是它不能改正错误的决定。我们可以通过两种方法来改进层次聚类的结果：一是在每层划分中，仔细分析对象之间的“联接”；二是把层次凝聚和迭代的重定位方法综合起来，先用自底向上的层次算法，再用迭代的重定位来改进结果。 层次方法包括BIRCH、CURE、ROCK、Chameleon算法等。 （3） 密度方法 绝大多数划分方法是基于对象之间的距离进行聚类的。这样的方法只能发现球状的簇，却在发现任意形状的簇上遇到了困难。随之提出了基于密度的聚类方法，它的主要思想是：只要邻近区域的密度(对象或数据点的数目)超过某个阈值，就继续聚类。 主要的基于密度的方法有：DBSCAN算法、OPTICS算法、DENCLUE算法等。 （4） 网格方法 基于网格的方法首先将数据空间量化为有限数目的单元，形成了一个网格结构，全部的聚类操作都在这个网格结构上进行。这种方法的主要优点在于它的处理速度很快，且处理时间与数据对象的数目相独立，只取决于量化空间中每一维的单元数目。 有代表性的网格方法是STING算法，除此之外，CLIQUE算法和Wavecluster算法既是基于网格的，又是基于密度的。 （三）聚类方法的进一步分析和总结 以上我们将现有的主要聚类方法大致分为划分的方法、层次的方法、基于密度的方法、基于网格的方法四大类。下面我们将从聚类标准、类的标