数学建模聚类分析省名师优质课获奖课件市赛课一等奖课件.ppt

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