数学建模-聚类分析

1、 聚类分析聚类分析分类l物以类聚、人以群分；物以类聚、人以群分；l但根据什么分类呢？但根据什么分类呢？l如要想把中国的县分类，就有多种方法如要想把中国的县分类，就有多种方法l可以按照自然条件来分，比如考虑降水、土可以按照自然条件来分，比如考虑降水、土地、日照、湿度等，地、日照、湿度等，l也可考虑收入、教育水准、医疗条件、基础也可考虑收入、教育水准、医疗条件、基础设施等指标；设施等指标；l既可以用某一项来分类，也可以同时考虑多既可以用某一项来分类，也可以同时考虑多项指标来分类。项指标来分类。 l研究对样品或指标进行分类的一种多元统计方法,是依据研究对象的个体的特征进行分类的方法。l聚类分析把分类

2、对象按一定规则分成若干类，这些类非事先给定的，而是根据数据特征确定的。在同一类中这些对象在某种意义上趋向于彼此相似，而在不同类中趋向于不相似。 聚类分析的聚类分析的基本思想基本思想是认为我们是认为我们所研究的样本或指标（变量）之间所研究的样本或指标（变量）之间存在着程度不同的相似性（亲疏关存在着程度不同的相似性（亲疏关系）。系）。l根据事物本身的特性研究个体分类的根据事物本身的特性研究个体分类的方法，原则是同一类中的个体有较大方法，原则是同一类中的个体有较大的相似性，不同类中的个体差异很大。的相似性，不同类中的个体差异很大。l不一定事先假定有多少类，完全可以不一定事先假定有多少类，完全可以按照

3、数据本身的规律来分类。按照数据本身的规律来分类。l按照远近程度来聚类需要明确两个概按照远近程度来聚类需要明确两个概念：一个是念：一个是点和点之间点和点之间的距离，一个的距离，一个是是类和类之间类和类之间的距离。的距离。 二、距离和相似系数二、距离和相似系数 在进行聚类分析时，样本间的相似系数和距离有多种不同的定义，通常按特性来划分。变量特征的测度尺度有三种类型： 间隔尺度（由连续的实值变量表示） 有序尺度（没有明确的数量表示，只有次序关系，如产品等级） 名义尺度（具有某种特性，如性别）l从一组复杂数据产生一个相当简单的类结构，必然要求进行“相关性”或“相似性”的度量。在相似性度量的选择中，常常

4、包含许多主观上的考虑，但最重要的考虑是指标的性质或观测的尺度（名义、次序、间隔）以及相关知识。l课堂上主要讨论的指标测量为间隔尺度的情况。距离距离l每个样本有p个指标，因此每个样本可以看成p维空间中的一个点，n个样本就组成p维空间中的n个点，这时很自然想到用距离来度量n个样本间的接近程度。l用 表示第i个样本与第j个样本之间的距离。一切距离应满足以下条件：kjidddjiddjidjidkjikijjiijijij, 0, 0对于一切，对于一切的指标相同与样本等价于样本对于一切ijd常见的距离有：常见的距离有：lblock distance 绝对值距离绝对值距离：leuclidean dist

5、ance 欧式距离欧式距离lsquared euclidean distance 平方欧式距离平方欧式距离lchebychev distance 切比雪夫距离切比雪夫距离lminkowski distance 明考斯基距离明考斯基距离 （明氏距离）（明氏距离）当当q=1,2时，为绝对值、欧式距离；时，为绝对值、欧式距离；若趋近无穷时，则为切比雪夫距离若趋近无穷时，则为切比雪夫距离xxMaxjtittdptxxdjtit1ptjtitxxd1221ptjtitxxdptqjtitxxdq11lLanberra 兰氏距离lMahalanobis 马氏距离l以上都是样本间距离的定义。ptjtitjt

