機(jī)器學(xué)習(xí)試驗(yàn)報(bào)告材料

1、®) 0芟郵歌大爭(zhēng)KMhU沖ZE MITV DFPafiTfi A rCLECOMHUNICATIDNt機(jī)器學(xué)習(xí)課實(shí)驗(yàn)報(bào)告ID算法實(shí)現(xiàn)決策樹2015 -2016學(xué)年第2學(xué)期專業(yè):智能科學(xué)與技術(shù)班級(jí):學(xué)號(hào):智能1301班06133029爭(zhēng)輝一、實(shí)驗(yàn)?zāi)康模豪斫釯D3算法的基本原理，并且編程實(shí)現(xiàn)。二、實(shí)驗(yàn)要求：使用C/C+/MATLAB實(shí)現(xiàn)ID3算法。輸入：若干行，每行5個(gè)字符串，表示Outlook Temp erature Humidity Wind P lay ball 如上表。輸出：決策樹。實(shí)驗(yàn)結(jié)果如下:輸入：SunnyHotHighWeak 1NoSunnyHotHighStro

2、ngNoOvercastHotHighWeakYesRai nMildHighWeak YesRai nCoolNormalWeakYesRai nCoolNormalStro ngNoOvercastCoolNormalStro ng YeSunnyMildHighWeakNoSunnyCoolNormalWeakYesRai nMildNormalWeakYesSunnyMildNormalStro ngYesOvercastMildHighStro ngYesOvercastHotNormalWeak YesRai nMildHighStro ngNo輸出:OutlookRainWind

3、OvercastYesSunnyStro ngWeakHumidityNoYesNormal YesHighNo、具體實(shí)現(xiàn)： 實(shí)現(xiàn)算法如下：#i nclude <iostream>#in clude <fstream>#in clude <math.h>#in clude <stri ng> using n ames pace std;#defi ne ROW 14#defi ne COL 5#defi ne log2 0.69314718055typ edef struct TNodechar data15;char weight15;TNod

4、e * firstchild,* nextsibli ng; *tree;OutLookg; Temp erature15; Humidity15;Win d15;P layTe nni s5;typ edef struct LNode charcharcharcharcharLNode *n ext;*li nk;typ edef struct AttrNodecharattributes15;/ 屬性intattr_Num;/屬性的個(gè)數(shù)AttrNode *n ext;*Attributes;char * Exa mp lesROWCOL = /"OverCast",&q

5、uot;Cool","High","Stro ng","No",/"Rai rr,"Hot","Normal","Stro ng","Yes","Sunn y","Hot","High","Weak","No", "Sunn y","Hot","High","Stro

6、ng","No", "OverCast","Hot","High","Weak","Yes","Rain","Mild","High","Weak","Yes","Rain","Cool","Normal","Weak","Yes", "Rain",

7、"Cool","Normal","Strong","No", "OverCast","Cool","Normal","Strong","Yes", "Sunny","Mild","High","Weak","No", "Sunny","Cool","Normal&quo

8、t;,"Weak","Yes", "Rain","Mild","Normal","Weak","Yes", "Sunny","Mild","Normal","Strong","Yes", "OverCast","Mild","Normal","Strong","Yes&

9、quot;, "OverCast","Hot","Normal","Weak","Yes", "Rain","Mild","High","Strong","No" ;char * Attributes_kind4 = "OutLook","Temperature","Humidity","Wind" int Attr_

10、kind4 = 3,3,2,2;char * OutLook_kind3 = "Sunny","OverCast","Rain"char * Temperature_kind3 = "Hot","Mild","Cool"char * Humidity_kind2 = "High","Normal"char * Wind_kind2 = "Weak","Strong"/*int i_Exampple

11、145 = 0,0,0,0,1,0,0,0,1,1,1,0,0,1,0,2,1,0,0,0,2,2,1,0,0,2,2,1,1,1,1,2,1,1,0,0,1,0,0,1,0,2,1,0,0,2,1,1,0,0,0,1,1,1,0,1,1,1,1,0,1,1,1,0,0,2,1,0,0,1 ;*/ void treelists(tree T); void InitAttr(Attributes &attr_link,char * Attributes_kind,int Attr_kind); void InitLink(link &L,char * ExamplesCOL);v

12、oid ID3(tree &T,link L,link Target_Attr,Attributes attr);void PN_Num(link L,int &positve,int &negative);double Gain(int positive,int negative,char * atrribute,link L,Attributes attr_L);void main()link LL,p; Attributes attr_L,q;tree T;T = new TNode;T->firstchild = T->nextsibling = N

