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

第10章聚类分析Ⅱ:分层聚类与密度聚类10.1引言10.2分层聚类10.3分层聚类的实现10.4密度聚类10.5聚类结果评估10.6聚类算法对比本章小结

10.1引言

聚类分析是将物理或抽象对象的集合分组为由类似的对象组成的多个类的分析过程,它是一种重要的人类行为,已在数学、计算机科学、统计、生物和经济等不同领域进行了广泛的应用。

聚类分析的优点:

(1)简单、直观;

(2)主要应用于探索性的研究,其结果可以提供多个可能的解,选择最终的解需要研究者的主观判断和后续分析;

(3)不管实际数据中是否真正存在不同的类别,利用聚类分析都能得到分成若干类别的解;

(4)聚类分析的解完全依赖于研究者所选择的聚类变量,增加或删除一些变量对最终的解都可能产生实质性的影响。

聚类分析的缺点:

(1)不能自动发现分成多少个类———属于无监督分析方法;

(2)期望能很清楚地找到大致相等的类或细分是不现实的;

(3)对样本聚类时,变量之间的关系需要研究者决定;

(4)不会自动给出一个最佳的聚类结果。

问题1:K-均值算法有哪些典型的缺陷?是否存在有效的解决方法?

提示:噪声敏感、非凸结构,如第9章表93所示。

本章阐述的分层聚类与基于密度的算法可以克服K-均值算法的缺陷,其中分层聚类主要解决初始值选择与敏感性高的问题,而密度聚类主要解决非凸结构的问题,如表

10-1所示。

10.2分层聚类

分层聚类(或层次聚类)输出层次结构,这种结构比K-均值聚类返回的非结构化聚类集更具信息性。此外,分层聚类不需要预先指定聚类的数量,同时分层算法是确定性的。这些优势都是K-均值算法所不具备的。与K-均值算法和EM算法(Expectation_x0002_Maximizationalgorithm,最大期望算法)的线性复杂度相比,最常见的层次聚类算法具有至少O(N2)的复杂度,也就是说,分层聚类的这些优点以降低效率为代价。

10.2.1算法流程

分层聚类法首先将每个数据对象看成一个类,计算类之间的距离(如何计算类之间的距离将在10.2.2节中进行详细描述),每次将距离最近的数据对象合并成一个类。然后,计算类与类之间的距离,将距离最近的类归并为一个大类。不停地合并,直到合成一个类,如图10-1所示,每次归并两个点,直到所有的数据点都隶属于一个组。图10-1分层聚类通过不断归并(划分)数据进行聚类

分层聚类法基本上有两种:聚集法和分割法。聚集法首先将所有的研究对象都各自算作一类,将最“靠近”的类首先进行聚类,再将这个类和其他类中最“靠近”类的结合,这样继续合并直至所有对象都综合成一类或满足某个给定阈值条件为止。分割法正好相反,它首先将所有对象看成一大类,然后分割成两类,使一类中的对象尽可能地“远离”另一类的对象,再将每一类继续这样分割下去,直至每个对象都自成一类或满足一个阈值条件为止。

基于聚合的分层聚类算法更加通用,也是本书介绍的重点,其关键技术是如何通过层次树结构将数据归并/划分过程记录下来,形成系统树(Dendrogram),如图10-2所示。可见,树状结构更加直观与清晰。图10-2系统树的两种形式

10.2.2集合距离计算

问题2:K-均值算法用数据对象之间的距离刻画相似性,分层聚类法用什么方法呢?

分层聚类的重点在于如何计算数据对象集合之间的相似性。给定两个集合C1与C2,如何度量这两个集合之间的相似性?其难点在于如何定义集合之间的相似性,集合由数据对象构建,其相似性可基于数据相似性,如图10-3所示。图10-3集合之间相似性的计算

定义集合之间的相似性的原则是:集合相似性基于集合中数据对象之间的相似性。因此,典型的集合相似性包括最近距离、最远距离、平均距离。

1.最近距离

最近距离也称为单链距离(SingleLinkage),其计算方法是将两个组合数据点中距离最近的两个数据点间的距离作为这两个组合数据点的距离,这种方法容易受到极端值的影响,两个非常相似的组合数据点可能由于其中的某个极端的数据点距离较近而组合在一起,如图10-4所示。图10-4基于最近距离的集合相似性

2.最远距离

最远距离也称为全链距离(CompleteLinkage),其计算方法与最短距离的不同,它将两个组合数据点中距离最远的两个数据点间的距离作为这两个组合数据点的距离。最远距离的问题与最近距离的相反,两个不相似的组合数据点可能由于其中的极端值距离较远而无法组合在一起,如图10-5所示。图10-5基于最远距离的集合相似性

3.平均距离

平均距离(AverageLinkage)的计算方法是计算两个组合数据点中的每个数据点与其他所有数据点的距离,将所有距离的均值作为两个组合数据点间的距离,如图10-6所示。这种方法的计算量比较大,但其结果比前两种方法的更合理。图10-6基于平均距离的集合相似性

问题3:三种集合相似性计算的优缺点是什么?

