第九章 聚类分析和判别分析 讲过

第九章聚类分析与判别分析在实际工作中，我们经常遇到分类问题.若事先已经建立类别，则使用判别分析，若事先没有建立类别，则使用聚类分析.聚类分析主要是研究在事先没有分类的情况下，如何将样本归类的方法.聚类分析的内容包含十分广泛，有系统聚类法、动态聚类法、分裂法、最优分割法、模糊聚类法、图论聚类法、聚类预报等多种方法.聚类分析指将物理或抽象对象的集合分组成为由类似的对象组成的多个类的分析过程。它是一种重要的人类行为。聚类分析的目标就是在相似的基础上收集数据来分类。聚类源于很多领域，包括数学，计算机科学，统计学，生物学和经济学。在不同的应用领域，很多聚类技术都得到了发展，这技术方法被用作描述数据，衡量不同数据源间的相似性，以及把数据源分类到不同的簇中。聚类与分类的不同在于，聚类所要求划分的类是未知的。聚类是将数据分类到不同的类或者簇这样的一个过程,所以同一个簇中的对象有很大的相似性，而不同簇间的对象有很大的相异性。从统计学的观点看，聚类分析是通过数据建模简化数据的一种方法。§9.1聚类分析基本知识介绍在MATLAB软件包中，主要使用的是系统聚类法.系统聚类法是聚类分析中应用最为广泛的一种方法.它的基本原理是：首先将一定数量的样品(或指标)各自看成一类，然后根据样品(或指标)的亲疏程度，将亲疏程度最高的两类合并，然后重复进行，直到所有的样品都合成一类.衡量亲疏程度的指标有两类：距离、相似系数.一、常用距离欧氏距离假设有两个n维样本x=(x,x,…,x)和x=(x,x,…,x)，则它们的欧氏距离为111121n221222nd(x,x)=£(x一x)2121j2j'j=1标准化欧氏距离假设有两个n维样本x=(x,x,…,x)和x=(x,x,…,x)，则它们的标准化欧氏距离为111121n221222nsd(x,x)=(x-x)D-i(x-x)t

12^1212其中：D表示n个样本的方差矩阵，D=diagonal(o2Q2,...q2)，q2表示第j列的方差.12nj马氏距离假设共有n个指标，第i个指标共测得m个数据(要求m>n)：x'xx…x'i11121n1xxx…xx=i2•，X=(x,x,•…，x)=12■21■n2・•i•12n■■■■・•・•<x丿im；x1mx2m…x丿nn