13、ULL; strcpy(T->weight,"");strcpy(T->data,"");attr_L = new AttrNode; attr_L->next = NULL;LL = new LNode;LL->next = NULL;/成功建立兩個(gè)鏈表InitLink(LL,Examples);InitAttr(attr_L,Attributes_kind,Attr_kind);ID3(T,LL,NULL,attr_L);coutvv"決策樹以廣義表形式輸出如下："<<e ndl; treeli

14、sts(T);/以廣義表的形式輸出樹/ cout<<Gain(9,5,"OutLook",LL,attr_L)<<endl;cout<<endl; /以廣義表的形式輸出樹 void treelists(tree T) tree p;if(!T)return; cout<<""<<T->weight<<"" cout<<T->data;p = T->firstchild; if (p) cout<<"("

15、 while (p) treelists(p);p = p->nextsibling; if (p)cout<<',' cout<<")"void InitAttr(Attributes &attr_link,char * Attributes_kind,int Attr_kind) Attributes p;for (int i =0;i < 4;i+) p = new AttrNode; p->next = NULL;strcpy(p->attributes,Attributes_kindi);p-

16、>attr_Num = Attr_kindi;p->next = attr_link->next; attr_link->next = p;void InitLink(link &LL,char * ExamplesCOL) link p;for (int i = 0;i < ROW;i+) p = new LNode; p->next = NULL;strcpy(p->OutLook,Examplesi0); strcpy(p->Temperature,Examplesi1); strcpy(p->Humidity,Example

17、si2); strcpy(p->Wind,Examplesi3); strcpy(p->PlayTennis,Examplesi4);p->next = LL->next; LL->next = p;void PN_Num(link L,int &positve,int &negative) positve = 0; negative = 0; link p;p = L->next;while (p)if (strcmp(p->PlayTennis,"No") = 0) negative+;else if(strcm

18、p(p->PlayTennis,"Yes") = 0) positve+;p = p->next; /計(jì)算信息增益/link L: 樣本集合 S/attr_L :屬性集合double Gain(int positive,int negative,char * atrribute,link L,Attributes attr_L) int atrr_ki nds;/每個(gè)屬性中的值的個(gè)數(shù)Attributes p = attr_L->next; link q = L->next;int attr_th = 0;/ 第幾個(gè)屬性 while (p) if (s

19、trcmp(p->attributes,atrribute) = 0)atrr_kinds = p->attr_Num;break;p = p->next;attr_th+;double entropy,gain=0;double p1 = 1.0*positive/(positive + negative); double p2 = 1.0*negative/(positive + negative);entropy = -p1*log(p1)/log2 - p2*log(p2)/log2;/ 集合熵 gain = entropy;/獲取每個(gè)屬性值在訓(xùn)練樣本中出現(xiàn)的個(gè)數(shù)/獲

