数学建模聚类分析.

聚类分析一、聚类分析（ClusterAnalysis）简介聚类分析是直接比较各事物之间的性质，将性质相近的归为一类，将性质差别较大的归入不同的类的分析技术。数理统计中的数值分类有两种问题：•判别分析：已知分类情况，将未知个体归入正确类别•聚类分析：分类情况未知，对数据结构进行分类基本思想聚类分析的基本思想:对所研究的样品或指标(变量)之间存在着程度不同的相似性(或亲疏关系)。（1）根据一批样品的多个指标,具体找出一些能够度量样品或指标之间的相似程度的统计量。（2）以这些统计量为分类的依据,把一些相似程度较大的样品(或指标)聚合为一类。把另一些彼此之间相似程度较大的样品(或指标)聚合为另一类。基本思想按相似程度的大小把关系密切的样品聚合到一个小的分类单位,关系疏远的样品聚合到一个大的分类单位,直到把所有的样品(或指标)都聚合完毕。把不同的类型一一划分出来,形成一个由小到大的分类系统。再把整个分类系统画成一张分群图(又称谱系图),用它把所有样品(或指标)间的亲疏关系表示出来。要做聚类分析，首先得按照我们聚类的目的，从对象中提取出能表现这个目的的特征指标；然后根据亲疏程度进行分类。聚类分析根据分类对象的不同可分为Q型和R型两大类Q型是对样本进行分类处理，其作用在于:1.具有共同特点的样本聚在一起2.所得结果比传统的定性分类方法更细致、全面、合理二、聚类对象R型是对变量进行分类处理，其作用在于：1.可以了解变量间及变量组合间的亲疏关系2.可以根据变量的聚类结果及它们之间的关系，选择主要变量进行回归分析或Q型聚类分析2相似性度量进行“相关性”或“相似性”度量。在相似性度量中常常包含有许多主观上的考虑，但是最重要的是考虑指标性质或观测的尺度。当样品进行聚类时，“靠近”往往是距离。同时对指标进行聚类时，根据相关系数或某种关联性度量来聚类。Q型样品间的“相似性”度量—距离设每个样品有p个指标,观察值记为nixxxxTpiiii,,2,1,),,,(21(1)每个样品可看成是p维空间的一个点。于是,可用各点之间的距离来衡量各样品点之间的接近程度。样品和之间的距离,一般应满足如下条件:(ⅰ),且时当且仅当;(ⅱ);(ⅲ);有时所用的距离不满足(ⅲ),但在广义的角度上仍称为距离。常用的距离有如下几种:ixixjx),(jixxd0),(jixxd0),(jixxdjixx),(),(ijjixxdxxd),(),(),(jkkijixxdxxdxxdpkjkikijxxd12112)(pkjkikijxxd3、明考斯基距离(Minkowski)1、绝对距离（Block距离）2、欧氏距离(Euclideandistance)qpkqjkikijxxd11)(4、切比雪夫距离(Chebychev)jkikpkijxxd1max)(6.马氏距离5.数据的标准化,ijjijjxxxSjjxSj其中和是第个指标的均值和样本标准差以上距离与各变量的量纲有关，为了消除量纲的影响，可对数据标准化。21()()()()()()'()ijijijdMxxSxx例1欧洲各国的语言有许多相似之处，有的十分相似。为了研究这些语言的历史关系，也许通过比较他们数字的表达式比较恰当。表列举出英语，挪威语，丹麦语，荷兰语，德语，法语，西班牙语，意大利语，波兰语，匈牙利语和芬兰语的1,2,…,10的拼法，希望计算这11种语言之间的语言的距离.11种欧洲语言的数词英语挪威语丹麦语荷兰语德语法语西班牙语意大利语波兰语匈牙利语芬兰语(E)(N)(Da)(Du)(G)(Fr)(S)(I)(P)(H)(Fi)oneeneneeneinununounojedenegyyksitwotototweezweideuxdosducdwakettokaksithreetretredriedreitriostrestretrzyharomkolmefourfirefireviervierquatrecuatroquattroczterynegyneuafivefemfemvijffunfcinqcincocinquepiecotviisisixsekssekszexsechssixseixseiszeschathuusisevensjusyvzevensiebenseptsietesettesiedenhetseitsemaneightatteotteachtachthuitochoottoosiemnyolckahdeksanninenininegenneunneufnuevenovedziewieckilencyhdeksantentinitienzehndixdiezdiecidziesiectizkymmenen选择适用的距离在聚类分析中通常要结合实际问题来选择适用的距离,有时应根据实际问题定义新的距离,显然，本例无法直接用上述公式来计算距离。但可以发现前三种文字(英、挪、丹)很相似,特别是每个单词的第一个字母。可以用10个数词中第一个字母不同的个数来定义两种语言之间的距离。例如：英语和挪威语中只有1和8的第一个字母不同,则它们之间的距离为2。ENDaDuGFrSpIPHFiE0N20Da210Du7560G64550Fr666970Sp6659720I66597110P7761085340H98889101010100Fi999999999802112121nkkjnkkinkkjkiijxxxxCnknkjkjikinkjkjikiijxxxxxxxxr11221)()())((1、夹角余弦2、相关系数R型聚类统计量对两个指标之间的相似程度用相似系数来刻划，相似系数绝对对值越接近于1，表示指标间的关系越密切，绝对值越接近于0，表示指标间的关系越疏远.三系统聚类分析1.系统聚类分析的基本思想是：距离相近的样品（或变量）先聚成类，距离相远的后聚成类，过程一直下去，每个样品（或变量）总能聚到合适的类中。系统聚类分析过程是：假设总共有n个样品（或变量），第一步将每个样品（或变量）独自聚成一类，共有n类；第二步根据所确定的样品（或变量）“距离”公式，将距离较近的两个样品（或变量）聚合为一类，其他样品（或变量）仍各自聚为一类，共有n－1类；第三步将“距离”最近的两个类进一步聚成一类，共聚成n－2类；……以上步骤一直进行下去，最后将所有的样品或变量）聚成一类。将整个分类系统地画成一张谱系图，所以有时系统聚类分析也叫谱系聚类分析。2.类间距离首先定义类与类之间地距离，又类间的距离定义不同产生不同的系统聚类分析。常见的类间的距离有法。它们的归类步骤基本是一致的。8种之多，与之相应的系统聚类分析也有8种之多、分别为最短距离法、最长距离法、中间距离法、重心法、类平均法、可变类平均法、可变法和离差平方和用i,j表示样品。用表示与之间的距离,用与表示两个类,所包含的样品数分别为与之间的距离用表示。下面给出四种最常用的类与类之间距离的定义。jixx,ixijdjxqGpGpGqGpnqn),(qpGGD1、最短距离（NearestNeighbor)x21•x12•x22•x11•13dqpijqppqGjGidGGDD,min),(即定义与之间的距离为与中最近的两个样品的距离。类与类之间的最短距离有如下的递推公式。设由与合并而成,则与其它类的最短距离为pGqGpGqGpGrGqGrG),(qpkGkkqijkpijkrijkrGjGidGjGidGjGidGGD,min,,minmin,min),(),(),,(minkqkpGGDGGD1、根据样品的特征，规定样品之间的距离，共有个。将所有列表，记为D（0）表，该表是一张对称表。所有的样本点各自为一类。2、选择D（0）表中最小的非零数，不妨假设，于是将和合并为一类，记为。pqdpGqGqprGGG，2nCijd开始各样本自成一类最短距离法进行聚类分析的步骤如下：3、利用递推公式计算新类与其它类之间的距离。分别删除D（0）表的第p，q行和第p，q列，并新增一行和一列添上的结果，产生D（1）表。4、在D（1）表再选择最小的非零数，其对应的两类有构成新类，再利用递推公式计算新类与其它类之间的距离。分别删除D（1）表的相应的行和列，并新增一行和一列添上的新类和旧类之间的距离。结果，产生D（2）表。类推直至所有的样本点归为一类为止。最短距离法进行聚类分析的步骤如下：（1)定义样品之间的距离（2)找出距离最小元素，设为，则将pqDpqGG与合并成一新类记为rG,记为{,}rpqGGG（3）按上式计算新类与其他类之间的距离。（4）重复（2），（3）的步骤，直到将所有元素并成一类为止。(如果某一步距离最小的元素不止一个，则将对应这些最小元素的类可以同时合并）例2设有6个样品，每个只测一个指标，分别是1，2，5，7，9，10，试采用绝对值距离用最短距离法将它们进行分类。解（1）样品首先采用绝对值距离，计算样品之间的距离阵为D(0).G1G2G3G4G5G6G10G210G3430G46520G587420G6985210D(0)G2={2}G1={1}G3={5}G4={7}G5={9}G6={10}G7G8G9G10123D2.最长距离（FurthestNeighbor）•••x11•x21••••12dqpijqpGjGidGGD,max),(即定义与之间的距离为与中最远的两个样品的距离。类与类之间的最长距离有如下的递推公式。设由与合并而成,则到的最长距离为pGqGpGqGpGrGqGrG),(qpkGkkqijkpijkrijkrGjGidGjGidGjGidGGD,max,,maxmax,max),(),(),,(maxkqkpGGDGGD2.最长距离（FurthestNeighbor）••••••991dd组间平均连接（Between-groupLinkage)3.类平均距离组内平均连接法（Within-groupLinkage)1234566ddddddx21•x12•x22•x11•3.类平均距离4.重心法（Centroidclustering):均值点的距离••11,xy22,xyqpknnnqqppkkxnxnnx1rkrkkrxxxxd22222pqkqkpqrkqprkpkrdnnnndnndnnd将p和q合并为k，则k类的样品个数为它的重心是rx某一类r的重心是，它与新类k的距离是经推导可以得到如下递推公式：pnqn设聚类到某一步，类p与q分别有样品、个，例2设有6个样品，每个只测一个指标，分别是1，2，5，7，9，10，试采用欧氏距离的平方,试用重心法将它们进行分类。G1G2G3G4G5G6G10G210G31690G4362540G564491640G6816425910D2(0)G7G3G4G8G70G312.250G430.2540G86420.256.250D2(1)其中2222373132121111222211111691222212.25DDDDD2(2)G7G9G8G70G920.250G86412.250D2(3)G7G10G70G1039.06250G1={1}G2={2}G3={5}G4={7}G5={9}G6={10}2412.5D1G9G7G8G10G115.动态聚类法（快速聚类法）系统聚类法是一种比较成功的聚类方法。然而当样本点数量十分庞大时，则是一件非常繁重的工作，且聚类的计算速度也比较慢。比如在市场抽样调查中，有4万人就其对衣着的偏好作了回答，希望能迅速将他们分为几类。这时，采用系统聚类法就很困难，而动态聚类法就会显得方便，适用。动态聚类使用于大型数据。•基本思想