于是，我们得到mxn阶的数据矩阵X二(x,x,…,x)，每一行是一个样本数据.mxn阶数据矩阵X12n的nxn阶协方差矩阵记做Cov(X).两个n维样本x二(x,x,…,x)和x二(x,x,…,x)的马氏距离如下：111121n221222nmahal(x,x)=、(x-x)(Cov(X))-i(x-x)t121212马氏距离考虑了各个指标量纲的标准化，是对其它几种距离的改进.马氏距离不仅排除了量纲的影响，而且合理考虑了指标的相关性.布洛克距离两个n维样本x=(x,x,…,x)和x=(x,x,…,x)的布洛克距离如下：111121n221222nb(x,x)=£Ix-xI121j2jj=1闵可夫斯基距离2nm(x,x)=12两个n维样本x1=(xn，%…)和x2=(x21,x222nm(x,x)=122jYIx-x1jj=12j注：p=1时是布洛克距离；p=2时是欧氏距离.余弦距离d(x,d(x,x)=12xxT12这是受相似性几何原理启发而产生的一种标准相似距离1-jt一JxxTJxxT11'22在识别图像和文字时，常用夹角余弦为标准.本点之间距离的内部函数为本点之间距离的内部函数为y=pdist(x)y=pdist(x,'seuclid')y=pdist(x,'mahal')y=pdist(x,'cityblock')y=pdist(x,'minkowski')y=pdist(x,'minkowski',p)d(x,x)=1-—12(x-x)(x-x)T(x-x)(x-x)TN1111^2222二、MATLAB中常用的计算距离的函数假设我们有mxn阶数据矩阵x=(%x2‘…，叮，每一行是一个样本数据•在MATLAB中计算样计算样本点之间的欧氏距离计算样本点之间的标准化欧氏距离计算样本点之间的马氏距离计算样本点之间的布洛克距离计算样本点之间的闵可夫斯基距离计算样本点之间的参数为p的闵可夫斯基距离y=pdist(x,'cosine')计算样本点之间的余弦距离y=pdist(x,'correlation')计算样本点之间的相似距离另外，内部函数yy=squareform(y)表示将样本点之间的距离用矩阵的形式输出.三、常用的聚类方法常用的聚类方法主要有以下几种：最短距离法、最长距离法、中间距离法、重心法、平方和递增法四、创建系统聚类树假设已经得到样本点之间的距离y,可以用linkage函数创建系统聚类树，格式为z=linkage(y).其中：z为一个包含聚类树信息的(m-1)3的矩阵•例如：z=2.0005.0000.23.0004.0001.28则z的第一行表示第2、第5样本点连接为一个类，它们距离为0.2；则z的第二行表示第3、第4样本点连接为一个类，它们距离为1.28.在MATLAB中创建系统聚类树的函数为z=linkage(y)表示用最短距离法创建系统聚类树z=linkage(y,'complete')表示用最长距离法创建系统聚类树z=linkage(y,'average')表示用平均距离法创建系统聚类树z=linkage(y,'centroid')表示用重心距离法创建系统聚类树z=linkage(y,'ward')表示用平方和递增法创建系统聚类树§9.2聚类分析示例例1在MATLAB中写一个名为opt」inkage_l的M文件：x=[31.7;11;23;22.5;1.21;1.11.5;31];y=pdist(x,'mahal');yy=squareform(y)%Reformatadistancematrixbetweenuppertriangularandsquareformz=linkage(y,'centroid')h二dendrogram(z)%Plotdendrogramgraphs画树状图存盘后按F5键执行，得到结果如下：yy=02.38792.19831.69462.16842.22840.88952.387902.60972.06160.23780.62552.37782.19832.609700.63532.55222.01532.98901.69462.06160.635301.97501.51062.41722.16840.23782.55221.975000.66662.14002.22840.62552.01531.51060.666602.45170.88952.37782.98902.41722.14002.45170z=2.00005.00000.23786.00008.00000.63533.00004.00000.6353

1.00007.00001.00007.00000.88959.000010.00002.106311.000012.00002.0117按重心距离法得到的系统聚类树为其中：h=dendrogram(z)表示输出聚类树形图的冰状图.一、根据系统聚类树创建聚类假设已经求出系统聚类树z,我们根据z来创建聚类，使用cluster函数.例2在MATLAB中写一个名为opt_cluster_l的M文件：x=[31.7;11;23;22.5;1.21;1.11.5;31];y=pdist(x,'mahal');yy二squareform(y)z=linkage(y,'centroid')h=dendrogram(z)t=cluster(z,3)其中：“t=cluster(z,3)”表示分成3个聚类，需要分成几个由人工选择.存盘后按F5键执行，得到结果如下：t二3122113即第1、第7样本点为第3类，第2、第5、第6样本点为第1类，第3、第4样本点为第2类.二、根据原始数据创建分类在MATLAB软件包中，内部函数clusterdata对原始数据创建分类，格式有两种：clusterdata(x,a)，其中Ovavl,表示在系统聚类树中距离小于a的样本点归结为一类；clusterdata(x,b)，其中b>1是整数，表示将原始数据x分为b类.例3在MATLAB中写一个名为opt_clusterdata_l的M文件：x=[31.7;11;23;22.5;1.21;1.11.5;31];t=clusterdata(x,0.5)z=clusterdata(x,3)存盘后按F5键执行，得到结果如下：t=4322314z=23l1332其中：t的结果表示距离小于0.5的样本点归结为一类，这样，共有四类，第1类：样本点6；第2类:样本点3、4；第3类：样本点2、5；第4类：样本点1、7.而z的结果表示首先约定将原始数据x分为3类，然后计算，结果如下：第1类：样本点3、4；第2类：样本点1、7；第3类：样本点2、5、6.利用内部函数clusterdata对原始数据创建分类，其缺点是不能更改距离的计算法.比较好的方法是分步聚类法.三、分步聚类法假设有样本数据矩阵x,第一步对于不同的距离，利用pdist函数计算样本点之间的距离：y1=pdist(x)y2=pdist(x,'seuclid')y3=pdist(x,'mahal')y4=pdist(x,'cityblock')第二步计算系统聚类树以及相关信息：z1=linkage(y1)z2=linkage(y2)z3=linkage(y3)z4=linkage(y4)第三步利用cophenet函数计算聚类树信息与原始数据的距离之间的相关性，这个值越大越好：％cophenetCopheneticcorrelationcoefficient同表象相关系数，同型相关系数，共性分类相关系数CPCCt1=cophenet(z1,y1)t2=cophenet(z2,y2)t3=cophenet(z3,y3)t4=cophenet(z4,y4)注：Z在前，y在后，顺序不能颠倒.第四步选择具有最大的cophenet值的距离进行分类.利用函数clusterdata(x,a)对数据x进行分类，其中Ovavl,表示在系统聚类树中距离小于a的样本点归结为一类.例4在MATLAB中写一个名为opt_cluster_2的M文件：x=[31.7;11;23;22.5;1.21;1.11.5;31];y1=pdist(x);y2=pdist(x,'seuclid');y3=pdist(x,'mahal');y4=pdist(x,'cityblock');Z1=linkage(y1);Z2=linkage(y2);Z3=linkage(y3);Z4=linkage(y4);t1=cophenet(Z1,y1)t2=cophenet(Z2,y2)t3=cophenet(Z3,y3)t4=cophenet(Z4,y4)存盘后按F5键执行，得到结果如下：tl=O.929lt2=O.9238t3=O.9l9lt4=O.9242结果中tl=O.929l最大，可见此例利用欧式距离最合适.于是，在MATLAB中另写一个名为opt_cluster_3的M文件：x=[31.7;11;23;22.5;1.21;1.11.5;31];y1=pdist(x);Z1=linkage(y1)存盘后按F5键执行，得到结果如下：zl=2.00005.00000.20003.00004.00000.50006.00008.00000.50991.00007.00000.70009.000011.00001.280610.000012.00001.345矩阵z1的第1行表示样本点2、5为一类，在系统聚类树上的距离为0.2，其它类推.考察矩阵z1的第3列，系统聚类树上的6个距离，可以选择0.5作为聚类分界值.在MATLAB中另写一个名为opt_cluster_4的M文件：x=[31.7;11;23;22.5;1.21;1.11.5;31];y1=pdist(x);z1=linkage(y1)b1=cluster(z1,0.5)存盘后按F5键执行，得到结果如下：b1=4322314结果表示将原始数据x分为4类，第1类：样本点6；第2类：样本点3、4；第3类：样本点2、5；第4类：样本点1、7.主要应用商业聚类分析被用来发现不同的客户群，并且通过购买模式刻画不同的客户群的特征。聚类分析是细分市场的有效工具，同时也可用于研究消费者行为，寻找新的潜在市场、选择实验的市场,并作为多元分析的预处理。生物聚类分析被用来动植物分类和对基因进行分类，获取对种群固有结构的认识地理聚类能够帮助在地球中被观察的数据库商趋于的相似性保险行业聚类分析通过一个高的平均消费来鉴定汽车保险单持有者的分组，同时根据住宅类型，价值，地理位置来鉴定一个城市的房产分组因特网聚类分析被用来在网上进行文档归类来修复信息电子商务聚类分析在电子商务中网站建设数据挖掘中也是很重要的一个方面,通过分组聚类出具有相似浏览行为的客户，并分析客户的共同特征，可以更好的帮助电子商务的用户了解自己的客户，向客户提供更合适的服务。例5下表是1999年中国省、自治区的城市规模结构特征的一些数据，可通过聚类分析将这些省、自治区进行分类，具体过程如下：省、自治区首位城市规模(万人)城市首位度四城市指数基尼系数城市规模中位值(万人)京津冀699.701.43710.93640.780410.880山西179.461.89821.00060.587011.780内蒙古111.131.41800.67720.515817.775辽宁389.601.91820.85410.576226.320吉林211.341.78801.07980.456919.705黑龙江259.002.30590.34170.507623.480苏沪923.193.73502.05720.620822.160浙江139.291.87120.88580.453612.670安徽102.781.23330.53260.379827.375福建108.501.72910.93250.468711.120江西129.203.24541.19350.451917.080山东173.351.00180.42960.450321.215河南151.541.49270.67750.473813.940湖北434.467.13282.44130.528219.190湖南139.292.35010.83600.489014.250广东336.543.54071.38630.402022.195广西96.121.22880.63820.500014.340海南45.432.19150.86480.41368.730川渝365.011.68011.14860.572018.615云南146.006.63332.37850.535912.250贵州136.222.82791.29180.598410.470西藏11.794.15141.17980.61187.315陕西244.045.11941.96820.628717.800甘肃145.494.75151.93660.580611.650青海61.368.26950.85980.80987.420宁夏47.601.50780.95870.48439.730新疆128.673.85351.62160.490114.470x=load(‘data.txt');y1=pdist(x);y2=pdist(x,'seuclid');y3=pdist(x,'mahal');y4=pdist(x,'cityblock');z1=linkage(y1);z2=linkage(y2);z3=linkage(y3);z4=linkage(y4);t1=cophenet(z1,y1);t2=cophenet(z2,y2);t3=cophenet(z3,y3);t4=cophenet(z4,y4);A=[t1t2t3t4];m=max(A);ift1==my1=pdist(x);z1=linkage(y1)elseift2==my2=pdist(x);z2=linkage(y2)elseift3==my3=pdist(x);z3=linkage(y3)else

y4=pdist(x);y4=pdist(x);z4=linkage(y4)end§9.3判别分析基本知识介绍一、协方差矩阵设(£，耳)是一个二维随机变量，又1E(g-Eg)(耳-)lv+s，则称E(g-Eg)(H-)为g与耳的协方差，记作Cov点,n).例如，在MATLAB软件包中写一个名为opt_cov_1的M文件:x=[123];y=[321];cov(x,y)存盘后按F5键执行，得到结果如下：ans=1-1-11设(gi，今…,g设(gi，今…,gn)是n维随机变量,定义c=E(g-Eg)(g-Eg)，则称ijcc…c1112cc•…c2122••••••••••<1n2i2nnn丿ij、1n为(g,g，…,g)的协方差矩阵.12n如果要进行相关系数分析，则在MATLAB软件包中写一个名为opt_corrcoef_1的M文件:x=[123];y=[321];corrcoef(x,y)存盘后按F5键执行，得到结果如下：ans1-1-11注：两个随机变量的相关系数r(x,y)满足-1<r(x,y)<1.注：二、基本数学原理二、基本数学原理判别分析是利用原有的分类信息，得到判别函数(判别函数是这种分类的函数关系式，一般是与分类相关的若干个指标的线性关系式)，然后利用该函数去判断未知样品属于哪一类.因此这是一个学习和预测的过程.常用的判别分析法有距离判别法、费歇尔判别法、贝叶斯判别法等.1）距离判别法距离判别法有欧式距离法和马氏距离法等.其中，欧式距离法比较粗糙，MATLAB软件包中采用的是马氏距离法.个样本数据.mxn阶数据矩假设共有n个指标，第i个指标共测得m个数据（要求个样本数据.mxn阶数据矩(、xi1xx=ii2■••<x丿im于是，我们得到mXn阶的数据矩阵X=（X1,x2,…，xn），每一行是阵X的nxn阶协方差矩阵记做Cov（X）.a）求n维向量r=（r,r，…，r）到mxn矩阵X的马氏距离.12n定义r-X=（r-x,r-x，…,r-x），则n维向量r=（r,r，…，r）到mxn矩阵X的马氏距离1122nn12n的公式如下：mahal(r,X)=(r-X)Cov(X)-1(r-X)t其中：x表示第i个指标X的算术平均值.iib)矩阵X到自身的马氏距离，相当于矩阵X的每一行到X的马氏距离，记做mahal(X,X).做这种运算可以求出矩阵X的.注：马氏距离法没有考虑样本指标值的分布.例1有8x3数据矩阵如下：X二[0.0520.0840.021;0.0370.00710.022;0.0410.0550.11;0.110.0210.0073;0.0300.1120.072;0.160.0560.021;0.0740.0830.105;0.190.021]在MATALB软件包中输入以下程序：X=[0.0520.0840.021;0.0370.00710.022;0.0410.0550.11;0.110.0210.0073;0.0300.1120.072;0.160.0560.021;0.0740.0830.105;0.190.021];d=mahal(X,X)执行后得到结果：d=0.69983.90500.83101.88192.76724.24240.59916.0735可见，矩阵X中第二行、第五行、第六行、第八行数据异常.2）费歇尔判别法该法是以费歇尔准则为标准来评选判别函数的.所谓费歇尔判别法，指的是较优的判别函数应该能根据待判对象的n个指标最大程度地将它所属的类与其它类区分开来•一般采用线性函数作为判别函数.基本方法是：首先假定一个线性的判别函数，然后根据已知信息对判别函数进行训练，得到函数关系式的系数，从而最终确定判别函数.该法有时会使误判次数增加，但由于使用的是线性函数，所以使用起来也比较方便.3）贝叶斯判别法贝叶斯判别法是一种概率方法，它的好处是可以充分利用先验信息，可以考虑专家的意见.应用此方法，需要事先假定样本指标值的分布（例如，多元正态分布等）.在MATLAB软件包中，将已经分类的m个数据（长度为n）作为行向量，得到一个矩阵training，每行都属于一个分类类别，分类类别构成一个整数列向量g（共有m行），待分类的k个数据（长度为n）作为行向量，得到一个矩阵sample，然后利用classify函数进行线性判别分析（默认）•它的格式为classify（sample,training,group）其中：sample与training必须具有相同的列数；group与training必须具有相同的行数；group是一个整数向量.MATLAB内部函数classify的功能是将sample的每一行进行判别，分到training指定的类中•进一步，较复杂的格式为[class,err]=classify（sample,training,group,type）其中：class返回分类表；err返回误差比例信息；sample是样本数据矩阵；training是已有的分类数据矩阵；group是分类列向量；type有3种选择：1）type=linear（默认设置）：表示进行线性判别分析；2）type二quadratic：表示进行二次判别分析；3）type二mahalanobis:表示用马氏距离进行判别分析.§9.4判别分析示例例1某地大气样品污染分类表如下：在MATLAB中写一个名为opt」inkagel的M文件:气体氯硫化氢二氧化硫碳4环氧氯丙烷环己烷污染分类10.0560.0840.0310.0380.00810.022120.040.05220.0073130.050.0740.0410.0480.00710.02140.0450.0250.0063150.0380.130.0790.170.0580.043260.030.110.070.160.050.046270.0340.0950.0529180.030.090.0639190.0840.0660.0290.320.0120.