1、昆明理工大學信息工程與自動化學院學生實驗報告（2011-2012學年第1學期）課程名稱：人工智能開課實驗室：信自樓計算機機房4442011年12月16日專業班級0學號200姓名成績實驗名稱天氣決策樹指導教師教該同學是否了解實驗原理：A.了解口B.基本了解口C.不了解口師該同學的實驗能力：A.強口B.中等C.差口該同學的實驗是否達到要求：A.達到口B.基本達到口C.未達到口”也小曰本包什A.規范口B.基本規范口C.不規范口評實驗相告杲否熱茶：語實驗過程是否詳細記錄：A.詳細口B.一般C.沒有口教師簽名：2011年12月日、上機目的及內容1.上機內容根據下列給定的14個數據，運用Informati

2、onGain構造一個天氣決策樹例子編號屬性分類天況溫度濕度風況1晴執八八大無N2晴執八、大有N3多云執八八大無P4雨中大無P5雨4/V正常無P6雨八y正常有N7多云4/V正常有P8晴中大無N9晴正常無P10雨中正常：無P11晴中正常有P12多云中大有P13多云執八八正常：無P14雨中大有N2.上機目的(1)學習用InformationGain構造決策樹的方法;(2)在給定的例子上，構造出正確的決策樹；(3)理解并掌握構造決策樹的技術要點。、實驗原理及基本技術路線圖(方框原理圖或程序流程圖)(1)設計并實現程序，構造出正確的決策樹；(2)對所設計的算法采用大0符號進行時間復雜性和空間復雜性分析;

