机器学习 - 决策树算法[二]

作者: nlpming | 来源:发表于2021-07-01 01:09 被阅读0次

Python学习——决策树中纯度算法的实现
决策树算法
决策树算法及python实现
Machine Learning in Action:Decis
决策树算法总结
算法工程师知识树持续更新
机器学习之决策树
实现简单的决策树最优划分
DTrees详尽剖析与可视化展示（上）
SVM 随笔

1. CART决策树

分类与回归树（classification and regression tree, CART）模型由Breiman等人在1984年提出。CART决策树是二叉树，内部结点特征的取值为“是”和“否”，左分支是取值为“是”的分支，右分支是取值为“否”的分支。这样的决策树等价于递归地二分每个特征，将输入空间即特征空间划分为有限个单元，并在这些单元上确定预测的概率分布，也就是在输入给定的条件下输出的条件概率分布。
CART决策树的生成就是递归地构建二叉决策树的过程。对回归树用平方误差最小化准则，对分类树用基尼指数最小化准则，进行特征选择生成二叉树。

2. 回归树的生成

假设 $X$ 与 $Y$ 分别为输入和输出变量，并且 $Y$ 是连续变量，给定训练数据集： $D = \{ (x_1,y_1),(x_2,y_2),...,(x_N,y_N) \}$ 。假设已经将输入空间（特征空间）划分为 $M$ 个单元 $R_1,R_2,...,R_M$ ，并且在每个单元 $R_m$ 上有一个固定的输出值 $c_m$ ，于是回归树模型可表示为：
$f(x) = \sum_{m=1}^{M} c_mI(x \in R_m)$
当输入空间的划分确定时，可以用平方误差 $\sum_{x_i \in R_m} (y_i - f(x_i))^2$ 来表示回归树对于训练数据的预测误差，用平方误差最小化的准则求解每个单元上的最优输出值。上式子中 $I$ 为指示函数，表示 $x$ 最终是否落在区域 $R_m$ ，如果在则为1否则为0；
最小二乘回归树生成算法 如下：

输入：训练数据 $D$ ；
输出：回归树 $f(x)$ ；
在训练数据所在的输入空间中，递归地将每个区域划分为两个子区域并决定每个子区域上的输出值，构建二叉决策树。
（1）选择最优切分变量 $j$ 与切分点 $s$ ，求解：
$\mathop{min} \limits_{j,s} \left[ \mathop{min} \limits_{c_1} \sum_{x_i \in R_1(j,s)} (y_i - c_1)^2 + \mathop{min} \limits_{c_2} \sum_{x_i \in R_2(j,s)} (y_i - c_2)^2 \right]$
（2）用选定的对 $(j, s)$ 划分区域并决定相应的输出值：每个区域的最优值，为区域中所有样本取值的均值。 $x^{(j)}$ 表示特征向量 $x$ 的第 $j$ 维取值。
$\begin{align} R_{1}(j,s) &= \{ x| x^{(j)} <= s \} \\ R_{2}(j,s) &= \{ x| x^{(j)} > s \} \end{align}$
$\hat{c}_m = \frac{1}{N_m} \sum_{x_i \in R_{m}(j,s)} y_i, x \in R_m, m=1,2$
（3）继续对两个子区域调用步骤（1），（2），直至满足停止条件。
（4）将输入空间划分为 $M$ 个区域 $R_1,R_2,...,R_M$ ，生成决策树：
$f(x) = \sum_{m=1}^{M} c_mI(x \in R_m)$

3. 分类树的生成

分类树用基尼指数选择最优特征，同时决定该特征的最优二值切分点。分类问题中，假设有 $K$ 个类，样本点属于第 $k$ 类的概率为 $p_k$ ，则概率分布的基尼指数定义为：
$Gini(p) = \sum_{k=1}^{K} p_k(1-p_k) = 1 - \sum_{k=1}^{K} p_k^2$
对于给定的样本集合 $D$ ，其基尼指数为：这里 $C_k$ 是 $D$ 中属于第 $k$ 类的样本子集， $K$ 是类的个数。
$Gini(D) = 1 - \sum_{k=1}^{K} \left( \frac{|C_k|}{|D|} \right)^2$
如果样本集合 $D$ 根据特征 $A$ 是否取某一可能值 $a$ 被划分成 $D_1$ 和 $D_2$ 两部分，则在特征 $A$ 的条件下，集合 $D$ 的基尼指数定义为：
$Gini(D, A) = \frac{|D_1|}{|D|} Gini(D_1) + \frac{|D_2|}{|D|} Gini(D_2)$
基尼指数 $Gini(D)$ 表示集合 $D$ 的不确定性，基尼指数 $Gini(D,A)$ 表示经过 $A=a$ 分割后集合 $D$ 的不确定性。基尼指数值越大，样本集合的不确定性也越大，这一点与熵相似。

