《数据挖掘基础及其应用》课件第9章

第9章聚类分析Ⅰ:概念与K-均值算法9.1引言9.2聚类流程与方法9.3K-均值算法9.4K-均值算法的拓展9.5图像分割的应用本章小结

9.1引言

聚类分析是将物理或抽象对象的集合进行分组的过程,其中每一组中的对象具有高度的相似性。聚类分析也是一种重要的人类行为,可辅助人类的生产、生活。聚类源于很多领域,包括数学、计算机科学、统计学、生物学和经济学等。在不同的应用领域,很多聚类技术都得到了发展,这些技术方法被用于描述数据、衡量不同数据源间的相似性,以及把数据源分类到不同的簇中,如图9-1所示。图9-1聚类分析

问题:聚类与分类的区别是什么?

提示:从目标、数据、模式等方面考虑。

从统计学的观点来看,聚类分析是通过数据建模从而简化数据的一种方法。传统的统计聚类分析方法包括系统聚类法、分解法、加入法、动态聚类法、有序样品聚类、有重叠聚类和模糊聚类等。采用K-均值、K-中心点等算法的聚类分析工具已被加入到许多著名的统计分析软件包中,如SPSS、SAS等。

聚类分析是一种探索性的分析,在分类的过程中,人们不必事先给出一个分类的标准,聚类分析能够从样本数据出发,自动进行分类。聚类分析由所使用方法的不同,常常会得到不同的结论。不同研究者对于同一组数据进行聚类分析,所得到的聚类结果未必一致。

从实际应用的角度来看,聚类分析是数据挖掘的主要任务之一。

分类与聚类的区分归纳为如下几点,如表9-1所示。

基于上述分析,给定聚类分析定义如下:

聚类依据研究对象(样品或指标)的特征对其进行分类,从而减少研究对象的数目。由于很多事物缺乏可靠的历史资料,无法确定共有多少类别,而聚类的目的是将性质相近的事物/对象归入一个组/簇。

定义9.1(聚类分析ClusteringAnalysis)将一组研究对象分为相对同质的群组(Clusters)的统计分析技术。

聚类分析已经广泛运用于各行各业,包括:

(1)商业:聚类分析被用来发现不同的客户群,并且通过购买模式刻画不同客户群的特征。

(2)生物医学:聚类分析被用来对动植物和基因进行分类,获取对种群固有结构的认识,利用聚类分析挖掘致癌基因等。

(3)地理:聚类能够帮助判别在地球中被观察对象的相似性。

(4)保险行业:聚类分析通过平均消费的高低来鉴定汽车保险单持有者的分组,同时根据住宅类型、价值、地理位置来鉴定一个城市的房产分组。

(5)因特网:聚类分析被用来在网上进行文档归类来修复信息。

(6)电子商务:聚类分析也是电子商务网站建设数据挖掘中很重要的一个方面,通过分组聚类出具有相似浏览行为的客户,并分析客户的共同特征,可以更好地帮助电子商务的用户了解自己的客户,向客户提供更合适的服务。

9.2聚类流程与方法

9.2.1聚类流程典型的聚类分析流程如图9-2所示,主要包括四个过程:数据预处理、数据相似度度量、聚类策略的选择、聚类结果评估。图9-2聚类分析的基本流程

1.数据预处理

数据预处理包括数据类型选择、特征标度刻画等,主要依靠特征选择和特征抽取。其中,特征选择是选择重要的特征,特征抽取是把输入的特征转化为一个新的显著特征,它们经常被用来获取一个合适的特征集,从而避免“维数灾难”。数据预处理还包括将孤立点移出数据。由于孤立点是不依附于一般数据行为或模型的数据,它经常会导致有偏差的聚类结果,因此为了得到正确的聚类,必须将它们剔除。

2.数据相似度度量

既然相似性是定义一个簇的基础,那么同一个特征空间中不同数据之间相似度的衡量对于聚类极为重要。由于特征类型和特征标度的多样性,距离度量的选择必须谨慎,它经常依赖于应用。

若函数dist(·,·)是一个“距离度量”,则需要满足一些基本性质:

(1)非负性:dist(xi,xj)≥0;

(2)统一性:dist(xi,xj)=0,当且仅当xi=xj;

(3)对称性:dist(xi,xj)=dist(xj,xi);

(4)直递性(三角不等式):dist(xi,xj)≤dist(xi

,xk)+dist(xk,xj

)。

假定每个样本有p个变量,则每个样本都可以看成p维空间中的一个点,n个样本就是p维空间中的n个点,将第i个样本与第j个样本之间的距离记为dij。典型的距离函数包括:

