模式识别期末论文9(共22页)

1、深圳大学研究生课程(kchng)：模式识别理论与方法课程(kchng)作业实验报告实验(shyn)名称：Classification and Regression Tree 实验编号：Proj08-01姓 名：萧嘉慰学 号：2110130216规定提交日期：2012年7月14 日实际提交日期：2012年7月13日摘 要：本实验编程实现了分类回归树算法，采用非剪枝完全树分类和进行进行非二叉分支。实验(shyn)内容：写一个(y )生成二叉分类树的通用程序，并使用课本 359页的表中的数据来训练该树，使用熵不纯度(chnd)进行分支。 (a) 采用非剪枝完全树分类下列模式： A,E,I,L,N,

2、D,E,J,K,N, B,F,J,K,M, C,D,J,L,N。 (b) 对叶节点进行剪枝，使剪枝后树的不纯度的增加尽可能小。 (c) 修改程序，使之可以进行非二叉分支，以生成多叉树。其中每个节点的分叉数可根据该节点在训练时的情况进行自动确定。 用增益比不纯度重新训练生成一个新树， 并用该树重新对(a)进行分类。技术论述： 分类回归树算法其采用基于最小距离的基尼指数估计函数, 这是因为基尼指数可以单独考虑子数据集中类属性的分布情况, 用来决定由该子数据集生成的决策树的拓展形状。CART创建简单二叉树结构对新事例进行分类, 这样可以有效地处理缺失数据, 尤其对于分类与预测时更好。并且 CART方

3、法中有贝叶斯分类的特征, 使用者可以提供主观的分类先验概率作为选择分类的权重, 则 CART在获得最终选择树前使用交叉检验来评估候选树的误分类率, 这对分析复杂样本数据非常有用。CART处理离散变量与连续变量同样容易, 这是由于它使用了或形状的几乎不依靠无关变量的分支。而且, 被CART 考虑到的分支在任何单调转换下是不变的,如对一个或更多的特征取对数、平方根等都是不变的。实验结果与讨论：Tree = Label: 1 Value: 66 Num: 20 Right: 1x1 struct Left: 1x1 struct(a)W1 = 1W2 = 3W3 = 1W4 = 3(b)W1 = 1

4、W2 = 3W3 = 1W4 = 3(c) 做不出来，程序(chngx)出不了结果。 附录：实验(shyn)程序（1）子函数function Tree=CART_MakeBinaryTree(TrainingSamples, ClassificationProperties, Region)% 基于 熵不纯度(chnd) 递归地实现 非剪枝完全二叉树%输入参数：目标数据(shj)（训练样本）TrainingSamples n*d、 （特征向量依次放置）% 对应的类别属性 ClassificationProperties n*1、（取值范围 1-C） % 特征向量维度顺序下上限 Region d

