文档介绍：第5讲决策树的〃$算法一・ZD简介:(下文有具体介绍)准则选择特征,递归地构建决策树,具体方法是:从根节点开始,对结点计算所有可能的特征的信息增益,选择信息增益最大的特征作为结点的特征,由该特征的不同取值建立于子结点;再对子结点递归地调用以上方法,构建决策树;直到所有特征的信息增益均很小或没有特征可以选择为止。最后得到一个决策树。〃乂相当于用极大似然法进行概率模型的选择。为了更好地理解算法,我们首先来看一个例子。:一件事有四种可能A,B,C,D,且每种可能性相同则P(A)=P(B)二P(C)二P(D)二丄,如果已知D不可能发生,则P(A)=P(B)=P(C)=-,此时,3不确定性变小,嫡变小;现有1000组数据:属性$1$2S3$4$5数据类别样本X,100111样本X2011002样本X3110111••••思考:有没有一种属性占有很重要的地位?5种属性都考虑,有相对重要的和相对不重要的,怎么挑出重要的呢?三•若1000组数据,有G,C2,C33种属性,,;现有新样本,共有5种属性,d=(51,52,53,54,5s)猜其有C】的属性,若已知S2=0,且每个取值只有两种。此时S2=o,则我们只看S2=o的情况下的GGG,相当于条件概率,若有700组数据,,C2=,C3=0,即加入i定的信息模型的精度变高了。若S2=l时,有300组数据,C,=0,C2=,C3=,则精度明显提高。此时,我们提出原则:逐一测试SPS2,S3,S4,S5,计算他们分别等于0和等于1时的概率,有了概率就可以算嫡。我们定义原嫡二一工用10朗新久商二一7001000工严°1。戒円+3001000工严戶10酿円)■I若原来CPC2,,0,,贝9原嫡二一工PiloM>o若s2=o,cpc2,c3分别为ioo,新爛=0;若s2=i,ggg分别为o,o,1,新嫡=o;由此可见,新嫡变小了,这种新属性的加入,嫡的变化最大,说明这种属性有绝对性的地位。步骤:1•用所有的数据计算爛,用所有属性算新爛,原爛与新爛的差叫做信息增益;若S?最大。,一堆300个数据,另一堆700个数据,若现剩4个属性,再按步骤1找出信息增益最大的那个,画出如下的图以上即是决策树。内测:模型的精度几乎100%外测:模型的精度很低,即泛化性弱,过拟合了。这种情况怎么办呢?我们采用剪枝(差不多就停,不分到底)的办法,剪枝后,内测精度变低,外测精度变高,从而避免了过分拟合。C45算法:算信息增益,,我们就分成15堆,我们发现,嫡很快变小且内测精度几乎100%,外测却很低,说明这种算法不好,因此我们进行调整,选出某种属性(选信息增益大的)剪掉。随机森林:1000组数据,用随机处理器,有放回的抽取1000个数据,建立决策树,不剪枝,用同样的方法造出500棵树,把第一棵树的数据代入第二棵树看类型,把第二棵树的数据代入第三棵树看类型,以此类推•…取出最后最多的。六•决策树的实现图G=G(V,E)其中V表示顶点集合,E表示边集集合。例如下图:无方向且边无权重V二{1,2,3,4,5,6,7}E=l,22,3 1,4 1,3 2,5 3,6 3,