从决策树学习谈到贝叶斯分类算法、EM、HMM(共41页)

1、第一篇：从决策树学习(xux)谈到贝叶斯分类算法、EM、HMM引言(ynyn) 最近(zujn)在面试中，除了基础 & 算法 & 项目之外，经常被问到或被要求介绍和描述下自己所知道的几种分类或聚类算法(当然，这完全不代表你将来的面试中会遇到此类问题，只是因为我的简历上写了句：熟悉常见的聚类 & 分类算法而已)，而我向来恨对一个东西只知其皮毛而不得深入，故写一个有关数据挖掘十大算法的系列文章以作为自己备试之用，甚至以备将来常常回顾思考。行文杂乱，但侥幸若能对读者起到一点帮助，则幸甚至哉。 本文借鉴和参考了两本书，一本是Tom M.Mitchhell所著的机器学习，一本是数据挖掘导论，这两本书皆分

2、别是机器学习 & 数据挖掘领域的开山 or 杠鼎之作，读者有继续深入下去的兴趣的话，不妨在阅读本文之后，课后细细研读这两本书。除此之外，还参考了网上不少牛人的作品(文末已注明参考文献或链接)，在此，皆一一表示感谢(从本质上来讲，本文更像是一篇读书 & 备忘笔记)。 本系列暂称之为 HYPERLINK /v_july_v/article/category/1061301 t _blank Top 10 Algorithms in Data Mining，其中，各篇分别有以下具体内容：开篇：即本文从决策树学习谈到贝叶斯分类算法、EM、HMM；第二篇： HYPERLINK /v_july_v/art

3、icle/details/7624837 t _blank 支持向量机通俗导论（理解SVM的三层境界）；第三篇： HYPERLINK /v_july_v/article/details/8203674 t _blank 从K近邻算法、距离度量谈到KD树、SIFT+BBF算法；第四篇：神经网络 待写. 说白了，一年多以前，我在本blog内写过一篇文章，叫做： HYPERLINK /v_july_v/article/details/6142146 t _blank 数据挖掘领域十大经典算法初探(题外话：最初有个出版社的朋友便是因此文找到的我，尽管现在看来，我离出书日期仍是遥遥无期)。现在，我抽取其

4、中几个最值得一写的几个算法每一个都写一遍，以期对其有个大致通透的了解。 OK，全系列任何一篇文章若有任何错误，漏洞，或不妥之处，还请读者们一定要随时不吝赐教 & 指正，谢谢各位。分类与聚类，监督(jind)学习与无监督学习 在讲具体的分类和聚类算法之前(zhqin)，有必要讲一下什么是分类，什么是 HYPERLINK /wiki/%E6%95%B0%E6%8D%AE%E8%81%9A%E7%B1%BB t _blank 聚类，以及都包含哪些(nxi)具体算法或问题。Classification (分类)，对于一个 classifier ，通常需要你告诉它“这个东西被分为某某类”这样一些例子，理

5、想情况下，一个 classifier 会从它得到的训练集中进行“学习”，从而具备对未知数据进行分类的能力，这种提供训练数据的过程通常叫做 supervised learning (监督学习)，而Clustering(聚类)，简单地说就是把相似的东西分到一组，聚类的时候，我们并不关心某一类是什么，我们需要实现的目标只是把相似的东西聚到一起，因此，一个聚类算法通常只需要知道如何计算相似 度就可以开始工作了，因此 clustering 通常并不需要使用训练数据进行学习，这在 Machine Learning 中被称作 unsupervised learning (无监督学习). 常见的分类与聚类算法

6、 所谓分类分类，简单来说，就是根据文本的特征或属性，划分到已有的类别中。如在自然语言处理NLP中，我们经常提到的文本分类便就是一个分类问题，一般的模式分类方法都可用于文本分类研究。常用的分类算法包括：决策树分类法，朴素的贝叶斯分类算法(native Bayesian classifier)、基于 HYPERLINK /v_july_v/article/details/7624837 t _blank 支持向量机(SVM)的分类器，神经网络法，k-最近邻法(k-nearest neighbor，kNN)，模糊分类法等等(所有这些分类算法日后在本blog内都会一一陆续阐述)。 分类作为一种监督学习

