聚类分析 (2)精选文档.ppt

《聚类分析 (2)精选文档.ppt》由会员分享，可在线阅读，更多相关《聚类分析 (2)精选文档.ppt（45页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、聚类分析本讲稿第一页，共四十五页聚类根据实际的需要，又可能有两个方向：聚类根据实际的需要，又可能有两个方向：1.样本聚类（样本聚类（Q聚类）聚类）(caseclusteranalysis)2.变量聚类变量聚类（R聚类）聚类）(variabeclusteranalysis)本讲稿第三页，共四十五页根据根据聚类方法聚类方法，聚类分析聚类分析又分为又分为：1.系统聚类系统聚类(joiningclusterprocedures)2.动态聚类动态聚类(iterativepartitioningprocedures)本讲稿第四页，共四十五页5.2 系统聚类法系统聚类法5.2.1基本思想基本思想系统聚类法有

2、两种：系统聚类法有两种：（1）聚集法聚集法（2）分解法）分解法本讲稿第十七页，共四十五页5.2.2群间距离的定义群间距离的定义1.最短距离法最短距离法(nearestneighbor或或singlelinkage)）类与类之间距离采用公式类与类之间距离采用公式它等于它等于Gp和和Gq中靠近的两个样品距离中靠近的两个样品距离,简单易用，易有延伸的链状结构，效果不好简单易用，易有延伸的链状结构，效果不好本讲稿第十八页，共四十五页2.最长距离法最长距离法(completelinkageorfurthestneighbor)它等于它等于Gp和和Gq中最远的两个样之间的距离。中最远的两个样之间的距离。克

3、服了最短距离法的连接聚合的局限，受异常值影响大，克服了最短距离法的连接聚合的局限，受异常值影响大，效果不好效果不好本讲稿第十九页，共四十五页3.未加权的类平均法未加权的类平均法(unweightedpair-groupaverage)它等于它等于Gp和和Gq中任意的两个样本之间距离的平均。中任意的两个样本之间距离的平均。充分利用已知信息，克服了最短（长）距离法受异常值影响大充分利用已知信息，克服了最短（长）距离法受异常值影响大的局限，效果较好，应用较广。的局限，效果较好，应用较广。本讲稿第二十页，共四十五页4.加权的类平均法加权的类平均法(weightedpair-groupaverage)5

4、.未加权的类间重心法未加权的类间重心法（unweighted pair-group centroid）它等于两个重心它等于两个重心 与与 间的距离。间的距离。本讲稿第二十一页，共四十五页5.2.3 聚类分析步骤聚类分析步骤系系统统聚聚类类法法（hierarchicalclusteringmehtod）是是聚聚类类分分析析诸方法中用得最多者。诸方法中用得最多者。步骤如下：步骤如下：（1）计算）计算n个样本点两两间的距离个样本点两两间的距离，记作记作对称距离矩阵。对称距离矩阵。（2）构造）构造n个类，每个类只包含一个样本点。个类，每个类只包含一个样本点。（3）合并距离最近的两类为一新类。）合并距离

5、最近的两类为一新类。（4）计算新类与当前各类的距离得新的距离距阵。）计算新类与当前各类的距离得新的距离距阵。若类的个数等于若类的个数等于1，转到步骤（，转到步骤（5），），否则回到步骤（否则回到步骤（3）。）。（5）画聚类图。）画聚类图。（6）决定类的个数和各类的样本点）决定类的个数和各类的样本点。本讲稿第二十五页，共四十五页现现在在，我我们们通通过过一一个个简简单单的的数数值值例例子子，来来说说明明各各种种系系统聚类方法。统聚类方法。例例7.1设设有有五五个个样样本本，每每个个只只有有一一个个变变量量，分分别别是是1，2，4.5，6，8，试将其分类。，试将其分类。我我们们首首先先计计算算五五

6、个个样样本本之之间间的的距距离离（用用绝绝对对值值距距离离或或欧欧氏氏距距离离，这这时时两两者者等等价价），用用D表表示示相相应应的的矩矩阵阵（由由于于矩矩阵对称，所以只写出上三角部分）：阵对称，所以只写出上三角部分）：本讲稿第二十六页，共四十五页开始例中有五类：开始例中有五类：这五类之间的距离等于五个样品之间的距离。这五类之间的距离等于五个样品之间的距离。我们发现我们发现D中最小的元素是中最小的元素是D(1，2)=1，故将，故将G1和和G2并成一并成一新类新类然后计算然后计算G6与与G3，G4，G5的距离。的距离。本讲稿第二十七页，共四十五页G6G3G4G5G6=G1G202.54601.5

