机器学习(周志华) 参考答案 第四章 决策树 4.4

时间：2023-02-12 23:30:35

机器学习(周志华) 参考答案 第四章 决策树 4.4

机器学习(周志华西瓜书) 参考答案 总目录

机器学习(周志华) 参考答案 第四章 决策树

4.试编程实现基于基尼指数进行划分选择的决策树算法，并为表4.2中数据生成预剪枝、后剪枝决策树，并与未剪枝决策树进行比较。

如果让决策树完全伸展的话，训练误差最终到0，但是会带来很严重的过拟合，学习到一些不该学到的东西

解决这个问题的方法之一就是对决策树进行剪枝。
剪枝分为预剪枝和后剪枝，预剪枝在伸展前判断，效率高，但可能会导致欠拟合，但是当数据量很大时，欠拟合的风险大大减小。后剪枝没有欠拟合的风险，过拟合风险也不大，但是它要在每个非叶节点计算完后(并不需要等到整棵树建完才判断)才可以判断是否需要剪枝，所需的时间成本是很大的。

与前面不同的是，剪枝通过测试样本来判断，测试样本随着训练样本进入到各个叶节点，划分靠训练样本，剪枝靠测试样本。
预剪枝与后剪枝虽然差别很大，但是代码却很相近，只要把剪枝的判断(剪枝的判断计算可以不需要移动)从划分前移动到划分后，就像树的遍历，改变一下访问节点的位置就能达到效果，这是递归(栈结构)的一大好处。

这里的参数选择用了基尼指数，由于题目要求是在离散数据上进行剪枝，我也就没去加代码去实现连续参数的剪枝，因为写出现有的这些代码已经是够累了。

预剪枝的结果图，差点就没只有一个点，和书上一个结果
机器学习(周志华) 参考答案 第四章 决策树 4.4

后剪枝的结果图，其实这个图和书上的图也是一样的，只是这个画的。。。。。
机器学习(周志华) 参考答案 第四章 决策树 4.4

这里给出后剪枝的treeres表，如果不知道具体属性含义请参考4.3题
由于没有连续属性，所以忽略第四行

1 2 3 4 5 6 7 8 9 10
‘脐部’ ‘好瓜’ ‘根蒂’ ‘坏瓜’ ‘色泽’ ‘好瓜’ ‘好瓜’ ‘好瓜’ ‘好瓜’ ‘坏瓜’
[] ‘凹陷’ ‘稍凹’ ‘蜷缩’ ‘稍蜷’ ‘青绿’ ‘乌黑’ ‘浅白’ ‘硬挺’ ‘平坦’

代码主体
加入了测试数据的输入

%{
    x:训练样本属性  连续变量直接用数值,离散变量用1，2，3区别
    y:训练样本分类值  1-好 2-不好 
    x:测试样本属性  连续变量直接用数值,离散变量用1，2，3区别
    y:测试样本分类值  1-好 2-不好
    tree:生成的树形结构，用数组表示 按先根遍历编号 值为父节点编号 1为根节点
    treeleaf:标记是否为叶子节点
    treeres:每组3个变量
1:如果是叶子节点则记录分类 如果是非叶节点记录当前节点的分类属性
2:离散属性直接记录父节点分类的具体属性 连续属性1-小于 2-大于
3:如果是连续属性，记录阀值，离散属性为0
    ptr:节点数目累加变量
%}
global x y x_test y_test fenlei fenlei1 xigua; 
global tree treeleaf treeres ptr;

%其实这样多次读取文件很慢
x = xlsread('C:\Users\icefire\Desktop\ml\西瓜3.xlsx', 'sheet1', 'A1:K6');
y = xlsread('C:\Users\icefire\Desktop\ml\西瓜3.xlsx', 'sheet1', 'A9:K9');
x_test = xlsread('C:\Users\icefire\Desktop\ml\西瓜3.xlsx', 'sheet1', 'L1:Q6');
y_test = xlsread('C:\Users\icefire\Desktop\ml\西瓜3.xlsx', 'sheet1', 'L9:Q9');


%西瓜属性的中文标识
fenlei1={'色泽', '根蒂', '敲声', '纹理', '脐部' ,'触感'};
fenlei={'青绿','蜷缩', '浊响', '清晰', '凹陷', '硬滑',;
'乌黑', '稍蜷', '沉闷', '稍糊', '稍凹', '软粘',;
'浅白', '硬挺', '清脆', '模糊', '平坦', '无',;};
xigua = {'好瓜','坏瓜'};

[m,n]=size(y);
[tm,tn]=size(y_test);
%为set集合提前分配空间 集合中存放所有样本的编号
for i=n:-1:1
    set(i) = i;
end
for i=tn:-1:1
    test_set(i) = i;