20、取每個(gè)屬性值所對(duì)應(yīng)的正例和反例的個(gè)數(shù) /聲明一個(gè) 3*atrr_kinds 的數(shù)組int * kinds= new int * 3;for (int j =0;j < 3;j+)kindsj = new intatrr_kinds;/ 保存每個(gè)屬性值在訓(xùn)練樣本中出現(xiàn)的個(gè)數(shù) /初始化for (int j = 0;j< 3;j+)for (int i =0;i < atrr_kinds;i+)kindsji = 0;while (q)if (strcmp("OutLook",atrribute) = 0)for (int i = 0;i < atrr_k

21、inds;i+)if(strcmp(q->OutLook,OutLook_kindi) = 0) kinds0i+;if(strcmp(q->PlayTennis,"Yes") = 0) kinds1i+;elsekinds2i+;else if (strcmp("Temperature",atrribute) = 0)for (int i = 0;i < atrr_kinds;i+)if(strcmp(q->Temperature,Temperature_kindi) = 0) kinds0i+;if(strcmp(q->

22、PlayTennis,"Yes") = 0) kinds1i+;elsekinds2i+;else if (strcmp("Humidity",atrribute) = 0)for (int i = 0;i < atrr_kinds;i+)if(strcmp(q->Humidity,Humidity_kindi) = 0) kinds0i+;if(strcmp(q->PlayTennis,"Yes") = 0) kinds1i+;/elsekinds2i+;else if (strcmp("Wind&quo

23、t;,atrribute) = 0)for (int i = 0;i < atrr_kinds;i+)if(strcmp(q->Wind,Wind_kindi) = 0) kinds0i+;if(strcmp(q->PlayTennis,"Yes") = 0) kinds1i+;elsekinds2i+;q = q->next; /計(jì)算信息增益double * gain_kind = new doubleatrr_kinds; int positive_kind = 0,negative_kind = 0;for (int j = 0;j <

24、atrr_kinds;j+)if (kinds0j != 0 && kinds1j != 0 && kinds2j != 0) p1 = 1.0*kinds1j/kinds0j;p2 = 1.0*kinds2j/kinds0j;gain_kindj = -p1*log(p1)/log2-p2*log(p2)/log2;gain = gain - (1.0*kinds0j/(positive + negative)*gain_kindj; elsegain_kindj = 0; return gain; /在 ID3 算法中的訓(xùn)練樣本子集合與屬性子集合的鏈表需要進(jìn)

25、行清空 void FreeLink(link &Link)link p,q;p = Link->next;Link->next = NULL; while (p)q = p;p = p->next; free(q);void ID3(tree &T,link L,link Target_Attr,Attributes attr) Attributes p,max,attr_child,p1;link q,link_child,q1;tree r,tree_p;int positive =0,negative =0;PN_Num(L,positive,negat

26、ive);/初始化兩個(gè)子集合attr_child = new AttrNode; attr_child->next = NULL;link_child = new LNode; link_child->next = NULL;if (positive = 0)/ 全是反例strcpy(T->data,"No");return;else if( negative = 0)/全是正例strcpy(T->data,"Yes");return;p = attr->next; /屬性鏈表double gain,g = 0;/*/* 建

27、立屬性子集合與訓(xùn)練樣本子集合有兩個(gè)方案： 一：在原來(lái)鏈表的基礎(chǔ)上進(jìn)行刪除； 二：另外申請(qǐng)空間進(jìn)行存儲(chǔ)子集合； 采用第二種方法雖然浪費(fèi)了空間，但也省了很多事情，避免了變量之間 的應(yīng)用混亂*/ /* */if(p)while (p)gain = Gain(positive,negative,p->attributes,L,attr); cout<<p->attributes<<" "<<gain<<endl;if(gain > g)g = gain;max = p;/尋找信息增益最大的屬性p = p->ne

28、xt;strc py(T->data,max->attributes);/增加決策樹的節(jié)點(diǎn)cout<<" 信 息 增 益 最 大 的 屬 性 ： max->attributes "<<max->attributes<<endl<<endl;/下面開始建立決策樹/創(chuàng)建屬性子集合p = attr->next;while (p)if (strcmp(p->attributes,max->attributes) != 0)p1 = new AttrNode; strcpy(p1->att

29、ributes,p->attributes); p1->attr_Num = p->attr_Num;p1->next = NULL;p1->next = attr_child->next; attr_child->next = p1;p = p->next;/需要區(qū)分出是哪一種屬性/建立每一層的第一個(gè)節(jié)點(diǎn)if (strcmp("OutLook",max->attributes) = 0)r = new TNode;r->firstchild = r->nextsibling = NULL;strcpy(r-

30、>weight,OutLook_kind0);T->firstchild = r;獲取與屬性值相關(guān)的訓(xùn)練樣例Exa mp le(vi),建立一個(gè)新的訓(xùn)練樣本鏈表 link_childq = L->next;while (q)if (strcmp(q->OutLook,OutLook_kind0) = 0)q1 = new LNode;strcpy(q1->OutLook,q->OutLook);strcpy(q1->Humidity,q->Humidity);strcpy(q1->Temperature,q->Temperature)

31、; strcpy(q1->Wind,q->Wind); strcpy(q1->PlayTennis,q->PlayTennis); q1->next = NULL;q1->next = link_child->next; link_child->next = q1;q = q->next;else if (strcmp("Temperature",max->attributes) = 0)r = new TNode; r->firstchild = r->nextsibling = NULL; strc

32、py(r->weight,Temperature_kind0);T->firstchild = r;/獲取與屬性值相關(guān)的訓(xùn)練樣例 Example(vi), 建立一個(gè)新的訓(xùn)練樣本 鏈表 link_childq = L->next; while (q) if (strcmp(q->Temperature,Temperature_kind0) = 0)q1 = new LNode;strcpy(q1->OutLook,q->OutLook);strcpy(q1->Humidity,q->Humidity);strcpy(q1->Temperatu

33、re,q->Temperature);strcpy(q1->Wind,q->Wind);strcpy(q1->PlayTennis,q->PlayTennis);q1->next = NULL;q1->next = link_child->next; link_child->next = q1;q = q->next;else if (strcmp("Humidity",max->attributes) = 0)r = new TNode;r->firstchild = r->nextsiblin

34、g = NULL; strcpy(r->weight,Humidity_kind0); T->firstchild = r;/獲取與屬性值相關(guān)的訓(xùn)練樣例 Example(vi), 建立一個(gè)新的訓(xùn)練樣本 鏈表 link_childq = L->next;while (q)if (strcmp(q->Humidity,Humidity_kind0) = 0)q1 = new LNode; strcpy(q1->OutLook,q->OutLook); strcpy(q1->Humidity,q->Humidity); strcpy(q1->Te

35、mperature,q->Temperature); strcpy(q1->Wind,q->Wind); strcpy(q1->PlayTennis,q->PlayTennis); q1->next = NULL;q1->next = link_child->next; link_child->next = q1;q = q->next;else if (strcmp("Wind",max->attributes) = 0)r = new TNode;r->firstchild = r->next

36、sibling = NULL; strcpy(r->weight,Wind_kind0);T->firstchild = r;/獲取與屬性值相關(guān)的訓(xùn)練樣例 Example(vi), 建立一個(gè)新的訓(xùn)練樣本 鏈表 link_childq = L->next;while (q)if (strcmp(q->Wind,Wind_kind0) = 0)q1 = new LNode;strcpy(q1->OutLook,q->OutLook);strcpy(q1->Humidity,q->Humidity);strcpy(q1->Temperature,

37、q->Temperature);strcpy(q1->Wind,q->Wind); strcpy(q1->PlayTennis,q->PlayTennis);q1->next = NULL;q1->next = link_child->next;link_child->next = q1; q = q->next;int p = 0,n = 0;PN_Num(link_child,p,n);if (p != 0 && n != 0)ID3(T->firstchild,link_child,Target_Attr,

38、attr_child);FreeLink(link_child);else if(p = 0)strcpy(T->firstchild->data,"No");FreeLink(link_child);/ strcpy(T->firstchild->data,q1->PlayTennis);/此處應(yīng)該需要修改:)else if(n = 0) strcpy(T->firstchild->data,"Yes"); FreeLink(link_child);/建立每一層上的其他節(jié)點(diǎn) tree_p = T->fir

