交通数据处理与分析 第三章 聚类分析

聚类分析分类物以类聚、人以群分；但根据什么分类呢？如要想把中国的县分类，就有多种方法可以按照自然条件来分，比如考虑降水、土地、日照、湿度等，也可考虑收入、教育水准、医疗条件、基础设施等指标；既可以用某一项来分类，也可以同时考虑多项指标来分类。聚类分析是研究分类问题的一种多元统计方法。所谓类，就是指相似元素的集合聚类分析的研究目的

把相似的东西归成类，根据相似的程度将研究目标进行分类。什么是聚类分析聚类分析对一个数据，既可以对变量(指标)进行分类(相当于对数据中的列分类)，也可以对观测值(事件，样品)来分类(相当于对数据中的行分类)。当然，不一定事先假定有多少类，完全可以按照数据本身的规律来分类。本章要介绍的分类的方法称为聚类分析（clusteranalysis）。聚类分析原理介绍聚类分析中“类”的特征：聚类所说的类不是事先给定的，而是根据数据的相似性和距离来划分聚类分析原理介绍我们看看以下的例子：有16张牌如何将他们分为一组一组的牌呢？AKQJ聚类分析原理介绍分成四组每组里花色相同组与组之间花色相异AKQJ花色相同的牌为一副Individualsuits聚类分析原理介绍分成四组符号相同的牌为一组AKQJ符号相同的的牌Likefacecards聚类分析原理介绍这个例子告诉我们，分组的意义在于我们怎么定义并度量“相似性”AKQJ聚类分析的研究对象R型分析----对变量进行分类Q型分析----对样品进行分类聚类分析研究的主要内容如何度量事物之间的相似性?怎样构造聚类的具体方法以达到分类的目的?如何度量距离远近？如果想要对100个学生进行分类，而仅知道他们的数学成绩，则只好按照数学成绩分类；这些成绩在直线上形成100个点。这样就可以把接近的点放到一类。如果还知道他们的物理成绩，这样数学和物理成绩就形成二维平面上的100个点，也可以按照距离远近来分类。如何度量距离远近？三维或者更高维的情况也是类似；只不过三维以上的图形无法直观地画出来而已。两个距离概念按照远近程度来聚类需要明确两个概念：一个是点和点之间的距离，一个是类和类之间的距离。点间距离有很多定义方式。最简单的是歐氏距离。当然还有一些和距离相反但起同样作用的概念，比如相似性等，两点越相似度越大，就相当于距离越短。两个距离概念由一个点组成的类是最基本的类；如果每一类都由一个点组成，那么点间的距离就是类间距离。但是如果某一类包含不止一个点，那么就要确定类间距离，类间距离是基于点间距离定义的：比如两类之间最近点之间的距离可以作为这两类之间的距离，也可以用两类中最远点之间的距离或各类的中心之间的距离来作为类间距离。一、相似性的测度

距离：测度样品之间的亲疏程度。将每一个样品看作p维空间的一个点，并用某种度量测量点与点之间的距离，距离较近的归为一类，距离较远的点应属于不同的类。相似系数：测度变量之间的亲疏程度距离和相似系数2、常用的距离明氏距离特别地，当k＝1时，即为绝对值距离(1)明氏距离（Minkowski）令表示样品与的距离

设原始数据为明氏距离当k＝2时，即为欧氏距离当k＝∞时，即为切比雪夫距离123452018104471055325.236.328.911.517欧氏距离切比雪夫距离明考夫斯基距离有以下两个缺点：①明氏距离的数值与指标的量纲有关。当各变量的测量值相差悬殊时，常发生“大数吃小数”的现象，为消除量纲的影响，通常先将每个变量进行标准化。②明氏距离的定义没有考虑各个变量之间相关性的影响。年龄收入家庭人口数甲3030001乙4032003当xi>0时(i=1,2,…,n;k=1,2,…,p)，第i个样品Xi和Xj之间的兰氏距离表示为兰氏（Lance和Williams）距离兰氏距离与各变量的单位无关，对大的异常值不敏感，故适用于高度偏斜的数据马氏距离由印度著名统计学家马哈拉诺比斯(Mahalanobis)所定义的一种距离，其计算公式为：