7、方法，要求必须事先明确知道各个类别的信息，并且断言所有待分类项都有一个类别与之对应。但是很多时候上述条件得不到满足，尤其是在处理海量数据的时候，如果通过预处理使得数据满足分类算法的要求，则代价非常大，这时候可以考虑使用聚类算法。 而K均值(K-means clustering)聚类则是最典型的聚类算法(当然，除此之外，还有很多诸如属于划分法K-MEDOIDS算法、CLARANS算法；属于层次法的BIRCH算法、CURE算法、CHAMELEON算法等；基于密度的方法：DBSCAN算法、OPTICS算法、DENCLUE算法等；基于网格的方法：STING算法、CLIQUE算法、WAVE-CLUSTE

8、R算法；基于模型的方法，本系列后续会介绍其中几种)。 监督学习与无监督学习 机器学习发展到现在，一般划分为 监督学习(supervised learning)，半监督学习(semi-supervised learning)以及无监督学习(unsupervised learning)三类。举个具体的对应例子，则是比如说，在NLP词义消岐中，也分为监督的消岐方法，和无监督的消岐方法。在有监督的消岐方法中，训练数据是已知的，即每个词的语义分类是被标注了的；而在无监督的消岐方法中，训练数据是未经标注的。 上面所介绍的常见的分类算法(sun f)属于监督学习，聚类则属于无监督学习(反过来说，监督学习属于

9、分类(fn li)算法则不准确，因为监督学习只是说我们给样本sample同时(tngsh)打上了标签（label），然后同时利用样本和标签进行相应的学习任务，而不是仅仅局限于分类任务。常见的其他监督问题，比如相似性学习，特征学习等等也是监督的，但是不是分类)。 再举个例子，正如人们通过已知病例学习诊断技术那样，计算机要通过学习才能具有识别各种事物和现象的能力。用来进行学习的材料就是与被识别对象属于同类的有限数量样本。监督学习中在给予计算机学习样本的同时，还告诉计算各个样本所属的类别。若所给的学习样本不带有类别信息,就是无监督学习(浅显点说：同样是学习训练，监督学习中，给的样例比如是已经标注了如

10、心脏病的，肝炎的；而无监督学习中，就是给你一大堆的样例，没有标明是何种病例的)。 而在支持向量机导论一书给监督学习下的定义是：当样例是输入/输出对给出时，称为监督学习，有关输入/输出函数关系的样例称为训练数据。而在无监督学习中，其数据不包含输出值，学习的任务是理解数据产生的过程。第一部分、决策树学习1.1、什么是决策树 咱们直接切入正题。所谓决策树，顾名思义，是一种树，一种依托于策略抉择而建立起来的树。 机器学习中，决策树是一个预测模型；他代表的是对象属性与对象值之间的一种映射关系。树中每个节点表示某个对象，而每个分叉路径则代表的某个可能的属性值，而每个叶结点则对应从根节点到该叶节点所经历的路

11、径所表示的对象的值。决策树仅有单一输出，若欲有复数输出，可以建立独立的决策树以处理不同输出。 从数据产生决策树的机器学习技术叫做决策树学习, 通俗点说就是决策树，说白了，这是一种依托于分类、训练上的预测树，根据已知预测、归类未来。 来理论的太过抽象，下面举两个浅显易懂的例子：第一个例子 套用俗语，决策树分类的思想类似于找对象。现想象一个女孩的母亲要给这个女孩介绍男朋友，于是有了下面的对话： 女儿：多大年纪了？ 母亲：26。 女儿：长的帅不帅？ 母亲：挺帅的。 女儿：收入高不？ 母亲：不算很高，中等情况。 女儿：是公务员不？ 母亲：是，在税务局上班呢。 女儿：那好，我去见见。 这个女孩的决策过程

12、就是典型的分类树决策。相当于通过年龄、长相、收入和是否(sh fu)公务员对将男人分为两个类别：见和不见。假设这个女孩对男人的要求是：30岁以下、长相中等以上并且是高收入者或中等以上收入的公务员，那么这个可以(ky)用下图表示女孩的决策逻辑： 也就是(jish)说，决策树的简单策略就是，好比公司招聘面试过程中筛选一个人的简历，如果你的条件相当好比如说某985/211重点大学博士毕业，那么二话不说，直接叫过来面试，如果非重点大学毕业，但实际项目经验丰富，那么也要考虑叫过来面试一下，即所谓具体情况具体分析、决策。但每一个未知的选项都是可以归类到已有的分类类别中的。第二个例子 此例子来自Tom M.

