《统计学习方法》python实现 chapter5 决策树1

看书的时候很忧伤，作为一个专门关注回归问题的时候，书上说主要关注的是分类问题。

决策树： 分类决策树模型是一种描述对实例进行分类的树形结构。决策树由结点（Node)和有向边（directed edge)组成。结点有两种类型：内部结点（internal node)和叶节点（leaf node).内部结点表示一个特征或属性，叶结点表示一个类。
信息增益
在信息论与概率统计中，熵（entropy)是表示随机变量不确定性的度量。设X是一个取有限个的离散随机变量，其概率分布为
$P(X = x_i )= p_i$
则随机变量X的熵的定义为 $H( X ) = -\sum_{i=1}^n p_i logp_i$
通常对数是以2或者 e为底，单位为比特（bit）或纳特（nat)。由于熵只依赖于X的分布，而与X的取值无关，所以也可以将X的熵记作 $H(p )$ ,即
$H(p) = -\sum_{i=1}^np_ilogp_i$
熵越大，随机变量的不确定性越大，从定义可验证 $0 \le H(P) \le logn$
信息增益表示得知特征X的信息而使得类Y的信息的不确定性减少的程度
定义：信息增益是，特征A对训练数据集D的信息增益g(D,A),定义为数据集D的经验熵H(D)与特征A给定条件下的经验条件熵H(D|A)之差，即 $g(D,A) = H(D) - H(D|A)$
信息增益大的特征具有更强的分类能力

信息增益算法

信息增益比
以信息增益作为划分数据集的特征，存在偏向于取值较多的特征的问题。使用信息增益比可以对这个问题进行校正。这是特征选择的另一准则。

信息增益比

ID3算法
ID3算法的核心是在决策树各个结点熵应用信息增益准则选择特征，递归地构建决策树。
具体方法：
从根结点开始，对结点计算所有可能的特征的信息增益，选择信息增益最大的特征作为结点的特征，由该特征的不同取值建立子结点；再对子节点递归地调用以上方法，构建决策树；直到所有特征的信息增益均很小或没有特征可以选择为止。最后得到一棵决策树。

ID3算法

ID3 算法只有树的生成，所以该算法生成的树容易产生过拟合

C4.5算法
与ID3算法唯一的区别在于，C4.5将信息增益改成了信息增益比

C4.5