=马氏距离又称为广义欧氏距离。马氏距离考虑了观测变量之间的相关性。如果假定各变量之间相互独立，即观测变量的协方差矩阵是对角矩阵，此时马氏距离就是标准化的欧氏距离。马氏距离不受指标量纲及指标间相关性的影响夹角余弦相似系数相关系数相似系数由相似系数还可定义变量之间的距离相似系数间隔尺度变量变量用连续的量来表示，如长度、重量、速度、流量有序尺度变量变量度量时不用明确的数量表示，而是用等级来表示，如产品的等级，交通的拥堵程度等。名义尺度变量变量用一些类表示，这些类之间既无等级关系，也无数量关系，如性别，车型等。变量类型系统聚类法系统聚类法的基本思想

先将n个样品各自看成一类，然后规定样品之间的“距离”和类与类之间的距离。选择距离最近的两类合并成一个新类，计算新类和其它类（各当前类）的距离，再将距离最近的两类合并。这样，每次合并减少一类，直至所有的样品都归成一类为止。最终形成一个亲疏关系图谱（聚类树形图或谱系图），通常从图上可清洗地看出应分为几类以及每一类中所包含的样品（或变量）。除此之外也可借助统计量确定分类结果系统聚类法的基本思想在聚类分析中，通常用G表示类，将定G中有m个元素（即样品或变量），不失一般化，用列向量xi（i=1，2，…，m）来表示，dij表示元素xi与xj之间的距离。DKL表示类GK与GL之间的距离。类与类之间用不同的方法定义距离，产生了以下不同的系统聚类方法系统聚类法的基本思想

最短距离法最长距离法中间距离法重心法类平均法

离差平方和法（Ward法）系统聚类方法：

上述6种方法归类的基本步骤一致，只是类与类之间的距离有不同的定义。定义类p与q之间的距离为两类最近样品的距离，即xq1•xp2•xq2•xp1•xq3•最短距离法设类p与q合并成一个新类，记为k，则k与任一类r的距离是pqkr定义类与类之间的距离为两类最近样品间的距离，即最短距离法若某一步类GK与类GL聚成一个新类，记为GM，类GM与任意已有的类GJ之间的距离为聚类步骤如下将初始的每个样品（或变量）各自作为一类，并规定样品（或变量）之间的距离，通常采用欧式距离。计算n个样品（或p个变量）的距离矩阵D(0)，它是一个对称矩阵。寻找D(0)中最小元素，设为DKL，将GK和GL聚成一个新类，记为GM，即GM={GK，GL}计算新类GM与任一类GJ之间距离的递推公式为最短距离法对距离矩阵D(0)进行修改，将GK和GL所在的行和列合并成一个新行新列，对应GM，新行和新列上的新距离由上式计算，其余行列上的值不变，这样得到新的距离矩阵记为D(1)对D(1)重复上述对D(0)的操作，得到距离矩阵D(2)，如此进行下去，直至所有元素合并成一类为止。最短距离法设有5个样品，每个只测量了一个指标，指标值分别是1,2,6,8,11.若样品间采用绝对值距离，下面用最短距离法对这五个样品进行聚类，过程如下将五个样品各自作为一类，分别记为G1,G2,G3,G4,G5。计算样品间的初始距离矩阵D(0)，如下表所示最短距离法G1G2G3G4G5G10G210G3540G47620G5109530D(0)中最小元素是D12=1，于是将G1和G2合并成G6，得到距离矩阵D(1)最短距离法

G6G3G4G5G60G340G4620G59530D(1)中最小元素是D34=2，于是将G3和G4合并成G7，得到距离矩阵D(2)最短距离法G6G7G5G60G740G5930D(2)中最小元素是D57=3，于是将G5和G7合并成G8，得到距离矩阵D(3)最短距离法G6G8G60G840最后将G6和G8合并成G9，这是所有五个样品聚为一类，聚类结束。例

最短距离法

设抽取5个样品，每个样品观察2个指标，：某路段上年均交通事故发生数：某路段上年均因交通事故受伤人数1234520181044710553

②③④⑤①②③④3.610.216.1216.499.4314.8715.6566.32

2计算5个样品两两之间的距离记为距离矩阵（采用欧氏距离），2.合并距离最小的两类为新类，按顺序定为第６类。⑥＝3、计算新类⑥与各当前类的距离，得距离矩阵如下：②③⑥①②③

3.6

10.216.129.4314.876为最小，⑦=⑥⑦③⑥

6

9.4314.874、重复步骤2、3，合并距离最近的两类为新类，直到所有的类并为一类为止。

为最小，⑧=5、6、按聚类的过程画聚类谱系图45⑥⑨⑧并类距离312⑦7、决定类的个数与类。

