第-4-章--聚类分析.ppt

第-4-章--聚类分析.ppt

《第-4-章--聚类分析.ppt》由会员分享，可在线阅读，更多相关《第-4-章--聚类分析.ppt（63页珍藏版）》请在冰点文库上搜索。

第四章聚类分析,中国地质大学（北京）计算机教研室管建和,聚类分析（ClusterAnalysis）是研究“物以类聚”的一种多元统计方法。

国内有人称它为群分析、点群分析、簇群分析等。

4.1聚类分析的基本概念,研究对样品或指标进行分类的一种多元统计方法,是依据研究对象的个体的特征进行分类的方法。

聚类分析把分类对象按一定规则分成若干类，这些类非事先给定的，而是根据数据特征确定的。

在同一类中这些对象在某种意义上趋向于彼此相似，而在不同类中趋向于不相似。

职能是建立一种能按照样品或变量的相似程度进行分类的方法。

聚类分析的基本思想是认为我们所研究的样本或指标（变量）之间存在着程度不同的相似性（亲疏关系）。

于是根据一批样本的多个观测指标，具体找出一些彼此之间相似程度较大的样本（或指标）聚合为一类，把另外一些彼此之间相似程度较大的样本（或指标）又聚合为另一类，关系密切的聚合到一个小的分类单位，关系疏远的聚合到一个大的分类单位，直到把所有样本（或指标）都聚合完毕，把不同的类型一一划分出来，形成一个由小到大的分类系统。

最后把整个分类系统画成一张谱系图，用它把所有样本（或指标）间的亲疏关系表示出来。

这种方法是最常用的、最基本的一种，称为系统聚类分析。

除此以外，还有动态聚类法、图论聚类法、模糊聚类法、有序聚类法等。

聚类分析有两种：

一种是对样本的分类，称为Q型，另一种是对变量（指标）的分类，称为R型。

R型聚类分析的主要作用：

不但可以了解个别变量之间的亲疏程度，而且可以了解各个变量组合之间的亲疏程度。

根据变量的分类结果以及它们之间的关系，可以选择主要变量进行Q型聚类分析或回归分析。

（R为选择标准）Q型聚类分析的主要作用：

可以综合利用多个变量的信息对样本进行分析。

分类结果直观，聚类谱系图清楚地表现数值分类结果。

聚类分析所得到的结果比传统分类方法更细致、全面、合理。

那么Q型系统聚类法则可以表述为：

把样本看成n维空间的点，而把变量看成n维空间的坐标轴，m个样本开始时自成一类，然后规定各类之间的距离，将距离最小的一对并成一类，然后再计算距离，直到所有单位全部合并为止。

模式识别空间数据分析在GIS中，通过聚类发现特征空间来建立主题索引；在空间数据挖掘中，检测并解释空间中的簇；图象处理经济学（尤其是市场研究方面）WWW文档分类分析WEB日志数据来发现相似的访问模式,聚类的常规应用,应用聚类分析的例子,市场销售:

帮助市场人员发现客户中的不同群体，然后用这些知识来开展一个目标明确的市场计划；土地使用:

在一个陆地观察数据库中标识那些土地使用相似的地区；保险:

对购买了汽车保险的客户，标识那些有较高平均赔偿成本的客户；城市规划:

根据类型、价格、地理位置等来划分不同类型的住宅；地震研究:

根据地质断层的特点把已观察到的地震中心分成不同的类；,什么是一个好的聚类方法?

一个好的聚类方法要能产生高质量的聚类结果簇，这些簇要具备以下两个特点：

高的簇内相似性低的簇间相似性聚类结果的好坏取决于该聚类方法采用的相似性评估方法以及该方法的具体实现；聚类方法的好坏还取决与该方法是能发现某些还是所有的隐含模式；,4.2距离和相似系数,在进行聚类分析时，样本间的相似系数和距离有多种不同的定义，通常按特性来划分。

变量特征的测度尺度有三种类型：

间隔尺度（由连续的实值变量表示）有序尺度（没有明确的数量表示，只有次序关系，如产品等级）名义尺度（具有某种特性，如性别）,从一组复杂数据产生一个相当简单的类结构，必然要求进行“相关性”或“相似性”的度量。

在相似性度量的选择中，常常包含许多主观上的考虑，但最重要的考虑是指标的性质或观测的尺度（名义、次序、间隔）以及相关知识。

课堂上主要讨论的指标测量为间隔尺度的情况。

距离,每个样本有p个指标，因此每个样本可以看成p维空间中的一个点，n个样本就组成p维空间中的n个点，这时很自然想到用距离来度量n个样本间的接近程度。

