实验二报告-决策树实验.doc

决策树实验一、实验原理 决策树是一个类似于流程图的树结构，其中每个内部结点表示在一个属性上的测试，每个分支代表一个测试输入，而每个树叶结点代表类或类分布。数的最顶层结点是根结点。一棵典型的决策树如图1所示。它表示概念buys_computer，它预测顾客是否可能购买计算机。内部结点用矩形表示，而树叶结点用椭圆表示。为了对未知的样本分类，样本的属性值在决策树上测试。决策树从根到叶结点的一条路径就对应着一条合取规则，因此决策树容易转化成分类规则。 图1ID3算法： 决策树中每一个非叶结点对应着一个非类别属性，树枝代表这个属性的值。一个叶结点代表从树根到叶结点之间的路径对应的记录所属的类别属性值。 每一个非叶结点都将与属性中具有最大信息量的非类别属性相关联。 采用信息增益来选择能够最好地将样本分类的属性。信息增益基于信息论中熵的概念。ID3总是选择具有最高信息增益（或最大熵压缩）的属性作为当前结点的测试属性。该属性使得对结果划分中的样本分类所需的信息量最小，并反映划分的最小随机性或“不纯性”。二、算法伪代码算法Decision_Tree(data,AttributeName)输入由离散值属性描述的训练样本集data;候选属性集合AttributeName。输出一棵决策树。（1） 创建节点N；（2） If samples 都在同一类C中then（3） 返回N作为叶节点，以类C标记；（4） If attribute_list为空then（5） 返回N作为叶节点，以samples 中最普遍的类标记；/多数表决（6） 选择attribute_list 中具有最高信息增益的属性test_attribute;（7） 以test_attribute 标记节点N；（8） For each test_attribute 的已知值v /划分 samples（9） 由节点N分出一个对应test_attribute=v的分支；（10令Sv为 samples中 test_attribute=v 的样本集合；/一个划分块（11）If Sv为空 then（12）加上一个叶节点，以samples中最普遍的类标记；（13）Else 加入一个由Decision_Tree(Sv,attribute_list-test_attribute)返回节点值。4、 实验主函数 #include #include #include #include #include #include using namespace std; #define MAXLEN 5/输入每行的数据个数 vector vector state;/实例集 vector item(MAXLEN);/对应一行实例集 vector attribute_row;/保存首行即属性行数据 string end(end);/输入结束 string yes(危险); string no(不危险); string blank(); mapstring,vector map_attribute_values;/存储属性对应的所有的值 int tree_size = 0; struct Node/决策树节点 string attribute;/属性值 string arrived_value;/到达的属性值 vector childs;/所有的孩子 Node() attribute = blank; arrived_value = blank; ; Node * root; /根据数据实例计算属性与值组成的map void ComputeMapFrom2DVector() unsigned int i,j,k; bool exited = false; vector values; for(i = 1; i MAXLEN-1; i+)/按照列遍历 for (j = 1; j state.size(); j+) for (k = 0; k values.size(); k+) if(!pare(stateji) exited = true; if(!exited) values.push_back(stateji);/注意Vector的插入都是从前面插入的，注意更新it，始终指向vector头 exited = false; map_attribute_valuesstate0i = values; values.erase(values.begin(), values.end(); /根据具体属性和值来计算熵 double ComputeEntropy(vector vector remain_state, string attribute, string value,bool ifparent) vector count (2,0); unsigned int i,j; bool done_flag = false;/哨兵值 for(j = 1; j MAXLEN; j+) if(done_flag) break; if(!attribute_pare(attribute) for(i = 1; i remain_state.size(); i+) if(!ifparent&!remain_pare(value) | ifparent)/ifparent记录是否算父节点 if(!remain_stateiMAXLEN - 1.compare(yes) count0+; else count1+; done_flag = true; if(count0 = 0 | count1 = 0 ) return 0;/全部是正实例或者负实例 /具体计算熵 根据+count0,-count1,log2为底通过换底公式换成自然数底数 double sum = count0 + count1; double entropy = -count0/sum*log(count0/sum)/log(2.0) - count1/sum*log(count1/sum)/log(2.0); return entropy; /计算按照属性attribute划分当前剩余实例的信息增益 double ComputeGain(vector vector remain_state, string attribute) unsigned int j,k,m; /首先求不做划分时的熵 double parent_entropy = ComputeEntropy(remain_state, attribute, blank, true); double children_entropy = 0; /然后求做划分后各个值的熵 vector values = map_attribute_valuesattribute; vector ratio; vector count_values; int tempint; for(m = 0; m values.size(); m+) tempint = 0; for(k = 1; k MAXLEN - 1; k+) if(!attribute_pare(attribute) for(j = 1; j remain_state.size(); j+) if(!remain_pare(valuesm) tempint+; count_values.push_back(tempint); for(j = 0; j values.size(); j+) ratio.push_back(double)count_valuesj / (double)(remain_state.size()-1); double temp_entropy; for(j = 0; j values.size(); j+) temp_entropy = ComputeEntropy(remain_state, attribute, valuesj, false); children_entropy += ratioj * temp_entropy; return (parent_entropy - children_entropy); int FindAttriNumByName(string attri) for(int i = 0; i MAXLEN; i+) if(!pare(attri) return i; cerrcant find the numth of attributeendl; return 0; /找出样例中占多数的正/负性 string MostCommonLabel(vector vector remain_state) int p = 0, n = 0; for(unsigned i = 0; i = n) return yes; else return no; /判断样例是否正负性都为label bool AllTheSameLabel(vector vector remain_state, string label) int count = 0; for(unsigned int i = 0; i remain_state.size(); i+) if(!remain_stateiMAXLEN-1.compare(label) count+; if(count = remain_state.size()-1) return true; else return false; /计算信息增益，DFS构建决策树 /current_node为当前的节点 /remain_state为剩余待分类的样例 /remian_attribute为剩余还没有考虑的属性 /返回根结点指针 Node * BulidDecisionTreeDFS(Node * p, vector vector remain_state, vector remain_attribute) /if(remain_state.size() 0) /printv(remain_state); / if (p = NULL) p = new Node(); /先看搜索到树叶的情况 if (AllTheSameLabel(remain_state, yes) p-attribute = yes; return p; if (AllTheSameLabel(remain_state, no) p-attribute = no; return p; if(remain_attribute.size() = 0)/所有的属性均已经考虑完了,还没有分尽 string label = MostCommonLabel(remain_state); p-attribute = label; return p; double max_gain = 0, temp_gain; vector :iterator max_it = remain_attribute.begin(); vector :iterator it1; for(it1 = remain_attribute.begin(); it1 max_gain) max_gain = temp_gain; max_it = it1; /下面根据max_it指向的属性来划分当前样例，更新样例集和属性集 vector new_attribute; vector vector new_state; for(vector :iterator it2 = remain_attribute.begin(); it2 attribute = *max_it; vector values = map_attribute_values*max_it; int attribue_num = FindAttriNumByName(*max_it); new_state.push_back(attribute_row); for(vector :iterator it3 = values.begin(); it3 values.end(); it3+) for(unsigned int i = 1; i arrived_value = *it3; if(new_state.size() = 0)/表示当前没有这个分支的样例，当前的new_node为叶子节点 new_node-attribute = MostCommonLabel(remain_state); else BulidDecisionTreeDFS(new_node, new_state, new_attribute); /递归函数返回时即回溯时需要1 将新结点加入父节点孩子容器 2清除new_state容器 p-childs.push_back(new_node); new_state.erase(new_state.begin()+1,new_state.end();/注意先清空new_state中的前一个取值的样例，准备遍历下一个取值样例 return p; void Input() string s; while(cins,pare(end) != 0)/-1为输入结束 item0 = s; for(int i = 1;i itemi; state.push_back(item);/注意首行信息也输入进去，即属性 for(int j = 0; j MAXLEN; j+) attribute_row.push_back(state0j); void PrintTree(Node *p, int depth) for (int i = 0; i depth; i+) cout arrived_value.empty() coutarrived_valueendl; for (int i = 0; i depth+1; i+) cout t;/按照树的深度先输出tab coutattributeendl; for (vector:iterator it = p-childs.begin(); it != p-childs.end(); it+) PrintTree(*it, depth + 1); void FreeTree(Node *p) if (p = NULL) return; for (vector:iterator it = p-childs.begin(); it != p-childs.end