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

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

2、分类。对一个数据，既可以对变量对一个数据，既可以对变量( (指标指标) )进行进行分类分类( (相当于对数据中的列分类相当于对数据中的列分类) )，也可，也可以对观测值以对观测值( (事件，样品事件，样品) )来分类来分类( (相当相当于对数据中的行分类于对数据中的行分类) )。当然，不一定事先假定有多少类，完当然，不一定事先假定有多少类，完全可以按照数据本身的规律来分类。全可以按照数据本身的规律来分类。本章要介绍的分类的方法称为聚类分本章要介绍的分类的方法称为聚类分析（析（cluster analysiscluster analysis）。）。聚类分析中“类”的特征： 聚类所说的类不是事先给

3、定的，而是根据数据的相似性和距离来划分我们看看以下的例子：有16张牌如何将他们分为 一组一组的牌呢？AKQJ分成四组每组里花色相同组与组之间花色相异AKQJ花色相同的牌为一副花色相同的牌为一副Individual suits分成四组符号相同的牌为一组AKQJ符号相同的的牌符号相同的的牌Like face cards这个例子告诉我们，分组的意义在于我们怎么定义并度量“相似性”AKQJ聚类分析的研究对象 R型分析-对变量进行分类 Q型分析-对样品进行分类聚类分析研究的主要内容n如何度量事物之间的相似性 ?n怎样构造聚类的具体方法以达到分类的目的?如果想要对如果想要对100100个学生进行分类，个学

4、生进行分类，而仅知道他们的数学成绩，则只好而仅知道他们的数学成绩，则只好按照数学成绩分类；这些成绩在直按照数学成绩分类；这些成绩在直线上形成线上形成100100个点。这样就可以把个点。这样就可以把接近的点放到一类。接近的点放到一类。如果还知道他们的物理成绩，这样如果还知道他们的物理成绩，这样数学和物理成绩就形成二维平面上数学和物理成绩就形成二维平面上的的100100个点，也可以按照距离远近个点，也可以按照距离远近来分类。来分类。三维或者更高维的情况也是类似；三维或者更高维的情况也是类似；只不过三维以上的图形无法直观地只不过三维以上的图形无法直观地画出来而已。画出来而已。 按照远近程度来聚类需要

5、明确两按照远近程度来聚类需要明确两个概念：一个是个概念：一个是点和点之间点和点之间的距的距离，一个是离，一个是类和类之间类和类之间的距离。的距离。点间距离点间距离有很多定义方式。最简有很多定义方式。最简单的是歐氏距离。单的是歐氏距离。当然还有一些和距离相反但起同当然还有一些和距离相反但起同样作用的概念，比如相似性等，样作用的概念，比如相似性等，两点越相似度越大，就相当于距两点越相似度越大，就相当于距离越短。离越短。由一个点组成的类是最基本的类；如由一个点组成的类是最基本的类；如果每一类都由一个点组成，那么点间果每一类都由一个点组成，那么点间的距离就是类间距离。但是如果某一的距离就是类间距离。但

6、是如果某一类包含不止一个点，那么就要确定类类包含不止一个点，那么就要确定类间距离，间距离，类间距离类间距离是基于点间距离定义的：比是基于点间距离定义的：比如如两类之间最近点之间的距离两类之间最近点之间的距离可以作可以作为这两类之间的距离，也可以用为这两类之间的距离，也可以用两类两类中最远点之间的距离中最远点之间的距离或各类的中心之或各类的中心之间的距离来作为类间距离。间的距离来作为类间距离。距离距离：测度样品之间的亲疏程度。将每一个样品看作p 维空间的一个点，并用某种度量测量点与点之间的距离，距离较近的归为一类，距离较远的点应属于不同的类。相似系数相似系数：测度变量之间的亲疏程度距离距离和相似

