模式识别期末论文9

深圳大学研究生课程：模式识别理论与方法

课程作业实验报告

实验名称：Classification and Regression Tree

实验编号：Proj08-01

姓 名：萧嘉慰

学 号：2110130216

规定提交日期：2012年7月14 日

实际提交日期：2012年7月13日

摘 要：本实验编程实现了分类回归树算法，采用非剪枝完全树分类和进行进行非二叉分支。

实验内容：

写一个生成二叉分类树的通用程序，并使用课本 359页的表中的数据来训练该树，使用熵

不纯度进行分支。

(a) 采用非剪枝完全树分类下列模式：

{A,E,I,L,N}, {D,E,J,K,N}, {B,F,J,K,M}, {C,D,J,L,N}。

(b) 对叶节点进行剪枝，使剪枝后树的不纯度的增加尽可能小。

(c) 修改程序，使之可以进行非二叉分支，以生成多叉树。其中每个节点的分叉数可根据该节点

在训练时的情况进行自动确定。 用增益比不纯度重新训练生成一个新树， 并用该树重新对(a)进行分类。

技术论述：

分类回归树算法其采用基于最小距离的基尼指数估计函数, 这是因为基尼指数可以单独考虑子数据集中类属性的分布情况, 用来决定由该子数据集生成的决策树的拓展形状。CART创建简单二叉树结构对新事例进行分类, 这样可以有效地处理缺失数据, 尤其对于分类与预测时更好。并且 CART方法中有贝叶斯分类的特征, 使用者可以提供主观的分类先验概率作为选择分类的权重, 则 CART在获得最终选择树前使用交叉检验来评估候选树的误分类率, 这对分析复杂样本数据非常有用。CART处理离散变量与连续变量同样容易, 这是由于它使用了或形状的几乎不依靠无关变量的分支。而且, 被CART 考虑到的分支在任何单调转换下是不变的,如对一个或更多的特征取对数、平方根等都是不变的。

实验结果与讨论：

Tree =

Label: 1

Value: 66

Num: 20

Right: [1x1 struct]

Left: [1x1 struct]

(a)W1 = 1

W2 =

3

W3 =

1

W4 =

3

(b)W1 =

1

W2 =

3

W3 =

1

W4 =

3

(c) 做不出来，程序出不了结果。

附录：实验程序

（1）子函数

function Tree=CART_MakeBinaryTree(TrainingSamples,

ClassificationProperties, Region)

% 基于 熵不纯度 递归地实现 非剪枝完全二叉树

%输入参数：目标数据（训练样本）TrainingSamples n*d、 （特征向量依次放置）

% 对应的类别属性 ClassificationProperties n*1、（取值范围 1--C）

% 特征向量维度顺序下上限 Region d*2 （特征值取离散的自然数区间，左小右大）

%输出参数：一个基本树形节点 Tree

% 基本树形节点结构

%一：标签（记录当前节点判定所用的维度，表叶子时为空）；

%二：阈值（记录当前所用维度判定之阈值，叶子节点时表类别）；

%三：左枝（小于等于阈值的待分目标 归于此，表叶子时为空）

%四：右枝（大于阈值的 归于此，表叶子时为空）

[n,Dim]=size(TrainingSamples);

[t,m]=size(Region);

if Dim ~= t || m ~= 2

disp('参数错误，请检查');

return;

end

%检查类别属性是否单纯，如果只有一个属性，那么则是叶子，否则需要继续分

if ( length(unique(ClassificationProperties)) == 1)

Tree.Right = [];

Tree.Left = [];

bel = [];

Tree.Value = ClassificationProperties(1);

Tree.Num =n;

return;

end

%如果两个样本 为两类 直接设置为左右叶子 差异最大维度做为查询项目

%单独处理此类情况，做为一种优化方法应对 后面提到的缺陷

if length(ClassificationProperties) == 2

[m,p]=max(abs(TrainingSamples(1,:) -TrainingSamples(2,:)));

bel = p;

Tree.Value = ((TrainingSamples(1,p)

+TrainingSamples(2,p))/2); %floor

Tree.Num =n; BranchRight.Right = [];

BranchRight.Left = [];

bel = [];

BranchRight.Num =1;

BranchLeft.Num =1;

BranchLeft.Right = [];

BranchLeft.Left = [];

bel = [];

if TrainingSamples(1,p) > 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

%确定 节点标签（当前节点判定所用的维度），不纯度下降落差最大的维度当选

%依次计算各个维度当选之后所造成的不纯度之和

%每个维度中可选值中 最大值代表本维度

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 %分到一边去了，不妥，直接考察下一个

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/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, 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(:,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

bel = p;

Tree.Value = Dvp(p,2);

%将训练样本分成两类，开始递归