二聚类与判别

《二聚类与判别》由会员分享，可在线阅读，更多相关《二聚类与判别（10页珍藏版）》请在装配图网上搜索。

1、数学建模实验指导书刘 凤 秋哈理工应科院应用数学系2008年 9月实验二聚类与判别实验项目名称： 利用 Matlab 进行聚类和判别分析实验项目性质： 普通实验所属课程名称： 数学建模实验参考资料：实验计划学时： 4一、实验目的：1、利用 MATLAB 进行聚类分析和判别分析；2、通过实际例题学习用聚类和判别分析解决相关简单的实际问题；3、理解判别分析误判率含义，应用判别模型进行预测。二、实验内容2.1聚类分析1、工厂产品问题（教材220 页例题 9.3 ）；2、工人身高体重问题（教材 239 页习题 9.1 ）；2.2判别分析1、 雨天非雨天问题（教材231 页例 9.5 ）；2、 蠓的分类

2、（教材 234 页）；三、实验方法、步骤及结果分析简要提示3.1 基础知识一、聚类在 MATLAB中通过 pdist 、 linkage、 dendrogram 、 cluster等函数来完成此种方法。层次聚类的过程如下：1、 相似性度量确定对象（实际上就是数据集中的每个数据点）之间的相似性，实际上就是定义一个表征对象之间差异的距离，例如最简单的平面上点的聚类中，最经常使用的就是欧几里得距离。使用pdist来实现，具体用法如下:Y = pdist（ X， distance）根据距离distance来计算X 中各点之间的距离Y。其中X 为数据集，distance可以取为欧氏距离，马氏距离，切比雪

3、夫距离。对于具有M个点的数据集X，pdist之后的 Y 将是具有M*(M-1)/2个元素的行向量。例 1-1 ： Y=pdist （X）举例。 X=randn(6,2)X =-0.43261.1892-1.6656-0.03760.12530.32730.28770.1746-1.1465-0.18671.19090.7258plot(X(:,1),X(:,2),bo) %画出 X 的散点图（图1）图 1Y=pdist(X) %计算 X 的第一个点与与2-6 点、第 2 点与 3-6 点 ,.距离Y =Columns 1 through 151.73941.02671.24421.55011.

4、68831.82771.96480.54012.95680.22281.37171.13771.47901.05812.5092例子中 X 数据集可以看作包含6 个平面数据点， pdist之后的 Y 是一个行向量， 15 个元素分别代表 X的第 1点与 2-6 点、第2 点与 3-6点 ,.这样的距离。则Y 为具有 C62个元素的行向量。注：（ 1）Y 这样的显示虽然节省了内存空间，但对用户来说不是很易懂，如果需要对这些距离进行特定操作的话，也不太好索引。MATLAB中可以用 squareform 把 Y 转换成方阵形式，方阵中 位置的数值就是 X 中第 i和第 j 点之间的距离，显然这个方阵

5、应该是个对角元素为0的对称阵。 squareform(Y) ans =0 1.7394 1.0267 1.2442 1.5501 1.68831.73940 1.8277 1.9648 0.5401 2.95681.0267 1.82770 0.2228 1.3717 1.13771.24421.96480.222801.47901.05811.55010.54011.37171.479002.50921.68832.95681.13771.05812.50920注：（2）pdist可以使用多种参数，指定不同的距离算法。另外，当数据规模很大时，可以想象pdist产生的Y 占用内存将是很吓人的，

6、比如X 有10k 个数据点， 那么X 占 10k*8*2Bytes=160K，这看起来不算啥，但是pdist后的Y 会有10k*10k/2*8Bytes=400M。因此，使用MATLAB的层次聚类来处理大规模数据，大概是很不合适的。2、聚类树的产生确定好了对象间的差异度（距离）后，就可以用Z=linkage(Y)产生层次聚类树。 Z=linkage(Y)表示为 6+1 类，即第7 类Z =3.00004.00000.22282.00005.00000.54011.00007.00001.0267表示为 6+2 类，即第8 类6.00009.00001.05818.000010.00001.37

7、17对于 6 个元素的X， Y 是 1 行 6*(6-1)/2的行向量， Z 则是 (6-1)*3标列，最后一列是距离列。如上例中表示在产生聚类树的计算过程中，第的矩阵。3 和第Z 数组的前两列是索引下 4 点先聚成一类，他们之间的距离是0.2228，以此类推。要注意的是，为了标记每一个节点，需要给新产生的聚类也安排一个标识，MATLAB中会将新产生的聚类依次用6+1,6+2,.依次来标识。比如第3 和第4 点聚成的类以后就用7 来标识，第2 和第5 点聚成的类用8 来标识，依次类推。通过linkage函数计算之后，实际上二叉树式的聚类已经完成了。Z 这个数据数组不太好看，可以用dendrog

