昆明理工大學(xué)天氣決策樹

1、昆明理工大學(xué)信息工程與自動(dòng)化學(xué)院學(xué)生實(shí)驗(yàn)報(bào)告（ 學(xué)年 第 1 學(xué)期 ）課程名稱：人工智能 開課實(shí)驗(yàn)室： 信自樓 504年 12 月 24 日年級(jí)、專業(yè)、班學(xué)號(hào)姓名成績實(shí)驗(yàn)項(xiàng)目名稱天氣決策樹指導(dǎo)教師吳霖教師 評(píng) 語該同學(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á)到實(shí)驗(yàn)報(bào)告是否規(guī)范：A.規(guī)范B.基本規(guī)范C.不規(guī)范實(shí)驗(yàn)過程是否詳細(xì)記錄：A.詳細(xì)B.一般 C.沒有 教師簽名： 年月日、上機(jī)目的及內(nèi)容1.上機(jī)內(nèi)容 根據(jù)下列給定的 14 個(gè)數(shù)據(jù) ,運(yùn)用 Information Gain 構(gòu)造一個(gè)天氣決策

2、樹。例子編號(hào)屬性分類天況溫度濕度風(fēng)況1晴熱大無N2晴熱大有N3多云熱大無P4雨中大無P5雨冷正常無P6雨冷正常有N7多云冷正常有P8晴中大無N9晴冷正常無P10雨中正常無P11晴中正常有P12多云中大有P13多云熱正常無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)造出正確的決策樹；（ 2）對所設(shè)計(jì)的算法采用大 O 符號(hào)進(jìn)行時(shí)間復(fù)雜性和空間復(fù)雜性分析；實(shí)驗(yàn)考慮到幾個(gè)屬性：天況晴、雨

3、、多云； 溫度熱、中、冷； 濕度大、正常； 風(fēng)況 有、無；然后根據(jù)每個(gè)屬性來算出信息增益，接下來我們根據(jù)信息增益最大的來進(jìn)行劃分。根據(jù)問 題設(shè)計(jì)算法，建立數(shù)據(jù)結(jié)構(gòu)，設(shè)計(jì)需要用的類，然后通過編程實(shí)現(xiàn)問題求解。了解和求解最大信息增益 和最小熵選擇平均熵最小的屬性作為根節(jié)點(diǎn)，用同樣的方法選擇其他節(jié)點(diǎn)直至形成整個(gè)決策樹。 dataset 就是具體的劃分過程，首先找到可用的劃分項(xiàng)目，再第一次劃分之后再相關(guān)的數(shù)據(jù)來計(jì)算熵。Attributevalue 函數(shù)流程圖Datapiont 函數(shù)流程圖三、所用儀器、材料（設(shè)備名稱、型號(hào)、規(guī)格等或使用軟件）1臺(tái) PC及VISUAL C+軟件四、實(shí)驗(yàn)方法、步驟（或：程序

4、代碼或操作過程）源代碼：main 函數(shù)：#include <fstream>#include <iostream>#include <list>#include <sstream>#include <string>#include <vector>#include ""#include ""#include ""DataPoint processLine(std:string const& sLine) std:istringstream isLine(s

5、Line, std:istringstream:in); std:vector<AttributeValue> attributes;while( () )std:string rawfield; isLine >> rawfield; ( AttributeValue( rawfield ) );AttributeValue v = ();();bool type = ();return DataPoint(attributes, type);void main()std:ifstream ifs("", std:ifstream:in);Data

