昆明理工大学 天气决策树

1、昆明理工大学信息工程与自动化学院学生实验报告（ 学年 第1学期 ）课程名称：人工智能 开课实验室：信自楼504 年12月 24日年级、专业、班学号姓名成绩实验项目名称天气决策树指导教师 吴霖教师评语该同学是否了解实验原理：A.了解B.基本了解C.不了解该同学的实验能力：A.强 B.中等 C.差 该同学的实验是否达到要求：A.达到B.基本达到C.未达到实验报告是否规范：A.规范B.基本规范C.不规范实验过程是否详细记录：A.详细B.一般 C.没有 教师签名： 年 月 日一、上机目的及内容1.上机内容根据下列给定的14个数据,运用Information Gain构造一个天气决策树。例子编号属 性分

2、类天况温度湿度风况1晴热大无N2晴热大有N3多云热大无P4雨中大无P5雨冷正常无P6雨冷正常有N7多云冷正常有P8晴中大无N9晴冷正常无P10雨中正常无P11晴中正常有P12多云中大有P13多云热正常无P14雨中大有N2.上机目的（1）学习用Information Gain构造决策树的方法；（2）在给定的例子上，构造出正确的决策树；（3）理解并掌握构造决策树的技术要点。二、实验原理及基本技术路线图（方框原理图或程序流程图）（1）设计并实现程序，构造出正确的决策树；（2）对所设计的算法采用大O符号进行时间复杂性和空间复杂性分析；实验考虑到几个属性：天况晴、雨、多云； 温度热、中、冷； 湿度大、正

3、常； 风况有、无；然后根据每个属性来算出信息增益，接下来我们根据信息增益最大的来进行划分。根据问题设计算法，建立数据结构，设计需要用的类，然后通过编程实现问题求解。了解和求解最大信息增益和最小熵选择平均熵最小的属性作为根节点，用同样的方法选择其他节点直至形成整个决策树。dataset就是具体的划分过程，首先找到可用的划分项目，再第一次划分之后再相关的数据来计算熵。 Main函数流程图 Dataset函数主要流程图 Basefun函数流程图Attributevalue函数流程图Datapiont函数流程图三、所用仪器、材料（设备名称、型号、规格等或使用软件）1台PC及VISUAL C+6.0软件

4、四、实验方法、步骤（或：程序代码或操作过程）源代码：main函数：#include <fstream>#include <iostream>#include <list>#include <sstream>#include <string>#include <vector>#include "AttributeValue.h"#include "DataPoint.h"#include "DataSet.h"DataPoint processLine(std:st

5、ring const& sLine)std:istringstream isLine(sLine, std:istringstream:in);std:vector<AttributeValue> attributes;/ TODO: need to handle beginning and ending empty spaces.while( isLine.good() )std:string rawfield;isLine >> rawfield;attributes.push_back( AttributeValue( rawfield ) );Attri

6、buteValue v = attributes.back();attributes.pop_back();bool type = v.GetType();return DataPoint(attributes, type);void main()std:ifstream ifs("tree.txt", std:ifstream:in);DataSet initDataset;while( ifs.good() )/ TODO: need to handle empty lines.std:string sLine;std:getline(ifs, sLine);initD

7、ataset.addDataPoint( processLine(sLine) );std:list<DataSet> processQ;std:vector<DataSet> finishedDataSet;processQ.push_back(initDataset);while ( processQ.size() > 0 )std:vector<DataSet> splittedDataSets;DataSet dataset = processQ.front();dataset.splitDataSet(splittedDataSets);pr

8、ocessQ.pop_front();for (int i=0; i<splittedDataSets.size(); +i)float prob = splittedDataSetsi.getPositiveProb();if (prob = 0.0 | prob = 1.0)finishedDataSet.push_back(splittedDataSetsi);elseprocessQ.push_back(splittedDataSetsi);std:cout << "The dicision tree is:" << std:endl;

9、for (int i = 0; i < finishedDataSet.size(); +i)finishedDataSeti.display();DataSet函数：#include <iostream>#include <map>#include "base.h"#include "DataSet.h"void SplitAttributeValue:display()std:cout << "tSplit attribute ID(" << m_attributeIndex

10、<< ")t"std:cout << "Split attribute value(" << m_v.getValue() << ")" << std:endl;void DataSet:addDataPoint(DataPoint const& datapoint)m_data.push_back(datapoint);float DataSet:getPositiveProb()float nPositive = 0;for(int i=0; i<m_dat

11、a.size(); +i)if ( m_datai.isPositive() )nPositive+;return nPositive / m_data.size();struct Statint nPos;int nNeg;int id;void DataSet:splitDataSet(std:vector<DataSet>& splittedSets)/ find all available splitting attributesint nAttributes = m_data0.getNAttributes();int i, j;std:vector<boo

12、l> splittingAttributeBV;splittingAttributeBV.resize(nAttributes);for (i=0; i<nAttributes; +i)splittingAttributeBVi = true;for (i=0; i<m_splitAttributes.size(); +i)splittingAttributeBV m_splitAttributesi.getAttributeIndex() = false;std:vector<int> splittingAttributeIds;for (i=0; i<n

13、Attributes; +i)if (true = splittingAttributeBVi)splittingAttributeIds.push_back(i);typedef std:map<AttributeValue, Stat, AttributeValueCmp> AttributeValueStat;typedef std:map<AttributeValue, Stat, AttributeValueCmp>:iterator AttributeValueStat_iterator;typedef std:map<AttributeValue,