7、系数和相似系数kplkjlilijxxd11)|(pljlilijxxd1明氏距离明氏距离特别地，当k1时，即为绝对值距离绝对值距离(1) (1) 明氏距离（明氏距离（Minkowski）ixjxijd令表示样品与的距离 npnnppxxxxxxxxx212222111211设原始数据为kplkjlilijxxd11)|(pljlilijxxd12)(明氏距离明氏距离当k2时，即为欧氏距离欧氏距离当k时，即为切比雪夫距离切比雪夫距离jlilplijxxd1max123452018104471055325.236.328.911.5171x2x3x3124224)(lllxxd222)5 .11

8、3 .36()510()418(欧氏距离欧氏距离切比雪夫距离切比雪夫距离lllxxd423124max8 .245 .113 .3624d计算 明氏距离的数值与指标的量纲量纲有关。当各变量的测量值相差悬殊时，常发生“大数吃小数”的现象，为消除量纲的影响，通常先将每个变量进行标准化。 明氏距离的定义没有考虑各个变量之间相关性的影响。年龄收入家庭人口数甲3030001乙4032003222) 31 ()32003000()4030(d 当xi0时(i=1,2,n; k= 1,2, p)，第i个样品Xi和Xj之间的兰氏距离表示为( )1,1,2,., ;1,2,.,pikjkijkikjkxxdLi

9、njnxx=-=+ 兰氏距离与各变量的单位无关，对大的异常值不敏感，故适用于高度偏斜的数据马氏距离马氏距离 由印度著名统计学家马哈拉诺比斯(Mahalanobis)所定义的一种距离，其计算公式为： ijd21221112211,pjpijijipjpijijixxxxxxSxxxxxx =211jijixxSxxn马氏距离又称为广义欧氏距离。n马氏距离考虑了观测变量之间的相关性。如果假定各变量之间相互独立，即观测变量的协方差矩阵是对角矩阵，此时马氏距离就是标准化的欧氏距离。n马氏距离不受指标量纲量纲及指标间指标间相关性相关性的影响 夹角余弦()11 222111,1,2,., ;1,2,.,n

10、kikjkijnnkikjkkx xCip jpxx=轾骣骣鼢珑犏鼢珑鼢犏珑鼢桫桫臌邋相关系数( )()()()()122112,1,2,. ;1,2,.nkiikjiknnkiikjjkkxxxxCin jnxxxx=-=轾轾犏犏-犏犏臌臌邋1111,1,2,., ;1,2,.,nnikijkjkkxxxxin jnnn=邋由相似系数还可定义变量之间的距离11,2,., ;1,2,.,ijijdCin jn=-=间隔尺度变量 变量用连续的量来表示，如长度、重量、速度、流量有序尺度变量 变量度量时不用明确的数量表示，而是用等级来表示，如产品的等级，交通的拥堵程度等。名义尺度变量 变量用一些类表

11、示，这些类之间既无等级关系，也无数量关系，如性别，车型等。系统聚类法的基本思想系统聚类法的基本思想 先将n个样品各自看成一类，然后规定样品之间的“距离”和类与类之间的距离。选择距离最近距离最近的两类合并成一个新类，计算新类和其它类（各当前类）的距离，再将距离最近的两类合并。这样，每次合并减少一类，直至所有的样品都归成一类为直至所有的样品都归成一类为止止。 最终形成一个亲疏关系图谱（聚类树形图或谱系图），通常从图上可清洗地看出应分为几类以及每一类中所包含的样品（或变量）。除此之外也可借助统计量确定分类结果在聚类分析中，通常用G表示类，将定G中有m个元素（即样品或变量），不失一般化，用列向量xi（

12、i = 1，2，m）来表示，dij表示元素xi与xj之间的距离。DKL表示类GK与GL之间的距离。类与类之间用不同的方法定义距离，产生了以下不同的系统聚类方法1. 最短距离法2. 最长距离法3. 中间距离法4. 重心法5. 类平均法 6.6. 离差平方和法（离差平方和法（WardWard法法）系统聚类方法：系统聚类方法： 上述 6 种方法归类的基本步骤一致基本步骤一致，只是类与类之间的距离类与类之间的距离有不同的定义。定义类p与q之间的距离为两类最近样品的距离，即 ,minpqijip j qDd挝=xq1xp2xq2xp1pqDxq3最短距离法最短距离法min,krprqrDDD=设类p与

13、q合并成一个新类，记为k，则k与任一类r 的距离是pqkr定义类与类之间的距离为两类最近样品间的距离，即min:,KLijiKjKDdxGxG=挝若某一步类GK与类GL聚成一个新类，记为GM，类GM与任意已有的类GJ之间的距离为min,MJKJLJDDDJK L=聚类步骤如下将初始的每个样品（或变量）各自作为一类，并规定样品（或变量）之间的距离，通常采用欧式距离。计算n个样品（或p个变量）的距离矩阵D(0)，它是一个对称矩阵。寻找D(0)中最小元素，设为DKL，将GK和GL聚成一个新类，记为GM，即GM=GK，GL计算新类GM与任一类GJ之间距离的递推公式为,minminmin,minmin,

14、iMjJikjJiLjJMJijijijKJLJxGxGxGxGxGxGDdddDD挝挝挝=对距离矩阵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)，如下

