决策树

决策树

决策树三要素

1. 特征选择

2. 决策树生成

3. 决策树剪枝

   1. 预剪枝

      限制树的深度，叶子节点个数，叶子节点样本数，信息增益等

   2. 后剪枝

      正则化

ID3

  ID3是根据信息增益来选择特征，将数据划分成多份，构成决策树。

信息增益

  信息增益是什么呢？划分数据前后 数据中“信息量”的 变化，通常选择信息增益最大的特征作为当前划分的依据。

信息熵

  如何衡量“信息量”呢？这里引入熵的概念，熵表示信息不确定性的程度，熵越大，不确定性越强，熵越小，不确定性越小(越确定)。熵的公式如下：

\[H(X)=-sum_{i=1}^{i=n}p_{i}*log(p_{i})\]

  n样本是分类的个数，\(p_{i}\)表示样本分类为类别i的概率。熵的大小是和每个类别的概率有关的。

  熵和概率的关系如上图所示：随着概率从小变大，熵的值先增大道最大值然后降到最小值，当概率值\(p=0.5\)时，熵值最大，说明不确定性越大，当概率值\(p=0.9\)时，熵值最小，不确定性越小。

条件熵

  对于条件熵，则是当X的取值确定之后，在这个条件下的熵值。即当我们确定了样本某特征X的取值之后，即在这个条件下的熵值，

\[H(Y|X)=sum_{i=1}^{i=n}p_{i}*H(Y|X=x_{i})\]

  举个例子我们有一波样本D，共有k个类别\(C_{k}\)，它的熵为H(D)，某一特征A有n个取值，依据特征A可以将数据集划分为n个子集，分别为\(D_{1}\)，\(D_{2}\)...\(D_{n}\)，首先计算每个子集的信息熵H(D|A)，然后计算每个子集的样本占总样本的比例\(p_{i}\)，然后将每个子集的信息熵*比例 加起来，就是特征A的条件熵。

  所以回到ID3算法上，特征A对数据集D的信息增益就是\[g(D,A)=H(D)-H(D|A)\]。

  在生成树的过程中，每次分裂时选择特征就是依据信息增益来选择最佳分裂点。选好最佳分裂点之后，依据特征取值将样本分成n(特征A取值的个数)叉树，然后在每个子树下面继续进行分裂，直到树生成完成。

ID3算法的缺点：

1. ID3没有考虑连续值，对于特征取值为连续值的情况无法适用。
2. ID3选用信息增益作为分裂的依据，会更倾向于特征属性值多的作为分裂节点，举个例子：\(-1/3*log(1/3)*3\) > \(-1/2*log(1/2)*2\)。
3. ID3对于缺失值也无法出来，而且更容易过拟合。

为什么ID3倾向于特征属性值偏多的特征？

  信息增益是整个数据集的经验熵与特征a对整个数据集的经验条件熵的差值，信息增益越大即经验条件熵越小 通俗的来讲,信息增益反映的给定一个条件以后不确定性减少的程度(特征A使得数据集的分类不确定性减少的程度) , 肯定是是分得越细的数据集确定性更高,也就是条件熵越小,信息增益越大。