1、WORD格式實(shí)用昆明理工大學(xué)信息工程與自動(dòng)化學(xué)院學(xué)生實(shí)驗(yàn)報(bào)告（ 2011 2012學(xué)年 第1學(xué)期 ）課程名稱：人工智能開課實(shí)驗(yàn)室：信自樓計(jì)算機(jī)機(jī)房4442011年12 月16 日專業(yè)班級(jí) 0學(xué)號(hào)200姓名成績實(shí)驗(yàn)名稱天氣決策樹指導(dǎo)教師教該同學(xué)是否了解實(shí)驗(yàn)原理：A.了解B.基本了解C. 不了解該同學(xué)的實(shí)驗(yàn)?zāi)芰Γ篈.強(qiáng)B.中等C. 差師該同學(xué)的實(shí)驗(yàn)是否達(dá)到要求：A. 達(dá)到B.基本達(dá)到C. 未達(dá)到評(píng)實(shí)驗(yàn)報(bào)告是否規(guī)范：A. 規(guī)范B.基本規(guī)范C. 不規(guī)范語實(shí)驗(yàn)過程是否詳細(xì)記錄：A. 詳細(xì)B.一般C. 沒有教師簽名：2011年 12月日一、上機(jī)目的及內(nèi)容1.上機(jī)內(nèi)容根據(jù)下列給定的14 個(gè)數(shù)據(jù) ,運(yùn)用 In

2、formation Gain構(gòu)造一個(gè)天氣決策樹。屬 性例子編號(hào)分類天況溫度濕度風(fēng)況1晴熱大無N2晴熱大有N3多云熱大無P4雨中大無P5雨冷正常無P6雨冷正常有N7多云冷正常有P8晴中大無N9晴冷正常無P10雨中正常無P11晴中正常有P12多云中大有P專業(yè)資料整理WORD格式文檔專業(yè)資料整理WORD格式實(shí)用13多云熱正常無P14雨中大有N2. 上機(jī)目的（ 1）學(xué)習(xí)用 Information Gain構(gòu)造決策樹的方法；（ 2）在給定的例子上，構(gòu)造出正確的決策樹；（ 3）理解并掌握構(gòu)造決策樹的技術(shù)要點(diǎn)。二、實(shí)驗(yàn)原理及基本技術(shù)路線圖（方框原理圖或程序流程圖）（ 1）設(shè)計(jì)并實(shí)現(xiàn)程序，構(gòu)造出正確的決策樹；

3、（ 2）對所設(shè)計(jì)的算法采用大 O 符號(hào)進(jìn)行時(shí)間復(fù)雜性和空間復(fù)雜性分析；主函數(shù)流程圖：Attributevalue.cpp流程圖文檔專業(yè)資料整理WORD格式實(shí)用Basefun流程圖：Datapiont.cpp流程圖：Dataset主要流程圖：文檔專業(yè)資料整理WORD格式實(shí)用三、所用儀器、材料（設(shè)備名稱、型號(hào)、規(guī)格等或使用軟件）1 臺(tái) PC 及 VISUAL C+6.0軟件四、實(shí)驗(yàn)方法、步驟（或：程序代碼或操作過程）工程源代碼：Main.cpp:#include <fstream>#include <iostream>#include <list>文檔專業(yè)資料整

4、理WORD格式實(shí)用#include <sstream>#include <string>#include <vector>#include "AttributeValue.h"#include "DataPoint.h"#include "DataSet.h"DataPoint processLine(std:string const& sLine)std:istringstream isLine(sLine, std:istringstream:in);std:vector<Attr

5、ibuteValue> attributes;/ TODO: need to handle beginning and ending empty spaces.while( isLine.good() )std:string rawfield;isLine >> rawfield;attributes.push_back( AttributeValue( rawfield ) );文檔專業(yè)資料整理WORD格式實(shí)用AttributeValue v = attributes.back();attributes.pop_back();bool type = v.GetType();

6、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<DataSet> processQ;std

7、:vector<DataSet> finishedDataSet;文檔專業(yè)資料整理WORD格式實(shí)用processQ.push_back(initDataset);while ( processQ.size() > 0 )std:vector<DataSet> splittedDataSets;DataSet dataset = processQ.front();dataset.splitDataSet(splittedDataSets);processQ.pop_front();for (int i=0; i<splittedDataSets.size();

8、 +i)float prob = splittedDataSetsi.getPositiveProb();if (prob = 0.0 | prob = 1.0)finishedDataSet.push_back(splittedDataSetsi);elseprocessQ.push_back(splittedDataSetsi);文檔專業(yè)資料整理WORD格式實(shí)用std:cout << "The dicision tree is:" << std:endl;for (int i = 0; i < finishedDataSet.size();

9、 +i)finishedDataSeti.display();Attributevalue.cpp：#include "AttributeValue.h"#include "base.h"AttributeValue:AttributeValue(std:string const& instring): m_value(instring)bool AttributeValue:GetType()if (m_value = "P")return true;else if (m_value = "N")retu

