1.决策树概述

1.1 决策树模型简介

决策树是一种树形结构，其中每个内部节点表示一个属性上的测试，每个分支代表一个测试输出，每个叶子节点代表一种类别。

树的组成：

根节点：第一个选择点
非叶子结点与分支：中间过程
叶子节点：最终的决策结果

1.2 决策树建立步骤

1.3 三种经典的决策树生成算法

决策树建立过程中，选择合适的特征及该特征下选择合适的决策值对决策树的结构影响很大，对决策树的研究基本上集中于该问题，该问题习惯上称为样本集分裂，依其解决方法可将决策树算法分为ID3、C4.5、CART等三种。

基于信息增益的ID3算法；
基于信息增益率的C4.5算法；
基于基尼指数的CART算法

2 信息熵与信息增益

2.1 信息量

信息的概念：信息就是对不确定性的消除。如一条天气预报消息“明天气温下降8度”可以消除人们对明天天气变化的不确定性。
消除的不确定性越大，那么信息量就应该越大。不确定性的消除是根据人们的先验知识来比较的。再比如，“中国足球队打败巴西足球队”比“中国乒乓球队打败巴西乒乓球队”所消除的不确定性就大的多。因此，预言以往发生小概率的事件的消息所带来的信息量就要大。以往发生的概率叫做先验概率，用p表示。香农基于先验概率来定义信息量公式：

 $I(x)=log(\frac{1}{p})=-log(p)$

假设中国足球队和巴西足球队曾经有过8次比赛，其中中国队胜1次。以U₁表示未来的中巴比赛中国队胜的事件，那么