8、ram(Z)来可视化聚类树。dendrogram(Z)注：（ 3） dendrogram默认最多画30 个最底层节点，当然可是设置参数改变这个限制，比如dendrogram(Z,0)就会把所有数据点索引下标都标出来，但对于成千上万的数据集合，这样的结果必然是图形下方非常拥挤。3、聚类树的检验（ Verifying the Cluster Tree）*初步的聚类树画完后，还要做很多后期工作的，包括这样的聚类是不是可靠，是不是代表了实际的对象分化模式，对于具体的应用，应该怎样认识这个完全版的聚类树，产生具有较少分叉的可供决策参考的分类结果呢？这都是需要考虑的。MATLAB中提供了cluster,

9、clusterdata, cophenet, inconsistent等相关函数。cluster用于剪裁完全版的聚类树，产生具有一定cutoff的可用于参考的树。clusterdata可以认为是pdist,linkage,cluster的综合，当然更简易一点。cophenet 和 inconsistent用来计算某些系数，前者用于检验一定算法下产生的二叉聚类树和实际情况的相符程度（就是检测二叉聚类树中各元素间的距离和pdist计算产生的实际的距离之间有多大的相关性）， inconsistent则是量化某个层次的聚类上的节点间的差异性（可用于作为cluster的剪裁标准）。后面这些的理解，大概需

10、要对聚类有一个更深刻更数学的认识。在一个层次聚类树中，在原数据集中任何两个对象最终是某种程度上联结在一起。联结的高度代表了包含这两个对象两个组之间的距离。这个高度就是两个对象间的分类距离。对于由linkage函数产生的聚类树，一种衡量其优劣的方式就是比较由linkage和 pdist产生的距离。如果聚类有效，在分类树中，对象的联结与距离向量中的对象将会具有强关联性。Cophenet 函数比较了这些值所在的两个集合并且计算它们的相关性，返回值称为分类相关系数，此值越接近1，说明对数据聚类的结果越能精确。例如：图 4将 20 工厂的值赋给16 和 21 工厂的聚类结果根据图 4 可见，聚类结果为：

11、第一次计算两个样品的最小距离是1，所以把距离为1 的点合成一类：17， 18， 19， 12，13， 5， 6， 11， 7， 8，9， 1， 2第二次计算两个类间的最短距离为2 。把距离不大于2 的类归为一类，则得5 个扩大的新类：20， 17， 18， 19， 5， 6， 11， 3， 7， 8，9， 10第三次计算两个类间的最小距离为2，则有新类12，13， 15， 1，2， 3， 4第四次计算两个类间的最小距离为2.2361，则将所有的点（除16 和 21），归在四类中：12， 13， 15， 14， 1， 2，3， 4， 5， 6，11， 7， 8， 9， 10， 17，18， 19

12、， 20二、判别能将数据模型进行分类的特征曲线称作分类器。对于一种已知的分类器而言，源于训练数据。然后基于此分类器对新的样本进行分类。两个总体的判别法参数化的方法，例如判别分析根据训练数据拟合出参数模型，然后代入新的数据对其进行分类。非参数化的方法，如分类树的方法使用其它的方式去确定分类器。判别分析使用训练数据去估计关于预测变量的判别函数。在预测空间中，判别函数确定不同类之间的界限。1、距离判别法以 G1 和 G2 分别表示两总体，设它们是取值于R p 中的随机变量，它们的数学期望和协方差矩阵分别为EG11， EG22 ， VarG1S1 ， VarG 2S2问题：设有一个样本xR p ，问