10、rn false;elsethrow DataErrException();專業(yè)資料整理WORD格式文檔專業(yè)資料整理WORD格式實(shí)用Basefun.cpp:#include <math.h>float log2 (float x)return 1.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

11、;Datapiont.cpp:#include <iostream>#include "DataPoint.h"DataPoint:DataPoint(std:vector<AttributeValue> const& attributes, bool type): m_type(type)for (int i=0; i<attributes.size(); +i)m_attributes.push_back( attributesi );void DataPoint:display()for (int i=0; i<m_attr

12、ibutes.size(); +i)專業(yè)資料整理WORD格式std:cout << "t" << m_attributesi.getValue();文檔專業(yè)資料整理WORD格式實(shí)用if (true = m_type)std:cout << "tP"elsestd:cout << "tN"std:cout << std:endl;Dataset.cpp:#include <iostream>#include <map>#include "bas

13、e.h"#include "DataSet.h"void SplitAttributeValue:display()std:cout << "tSplit attribute ID(" << m_attributeIndex << ")t"std:cout << "Split attribute value(" << m_v.getValue() << ")" << std:endl;void Data

14、Set:addDataPoint(DataPoint const& datapoint)m_data.push_back(datapoint);float DataSet:getPositiveProb()float nPositive = 0;for(int i=0; i<m_data.size(); +i)if ( m_datai.isPositive() )nPositive+;專業(yè)資料整理WORD格式return nPositive / m_data.size();文檔專業(yè)資料整理WORD格式實(shí)用struct Statint nPos;int nNeg;int id;vo

15、id DataSet:splitDataSet(std:vector<DataSet>& splittedSets)/ find all available splitting attributesint nAttributes = m_data0.getNAttributes();int i, j;std:vector<bool> splittingAttributeBV;splittingAttributeBV.resize(nAttributes);for (i=0; i<nAttributes; +i)splittingAttributeBVi =

16、 true;for (i=0; i<m_splitAttributes.size(); +i)splittingAttributeBV m_splitAttributesi.getAttributeIndex() = false;std:vector<int> splittingAttributeIds;for (i=0; i<nAttributes; +i)if (true = splittingAttributeBVi)splittingAttributeIds.push_back(i);typedef std:map<AttributeValue, Stat

17、, AttributeValueCmp> AttributeValueStat; typedef std:map<AttributeValue, Stat, AttributeValueCmp>:iteratorAttributeValueStat_iterator;typedefstd:map<AttributeValue,Stat,AttributeValueCmp>:const_iterator專業(yè)資料整理WORD格式AttributeValueStat_const_iterator;/ go through data once, and collect n

18、eeded statistics to calculate entropy std:vector< AttributeValueStat > splittingStats;splittingStats.resize( splittingAttributeIds.size() );文檔專業(yè)資料整理WORD格式實(shí)用for (i=0; i<m_data.size(); +i)for (j=0; j<splittingAttributeIds.size(); +j)AttributeValueconst&v=m_datai.getAttribute(splittingA

19、ttributeIdsj);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;stat.nNeg = 1;stat.id = 0;splittingStatsj.insert(std:pair<AttributeValue, Stat>(v, stat);elseif

20、 ( m_datai.isPositive() )it->second.nPos+;elseit->second.nNeg+;/ display collected statisticsfor (j=0; j<splittingAttributeIds.size(); +j)專業(yè)資料整理WORD格式std:cout << "Attribute(" << splittingAttributeIdsj <<"):" << std:endl; std:cout << "tV

21、alue t nPos tnNeg" << std:endl;for (AttributeValueStat_const_iterator it =splittingStatsj.begin(); it !=splittingStatsj.end(); +it)文檔專業(yè)資料整理WORD格式實(shí)用std:cout << "t" << it->first.getValue() << " t " << it->second.nPos <<" t "

22、<< it->second.nNeg << std:endl;/findsplittingattributefloatminEntropy=0.0;intsplitAttributeId=-1;for (j=0; j<splittingStats.size(); +j)int n = m_data.size();float entropy = 0.0;for (AttributeValueStat_iterator it =splittingStatsj.begin(); it !=splittingStatsj.end(); +it)int nSample

23、s = 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;splitAttributeId = j;std:cout << "Split at attribute(" << splittingAttributeId

24、ssplitAttributeId << ")"<< std:endl << std:endl;/ splitint attrId = splittingAttributeIdssplitAttributeId;AttributeValueStat const& attVStat =splittingStatssplitAttributeId;splittedSets.clear();專業(yè)資料整理WORD格式int k = 0;for (AttributeValueStat_iterator it =splittingStatss

25、plitAttributeId.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)文檔專業(yè)資料整理WORD格式實(shí)用splittedSetsi.m_splitAttributes.push_back( 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 const& v = m_datai.getAttribute(attrId);Attrib