1.决策树的原理及核心

1.1 原理

决策树是一种非参数的非监督学习算法
输入： 是具有一系列特征和标签的数据
输出：训练集中的数据总结出的决策的规则，以树状图的结构来描述规则
意义：解决分类或回归问题总结：决策树就是根据**特定规则****，不断地选择特征(也成属性)作为分支节点，由上至下的不断补充节点，构建的一颗可以描述训练集隐含的决策规则的树🌲

1.2 决策树的划分选择

1.2.1信息增益

  信息熵〞(information entropy)是度量样本集合纯度最常⽤的⼀种指标.
假定当前样本集合D中，第k类样本所占的⽐例为p_k（k=1,2,|y|)，则D
的信息熵定义为:

                               \operatorname{Ent}(D)=-\sum_{k=1}^{|\mathcal{Y}|} p_k \log _2 p_k

    假定离散属性 a 有 V 个可能的取值 \left{a^1, a^2, \ldots, a^V\right}, 若使用 a 来对样本集 D 进行划分, 则会产生 V 个分支结点, 其中第 v 个分支结点包含了 D 中所有在属性 a上取值为 a^v 的样本, 记为 D^v. 我们可上式，计算出 D^v 的信息熵,再考虑到不同的分支结点所包含的样本数不同, 给分支结点赋予权重 \left|D^v\right| /|D|,即样本数越多的分支结点的影响越大, 于是可计算出用属性 a 对样本集 D 进行划分所获得的 “信息增益” (information gain)
\operatorname{Gain}(D, a)=\operatorname{Ent}(D)-\sum_{v=1}^V \frac{\left|D^v\right|}{|D|} \operatorname{Ent}\left(D^v\right)

      一般而言, 信息增益越大,则意味着使用属性 a 来进行划分所获得的 “纯度提升” 越大. 因此, 我们可用信息增益来进行决策树的划分属性选择, 选择属
a_*=\underset{a \in A}{\arg \max } \operatorname{Gain}(D, a).
著名的 ID3 决策树学习算法 [Quinlan, 1986] 就是以信息增益为准则来选择划分属性.
以表 4.1 中的西瓜数据集 2.0 为例, 该数据集包含 17 个训练样例, 用以学习一棵能预测没剖开的是不是好瓜的决策树.

显然, |\mathcal{Y}|=2. 在决策树学习开始时, 根结点包含 D 中的所有样例, 其中正例占 p_1=\frac{8}{17}, 反例占 p_2=\frac{9}{17}. 于是, 根据式(4.1)可计算出根结点的信息熵为
\operatorname{Ent}(D)=-\sum_{k=1}^2 p_k \log _2 p_k=-\left(\frac{8}{17} \log _2 \frac{8}{17}+\frac{9}{17} \log _2 \frac{9}{17}\right)=0.998 .

1.2.2 增益率

如果，将“编号”也作为一个划分属性，“编号”将产生17个分支，且每个分支仅包含一个样本，这些分支的节点的纯度已然是最大了，为了避免这个问题，提出了增益率的概念，公式如下：
\operatorname{Gain_ ratio}(D, a)=\frac{\operatorname{Gain}(D, a)}{\operatorname{IV}(a)},
\operatorname{IV}(a)=-\sum_{v=1}^V \frac{\left|D^v\right|}{|D|} \log _2 \frac{\left|D^v\right|}{|D|}
IV(a)称为属性a的“固有值”(intrinsic value) , 属性a的可能取值数⽬越多(即V越⼤），则IV(a）的值通常会越⼤• 例如，对表4.1 的西⽠数据集2.0，有IV(触感）=0.874（V =2),IV（⾊泽）=1.580(V = 3）,
IV(编号）=4.088 （V =17).

1.2.3 基尼指数

  CART使用了基尼指数，来选择划分属性，数据集D的纯度可用基尼值来度量如下：
          \begin{aligned} \operatorname{Gini}(D)&=\sum_{k=1}^{|\mathcal{Y}|} \sum_{k^{\prime} \neq k} p_k p_{k^{\prime}} \&=1-\sum_{k=1}^{|\mathcal{Y}|} p_k^2 .\end{aligned}
    Gini(D)反映了，从数据集合D中随机抽取两个样本不一致的概率，故基尼值越小，数据集D的纯度就越高。
基尼指数的定义，可使用如下公式表示：

         \operatorname{Gini_ index}(D, a)=\sum_{v=1}^V \frac{\left|D^v\right|}{|D|} \operatorname{Gini}\left(D^v\right).

使用时，选择那个使得划分后，基尼指数最小的属性作为最优划分属性：
         a_*=\underset{a \in A}{\arg \min } Gini_index (D, a).

1.3 减枝处理

1.3.1 预剪枝

1.3.2 后剪枝

1.4 缺值处理

1.5 多变量决策树

2.sklearn的决策树实践