数据挖掘CHAPTER8聚类分析[统计学经典理论].doc

第八章聚类分析
设想要求对一个数据对象的集合进行分析,但与分类不同的是,它要划分的类是未知的。聚类(clustering)就是将数据对象分组成为多个类或簇(cluster),在同一个簇中的对象之间具有较高的相似度,而不同簇中的对象差别较大。相异度是基于描述对象的属性值来计算的。距离是经常采用的度量方式。聚类分析源于许多研究领域,包括数据挖掘,统计学,生物学,以及机器学习。
在本章中,大家将了解基于大数据量上进行操作而对聚类方法提出的要求,将学习如何计算由各种属性和不同的类型来表示的对象之间的相异度。还将学习几种聚类技术,它们可以分为如下几类:划分方法(partitioning method),层次方法(hierarchical method),基于密度的方法(density-based method),基于网格的方法(grid-based method),和基于模型的方法(model-based method)。本章最后讨论如何利用聚类方法进行孤立点分析(outlier detection)。
什么是聚类分析?
将物理或抽象对象的集合分组成为由类似的对象组成的多个类的过程被称为聚类。由聚类所生成的簇是一组数据对象的集合,这些对象与同一个簇中的对象彼此相似,与其他簇中的对象相异。在许多应用中,一个簇中的数据对象可以被作为一个整体来对待。
聚类分析是一种重要的人类行为。早在孩提时代,一个人就通过不断地改进下意识中的聚类模式来学会如何区分猫和狗,或者动物和植物。聚类分析已经广泛地用在许多应用中,包括模式识别,数据分析,图像处理,以及市场研究。通过聚类,一个人能识别密集的和稀疏的区域,因而发现全局的分布模式,以及数据属性之间的有趣的相互关系。
“聚类的典型应用是什么?”在商业上,聚类能帮助市场分析人员从客户基本库中发现不同的客户群,并且用购买模式来刻画不同的客户群的特征。在生物学上,聚类能用于推导植物和动物的分类,对基因进行分类,获得对种群中固有结构的认识。聚类在地球观测数据库中相似地区的确定,汽车保险持有者的分组,及根据房子的类型,价值,和地理位置对一个城市中房屋的分组上也可以发挥作用。聚类也能用于对Web上的文档进行分类,以发现信息。作为一个数据挖掘的功能,聚类分析能作为一个独立的工具来获得数据分布的情况,观察每个簇的特点,集中对特定的某些簇作进一步的分析。此外,聚类分析可以作为其他算法(如分类等)的预处理步骤,这些算法再在生成的簇上进行处理。
数据聚类正在蓬勃发展,有贡献的研究领域包括数据挖掘,统计学,机器学习,空间数据库技术,生物学,以及市场营销。由于数据库中收集了大量的数据,聚类分析已经成为数据挖掘研究领域中一个非常活跃的研究课题。
作为统计学的一个分支,聚类分析已经被广泛地研究了许多年,主要集中在基于距离的聚类分析。基于k-means(k-平均值),k-medoids(k-中心)和其他一些方法的聚类分析工具已经被加入到许多统计分析软件包或系统中,例如S-Plus,SPSS,以及SAS。在机器学习领域,聚类是无指导学习(unsupervised learning)的一个例子。与分类不同,聚类和无指导学习不依赖预先定义的类和训练样本。由于这个原因,聚类是通过观察学习,而不是通过例子学习。在概念聚类(conceptual clustering)中,一组对象只有当它们可以被一个概念描述时才形成一个簇。这不同于基于几何距离来度量相似度的传统聚类。概念聚类由两个部分组成:(1)发现合适的簇;(2)形成对每个簇的描述。在这里,追求较高类内相似度和较低类间相似度的指导原则仍然适用。
在数据挖掘领域,研究工作已经集中在为大数据量数据库的有效且高效的聚类分析寻找适当的方法。活跃的研究主题集中在聚类方法的可伸缩性,方法对聚类复杂形状和类型的数据的有效性,高维聚类分析技术,以及针对大的数据库中混合数值和分类数据的聚类方法。
聚类是一个富有挑战性的研究领域,它的潜在应用提出了各自特殊的要求。数据挖掘对聚类的典型要求如下:
可伸缩性:许多聚类算法在小于200个数据对象的小数据集合上工作得很好;但是,一个大规模数据库可能包含几百万个对象,在这样的大数据集合样本上进行聚类可能会导致有偏的结果。我们需要具有高度可伸缩性的聚类算法。
处理不同类型属性的能力:许多算法被设计用来聚类数值类型的数据。但是,应用可能要求聚类其他类型的数据,如二元类型(binary),分类/标称类型(categorical/nominal),序数型(ordinal)数据,或者这些数据类型的混合。
发现任意形状的聚类:许多聚类算法基于欧几里得或者曼哈顿距离度量来决定聚类。基于这样的距离度量的算法趋向于发现具有相近尺度和密度的球状簇。但是,一个簇可能是任