Li Junli 李军利
Apr 21 2019
决策树算法
决策树算法在机器学习中算是很经典的一个算法系列了。它既可以作为分类算法,也可以作为回归算法,同时也特
别适合集成学习比如随机森林。本文对决策树算法原理做一个总结,第一章对ID3,C4.5的算法思想做了总结,第
二章重点对CART算法做一个详细的介绍。选择CART做重点介绍的原因是scikit-learn使用了优化版的CART算法作
为其决策树算法的实现。
1. ID3与C4.5算法
机器学习算法其实很古老,作为一个码农经常会不停的敲if,else if,else,其实就已经在用到决策树的思想了。只
是你有没有想过,有这么多条件,用哪个条件特征先做if,哪个条件特征后做if比较优呢?怎么准确的定量选择这个
标准就是决策树机器学习算法的关键了。1970年代,一个叫昆兰的大牛找到了用信息论中的熵来度量决策树的决
策选择过程,方法一出,它的简洁和高效就引起了轰动,昆兰把这个算法叫做ID3,后续有很多改进算法,比如
C4.5、C5.0 。下面介绍ID3等算法是怎么选择特征的。
1.1 ID3算法的信息论基础
首先,我们需要熟悉信息论中熵的概念。熵度量了事物的不确定性,越不确定的事物,它的熵就越大。具体的,随
机变量X的熵的表达式如下:
其中n代表X的n种不同的离散取值。而pi代表了X取值为i的概率,log为以2或者e为底的对数。举个例子,比如X有2
个可能的取值,而这两个取值各为1/2时X的熵最大,此时X具有最大的不确定性。值为:
若一个值概率大于1/2,另一个值概率小于1/2,则不确定性减少,对应的熵也会减少。比如一个概率1/3,一个概
率2/3,则对应熵为:
熟悉了一个变量X的熵,很容易推广到多个个变量的联合熵,这里给出两个变量X和Y的联合熵表达式:
有了联合熵,又可以得到条件熵的表达式H(Y|X),条件熵类似于条件概率,它度量了我们的Y在知道X以后剩下的不
确定性。已知X的条件下,Y的条件熵推导:
评论0