2013 年秋季学期研究生课程考核
（读书报告、研究报告）
考核科目:人工智能实验报告（二）学生所在院（系）:计算机学院
学生所在学科:计算机科学与技术
学生姓名:
学号:
学生类别:学术
考核结果阅卷人
一．问题描述
决策树是最简单的但是最成功的学习算法形式之一，一个决策树将用属性集合描述的事物或情景作为输入，并返回一个“决策”作为输入的预测的输出值，输入的属性值可以使离散的，也可以是连续的，实验中我们使用的是离散的数据，决策树通过执行一个测试序列来得到它的决策。
下面为实验数据,运用Information Gain构造一个天气决策树。
二、算法介绍及程序流程图
（1）设计并实现程序，构造出正确的决策树，实验考虑到几个属性：天况——晴、雨、多云；温度——热、中、冷；湿度——大、正常；风况——有、无；然后根据每个属性来算出信息增益，接下来我们根据信息增益最大的来进行划分。根据问题设计算法，建立数据结构，设计需要用的类，然后通过编程实现问题求解。了解和求解最大信息增益和最小熵选择平均熵最小的属性作为根节点，用同样的方法选择其他节点直至形成整个决策树。dataset就是具体的划分过程，首先找到可用的划分项目，再第一次划分之后再相关的数据来计算熵。
问题分许：天况——晴、雨、多云
温度——热、中、冷
湿度——大、正常
风况——有、无
首先我们要根据每个属性来算出信息增益，接下来我们根据信息增益最大的来进行划分。
选择一个属性，根据该Information Gain把数据分割为K份。分许如下：
数据集
计算
数据集列表
（2）主要函数流程图：
Basefun流程图
三、算法实现
1.实验环境
一台PC及VISUAL C++6.0软件2.部分程序代码
Main.cpp:
#include
#include
#include
#include
#include
#include
#include "AttributeValue.h"
#include "DataPoint.h"
#include "DataSet.h"
DataPoint processLine(std::string const& sLine)
{
std::istringstream isLine(sLine, std::istringstream::in);
std::vector attributes;
// TODO: need to handle beginning and ending empty spaces.
while( isLine.good() )
{
std::string rawfield;
isLine >> rawfield;
attributes.push_back( AttributeValue( rawfield ) );
}
AttributeValue v = attributes.back();
attributes.pop_back();
bool type = v.GetType();
return DataPoint(attributes, type);
}
void main()
std::ifstream ifs("in.txt", std::ifstream::in);
DataSet initDataset;
while( ifs.good() )
{
// TODO: need to handle empty lines.
std::string sLine;
std::getline(ifs, sLine);
initDataset.addDataPoint( processLine(sLine) );
}
std::list processQ;
std::vector finishedDataSet;
processQ.push_back(initDataset);
while ( processQ.size() > 0 )
{
std::vector splittedDataSets;
DataSet dataset = processQ.front();
dataset.splitDataSet(splittedDataSets);
processQ.pop_front();
for (int i=0; i{
float prob = splittedDataSets[i].getPositiveProb();
if (prob == 0.0 || prob == 1.0)
{
finishedDataSet.push_back(splittedDataSets[i]);
}
else
{
processQ.push_back(splittedDataSets[i]);
}
}
}
std::cout << "The dicision tree is:" << std::endl;
for (int i = 0; i < finishedDataSet.size(); ++i)
{
finishedDataSet[i].display();
}
}
Basefun.cpp:
#include
float log2 (float x)
{
return 1.0 / log10(2) * log10(x);
}
float calEntropy(float prob)
{
float sum=0;
if (prob == 0 || prob == 1)
{