7、3.5G402G50G3然后，在上表中发现最小的元素为然后，在上表中发现最小的元素为D（3,4）=1.5，故将，故将G3和和G4合并为合并为G7本讲稿第二十八页，共四十五页再计算得再计算得G7=G3G4G6G7G5G602.5602G50本讲稿第二十九页，共四十五页将将G7与与G5合并为合并为G8，计算得计算得最后，将最后，将G6与与G8合并为合并为G9本讲稿第三十页，共四十五页将上述并类过程画成图将上述并类过程画成图7.1，0121.52.5G1距离图（7.1）聚类图G2G3G4G5G6G7G8G9本讲稿第三十一页，共四十五页最最后后决决定定类类的的个个数数与与类类。从从图图上上看看，分分两

8、两类类较较为为合合适适，得得到到两类为两类为或用样本来表示这两类是或用样本来表示这两类是0121.52.5G1距离图（7.1）聚类图G2G3G4G5G6G7G8G9本讲稿第三十二页，共四十五页或由给定的距离，决定如何分类。或由给定的距离，决定如何分类。例如给定分类距离为例如给定分类距离为2.2,这等价于在图这等价于在图7.1上，距离为上，距离为2.2处切一刀处切一刀,可分为两类可分为两类;若分类距离为若分类距离为1.8,则应分为三类则应分为三类0121.52.5G1距离图（7.1）聚类图G2G3G4G5G6G7G8G9本讲稿第三十三页，共四十五页5.3 动态聚类方法动态聚类方法(K-均值聚类法

9、）均值聚类法）5.3.1基本思想基本思想当当样样本本数数很很多多的的情情况况下下，系系统统聚聚类类方方法法的的计计算算工工作作量量很很大大，克克服服这这个个缺缺点点的的方方法法是是，先先大大致致将将所所有有样样本本分分成成k类类（初初始始分分类类），然然后后按按照照某某种种最最优优原原则则进进行行修修改改，直直到到分分类类比比较较合合理理为为止止，这这就就是是逐逐步步聚聚类类方方法法。根根据据修修改改原原则则的的不不同同，可可以以将将逐逐步步聚聚类类方方法法命命名名为为各各种种不不同同的的方方法法。这这里里介介绍绍最最常常用用的的K-均均值值聚类法聚类法（k-meansclustering)本

10、讲稿第三十四页，共四十五页K均值聚类首先要明确：均值聚类首先要明确：1.确定要分的类数：确定要分的类数：设有设有n个个p维样本点需要分成维样本点需要分成k类类2.初始点的选择原则初始点的选择原则3.修改分类的原则修改分类的原则本讲稿第三十五页，共四十五页5.3.2 K均值聚类步骤均值聚类步骤（i）初步分类。首先人为地选择）初步分类。首先人为地选择k个凝聚点个凝聚点;例如可随机地选择例如可随机地选择m个样本点作为凝聚点。但为了加快个样本点作为凝聚点。但为了加快计算速度，使分类比较合理计算速度，使分类比较合理,凝聚点可按下述原则选择：凝聚点可按下述原则选择：（a）先选择所有样本对中相距最远的两个样

11、本点）先选择所有样本对中相距最远的两个样本点xi1，xi2为前二个凝聚点。即为前二个凝聚点。即本讲稿第三十六页，共四十五页（b）选选择择第第三三个个凝凝聚聚点点xi3时时，使使得得xi3与与xi1,xi2的的较较小小距距离离是所有点与是所有点与xi1,xi2的较小距离中最大的。的较小距离中最大的。（c）然后按同样原则选择）然后按同样原则选择xi4有人将这种选取凝聚点的方法叫做有人将这种选取凝聚点的方法叫做最小最大原则最小最大原则本讲稿第三十七页，共四十五页计计算算样样本本点点与与每每个个凝凝聚聚点点之之间间的的距距离离，将将每每个个样样本本归归入入离离它它最最近近的的凝凝聚聚点点所所属属那那一

12、一类类，这这样样就就将将全全部部样样本本分分成了成了k类，记为类，记为G01,G02,G0k）修改分类。计算各类的重心）修改分类。计算各类的重心，然然后后把把各各类类重重心心作作为为新新凝凝聚聚点点，再再计计算算每每个个样样本本点点与与新新凝凝聚聚点点的的距距离离，将将每每个个样样本本重重新新归归入入离离它它最最近近的的凝凝聚聚点点所所决决定定的的类，得到第一次修改后的分类类，得到第一次修改后的分类）重复手续）重复手续），直到样本分类不再变动为止），直到样本分类不再变动为止本讲稿第三十八页，共四十五页例例在在12个个不不同同产产区区测测定定相相思思树树种种子子的的平平均均发发芽芽率率和和发发芽

13、芽势（为了便于计算略去其他指标），其结果列于下表：势（为了便于计算略去其他指标），其结果列于下表：表（表（7.1）十二个产区相思树种子发芽情况十二个产区相思树种子发芽情况产区号产区号123456789101112发芽率发芽率x10.7070.6000.6930.7170.6880.5330.8770.5130.8150.6330.7400.777发芽势发芽势x20.3850.4330.5050.3430.6050.3800.7130.3530.6750.4650.5800.723本讲稿第三十九页，共四十五页产区号产区号123456789101112发芽率发芽率x10.7070.6000.693

