决策树 实验报告

决策树实验

一、实验原理

决策树是一个类似于流程图的树结构，其中每个内部结点表示在一个属性上的测试，每个分支代表一个测试输入，而每个树叶结点代表类或类分布。数的最顶层结点是根结点。一棵典型的决策树如图1所示。它表示概念buys_computer，它预测顾客是否可能购买计算机。内部结点用矩形表示，而树叶结点用椭圆表示。为了对未知的样本分类，样本的属性值在决策树上测试。决策树从根到叶结点的一条路径就对应着一条合取规则，因此决策树容易转化成分类规则。

图1

ID3算法：

■ 决策树中每一个非叶结点对应着一个非类别属性，树枝代表这个属性的值。一个叶结点代表从树根到叶结点之间的路径对应的记录所属的类别属性值。

■ 每一个非叶结点都将与属性中具有最大信息量的非类别属性相关联。

■ 采用信息增益来选择能够最好地将样本分类的属性。

信息增益基于信息论中熵的概念。ID3总是选择具有最高信息增益（或最大熵压缩）的属性作为当前结点的测试属性。该属性使得对结果划分中的样本分类所需的信息量最小，并反映划分的最小随机性或“不纯性”。

二、算法伪代码

算法Decision_Tree(data,AttributeName)

输入由离散值属性描述的训练样本集data;

候选属性集合AttributeName。

输出一棵决策树。

（1） 创建节点N；

（2） If samples 都在同一类C中then

（3） 返回N作为叶节点，以类C标记；

（4） If attribute_list为空then

（5） 返回N作为叶节点，以samples 中最普遍的类标记；//多数表决

（6） 选择attribute_list 中具有最高信息增益的属性test_attribute;

（7） 以test_attribute 标记节点N；

共 页 第 页 计算机科学与技术学院 数据结构 实验报告

班级 2014级计算机1班

学号

20144138021 姓名 张建华

成绩

实验项目 简单哈夫曼编/译码的设计与实现 实验日期 2016.1.5

一、实验目的

本实验的目的是进一步理解哈夫曼树的逻辑结构和存储结构，进一步提高使用理论知识指导解决实际问题的能力。

二、实验问题描述

利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码，此实验即设计这样的一个简单编/码系统。系统应该具有如下的几个功能：

1、接收原始数据。

从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmtree.dat中。

2、编码。

利用已建好的哈夫曼树（如不在内存，则从文件hfmtree.dat中读入），对文件中的正文进行编码，然后将结果存入文件codefile.dat中。

3、译码。

利用已建好的哈夫曼树将文件codefile.dat中的代码进行译码，结果存入文件textfile.dat中。

4、打印编码规则。

即字符与编码的一一对应关系。

5、打印哈夫曼树，

将已在内存中的哈夫曼树以直观的方式显示在终端上。

三、实验步骤

1、实验问题分析

1、构造哈夫曼树时使用静态链表作为哈夫曼树的存储。

在构造哈夫曼树时，设计一个结构体数组HuffNode保存哈夫曼树中各结点的信息，根据二叉树的性质可知，具有n个叶子结点的哈夫曼树共有2n-1个结点，所以数组HuffNode的大小设置为2n-1，描述结点的数据类型为：

Typedef strcut

决策树程序实验

众所周知，数据库技术从20世纪80年代开始，已经得到广泛的普及和应用。随着数据库容量的膨胀，特别是数据仓库以及web等新型数据源的日益普及，人们面临的主要问题不再是缺乏足够的信息可以使用，而是面对浩瀚的数据海洋如何有效地利用这些数据。

从数据中生成分类器的一个特别有效的方法是生成一个决策树（Decision

Tree）。决策树表示方法是应用最广泛的逻辑方法之一，它从一组无次序、无规则的事例中推理出决策树表示形式的分类规则。决策树分类方法采用自顶向下的递归方式，在决策树的内部结点进行属性值的比较并根据不同的属性值判断从该结点向下的分支，在决策树的叶结点得到结论。所以从决策树的根到叶结点的一条路径就对应着一条合取规则，整棵决策树就对应着一组析取表达式规则。

决策树是应用非常广泛的分类方法，目前有多种决策树方法，如ID3、CN2、SLIQ、SPRINT等。

一、问题描述

相关信息

决策树是一个类似于流程图的树结构，其中每个内部结点表示在一个属性上的测试，每个分支代表一个测试输入，而每个树叶结点代表类或类分布。数的最顶层结点是根结点。一棵典型的决策树如图1所示。它表示概念buys_computer，它预测顾客是否可能购买计算机。内部结点用矩形表示，而树叶结点用椭圆表示。为了对未知的样本分类，样本的属性值在决策树上测试。决策树从根到叶结点的一条路径就对应着一条合取规则，因此决策树容易转化成分类规则。

图1

ID3算法：

■ 决策树中每一个非叶结点对应着一个非类别属性，树枝代表这个属性的值。一个叶结点代表从树根到叶结点之间的路径对应的记录所属的类别属性值。

■ 每一个非叶结点都将与属性中具有最大信息量的非类别属性相关联。

■ 采用信息增益来选择能够最好地将样本分类的属性。

信息增益基于信息论中熵的概念。ID3总是选择具有最高信息增益（或最大熵压缩）的属性作为当前结点的测试属性。该属性使得对结果划分中的样本分类所需的信息量最小，并反映划分的最小随机性或“不纯性”。

-1- 昆明理工大学信息工程与自动化学院学生实验报告

（ 201 — 201 学年 第 1 学期 ）

课程名称：人工智能 开课实验室： 年 月 日

年级、专业、班 学号 姓名 成绩

实验项目名称 天气决策树 指导教师

教师评语

该同学是否了解实验原理： A.了解□ B.基本了解□ C.不了解□

该同学的实验能力： A.强 □ B.中等 □ C.差 □

该同学的实验是否达到要求： A.达到□ B.基本达到□ C.未达到□

实验报告是否规范： A.规范□ B.基本规范□ C.不规范□

实验过程是否详细记录： A.详细□ B.一般 □ C.没有 □

教师签名：

年 月 日

一、上机目的及内容

1.上机内容

根据下列给定的14个数据,运用Information Gain构造一个天气决策树。

例子编号 属 性 分类 天况 温度 湿度 风况

1 晴 热 大 无 N

2 晴 热 大 有 N

3 多云 热 大 无 P

4 雨 中 大 无 P

5 雨 冷 正常 无 P

6 雨 冷 正常 有 N

7 多云 冷 正常 有 P

8 晴 中 大 无 N

-2- 9 晴 冷 正常 无 P

10 雨 中 正常 无 P

11 晴 中 正常 有 P

12 多云 中 大 有 P

13 多云 热 正常 无 P

14 雨 中 大 有 N

2.上机目的

（1）学习用Information Gain构造决策树的方法；

（2）在给定的例子上，构造出正确的决策树；

（3）理解并掌握构造决策树的技术要点。