文档介绍：Forpersonaluseonlyinstudyandresearch;mercialuse山东大学计算机学院实验报告实验题目:决策树算法ID3学号:日期::2014级4班姓名:Email:实验目的:熟悉matlab环境及相关函数的熟练使用。学****如何构造一棵决策树,并且用matlab画出树形状。学****如何使用一棵决策树,即将测试数值代入时,如何判断属于哪一类。会写测试集代入的分类表达式和类别的逻辑表达式并化简。分析该算法准确性。硬件环境: windows10操作系统软件环境:matlab环境,AzureML平台实验步骤:一、背景知识及原理决策树算法:树状结构,每一个叶子节点对应着一个分类决策树方法在分类、预测、规则提取等领域有着广泛的应用。在20世纪70年代后期和80年代初期,,决策树在机器学****数据挖掘领域得到极大的发展。,成为新的监督学****算法。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决策树算法作为一个典型的决策树学****算法,其核心是在决策树的各级节点上都用信息增益作为判断标准来进行属性的选择,使得在每个非叶子节点上进行测试时,都能获得最大的类别分类增益,使分类后的数据集的熵最小。这样的处理方法使得树的平均深度较小