機(jī)器學(xué)習(xí)實驗報告

1、精選優(yōu)質(zhì)文檔-傾情為你奉上機(jī)器學(xué)習(xí)課內(nèi)實驗報告（1） ID算法實現(xiàn)決策樹2015 - 2016學(xué)年 第 2 學(xué)期專業(yè)：智能科學(xué)與技術(shù)班級：智能1301班學(xué)號：姓名：張爭輝一、 實驗?zāi)康模豪斫釯D3算法的基本原理，并且編程實現(xiàn)。二、 實驗要求：使用C/C+/MATLAB實現(xiàn)ID3算法。輸入：若干行，每行 5 個字符串，表示Outlook Temperature Humidity Wind Play ball如上表。輸出：決策樹。實驗結(jié)果如下：輸入： Sunny Hot High Weak No Sunny Hot High Strong No Overcast Hot High Weak Yes

2、 Rain Mild High Weak Yes Rain Cool Normal Weak Yes Rain Cool Normal Strong No Overcast Cool Normal Strong Yes Sunny Mild High Weak No Sunny Cool Normal Weak Yes Rain Mild Normal Weak Yes Sunny Mild Normal Strong Yes Overcast Mild High Strong Yes Overcast Hot Normal Weak Yes Rain Mild High Strong No輸

3、出：Outlook Rain Wind Strong No Weak Yes Overcast Yes Sunny Humidity Normal Yes High No 三、 具體實現(xiàn)：實現(xiàn)算法如下：#include <iostream>#include <fstream>#include <math.h>#include <string>using namespace std;#define ROW 14#define COL 5#define log2 0.typedef struct TNode char data15; char wei

4、ght15; TNode * firstchild,*nextsibling;*tree;typedef struct LNode char OutLook15; char Temperature15; char Humidity15; char Wind15; char PlayTennis5; LNode *next;*link;typedef struct AttrNode char attributes15;/屬性 int attr_Num;/屬性的個數(shù) AttrNode *next;*Attributes;char * ExamplesROWCOL = /"OverCast

5、","Cool","High","Strong","No", /"Rain","Hot","Normal","Strong","Yes", "Sunny","Hot","High","Weak","No", "Sunny","Hot","High",

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

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

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

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

10、t;int Attr_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

11、 i_Exampple145 = 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,

12、char * ExamplesCOL);void 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->firstchil

13、d = T->nextsibling = NULL; strcpy(T->weight,""); strcpy(T->data,""); attr_L = new AttrNode; attr_L->next = NULL; LL = new LNode; LL->next = NULL; /成功建立兩個鏈表 InitLink(LL,Examples); InitAttr(attr_L,Attributes_kind,Attr_kind); ID3(T,LL,NULL,attr_L); cout<<"決

14、策樹以廣義表形式輸出如下："<<endl; treelists(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->firs

15、tchild; if (p) cout<<"(" 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;

16、strcpy(p->attributes,Attributes_kindi); p->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->Tempe

17、rature,Examplesi1); strcpy(p->Humidity,Examplesi2); 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->P

18、layTennis,"No") = 0) negative+; else if(strcmp(p->PlayTennis,"Yes") = 0) positve+; p = p->next; /計算信息增益/link L: 樣本集合S/attr_L：屬性集合double Gain(int positive,int negative,char * atrribute,link L,Attributes attr_L) int atrr_kinds;/每個屬性中的值的個數(shù) Attributes p = attr_L->next; link