39、stchild;for (int i = 1;i < max->attr_Num;i+) /需要區(qū)分出是哪一種屬性 if (strcmp("OutLook",max->attributes) = 0) r = new TNode; r->firstchild = r->nextsibling = NULL; strcpy(r->weight,OutLook_kindi); tree_p->nextsibling = r;/獲取與屬性值相關(guān)的訓(xùn)練樣例 Example(vi), 建立一個(gè)新的訓(xùn)練樣 本鏈表 link_childq = L

40、->next;while (q)if (strcmp(q->OutLook,OutLook_kindi) = 0)q1 = new LNode;strcpy(q1->OutLook,q->OutLook); strcpy(q1->Humidity,q->Humidity);strcpy(q1->Temperature,q->Temperature); strcpy(q1->Wind,q->Wind);strcpy(q1->PlayTennis,q->PlayTennis); q1->next = NULL;q1-&g

41、t;next = link_child->next; link_child->next = q1;q = q->next;else if (strcmp("Temperature",max->attributes) = 0)r = new TNode; r->firstchild = r->nextsibling = NULL; strcpy(r->weight,Temperature_kindi); tree_p->nextsibling = r;/獲取與屬性值相關(guān)的訓(xùn)練樣例 Example(vi), 建立一個(gè)新的訓(xùn)練樣 本

42、鏈表 link_childq = L->next;while (q)if (strcmp(q->Temperature,Temperature_kindi) = 0)q1 = new LNode;strcpy(q1->OutLook,q->OutLook);strcpy(q1->Humidity,q->Humidity); strcpy(q1->Temperature,q->Temperature); strcpy(q1->Wind,q->Wind);strcpy(q1->PlayTennis,q->PlayTennis)

43、;q1->next = NULL;q1->next = link_child->next; link_child->next = q1;q = q->next;else if (strcmp("Humidity",max->attributes) = 0) r = new TNode; r->firstchild = r->nextsibling = NULL; strcpy(r->weight,Humidity_kindi); tree_p->nextsibling = r;/獲取與屬性值相關(guān)的訓(xùn)練樣例 Exam

44、ple(vi), 建立一個(gè)新的訓(xùn)練樣 本鏈表 link_childq = L->next; while (q) if (strcmp(q->Humidity,Humidity_kindi) = 0)q1 = new LNode; strcpy(q1->OutLook,q->OutLook); strcpy(q1->Humidity,q->Humidity); strcpy(q1->Temperature,q->Temperature); strcpy(q1->Wind,q->Wind); strcpy(q1->PlayTenni

45、s,q->PlayTennis); q1->next = NULL;q1->next = link_child->next; link_child->next = q1;q = q->next;else if (strcmp("Wind",max->attributes) = 0)r = new TNode;r->firstchild = r->nextsibling = NULL;strcpy(r->weight,Wind_kindi);tree_p->nextsibling = r;/獲取與屬性值相關(guān)的訓(xùn)練樣例 Example(vi), 建立一個(gè)新的訓(xùn)練樣 本鏈表 link_childq = L->next;while (q)if (str