数学建模聚类分析学习教案.pptx

《数学建模聚类分析学习教案.pptx》由会员分享，可在线阅读，更多相关《数学建模聚类分析学习教案.pptx（52页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、会计学1数学数学(shxu)建模聚类分析建模聚类分析第一页，共52页。基本基本(jbn)思思想想 聚类分析的基本思想:对所研究的样品或指标(变量)之间存在着程度不同的相似性(或亲疏关系)。（1）根据一批样品的多个指标,具体找出一些能够度量样品或指标之间的相似程度的统计(tngj)量。（2）以这些统计(tngj)量为分类的依据,把一些相似程度较大的样品(或指标)聚合为一类。把另一些彼此之间相似程度较大的样品(或指标)聚合为另一类。第2页/共52页第二页，共52页。基本基本(jbn)思思想想 按相似程度的大小把关系密切的样品聚合到一个小的分类单位,关系疏远(shyun)的样品聚合到一个大的分类单位

2、,直到把所有的样品(或指标)都聚合完毕。把不同的类型一一划分出来,形成一个由小到大的分类系统。再把整个分类系统画成一张分群图(又称谱系图),用它把所有样品(或指标)间的亲疏关系表示出来。第3页/共52页第三页，共52页。要做聚类分析，首先得按照我们聚类的目的，从对象中提取出能表现这个目的的特征指标；然后根据亲疏(qn sh)程度进行分类。聚类分析根据分类(fn li)对象的不同可分为Q型和R型两大类Q型是对样本进行分类处理，其作用在于:具有共同特点的样本聚在一起所得结果比传统的定性分类方法(fngf)更细致、全面、合理二、聚类对象第4页/共52页第四页，共52页。R型是对变量进行分类处理，其作

3、用在于：可以了解变量间及变量组合间的亲疏关系可以根据变量的聚类结果及它们之间的关系，选择主要变量进行回归(hugu)分析或Q型聚类分析第5页/共52页第五页，共52页。2 相似性相似性度量度量(dling)进行“相关性”或“相似性”度量。在相似性度量中常常包含有许多主观(zhgun)上的考虑，但是最重要的是考虑指标性质或观测的尺度。当样品进行聚类时，“靠近”往往(wngwng)是距离。同时对指标进行聚类时，根据相关系数或某种关联性度量来聚类。第6页/共52页第六页，共52页。Q型样品型样品(yngpn)间的间的“相似性相似性”度量度量距离距离 设每个样品(yngpn)有 p 个指标,观察值记为

4、(1)每个样品 可看成(kn chn)是 p 维空间的一个点。于是,可用各点之间的距离来衡量各样品点之间的接近程度。样品 和 之间的距离 ,一般应满足如下条件:(),且 时当且仅当 ;();();有时所用的距离不满足(),但在广义的角度上仍称为距离。常用的距离有如下几种:第7页/共52页第七页，共52页。3、明考斯基距离(jl)(Minkowski)1、绝对(judu)距离（Block距离）2、欧氏距离(jl)(Euclidean distance)4、切比雪夫距离(Chebychev)第8页/共52页第八页，共52页。6.马氏距离(jl)5.数据(shj)的标准化以上距离与各变量的量纲有关，

5、为了消除(xioch)量纲的影响，可对数据标准化。第9页/共52页第九页，共52页。例1 欧洲各国的语言有许多相似之处，有的十分相似。为了研究这些语言的历史关系，也许通过比较(bjio)他们数字的表达式比较(bjio)恰当。表列举出英语，挪威语，丹麦语，荷兰语，德语，法语，西班牙语，意大利语，波兰语，匈牙利语和芬兰语的1,2,10的拼法，希望计算这11种语言之间的语言的距离.第10页/共52页第十页，共52页。11种欧洲(u zhu)语言的数词第11页/共52页第十一页，共52页。选择选择选择选择(xu(xu nz)nz)适用适用适用适用的距离的距离的距离的距离 在聚类分析中通常要结合实际问题