用表示第i个样本与第j个样本之间的距离。

一切距离应满足以下条件：

常见的距离有：

blockdistance绝对值距离：

euclideandistance欧式距离squaredeuclideandistance平方欧式距离chebychevdistance切比雪夫距离minkowskidistance明考斯基距离（明氏距离）当q=1,2时，为绝对值、欧式距离；若趋近无穷时，则为切比雪夫距离,明氏距离在实际的运用很多，但有一些缺点。

例如观测值的单位问题；指标间的相关问题，因此改进得到以下两种距离：

Lanberra兰氏距离Mahalanobis马氏距离以上都是样本间距离的定义。

相似系数,夹角余弦相关系数变量间的距离利用相似系数来定义距离利用样本协差阵来定义距离把变量Xi的n次观测值看成n维空间的点,在n维空间中定义m个变量间的距离。

夹角余弦两变量的夹角余弦定义为：

相关系数两变量的相关系数定义为：

4.3系统聚类法基本步骤,1.选择样本间距离的定义及类间距离的定义；2.计算n个样本两两之间的距离，得到距离矩阵3.构造个类，每类只含有一个样本；4.合并符合类间距离定义要求的两类为一个新类；5.计算新类与当前各类的距离。

若类的个数为1，则转到步骤6，否则回到步骤4;6.画出聚类图；7.决定类的个数和类。

聚类分析中的数据类型,区间标度变量；二元变量；标称型，序数型变量；混合类型变量；,系统聚类分析的方法,系统聚类法的聚类原则决定于样品间的距离以及类间距离的定义，类间距离的不同定义就产生了不同的系统聚类分析方法。

以下用dij表示样品X（i）和X（j）之间的距离，当样品间的亲疏关系采用相似系数Cij时，令；以下用D（p,q）表示类Gp和Gq之间的距离。

4.3.1最短距离法（SINglemethod）,4.3.2最长距离法（COMpletemethod）,最长距离,最短距离,A,B,C,D,E,F,最小化划分方法简介,对于一个给定的n个对象或元组的数据库，采用目标函数最小化的策略，通过迭代把数据分成k个划分块，每个划分块为一个簇，这就是划分方法。

划分方法满足两个条件：

（1）每个分组至少包含一个对象；

（2）每个对象必属于且仅属于某一个分组。

常见的划分方法有k-均值方法和k-中心点方法。

其他方法大都是这两种方法的变形。

k-均值算法介绍,k-均值聚类算法的核心思想是通过迭代把数据对象划分到不同的簇中，以求目标函数最小化，从而使生成的簇尽可能地紧凑和独立。

首先，随机选取k个对象作为初始的k个簇的质心；然后，将其余对象根据其与各个簇质心的距离分配到最近的簇；再求新形成的簇的质心。

这个迭代重定位过程不断重复，直到目标函数最小化为止。

K-均值算法,输入期望得到的簇的数目k，n个对象的数据库。

输出使得平方误差准则函数最小化的k个簇。

方法选择k个对象作为初始的簇的质心；repeat计算对象与各个簇的质心的距离，将对象划分到距离其最近的簇；重新计算每个新簇的均值；Until簇的质心不再变化。

K-均值算法图例,0,1,2,3,4,5,6,7,8,9,10,0,1,2,3,4,5,6,7,8,9,10,K=2ArbitrarilychooseKobjectasinitialclustercenter,Assigneachobjectstomostsimilarcenter,Updatetheclustermeans,Updatetheclustermeans,reassign,reassign,例,为了研究浙江等5省1991年城镇居民生活消费情况的分布规律，根据调查资料做类型分类，用最短距离做类间分类。

数据如下：

数据矩阵（DataMatrix）,设有n个对象，可用p个变量（属性）描述每个对象，则np矩阵称为数据矩阵。

数据矩阵是对象-变量结构的数据表达方式。

对象间距离的计算,设两个p维向量xi=（xi1,xi2,xip）T和xj=（xj1,xj2,xjp）T分别表示两个对象，有多种形式的距离度量可以采用。

距离公式如前面所示:

闵可夫斯基（Minkowski）距离：

曼哈坦（Manhattan）距离：

欧几里得（Euclidean）距离：

切比雪夫（Chebyshev）距离：

马哈拉诺比斯（Mahalanobis）距离：

相异度矩阵（DissimilarityMatrix）,按n个对象两两间的相异度构建n阶矩阵（因为相异度矩阵是对称的，只需写出上三角或下三角即可）：

其中d（i,j）表示对象i与j的相异度，它是一个非负的数值。

当对象i和j越相似或“接近”时，d（i,j）值越接近0；而对象i和j越不相同或相距“越远”时，d（i,j）值越大。

