数学建模聚类分析马莎莎

1、聚聚 类类 分分 析析 一、聚类分析（一、聚类分析（Cluster Analysis）简介）简介 聚类分析是直接比较各事物之间的性质，将性质聚类分析是直接比较各事物之间的性质，将性质相相近近的归为一类，将性质的归为一类，将性质差别较大差别较大的归入不同的类的分析的归入不同的类的分析技术。技术。基本思想基本思想 聚类分析的基本思想聚类分析的基本思想: : 所研究的所研究的样品或指标样品或指标( (变变量量) )之间存在着之间存在着程度不同的相似性程度不同的相似性( (或亲疏关系或亲疏关系) )。（1 1）根据一批样本的多个指标）根据一批样本的多个指标, , 具体找出一些能够具体找出一些能够度量度

2、量样本或指标之间的样本或指标之间的相似程度相似程度的的统计量统计量。（2 2）以这些统计量为分类的）以这些统计量为分类的依据依据, , 把一些相似程度把一些相似程度较大较大的样本的样本( (或指标或指标) )聚合为一类。聚合为一类。 基本思想基本思想 按相似程度的大小按相似程度的大小把关系把关系密切密切的样本聚合到一个的样本聚合到一个小小的分类单位的分类单位, , 关系关系疏远疏远的样本聚合到一个的样本聚合到一个大大的分类单位的分类单位, , 直到把所有的样本直到把所有的样本( (或指标或指标) )都聚合完毕。都聚合完毕。 把不同的类型一一划分出来把不同的类型一一划分出来, , 形成一个由小到

3、大形成一个由小到大的分类系统。再把整个分类系统画成一张分群图的分类系统。再把整个分类系统画成一张分群图( (又又称称谱系谱系图图), ), 用它把所有样本用它把所有样本( (或指标或指标) )间的亲疏关系间的亲疏关系表示出来。表示出来。 一个事物常常需要用多个变量来刻画，如果对于一一个事物常常需要用多个变量来刻画，如果对于一群有待分类的样本点需用群有待分类的样本点需用p个变量描述，则这个样本点个变量描述，则这个样本点可以看成是可以看成是 空间中的一个点。空间中的一个点。聚类分析根据分类对象的不同可分为聚类分析根据分类对象的不同可分为Q型和型和R型两大类型两大类Q型是对型是对样本样本进行分类处理

4、，其作用在于进行分类处理，其作用在于:1. 具有共同特点的样本聚在一起具有共同特点的样本聚在一起2. 所得结果比传统的定性分类方法更细致、全面、所得结果比传统的定性分类方法更细致、全面、合理合理二、聚类对象：二、聚类对象：样本、变量样本、变量pRR型是对型是对变量变量进行分类处理，其作用在于：进行分类处理，其作用在于：1. 可以了解变量间及变量组合间的亲疏关系可以了解变量间及变量组合间的亲疏关系2. 可以根据变量的聚类结果及它们之间的关系，可以根据变量的聚类结果及它们之间的关系，选择主要变量进行回归分析或选择主要变量进行回归分析或Q型聚类分析型聚类分析相似性度量相似性度量 进行进行“相关性相关

