实验二--分类挖掘算法(ID3).docx

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

8~10）。
5)算法使用同样的过程， 递归地形成每个划分上的样本决策树。

一旦一个属性出现在一
个结点上，就不必考虑该结点的任何后代（步骤 13）。
6)递归划分步骤，当下列条件之一成立时停止：
①给定结点的所有样本属于同一类（步骤 2和 3）。
②没有剩余属性可以用来进一步划分样本（步骤 4）。在此情况下，采用多数表决（步
骤 5）。这涉及将给定的结点转换成树叶， 并用 samples 中的多数所在类别标记它。 换一种方式，可以存放结点样本的类分布。
③分支 test_attribute=ai 没有样本。 在这种情况下， 以 samples 中的多数类