提示:从定义、准确性、稳定性等方面进行分析。

(1)单链、全链方式的优势在于计算过程简单,缺点是不够稳定,仅利用了局部信息;

(2)平均距离方法的优势在于相对稳定,利用了集合中的全局信息,缺点是计算相对复杂。

现举例说明分层聚类法的操作过程。给定5个样本的集合,样本之间的欧氏距离由如下矩阵D表示,采用最小距离作为类间距离,并设定最终类别个数为1,即将所有样本聚为一类作为终止条件。

问题4:相较于K-均值算法,分层聚类法的优势是什么?

提示:从噪声、准确性、稳定性等方面进行分析,如表10-2所示。

通过对比可知:

①分层聚类法可以有效解决噪声、聚类数等问题。

②分层聚类法的时间复杂度高。具体来说,K-均值算法的时间复杂度接近线性,而分层聚类法的时间复杂度是二次方。

③K-均值算法与分层聚类法都不能对非凸聚类进行准确的分析。

10.3分层聚类的实现

这里我们选用SPSS数据管理软件实现分层聚类,选用的数据集为一组有关12盎司啤酒成分和价格的数据,变量包括name(啤酒名称)、calories(热量卡路里)、sodium(钠含量)、alcohol(酒精含量)以及cost(价格)。

其具体步骤如下:

(1)将数据导入软件中,如图10-7所示。

(2)依次单击Analyze→Classify→HierarchicalCluster...选项,打开分层聚类对话框,如图10-8所示。

(3)在“HierarchicalClusterAnalysis”对话框中,将用于聚类的变量calories、sodium、alcohol、cost放入“Variables”文本框中;将“name”放入LabelCasesby标签中,使得每一

条数据用name的值命名;在“Cluster”一栏中选择“Cases”对样本进行聚类,即对啤酒进行聚类;在“Display”一栏中选择需要展示的输出结果,如图10-9所示。图10-7将数据导入软件中图10-8打开分层聚类对话框

图10-9设置各项参数

(4)单击“Statistics...”按钮,进入Statistics对话框,选择要求输出的统计量,选中“Agglomerationschedule”复选框,显示聚类过程中每一步合并的类或观测量,如图10-10所示。然后单击“Continue”按钮,返回“HierarchicalClusterAnalysis”对话框。图10-10-Statics对话框

(5)单击“Plots...”按钮,进入Plots对话框,选中“Dendrogram”复选框,选择输出树状图,如图10-11所示。然后单击“Continue”按钮,返回“HierarchicalClusterAnalysis”

对话框。图10-11Plots对话框

(6)单击“Method...”,按钮进入Method对话框确定聚类方法,单击“ClusterMethod”下拉列表框中的下箭头按钮,展开方法选择菜单,选择“Between-groupslinkage”组间连接

选项,即类平均法;点击“Measure”文本框内“Interval”下拉列表框中的下箭头按钮,展开距离测度选择菜单,选择决定是否合并两类的距离测度,这里选择“SquaredEuclideandistance”选项,即欧氏距离平方,如图10-12所示。然后单击“Continue”按钮返回“HierarchicalClusterAnalysis”对话框。图10-12Method对话框

(7)单击“OK”按钮,得到层次聚类聚集状态图和表示层次聚类过程的树状图,如图10-13、图10-14所示。

图10-13层次聚类聚集状态图图10-14层次聚类过程的树状图

10.4密度聚类

分层聚类可克服K-均值算法的部分缺陷,但是K-均值算法与分层聚类算法都不能有效解决的问题是:在非凸簇结构条件下,两类算法的效果不佳。密度聚类又称“基于密度的聚类”,此类算法假设聚类结构能通过样本分布的紧密程度确定。

密度聚类算法的优点:

(1)聚类速度快,且能够有效处理噪声点和发现任意形状的空间聚类;

(2)与K-均值算法相比,不需要输入需要划分的聚类个数;

(3)聚类簇的形状没有偏倚;

(4)可以在需要时输入过滤噪声的参数。

密度聚类算法的缺点:

(1)当数据量增大时,要求较大的内存支持,I/O消耗也很大;

(2)当空间聚类的密度不均匀、聚类间距差相差很大时,聚类质量较差,因为这种情况下参数“MinPts”和“Eps”选取困难。

(3)算法聚类效果依赖于距离公式的选取,实际应用中常用欧氏距离;对于高维数据,存在“维数灾难”。

10.4.1类密度

DBSCAN算法基于一组“邻域”参数(ε,MinPts)来刻画样本分布的紧密程度,对数据点进行分类,包括核心点、边界点、噪声点。给定数据集D={x1,x2,…,xn},定义如下:

(1)Eps邻域:给定对象半径Eps内的邻域,称为该对象的Eps邻域,即对xj∈D,其Eps邻域包含样本集D中与xj的距离不大于ε的样本,即Nε(xj)={xjεD|dist(xi,xj)≤ε};

(2)核心点(CorePoint):如果某个数据对象的Eps邻域至少包含最小数目MinPts的对象,则称该对象为核心对象,即若Nε(xj)≥MinPts,则xj是一个核心对象;