5、性”或或“相似性相似性”度量。在相似性度量。在相似性度量中常常包含有许多主观上的考虑，但是最重要度量中常常包含有许多主观上的考虑，但是最重要的是考虑指标性质或观测的尺度。的是考虑指标性质或观测的尺度。对对样本进行聚类时，样本进行聚类时，“靠近靠近”往往是往往是距离距离。对指标进行聚类时，根据对指标进行聚类时，根据相关系相关系数数或某种或某种关联性关联性度量度量来来聚类。聚类。Q型型样本间样本间的的“相似性相似性”度量度量距离距离 设每个样本有 p 个指标, 观察值记为nixxxxTpiiii, 2 , 1,),(21(1)每个样本 可看成是 p 维空间的一个点。于是, 可用各点之间的距离来衡量

6、各样本点之间的接近程度。 样本 和 之间的距离 , 一般应满足如下条件: () , 且 时当且仅当 ; () ; () ; 有时所用的距离不满足(), 但在广义的角度上仍称为距离。常用的距离有如下几种:ixixjx),(jixxd0),(jixxd0),(jixxdjixx ),(),(ijjixxdxxd),(),(),(jkkijixxdxxdxxdpkjkikijxxd12112)(pkjkikijxxd 1、闵氏距离、闵氏距离(Minkowski)2、绝对距离（、绝对距离（Block距离）距离）3、欧氏距离、欧氏距离(Euclidean distance)qpkqjkikijxxd11

7、)(4、切比雪夫距离、切比雪夫距离(Chebychev)jkikpkijxxd1max)(6.马氏距离马氏距离5.数据的标准化数据的标准化ijjijjxxxS jjxSj其中 和是第 个指标的均值和样本标准差以上距离与各变量的量纲有关，为了消除量纲的以上距离与各变量的量纲有关，为了消除量纲的影响，可对数据标准化。影响，可对数据标准化。21( )( )( )( )()()()ijijijdMxxSxx 例例1 欧洲各国的语言有许多相似之处，有的十分欧洲各国的语言有许多相似之处，有的十分相似。为了研究这些语言的历史关系，也许通过比较相似。为了研究这些语言的历史关系，也许通过比较他们数字的表达式比较

8、恰当。表格列举出英语，挪威他们数字的表达式比较恰当。表格列举出英语，挪威语，丹麦语，荷兰语，德语，法语，西班牙语，意大语，丹麦语，荷兰语，德语，法语，西班牙语，意大利语，波兰语，匈牙利语和芬兰语的利语，波兰语，匈牙利语和芬兰语的1,2,10的拼法，的拼法，希望计算这希望计算这11种语言之间的语言的距离种语言之间的语言的距离.11种欧洲语言的数词选择适用的距离选择适用的距离 在聚类分析中通常要结合实际问题来选择在聚类分析中通常要结合实际问题来选择适用适用的的距离距离, , 有时应根据实际问题定义新的距离有时应根据实际问题定义新的距离, , 显然，本例无法直接用上述公式来计算距离。但显然，本例无法

9、直接用上述公式来计算距离。但可以发现可以发现前三种文字前三种文字( (英、挪、丹英、挪、丹) )很相似很相似, , 特别是每个单词的第特别是每个单词的第一一个字母。可以用个字母。可以用1010个数词个数词中中第一个第一个字母字母不同不同的的个数个数来定义两种语言之间的距离。来定义两种语言之间的距离。例如：英语和挪威语中只有例如：英语和挪威语中只有1 1和和8 8的第一个字母不同的第一个字母不同, , 则它们之间的距离为则它们之间的距离为2 2。E N Da Du G Fr Sp I P H Fi E 0 N 2 0Da 2 1 0Du 7 5 6 0G 6 4 5 5 0Fr 6 6 6 9

10、7 0Sp 6 6 5 9 7 2 0I 6 6 5 9 7 1 1 0P 7 7 6 10 8 5 3 4 0H 9 8 8 8 9 10 10 10 10 0Fi 9 9 9 9 9 9 9 9 9 8 0首先定义类与类之间的距离，由类间距离的定义首先定义类与类之间的距离，由类间距离的定义 不同产生不同的系统聚类分析。常见的类间的距离不同产生不同的系统聚类分析。常见的类间的距离有有法。它们的归类步骤基本是一致的。法。它们的归类步骤基本是一致的。8种之多，与之相应的系统聚类分析也有种之多，与之相应的系统聚类分析也有8种之多、种之多、分别为最短距离法、最长距离法、中间距离法、重心分别为最短距离

11、法、最长距离法、中间距离法、重心法、类平均法、可变类平均法、可变法和离差平方和法、类平均法、可变类平均法、可变法和离差平方和Q型型类与类类与类间间的的“相似性相似性”度量度量 说明：说明： 用 i , j 表示样本 。用 表示 与 之间的距离, 用 与 表示两个类, 所包含的样本数分别为 与 之间的距离用 表示。下面给出四种最常用的类与类之间距离的定义。jixx ,ixijdjxqGpGpGqGpnqn),(qpGGD1 、最短距离（、最短距离（Nearest Neighbor)x21x12x22x1112dqpijqppqGjGidGGDD,min),(即定义 与 之间的距离为 与 中最近的

12、两个样本的距离。 pGqGpGqGn最短距离法进行聚类分析的步骤如下：最短距离法进行聚类分析的步骤如下：（1）定义样品之间距离，计算样品的两两距离，得一距离）定义样品之间距离，计算样品的两两距离，得一距离 阵记为阵记为D（0） ，开始每个样品自成一类，显然这时，开始每个样品自成一类，显然这时Dij = dij。（2）找出距离最小元素，设为）找出距离最小元素，设为Dpq，则将，则将Gp和和Gq合并成一个合并成一个 新类，记为新类，记为Gr，即，即Gr = Gp，Gq。（3）按（）按（5.12）计算新类与其它类的距离。）计算新类与其它类的距离。 （4）重复（）重复（2）、（）、（3）两步，直到所有

13、元素。并成一类为）两步，直到所有元素。并成一类为 止。如果某一步距离最小的元素不止一个，则对应这些止。如果某一步距离最小的元素不止一个，则对应这些 最小元素的类可以同时合并。最小元素的类可以同时合并。n【例例2】设有六个样品，每个只测量一个指标，分别是设有六个样品，每个只测量一个指标，分别是1，2，5，7，9，10，试用最短距离法将它们分类。，试用最短距离法将它们分类。（1）样品采用绝对值距离，计算样品间的距离阵）样品采用绝对值距离，计算样品间的距离阵D（0） ，见，见表表1表表1 G1G2G3G4G5G6G1 0G2 10G3 430G4 6520G5 8742 0G6 9852 10 D(

14、0)（2）D（0）中最小的元素是中最小的元素是D12D561，于是将，于是将G1和和G2合合并成并成G7，G5和和G6合并成合并成G8，并利用（，并利用（5.12）式计算新类与其）式计算新类与其它类的距离它类的距离D（1） ，见表，见表2表表2 （3）在）在D（1）中最小值是中最小值是D34D482，由于，由于G4与与G3合并，合并，又与又与G8合并，因此合并，因此G3、G4、G8合并成一个新类合并成一个新类G9，其与其，其与其它类的距离它类的距离D（2） ，见表，见表3表表3 （4）最后将）最后将G7和和G9合并成合并成G10，这时所有的六个样品聚为一，这时所有的六个样品聚为一类，其过程终止

15、。类，其过程终止。上述聚类的可视化过程见图上述聚类的可视化过程见图1所示，横坐标的刻度表示并类所示，横坐标的刻度表示并类的距离。这里我们应该注意，聚类的个数要以实际情况所定，的距离。这里我们应该注意，聚类的个数要以实际情况所定，其详细内容将在后面讨论。其详细内容将在后面讨论。图图1 最短距离聚类法的过程最短距离聚类法的过程G2=2G1=1G3=5G4=7G5=9G6=10G7G8G9G10123D2.最长距离（最长距离（Furthest Neighbor ）x11x21n再找距离最小两类并类，直至所有的样品全归为一类为止。再找距离最小两类并类，直至所有的样品全归为一类为止。可以看出最长距离法与

16、最短距离法只有两点不同：可以看出最长距离法与最短距离法只有两点不同：一是类与类之间的距离定义不同；一是类与类之间的距离定义不同；另一是计算新类与其它类的距离所用的公式不同。另一是计算新类与其它类的距离所用的公式不同。n【例例2】针对例针对例1的数据，试用重心法将它们聚类。的数据，试用重心法将它们聚类。（1）样品采用欧氏距离，计算样品间的平方距离阵）样品采用欧氏距离，计算样品间的平方距离阵D2（0），见，见表表4所示。所示。 表表4 （2）D2（0）中最小的元素是中最小的元素是D212D2561，于是将，于是将G1和和G2合合并成并成G7，G5和和G6合并成合并成G8，并利用（，并利用（5.18

17、）式计算新类与）式计算新类与其它类的距离得到距离阵其它类的距离得到距离阵D2（1） ，见表，见表5： 其中，其中，其它结果类似可以求得其它结果类似可以求得 （3）在）在D2（1）中最小值是中最小值是D2344，那么，那么G3与与G4合并一个新合并一个新类类G9，其与与其它类的距离，其与与其它类的距离D2（2） ，见表，见表6： 表表6 （4）在中最小值是）在中最小值是12.5，那么与合并一个新类，其与与，那么与合并一个新类，其与与其它类的距离，见表其它类的距离，见表7：表表7 （5）最后将）最后将G7和和G10合并成合并成G11，这时所有的六个样品聚为一类，这时所有的六个样品聚为一类，其过程终

18、止。其过程终止。上述重心法聚类的可视化过程见图上述重心法聚类的可视化过程见图3所示，横坐标的刻度表所示，横坐标的刻度表示并类的距离。示并类的距离。图图3 重心聚类法的过程重心聚类法的过程G1=1G2=2G3=5G4=7G5=9G6=102412.5D1G9G7G8G10G115. 离差平方和法离差平方和法该方法是该方法是Ward提出来的，所以又称为提出来的，所以又称为Ward法。该方法的基法。该方法的基本思想来自于方差分析，如果分类正确，同类样品的离差平本思想来自于方差分析，如果分类正确，同类样品的离差平方和应当较小，类与类的离差平方和较大。具体做法是先将方和应当较小，类与类的离差平方和较大。

19、具体做法是先将n个样品各自成一类，然后每次缩小一类，每缩小一类，离个样品各自成一类，然后每次缩小一类，每缩小一类，离差平方和就要增大，选择使方差增加最小的两类合并，直到差平方和就要增大，选择使方差增加最小的两类合并，直到所有的样品归为一类为止。所有的样品归为一类为止。设将设将n个样品分成个样品分成k类类G1，G2，Gk，用，用Xit表示表示Gt中的第中的第I个样品，个样品，nt表示表示Gt中样品的个数，中样品的个数， 是是Gt的重心，则的重心，则Gt的样品的样品离差平方和为离差平方和为2112121nkkjnkkinkkjkiijxxxxCnknkjkjikinkjkjikiijxxxxxxxxr11221)()()(1、夹角余弦、夹角余弦2、相关系数、相关系数R型聚类统计量型聚类统计量 对两个指标之间的相似程度用对两个指标之间的相似程度用相关系数相关系数来刻划，来刻划，相关系数相关系数绝对