3、主函數流程圖：*聞：ifsn諭inMuirEpkvAttributevalue.cpp流程圖iviiiTtiirvv.reiumiiLhe.*irowDfluiErExtepii.Basefun流程圖:letiirrHi;siiin-pinf?*l-nu2(p：<ib吧nfiutiKutn：Datapiont.cpp流程圖:ind-0>rdauLFeui嘰$T山心Std3EOUt«Bhll»ndL;Dataset主要流程圖:1iiri2。m_qplwAttribn陀sidir.sid:cout«wDaUi:M«s.i-0indaiaijdii

4、playl>ri三、所用儀器、材料（設備名稱、型號、規格等或使用軟件）1臺PC及VISUALC+6.0軟件四、實驗方法、步驟（或:程序代碼或操作過程）工程源代碼：Main.cpp:#inelude<fstream># include<iostream># include<list># include<sstream>#inelude<string>#include<vector>#include"AttributeValue.h"#include"DataPoint.hn#include

5、"DataSet.hnDataPointprocessLine(std:stringconst&sLine)(std:istringstreamisLine(sLine,std:istringstream:in);std:vector<AttributeValue>attributes;/TODO:needtohandlebeginningandendingemptyspaces.while(isLine.good()std:stringrawfield;isLine»rawfield;attributes.push_back(AttributeValu

6、e(rawfield);)AttributeValuev=attributes.back();attributes.pop_back();booltype=v.GetType();returnDataPoint(attributes,type);voidmain()std:ifstreamifs("in.txt",std:ifstream:in);DataSetinitDataset;while(ifs.good()/TODO:needtohandleemptylines.std:stringsLine;std:getline(ifs,sLine);initDataset.

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

8、or(inti=0;i<splittedDataSets.size();+i)floatprob=splittedDataSetsi.getPositiveProb();if(prob=0.0|prob=1.0)(finishedDataSet.push_back(splittedDataSetsi);)else(processQpushck(splittedDataSets)std:cout«"Thedicisiontreeis:"«std:endl;for(inti=0;i<finishedDataSet.size();+i)(finis

9、hedDataSeti.display();Attributevalue.cpp#includeHAttributeValue.hM#include"base.h"AttributeValue:AttributeValue(std:stringconst&instring):m_value(instring)(boolAttributeValue:GetType()(if(m_value="P”)returntrue;)elseif(m_value="N")-returnfalse;)elsethrowDataErrException(

10、);)Basefun.cpp:#include<math.h>floatIog2(floatx)(return1.0/Iog10(2)*Iog10(x);)floatcalEntropy(floatprob)(floatsum=0;if(prob=0|prob=1)return0;)sum-=prob*Iog2(prob);sum-=(1-prob)*Iog2(1-prob);returnsum;Datapiont.cpp:#include<iostream>#include"DataPoint.h"DataPoint:DataPoint(std:v

11、ector<AttributeValue>const&attributes,booltype):m_type(type)(for(inti=0;i<attributes.size();+i)(m_attributes.push_back(attributesi);voidDataPoint:display()(for(inti=0;i<m_attributes.size();+i)(std:cout«”t"«m_attributesi.getValue();一if(true=m_type)std:cout«ntP"

12、;)else(std:cout«"tNn;)std:cout«std:endl;Dataset.cpp:#include<iostream>#include<map>includeHbase.h"include"DataSet.h"voidSplitAttributeValue:display()std:cout«HtSplitattributeID(n«m_attributelndex«H)tH;std:cout«"Splitattributevalue(&q

13、uot;«m_v.getValue()«*')"«std:endl;voidDataSet:addDataPoint(DataPointconst&datapoint)m_data.push_back(datapoint);)floatDataSet:getPositiveProb()floatnPositive=0;for(inti=0;i<m_data.size();+i)(if(m_datai.isPositive()(nPositive+;returnnPositive/m_data.size();)一structStati

14、ntnPos;intnNeg;intid;)；voidDataSet:splitDataSet(std:vector<DataSet>&splittedSets)/findallavailablesplittingattributesintnAttributes=m_dataO.getNAttributes();inti,j;std:vector<bool>splittingAttributeBV;splittingAttributeBV.resize(nAttributes);for(i=0;i<nAttributes;+i)<splittingA

15、ttributeBVi=true;)for(i=0;i<m_splitAttributes.size();+i)(splittingAttributeBVm_splitAttributesi.getAttributelndex()=false;std:vector<int>splittingAttributelds;for(i=0;i<nAttributes;+i)if(true=splittingAttributeBVi)(splittingAttributelds.push_back(i);typedefstd:map<AttributeValue,Stat,

16、AttributeValueCmp>AttributeValueStat;typedefstd:map<AttributeValue,Stat,AttributeValueCmp>:iteratorAttributeValueStatJterator;typedefstd:map<AttributeValue,Stat,AttributeValueCmp>:const_iteratorAttributeValueStat_const_iterator;/gothroughdataonce,andcollectneededstatisticstocalculatee

17、ntropystd:vector<AttributeValueStat>splittingStats;splittingStats.resize(splittingAttributelds.size();for(i=0;i<m_data.size();+i)for(j=0;j<splittingAttributelds.size();+j)(AttributeValueconst&vm_datai.getAttribute(splittingAttributeldsj)；AttributeValueStatJteratorit=splittingStatsj.f

18、ind(v);if(splittingStatsj.end()=it)(Statstat;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);else(if(m_datai.isPositive()(it->second.nPos+;)elseit->second.nNeg+;/displaycollected

19、statisticsfor(j=0;j<splittingAttributelds.size();+j)(std:cout«"Attribute("«splittingAttributeldsj««std:endl;std:cout«AtValuetnPostnNeg"«std:endl;for(AttributeValueStat_const_iteratorit=splittingStatsj.begin();it!=splittingStatsj.end();+it)std:cout«

20、;Htn«it->first.getValue()«Ht"«it->second.nPos«ntn«it->second.nNeg«std:endl;/findsplittingattributefloatminEntropy=0.0;intsplitAttributeld=-1;for(j=0;j<splittingStats.size();+j)intn=m_data.size();floatentropy=0.0;for(AttributeValueStatJteratorit=splittin

21、gStatsj.begin();it!=splittingStatsj.end();+it)(intnSamples=it->second.nPos+it->second.nNeg;floatp=it->second.nPos;p/=nSamples;entropy+=calEntropy(p)*nSamples/n;if(entropy<minEntropy|-1=splitAttributeld)(minEntropy=entropy;splitAttributeld=j;std:cout « ”Split at attribute« split

22、tingAttributeldssplitAttributeld«”)«std:endl«std:endl;/splitintattrld=splittingAttributeldssplitAttributeld;AttributeValueStatconst&attVStat=splittingStatssplitAttributeld;splittedSets.clear();intk=0;for(AttributeValueStatJteratorit=splittingStatssplitAttributeld.begin();it!=split

23、tingStatssplitAttributeld.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_back(m_splitAttributesj);>for(AttributeValueStatJteratoritt=splittingStatssplitAttributeld.begin();itt!=splittingStatsspl

24、itAttributeld.end();+itt)(splittedSetsitt->second.id.m_splitAttributes.push_back(SplitAttributeValue(itt->first,attrld);for(i=0;i<m_data.size();+i)(AttributeValueconst&v=m_datai.getAttribute(attrld);AttributeValueStat_const_iteratorit=attVStat.find(v);if(attVStat.end()!=it)splittedSetsi

25、t->second.id.addDataPoint(m_datai);)else(throwDataErrException();voidDataSet:display()inti;std:cout«"Dataset(H«this«")"«std:endl;for(i=0;i<m_splitAttributes.size();+i)im_splitAttributesi.display();std:cout«"Data:"«std:endl;for(i=0;i<m_data.size();+i)<m_datai.display();)std:cout«std:e）五、實驗過程原始記錄（測試數據、圖表、計算等）Ifittti'ibuiteC-Ualu?nFos多云422nNeff032Ualue 4 E 執 八、 中Attribute<2： Ualue 古 正常 ftttv*ibwteA3A;ISdIUalue無有:at 七'nNeA122nNejj41nHecf230 tt rlbuiteXlA :Ualue、A執八、中fit