决策树和随机森林

《决策树和随机森林》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、决策树和随机森林牛客网邹伟2015年1月23日64-1目标任务与主要内容掌握信息熵熵、联合熵、条件熵、互信息决策树学习算法信息增益ID3、C4.5、CARTBagging与随机森林的思想投票机制64-2CART输入数据x：M个样本数据，每个数据包括年龄、性别、职业、每日使用计算机时间等输出y：该样本是否喜欢计算机游戏64-3随机森林64-4决策树：Level64-5定义信息量原则：某事件发生的概率小，则该事件的信息量大。如果两个事件X和Y独立，即p(xy)=p(x)p(y)，假定X和Y的信息量分别为h(X)和h(Y)，则二者同时发生的信息量应该为h(XY)=h(X)

2、+h(Y)。定义事件X发生的信息量：hxlogx2思考：事件X的信息量的期望如何计算呢？64-6熵对随机事件的信息量求期望，得熵的定义：HXpxlnpxxX注：经典熵的定义，底数是2，单位是bit本例中，为分析方便使用底数e若底数是e，单位是nat(奈特)64-7联合熵和条件熵两个随机变量XY的联合分布形成联合熵，用H(X,Y)表示H(X,Y)–H(Y)(X,Y)发生所包含的熵，减去Y单独发生包含的熵：在Y发生的前提下，X发生“新”带来的熵该式子定义为Y发生前提下，X的熵：条件熵H(X

3、Y)64-8推导条件熵的定义式H(X,Y)H(Y)

4、p(x,y)logp(x,y)p(y)logp(y)x,yyp(x,y)logp(x,y)p(x,y)logp(y)x,yyxp(x,y)logp(x,y)p(x,y)logp(y)x,yx,yp(x,y)p(x,y)logx,yp(y)p(x,y)logp(x

5、y)x,y64-9根据条件熵的定义式，可以得到H(X,Y)H(X)p(x,y)logp(y

6、x)x,yp(x,y)logp(y

7、x)xyp(x)p(y

8、x)logp(y

9、x)xyp(x)p(y

10、x)logp(y

11、x)xyp(x)p

12、(y

13、x)logp(y

14、x)xyp(x)HY

15、Xxx64-10互信息两个随机变量X，Y的互信息，定义为X，Y的信息熵减去X，Y的联合熵。I(X,Y)=H(X)+H(Y)-H(X,Y)p(x,y)I(X,Y)p(x,y)logx,yp(x)p(y)64-11计算互信息定义式I(X,Y)=H(X)+H(Y)-H(X,Y)IX,YHXHYHX,Ypxlogpxpylogpypx,ylogpx,yxyx,ypx,ylogpx

16、px,ylogpypx,ylogpx,yxyyxx,ypx,ylogpxpx,ylogpypx,ylogpx,yx,yx,yx,ypx,ylogpx,ylogpxlogpyx,ypx,ypx,ylogx,ypxpy64-12条件熵与互信息的等式互信息：I(X,Y)=H(X)+H(Y)-H(X,Y)条件熵：H(X

17、Y)=H(X,Y)-H(Y)带入，得：I(X,Y)=H(X)-H(X

18、Y)条件熵：H(Y

19、X)=H(X,Y)-

20、H(X)带入，得：I(X,Y)=H(Y)-H(Y

21、X)由I(X,Y)≥0，得H(X)≥H(X

22、Y)，H(Y)≥H(Y

23、X)如何用自然语言解释H(X)≥H(X

24、Y)？64-13强大的Venn图：帮助记忆64-14决策树的实例注：Weka的全名是怀卡托智能分析环境(WaikatoEnvironmentforKnowledgeAnalysis)，是一款免费的，非商业化(与之对应的是SPSS公司商业数据挖掘产品--Clementine)的，基于JAVA环境下开源的机器学习(machinelearning)以及数据挖掘(dataminining)软件。它和它的源代码可在其官方网站下载。64-1

25、5决策树示意图64-16决策树(DecisionTree)决策树是一种树型结构，其中每个内部结点表示在一个属性上的测试，每个分支代表一个测试输出，每个叶结点代表一种类别。决策树学习是以实例为基础的归纳学习。决策树学习采用的是自顶向下的递归方法，其基本思想是以信息熵为度量构造一棵熵值下降最快的树，到叶子节点处的熵值为零，此时每个叶节点中的实例都属于同一类。64-17决策树学习的生成算法建立决策树的关键，即在当前状态