6、来选择适用的距离,有时应根据实际问题定义新的距离,显然，本例无法直接用上述公式来计算距离。但可以(ky)发现前三种文字(英、挪、丹)很相似,特别是每个单词的第一个字母。可以(ky)用10个数词中第一个字母不同的个数来定义两种语言之间的距离。例如：英语和挪威语中只有1和8的第一个字母不同,则它们之间的距离为2。第12页/共52页第十二页，共52页。第13页/共52页第十三页，共52页。1、夹角(ji jio)余弦2、相关系数R型聚类统计(tngj)量 对两个指标(zhbio)之间的相似程度用相似系数来刻划，相似系数绝对对值越接近于1，表示指标(zhbio)间的关系越密切，绝对值越接近于0，表示指

7、标(zhbio)间的关系越疏远.第14页/共52页第十四页，共52页。三 系统(xtng)聚类分析1.系统聚类分析的基本(jbn)思想是：距离(jl)相近的样品（或变量）先聚成类，距离(jl)相远的后聚成类，过程一直下去，每个样品（或变量）总能聚到合适的类中。系统聚类分析过程是：假设总共有n个样品（或变量），第一步将每个样品（或变量）独自聚成一类，共有n类；第15页/共52页第十五页，共52页。第二步根据所确定的样品(yngpn)（或变量）“距离”公式，将距离较近的两个样品（或变量）聚合(jh)为一类，其他样品（或变量）仍各自聚为一类(y li)，共有n1类；第三步将“距离”最近的两个类进一步

8、聚成一类，共聚成n2类；以上步骤一直进行下去，最后将所有的样品或变量）聚成一类。将整个分类系统地画成一张谱系图，所以有时系统聚类分析也叫谱系聚类分析。第16页/共52页第十六页，共52页。2.类间距离(jl)首先定义(dngy)类与类之间地距离，又类间的距离定义(dngy)不同(b tn)产生不同(b tn)的系统聚类分析。常见的类间的距离有法。它们的归类步骤基本是一致的。8种之多，与之相应的系统聚类分析也有8种之多、分别为最短距离法、最长距离法、中间距离法、重心法、类平均法、可变类平均法、可变法和离差平方和第17页/共52页第十七页，共52页。用 i,j 表示样品 。用 表示 与 之间的距离

9、,用 与 表示两个类,所包含(bohn)的样品数分别为 与 之间的距离用 表示。下面给出四种最常用的类与类之间距离的定义。第18页/共52页第十八页，共52页。1、最短距离（Nearest Neighbor)x21x12x22x11第19页/共52页第十九页，共52页。即定义 与 之间的距离为 与 中最近(zujn)的两个样品的距离。类与类之间的最短距离有如下的递推公式。设 由 与 合并而成,则 与其它类 的最短距离为第20页/共52页第二十页，共52页。1 1、根根据据样样品品的的特特征征，规规定定(gudng)(gudng)样样品品之之间间的的距距离离 ，共共有有 个个。将将所所有有列列表

10、表，记记为为D D（0 0）表表，该该表表是一张对称表。所有的样本点各自为一类。是一张对称表。所有的样本点各自为一类。2、选择D（0）表中最小的非零数，不妨假设 ，于是(ysh)将 和 合并为一类，记为 。开始各样本(yngbn)自成一类最短距离法进行聚类分析的步骤如下：第21页/共52页第二十一页，共52页。3、利用递推公式计算新类与其它类之间的距离。分别删除(shnch)D（0）表的第p，q行和第p，q列，并新增一行和一列添上的结果，产生D（1）表。第22页/共52页第二十二页，共52页。4、在D（1）表再选择最小的非零数，其对应的两类有构成新类，再利用递推公式(gngsh)计算新类与其它