13、x 属于总体 G1 还是属于总体G2？距离判别法是根据x 与 G1、 G2 的距离决定 x 的归属。其原则是：若x 与 G1 距离小，则 x 属于 G1；若 x与 G2 的距离小，则 x 属于 G2。即（）如果 d( x,G 1)d ( x,G 2 ) ，则判断 xG1 ；（）如果 d( x,G 2 )d( x,G 1 ) ，则判断 xG2 。其中， d (x,G i ) 为马氏距离，即d2( x,G i )(xiTi1i)， i1,2)S( xclass,err,POSTERIOR = classify(sample,training,group,type)说明： sample 样本数据；t

14、raining训练数据集。 Classify将训练集 training中的每行样本sample 数据进行分类， sample与 training必须是具有相同列数的矩阵；group训练数据所对应的类集合；type判别函数的类型；可选以下类型：（ 1） linear 线性分类器，为缺省时默认值。（ 2）diaglinear 对角线性分类器， 类似于 linear,但其具有一对角协方差矩阵估计(naiveBayes classifiers).（ 3）quadraticFitsmultivariatenormal densitieswith covarianceestimatesstratified

15、by group.（ 4）diagquadratic 类似于quadratic，但具有一个对角协方差矩阵估计。Similartoquadratic,butwithadiagonalcovariancematrixestimate(naiveBayesclassifiers).（ 5） mahalanobis 使用马氏距离及协方差估计。返回值 class 对 sample 的分类结果；err基于训练数据的误判率估计；POSTERIOR后验概率矩阵的估计值，即已知第i个样本观察值条件下，其来源于第j各类的概率Pr(group j|obs i)。马氏判别法时不计算此后验概率。2、费希尔判别法费歇判别

16、法是借助于方差分析导出线性判别函数。设有 k 个总体 Gi(i 1, 2, , k) ，从总体 Gi 中取 ni 个 p 维观察数据，得G1 ： x1(1) , xn(1)1G2 ： x1(2) , xn(2)2G k： x1( k) , , xn(k)k其中， x (ij) 为 p 维列向量。样本总数为n1n2nkn 。费歇准则下的线性判别函数为u( x)aT x ，其中 a 为 (2) 式的最大特征根1 所对应的最大特征向量l ( 对应的判别效率为 (l )1)。因此 ,费歇的判别思想是利用投影，将k 组 p 维数据投影到某一个方向a，使得它们的投影组之间尽可能地分开。在k2时，由 (4)

17、 式可取3、判别准则的评价误判概率aQ 1d（5）当一个判别准则提出之后，很自然的问题就是它们的优良性如何？通常，我们用它的误判概率来衡量，即在一定判别准则下，将一个样品判错的概率称为该判别准则的误判概率，简称误判率。设两个总体 G1 和 G2 ， x1(1) , xn(1)与 x1(2) , xn(2) 为分别来自于G1和 G2的容量分别为 n1 和 n2 的训练12样本，以全体训练样本作为n1 + n2 个新样本，逐个代入已经建立的判别准则中判别其归属，这个过程称为回判。将回判结果连同其实际分类列表如下：表 1两总体的回判结果实际归类回判情况G1G 2合计G1n11n12n1G 2n21n

18、22n2其中n11 ：属于 G1 的样品被正确判归G1 的个数；n12 ：属于 G1 的样品被错误判归G2 的个数；n21 ：属于 G2的样品被错误判归G1 的个数；n22 ：属于 G2的样品被正确判归G2 的个数。显然有 n11 +n12 = n1 ， n21 + n22= n2 ， n1 +n2 为两总体训练样品的总数，n12 + n21 为总的误判个数。误判率的回代估计为?n12n21 。pn1n2p? 在一定程度上反映了某判别准则的误判率且对任何判别准则都易于计算，但其只是误判率p? 一种近似，当样本容量较大时，还是具有一定的参考价值。4、多总体的距离判别法 *基本思路：若有k 各 n

19、 维总体，其均值向量和协方差矩阵（或样本均值和样本协方差矩阵）均已知。类似于两总体距离判别法，计算新样本到各总体的距离，比较所得到的距离的大小，判定x 属于与其距离最短的总体（若最短距离不唯一，可将其归于任一个与其具有最短距离的总体）。详细内容请参考数理统计与MATLAB 工程数据分析，清华大学出版社，王岩等编著。3.2 实验 2.1 详细提示M程序文件：X=randn(6,2);plot(X(:,1),X(:,2),bo)Y=pdist(X);squareform(Y)Z=linkage(Y)dendrogram(Z)图 1 最后的聚类结果3.3 实验 2.2-1 详细提示M程序文件：cle

20、arclcloadrainday.matme=X1;X2;Y1 = me(1:end,1);A=ones(9,1);B=ones(9,1)*2;group=A;B;h1 = gscatter(Y1,Y2,group,rb, v,offset(h1,LineWidth,2)legend(rain, rainless, .Location, NW )X,Y = meshgrid(linspace(-15,10),linspace(-20,15);X = X(:); Y = Y(:);C,err,P,logp,coeff = classify(X Y,Y1 Y2,group,mahalanobis)

21、;);.holdon ;gscatter(X,Y,C,rb, .,1,off);K = coeff(1,2).const;L = coeff(1,2).linear;Q = coeff(1,2).quadratic;f = sprintf(0 = %g+%g*x+%g*y+%g*x2+%g*x.*y+%g*y.2, .K,L,Q(1,1),Q(1,2)+Q(2,1),Q(2,2);h2 = ezplot(f,-15 10 -20 15);set(h2,Color, m, LineWidth,2)axis(-15,10 -20,15)xlabel(temperater)ylabel(humidi

22、ty)title(bf Classification with Training Data)plot(2,2,*)运行结果：图 4 采用马氏分类器所得判别结果由图 4 可见，判别曲线将平面分为两部分，红色为雨天所在区域，蓝色为非雨天所在区域，*表示x (2 , 2) T 这一天，从而判别为雨天。若将C,err,P,logp,coeff = classify(X Y,Y1 Y2,.group,mahalanobis);改为C,err,P,logp,coeff = classify(X Y,Y1 Y2,.group,quadratic);即采用二次分类器，运行结果如下：图 4 采用马氏分类器所得判别结果四、实验主要仪器设备和材料：实用数学软件：Matlab 的计算机。五、实验报告要求1、实验报告格式严格按哈尔滨理工大学有关规定要求；2、应在理解的基础上简单扼要的书写实验原理, 实验方法和步骤 （包括程序、 运行结果、 结果的解释） ；3、就观察到的现象, 变化的规律给出相应的解释；4、对实验中存在的问题, 进一步的想法等进行讨论。六、思考题1、习题 9.3 （教材 239 页）