13、Mitchell著的机器学习一书： 小王的目的是通过下周天气预报寻找什么时候人们会打高尔夫，他了解到人们决定是否打球的原因最主要取决于天气情况。而天气状况有晴，云和雨；气温用华氏温度表示；相对湿度用百分比；还有有无风。如此，我们便可以构造一棵决策树，如下（根据天气这个分类决策这天是否合适打网球）： 上述(shngsh)决策树对应于以下表达式：（Outlook=Sunny Humidity=70）V （Outlook = Overcast）V （Outlook=Rain Wind=Weak）1.2、ID3算法(sun f)1.2.1、决策树学习(xux)之ID3算法 ID3算法是决策树算法的一种

14、。想了解什么是ID3算法之前，我们得先明白一个概念：奥卡姆剃刀。奥卡姆剃刀（Occams Razor, Ockhams Razor），又称“奥坎的剃刀”，是由14世纪逻辑学家、圣方济各会修士奥卡姆的威廉（William of Occam，约1285年至1349年）提出，他在箴言书注2卷15题说“切勿浪费较多东西，去做用较少的东西，同样可以做好的事情。简单点说，便是：be simple。 ID3算法（IterativeDichotomiser3迭代二叉树3代）是一个由RossQuinlan发明的用于决策树的算法。这个算法便是建立在上述所介绍的奥卡姆剃刀的基础上：越是小型的决策树越优于大的决策树（

15、be simple简单理论）。尽管如此，该算法也不是总是生成最小的树形结构，而是一个启发式算法。 OK，从信息论知识中我们知道，期望信息越小，信息增益越大，从而纯度越高。ID3算法的核心思想就是以信息增益度量属性选择，选择分裂后信息增益(很快，由下文你就会知道信息增益又是怎么一回事)最大的属性进行分裂。该算法采用自顶向下的贪婪搜索遍历可能的决策树空间。 所以(suy)，ID3的思想(sxing)便是：自顶向下的贪婪搜索遍历可能的决策树空间(kngjin)构造决策树(此方法是ID3算法和C4.5算法的基础)；从“哪一个属性将在树的根节点被测试”开始；使用统计测试来确定每一个实例属性单独分类训练样

16、例的能力，分类能力最好的属性作为树的根结点测试(如何定义或者评判一个属性是分类能力最好的呢？这便是下文将要介绍的信息增益，or 信息增益率)。然后为根结点属性的每个可能值产生一个分支，并把训练样例排列到适当的分支（也就是说，样例的该属性值对应的分支）之下。重复这个过程，用每个分支结点关联的训练样例来选取在该点被测试的最佳属性。这形成了对合格决策树的贪婪搜索，也就是算法从不回溯重新考虑以前的选择。 下图所示即是用于学习布尔函数的ID3算法概要：1.2.2、哪个属性是最佳的分类属性1、信息增益的度量标准：熵 上文中，我们提到：“ID3算法的核心思想就是以信息增益度量属性选择，选择分裂后信息增益(很

17、快，由下文你就会知道信息增益又是怎么一回事)最大的属性进行分裂。”接下来，咱们就来看看这个信息增益是个什么概念(当然，在了解信息增益之前，你必须先理解：信息增益的度量标准：熵)。 上述(shngsh)的ID3算法的核心问题是选取在树的每个结点(ji din)要测试的属性。我们希望选择的是最有利于分类实例的属性，信息增益(Information Gain)是用来(yn li)衡量给定的属性区分训练样例的能力，而ID3算法在增长树的每一步使用信息增益从候选属性中选择属性。 为了精确地定义信息增益，我们先定义信息论中广泛使用的一个度量标准，称为熵（entropy），它刻画了任意样例集的纯度（puri

18、ty）。给定包含关于某个目标概念的正反样例的样例集S，那么S相对这个布尔型分类的熵为： 上述公式中，p+代表正样例，比如在本文开头第二个例子中p+则意味着去打羽毛球，而p-则代表反样例，不去打球(在有关熵的所有计算中我们定义0log0为0)。 如果写代码实现熵的计算，则如下所示：cpp HYPERLINK /v_july_v/article/details/7577684 o view plain view plain HYPERLINK /v_july_v/article/details/7577684 o copy copy HYPERLINK /v_july_v/article/deta