(3)边界点(EdgePoint):不是核心点,它落在某个核心点的Eps邻域内,其Eps邻域内包含对象的数量小于MinPts,即若xi位于xj

的Eps邻域中,xj

是核心点,|Nε(xi)|<MinPts,则xi为边界点;

(4)噪声点(OutlierPoint):既不是核心点,也不是边界点的任何点。

数据点分类如图10-15所示,数据点的分类取决于参数MinPts和Eps。图10-15DBSCAN算法数据点分类情况示意图图10-16DBSCAN算法数据对象之间的关系示意图

10.4.2算法过程

1.时间复杂度

DBSCAN的基本时间复杂度是O(N*找出Eps邻域中的点所需要的时间),N是点的个数。在低维空间数据中最坏情况下,时间复杂度是O(N2)。在低维空间数据中,有一些数据结构如KD树(K-DimensionalTree),使得可以有效检索特定点给定距离内的所有点,时间复杂度可以降低到O(NlgN)。

2.空间复杂度

在低维和高维数据中,其空间复杂度都是O(N),对于每个点,DBSCAN只需要维持少量数据,即簇标号和每个点的标识(核心点或边界点,或噪声点)。

3.参数设置

DBSCAN共包括3个输入数据:

①数据集D;

②邻域半径Eps;

③给定点在邻域内成为核心对象的最小邻域点数MinPts。其中,Eps和MinPts要根据具体应用人为设定。

例如,选择与图95中相同的数据集,采用DBSCAN算法对数据点进行聚类。取k=4,可得到如图10-17所示的结果。

图10-17为样本数据的K-距离图。由图可以看出,第一个谷值点位置对应的K-距离值为0.8,则设定参数Eps为0.8,相应地,设置参数MinPts为4。由图10-18可以看出,使用参数(Eps=0.8,MinPts=4),DBSCAN算法可以得到很好的聚类结果,而采用参数(Eps=0.5,MinPts=4)和(Eps=3,MinPts=4)不能得到有效的聚类划分。可见,过小的Eps参数使得应属于同一聚类的数据被划分为多个聚类,过大的Eps参数使得所有数据被聚为一类。图10-17样本数据的K-距离图图10-18样本数据

10.5聚类结果评估

聚类效果的好坏会直接影响聚类的效果。大体上,有两类指标用以衡量聚类效果的好坏,一类是外部聚类效果,另一类是内部聚类效果。聚类分析的目标是:簇内数据对象高度相似、簇间数据对象高度分离,即得到内紧外松的结构,如图10-19所示。图10-19聚类分析的目标是得到内紧外松的结构

聚类性能度量大致分为两类,一类是将簇结果与某个参考模型进行比较,称为“外部指标”;另一类是直接考察聚类结果,而不利用任何参考模型,称为“内部指标”。

此外,根据簇的内部紧凑性、外部分离性,常见的聚类性能度量的内部指标还有WSS(WithinSumofSquares)和BSS(BetweenSumofSquares),分别定义为

式中:mi

表示第i个聚类Ci的中心点;m表示所有数据的中心点。WSS越小,说明簇内内容相似性越高;BSS越大,说明簇间内容相似性越低。因此,最小化WSS、最大化BSS,也是常用的聚类性能度量的内部指标。

10.6聚类算法对比

10.6.1K-均值算法K-均值算法的原理可简单理解为:假设有一堆散点需要聚类,想要的聚类效果就是“类内的点都足够近,类间的点都足够远”。首先要确定这堆散点最后聚成几类,然后挑选几个点作为初始中心点,再依据启发式算法(HeuristicAlgorithms)给数据点做迭代重置(IterativeRelocation),直到最后达到“类内的点都足够近,类间的点都足够远”的目标。

优点:

(1)简单,易于理解和实现;

(2)时间复杂度低。

缺点:

(1)需要手工输入类数目,对初始值的设置很敏感,所以有了K-means++、intelligentK-means、geneticK-means算法;

(2)对噪声和离群值非常敏感,所以有了K-medoids和K-medians算法;

(3)只适用于数值类型数据,不适用于分类类型数据,所以有了K-modes算法;

(4)不能解决非凸(Non-convex)数据,所以有了核K-means算法;

(5)主要发现圆形或者球形簇,不能识别非球形的簇。

10.6.2分层聚类

分层聚类算法先计算样本之间的距离,每次将距离最近的点合并到同一个类;然后计算类与类之间的距离,将距离最近的类合并为一个大类;不停地合并,直到合成了一个类。

其优、缺点如下:

优点:

(1)距离和规则的相似度容易定义,限制少;

(2)不需要预先制订聚类数;

(3)可以发现类的层次关系;

(4)可以聚类成其他形状。

缺点:

(1)计算复杂度太高;

(2)奇异值对聚类也能产生很大的影响;

(3)算法很可能聚类成链状。

10.6.3DBSCAN算法

DBSCAN算法基于密度,对于集中区域效果较好。为了发现任意形状的簇,该算法将簇看作数据空间中被低密度区域分割开的稠密对象区域,是一种基于高密度连通区域密度的聚类方法