机器学习决策树算法ID3.docx
《机器学习决策树算法ID3.docx》由会员分享，可在线阅读，更多相关《机器学习决策树算法ID3.docx（11页珍藏版）》请在冰点文库上搜索。
机器学习决策树算法ID3
山东大学计算机学院实验报告
实验题目：
决策树算法ID3
学号：
日期：
2016.12.6
班级：
2014级4班
姓名：
Email：
实验目的：
1．熟悉matlab环境及相关函数的熟练使用。
2．学习如何构造一棵决策树，并且用matlab画出树形状。
3．学习如何使用一棵决策树，即将测试数值代入时，如何判断属于哪一类。
4．会写测试集代入的分类表达式和类别的逻辑表达式并化简。
5．分析该算法准确性。
硬件环境：
windows10操作系统
软件环境：
matlab环境，AzureML平台
实验步骤：
一、背景知识及原理
决策树算法：
树状结构，每一个叶子节点对应着一个分类
决策树方法在分类、预测、规则提取等领域有着广泛的应用。
在20世纪70年代后期和80年代初期，机器学习研究者J.RossQuinilan提出了ID3算法以后，决策树在机器学习、数据挖掘领域得到极大的发展。
Quinilan后来又提出了C4.5，成为新的监督学习算法。
1984年几位统计学家提出了CART分类算法。
ID3和ART算法大约同时被提出，但都是采用类似的方法从训练样本中学习决策树的。
决策树是一树状结构，它的每一个叶子节点对应着一个分类，非叶子节点对应着在某个属性上的划分，根据样本在该属性上的不同取值将其划分成若干个子集。
构造决策树的核心问题是在每一步如何选择适当的属性对样本进行拆分。
对一个分类问题，从已知类标记的训练样本中学习并构造出决策树是一个自上而下分而治之的过程。
ID3算法简介及基本原理
ID3算法基于信息熵来选择最佳的测试属性，它选择当前样本集中具有最大信息增益值的属性作为测试属性；样本集的划分则依据测试属性的取值进行，测试属性有多少个不同的取值就将样本集划分为多少个子样本集，同时决策树上相应于该样本集的节点长出新的叶子节点。
ID3算法根据信息论的理论，采用划分后样本集的不确定性作为衡量划分好坏的标准，用信息增益值度量不确定性：
信息增益值越大，不确定性越小。
因此，ID3算法在每个非叶节点选择信息增益最大的属性作为测试属性，这样可以得到当前情况下最纯的划分，从而得到较小的决策树。
设S是s个数据样本的集合。
假定类别属性具有m个不同的值：
，设是类中的样本数。
对一个给定的样本，它总的信息熵为，其中，是任意样本属于的概率，一般可以用估计。
设一个属性A具有k个不同的值，利用属性A将集合S划分为k个子集，其中包含了集合S中属性A取值的样本。
若选择属性A为测试属性，则这些子集就是从集合S的节点生长出来的新的叶节点。
设是子集中类别为的样本数，则根据属性A划分样本的信息熵为
其中，，是子集中类别为的样本的概率。
最后，用属性A划分样本集S后所得的信息增益（Gain）为
显然越小，Gain（A）的值就越大，说明选择测试属性A对于分类提供的信息越大，选择A之后对分类的不确定程度越小。
属性A的k个不同的值对应的样本集S的k个子集或分支，通过递归调用上述过程（不包括已经选择的属性），生成其他属性作为节点的子节点和分支来生成整个决策树。
ID3决策树算法作为一个典型的决策树学习算法，其核心是在决策树的各级节点上都用信息增益作为判断标准来进行属性的选择，使得在每个非叶子节点上进行测试时，都能获得最大的类别分类增益，使分类后的数据集的熵最小。
这样的处理方法使得树的平均深度较小，从而有效地提高了分类效率。
ID3算法的具体流程
1）对当前样本集合，计算所有属性的信息增益；
2）选择信息增益最大的属性作为测试属性，把测试属性取值相同的样本划为同一个子样本集；
3）若子样本集的类别属性只含有单个属性，则分支为叶子节点，判断其属性值并标上相应的符号，然后返回调用处；否则对子样本集递归调用本算法。
二、实验步骤
1.因为以前经常使用微软的Azure平台，这次仍然想用这个平台实验一下。
测试使用决策树算法求出的准确率和召回率等以及改变参数对结果的影响。
a.两分类决策树（第一个图是数据，前12个数据；第二个图是平台上的流程图）
参数配置：
（随机种子0，0.25的测试集）
结果：
测试集共3个数据，分错了2个，准确率为33.3%，召回率1%。
通过可视化平台的结果对比可以发现决策树算法的准确率很低，我感觉这个的原因是数据太少，所以偶然性太强，数据若是多一些，可能会好一些。
2.开始自己着手写matlab程序，刚开始看到题感觉挺简单的，不就是算出熵，然后算信息增益得到每次要判断的属性，那树不就画出来了么。
然而事实告诉我，用笔算的简单但是写程序就不那么容易了。
每次传进去的是一批数据，得根据数据去画树。
然后我就通过看清华大学那本机器学习的书，找到了一个伪代码的算法，思路没有错，就是一个递归算法，输入的变量是数据和属性，输出的变量是一棵树的结构。
照着这个循环写完之后，运行出来又出现了错误，然后和同学讨论发现是结构体的问题，结构体比较BT的地方是要求参数数目是相同的，所以每次定义结构体的以及每个return的时候都需要写全所有的参数，即使为空。
（第一张图片是算法伪代码，第二张是结构体的写法）
3.把树构造好后，返回的是一棵树的结构，里面包含了好几层，可以用plot的专门画树的方法画出来。
但是，如何使用这棵树呢？
我是把每棵树的每个节点也就是结构体构造了好几个属性（如上图所示），保存了节点的类别（1或者2），保存了节点下一个属性（最大信息增益的属性），保存了它是否是叶子节点。
这样每次使用树的时候，代入数值后，先比较第一个最大信息增益的属性，然后找下一个，直到叶子节点就可以判断出类别了。
第二个问题是第二个测试数据中的第二维是D，并不在该有的属性集中，然后我按照老师上课讲的方法，把它设置为属性集（1，2，3）中出现次数最多的值3，然后去计算。
4.算法的过程：
a是ID3算法中最后的包括了递归的循环（注意每次递归进去的是去掉了已使用过的属性值的，数据data和属性attributes都要去掉）；b是信息增益的求法；c是判断样本在属性上取值是否相同：
a.%从属性中选择最优划分属性a，求最优属性位于第a行，后面递归传入data时记得去掉那一行
a=gain（data,attributes）;
tree.nextsx=a;
ma=length（unique（data（a,:
）））;
%首先对每一个属性循环，生成node的一个分支
fori=1:
ma
node=struct（'value','null'）;
node.node='null';
node.nextsx=0;%树的每个节点的下一个要选择的属性
tree.node（i）=node;
%得到data中在该属性上不同取值的样本子集dd
%[d1,d2,d3,d4]=fkjz（data,a）;
dd=[];
fort=1:
l
ifdata（a,t）==i
dd=[dd,data（:
t）];
end
end
if（isempty（dd））
%fprintf（'data中在属性上不同取值的样本子集为空\n'）;
if（last_sum>=（l/2）*l）;
tree.node（i）.value='true';
else
tree.node（i）.value='false';
end
tree.node（i）.nextsx=0;%树的每个节点的下一个要选择的属性
else
dd（a,:
）=[];
shux=attributes;
shux（a）=[];
tree.node（i）=ID3（dd,shux）;
%tree.node（i）=a;
end
end
b.fori=1:
m2
[x1,x2,x3,x4]=fkjz（x,i）;%每次都得到按照某一个属性分开的矩阵
l1（i,:
）=[size（x1,2）/12,size（x2,2）/12,size（x3,2）/12,size（x4,2）/12];%5行4列，5种特征，每种特征中每种节点占总结点，也就是Sv/S
ifsize（x1,2）/12~=0
[p11（i,1）,p12（i,1）,entro1（i,1）]=entropy（x1（m,:
）,1,2）;
end
ifsize（x2,2）/12~=0
[p11（i,2）,p12（i,2）,entro1（i,2）]=entropy（x2（m,:
）,1,2）;
end
ifsize（x3,2）/12~=0
[p11（i,3）,p12（i,3）,entro1（i,3）]=entropy（x3（m,:
）,1,2）;
end
ifsize（x4,2）/12~=0
[p11（i,4）,p12（i,4）,entro1（i,4）]=entropy（x4（m,:
）,1,2）;
end
gain2（i）=entro-（l1（i,1）*entro1（i,1）+l1（i,2）*entro1（i,2）+l1（i,3）*entro1（i,3）+l1（i,4）*entro1（i,4））;
end
%求最大的信息增益位于的行数
gain_max=find（gain2==（max（gain2）））;
gain_max=gain_max
（1）;
c.[m,l]=size（x）;
a=0;
fori=2:
l
forw=1:
m-1
ifx（w,1）~=x（w,i）
return
end
end
end
a=1;
三、实验结果
1.树的结构：
算上根节点分成了4层，属性依次选的是1，2，5（第一张图是画的这次分出的树的结构；第二张图是调用算法后返回了的树；后面几张图是打开树的结构体的内部参数和结构：
其中，true是指w1类，false是指w2类。
每个结构体都是包含了3个属性，value是类别，nextsx是下一个要选择的信息增益最大的属性位于的行数（因为每次我代入递归的时候是去掉已用过的属性，所以显示的第一次nextsx=1即第一行属性，第二次nextsx=1，也就是第二行，第三次nextsx=3，也就是第五行）tree是根节点，按照第一个属性往下分出了4个子集，其中第二个子集又按照第二个属性分出了3个子集，这3个子集的第一个子集按照第五个属性分出3个节点，自此分好）
2.第二题分类两个测试数据，第一个数据为{2，3，2，1，2}，第二个数据为{3，3，3，2，1}，分类结果为第一个数据分到w1类，第二个数据分到w2类。
3.第三题写出测试数据的逻辑表达式
a1=（A-D=B）（E-G=G）
a2=（A-D=C）
4.第四题写出w1,w2的逻辑表达式
w1=（A-D=A）+（A-D=B）（E-G=G）+（A-D=B）（E-G=E）（M-N=M）;
w2=（A-D=B）（E-G=E）（M-N=N）+（A-D=B）（E-G=F）+（A-D=C）+（A-D=D）;
结论分析与体会：
刚开始感觉这个题还挺简单的，因为思路是非常清晰的，根据信息增益找属性，然后递归ID3算法就能得到树的结构了，但是用笔算简单，用程序写的健全是不容易的。
特别是争取更加抽象一些，不能只根据这12个数据来算，最好是以后不管传入什么数据进去都是可以算出来的。
所以每个算法都包装一下，思路一定要清晰。
回过头看这个题目，感觉机器学习真的不能只靠听课了，平时要多看博客之类的，才能深刻理解。
除此之外感觉matlab越来越熟练了。
升级会员 