14、Stat, AttributeValueCmp>:const_iterator AttributeValueStat_const_iterator;/ go through data once, and collect needed statistics to calculate entropystd:vector< AttributeValueStat > splittingStats;splittingStats.resize( splittingAttributeIds.size() );for (i=0; i<m_data.size(); +i)for (j=0

15、; j<splittingAttributeIds.size(); +j)AttributeValue const& v = m_datai.getAttribute(splittingAttributeIdsj);AttributeValueStat_iterator it = splittingStatsj.find(v);if ( splittingStatsj.end() = it )Stat stat;if ( m_datai.isPositive() )stat.nPos = 1;stat.nNeg = 0;stat.id = 0;elsestat.nPos = 0;

16、stat.nNeg = 1;stat.id = 0;splittingStatsj.insert(std:pair<AttributeValue, Stat>(v, stat);elseif ( m_datai.isPositive() )it->second.nPos+;elseit->second.nNeg+;/ display collected statisticsfor (j=0; j<splittingAttributeIds.size(); +j)std:cout << "Attribute(" << sp

17、littingAttributeIdsj << "):" << std:endl;std:cout << "tValue t nPos t nNeg" << std:endl;for (AttributeValueStat_const_iterator it = splittingStatsj.begin();it != splittingStatsj.end(); +it)std:cout << "t" << it->first.getValue() &l

18、t;< " t " << it->second.nPos << " t " << it->second.nNeg << std:endl;/ find splitting attributefloat minEntropy = 0.0;int splitAttributeId = -1;for (j=0; j<splittingStats.size(); +j)int n = m_data.size();float entropy = 0.0;for (AttributeValueS

19、tat_iterator it = splittingStatsj.begin();it != splittingStatsj.end(); +it)int nSamples = it->second.nPos + it->second.nNeg;float p = it->second.nPos;p /= nSamples;entropy += calEntropy(p) * nSamples / n;if (entropy < minEntropy | -1 = splitAttributeId)minEntropy = entropy;splitAttribute

20、Id = j;std:cout << "Split at attribute(" << splittingAttributeIdssplitAttributeId << ")" << std:endl << std:endl;/ splitint attrId = splittingAttributeIdssplitAttributeId;AttributeValueStat const& attVStat = splittingStatssplitAttributeId;splitte

21、dSets.clear();int k = 0;for (AttributeValueStat_iterator it = splittingStatssplitAttributeId.begin();it != splittingStatssplitAttributeId.end(); +it)it->second.id = k+;splittedSets.resize( k);for (i=0; i<k; +i)for (j=0; j<m_splitAttributes.size(); +j)splittedSetsi.m_splitAttributes.push_bac

22、k( m_splitAttributesj );for (AttributeValueStat_iterator itt = splittingStatssplitAttributeId.begin();itt != splittingStatssplitAttributeId.end(); +itt)splittedSetsitt->second.id.m_splitAttributes.push_back(SplitAttributeValue(itt->first, attrId);for (i=0; i<m_data.size(); +i)AttributeValue

23、 const& v = m_datai.getAttribute(attrId);AttributeValueStat_const_iterator it = attVStat.find(v);if ( attVStat.end() != it )splittedSetsit->second.id.addDataPoint(m_datai);elsethrow DataErrException();void DataSet:display()int i;std:cout << "Dataset(" << this << &q

24、uot;)" << std:endl;for (i=0; i<m_splitAttributes.size(); +i)m_splitAttributesi.display();std:cout << "Data:" << std:endl;for (i=0; i<m_data.size(); +i)m_datai.display();std:cout << std:endl;DataPoint函数：#include <math.h> float log2 (float x)return 1.

25、0 / log10(2) * log10(x);float calEntropy(float prob)float sum=0; if (prob = 0 | prob = 1)return 0;sum -= prob * log2(prob);sum -= (1 - prob) * log2 ( 1 - prob );return sum;Basefun函数：#include <math.h> float log2 (float x)return 1.0 / log10(2) * log10(x);float calEntropy(float prob)float sum=0;

26、if (prob = 0 | prob = 1)return 0;sum -= prob * log2(prob);sum -= (1 - prob) * log2 ( 1 - prob );return sum;AttributeValue函数：#include "AttributeValue.h"#include "base.h"AttributeValue:AttributeValue(std:string const& instring):m_value(instring)bool AttributeValue:GetType()if (

27、m_value = "P")return true;else if (m_value = "N")return false;elsethrow DataErrException();AttributeValue头文件：#ifndef ATTRIBUTE_VALUE_H_#define ATTRIBUTE_VALUE_H_#include <string>class AttributeValuepublic:AttributeValue(std:string const& instring);bool GetType();std:str

28、ing const& getValue() constreturn m_value;private:std:string m_value;struct AttributeValueCmpbool operator() (AttributeValue const& lhs, AttributeValue const& rhs) constreturn lhs.getValue() < rhs.getValue();#endifBase头文件：class DataErrException : public std:exception;float calEntropy(

29、float prob);DataPoint头文件：#ifndef DATA_POINT_H_#define DATA_POINT_H_#include <vector>#include "AttributeValue.h"class DataPointpublic:DataPoint(std:vector<AttributeValue> const& attributes, bool type);bool isPositive()return m_type;int getNAttributes()return m_attributes.size();AttributeValue const& getAttribute(int index)return m_attributesindex;void display