观察此图，我们可以把5个样品分为3类，、、。•••x11•x21••••二、最长距离法定义类p与q之间的距离为两类最远样品的距离，即设类p与q合并成一个新类，记为k，则k与任一类r的距离是pqkr

②③④⑤①②③④3.610.216.1216.499.4314.8715.6566.32

2计算5个样品两两之间的距离记为距离矩阵（采用欧氏距离），2.合并距离最小的两类为新类，按顺序定为第６类。⑥＝例最长距离法

3、计算新类⑥与各当前类的距离，得距离矩阵如下：②③⑥①②③

3.6

10.216.499.4315.656.32为最小，⑦=⑥⑦③⑥6.32

10.216.494、重复步骤2、3，合并距离最近的两类为新类，直到所有的类并为一类为止。

为最小，⑧=5、6、按聚类的过程画聚类谱系图45⑥⑨⑧并类距离312⑦7、决定类的个数与类。

观察此图，我们可以把5个样品分为3类，、、。三、中间距离法定义类与类之间的距离既不采用两类之间最近的距离，也不采用两类之间最远的距离，而是采用介于两者之间的距离，故称为中间距离法。•••rpqk

②③④⑤①②③④13104260272892212453640

4计算5个样品两两之间的距离记为距离矩阵（采用欧氏距离），2.合并距离最小的两类为新类，按顺序定为第６类。⑥＝例中间距离法

3、计算新类⑥与各当前类的距离，得距离矩阵如下：②③⑥①②③

13

1042658923237为最小，⑦=⑥⑦③⑥

37

93.25245.254、重复步骤2、3，合并距离最近的两类为新类，直到所有的类并为一类为止。

为最小，⑧=5、6、按聚类的过程画聚类谱系图45⑥⑨⑧并类距离312⑦7、决定类的个数与类。

观察此图，我们可以把5个样品分为3类，、、。四、重心法（Centroid)••和类与类之间的距离就考虑用重心之间的距离表示。设p与q的重心分别是，则类p和q的距离为将p和q合并为k，则k类的样品个数为它的重心是某一类r的重心是，它与新类k的距离是经推导可以得到如下递推公式：设聚类到某一步，类p与q分别有样品

、个，

②③④⑤①②③④13104260272892212453640

4计算5个样品两两之间的距离记为距离矩阵（采用欧氏距离），2.合并距离最小的两类为新类，按顺序定为第６类。⑥＝例重心法

3、计算新类⑥与各当前类的距离，得距离矩阵如下：②③⑥①②③

13

1042658923237为最小，⑦=⑥⑦③⑥

37

93.25245.254、重复步骤2、3，合并距离最近的两类为新类，直到所有的类并为一类为止。

为最小，⑧=5、6、按聚类的过程画聚类谱系图45⑥⑨⑧并类距离312⑦7、决定类的个数与类。

观察此图，我们可以把5个样品分为3类，、、。五、类平均法（Average)定义两类之间的距离平方为这两类元素两两之间距离平方的平均•••••pq将p和q合并为k，则k类的样品个数为设聚类到某一步，类p与q分别有样品、个，k类与任一类r的距离为

②③④⑤①②③④13104260272892212453640

4计算5个样品两两之间的距离记为距离矩阵（采用欧氏距离），2.合并距离最小的两类为新类，按顺序定为第６类。⑥＝例类平均法

3、计算新类⑥与各当前类的距离，得距离矩阵如下：②③⑥①②③

13

1042668923338为最小，⑦=⑥⑦③⑥

38

96.5249.54、重复步骤2、3，合并距离最近的两类为新类，直到所有的类并为一类为止。

为最小，⑧=5、6、按聚类的过程画聚类谱系图45⑥⑨⑧并类距离312⑦7、决定类的个数与类。

