一、决策树的思想

决策树是一种分类方法

1.1 一些基本概念

决策树的构建是根据训练集构建的，根据同一个数据集可以构建不同的决策树，即特征可以随机组合。

对于同一训练集构建的不同决策树，我们需要衡量多个决策树的优劣，即评价一个决策树的好坏以及如何建立一个好的决策树是一个待解决的问题。

决策树尽可能与训练集一致，其次决策树应该具有更好的泛化能力。但是，我们不可能建立所有可能的决策树，再从中选择一个最好的。

由于特征数量的多少，我们不能建立所有的决策树，所以使用启发式的方法构建决策树，即：优先使用分类效果好的特征（当然，特征的效果好坏依赖于数据集）。

前面提到，采用启发式方法构建决策树需要按照特征效果依次构建决策树，那么判断特征效果的好坏的过程就叫做特征评价。

这里，首先引入数据集的熵这一概念。熵，是对数据集混乱程度的评价：

$H(D)=-\sum_{i=1}^{n}{P_i}·log(P_i)$

这里熵的引入和信息论信源的熵相同（以2为底），熵越大，数据集越混乱。

条件熵：特征$A$按其取值将数据集$D$划分为$n$个子数据集$D_i$，子数据集熵的期望就是该特征的条件熵（加权平均）。

$H(D|A)=\sum_{i=1}^{n}{\frac{|D_i|}{|D|}H(D_i)}$

其中$||$表示$$数据集中包含的样本数量。

条件熵反映了对数据集$D$实施该特征后数据的混乱程度，$A$表是特征。

信息增益是指对数据集$D$实施特征$A$后，熵的下降程度，反映了特征效果的好坏：

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

其中$g(D,A)$表示数据集$D$下$A$的信息增益。