(3)马氏(Mahalanobis)距离函数,其表达式为

3.聚类策略的选择

将数据对象分到不同的类/簇是聚类分析的最终目标,而划分方法和层次方法是聚类分析的主要方法。其中,划分方法一般从初始划分和最优化一个聚类标准开始,而层次方法则利用相似性构建树结构进行聚类。硬聚类(CrispClustering或HardClustering)中每一个数据对象属于且仅属于某一个类,软聚类(FuzzyClustering或SoftClustering)中每个数据对象可以隶属一个或多个类;硬聚类与软聚类分别对应集合的划分与覆盖问题。

4.聚类结果评估

聚类结果的质量评估是聚类分析中极为重要的内容之一。聚类是一个无管理的程序,也没有客观的标准来评价聚类结果。一般来说,利用类/簇的几何性质来评估聚类结果,包括类间的分离和类内部的耦合。也可通过预先定义的函数对聚类结果进行评估,如方差等。如果在有先验的专家知识的情况下,可利用专家知识引导评估等。

9.2.2聚类方法

聚类分析是数据挖掘中一个很活跃的研究领域,目前已经提出了许多聚类算法。传统的聚类算法可以分为五类:划分方法、层次方法、基于密度的方法、基于网格的方法和基

于模型的方法。

1.划分方法(PartitioningMethod,PAM)

划分方法的步骤为:首先创建k个划分,k为要创建的划分个数;然后利用循环定位技术通过将对象从一个划分移到另一个划分来帮助改善划分质量。

2.层次方法

层次方法是(HierarchicalMethod)创建一个层次以分解给定的数据集。该方法可以分为自上而下(分解)和自下而上(合并)两种操作方式。为弥补分解与合并的不足,层次方法经常要与其他聚类方法相结合,如循环定位法。典型的层次分类方法包括:(1)BIRCH(BalancedIterativeReducingandClusteringusingHierarchies)方法。

(2)CURE(ClusteringUsingREpresentatives)方法。

(3)ROCK方法。该方法利用聚类间的连接进行聚类合并。

(4)CHEMALOEN(变色龙,是一个利用动态模型的层次聚类算法)方法。

3.基于密度的方法

该方法根据密度完成对象的聚类,并根据对象周围的密度不断增长聚类。典型的基于密度的方法包括:

(1)DBSCAN,该方法通过不断生长足够高的密度区域来进行聚类,它能从含有噪声的空间数据库中发现任意形状的聚类,并将一个聚类定义为一组“密度连接”的点集。

(2)OPTICS算法不显式地生成数据聚类,它只是对数据对象集合中的对象进行排序,得到一个有序的对象列表,其中包含了足够的信息用来提取聚类。

4.基于网格的方法

基于网格的方法(Grid-BasedMethods)首先将对象空间划分为有限个单元以构成网格结构,然后利用网格结构完成聚类。STING是一个利用网格单元保存的统计信息进行基于网格聚类的方法。此外,CLIQUE(ClusteringinQuest)和

Wave-Cluster是将基于网格与基于密度相结合的方法。

5.基于模型的方法

基于模型的方法为每个簇假定了一个模型,寻找数据对给定模型的最佳拟合。一个基于模型的算法可能通过构建反映数据点空间分布的密度函数来定位聚类。基于模型的算法

也基于标准的统计数据自动决定聚类的数目,考虑“噪声”数据或孤立点,从而产生稳健的聚类方法。典型的基于模型的方法(Model-BasedMethods)包括:

(1)统计方法COBWEB,它是一个常用的且简单的增量式概念聚类方法。

(2)CLASSIT方法,它是COBWEB的另一个版本,可以对连续取值属性进行增量式聚类。

9.3K-均值算法

K-均值(K-means)算法是一种使用最广泛的聚类算法,它将各个聚类子集内的所有数据样本的均值作为该聚类的代表点。该算法的主要思想是通过迭代过程把数据集划分为不同的类别,使得评价聚类性能的准则函数达到最优,从而使生成的每个聚类类内紧凑。

9.3.1算法的三大要素

聚类的目标是将数据对象分配到不同的聚类中,以使得类间相对松散、类内相对紧凑。如图9-3所示,每个数据对象用一个点表示,同类数据对象用相同形状标记。图9-3K-均值算法挖掘不同的簇/分组

1.相似性函数

K-均值聚类算法不适于处理离散型属性,适合处理连续型属性。因此在计算数据样本之间的距离时,可以根据实际需要选择欧氏距离、曼哈顿距离或者明考斯距离中的一种作为算法的相似性度量,其中最常用的是欧氏距离。