观察此图，我们可以把5个样品分为3类，、、。系统聚类法的不同之处在于类间距离的计算方法不同，Wishart将不同的距离计算公式统一为系统聚类法的统一同样的观测数据，应用不同的聚类方法进行聚类，可能得到不同的结果。通常从两个方面进行评价单调性空间的浓缩与扩张系统聚类法的评价单调性令Di是系统聚类过程中第i次并类时的距离，若有D1≤D2≤…≤Di，则成次系统聚类法具有单调性。在上述聚类方法中，最短距离法、最长距离法、中间距离法、类平均法和离散平方和法具有单调性，而中间距离法和重心法不具有单调性。系统聚类法的评价空间的浓缩与扩张针对同一问题，用不同系统聚类法进行聚类，做出的聚类树形图的横坐标（并类距离）的范围相差很大。范围小的方法区别类的灵敏度差，而范围太大的方法灵敏度又过高设有甲、乙两类聚类方法，第i步的距离矩阵分别为Ai和Bi，若Ai≥Bi，则称甲方法比乙方法更使空间扩张，或称乙方法比甲方法更使空间浓缩。系统聚类法的评价与类平均法相比，最短距离法和重心法使空间浓缩，最长距离法和离差平方和法是空间扩张。太浓缩的方法不够灵敏，太扩张的方法又容易失真，而类平均法相对比较适中。系统聚类法的评价PdistY=pdist（X）计算样品对的欧式距离。输入参数X是nхp的矩阵，矩阵的每一行对应一个样品，每一列对应一个变量。输出参数Y是包含n(n-1)/2个元素的行向量，用(i,j)表示第i个样品和第j个样品构成的样品对，则Y中的元素依次是(2,1),(3,1),…,(n,1),(3,2),…,(n,2),…,(n,n-1)系统聚类法的相关函数Y=pdist（X,metric）输入参数metric指定计算距离的方法，metric为字符串，可用的字符串如下表所示。系统聚类法的相关函数Metric参数值说明‘euclidean’欧式距离‘seuclidean’标准化欧式距离‘mahalanobis’马哈拉诺比斯距离‘cityblock’绝对值距离‘minkowski’闵可夫斯基距离‘chebychev’切比雪夫距离Y=pdist（X,‘minkowski’,p）计算样品对的闵可夫斯基距离，输入参数p为闵可夫斯基距离计算中的指数，默认情况下，指数为2系统聚类法的相关函数SquareformZ=squareform(y)Z=squareform(y,‘tomatrix’)y=squareform(Z)y=squareform(Z,‘tovector’)前两种调用时把pdist函数输出的距离向量y转为距离矩阵Z，而后两种调用则是把距离矩阵Z转换为pdist函数输出的距离向量y。系统聚类法的相关函数Linkage函数Z=linkage（y）利用最短距离法创建一个系统聚类树。输入参数y是样品对距离向量，是包含n(n-1)/2个元素的行向量，通常是pdist函数的输出。输出Z是一个系统聚类树矩阵，它是(n-1)*3的矩阵，这里的n是原始数据中观测样品的个数。Z矩阵每一行对应一次并类，第i行上前两个元素为第i次并类的两个类的类编号，初始类编号为1~n，以后每形成一个新类，类编号从n+1开始逐次增加1.Z矩阵的第i行中的第3个元素为第i次并类是的并类距离系统聚类法的相关函数Z=linkage（y,method）利用method参数制定的方法创建系统聚类树，method是字符串，可用的字符串如下所示系统聚类法的相关函数Method参数值说明‘average’类平均法‘centroid’重心法‘complete’最长距离法‘median’中间距离法‘single’最短距离法‘ward’离差平方和法‘weighted’可变类平均法Z=linkage（y,method,metric）metric用来制定计算距离的方法系统聚类法的相关函数Dendrogram函数H=dendrogram（Z）由系统聚类树矩阵Z生成系统聚类树形图。输入参数Z是由linkage函数输出的系统聚类树矩阵。输出参数H是树形图中线条的句柄值向量，用来控制线条属性。系统聚类法的相关函数H=dendrogram（Z，p）生成一个树形图，通过输入参数p来控制显示的叶节点数。系统聚类法的相关函数H=dendrogram（…,‘orientation’,‘orient’）通过设定’orientation’参数及参数值’orient’来控制聚类树形图的方向和放着叶节点标签的位置，可用参数如下所示参数值说明‘top’从上至下，叶节点标签在下方，为默认情况‘bottom’从下至上，叶节点标签在上方‘left’从左至右，叶节点标签在右边‘right’从右至左，叶节点标签在左边H=dendrogram（…,‘labels’,S）通过一个字符串数组或字符串元胞数组设定每一个观测值的标签。当树形图中显示了全部的叶节点时，叶节点的标签记为相应观测的标签；当树形图中忽略了某些节点时，只包含单个观测的叶节点的标签记为相应观测的标签。系统聚类法的相关函数Cophenet函数Cophenet函数用来计算系统聚类树的cophenetic相关系数Cophenetic相关系数反映了聚类效果的好坏，cophenetic相关系数越接近于1，