11、类之间的距离。分别删除D（1）表的相应的行和列，并新增一行和一列添上的新类和旧类之间的距离。结果，产生D（2）表。类推直至所有的样本点归为一类为止。第23页/共52页第二十三页，共52页。最短距离法进行(jnxng)聚类分析的步骤如下：（1)定义(dngy)样品之间的距离（2)找出距离最小元素，设为，则将 合并成一新类记为,记为（3）按上式计算(j sun)新类与其他类之间的距离。（4）重复（2），（3）的步骤，直到将所有元素并成一类为止。(如果某一步距离最小的元素不止一个，则将对应这些最小元素的类可以同时合并）第24页/共52页第二十四页，共52页。例2 设有6个样品，每个只测一个指标，分别

12、是1，2，5，7，9，10，试采用绝对值距离(jl)用最短距离(jl)法将它们进行分类。第25页/共52页第二十五页，共52页。解（1）样品首先(shuxin)采用绝对值距离，计算样品之间的距离阵为D(0).G1G2G3G4G5G6G10G210G3430G46520G587420G6985210 D(0)第26页/共52页第二十六页，共52页。G2=2G1=1G3=5G4=7G5=9G6=10G7G8G9G10123D第27页/共52页第二十七页，共52页。2.最长距离（Furthest Neighbor）x11x21第28页/共52页第二十八页，共52页。即定义 与 之间的距离为 与 中最

13、远的两个样品(yngpn)的距离。类与类之间的最长距离有如下的递推公式。设 由 与合并而成,则 到 的最长距离为2.最长距离（Furthest Neighbor）第29页/共52页第二十九页，共52页。组间平均(pngjn)连接（Between-group Linkage)3.类平均(pngjn)距离第30页/共52页第三十页，共52页。组内平均(pngjn)连接法（Within-group Linkage)x21x12x22x113.类平均(pngjn)距离第31页/共52页第三十一页，共52页。4.重心(zhngxn)法（Centroid clustering):均值点的距离第32页/共5

14、2页第三十二页，共52页。将p和q合并(hbng)为k，则k类的样品个数为它的重心(zhngxn)是某一类 r 的重心是，它与新类k的距离(jl)是经推导可以得到如下递推公式：设聚类到某一步，类p与 q分别有样品 、个，第33页/共52页第三十三页，共52页。例2 设有6个样品，每个只测一个指标，分别是1，2，5，7，9，10，试采用欧氏距离的平方,试用重心法将它们进行(jnxng)分类。G1G2G3G4G5G6G10G210G31690G4362540G564491640G6816425910D2(0)第34页/共52页第三十四页，共52页。G7G3G4G8G70G312.250G430.2

15、540G86420.256.250D2(1)其中(qzhng)第35页/共52页第三十五页，共52页。D2(2)G7G9G8G70G920.250G86412.250D2(3)G7G10G70G1039.06250第36页/共52页第三十六页，共52页。G1=1G2=2G3=5G4=7G5=9G6=102412.5D1G9G7G8G10G11第37页/共52页第三十七页，共52页。5.5.5.5.动态动态动态动态(dngti)(dngti)(dngti)(dngti)聚类法（快速聚类法）聚类法（快速聚类法）聚类法（快速聚类法）聚类法（快速聚类法）系系统统聚聚类类法法是是一一种种比比较较成成功功

16、的的聚聚类类方方法法。然然而而当当样样本本点点数数量量十十分分(shfn)(shfn)庞庞大大时时，则则是是一一件件非非常常繁繁重重的的工作，且聚类的计算速度也比较慢。工作，且聚类的计算速度也比较慢。比比如如在在市市场场抽抽样样调调查查中中，有有4 4万万人人就就其其对对衣衣着着的的偏偏好作了回答，希望能迅速将他们分为几类。好作了回答，希望能迅速将他们分为几类。这这时时，采采用用系系统统聚聚类类法法就就很很困困难难，而而动动态态聚聚类类法法就就会会显得方便，适用。显得方便，适用。动态聚类使用于大型数据。动态聚类使用于大型数据。第38页/共52页第三十八页，共52页。n n基本思想：选取若干个样