19、ils/7577684 o print print HYPERLINK /v_july_v/article/details/7577684 o ? ?/根据具体属性和值来计算熵doubleComputeEntropy(vectorvectorremain_state,stringattribute,stringvalue,boolifparent)vectorcount(2,0);unsignedinti,j;booldone_flag=false;/哨兵值for(j=1;jMAXLEN;j+)if(done_flag)break;if(!attribute_pare(attribute)fo

20、r(i=1;iremain_state.size();i+)if(!ifparent&!remain_pare(value)|ifparent)/ifparent记录是否算父节点if(!remain_stateiMAXLEN-pare(yes)count0+;elsecount1+;done_flag=true;if(count0=0|count1=0)return0;/全部是正实例或者负实例/具体(jt)计算熵根据(gnj)+count0,-count1,log2为底通过换底公式(gngsh)换成自然数底数doublesum=count0+count1;doubleentropy=-coun

21、t0/sum*log(count0/sum)/log(2.0)-count1/sum*log(count1/sum)/log(2.0);returnentropy;/根据具体属性和值来计算熵 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) bre

22、ak; if(!attribute_pare(attribute) for(i = 1; i wind增益的0.048。说白了，就是在星期六上午是否适合打网球的问题诀策中，采取humidity较wind作为分类属性更佳，决策树由此而来。cpp HYPERLINK /v_july_v/article/details/7577684 o view plain view plain HYPERLINK /v_july_v/article/details/7577684 o copy copy HYPERLINK /v_july_v/article/details/7577684 o print pr

23、int HYPERLINK /v_july_v/article/details/7577684 o ? ?/计算信息(xnx)增益，DFS构建(u jin)决策树/current_node为当前(dngqin)的节点/remain_state为剩余待分类的样例/remian_attribute为剩余还没有考虑的属性/返回根结点指针Node*BulidDecisionTreeDFS(Node*p,vectorvectorremain_state,vectorremain_attribute)/if(remain_state.size()0)/printv(remain_state);/if(p=

24、NULL)p=newNode();/先看搜索到树叶的情况if(AllTheSameLabel(remain_state,yes)p-attribute=yes;returnp;if(AllTheSameLabel(remain_state,no)p-attribute=no;returnp;if(remain_attribute.size()=0)/所有的属性均已经考虑完了,还没有分尽stringlabel=MostCommonLabel(remain_state);p-attribute=label;returnp;doublemax_gain=0,temp_gain;vector:iter

25、atormax_it;vector:iteratorit1;for(it1=remain_attribute.begin();it1max_gain)max_gain=temp_gain;max_it=it1;/下面根据max_it指向的属性来划分当前样例，更新样例集和属性集vectornew_attribute;vectorvectornew_state;for(vector:iteratorit2=remain_attribute.begin();it2attribute=*max_it;vectorvalues=map_attribute_values*max_it;intattribu

26、e_num=FindAttriNumByName(*max_it);new_state.push_back(attribute_row);for(vector:iteratorit3=values.begin();it3values.end();it3+)for(unsignedinti=1;iarrived_value=*it3;if(new_state.size()=0)/表示当前(dngqin)没有这个分支的样例，当前的new_node为叶子(y zi)节点new_node-attribute=MostCommonLabel(remain_state);elseBulidDecision

27、TreeDFS(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中的前一个取值的样例，准备遍历下一个取值样例returnp;/计算信息增益，DFS构建决策树 /current_node为当前的节点 /remain_state为剩余待分类的样例 /remian_attribute为剩余还没有考虑的属性 /

28、返回根结点指针 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

29、-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; vector :iterator it1; for(it1 = remain_attribute.begin(); it1 max_gain) max_gain = temp_

30、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(attribut

31、e_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); /递归函数返

32、回时即回溯时需要1 将新结点加入父节点孩子容器 2清除new_state容器 p-childs.push_back(new_node); new_state.erase(new_state.begin()+1,new_state.end();/注意先清空new_state中的前一个取值的样例，准备遍历下一个取值样例 return p; 1.2.3、ID3算法决策树的形成 OK，下图为ID3算法第一步后形成的部分决策树。这样综合起来看，就容易理解多了。1、overcast样例必为正，所以为叶子结点，总为yes；2、ID3无回溯，局部最优，而非全局最优，还有另一种树后修剪决策树。下图是ID3算法第

33、一步后形成的部分决策树： 如上图，训练样例被排列(pili)到对应的分支结点。分支Overcast的所有样例都是正例，所以成为目标(mbio)分类为Yes的叶结点。另两个结点将被进一步展开，方法是按照(nzho)新的样例子集选取信息增益最高的属性。1.3、C4.5算法1.3.1、ID3算法的改进：C4.5算法 C4.5，是机器学习算法中的另一个分类决策树算法，它是决策树(决策树也就是做决策的节点间的组织方式像一棵树，其实是一个倒树)核心算法，也是上文1.2节所介绍的ID3的改进算法，所以基本上了解了一半决策树构造方法就能构造它。 决策树构造方法其实就是每次选择一个好的特征以及分裂点作为当前节点

34、的分类条件。 既然说C4.5算法是ID3的改进算法，那么C4.5相比于ID3改进的地方有哪些呢？：用信息增益率来选择属性。ID3选择属性用的是子树的信息增益，这里可以用很多方法来定义信息，ID3使用的是熵(entropy，熵是一种不纯度度量准则),也就是熵的变化值，而C4.5用的是信息增益率。对，区别就在于一个是信息增益，一个是信息增益率。在树构造过程中进行剪枝，在构造决策树的时候，那些挂着几个元素的节点，不考虑最好，不然容易导致overfitting。对非离散数据(shj)也能处理。能够对不完整(wnzhng)数据进行处理 针对上述第一点，解释下：一般来说率就是用来取平衡用的，就像方差起的作

35、用差不多，比如有两个跑步的人，一个(y )起点是10m/s的人、其10s后为20m/s；另一个人起速是1m/s、其1s后为2m/s。如果紧紧算差值那么两个差距就很大了，如果使用速度增加率(加速度，即都是为1m/s2)来衡量，2个人就是一样的加速度。因此，C4.5克服了ID3用信息增益选择属性时偏向选择取值多的属性的不足。C4.5算法之信息增益率 OK，既然上文中提到C4.5用的是信息增益率，那增益率的具体是如何定义的呢？： 是的，在这里，C4.5算法不再是通过信息增益来选择决策属性。一个可以选择的度量标准是增益比率gainratio（Quinlan1986）。增益比率度量是用前面的增益度量Ga

36、in(S，A)和分裂信息度量SplitInformation(S，A)来共同定义的，如下所示： 其中，分裂信息度量被定义为(分裂信息用来衡量属性分裂数据的广度和均匀)： 其中S1到Sc是c个值的属性A分割S而形成的c个样例子集。注意分裂信息实际上就是S关于属性A的各值的熵。这与我们前面对熵的使用不同，在那里我们只考虑S关于学习到的树要预测的目标属性的值的熵。 请注意，分裂信息项阻碍选择值为均匀分布的属性。例如，考虑一个含有n个样例的集合被属性A彻底分割（译注：分成n组，即一个样例一组）。这时分裂信息的值为log2n。相反，一个布尔属性B分割同样的n个实例，如果恰好平分两半，那么分裂信息是1。如

37、果属性A和B产生同样的信息增益，那么根据增益比率度量，明显B会得分更高。 使用增益比率代替增益来选择属性产生的一个实际问题是，当某个Si接近S（|Si|S|）时分母可能为0或非常小。如果某个属性对于S的所有样例有几乎同样的值，这时要么导致增益比率未定义，要么是增益比率非常大。为了避免选择这种属性，我们可以采用这样一些启发式规则，比如先计算每个属性的增益，然后仅对那些增益高过平均值的属性应用增益比率测试（Quinlan1986）。 除了信息(xnx)增益，LopezdeMantaras（1991）介绍了另一种直接针对上述问题而设计的度量，它是基于(jy)距离的（distance-based）。这

38、个(zh ge)度量标准基于所定义的一个数据划分间的距离尺度。具体更多请参看：Tom M.Mitchhell所著的机器学习之3.7.3节。1.3.2、C4.5算法构造决策树的过程cpp HYPERLINK /v_july_v/article/details/7577684 o view plain view plain HYPERLINK /v_july_v/article/details/7577684 o copy copy HYPERLINK /v_july_v/article/details/7577684 o print print HYPERLINK /v_july_v/artic

39、le/details/7577684 o ? ?FunctionC4.5(R:包含连续属性的无类别属性集合,C:类别属性,S:训练集)/*返回一棵决策树*/BeginIfS为空,返回一个值为Failure的单个节点;IfS是由相同类别属性值的记录组成,返回一个带有该值的单个节点;IfR为空,则返回一个单节点,其值为在S的记录中找出的频率最高的类别属性值;注意未出现错误则意味着是不适合分类的记录；For所有的属性R(Ri)DoIf属性Ri为连续属性，则Begin将Ri的最小值赋给A1：将Rm的最大值赋给Am；/*m值手工设置*/ForjFrom2Tom-1DoAj=A1+j*(A1Am)/m;将

40、Ri点的基于Aj的最大信息增益属性(Ri,S)赋给A；End；将R中属性之间具有最大信息增益的属性(D,S)赋给D;将属性D的值赋给dj/j=1,2.m；将分别由对应于D的值为dj的记录组成的S的子集赋给sj/j=1,2.m;返回一棵树，其根标记为D;树枝标记为d1,d2.dm;再分别构造以下树:C4.5(R-D,C,S1),C4.5(R-D,C,S2).C4.5(R-D,C,Sm);EndC4.5Function C4.5(R:包含连续属性的无类别属性集合,C:类别属性,S:训练集)/*返回一棵决策树*/Begin If S为空,返回一个值为Failure的单个节点; If S是由相同类别属

41、性值的记录组成, 返回一个带有该值的单个节点; If R为空,则返回一个单节点,其值为在S的记录中找出的频率最高的类别属性值; 注意未出现错误则意味着是不适合分类的记录； For 所有的属性R(Ri) Do If 属性Ri为连续属性，则 Begin 将Ri的最小值赋给A1： 将Rm的最大值赋给Am；/*m值手工设置*/ For j From 2 To m-1 Do Aj=A1+j*(A1Am)/m; 将Ri点的基于Aj的最大信息增益属性(Ri,S)赋给A； End； 将R中属性之间具有最大信息增益的属性(D,S)赋给D; 将属性D的值赋给dj/j=1,2.m； 将分别由对应于D的值为dj的记录

42、组成的S的子集赋给sj/j=1,2.m; 返回一棵树，其根标记为D;树枝标记为d1,d2.dm; 再分别构造以下树: C4.5(R-D,C,S1),C4.5(R-D,C,S2).C4.5(R-D,C,Sm);End C4.51.3.3、C4.5算法实现中的几个关键步骤 在上文中，我们已经知道了决策树学习C4.5算法中4个重要概念的表达，如下： 接下来，咱们写下代码(di m)实现， 1、信息熵cpp HYPERLINK /v_july_v/article/details/7577684 o view plain view plain HYPERLINK /v_july_v/article/de

43、tails/7577684 o copy copy HYPERLINK /v_july_v/article/details/7577684 o print print HYPERLINK /v_july_v/article/details/7577684 o ? ?doubleC4_5:entropy(int*attrClassCount,intclassNum,intallNum)doubleiEntropy=0.0;for(inti=0;iclassNum;i+)doubletemp=(double)attrClassCounti)/allNum;if(temp!=0.0)iEntropy

44、-=temp*(log(temp)/log(2.0);returniEntropy;double C4_5:entropy(int *attrClassCount, int classNum, int allNum)double iEntropy = 0.0;for(int i = 0; i classNum; i+)double temp = (double)attrClassCounti) / allNum;if(temp != 0.0)iEntropy -= temp * (log(temp) / log(2.0);return iEntropy; 2、信息(xnx)增益率cpp HYP

45、ERLINK /v_july_v/article/details/7577684 o view plain view plain HYPERLINK /v_july_v/article/details/7577684 o copy copy HYPERLINK /v_july_v/article/details/7577684 o print print HYPERLINK /v_july_v/article/details/7577684 o ? ?doubleC4_5:gainRatio(intclassNum,vectorattriCount,doublepEntropy)int*att

46、riNum=newintattriCount.size();intallNum=0;for(inti=0;i(int)attriCount.size();i+)attriNumi=0;for(intj=0;jclassNum;j+)attriNumi+=attriCountij;allNum+=attriCountij;doublegain=0.0;doublesplitInfo=0.0;for(inti=0;i(int)attriCount.size();i+)gain-=(double)attriNumi)/allNum*entropy(attriCounti,classNum,attri

47、Numi);splitInfo-=(double)attriNumi)/allNum*(log(double)attriNumi)/allNum)/log(2.0);gain+=pEntropy;deleteattriNum;return(gain/splitInfo);double C4_5:gainRatio(int classNum, vector attriCount, double pEntropy)int* attriNum = new intattriCount.size();int allNum = 0;for(int i = 0; i (int)attriCount.size

48、(); i+)attriNumi = 0;for(int j = 0; j classNum; j+)attriNumi += attriCountij;allNum += attriCountij;double gain = 0.0;double splitInfo = 0.0;for(int i = 0; i (int)attriCount.size(); i+)gain -= (double)attriNumi) / allNum * entropy(attriCounti, classNum, attriNumi);splitInfo -= (double)attriNumi) / a

49、llNum * (log(double)attriNumi)/allNum) / log(2.0);gain += pEntropy;delete attriNum; return (gain / splitInfo); 3、选取最大增益(zngy)属性作为分类条件cpp HYPERLINK /v_july_v/article/details/7577684 o view plain view plain HYPERLINK /v_july_v/article/details/7577684 o copy copy HYPERLINK /v_july_v/article/details/757

50、7684 o print print HYPERLINK /v_july_v/article/details/7577684 o ? ?intC4_5:chooseAttribute(vectorattrIndex,vector*sampleCount)intbestIndex=0;doublemaxGainRatio=0.0;intclassNum=(int)(decisionsattrIndex(int)attrIndex.size()-1).size();/numberofclass/computertheclassentropyint*temp=newintclassNum;intal

51、lNum=0;for(inti=0;iclassNum;i+)tempi=sampleCount(int)attrIndex.size()-1ii;allNum+=tempi;doublepEntropy=entropy(temp,classNum,allNum);deletetemp;/computergainratioforeveryattributefor(inti=0;imaxGainRatio)bestIndex=i;maxGainRatio=gainR;returnbestIndex;int C4_5:chooseAttribute(vector attrIndex, vector

52、* sampleCount)int bestIndex = 0;double maxGainRatio = 0.0;int classNum = (int)(decisionsattrIndex(int)attrIndex.size()-1).size();/number of class/computer the class entropyint* temp = new intclassNum;int allNum = 0;for(int i = 0; i classNum; i+)tempi = sampleCount(int)attrIndex.size()-1ii;allNum +=

53、tempi;double pEntropy = entropy(temp, classNum, allNum);delete temp;/computer gain ratio for every attributefor(int i = 0; i maxGainRatio)bestIndex = i;maxGainRatio = gainR;return bestIndex; 4、还有一系列建树，打印(d yn)树的步骤，此处略过。1.4、读者(dzh)点评formWind：决策树使用于特征(tzhng)取值离散的情况，连续的特征一般也要处理成离散的(而很多文章没有表达出决策树的关键(gun

54、jin)特征or概念)。实际应用中，决策树overfitting比较的严重，一般要做boosting。分类器的性能上不去，很主要的原因在于特征的鉴别性不足，而不是分类器的好坏，好的特征才有好的分类效果，分类器只是弱相关。那如何提高特征的鉴别性呢？一是设计特征时尽量引入domainknowledge，二是对提取出来的特征做选择、变换和再学习，这一点是机器学习算法不管的部分(我说的这些不是针对决策树的，因此不能说是决策树的特点，只是一些机器学习算法在应用过程中的经验体会)。第二部分、贝叶斯分类 说实话，友人刘未鹏有一篇讲的贝叶斯的文章： HYPERLINK /2008/09/21/the-magi

55、cal-bayesian-method/ t _blank 数学之美番外篇：平凡而又神奇的贝叶斯方法，已经把贝叶斯讲的很清晰透彻了，我再讲也是如李白看到崔颢在黄鹤楼上所提的：登黄鹤楼昔人已乘黄鹤去，此地空余黄鹤楼；黄鹤一去不复返，白云千载空悠悠。 后便大为折服，已无什兴致再提了(偶现在就是这感觉)，然文章还得继续写。So，本文第二部分之大部分基本整理自未鹏兄之手(做了部分改动)，若有任何不妥之处，还望读者和未鹏兄海涵，谢谢。2.1、什么是贝叶斯分类 据维基百科上的介绍，贝叶斯定理是关于随机事件A和B的条件概率和边缘概率的一则定理。 如上所示，其中P(A|B)是在B发生的情况下A发生的可能性。在

56、贝叶斯定理中，每个名词都有约定俗成的名称：P(A)是A的先验概率或边缘概率。之所以称为先验是因為它不考虑任何B方面的因素。P(A|B)是已知B发生后A的条件概率（直白来讲，就是先有B而后=才有A），也由于得自B的取值而被称作A的后验概率。P(B|A)是已知A发生后B的条件概率（直白来讲，就是先有A而后=才有B），也由于得自A的取值而被称作B的后验概率。P(B)是B的先验概率或边缘概率，也作标准化常量（normalizedconstant）。 按这些(zhxi)术语，Bayes定理可表述(bio sh)为：后验概率=(相似(xin s)度*先验概率)/标准化常量，也就是說，后验概率与先验概率和相

57、似度的乘积成正比。另外，比例P(B|A)/P(B)也有时被称作标准相似度（standardisedlikelihood），Bayes定理可表述为：后验概率=标准相似度*先验概率。2.2贝叶斯公式如何而来 贝叶斯公式是怎么来的？下面再举wikipedia 上的一个例子：一所学校里面有 60% 的男生，40% 的女生。男生总是穿长裤，女生则一半穿长裤一半穿裙子。有了这些信息之后我们可以容易地计算“随机选取一个学生，他（她）穿长裤的概率和穿裙子的概率是多大”，这个就是前面说的“正向概率”的计算。然而，假设你走在校园中，迎面走来一个穿长裤的学生（很不幸的是你高度近似，你只看得见他（她）穿的是否长裤，而

58、无法确定他（她）的性别），你能够推断出他（她）是男生的概率是多大吗？ 一些认知科学的研究表明（决策与判断以及 HYPERLINK /subject/3199621/ t _blank Rationality for Mortals第12章：小孩也可以解决贝叶斯问题），我们对形式化的贝叶斯问题不擅长，但对于以频率形式呈现的等价问题却很擅长。在这里，我们不妨把问题重新叙述成：你在校园里面 HYPERLINK /wiki/Random_walk t _blank 随机游走，遇到了 N 个穿长裤的人（仍然假设你无法直接观察到他们的性别），问这 N 个人里面有多少个女生多少个男生。 你说，这还不简单：算

59、出学校里面有多少穿长裤的，然后在这些人里面再算出有多少女生，不就行了？ 我们来算一算：假设学校里面人的总数是 U 个。60% 的男生都穿长裤，于是我们得到了 U * P(Boy) * P(Pants|Boy) 个穿长裤的（男生）（其中 P(Boy) 是男生的概率 = 60%，这里可以简单的理解为男生的比例；P(Pants|Boy) 是条件概率，即在 Boy 这个条件下穿长裤的概率是多大，这里是 100% ，因为所有男生都穿长裤）。40% 的女生里面又有一半（50%）是穿长裤的，于是我们又得到了 U * P(Girl) * P(Pants|Girl) 个穿长裤的（女生）。加起来一共是 U * P

60、(Boy) * P(Pants|Boy) + U * P(Girl) * P(Pants|Girl) 个穿长裤的，其中有 U * P(Girl) * P(Pants|Girl) 个女生。两者一比就是你要求的答案。 下面我们把这个答案形式化一下：我们要求的是 P(Girl|Pants) （穿长裤的人里面有多少女生），我们计算的结果是 U * P(Girl) * P(Pants|Girl) / U * P(Boy) * P(Pants|Boy) + U * P(Girl) * P(Pants|Girl) 。容易发现这里校园内人的总数是无关的，两边同时消去U，于是得到P(Girl|Pants) =