6、itijxxxxpLd1)(|1)()()()()()(1)()(jijiijXXSXXMd相似系数相似系数l夹角余弦l相关系数l变量间的距离l利用相似系数来定义距离l利用样本协差阵来定义距离l把变量Xi的n次观测值看成n维空间的点,在n维空间中定义m个变量间的距离。l 夹角余弦 两变量的夹角余弦定义为： l 相关系数 两变量的相关系数定义为： 把样本看成把样本看成n维空间的点，而把变量看成维空间的点，而把变量看成n维空间的坐标轴，维空间的坐标轴，m个样本开始时自成一类，个样本开始时自成一类，然后规定各类之间的距离，将距离最小的一对然后规定各类之间的距离，将距离最小的一对并成一类，然后再计算距

7、离，直到所有单位全并成一类，然后再计算距离，直到所有单位全部合并为止。部合并为止。系统聚类法l根据一批样本的多个观测指标，具体找出一些彼此之根据一批样本的多个观测指标，具体找出一些彼此之间相似程度较大的样本（或指标）聚合为一类，把另间相似程度较大的样本（或指标）聚合为一类，把另外一些彼此之间相似程度较大的样本（或指标）又聚外一些彼此之间相似程度较大的样本（或指标）又聚合为另一类，关系密切的聚合到一个小的分类单位，合为另一类，关系密切的聚合到一个小的分类单位，关系疏远的聚合到一个大的分类单位，直到把所有样关系疏远的聚合到一个大的分类单位，直到把所有样本（或指标）都聚合完毕，把不同的类型一一划分出

8、本（或指标）都聚合完毕，把不同的类型一一划分出来，形成一个由小到大的分类系统。最后把整个分类来，形成一个由小到大的分类系统。最后把整个分类系统画成一张谱系图，用它把所有样本（或指标）间系统画成一张谱系图，用它把所有样本（或指标）间的亲疏关系表示出来。这种方法是最常用的、最基本的亲疏关系表示出来。这种方法是最常用的、最基本的一种，称为系统聚类分析。的一种，称为系统聚类分析。系统聚类法基本步骤1. 选择样本间距离的定义及类间距离的定义；2. 计算n个样本两两之间的距离，得到距离矩阵 3. 构造个类，每类只含有一个样本；4. 合并符合类间距离定义要求的两类为一个新类；5. 计算新类与当前各类的距离。

9、若类的个数为1，则转到步骤6，否则回到步骤4;6.画出聚类图； 7.决定类的个数和类。 ijdD 系统聚类分析的方法系统聚类分析的方法l系统聚类法的聚类原则决定于样品间的距离以及类间距离的定义，类间距离的不同定义就产生了不同的系统聚类分析方法。l以下用dij表示样品X(i)和X(j)之间的距离，当样品间的亲疏关系采用相似系数Cij时，令 ；l以下用D(p,q)表示类Gp和Gq之间的距离。221ijijCd1.最短距离法(SINgle method)2.最长距离法最长距离法(COMplete method)最长距离最短距离ABCDEF3.重心法重心法(CENtroid method)4.类平均法

10、类平均法(AVErage method)中间距离5.离差平方和法离差平方和法(WARD)l基本思想来源于方差分析。它认为：如果分类正确，同类间基本思想来源于方差分析。它认为：如果分类正确，同类间的类差平方和应较小，类与类之间的离差平方和应较大的类差平方和应较小，类与类之间的离差平方和应较大.l具体做法是，先将具体做法是，先将n个样本分成一类个样本分成一类,然后每次缩小一类然后每次缩小一类,每缩每缩小一类离差平方和就要增大小一类离差平方和就要增大. 离差平方和法离差平方和法(WARD)系统聚类方法的统一系统聚类方法的统一 系统聚类法参数表系统聚类法参数表 类的个数的确定类的个数的确定l由适当的阈

11、值确定；l根据数据点的散布直观地确定类的个数；l根据统计量确定分类个数；类的个数的确定类的个数的确定l根据谱系图确定分类个数的准则：l各类重心间的距离必须很大；l类中保包含的元素不要太多；l类的个数必须符合实际应用；l如果采用几种不同的聚类方法处理，则在各种聚类图中应该发现相同的类。四、系统聚类的参数选择四、系统聚类的参数选择聚类类别：聚类类别：统计统计图：树型谱系图图：树型谱系图 冰柱谱系图冰柱谱系图聚类方法聚类方法1.Between-groups linkage 类间平均法类间平均法 两类距离为两类元素两两之间平均平方距离两类距离为两类元素两两之间平均平方距离2.Within-groups

12、 linkage 类内平均法类内平均法两类距离为合并后类中可能元素两两之间平均平方距离两类距离为合并后类中可能元素两两之间平均平方距离3.Nearest neighbor 最短距离法最短距离法 4. Furthest neighbor 最长距离法最长距离法5.Centroid clustering 重心法重心法 (欧式距离欧式距离)6.Median clustering 中间距离法中间距离法 (欧式距离欧式距离)7.Ward Method 离差平方法离差平方法 (欧式距离欧式距离)SPSS界面指南界面指南饮料数据（drink.sav ）l16种饮料如何分类？种饮料如何分类？ k-均值聚类 lk

13、-均值聚类（均值聚类（k-means cluster，也叫，也叫快速聚类，快速聚类，quick cluster）却要求你先）却要求你先说好要分多少类。说好要分多少类。l假定你说分假定你说分3类，这个方法还进一步要类，这个方法还进一步要求 你 事 先 确 定求 你 事 先 确 定 3 个 点 为个 点 为 “ 聚 类 种聚 类 种子子”(SPSS软件软件自动自动为你选种子为你选种子)；也；也就是说，把这就是说，把这3个点作为三类中每一类个点作为三类中每一类的基石。的基石。l然后，根据和这三个点的距离远近，把然后，根据和这三个点的距离远近，把所有点分成三类。再把这三类的中心所有点分成三类。再把这三

14、类的中心(均值均值)作为新的基石或种子作为新的基石或种子(原来原来 “种子种子”就没用了就没用了)，再重新按照距离分类。，再重新按照距离分类。l如此叠代下去，直到达到停止叠代的要如此叠代下去，直到达到停止叠代的要求（比如，各类最后变化不大了，或者求（比如，各类最后变化不大了，或者叠代次数太多了）。叠代次数太多了）。l下面用饮料例的数据来做下面用饮料例的数据来做k-均值聚类。均值聚类。 假定要把这假定要把这1616种饮料分成种饮料分成3 3类。利用类。利用SPSSSPSS，只叠，只叠代了三次就达到目标了（计算机选的种子还可代了三次就达到目标了（计算机选的种子还可以）。这样就可以得到最后的三类的中

15、心以及每以）。这样就可以得到最后的三类的中心以及每类有多少点类有多少点 Final Cluster CentersFinal Cluster Centers203.1033.71107.341.654.163.4913.0510.068.763.152.692.94CALORIECAFFEINESODIUMPRICE123ClusterNumber of Cases in each ClusterNumber of Cases in each Cluster2.0007.0007.00016.000.000123ClusterValidMissing根据需要，可以输出哪些点分在一起。根据需要，

16、可以输出哪些点分在一起。结果是：第一类为饮料结果是：第一类为饮料1、10；第二类为；第二类为饮料饮料2、4、8、11、12、13、14；第三类；第三类为剩下的饮料为剩下的饮料3、5、6、7、9、15、16。SPSS实现(聚类分析)lK-均值聚类均值聚类l以数据以数据drink.sav为例，在为例，在SPSS中选择中选择AnalyzeClassifyK-Menas Cluster，l然后把然后把calorie（热量）、（热量）、caffeine（咖啡（咖啡因）、因）、sodium（钠）、（钠）、price（价格）选入（价格）选入Variables, l在在Number of Clusters处选

17、择处选择3（想要分的类（想要分的类数），数），l如果想要知道哪种饮料分到哪类，则选如果想要知道哪种饮料分到哪类，则选Save，再选再选Cluster Membership等。等。l注意注意k-均值聚类只能做均值聚类只能做Q型聚类，如要做型聚类，如要做R型型聚类，需要把数据阵进行转置。聚类，需要把数据阵进行转置。分层聚类 l分层聚类或系统聚类（分层聚类或系统聚类（hierarchical cluster）。开始时，有多少点就是多少）。开始时，有多少点就是多少类。类。l它第一步先把最近的两类（点）合并成它第一步先把最近的两类（点）合并成一类，然后再把剩下的最近的两类合并一类，然后再把剩下的最近的两

18、类合并成一类；成一类；l这样下去，每次都少一类，直到最后只这样下去，每次都少一类，直到最后只有一大类为止。越是后来合并的类，距有一大类为止。越是后来合并的类，距离就越远。离就越远。对于对于饮料聚类。饮料聚类。 SPSSSPSS输出为输出为Agglomeration ScheduleAgglomeration Schedule515139700032436.4850286969.1300010110102.6300015811150.330008516198.375101128319.77836121214322.540001236458.7950413571006.8

19、6370132121435.0768914351755.654101114236287.1751213151219406.6845140Stage123456789101112131415Cluster 1Cluster 2Cluster CombinedCoefficients Cluster 1Cluster 2Stage Cluster FirstAppearsNext StageVertical IcicleVertical IcicleXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX XXXXXXXXXXXXXXXX

20、 XXXXXXXXXXXXX XXXXXXXXXX XXXXX XXXXXXXXXXXXX XXXXXXXXXX XXXXX XXX XXXXXXXXX XXXX XXXXX XXXXX XXX XXXXXXXXX XXXX XXXXX XXX X XXX XXXXXXXXX XXXX XXXXX XXX X X X XXXXXXXXX XXXX XXXXX XXX X X X XXX XXXXX XXXX X XXX XXX X X X XXX XXXXX XXXX X XXX XXX X X X X X XXXXX XXXX X XXX XXX X X X X X XXXXX X XX X XXX X X X X X X X XXXXX X XX X XXX X X X X X X X XXX X X XX X XXX X X X X X X X X X X X XNumber of clusters1234567891011121314157 16 15 5 9 6 3 14 12 11 8 13 4 2 10 1Case“冰柱图冰柱图”(icicle)聚类要注意的问题 l聚类结果主要受所选择的变量影响。聚类结果主要受所选择的变量影响。如果去掉一