15、表所示G1G1G2G2G3G3G4G4G5G5G10G210G3540G47620G5109530D(0)中最小元素是D12=1，于是将G1和G2合并成G6，得到距离矩阵D(1)G6G6G3G3G4G4G5G5G60G340G4620G59530D(1)中最小元素是D34=2，于是将G3和G4合并成G7，得到距离矩阵D(2)G6G6G7G7G5G5G60G740G5930D(2)中最小元素是D57=3，于是将G5和G7合并成G8，得到距离矩阵D(3)G6G6G8G8G60G840最后将G6和G8合并成G9，这是所有五个样品聚为一类，聚类结束。例例 最短距离法最短距离法 设抽取5个样品，每个样品

16、观察2个指标 ， ：某路段上年均交通事故发生数 ：某路段上年均因交通事故受伤人数1x2x12345201810447105531x2x 3.6 10.2 16.12 16.49 9.43 14.87 15.65 6 6.32 2ijdnnijdD)(1.计算5个样品两两之间的距离记为距离矩阵（采用欧氏距离），452D=为最小，2. 合并距离最小的两类为新类，按顺序定为第类。5 , 4624252min,min 14.87,15.6514.87Ddd=634353min,6Ddd=614151min,min 16.12,16.4916.12Ddd=3、计算新类与各当前类的距离，得距离矩阵如下：3

17、.6 10.2 16.12 9.43 14.87 6731323min,9.43Ddd=761626min,14.87Ddd=6 . 312d 2 , 1为最小， = 6 9 .43 14.87 4、重复步骤2、3，合并距离最近的两类为新类，直到所有的类并为一类为止。 43. 9,min673787ddd 636d6 , 3为最小，=5、6、按聚类的过程画聚类谱系图 45并类距离3127、决定类的个数与类。 观察此图，我们可以把5个样品分为3类， 2 , 1 35 , 4、。43. 966 . 328 ,76, 32, 15 , 4ddddx11x2112d二、最长距离法二、最长距离法定义类p

18、与q之间的距离为两类最远样品的距离，即 ijqjpipqdd,max设类p与 q合并成一个新类，记为k，则k与任一类r 的距离是pqkrqrprkrddd,max 3.6 10.2 16.12 16.49 9.43 14.87 15.65 6 6.32 2ijdnnijdD)(1.计算5个样品两两之间的距离记为距离矩阵（采用欧氏距离），为最小，245d2. 合并距离最小的两类为新类，按顺序定为第类。5 , 4例例 最长距离法最长距离法 65.1565.15,87.14max,max524262ddd32. 6,max534363ddd49.1649.16,12.16max,max514161d

19、dd3、计算新类与各当前类的距离，得距离矩阵如下：3.6 10.2 16.49 9.43 15.65 6.322 .10,max231373ddd49.16,max261676ddd6 . 312d 2 , 1为最小， = 6.32 10 .2 16.494、重复步骤2、3，合并距离最近的两类为新类，直到所有的类并为一类为止。 49.16,max673787ddd 32. 636d6 , 3为最小，=5、6、按聚类的过程画聚类谱系图 45并类距离3127、决定类的个数与类。 观察此图，我们可以把5个样品分为3类， 2 , 1 35 , 4、。49.1632. 66 . 328 ,76, 32,

20、 15 , 4dddd三、中间距离法三、中间距离法定义类与类之间的距离既不采用两类之间最近的距离，也不采用两类之间最远的距离，而是采用介于两者之间的距离，故称为中间距离法。 krdr rp pq qk k2222412121pqqrprkrdddd 13 104 260 272 89 221 245 36 40 4ijdnnijdD)(1.计算5个样品两两之间的距离记为距离矩阵（采用欧氏距离），为最小，4245d2. 合并距离最小的两类为新类，按顺序定为第类。5 , 4例例 中间距离法中间距离法 2ijd3、计算新类与各当前类的距离，得距离矩阵如下： 13 104 265 89 232 372

21、654412722126021412121245251241261dddd2324412452122121412121245252242262dddd3744140213621412121245253243263dddd2ijd13212d 2 , 1为最小， = 37 93.25 245.25 4、重复步骤2、3，合并距离最近的两类为新类，直到所有的类并为一类为止。 37236d6 , 3为最小，=5、25.931341892110421412121212223213273dddd25.24513412322126521412121212226216276dddd2ijd160374125.

22、2452125.9321412121236267237287dddd6、按聚类的过程画聚类谱系图 45并类距离3127、决定类的个数与类。 观察此图，我们可以把5个样品分为3类， 2 , 1 35 , 4、。65.1208. 66 . 328 ,76, 32, 15 , 4dddd四、重心法四、重心法（Centroid)11,x y22,xypx和qxqpxxpqdd类与类之间的距离就考虑用重心之间的距离表示。设p与q的重心分别是，则类p和q的距离为qpknnnqqppkkxnxnnx1rkrkkrxxxxd22222pqkqkpqrkqprkpkrdnnnndnndnnd将p和q合并为k，则