由9.2节数据相似性内容可知,典型的相似性函数有:

2.选择评价聚类性能准则函数

K-均值聚类算法使用误差平方和准则函数来评价聚类性能。给定数据集X,其中只包含描述属性,不包含类别属性。假设X包含k个聚类子集X1,X2,…,Xk,各个聚类子集的均值代表点(也称聚类中心)分别为m1,m2,…,mk,则误差平方和准则函数公式为

3.数据对象如何分组

计算每个簇的平均值,并用该平均值代表相应的簇。根据每个对象与各个簇中心的距离,分配给最近的簇。

综上可知,K-均值算法三大要素包括目标函数、相似性与分组原则。

9.3.2算法的流程

算法过程示意图如图9-4所示,首先随机选定k个数据点作为初始的聚类中心,计算每个数据点到聚类中心的距离;然后把数据对象赋给最近的中心所对应的类/簇,重新计算簇中心,重新分组,一直迭代,直到算法终止。图9-4K-均值算法过程示意图图9-4K-均值算法过程示意图

例如,数据对象集合S如表9-2所示,作为一个聚类分析的二维样本,要求的簇的数量k=2。

9.3.3算法的性能分析

K-均值算法的优缺点总结如表9-3所示。图9-5K-均值算法不能对非凸数据进行聚类图9-6聚类密度对K-均值算法性能的影响较大

9.4K-均值算法的拓展

由于K-均值算法存在相应的缺陷,因此如何有效解决这些问题就成为了关键。针对K-均值算法对于不同的初始值,可能会导致不同的结果,解决方法有:(1)多设置一些不同的初值,对比最后的运算结果,一直到结果趋于稳定结束。这种方法比较耗时,也浪费资源。(2)很多时候,事先并不知道数据集的聚类数,这也是K-均值算法的一个不足。

ISODATA算法的流程如下:

K-均值算法其他的改进方式:

(1)K-modes算法:实现对离散数据的快速聚类,保留了K-均值算法的效率,同时将K-均值算法的应用范围扩大到离散数据。它是按照K-均值算法的核心内容进行修改,针对分类属性的度量和更新质心的问题而改进的。K-modes算法具体如下:①度量记录之间的相关性D的计算公式是,比较两记录之间的关系,属性相同为0,不同为1,并将所有关系相加。因此D越大,数据的不相关程度越强(与欧氏距离代表的意义是一样的)。②更新modes,使用一个簇的每个属性出现频率最高的那个属性值作为代表簇的属性值。

(2)K-prototype算法:可以对离散与数值属性两种混合的数据进行聚类。在K-prototype中定义了一个对数值与离散属性都计算的相异性度量标准。K-prototype算法

结合了K-均值算法与K-modes算法,针对混合属性解决了两个核心问题:①度量具有混合属性的方法是,数值属性采用K-均值算法得到P1,分类属性采用K-modes方法得到P2,则D=P1+aP2,其中a是权重。如果认为分类属性重要,则增加a,否则减少a。当a=0时,只有数值属性。②更新一个簇中心的方法是结合K-均值算法与K-modes算法。

(3)K-中心点算法:K-均值算法对于孤立点是敏感的,为了解决这个问题,不采用簇中的平均值作为参照点,可以选用簇中位置最中心的对象(中心点)作为参照点。这种划分方法仍然是基于最小化所有对象与其参照点之间的相异度之和来执行的。

9.5图像分割的应用

图9-7所示为一条狗、一辆自行车以及街道、树木和汽车。使用K-均值算法对图像进行分割,将图像分割为合适的背景区域(自行车、街道、树木及汽车)和前景区域(狗)。图9-8所示为一匹斑马、草地。使用K-均值算法对图像进行分割,将图像分割为合适的背景区域(草地)和前景区域(斑马)。图9-7K-均值算法应用于图像分割前后图9-8K-均值算法应用于图像分割前后(聚类中心个数为3,最大迭代次数为10)

本章小结

聚类分析是无监督学习中一项重要的研究课题,本章主要讲述了聚类分析的背景、定义及其基本分类方法,重点阐述了聚类分析的过程、K-均值算法的原理与过程、K-均值算法的优缺点及其在图像中的应用。本章回答了如下几个问题:

(1)为什么要进行聚类分析?

数据无标签。

(2)聚类分析的基本过程是什么?

四大过程:数据预处理、相似度度量、聚类策略的选择、聚类结果评估。

(3)K-