id3算法实验报告

今年以来我们在上级党组织的领导和区精神文明办的关心支持指导下坚持以邓小平理论和三个代表重要思想为指导认真落实科学发展观id3算法实验报告篇一：ID3算法实验报告 一、实验原理 决策树通过把实例从根节点排列到某个叶子节点来分类实例，叶子节点即为实例所属的分类。树上的每一个节点说明了对实例的某个属性的测试，并且该节点的每一个后继分支对应于该属性的一个可能值，例如下图。 构造好的决策树的关键在于如何选择好的逻辑判断或属性。对于同样一组例子，可以有很多决策树能符合这组例子。人们研究出，一般情况下或具有较大概率地说，树越小则树的预测能力越强。要构造尽可能小的决策树，关键在于选择恰当的逻辑判断或属性。由于构造最小的树是NP-难问题，因此只能采取用启发式策略选择好的逻辑判断或属性。用信息增益度量期望熵最低，来选择分类属性。 公式为 ID3算法创建树的Root结点如果Examples都为正，那么返回label=+中的单结点Root 如果Examples都为反，那么返回lable=-单结点树Root如果Attributes为空，那么返回单节点树Root，lable=Examples中最普遍的目标属性值否则开始 A目标属性值 lable=Examples中最普遍的 否则在这个新分支下加一个子树ID3(example-vi,target-attribute,attributes-|A|)结束返回 Root二、算法实现训练数据存放在Data.txt 中第一行为训练样本数量和每个样本中属性的数量第二行为每个属性取值的数量之后n行为所有样本 节点数据结构 struct DTNodeint name; /用 1,2,3.表示选择的属性，0表示不用分类，即叶节点int dataD_MAX+1; /表示此节点包含的数据,datai=1,表示包含二维数 组data中的第i条数据int leaf;/leaf=1 正例叶节点；leaf=2 反例叶节点；leaf=0不是节点 int c; /c=1 正类 ；c=0 反类DTNode *childP+1;/按属性值的个数建立子树; 定义函数 void Read_data() /从数据文件Data.txt中读入训练数据 DT_pointer Create_DT(DT_pointer Tree,int name,int value)/创建决策树 int chose(int *da)/选择分类属性float Gain(int *da,int p) /计算以p属性分类的期望熵float Entropy(int *da) /计算数据的熵int test_leaf(int *da) /测试节点属性void Out_DT(DT_pointer Tree) /用线性表形式输出建立的决策树int Class(int *da) /对输入的测试样本分类 全局变量 FILE *fp;int p_num; /属性的数量int piP_MAX+1; /每个属性有几种取值int d_num;/数据的数量int dataP_MAX+1D_MAX+1;/存储训练数据 三、程序不足 1.、默认训练数据是正确的，对是否发生错误不予考虑2、没有考虑训练数据可以包含缺少属性值的实例3、只能分正反两类四、程序源码#include#include#include#include#include #define P_MAX 10 #define D_MAX 50#define P 5/一条数据包括所有属性的取值（1,2,3.）和分类的值（0或1） FILE *fp;int p_num; /属性的数量int piP_MAX+1; /每个属性有几种取值int d_num;/数据的数量int dataP_MAX+1D_MAX+1;/存储训练数据 /定义结点类型 struct DTNodeint name; /此节点分类属性的名称int dataD_MAX+1; /表示此节点包含的数据int leaf; /leaf=1 正例叶节点；leaf=2 反例叶节点；叶节点int c; /c=1 正类 ；c=0 反类DTNode *childP+1;/按属性值的个数建立子树;typedef struct DTNode *DT_pointer; DT_pointer DT = NULL; int root = 0; int test_leaf(int *da) leaf=0不是 int i;int a,b; a = 0;/ a=0表示没有0类 a=1表示有0类 for(i = 1; i if(*(da+i) =1 & datai0 = 0)a = 1;break; b = 0;/b=0表示没有1类 b=1表示有1类 for(i = 1;i if(*(da+i) = 1 & datai0 = 1)b = 1;break;if(a = 0 & b = 1)return 1;/是1叶节点else if(a = 1 & b = 0)return 2;/是0叶节点else if(a = 0 & b = 0)return 2;/此节点无数据elsereturn 0;/不是叶节点 int test_c(int a) /给叶节点附属性值 if(a = 1)return 1;elsereturn 0; float Entropy(int *da) /计算数据的熵 int i;篇二：ID3算法实验报告 装 订 线 ： ID3算法分析与实现 学 院 xxxxxxxxxxxxxxxxxxxx 专 业 xxxxxxxxxxxxxxxx 学 号 xxxxxxxxxxx 姓 名 xxxx 指导教师 xxxxXX年x月xx日题目ID3算法分析与实现 摘要:决策树是对数据进行分类，以此达到预测的目的。该决策树方法先根据训练集数据形成决策树，如果该树不能对所有对象给出正确的分类，那么选择一些例外加入到训练集数据中，重复该过程一直到形成正确的决策集。决策树代表着决策集的树形结构。 先上问题吧，我们统计了14天的气象数据(指标包括outlook，temperature，humidity，windy)，并已知这些天气是否打球(play)。如果给出新一天的气象指标数据:sunny,cool,high,TRUE，判断一下会不会去打球。这个问题当然可以用朴素贝叶斯法求解，分别计算在给定天气条件下打球和不打球的概率，选概率大者作为推测结果。现在我们使用ID3归纳决策树的方法来求解该问题。预备知识：信息熵熵是无序性（或不确定性）的度量指标。假如事件A的全概率划分是（A1,A2,.,An），每部分发生的概率是(p1,p2,.,pn)，那信息熵定义为：通常以2为底数，所以信息熵的单位是bit。 补充两个对数去处公式：ID3算法构造树的基本想法是随着树深度的增加，节点的熵迅速地降低。熵降低的速度越快越好，这样我们有望得到一棵高度最矮的决策树。在没有给定任何天气信息时，根据历史数据，我们只知道新的一天打球的概率是9/14，不打的概率是5/14。此时的熵为：属性有4个：outlook，temperature，humidity，windy。我们首先要决定哪个属性作树的根节点。对每项指标分别统计：在不同的取值下打球和不打球的次数。 下面我们计算当已知变量outlook的值时，信息熵为多少。outlook=sunny时，2/5的概率打球，3/5的概率不打球。entropy=0.971 outlook=overcast时，entropy=0 outlook=rainy时，entropy=0.971而根据历史统计数据，outlook取值为sunny、overcast、rainy的概率分别是5/14、4/14、5/14，所以当已知变量outlook的值时，信息熵为：5/14 0.971 + 4/14 0 + 5/14 0.971 = 0.693这样的话系统熵就从0.940下降到了0.693，信息增溢gain(outlook)为0.940-0.693=0.247同样可以计算出gain(temperature)=0.029，gain(humidity)=0.152，gain(windy)=0.048。 gain(outlook)最大（即outlook在第一步使系统的信息熵下降得最快），所以决策树的根节点就取outlook。接下来要确定N1取temperature、humidity还是windy?在已知outlook=sunny的情况，根据历史数据，我们作出类似table 2的一张表，分别计算gain(temperature)、gain(humidity)和gain(windy)，选最大者为N1。依此类推，构造决策树。当系统的信息熵降为0时，就没有必要再往下构造决策树了，此时叶子节点都是纯的-这是理想情况。最坏的情况下，决策树的高度为属性（决策变量）的个数，叶子节点不纯（这意味着我们要以一定的概率来作出决策）。 Java实现 最终的决策树保存在了XML中，使用了Dom4J，注意如果要让Dom4J支持按XPath选择节点，还得引入包jaxen.jar。程序代码要求输入文件满足ARFF格式，并且属性都是标称变量。实验用的数据文件：relation weather.symbolicattribute outlook sunny, overcast, rainy attribute temperature hot, mild, cool attribute humidity high, normal篇三：ID3算法实验报告ID3算法实验08级第一小组介绍： ID3算法可分为主算法和建树算法两种。 （1）ID3主算法。主算法流程如图所示。其中PE、NE分别表示正例和反例集，它们共同组成训练集。PE、PE和NE、NE分别表示正例集和反例集的子集。ID3主算法流程 （2）建树算法。采用建树算法建立决策树。首先，对当前子例进行同类归集。其次，计算各集合属性的互信息，选择互信息最大的属性Ak。再次，将在Ak处取值相同的子例归于同一子集，Ak取几个值就几个子集。最后,对既含正例又含反例的子集递归调用建树算法。若子集仅含正例或反例，对应分支标上P或N，返回调用处。 ID3算法采用自顶向下不回溯的策略搜索全部属性空间并建立决策树，算法简单、深度小、分类速度快。但是，ID3算法对于大的属性集执行效率下降快、准确性降低，并且学习能力低下。考虑到本文所涉及到的数据量并很小，下文分类分析采用了该算法。决策树学习是把实例从根结点排列到某个叶子结点来分类实例，叶子结点即为实例所属的分类。学习到的决策树能再被表示成多个if-then的规则。ID3算法是一种决策树算法。 对下载的ID3算法程序进行阅读和调试后，做了相关实验，以下是相关记录。1、试验数据 该算法的试验数据有两个：data.dat和data.tag，分别存放训练样例和各个属性列表： data.dat: data.tag: 其中，训练样例集合的试验数据由课本第3.4。2节给出，分别将其属性使用离散值数据表示，在data.tag文件中可以看到离散值其表示的属性分别对应。 2、运行结果 试验结果，是以if-then形式输出决策树，其运行界面如图： 可以将结果整理为：if humidity = 2.00 then if outlook = 3.00 then if windy = 2.00 then ON else OFF else ON i