5、*2 （特征值取离散的自然数区间，左小右大）%输出参数：一个基本树形节点 Tree % 基本树形节点结构 %一：标签（记录当前节点判定所用的维度，表叶子时为空）；%二：阈值（记录当前所用维度判定之阈值，叶子节点时表类别）；%三：左枝（小于等于阈值的待分目标 归于此，表叶子时为空）%四：右枝（大于阈值的 归于此，表叶子时为空）n,Dim=size(TrainingSamples); t,m=size(Region);if Dim = t | m = 2 disp(参数错误，请检查); return;end%检查类别属性是否单纯，如果只有一个属性，那么则是叶子，否则需要继续分if ( length

6、(unique(ClassificationProperties) = 1) Tree.Right = ; Tree.Left = ; Tree.Label = ; Tree.Value = ClassificationProperties(1); Tree.Num =n; return;end%如果两个样本 为两类 直接设置为左右叶子 差异最大维度做为查询项目%单独处理此类情况，做为一种(y zhn)优化方法应对 后面提到的缺陷if length(ClassificationProperties) = 2 m,p=max(abs(TrainingSamples(1,:) -TrainingS

7、amples(2,:); Tree.Label = p; Tree.Value = (TrainingSamples(1,p) +TrainingSamples(2,p)/2); %floor Tree.Num =n; BranchRight.Right = ; BranchRight.Left = ; BranchRight.Label = ; BranchRight.Num =1; BranchLeft.Num =1; BranchLeft.Right = ; BranchLeft.Left = ; BranchLeft.Label = ; if TrainingSamples(1,p)

8、Tree.Value BranchRight.Value = ClassificationProperties(1); BranchLeft.Value = ClassificationProperties(2); else BranchRight.Value = ClassificationProperties(2); BranchLeft.Value = ClassificationProperties(1); end Tree.Right = BranchRight; Tree.Left = BranchLeft; return;end%确定 节点标签（当前节点判定所用的维度），不纯度下

9、降落差(luch)最大的维度当选%依次计算(j sun)各个维度当选之后所造成的不纯度之和 %每个维度中可选值中 最大值代表本维度Dvp=zeros(Dim,2); %记录每个维度中最大的不纯度 及相应的阈值for k=1:Dim EI=-20*ones(Region(k,2)-Region(k,1)+1,1); Iei=0; for m =Region(k,1):Region(k,2) Iei =Iei +1; %计算临时分类结果 去右边的记为 1 CpI=TrainingSamples(:,k) m; SumCpI=sum(CpI); if SumCpI = n | SumCpI = 0

10、%分到一边去了，不妥，直接考察(koch)下一个 continue; end CpI=not(CpI),CpI; EIt=zeros(2,1); %统计预计 新分到左右两枝的类别及相应(xingyng)的比率，然后得出熵不纯度 for j=1:2 Cpt=ClassificationProperties(CpI(:,j); if ( length(unique(Cpt) = 1) %应对 hist() 在处理同一元素时所存在的异常(ychng)问题 Pw =0; else Pw=hist(Cpt,unique(Cpt); Pw=Pw/length(Cpt); Pw=Pw.*log2(Pw);

11、end EIt(j)=sum(Pw); end Pr=length(Cpt)/n; EI(Iei)=EIt(1) *(1-Pr) + EIt(2) *Pr; end maxEI, p =max(EI); NmaxEI=sum(EI =maxEI); if NmaxEI 1 %如果最大值有多个，取中间那一个, 稍微改进了默认地只取第一个最大值的缺陷 t=find(EI =maxEI); p=round(NmaxEI /2); p=t(p); end Dvp(k,1)=maxEI; Dvp(k,2)=Region(k,1) +p -1;end %更新节点标签和阈值maxDv, p=max(Dvp(

12、:,1); NmaxDv=sum(Dvp(:,1) =maxDv); if NmaxDv 1 %如果最大值有多个，采用取值范围较小的那一个维度属性, 稍微改进了默认地只取第一个最大值的缺陷 t=find(Dvp(:,1) =maxDv); D,p=min(Region(t,2) -Region(t,1); p=t(p); end Tree.Label = p; Tree.Value = Dvp(p,2);%将训练样本分成(fn chn)两类，开始递归 CprI=TrainingSamples(:,p) Dvp(p,2); CplI=not(CprI); Tree.Num =n; Tree.Ri

13、ght = CART_MakeBinaryTree(TrainingSamples(CprI,:), ClassificationProperties(CprI), Region); Tree.Left = CART_MakeBinaryTree(TrainingSamples(CplI,:), ClassificationProperties(CplI), Region);function W=CART_PruningBinaryTree(Tree, Samples)% 针对(zhndu) 由函数 CART_MakeBinaryTree()生成的二叉树 Tree，按样本 Samples 遍历

14、Tree%如果 发现有与叶子共父节点的长枝条，并且其数量(shling)不多于叶子中的样本数，则将其父节点设为叶子，类别属性取多数%由于程序编写上一时间没能用Matlab语言实现对二叉树的修改，所以没有真实地修剪树，但是起到的修剪之后的效果, %遇到叶子时，就可以返回其类别属性TempLift=Tree.Left;TempRight=Tree.Right;LeftEmpty =isempty(TempLift.Right) & isempty(TempLift.Left);RightEmpty=isempty(TempRight.Right) & isempty(TempRight.Left)

15、;if LeftEmpty & RightEmpty %遇到挂有 两叶子节点，执行剪枝，择多归类 if TempLift.Num TempRight.Num W=TempLift.Value; else W=TempRight.Value; end return;elseif LeftEmpty | RightEmpty %遇到挂有 一个(y )叶子 和 一个子父节点，比较，择多归类 if LeftEmpty & (TempLift.Num TempRight.Num /3) W=TempLift.Value; return; elseif RightEmpty & (TempRight.Nu

16、m TempLift.Num /3) W=TempRight.Value; return; end endif Samples(Tree.Label) Tree.Value if RightEmpty W=Tree.Right.Value; return; else W=CART_PruningBinaryTree(Tree.Right,Samples); endelse if LeftEmpty W=Tree.Left.Value; return; else W=CART_PruningBinaryTree(Tree.Left,Samples); endendfunction W=CART_

17、UseBinaryTree(Tree,Test)% 针对(zhndu) 由函数 CART_MakeBinaryTree()生成的二叉树 Tree，给出 Test 类属 W%遇到叶子时，就可以返回(fnhu)其类别属性if isempty(Tree.Right) & isempty(Tree.Left) W=Tree.Value; return;endif Test(Tree.Label) Tree.Value W=CART_UseBinaryTree(Tree.Right,Test);else W=CART_UseBinaryTree(Tree.Left,Test); endfunction

18、Tree=CART_MakeAnyTree(TrainingSamples, ClassificationProperties, Region)% 基于 熵不纯度(chnd) 增益比不纯度 递归地实现 非剪枝完全 2/3/4叉树%分支数量动态确定方法：用不纯度下降最多的前两个维度将样本划分为四个象限，优先保证单纯的象限（一个(y )象限的样本全是同一类）独立地做为一分支点（叶子），因此% 如果没有单纯象限，则将四个象限相邻(xin ln)组合，取增益比不纯度最大的分法% 如果有一个单纯象限，则将此象限固定分为一枝，其它象限相邻组合，取增益比不纯度最大的分法% 如果有二个单纯象限，如果两个单纯象

19、限不相邻，则将四个象限直接分别做为一枝，% 如果相邻且类别相同，考察二三枝的情况；如果相邻但类别不同，考察三四枝情况，取增益比不纯度最大的分法% 如果有三个或四个单纯象限，则将四个象限直接分别做为一枝% 如果有空象限，则该象限按非单纯地参与分支组合%输入参数：目标数据（训练样本）TrainingSamples n*d、 （特征向量依次放置）% 对应的类别属性 ClassificationProperties n*1、（取值范围 1-C） % 特征向量维度顺序下上限 Region d*2 （特征值取离散的自然数区间，左小右大）%输出参数：一个基本树形节点 Tree % 基本树形节点结构 %一：标

20、签（1*2 记录当前节点判定所用的维度，表叶子时为空）；%二：阈值（ x,y 记录当前所用维度判定之阈值，叶子节点时表类别1*1）；%三：一象限枝（sx & sy 的待分目标 归于此，表叶子时无此项）%四：二象限枝（sy 的待分目标 归于此，表叶子时无此项）%五：三象限枝（sx & s=y 的待分目标 归于此，表叶子时无此项）%六：四象限枝（s=x & s m; SumCpI=sum(CpI); if SumCpI = n | SumCpI = 0 %分到一边去了，不妥，直接考察下一个 continue; end CpI=not(CpI),CpI; EIt=zeros(2,1); %统计预计

21、新分到左右两枝的类别及相应的比率，然后得出熵不纯度 for j=1:2 Cpt=ClassificationProperties(CpI(:,j); if ( length(unique(Cpt) = 1) %应对 hist() 在处理同一元素时所存在的异常(ychng)问题 Pw =0; else Pw=hist(Cpt,unique(Cpt); Pw=Pw/length(Cpt); Pw=Pw.*log2(Pw); end EIt(j)=sum(Pw); end Pr=length(Cpt)/n; EI(Iei)=EIt(1) *(1-Pr) + EIt(2) *Pr; end maxEI

22、, p =max(EI); NmaxEI=sum(EI =maxEI); if NmaxEI 1 %如果最大值有多个，取中间那一个, 稍微改进了默认(mrn)地只取第一个最大值的缺陷 t=find(EI =maxEI); p=round(NmaxEI /2); p=t(p); end Dvp(k,1)=maxEI; Dvp(k,2)=Region(k,1) +p -1;end %更新节点标签和阈值，提取 不纯度下降(xijing)最多的前两个维度maxDv, p=max(Dvp(:,1); NmaxDv=sum(Dvp(:,1) =maxDv); if NmaxDv 1 %如果最大值有多个，采

23、用取值范围较小的那一个维度属性, 稍微改进了默认地只取第一个最大值的缺陷 t=find(Dvp(:,1) =maxDv); D,p=min(Region(t,2) -Region(t,1); px=t(p); py=t(1); if px=py py=t(2); end else px=p; Dvp(p,1)=-100; %强行将原来最大值设置到最小，以便找出次大的 maxDv, p=max(Dvp(:,1); py=p; end X=Dvp(px,2); Y=Dvp(py,2); Tree.Label = px,py; %公共(gnggng)的 Tree.Value = X, Y;%分 单纯

24、度情况(qngkung) 进行讨论Bx=TrainingSamples(:,px) = X;By=TrainingSamples(:,py) = Y;Sx=not(Bx);Sy=not(By);Sp1=Bx & By;Sp2=Sx & By;Sp3=Sx & Sy;Sp4=Bx & Sy;CP1=ClassificationProperties(Sp1);CP2=ClassificationProperties(Sp2);CP3=ClassificationProperties(Sp3);CP4=ClassificationProperties(Sp4); %两类分法，只考虑半边平面的情况(q

25、ngkung)，而这 以X轴分为优，前面已经得出，更新为增益比不纯度即可 Pr=sum(Bx)/n; E2=-maxDv/(Pr*log2(Pr) +(1-Pr)*log2(1-Pr); %三类分法，有四种 % 1、2象限做为一个大的，3 4分别做为一枝 CP=CP1, CP2, CP3, CP4; E3=zeros(3,1); for k=0:3 CPt=CP(:,mod(k,4)+1), CP(:,mod(k+1,4)+1); %如果为空 或者 只有一种类别 ，直接认为是 纯净的 Pk(1)=length(Cpt); if ( length(unique(Cpt) 2) %应对 hist(

26、) 在处理同一元素时所存在的异常问题 Ebb =0; else Et = hist(CPt,unique(CPt); Et = Et /Pk(1); Ebb = Et.*log2(Et); end CPt=CP(:,mod(k+2,4)+1); Pk(2)=length(Cpt); if ( length(unique(Cpt) 2) %应对 hist() 在处理同一(tngy)元素时所存在的异常问题 Es1 =0; else Et = hist(CPt,unique(CPt); Et = Et /Pk(2); Es1 = Et.*log2(Et); end CPt=CP(:,mod(k+3,

27、4)+1); Pk(3)=length(Cpt); if ( length(unique(Cpt) 2) %应对 hist() 在处理同一元素时所存在(cnzi)的异常问题 Es2 =0; else Et = hist(CPt,unique(CPt); Et = Et /Pk(3); Es2 = Et.*log2(Et); end Pk=Pk/n; Et=sum(Ebb, Es1, Es2.*Pk); Pk=Pk.*log2(Pk); E3(k+1)=-Et/sum(Pk); %增益(zngy)比不纯度 end E3,p3=max(E3); %四类分法，有一种 E4=zeros(4,1); f

28、or k=1:4 CPt=CP(:,k); if length(unique(Cpt) 2 E4(k) =0; else Et = hist(CPt,unique(CPt); Et = Et /sum(Et); E4(k) = Et.*log2(Et); end end Pk=length(CP1), length(CP2), length(CP3), length(CP4)/n; E4=-sum(E4.*Pk)/sum(Pk.*log2(Pk); maxDv,p=max(E2, E3, E4); %增益(zngy)比不纯度 if p =1 %最终确定(qudng)分为二枝 Tree.Bran

29、ch(1) = CART_MakeAnyTree(TrainingSamples(Sx,:), ClassificationProperties(Sx), Region); Tree.Branch(2) = CART_MakeAnyTree(TrainingSamples(Bx,:), ClassificationProperties(Bx), Region); elseif p=2 % 分为(fn wi)三枝 Tree.State=p3; switch p3 case 1 Tree.Branch(1) = CART_MakeAnyTree(TrainingSamples(Bx,:), Cla

30、ssificationProperties(Bx), Region); Tree.Branch(2) = CART_MakeAnyTree(TrainingSamples(Sp3,:), CP3, Region); Tree.Branch(3) = CART_MakeAnyTree(TrainingSamples(Sp4,:), CP4, Region); case 2 Tree.Branch(1) = CART_MakeAnyTree(TrainingSamples(Sy,:), ClassificationProperties(Sy), Region); Tree.Branch(2) =

31、CART_MakeAnyTree(TrainingSamples(Sp4,:), CP4, Region); Tree.Branch(3) = CART_MakeAnyTree(TrainingSamples(Sp1,:), CP1, Region); case 3 Tree.Branch(1) = CART_MakeAnyTree(TrainingSamples(Sx,:), ClassificationProperties(Sx), Region); Tree.Branch(2) = CART_MakeAnyTree(TrainingSamples(Sp1,:), CP1, Region)

32、; Tree.Branch(3) = CART_MakeAnyTree(TrainingSamples(Sp2,:), CP2, Region); otherwise Tree.Branch(1) = CART_MakeAnyTree(TrainingSamples(By,:), ClassificationProperties(By), Region); Tree.Branch(2) = CART_MakeAnyTree(TrainingSamples(Sp2,:), CP3, Region); Tree.Branch(3) = CART_MakeAnyTree(TrainingSample

33、s(Sp3,:), CP3, Region); end else %分为(fn wi)四枝 Tree.Branch(1) = CART_MakeAnyTree(TrainingSamples(Sp1,:), CP1, Region); Tree.Branch(2) = CART_MakeAnyTree(TrainingSamples(Sp2,:), CP2, Region); Tree.Branch(3) = CART_MakeAnyTree(TrainingSamples(Sp3,:), CP3, Region); Tree.Branch(4) = CART_MakeAnyTree(Trai

34、ningSamples(Sp4,:), CP4, Region); endfunction Tree=CART_MakeMultiTree(TrainingSamples, ClassificationProperties, Region)% 基于 熵不纯度 递归地实现 非剪枝(jin zh)完全 多叉树% 首先(shuxin)基本二分法 提取出较合适的维度， 然后再考察能否在此维度上折成多段，取 增益比不纯度 最大的分法%输入参数：目标数据（训练样本）TrainingSamples n*d、 （特征向量依次放置）% 对应的类别属性 ClassificationProperties n*1、（

35、取值范围 1-C） % 特征向量维度顺序下上限 Region d*2 （特征值取离散的自然数区间，左小右大）%输出参数：一个基本树形节点 Tree % 基本树形节点结构 %一：标签（记录当前节点判定所用的维度，表叶子时为空）；%二：阈值（记录当前所用维度判定之阈值，叶子节点时表类别）；%三：左枝（小于等于阈值的待分目标 归于此，表叶子时为空）%四：右枝（大于阈值的 归于此，表叶子时为空）%检查类别属性是否(sh fu)单纯，如果只有一个属性，那么则是叶子，否则需要继续分if ( length(unique(ClassificationProperties) = 1) Tree.Branch =

36、 ; Tree.Label = ; Tree.Value = ClassificationProperties(1); return;end%如果(rgu)剩下的样本数 为类别数 直接设置为叶子 差异最大维度做为查询项目%单独处理此类情况，做为一种优化方法应对 后面提到(t do)的缺陷Nc=length(unique(ClassificationProperties);if length(ClassificationProperties) = Nc m,p=max(max(TrainingSamples) -min(TrainingSamples); Tree.Label = p; if N

37、c m; SumCpI=sum(CpI); if SumCpI = n | SumCpI = 0 %分到一边去了，不妥，直接考察下一个 continue; end CpI=not(CpI),CpI; EIt=zeros(2,1); %统计预计 新分到左右两枝的类别及相应的比率，然后得出熵不纯度 for j=1:2 Cpt=ClassificationProperties(CpI(:,j); if ( length(unique(Cpt) = 1) %应对 hist() 在处理同一元素时所存在的异常问题 Pw =0; else Pw=hist(Cpt,unique(Cpt); Pw=Pw/len

38、gth(Cpt); Pw=Pw.*log2(Pw); end EIt(j)=sum(Pw); end Pr=length(Cpt)/n; EI(Iei)=EIt(1) *(1-Pr) + EIt(2) *Pr; end maxEI, p =max(EI); NmaxEI=sum(EI =maxEI); if NmaxEI 1 %如果最大值有多个，取中间那一个, 稍微改进了默认地只取第一个最大值的缺陷 t=find(EI =maxEI); p=round(NmaxEI /2); p=t(p); end Dvp(k,1)=maxEI; Dvp(k,2)=Region(k,1) +p -1;end

39、%更新节点标签(bioqin)和阈值maxDv, p=max(Dvp(:,1); NmaxDv=sum(Dvp(:,1) =maxDv); if NmaxDv 1 %如果最大值有多个，采用取值范围较小的那一个维度属性, 稍微改进了默认(mrn)地只取第一个最大值的缺陷 t=find(Dvp(:,1) =maxDv); D,p=min(Region(t,2) -Region(t,1); p=t(p); end Tree.Label = p; %采用(ciyng)的维度 RegionN=Region(p,2) -Region(p,1) +1; switch RegionN case 2 %两个离散

40、区分度，只能分为两枝 Tree.Value = Dvp(p,2); CprI=TrainingSamples(:,p) Dvp(p,2); CplI=not(CprI); Tree.Branch(1) = CART_MakeMultiTree(TrainingSamples(CplI,:), ClassificationProperties(CplI), Region); Tree.Branch(2) = CART_MakeMultiTree(TrainingSamples(CprI,:), ClassificationProperties(CprI), Region); case 3 %三个

41、离散区分度，只需考察分为三枝时是否更优 Cp1=TrainingSamples(:,p) = Region(p,1); Cp2=TrainingSamples(:,p) = (Region(p,1)+1); Cp3=TrainingSamples(:,p) = Region(p,2); if isempty(Cp1) | isempty(Cp2) | isempty(Cp3) %如果有一枝为空，那么直接按两枝来分 Tree.Value = Dvp(p,2); CprI=TrainingSamples(:,p) Dvp(p,2); CplI=not(CprI); Tree.Branch(1) =

42、 CART_MakeMultiTree(TrainingSamples(CplI,:), ClassificationProperties(CplI), Region); Tree.Branch(2) = CART_MakeMultiTree(TrainingSamples(CprI,:), ClassificationProperties(CprI), Region); else Cpt =Cp1; if ( length(unique(Cpt) 2) %应对 hist() 在处理同一元素时所存在的异常(ychng)问题 EI1 =0; else Et = hist(CPt,unique(C

43、Pt); Et = Et /sum(Et); EI1 = Et.*log2(Et); end Cpt =Cp2; if ( length(unique(Cpt) 2) %应对 hist() 在处理同一(tngy)元素时所存在的异常问题 EI2 =0; else Et = hist(CPt,unique(CPt); Et = Et /sum(Et); EI2 = Et.*log2(Et); end Cpt =Cp3; if ( length(unique(Cpt) Dvp(p,2); Pk=n-Pk,Pk/n; E2=-maxDv/sum(Pk.*log2(Pk); if E3 E2 Tree.

44、Value = Region(p,1), Region(p,1) +1; Tree.Branch(1) = CART_MakeMultiTree(TrainingSamples(Cp1,:), ClassificationProperties(Cp1), Region); Tree.Branch(2) = CART_MakeMultiTree(TrainingSamples(Cp2,:), ClassificationProperties(Cp2), Region); Tree.Branch(3) = CART_MakeMultiTree(TrainingSamples(Cp3,:), ClassificationProperties(Cp3), Region); else Tree.Value = Dvp(p,2); CprI=TrainingSamples(:,p) Dvp(p,2); CplI=not(CprI); Tree.Branch(1) = CART_MakeMultiTree(TrainingSamples(CplI,:), ClassificationProperties(CplI), Region); Tree.Branch(