文档介绍：数据挖掘实验报告 1 实验二分类挖掘算法( ID3 ) 一、实验目的 1 、理解分类 2 、掌握分类挖掘算法 ID3 3 、为改进 ID3 打下基础二、实验内容 1 、选定一个数据集(可以参考教学中使用的数据集) 2 、选择合适的实现环境和工具实现算法 ID3 3 、给出分类规则三、实验原理决策树是一种最常见的分类算法, 它包含有很多不同的变种, ID3 算法是其中最简单的一种。 ID3 算法中最主要的部分就是信息熵和信息增益的计算。信息熵的计算公式如下。信息增益的计算公式为: 其中 P(ui) 为类别 ui 在样本 S 中出现的概率,A 是样本的属性, Value(A) 是属性 A 所有取值的集合, v 是A得其中一个属性值。 Sv是S中A 的值为 v 的样例集合。 ID3 算法的流程就是在属性集 A 中寻找信息增益值最大的属性, 作为根节点, 按照根节点属性的取值将样本集合分成几个子集, 将此属性从属性集中去掉, 在每个子集中选择信息增益值最大的属性,作为当前子集的根节点,上层集合的根节点的子节点,如此循环递归, 如果得到的子集中所有的样本属于一个类别,则递归停止。四、实验要求 1 、数据集具有一定的代表性,可以使用数据库技术管理 2 、实现界面友好 3 、提交实验报告:实验题目、目的、数据集描述、实验环境、过程、结果和分析等。五、实验步骤 1 、所采用的数据集, 如图 1 所示: 数据挖掘实验报告 2 2、具体步骤构造决策树的方法是采用自上而下的递归构造,其思路是: 1) 以代表训练样本的单个结点开始建树(步骤 1)。 2) 如果样本都在同一类,则该结点成为树叶,并用该类标记(步骤 2和3)。 3) 否则, 算法使用称为信息增益的机遇熵的度量为启发信息, 选择能最好地将样本分类的属性(步骤 6) 。该属性成为该结点的“测试”或“判定”属性(步骤 7) 。值得注意的是,在这类算法中,所有的属性都是分类的,即取离散值的。连续值的属性必须离散化。 4) 对测试属性的每个已知的值,创建一个分支,并据此划分样本(步骤 8~10 )。 5) 算法使用同样的过程, 递归地形成每个划分上的样本决策树。一旦一个属性出现在一个结点上,就不必考虑该结点的任何后代(步骤 13)。 6) 递归划分步骤,当下列条件之一成立时停止: ①给定结点的所有样本属于同一类(步骤 2和3)。②没有剩余属性可以用来进一步划分样本(步骤 4) 。在此情况下,采用多数表决(步骤5)。这涉及将给定的结点转换成树叶, 并用 samples 中的多数所在类别标记它。换一种方式,可以存放结点样本的类分布。③分支 test_attribute=ai 没有样本。在这种情况下,以 samples 中的多数类创建一个树叶(步骤 12)。 Decision_Tree(samples,attribute_list) 输入由离散值属性描述的训练样本集 samples; 候选属性集合 attribute_list 。输出一棵决策树。 1)