23、k类的样品个数为它的重心是rx某一类 r 的重心是，它与新类k的距离是经推导可以得到如下递推公式：pnqn设聚类到某一步，类p与 q分别有样品 、个， 13 104 260 272 89 221 245 36 40 4ijdnnijdD)(1.计算5个样品两两之间的距离记为距离矩阵（采用欧氏距离），为最小，4245d2. 合并距离最小的两类为新类，按顺序定为第类。5 , 4例例 重心法重心法 2ijd3、计算新类与各当前类的距离，得距离矩阵如下： 13 104 265 89 232 372654412722126021412121245251241261dddd2324412452122121

24、412121245252242262dddd3744140213621412121245253243263dddd2ijd13212d 2 , 1为最小， = 37 93.25 245.25 4、重复步骤2、3，合并距离最近的两类为新类，直到所有的类并为一类为止。 37236d6 , 3为最小，=5、25.931341892110421412121212223213273dddd25.24513412322126521412121212226216276dddd2ijd36.186379225.2453225.9331923231236267237287dddd6、按聚类的过程画聚类谱系图 4

25、5并类距离3127、决定类的个数与类。 观察此图，我们可以把5个样品分为3类， 2 , 1 35 , 4、。65.1308. 66 . 328 ,76, 32, 15 , 4dddd五、类平均法五、类平均法（Average)定义两类之间的距离平方为这两类元素两两之间距离平方的平均 piqjijqppqdnnd221p pq qqpknnn将p和q合并为k，则k类的样品个数为pnqn设聚类到某一步，类p与 q分别有样品、个，rikjijrkkrdnnd221ripjriqjijijrkddnn221)(122qrrqprrprkdnndnnnnk类与任一类 r 的距离为22qrkqprkpdnn

26、dnn 13 104 260 272 89 221 245 36 40 4ijdnnijdD)(1.计算5个样品两两之间的距离记为距离矩阵（采用欧氏距离），为最小，4245d2. 合并距离最小的两类为新类，按顺序定为第类。5 , 4例例 类平均法类平均法 2ijd3、计算新类与各当前类的距离，得距离矩阵如下： 13 104 266 89 233 3826627221260212121251241261ddd23324521221212121252242262ddd38402136212121253243263ddd2ijd13212d 2 , 1为最小， = 38 96.5 249.5 4、重

27、复步骤2、3，合并距离最近的两类为新类，直到所有的类并为一类为止。 38236d6 , 3为最小，=5、5 .968921104212121223213273ddd5 .24923221265212121226216276ddd2ijd5 .19825.2453225.93313231267237287ddd6、按聚类的过程画聚类谱系图 45并类距离3127、决定类的个数与类。 观察此图，我们可以把5个样品分为3类， 2 , 1 35 , 4、。09.1416. 66 . 328 ,76, 32, 15 , 4dddd系统聚类法的不同之处在于类间距离的计算方法不同，Wishart将不同的距离计

28、算公式统一为222222MJKKJLLJKLKJLJDDDDDDaabg=+同样的观测数据，应用不同的聚类方法进行聚类，可能得到不同的结果。通常从两个方面进行评价 单调性 空间的浓缩与扩张单调性 令Di是系统聚类过程中第i次并类时的距离，若有D1D2 Di，则成次系统聚类法具有单调性。在上述聚类方法中，最短距离法、最长距离法、中间距离法、类平均法和离散平方和法具有单调性，而中间距离法和重心法不具有单调性。空间的浓缩与扩张针对同一问题，用不同系统聚类法进行聚类，做出的聚类树形图的横坐标（并类距离）的范围相差很大。范围小的方法区别类的灵敏度差，而范围太大的方法灵敏度又过高设有甲、乙两类聚类方法，第

29、i步的距离矩阵分别为Ai和Bi，若AiBi，则称甲方法比乙方法更使空间扩张，或称乙方法比甲方法更使空间浓缩。与类平均法相比，最短距离法和重心法使空间浓缩，最长距离法和离差平方和法是空间扩张。太浓缩的方法不够灵敏，太扩张的方法又容易失真，而类平均法相对比较适中。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), ,