6、Set initDataset;while( () )std:string sLine; std:getline(ifs, sLine); ( processLine(sLine) );std:list<DataSet> processQ; std:vector<DataSet> finishedDataSet;(initDataset);while ( () > 0 ) std:vector<DataSet> splittedDataSets;DataSet dataset = ();(splittedDataSets);();for (int i=

7、0; i<(); +i)float prob = splittedDataSetsi.getPositiveProb();if (prob = | prob =(splittedDataSetsi);else(splittedDataSetsi);std:cout << "The dicision tree is:" << std:endl; for (int i = 0; i < (); +i)finishedDataSeti.display();DataSet 函數(shù)：#include <iostream>#include

8、<map>#include ""#include ""void SplitAttributeValue:display()std:cout << "tSplit attribute ID(" << m_attributeIndex << ")t" std:cout << "Split attribute value(" << () << ")" << std:endl;void D

9、ataSet:addDataPoint(DataPoint const& datapoint)(datapoint);float DataSet:getPositiveProb()float nPositive = 0;for(int i=0; i<(); +i)if ( m_datai.isPositive() )nPositive+;return nPositive / ();struct Statint nPos;int nNeg;int id;void DataSet:splitDataSet(std:vector<DataSet>& splitted

10、Sets)etNAttributes();int i, j;std:vector<bool> splittingAttributeBV;(nAttributes);for (i=0; i<nAttributes; +i) splittingAttributeBVi = true;for (i=0; i<(); +i)splittingAttributeBV m_splitAttributesi.getAttributeIndex() = false; std:vector<int> splittingAttributeIds;for (i=0; i<n

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

12、st_iterator AttributeValueStat_const_iterator;etAttribute(splittingAttributeIdsj);AttributeValueStat_iterator it = splittingStatsj.find(v); if ( splittingStatsj.end() = it )Stat stat;if ( m_datai.isPositive() )= 1;= 0;= 0;else= 0;= 1;= 0;splittingStatsj.insert(std:pair<AttributeValue, Stat>(v,

13、 stat);elseif ( m_datai.isPositive() )it->+;elseit->+;egin();it != splittingStatsj.end(); +it)std:cout << "t" << it->() << " t " << it-> << " t " << it-> << std:endl; egin();it != splittingStatsj.end(); +it)int nS

14、amples = it-> + it->float p = it->p /= nSamples;entropy += calEntropy(p) * nSamples / n; if (entropy < minEntropy | -1 = splitAttributeId)minEntropy = entropy; splitAttributeId = j;std:cout << "Split at attribute(" << splittingAttributeIdssplitAttributeId << &

15、quot;)" << std:endl <<std:endl;egin();it != splittingStatssplitAttributeId.end(); +it) it-> = k+;( k);for (i=0; i<k; +i)for (j=0; j<(); +j)splittedSetsi.( m_splitAttributesj );for (AttributeValueStat_iterator itt = splittingStatssplitAttributeId.begin(); itt != splittingSta

16、tssplitAttributeId.end(); +itt) splittedSetsitt->.(SplitAttributeValue(itt->first, attrId);for (i=0; i<(); +i)AttributeValue const& v = m_datai.getAttribute(attrId); AttributeValueStat_const_iterator it = (v);if ( () != it ) splittedSetsit->.addDataPoint(m_datai); else throw DataErrE

17、xception();void DataSet:display()int i;std:cout << "Dataset(" << this << ")" << std:endl;for (i=0; i<(); +i) m_splitAttributesi.display();std:cout << "Data:" << std:endl;for (i=0; i<(); +i) m_datai.display();std:cout << st

18、d:endl;DataPoint 函數(shù)：#include <>float log2 (float x)return / 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 函數(shù)：#include <>float log2 (float x)return / log10(2) *

19、 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;AttributeValue 函數(shù)：#include ""#include ""AttributeValue:AttributeValue(std:string const& instring): m_value(instring)bo

20、ol AttributeValue:GetType()if (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&

21、instring);bool GetType();std:string const& getValue() constreturn m_value;private:std:string m_value;struct AttributeValueCmpbool operator() (AttributeValue const& lhs, AttributeValue const& rhs) constreturn () < ();#endifBase 頭文件：class DataErrException : public std:exception;float ca

22、lEntropy(float prob);DataPoint 頭文件：#ifndef DATA_POINT_H_#define DATA_POINT_H_#include <vector>#include ""class DataPointpublic:DataPoint(std:vector<AttributeValue> const& attributes, bool type); bool isPositive()return m_type;int getNAttributes()return ();AttributeValue con

23、st& getAttribute(int index)return m_attributesindex;void display();private:std:vector<AttributeValue> m_attributes;bool m_type;#endifDataSet 頭文件：#include <map>#include <utility>#include ""class SplitAttributeValuepublic:SplitAttributeValue(AttributeValue v, int id): m

24、_v(v), m_attributeIndex(id)int getAttributeIndex()return m_attributeIndex;void display();private:int m_attributeIndex;AttributeValue m_v;class DataSetpublic:void addDataPoint(DataPoint const& datapoint);float getPositiveProb();void splitDataSet(std:vector<DataSet>& splittedSets); void display();private:std:vector<SplitAttributeVal