4. CART决策树生成算法

输入：训练数据集 $D$ ，停止计算的条件；
输出：CART决策树；
根据训练数据集，从根结点开始，递归地对每个结点进行以下操作，构建二叉树：
（1）设结点的训练数据集为 $D$ ，计算现有特征对该数据集的基尼指数。此时，对每一个特征 $A$ ，对其可能的每个取值 $a$ ，根据样本点对 $A=a$ 的测试为“是”或者“否”将 $D$ 分割成 $D_1$ 和 $D_2$ 两个部分。计算 $A=a$ 的基尼指数。
（2）在所有可能的特征 $A$ 以及它们所有可能的切分点 $a$ 中，选择基尼指数最小的特征以及对应的切分点作为最优特征与最优切分点。 依据最优特征与最优切分点，从根结点生成两个子结点，将训练数据集依特征分配到两个子结点中去。
（3）对两个子结点递归地调用（1），（2），直到满足停止条件为止。算法停止计算的条件是结点中的样本个数小于预定阈值，或样本的基尼指数小于预定阈值（样本基本属于同一类），或者没有更多特征。
（4）生成CART决策树。

举例说明：假设训练数据如下表所示， $A_1,A_2,A_3,A_4$ 分别表示特征：年龄、有工作、有自己的房子、信贷情况。并以1，2，3表示年龄为青年、中年、老年，以1，2表示有无工作和有无自己的房子。1，2，3表示表示信贷情况为非常好、好和一般。
image.png
求特征 $A_1$ 的基尼指数：
$Gini(D, A_1=1) = \frac{5}{15} \left( 2 * 2/5 (1-2/5) \right) + \frac{10}{15} (2 * 7/10 * (1-7/10)) = 0.44$
$Gini(D, A_1=2) = 0.48$
$Gini(D, A_1=3) = 0.44$
同样的方法继续求，其他特征各个切分点对于的基尼指数，最终可知 $Gini(D, A_3=1) = 0.27$ 最小，所以选择特征 $A_3 = 1$ 为最优切分点。

参考资料

《统计学习方法》 - 李航
机器学习 - 决策树算法[一] https://www.jianshu.com/p/b7dc0afb4804

Python学习——决策树中纯度算法的实现
决策树决策树算法是机器学习中的一个基础算法，该算法有着诸多的优点。在python中实现决策树，现阶段都已经集成中...
决策树算法
决策树决策树也是经常使用的数据挖掘算法，其不用了解机器学习的知识，就能搞明白决策树是如何工作的。决策树算法能够...
决策树算法及python实现
决策树算法是机器学习中的经典算法 1.决策树(decision tree) 决策树是一种树形结构，其中每个内部节点...
Machine Learning in Action:Decis
概述决策树这个算法比较接地气，就算你根本不懂机器学习算法也可以很好的理解决策树，决策树之前的算法就已经解释过了。...
决策树算法总结
目录一、决策树算法思想二、决策树学习本质三、总结一、决策树（decision tree）算法思想：决策树...
算法工程师知识树持续更新
机器学习算法监督学习分类模型LRSVM决策树NB回归模型线性回归最小二乘融合模型baggingRFboosti...
机器学习之决策树
决策树是机器学习最基础的算法之一，基于决策树可衍生出AdaBoostTree、随机森林、GBDT等高级算法。本文重...
实现简单的决策树最优划分
决策树（Decision Tree）是一种基本的分类与回归方法。是一种典型的非参数学习的机器学习算法。决策树算法的...
DTrees详尽剖析与可视化展示（上）
今天我们来介绍一种机器学习中的经典算法——决策树（DTrees）。在机器学习中算法可分为监督学习，非监督学习，半监...
SVM 随笔
前言当下机器学习比较重要 3 中算法，个人都目前为止认为比较重要机器学习算法分别是，深度学习、SVM 和决策树。...