数学建模聚类分析.pptx

一、聚类分析（Cluster Analysis）简介 聚类分析是直接比较各事物之间的性质，将性质相近的归为一类，将性质差别较大的归入不同的类的分析技术。数理统计中的数值分类有两种问题：判别分析判别分析：已知分类情况，将未知个体归入正确类别 聚类分析聚类分析：分类情况未知，对数据结构进行分类第1页/共52页基本思想基本思想 聚类分析的基本思想:对所研究的样品或指标(变量)之间存在着程度不同的相似性(或亲疏关系)。（1）根据一批样品的多个指标,具体找出一些能够度量样品或指标之间的相似程度的统计量。（2）以这些统计量为分类的依据,把一些相似程度较大的样品(或指标)聚合为一类。把另一些彼此之间相似程度较大的样品(或指标)聚合为另一类。第2页/共52页基本思想基本思想 按相似程度的大小把关系密切的样品聚合到一个小的分类单位,关系疏远的样品聚合到一个大的分类单位,直到把所有的样品(或指标)都聚合完毕。把不同的类型一一划分出来,形成一个由小到大的分类系统。再把整个分类系统画成一张分群图(又称谱系图),用它把所有样品(或指标)间的亲疏关系表示出来。第3页/共52页 要做聚类分析，首先得按照我们聚类的目的，从对象中提取出能表现这个目的的特征指标；然后根据亲疏程度进行分类。聚类分析根据分类对象的不同可分为Q型和R型两大类Q型是对样本进行分类处理，其作用在于:1.具有共同特点的样本聚在一起2.所得结果比传统的定性分类方法更细致、全面、合理二、聚类对象第4页/共52页R型是对变量进行分类处理，其作用在于：1.可以了解变量间及变量组合间的亲疏关系2.可以根据变量的聚类结果及它们之间的关系，选择主要变量进行回归分析或Q型聚类分析第5页/共52页 2 相似性度量 进行“相关性”或“相似性”度量。在相似性度量中常常包含有许多主观上的考虑，但是最重要的是考虑指标性质或观测的尺度。当样品进行聚类时，“靠近”往往是距离。同时对指标进行聚类时，根据相关系数或某种关联性度量来聚类。第6页/共52页Q型样品间的样品间的“相似性相似性”度量度量距离距离 设每个样品有 p 个指标,观察值记为(1)每个样品 可看成是 p 维空间的一个点。于是,可用各点之间的距离来衡量各样品点之间的接近程度。样品 和 之间的距离 ,一般应满足如下条件:(),且 时当且仅当 ;();();有时所用的距离不满足(),但在广义的角度上仍称为距离。常用的距离有如下几种:第7页/共52页 3、明考斯基距离(Minkowski)1、绝对距离（Block距离）2、欧氏距离(Euclidean distance)4、切比雪夫距离(Chebychev)第8页/共52页6.马氏距离5.数据的标准化以上距离与各变量的量纲有关，为了消除量纲的影响，可对数据标准化。第9页/共52页 例1 欧洲各国的语言有许多相似之处，有的十分相似。为了研究这些语言的历史关系，也许通过比较他们数字的表达式比较恰当。表列举出英语，挪威语，丹麦语，荷兰语，德语，法语，西班牙语，意大利语，波兰语，匈牙利语和芬兰语的1,2,10的拼法，希望计算这11种语言之间的语言的距离.第10页/共52页11种欧洲语言的数词第11页/共52页选择适用的距离选择适用的距离 在聚类分析中通常要结合实际问题来选择适用的距离,有时应根据实际问题定义新的距离,显然，本例无法直接用上述公式来计算距离。但可以发现前三种文字(英、挪、丹)很相似,特别是每个单词的第一个字母。可以用10个数词中第一个字母不同的个数来定义两种语言之间的距离。例如：英语和挪威语中只有1和8的第一个字母不同,则它们之间的距离为2。第12页/共52页第13页/共52页1、夹角余弦2、相关系数R型聚类统计量 对两个指标之间的相似程度用相似系数来刻划，相似系数绝对对值越接近于1，表示指标间的关系越密切，绝对值越接近于0，表示指标间的关系越疏远.第14页/共52页 三 系统聚类分析1.系统聚类分析的基本思想是：距离相近的样品（或变量）先聚成类，距离相远的后聚成类，过程一直下去，每个样品（或变量）总能聚到合适的类中。系统聚类分析过程是：假设总共有n个样品（或变量），第一步将每个样品（或变量）独自聚成一类，共有n类；第15页/共52页第二步根据所确定的样品（或变量）“距离”公式，将距离较近的两个样品（或变量）聚合为一类，其他样品（或变量）仍各自聚为一类，共有n1类；第三步将“距离”最近的两个类进一步聚成一类，共聚成n2类；以上步骤一直进行下去，最后将所有的样品或变量）聚成一类。将整个分类系统地画成一张谱系图，所以有时系统聚类分析也叫谱系聚类分析。第16页/共52页2.类间距离 首先定义类与类之间地距离，又类间的距离定义 不同产生不同的系统聚类分析。常见的类间的距离有法。它们的归类步骤基本是一致的。8种之多，与之相应的系统聚类分析也有8种之多、分别为最短距离法、最长距离法、中间距离法、重心法、类平均法、可变类平均法、可变法和离差平方和第17页/共52页 用 i,j 表示样品 。用 表示 与 之间的距离,用 与 表示两个类,所包含的样品数分别为 与 之间的距离用 表示。下面给出四种最常用的类与类之间距离的定义。第18页/共52页1、最短距离（Nearest Neighbor)x21x12x22x11第19页/共52页即定义 与 之间的距离为 与 中最近的两个样品的距离。类与类之间的最短距离有如下的递推公式。设 由 与 合并而成,则 与其它类 的最短距离为第20页/共52页 1、根据样品的特征，规定样品之间的距离 ，共有 个。将所有列表，记为D（0）表，该表是一张对称表。所有的样本点各自为一类。2、选择D（0）表中最小的非零数，不妨假设 ，于是将 和 合并为一类，记为 。开始各样本自成一类最短距离法进行聚类分析的步骤如下：第21页/共52页 3、利用递推公式计算新类与其它类之间的距离。分别删除D（0）表的第p，q行和第p，q列，并新增一行和一列添上的结果，产生D（1）表。第22页/共52页 4、在D（1）表再选择最小的非零数，其对应的两类有构成新类，再利用递推公式计算新类与其它类之间的距离。分别删除D（1）表的相应的行和列，并新增一行和一列添上的新类和旧类之间的距离。结果，产生D（2）表。类推直至所有的样本点归为一类为止。第23页/共52页最短距离法进行聚类分析的步骤如下：（1)定义样品之间的距离（2)找出距离最小元素，设为，则将 合并成一新类记为,记为（3）按上式计算新类与其他类之间的距离。（4）重复（2），（3）的步骤，直到将所有元素并成一类为止。(如果某一步距离最小的元素不止一个，则将对应这些最小元素的类可以同时合并）第24页/共52页 例2 设有6个样品，每个只测一个指标，分别是1，2，5，7，9，10，试采用绝对值距离用最短距离法将它们进行分类。第25页/共52页 解（1）样品首先采用绝对值距离，计算样品之间的距离阵为D(0).G1G2G3G4G5G6G10G210G3430G46520G587420G6985210 D(0)第26页/共52页G2=2G1=1G3=5G4=7G5=9G6=10G7G8G9G10123D第27页/共52页2.最长距离（Furthest Neighbor）x11x21第28页/共52页即定义 与 之间的距离为 与 中最远的两个样品的距离。类与类之间的最长距离有如下的递推公式。设 由 与合并而成,则 到 的最长距离为2.最长距离（Furthest Neighbor）第29页/共52页组间平均连接（Between-group Linkage)3.类平均距离第30页/共52页组内平均连接法（Within-group Linkage)x21x12x22x113.类平均距离第31页/共52页4.重心法（Centroid clustering):均值点的距离第32页/共52页将p和q合并为k，则k类的样品个数为它的重心是某一类 r 的重心是，它与新类k的距离是经推导可以得到如下递推公式：设聚类到某一步，类p与 q分别有样品 、个，第33页/共52页 例2 设有6个样品，每个只测一个指标，分别是1，2，5，7，9，10，试采用欧氏距离的平方,试用重心法将它们进行分类。G1G2G3G4G5G6G10G210G31690G4362540G564491640G6816425910D2(0)第34页/共52页G7G3G4G8G70G312.250G430.2540G86420.256.250D2(1)其中第35页/共52页D2(2)G7G9G8G70G920.250G86412.250D2(3)G7G10G70G1039.06250第36页/共52页G1=1G2=2G3=5G4=7G5=9G6=102412.5D1G9G7G8G10G11第37页/共52页5.5.动态聚类法（快速聚类法）动态聚类法（快速聚类法）系统聚类法是一种比较成功的聚类方法。然而当样本点数量十分庞大时，则是一件非常繁重的工作，且聚类的计算速度也比较慢。比如在市场抽样调查中，有4万人就其对衣着的偏好作了回答，希望能迅速将他们分为几类。这时，采用系统聚类法就很困难，而动态聚类法就会显得方便，适用。动态聚类使用于大型数据。第38页/共52页基本思想：选取若干个样品作为凝聚点，计算每个样品和凝聚点的距离，进行初始分类，然后根据初始分类计算其重心，再进行第二次分类，一直到所有样品不再调整为止。第39页/共52页选择凝聚点分 类修改分类分类是否合理分类结束YesNo第40页/共52页 用一个简单的例子来说明动态聚类法的工作过程。例如我们要把图中的点分成两类。快速聚类的步骤：1、随机选取两个点 和 作为凝聚点。2、对于任何点 ，分别计算 3、若 ，则将 划为第一类，否则划给第二类。4、分别计算两个类的重心，则得 和 ，以其为新的凝聚点，对空间中的点进行重新分类，得到新分类。第41页/共52页 (b)任取两个凝聚点 (c)第一次分类 (d)求各类中心 （a）空间的群点第42页/共52页 (e)第二次分类第43页/共52页动态聚类法 优点：计算量小，方法简便，可以根据经验，先作主观分类。缺点：结果受选择凝聚点好坏的影响，分类结果不稳定。第44页/共52页第一，选择凝聚点；第二，初始分类；对于取定的凝聚点，视每个凝聚点为一类，将每个样品根据定义的距离向最近的凝聚点归类。第三，修改分类 得到初始分类，计算各类的重心，以这些重心作为新的凝聚点，重新进行分类，重复步骤2，3，直到分类的结果与上一步的分类结果相同，表明分类已经合理为止。动态聚类法的基本步骤：第45页/共52页例3：某商店5位售货员的销售量和教育程度如下表：售货员售货员12345销售量销售量（千件）（千件）11688教育程度教育程度12320对这5位售货员分类。第46页/共52页1.选择凝聚点 1 为最大。可选择2和5作为凝聚点。计算各样品点两两之间的距离，得到如下的距离矩阵第47页/共52页对于取定的凝聚点，视每个凝聚点为一类，将每个样品根据定义的距离，向最近的凝聚点归类。1 G1 G2 1 3 4得到初始分类为：2.初始分类第48页/共52页计算G1和G2的重心：G1的重心（1,1.5），G2的重心（7.33,1.67）G1 G212345得到分类结果：3.修改分类以这两个重心点作为凝聚点，再按最小距离原则重新聚类重心是指每类的均值向量第49页/共52页售货员售货员12345销售量销售量（千件）（千件）11688教育程度教育程度12320对这5位售货员分类。G1的重心（1+1）/第一类中样品的个数=1,1.5），G2的重心（6+8+8）/3=7.33,1.67）第50页/共52页修改前后所分的类相同，故可停止修改。和。5个售货员可分为两类第51页/共52页感谢您的观看！第52页/共52页