17、品基本思想：选取若干个样品(yngp(yngp n)n)作为作为凝聚点，计算每个样品凝聚点，计算每个样品(yngp(yngp n)n)和凝聚点和凝聚点的距离，进行初始分类，然后根据初始分的距离，进行初始分类，然后根据初始分类计算其重心，再进行第二次分类，一直类计算其重心，再进行第二次分类，一直到所有样品到所有样品(yngp(yngp n)n)不再调整为止。不再调整为止。第39页/共52页第三十九页，共52页。选择(xunz)凝聚点分 类修改(xigi)分类分类是否(sh fu)合理分类结束YesNo第40页/共52页第四十页，共52页。用一个简单的例子来说明动态聚类法的工作过程。例如我们要把图

18、中的点分成两类。快速(kui s)聚类的步骤：1、随机选取两个点 和 作为凝聚点。2、对于任何点 ，分别计算 3、若 ，则将 划为第一类，否则划给第二类。4、分别计算两个类的重心，则得 和 ，以其为新的凝聚点，对空间中的点进行重新分类，得到新分类。第41页/共52页第四十一页，共52页。(b)任取两个凝聚点 (c)第一次分类 (d)求各类中心 （a）空间的群点第42页/共52页第四十二页，共52页。(e)第二次分类(fn li)第43页/共52页第四十三页，共52页。动态(dngti)聚类法 n n优点：计算量小，方法简便，可以根据优点：计算量小，方法简便，可以根据(gnj)(gnj)经验，先

19、作主观分类。经验，先作主观分类。n n缺点：结果受选择凝聚点好坏的影响，分缺点：结果受选择凝聚点好坏的影响，分类结果不稳定。类结果不稳定。第44页/共52页第四十四页，共52页。第一，选择(xunz)凝聚点；第二，初始分类；对于取定的凝聚点，视每个凝聚点为一类，将每个样品根据定义的距离向最近的凝聚点归类。第三，修改分类 得到初始分类，计算各类的重心，以这些重心作为新的凝聚点，重新进行分类，重复步骤2，3，直到分类的结果与上一步的分类结果相同，表明分类已经合理为止。动态聚类法的基本(jbn)步骤：第45页/共52页第四十五页，共52页。例3：某商店5位售货员的销售量和教育(jioy)程度如下表：

20、售货员售货员12345销售量销售量（千件）（千件）11688教育程度教育程度12320对这5位售货员分类(fn li)。第46页/共52页第四十六页，共52页。1.选择(xunz)凝聚点 1 为最大。可选择2和5作为凝聚点。计算各样品(yngpn)点两两之间的距离，得到如下的距离矩阵第47页/共52页第四十七页，共52页。对于取定的凝聚点，视每个凝聚点为一类，将每个样品根据定义的距离(jl)，向最近的凝聚点归类。1 G1 G2 1 3 4得到(d do)初始分类为：2.初始(ch sh)分类第48页/共52页第四十八页，共52页。计算(j sun)G1和G2的重心：G1的重心（1,1.5），G

21、2的重心（7.33,1.67）G1 G212345得到分类结果：3.修改(xigi)分类以这两个(lin)重心点作为凝聚点，再按最小距离原则重新聚类重心是指每类的均值向量第49页/共52页第四十九页，共52页。售货员售货员12345销售量销售量（千件）（千件）11688教育程度教育程度12320对这5位售货员分类(fn li)。G1的重心(zhngxn)（1+1）/第一类中样品的个数=1,1.5），G2的重心(zhngxn)（6+8+8）/3=7.33,1.67）第50页/共52页第五十页，共52页。修改(xigi)前后所分的类相同，故可停止修改(xigi)。和。5个售货员可分为两类第51页/共52页第五十一页，共52页。感谢您的观看(gunkn)！第52页/共52页第五十二页，共52页。