end

tree=zeros(1,100);
treeleaf=zeros(1,100);
treeres=cell(3,100);
ptr = 0;
%{
手动设置的变量:修改输入数据时要收到修改
    pf：属性的编号，按顺序编号
    pu：属性是连续还是离散的0-离散 1-连续
    pt：属性对应的分类数，连续属性用不着(可以设为0)
%}
pf=[1 2 3 4 5 6];
pu=[0 0 0 0 0 0];
pt=[3 3 3 3 3 2];

TreeGenerate_pre(0,set,test_set,pf,pu,pt);
treeplot(tree(1:ptr));

使用了一个新的函数TreeGenerate_pre和前面的TreeGenerate区分，当然主体还是一样，只是加了剪枝的计算与判断。当然还有一个TreeGenerate_aft,不过由于和TreeGenerate_pre几乎完全一样，就不贴了，会在TreeGenerate_pre里面注释

%{
    parent:父节点编号
    curset:当前的训练样本编号集合
    test_set:当前的测试样本编号集合
    pf:当前的属性编号集合
%}
function TreeGenerate_pre(parent,curset,test_set,pf,pu,pt)
global x y x_test y_test fenlei fenlei1 xigua; 
global tree treeleaf treeres ptr;
%由于加入了测试样本 测试样本随着当前训练样本一起划分到子节点
%但属性划分时只考虑训练样本
%剪枝判断时只考虑测试样本
%大体和TreeGenerate一样 仅增加剪枝判断
       ptr=ptr+1;
       tree(ptr)=parent;
       cur = ptr;

%递归返回情况1:当前所有样本属于同一类
       n = size(curset);
       n = n(2);

       cury=y(curset);
       y_data=unique(cury);
       y_nums=histc(cury,y_data);

if(y_nums(1)==n) 
            treeres{1,ptr} = xigua{y_data};
            treeleaf(cur) = n;
return;
end


%计算当前y的取值分类及各有多少个 如果只有一类表示属于同一类
       pfn=size(pf);
       tmp_para = x(pf,curset(1));
       f = 1;
       classy = y(curset(1));
       sum=zeros(1,2);
for i=1:n
if isequal(tmp_para , x(pf,curset(i)))
                t = (classy == y(curset(i)));
                sum(t) = sum(t)+1;
else
                f=0;
break;
end
end
if(f == 1 || pfn(2) == 0) 
            treeres{1,cur} = xigua{(sum(2)>=sum(1))+1};
            treeleaf(cur) = 1;
return;
end

%主递归
%在最优参数选择上与TreeGenerate没有区别
[k, threshold] = entropy_paraselect(curset,pf,pu);
       curx = x(pf,:);
       p_num=pf(k);
       treeres{1,cur} = fenlei1{p_num};
if(pu(k))%偷懒没实现对连续属性的剪枝
             num = [1 1];
             tmp_set = zeros(2,100);
for i=1:n
if(curx(k,curset(i))>=threshold)
                    tmp_set(1,num(1))=curset(i);
                    num(1) = num(1)+1;
else
                    tmp_set(2,num(2))=curset(i);
                    num(2) = num(2)+1;
end
end

for i=1:2
                    treeres{2,ptr+1} = fenlei{i,p_num};
                    treeres{3,ptr+1} = threshold;
                    ttmp_set = intersect(tmp_set(i,:),curset);
                    TreeGenerate_pre(cur,ttmp_set,pf,pu,pt);
end
else
%离散属性
            tpt=pt(k);
            curx_test = x_test(pf,:);
            pf(:,k)=[];
            pu(:,k)=[];
            pt(:,k)=[];
%计算当前训练样本未分类时各属性取值对应的正反例数
            num = ones(1,tpt);
            tmp_set = zeros(tpt,100);
            n=size(curset);
for i=1:n(2)             
               tmp_set(curx(k,curset(i)),num(curx(k,curset(i))))=curset(i);
               num(curx(k,curset(i))) = num(curx(k,curset(i)))+1;
end

%计算当前测试样本未分类时各属性取值对应的正反例数
            num = ones(1,tpt);
            tmp_test_set = zeros(tpt,100);
            n=size(test_set);
for i=1:n(2)             
               tmp_test_set(curx_test(k,test_set(i)),num(curx_test(k,test_set(i))))=test_set(i);
               num(curx_test(k,test_set(i))) = num(curx_test(k,test_set(i)))+1;
end

%计算分类后训练样本分类错误个数
             cury_test=y_test(test_set);
             y_test_data=unique(cury_test);
             y_test_nums=histc(cury_test,y_test_data);
             err_pre=y_test_nums((y_nums(1)>y_nums(2))+1); %分类前的错误数
             err_aft=0; %分类后的错误计数
