机器学习算法——决策树5（CART）

作者: 皮皮大 | 来源:发表于2019-08-24 10:07 被阅读6次

机器学习算法——决策树5（CART）
[python][机器学习]算法实现代码分享
2019-04-26
决策树
第5章决策树
CART树
统计学习方法5.6 - 7.2笔记
05 决策树 - 生成算法 ID3、C4.5、CART
sklearn.tree.DecisionTreeClassif
[机器学习算法]决策树引论和CART算法

三种算法比较

ID3：采用信息增益作为选择特征的标准，越大越好
C4.5：采用信息增益率作为选择特征的标准，越大越好
CART：

回归：平方误差函数，越小越好
分类：基尼系数，越小越好

CART算法

CART算法由特征选择、树的生成及剪枝组成，可以用于回归也可以用于分类。CART假设决策树是二叉树，内部节点特征的取值为"是"和"否"，左边取值为"是"的分支，右边为"否"的分支，进行递归地二分每个特征，算法分为两步：

决策树生成：基于训练数据集生成决策树，生成的决策树尽量大；
决策树剪枝：用验证数据集对已生成的树进行剪枝，并且选择最优树，用最小化损失函数作为剪枝的标准

决策树的生成就是递归地创建二叉树的过程。最小化准则：

回归：平方误差最小化
分类：基尼系数最小化

回归树

假设输入和输出变量分别是X和Y，并且Y是连续变量，在数据集 $D=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\}$ 上，如果将输入空间划分为M个单元 $R_1,R_2,...,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$ 用来表示回归树对于训练数据的预测误差

分类树

分类数用基尼系数选择最优特征，同时决定该特征的最优二值分切分点。分类问题中，假设有K个类，样本点属于第k类的概率为 $p_k$ ，概率分布的基尼质数定义为：
$\begin{align} Gini(p) & =\sum_{k=1}^{K}p_k(1-p_k) \\ & =\sum_{k=1}^{K}p_k - \sum_{k=1}^{K}p_k^2 \\ & = 1- \sum_{k=1}^{K}p_k^2 \end{align}$
对于二分类问题，若属于第一个类的概率为p，概率分布的基尼系数为： $Gini(D)=p(1-p)+(1-p)(1-(1-p))=2p(1-p)$ 对给定的样本集合D，基尼系数为 $Gini(D)=1-\sum_{k=1}^{K}(\frac {|C_k|} {|D|})^2$ 其中K是类的个数， $C_k$ 是 $D$ 中属于第 $k$ 类的样本子集。

基尼系数表示样本集合的不确定性，基尼系数越大，样本集合的不确定性就越大

`CART`算法

输入：训练数据集D，停止计算的条件
输出：CART决策树

具体构建决策树的步骤为：

设节点的数据集为D，计算现有特征对该数据集的基尼系数
在所有的特征A以及它们可能的切分点中，选择基尼系数最小的特征及对应的切分点作为最佳选择。
从现有节点中生成两个子节点，将训练数据集分配到两个子节点中去
递归地调用上面两个步骤，直到满足停止条件
生成CART树

停止条件：节点中样本数小于阈值，或者样本集的基尼系数小于阈值，或者没有更多特征

机器学习算法——决策树5（CART）
三种算法比较 ID3：采用信息增益作为选择特征的标准，越大越好C4.5：采用信息增益率作为选择特征的标准，越大越好...
[python][机器学习]算法实现代码分享
在自学机器学习的过程中，自己尝试实现了许多算法，包括线性回归、逻辑回归、决策树c4.5/cart、随机森林、Ada...
2019-04-26
决策树离散型数据ID3 连续型数据C4.5 分类与回归树算法(CART) CART算法就是将决策树中用于判断特征...
决策树
决策树决策树模型与学习特征选择决策树的生成决策树的剪枝 CART 算法决策树模型呈树形结构，在分类问题中...
第5章决策树
内容一、决策树内容简介二、决策树的模型与学习三、特征选择四、决策树生成五、决策树剪枝六、CART算法 ...
CART树
CART（classification and regression tree）算法是分类回归树算法，它是决策树的...
统计学习方法5.6 - 7.2笔记
5.6 决策树 -- CART算法 CART是二叉结构树。多叉可以转换成二叉，表示是和非在CART算法中分类树是...
05 决策树 - 生成算法 ID3、C4.5、CART
ID3 提出了初步的决策树算法；C4.5 提出了完整的决策树算法；CART (Classification And...
sklearn.tree.DecisionTreeClassif
sklearn.tree.DecisionTreeClassifier()函数用于构建决策树，默认使用CART算法...
[机器学习算法]决策树引论和CART算法
决策树综述 1.决策树的工作原理决策树decision tree分类法是一种简单但广泛使用的分类技术。以是否贷款...