14、0.7170.6880.5330.8770.5130.8150.6330.7400.777发芽势发芽势x20.3850.4330.5050.3430.6050.3800.7130.3530.6750.4650.5800.723)首首先先随随机机地地取取二二点点为为初初始始凝凝聚聚点点，这这里里取取G1类类的的凝凝聚聚点点为为五五号号地地区区，坐坐标标为为（0.668，0.605）；G2类类的的凝凝聚聚点点为为12号号地地区区，坐坐标标为为（0.777，0.723），算算出出各各产产区区和和二二凝凝聚点的距离，其结果列于下表：聚点的距离，其结果列于下表：本讲稿第四十页，共四十五页表（表（7.2）

15、产区第一次分类产区第一次分类类类地区号地区号聚类聚类123456789101112G1(0.668,0.605)0.0490.0370.0100.06900.0750.0470.0940.0210.0230.0030.022G2(0.777,0.723)0.1190.1150.0550.1480.0260.1770.0100.2070.0040.0870.0220所属类所属类G1G1G1G1G1G1G2G1G2G1G1G2表表中中数数字字是是欧欧氏氏距距离离的的平平方方，并并按按距距离离较较小小者者归归类类。例例如如1号号产产区区与与G1类类凝凝聚聚点点的的距距离离小小，因因而而1号号产产区区

16、归归入入G1类，等等。类，等等。本讲稿第四十一页，共四十五页表（表（7.2）产区第一次分类产区第一次分类类类地区号地区号聚类聚类123456789101112G1(0.668,0.605)0.0490.0370.0100.06900.0750.0470.0940.0210.0230.0030.022G2(0.777,0.723)0.1190.1150.0550.1480.0260.1770.0100.2070.0040.0870.0220所属类所属类G1G1G1G1G1G1G2G1G2G1G1G2）根根据据第第一一次次分分类类的的结结果果，算算出出G1类类样样本本（即即产产区区）的的重重心心坐

17、坐标标（即即G1类类样样本本的的平平均均发发芽芽率率和和平平均均发发芽芽势势）和和G2类类样样本本的的重重心心，然然后后计计算算各各样样本本与与重重心心的的距距离离，并并按按较小距离归类，其结果列于下表：较小距离归类，其结果列于下表：本讲稿第四十二页，共四十五页表（表（7.3）产区第二次分类产区第二次分类类类产区号产区号重心重心123456789101112G1(0.647,0.450)0.0080.0020.0050.0160.0260.0180.1220.0270.07900.0260.091G2(0.832,0.704)0.1150.1230.0560.1420.0280.1890.00

18、30.2190.0010.0930.0220.002所属类所属类G1G1G1G1G1G1G2G1G2G1G2G2由由于于归归类类结结果果与与上上一一次次归归类类结结果果不不同同，因因此此还还需需再再作作一一次次归归类。类。）根根据据第第二二次次分分类类结结果果，算算出出G1类类样样本本重重心心坐坐标标与与G2类类样样本本重重心心坐坐标标，再再算算出出各各样样本本与与二二类类重重心心距距离离，按按较较小距离归类，将结果列于下表。小距离归类，将结果列于下表。本讲稿第四十三页，共四十五页表（表（7.4）产区第三次分类产区第三次分类产地产地重心重心123456789101112(0.636,0.433

19、)0.0070.0010.0080.0150.0320.0130.1360.0220.0910.0010.0320.104(0.802,0.672)0.0910.0980.0400.1150.0170.1580.0070.18500.0710.0120.003G1G1G1G1G2G1G2G1G2G1G2G2由由于于第第三三次次分分类类结结果果与与第第二二次次分分类类结结果果不不相相同同，再再按按同同样样手手续续作作第第四四次分类次分类表（表（7.5）产区第四次分类产区第四次分类产地产地重心重心123456789101112（0.628，0.409）0.0070.0010.0130.0120.0

20、110.1380.0120.1640.0020.0590.0070.121（0.779，0.659）0.0800.0830.0310.1040.0110.1380.0120.1640.0020.0590.0070.004所属类所属类G1G1G1G1G2G1G2G1G2G1G2G2本讲稿第四十四页，共四十五页由由于于第第四四次次分分类类结结果果与与第第三三次次分分类类结结果果相相同同，这这就就是是最最后后分类。分类。现在得到分类情况如下：现在得到分类情况如下：G1=1,2,3,4,6,8,10,平均发芽率为平均发芽率为0.628,平均发芽势为平均发芽势为0.409(即即G1类重心坐标类重心坐标),是种子质量较差的地区。是种子质量较差的地区。G2=5,7,9,11,12，平均发芽率为平均发芽率为0.779，平均发芽势为，平均发芽势为0.659是种子质量较好地地区。是种子质量较好地地区。本讲稿第四十五页，共四十五页