for i=1:tpt  %每个具体取值对应的错误数
                   ttmp_test_set = intersect(tmp_test_set(i,:),test_set);
                   ttmp_set = intersect(tmp_set(i,:),curset);
                   ttmp_set_nums=histc(y(ttmp_set),y_test_data);
                   ttmp_test_set_nums=histc(y_test(ttmp_test_set),y_test_data);
                   err_aft= err_aft + ttmp_test_set_nums((ttmp_set_nums(1)>=ttmp_set_nums(2))+1);
end

%预剪枝主要判断 如果错误率没降低 就进行剪枝
%在划分递归前进行剪枝判断 如果是后剪枝 就把这个判断放在划分递归的后面(有点像树的遍历)
if(err_pre <= err_aft) 
                 treeres{1,cur} = xigua{(y_nums(1)>y_nums(2))+1};
                 treeleaf(cur) = 0;
return;
end
% 按每种取值递归
for i=1:tpt
                   ttmp_test_set = intersect(tmp_test_set(i,:),test_set);
                   ttmp_set = intersect(tmp_set(i,:),curset);
                   n = size(ttmp_set);
%如果该取值下没有样本，不进行递归，标记为当前样本下最多的一个分类
if(n(2)==0)
                       ptr=ptr+1;
                       tree(ptr)=cur;
                       treeres{1,ptr} = xigua{(y_nums(2)>y_nums(1))+1};
                       treeres{2,ptr} = fenlei{i,p_num};
                       treeleaf(cur) = 0;
else
                    treeres{2,ptr+1} = fenlei{i,p_num};
                    TreeGenerate_pre(cur,ttmp_set,ttmp_test_set,pf,pu,pt);
end
end
%
%后剪枝 在递归后判断
%if(err_pre < err_aft) 
% treeres{1,cur} = xigua{(y_nums(2)>y_nums(1))+1};
% treeleaf(cur) = 0;
% %比预剪枝多一步 把分配了的节点收回来 数目是当前属性取值可能数
% ptr = ptr - tpt;
% return;
%end
%
end

end

基尼指数选择参数，其实和信息增益没什么区别，连生成的树都是一样的。。。信息增益率还能看到些不同的树结构。稍微改了下信息增益的代码,由于大部分一样，注释就少了点

%{
基尼指数选择
    curset:当前样本集合
    pf：当前属性的编号
    pu：当前属性是连续还是离散的0-离散 1-连续
输出
    n：最优属性
    threshold:连续属性返回阀值
%}
function [n, threshold] = cart_paraselect(curset,pf,pu)
global x y; 
%几乎和信息增益一样 有不明白的参考信息增益选择注释
    curx = x(pf,curset);
    cury = y(curset);
    pn = size(pf);
    all = size(cury);
    min_cart = 100;     %由于是取最小值 所以初值设为很大的正数
    minn=0;
    threshold = 0;
for i=1:pn(2)
if(pu(i) == 1)
            con_min_cart =  100;
            con_threshold = 0;
            xlist = sort(curx(i,:),2);
for j=all(2):-1:2
               xlist(j) = (xlist(j)+xlist(j-1))/2;
end
for j=2:all(2)
               cur_cart = 0; 
               nums = zeros(2,2);
for k=1:all(2)
                    nums((curx(i,k)>=xlist(j))+1,cury(k)) = nums((curx(i,k)>=xlist(j))+1,cury(k)) + 1;
end
for k=1:2
if(nums(k,1)+nums(k,2) > 0)
                p=nums(k,1)/(nums(k,1)+nums(k,2));
                cur_cart = cur_cart + (1-p^2-(1-p)^2)*(nums(k,1)+nums(k,2))/all(2);
end
end
if(cur_cart<con_min_cart)
                   con_min_cart = cur_cart;
                   con_threshold = xlist(j);
end
end
if(con_min_cart < min_cart)
                min_cart=con_min_cart;
                minn = i;
                threshold = con_threshold;
end
else
            cur_cart = 0; 
            set_data=unique(curx(i,:));
            setn=size(set_data);
            nums = zeros(10,2);
for j=1:all(2)
               nums(curx(i,j),cury(j))=nums(curx(i,j),cury(j))+1;
end
for j=1:setn(2)
if((nums(set_data(j),1)+nums(set_data(j),2))>0)
                 p=nums(set_data(j),1)/(nums(set_data(j),1)+nums(set_data(j),2));
                  cur_cart = cur_cart +(1-p^2-(p-1)^2)*(nums(set_data(j),1)+nums(set_data(j),2))/all(2);
end
end
if(cur_cart < min_cart)
                minn = i;
                min_cart = cur_cart;
end
end
end
    n = minn;
    threshold = threshold * pu(n);

end
标签：

相关文章