机器学习(周志华) 参考答案 第四章 决策树 4.10
机器学习(周志华西瓜书) 参考答案 总目录
机器学习(周志华) 参考答案 第四章 决策树
10.从网上下载或自己编程实现任意一种多变量决策树算法，并观察其在西瓜数据集3.0上产生的结果。
这个书上倒是提供了个方法，直接对连续属性进行回归分析，为了方便就又是对率回归了
单变量的决策树都是水平划分的，如果能斜着分，弯着分那多好。
方法:
每次对全属性进行对率回归，得出最佳划分。然后按划分将数据集分为两个集合。当某个划分里的样本类型相同时，则停止划分并标记为当前类型；或者当前样本属性完全一样，则选择某类型数目最多的类标记为当前类型(这种情况几乎不可能出现)；不然就继续划分，知道训练误差为0，或者达到最大的层次。
数据集用的就是3.0里面两个连续的属性，生成的树结构如下: 
一看这棵树就不一般，二叉树里几乎就没它不是的。既然是平面划分，我又算了张直线划分的图，不过直线的交点不好控制。有的地方不该出头，但是去判断就太麻烦了，那是计算几何该考虑的东西了。
用红色喷头标出的就是不该出头的部分 直接无视就好了，最后这几条直线射线把所有样本划分，达到了0的训练误差，至于过拟合什么的，没测试样本，就当没好了。
因为全是连续数据，代码简化了很多。
%{
x:训练样本属性 连续变量直接用数值,离散变量用1，2，3区别
y:训练样本分类值 1-好 2-不好
tree:生成的树形结构，用数组表示 按先根遍历编号 值为父节点编号 1为根节点
treeleaf:标记是否为叶子节点
treeres:每组3个变量
1:如果是叶子节点则记录分类 如果是非叶节点记录当前节点的分类属性
2:离散属性直接记录父节点分类的具体属性 连续属性1-小于 2-大于
3:如果是连续属性，记录阀值，离散属性为0
ptr:节点数目累加变量
记录每次对率回归的参数 存入lw,lb
%}
global x y ;
global tree treeleaf treeres ptr;
global lw lb ;
x = xlsread('C:\Users\icefire\Desktop\ml\西瓜3.xlsx', 'sheet1', 'A7:Q8');
y = xlsread('C:\Users\icefire\Desktop\ml\西瓜3.xlsx', 'sheet1', 'A9:Q9');
%为变量预分配空间
[m,n]=size(y);
[tm,tn]=size(y_test);
for i=n:-1:1
set(i) = i;
end
for i=tn:-1:1
test_set(i) = i;
end
lw = zeros(2,100);
lb = zeros(2,100);
tree=zeros(1,100);
treeleaf=zeros(1,100);
treeres=zeros(1,100);
tf = zeros(1,100);
ptr = 0;
TreeGenerate_mul(0,set);
%treeplot(tree(1:ptr));
%绘制点
for i=1:17
if y(i)==1
plot(x(1,i),x(2,i),'+r');
hold on;
else if y(i)==2
plot(x(1,i),x(2,i),'og');
hold on;
end
end
end
%绘制直线
%第一条划分线单独画出
w1=lw(:,1);
b1=lb(1);
y1=-(0.1*w1(1)+b1)/w1(2);
y2=-(0.9*w1(1)+b1)/w1(2);
line([0.1 0.9],[y1 y2]);
hold on;
%通过树结构查询父节点直线参数，求出交点画出直线
for i=2:ptr
if(treeleaf(i)>0)
continue;
end
w1=lw(:,i);
w2=lw(:,tree(i));
b1=lb(i);
b2=lb(tree(i));
x1=0.1;
y1=-(x1*w1(1)+b1)/w1(2);
if(y1<0)
y1=0.5;
x1=-(y1*w1(2)+b1)/w1(1);
end
y2=(w2(1)*b1-w1(1)*b2)/(w1(1)*w2(2)-w2(1)*w1(2));
if(y2>0.5)
y2=0.5;
end
if(y2<0.1)
y2=0.1;
end
x2=-(y2*w1(2)+b1)/w1(1);
line([x1 x2],[y1 y2]);
hold on;
end
xlabel('密度');
ylabel('含糖率');
title('对率回归-多变量划分决策树'); TreeGenerate_mul递归也简化了很多，去掉了一系列的参数相关变量
每次最多二划分
function TreeGenerate_mul(parent,curset)
global x y;
global tree treeleaf treeres ptr;
global lw lb;
ptr=ptr+1;
tree(ptr)=parent;
cur = ptr;
%returne case 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(cur) = y_data(1);
treeleaf(cur) = n;
return;
end
%{
多参数对率回归(不用再选取最优属性)
每次选取最优的划分 ，将数据集分为2类
递归直到训练误差到0(没有冲突的样本)
或者到递归最大深度
%}
[w,b] = logre_paraselect_mul(curset);
lw(:,cur)=w;
lb(cur) =b;
curx = x(:,curset);
num = [1 1];
tmp_set = zeros(2,100);
%将样本分为2类 在支线上面和下面
for i=1:n
if(w'*curx(:,i)+b>0)
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
ttmp_set = intersect(tmp_set(i,:),curset);
TreeGenerate_mul(cur,ttmp_set);
end
end参数计算上，直接用的3.3对率回归的代码
%其实就是对率回归 返回参数
function [lw,lb] = logre_paraselect_mul(curset)
global x y;
curx = x(:,curset);
cury = y(curset);
cury=cury-1;
old_l=0; %记录上次计算的l
n=0; %计算迭代次数
b=[0;0;1]; %初始参数 （自定义）
[km,kn]=size(curx);
while(1)
cur_l=0;
bx=zeros(kn,1);
tx=[curx ;ones(1,kn)];
%计算当前参数下的l
for i=1:kn
bx(i) = b.'*tx(:,i);
cur_l = cur_l + ((-cury(i)*bx(i)) )+log(1+exp(bx(i)));
end
%迭代终止条件
if abs(cur_l-old_l)<0.001
break;
end
%更新参数(牛顿迭代法)以及保存当前l
n=n+1;
old_l = cur_l;
p1=zeros(kn,1);
dl=0;
d2l=0;
for i=1:kn
p1(i) = 1 - 1/(1+exp(bx(i)));
dl = dl - tx(:,i)*(cury(i)-p1(i));
d2l = d2l + tx(:,i) * tx(:,i).'*p1(i)*(1-p1(i));
end
b = b - d2l\dl;
end
lw = b(1:km,:);
lb = b(km+1);
end