30、(n, n-1)Y = pdist（X, metric）输入参数metric指定计算距离的方法，metric为字符串，可用的字符串如下表所示。MetricMetric参数值参数值说明说明euclidean欧式距离seuclidean标准化欧式距离mahalanobis马哈拉诺比斯距离cityblock绝对值距离minkowski闵可夫斯基距离chebychev切比雪夫距离Y = pdist（X, minkowski, p）计算样品对的闵可夫斯基距离，输入参数p为闵可夫斯基距离计算中的指数，默认情况下，指数为2SquareformZ = squareform(y)Z = squareform(y

31、, 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次并类的两个类的类编号，初始类编号为1n，以后每

32、形成一个新类，类编号从n+1开始逐次增加1.Z矩阵的第i行中的第3个元素为第i次并类是的并类距离Z = linkage（y, method）利用method参数制定的方法创建系统聚类树，method是字符串，可用的字符串如下所示MethodMethod参数值参数值说明说明average类平均法centroid重心法complete最长距离法median中间距离法single最短距离法ward离差平方和法weighted可变类平均法Z = linkage（y, method, metric）metric用来制定计算距离的方法Dendrogram函数H = dendrogram（Z）由系统聚类树矩

33、阵Z生成系统聚类树形图。输入参数Z是由linkage函数输出的系统聚类树矩阵。输出参数H是树形图中线条的句柄值向量，用来控制线条属性。H = dendrogram（Z， p）生成一个树形图，通过输入参数p来控制显示的叶节点数。H = dendrogram（, orientation, orient）通过设定orientation参数及参数值orient来控制聚类树形图的方向和放着叶节点标签的位置，可用参数如下所示参数值参数值说明说明top从上至下，叶节点标签在下方，为默认情况bottom从下至上，叶节点标签在上方left从左至右，叶节点标签在右边right从右至左，叶节点标签在左边H = dendrogram（, labels, S）通过一个字符串数组或字符串元胞数组设定每一个观测值的标签。当树形图中显示了全部的叶节点时，叶节点的标签记为相应观测的标签；当树形图中忽略了某些节点时，只包含单个观测的叶节点的