19、q = L->next; int attr_th = 0;/第幾個屬性 while (p) if (strcmp(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

20、 - p2*log(p2)/log2;/集合熵 gain = entropy; /獲取每個屬性值在訓(xùn)練樣本中出現(xiàn)的個數(shù) /獲取每個屬性值所對應(yīng)的正例和反例的個數(shù) /聲明一個3*atrr_kinds的數(shù)組 int * kinds= new int * 3; for (int j =0;j < 3;j+) kindsj = new intatrr_kinds;/保存每個屬性值在訓(xùn)練樣本中出現(xiàn)的個數(shù) /初始化 for (int j = 0;j< 3;j+) for (int i =0;i < atrr_kinds;i+) kindsji = 0; while (q) if (str

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

22、(strcmp(q->Temperature,Temperature_kindi) = 0) kinds0i+; if(strcmp(q->PlayTennis,"Yes") = 0) kinds1i+; else kinds2i+; 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->Play

23、Tennis,"Yes") = 0) kinds1i+;/ else kinds2i+; else if (strcmp("Wind",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+; else kinds2i+; q = q->next; /計算信息增益 double * gain

24、_kind = new doubleatrr_kinds; int positive_kind = 0,negative_kind = 0; for (int j = 0;j < 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/

25、(positive + negative)*gain_kindj; else gain_kindj = 0; return gain;/在ID3算法中的訓(xùn)練樣本子集合與屬性子集合的鏈表需要進(jìn)行清空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,

26、attr_child,p1; link q,link_child,q1; tree r,tree_p; int positive =0,negative =0; PN_Num(L,positive,negative); /初始化兩個子集合 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

27、( negative = 0)/全是正例 strcpy(T->data,"Yes"); return; p = attr->next; /屬性鏈表 double gain,g = 0; /*/ /* 建立屬性子集合與訓(xùn)練樣本子集合有兩個方案： 一：在原來鏈表的基礎(chǔ)上進(jìn)行刪除； 二：另外申請空間進(jìn)行存儲子集合； 采用第二種方法雖然浪費了空間，但也省了很多事情，避免了變量之間的應(yīng)用混亂 */ /*/ if(p) while (p) gain = Gain(positive,negative,p->attributes,L,attr); cout<<

28、p->attributes<<" "<<gain<<endl; if(gain > g) g = gain; max = p;/尋找信息增益最大的屬性 p = p->next; strcpy(T->data,max->attributes);/增加決策樹的節(jié)點 cout<<"信息增益最大的屬性：max->attributes = "<<max->attributes<<endl<<endl; /下面開始建立決策樹 /創(chuàng)建屬性子集合

29、 p = attr->next; while (p) if (strcmp(p->attributes,max->attributes) != 0) p1 = new AttrNode; strcpy(p1->attributes,p->attributes); p1->attr_Num = p->attr_Num; p1->next = NULL; p1->next = attr_child->next; attr_child->next = p1; p = p->next; /需要區(qū)分出是哪一種屬性 /建立每一層的第一

30、個節(jié)點 if (strcmp("OutLook",max->attributes) = 0) r = new TNode; r->firstchild = r->nextsibling = NULL; strcpy(r->weight,OutLook_kind0); T->firstchild = r; /獲取與屬性值相關(guān)的訓(xùn)練樣例Example(vi),建立一個新的訓(xùn)練樣本鏈表link_child q = L->next; while (q) if (strcmp(q->OutLook,OutLook_kind0) = 0) q1

31、 = 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->next = link_child->next; link_child->next = q1; q = q

32、->next; else if (strcmp("Temperature",max->attributes) = 0) r = new TNode; r->firstchild = r->nextsibling = NULL; strcpy(r->weight,Temperature_kind0); T->firstchild = r; /獲取與屬性值相關(guān)的訓(xùn)練樣例Example(vi),建立一個新的訓(xùn)練樣本鏈表link_child q = L->next; while (q) if (strcmp(q->Temperatur

33、e,Temperature_kind0) = 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->next = link_child->next; lin

34、k_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_kind0); T->firstchild = r; /獲取與屬性值相關(guān)的訓(xùn)練樣例Example(vi),建立一個新的訓(xùn)練樣本鏈表link_child q = L->next; while (q) if (s

35、trcmp(q->Humidity,Humidity_kind0) = 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->next = link_chi

36、ld->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_kind0); T->firstchild = r; /獲取與屬性值相關(guān)的訓(xùn)練樣例Example(vi),建立一個新的訓(xùn)練樣本鏈表link_child q = L->next; while (

37、q) if (strcmp(q->Wind,Wind_kind0) = 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->next = link_chi

38、ld->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,attr_child); FreeLink(link_child); else if(p = 0) strcpy(T->firstchild->data,"No"); FreeLink(link_child); /strcpy(

39、T->firstchild->data,q1->PlayTennis);/-此處應(yīng)該需要修改-:) else if(n = 0) strcpy(T->firstchild->data,"Yes"); FreeLink(link_child); /建立每一層上的其他節(jié)點 tree_p = T->firstchild; for (int i = 1;i < max->attr_Num;i+) /需要區(qū)分出是哪一種屬性 if (strcmp("OutLook",max->attributes) = 0) r

40、 = new TNode; r->firstchild = r->nextsibling = NULL; strcpy(r->weight,OutLook_kindi); tree_p->nextsibling = r; /獲取與屬性值相關(guān)的訓(xùn)練樣例Example(vi),建立一個新的訓(xùn)練樣本鏈表link_child q = L->next; while (q) if (strcmp(q->OutLook,OutLook_kindi) = 0) q1 = new LNode; strcpy(q1->OutLook,q->OutLook); str

41、cpy(q1->Humidity,q->Humidity); strcpy(q1->Temperature,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("Temperature",max-

42、>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),建立一個新的訓(xùn)練樣本鏈表link_child q = L->next; while (q) if (strcmp(q->Temperature,Temperature_kindi) = 0) q1 = new LNode; strcpy(

43、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->next = link_child->next; link_child->next = q1; q = q->next; else if (s

44、trcmp("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)練樣例Example(vi),建立一個新的訓(xùn)練樣本鏈表link_child q = 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->Temp