显然，d（i,j）=d（j,i），d（i,i）=0。

相异度矩阵是对象-对象结构的一种数据表达方式。

将每一个省区视为一个样本，先计算5个省区之间的欧式距离，用D0表示距离矩阵（对称阵，故给出下三角阵）因此将3.4合并为一类，为类6，替代了3、4两类类6与剩余的1、2、5之间的距离分别为：

d（3,4）1=min（d31,d41）=min（13.80,13.12）=13.12d（3,4）2=min（d32,d42）=min（24.63,24.06）=24.06d（3,4）5=min（d35,d45）=min（3.51,2.21）=2.21,得到新矩阵合并类6和类5，得到新类7类7与剩余的1、2之间的距离分别为：

d（5,6）1=min（d51,d61）=min（12.80,13.12）=12.80d（5,6）2=min（d52,d62）=min（23.54,24.06）=23.54,得到新矩阵合并类1和类2，得到新类8此时，我们有两个不同的类：

类7和类8。

它们的最近距离d（7,8）=min（d71,d72）=min（12.80,23.54）=12.80,得到矩阵最后合并为一个大类。

这就是按最短距离定义类间距离的系统聚类方法。

最长距离法类似！

4.3.3重心法（CENtroidmethod）,4.3.4类平均法（AVEragemethod）,中间距离,4.3.5离差平方和法（WARD）,基本思想来源于方差分析。

它认为：

如果分类正确，同类间的类差平方和应较小，类与类之间的离差平方和应较大.具体做法是，先将n个样本分成一类,然后每次缩小一类,每缩小一类离差平方和就要增大.,4.3.6离差平方和法（WARD）,4.3.7系统聚类方法的统一,4.3.8系统聚类法参数表,4.3.9类的个数的确定,由适当的阈值确定；根据数据点的散布直观地确定类的个数；根据统计量确定分类个数；,4.3.10类的个数的确定,根据谱系图确定分类个数的准则：

各类重心间的距离必须很大；类中保包含的元素不要太多；类的个数必须符合实际应用；如果采用几种不同的聚类方法处理，则在各种聚类图中应该发现相同的类。

聚类类别：

统计图：

树型谱系图冰柱谱系图聚类方法1.Between-groupslinkage类间平均法两类距离为两类元素两两之间平均平方距离2.Within-groupslinkage类内平均法两类距离为合并后类中可能元素两两之间平均平方距离3.Nearestneighbor最短距离法4.Furthestneighbor最长距离法5.Centroidclustering重心法（欧式距离）6.Medianclustering中间距离法（欧式距离）7.WardMethod离差平方法（欧式距离）,4.4系统聚类的参数选择,SPSS界面指南,4.5系统聚类法之例地区按经济效益分类某年全国28个省区经济效益指标表，演示,类间平均法,类内平均法,最短距离法,最长距离法,重心法,重心法,中间距离法,离差平方法,4.6快速聚类法,快速聚类法的聚类数由用户指定，分类是唯一的。

1.分类数2.聚类方法:

method:

iterateandclassifyclassifyonly3.聚类中心:

centers4.迭代次数:

iterate5.保存分类结果:

save,4.4层次聚类简介,层次聚类按数据分层建立簇，形成一棵以簇为节点的树，称为聚类图。

按自底向上层次分解，则称为凝聚的层次聚类。

按自顶向下层次分解，就称为分裂的层次聚类。

凝聚的和分裂的层次聚类,凝聚的层次聚类采用自底向上的策略，开始时把每个对象作为一个单独的簇，然后逐次对各个簇进行适当合并，直到满足某个终止条件。

分裂的层次聚类采用自顶向下的策略，与凝聚的层次聚类相反，开始时将所有对象置于同一个簇中，然后逐次将簇分裂为更小的簇，直到满足某个终止条件。

凝聚的和分裂的层次聚类,层次聚类方法的优缺点,层次聚类方法的优点在于可以在不同粒度水平上对数据进行探测，而且容易实现相似度量或距离度量。

单纯的层次聚类算法终止条件含糊，而且执行合并或分裂簇的操作后不可修正，这很可能导致聚类结果质量很低。

由于需要检查和估算大量的对象或簇才能决定簇的合并或分裂，所以这种方法的可扩展性较差。

通常考虑把层次聚类方法与其他方法（如迭代重定位方法）相结合来解决实际聚类问题。

层次聚类和其他聚类方法的有效集成可以形成多阶段聚类，能够改善聚类质量。

这类方法包括BIRCH、CURE、ROCK、Chameleon等。

本章完。

谢谢！

2010年4月8日,