决策树--从原理到Python实现

决策树基本上是每一本机器学习入门书籍必讲的东西，其决策过程和平时我们的思维很相似，所以非常好理解，同时有一堆信息论的东西在里面，也算是一个入门应用，决策树也有回归和分类，但一般来说我们主要讲的是分类，方便理解嘛。

虽然说这是一个很简单的算法，但其实现其实还是有些烦人，因为其feature既有离散的，也有连续的，实现的时候要稍加注意。

读一读

信息论的一些point：

（注：若看不清，可双击手机屏幕将图片放大）

然后加入一个叫信息增益的东西：

□.信息增益：(information gain)

g(D,A) = H(D)-H(D|A)

表示了特征A使得数据集D的分类不确定性减少的程度

□.信息增益比：(information gain ratio)

g‘(D,A)=g(D,A) / H(D)

□.基尼指数：

二.各种算法

1.ID3

ID3算法就是对各个feature信息计算信息增益，然后选择信息增益最大的feature作为决策点将数据分成两部分然后再对这两部分分别生成决策树。（注：若看不清，可双击手机屏幕将图片放大）

2.C4.5

C4.5与ID3相比其实就是用信息增益比代替信息增益，应为信息增益有一个缺点： 信息增益选择属性时偏向选择取值多的属性

算法的整体过程其实与ID3差异不大：

3.CART

CART(classification and regression tree)的算法整体过程和上面的差异不大，然是CART的决策是二叉树的每一个决策只能是“是”和“否”，换句话说，即使一个feature有多个可能取值，也只选择其中一个而把数据分类两部分而不是多个，这里我们主要讲一下分类树，它用到的是基尼指数：

三.代码及实现（注：若看不清，可双击手机屏幕将图片放大）

好吧，其实我就想贴贴代码而已…… 纯属toy~~~~~实现的CART算法：

这个maketree让我想起了线段树………………代码里的变量基本都有说明

试验代码：

四.reference

【1】：《机器学习》 -mitchell，卡耐基梅龙大学

【2】：《统计学习方法》-李航

(Via:CSDN博客 作者pi9nc)