决策树与随机森林

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

1、决策树与随机森林邹博北京10月机器学习班&ML在线公开课第1期2015年1月11日目标任务与主要内容复习信息熵熵、联合熵、条件熵、互信息决策树学习算法信息增益ID3、C4.5、CARTBagging与随机森林的思想投票机制分类算法的评价指标ROC曲线和AUC值2决策树的实例(Weka自带测试数据)注：Weka的全名是怀卡托智能分析环境(WaikatoEnvironmentforKnowledgeAnalysis)，是一款免费的，非商业化(与之对应的是SPSS公司商业数据挖掘产品--Clementine)的，基于JA

2、VA环境下开源的机器学习(machinelearning)以及数据挖掘(dataminining)软件。它和它的源代码可在其官方网站下载。3复习：熵将离散随机变量X的概率分布为P(X=xi)，则定义熵为：若P为连续随机变量，则概率分布变成概率密度函数，求和符号变成积分符号。在不引起混淆的情况下，下面谈到的“概率分布函数”，其含义是：1、若X为离散随机变量，则该名称为概率分布函数；2、若X为连续随机变量，则该名称为概率密度函数。4对熵的理解熵是随机变量不确定性的度量，不确定性越大，熵值越大；若随机变量退化成定值，熵为

3、0均匀分布是“最不确定”的分布熵其实定义了一个函数(概率分布函数)到一个值(信息熵)的映射。P(x)H(函数数值)泛函回忆一下关于“变分推导”章节中对于泛函的内容。5联合熵和条件熵两个随机变量X，Y的联合分布，可以形成联合熵JointEntropy，用H(X,Y)表示H(X,Y)–H(Y)(X,Y)发生所包含的信息熵，减去Y单独发生包含的信息熵——在Y发生的前提下，X发生“新”带来的信息熵该式子定义为Y发生前提下，X的熵：条件熵H(X

4、Y)=H(X,Y)–H(Y)6推导条件熵的定义式7相对熵相对熵，又称互熵，交

5、叉熵，鉴别信息，Kullback熵，Kullback-Leible散度等设p(x)、q(x)是X中取值的两个概率分布，则p对q的相对熵是说明：相对熵可以度量两个随机变量的“距离”在“贝叶斯网络”、“变分推导”章节使用过一般的，D(p

6、

7、q)≠D(q

8、

9、p)D(p

10、

11、q)≥0、D(q

12、

13、p)≥0提示：凸函数中的Jensen不等式8互信息两个随机变量X，Y的互信息，定义为X，Y的联合分布和独立分布乘积的相对熵。I(X,Y)=D(P(X,Y)

14、

15、P(X)P(Y))9计算H(X)-I(X,Y)10整理得到的等式H(X

16、Y)

17、=H(X,Y)-H(Y)条件熵定义H(X

18、Y)=H(X)-I(X,Y)根据互信息定义展开得到有些文献将I(X,Y)=H(Y)–H(Y

19、X)作为互信息的定义式对偶式H(Y

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

21、X)=H(Y)-I(X,Y)I(X,Y)=H(X)+H(Y)-H(X,Y)有些文献将该式作为互信息的定义式试证明：H(X

22、Y)≤H(X)，H(Y

23、X)≤H(Y)11强大的Venn图：帮助记忆12决策树示意图13决策树(DecisionTree)决策树是一种树型结构，其中每个内部结点表示在一个属性上的测试，每个分支

24、代表一个测试输出，每个叶结点代表一种类别。决策树学习是以实例为基础的归纳学习。决策树学习采用的是自顶向下的递归方法，其基本思想是以信息熵为度量构造一棵熵值下降最快的树，到叶子节点处的熵值为零，此时每个叶节点中的实例都属于同一类。14决策树学习算法的特点决策树学习算法的最大优点是，它可以自学习。在学习的过程中，不需要使用者了解过多背景知识，只需要对训练实例进行较好的标注，就能够进行学习。显然，属于有监督学习。从一类无序、无规则的事物(概念)中推理出决策树表示的分类规则。15决策树学习的生成算法建立决策树的关键，即在当

25、前状态下选择哪个属性作为分类依据。根据不同的目标函数，建立决策树主要有一下三种算法。ID3C4.5CART16信息增益概念：当熵和条件熵中的概率由数据估计(特别是极大似然估计)得到时，所对应的熵和条件熵分别称为经验熵和经验条件熵。信息增益表示得知特征A的信息而使得类X的信息的不确定性减少的程度。定义：特征A对训练数据集D的信息增益g(D,A)，定义为集合D的经验熵H(D)与特征A给定条件下D的经验条件熵H(D

26、A)之差，即：g(D,A)=H(D)–H(D

27、A)显然，这即为训练数据集D和特征A的互信息。17基本记号设

28、训练数据集为D，

29、D

30、表示其容量，即样本个数。设有K个类Ck，k=1,2,…,K，

31、Ck

32、为属于类Ck的样本个数。Σk

33、Ck

34、=

35、D

36、。设特征A有n个不同的取值{a1,a2…an}，根据特征A的取值将D划分为n个子集D1,D2,…Dn,

37、Di

38、为Di的样本个数，Σi

39、Di

40、=D。记子集Di中属于类Ck的样本的集合为Dik，

41、Dik

42、为Dik的样本个数。18信