【算法】决策树

作者: 猪猪奋斗记 | 来源:发表于2021-03-25 10:54 被阅读0次

决策树算法总结
100天搞定机器学习|Day23-25 决策树及Python实现
决策树Decision Tree
Python学习——决策树中纯度算法的实现
决策树算法
Machine Learning in Action:Decis
通俗地说决策树算法（一）基础概念介绍
ID3和C4.5决策树算法总结及其ID3Python实现
机器学习6-决策树
数据分析方法-决策树

基本流程

决策树（decision tree）是一类常见的机器学习方法。决策树是一个预测模型；他代表的是对象属性与对象值之间的一种映射关系。树中每个节点表示某个对象，而每个分叉路径则代表的某个可能的属性值，而每个叶结点则对应从根节点到该叶节点所经历的路径所表示的对象的值。决策树仅有单一输出，若欲有复数输出，可以建立独立的决策树以处理不同输出。数据挖掘中决策树是一种经常要用到的技术，可以用于分析数据，同样也可以用来作预测。

决策树

决策树的建立

输入: 训练集 $D = \{(x_1,y_1),(x_2,y_2),...,(x_m,y_m)\}$ ;
属性集: $A=\{a_1,a_2,...,a_d\} a_*$
伪代码：

函数 TreeGenerate(D,A)
生成节点node:
if D 中的样本全属于同一类别 C then
    将node标记为C类叶子节点；return
end if
if A = ϕ OR D 中样本在 A 上取值相同 then
    将 node 标记为叶节点，其类别标记为 D 中样本数最多的类；return
end if
从A中选则最优划分属性a∗;
for a* 的每一个值a*(v) do
    为node生成一个分支；令Dv表示D中在a*上取值为a*(v)的样本子集；
    if Dv 为空 then
        将分支节点标记为叶节点，其类别标记为D中样本最多的类；return
    else
        以Tree(Dv,A\{a*})为分支节点
    end if
end for

输出：以node为根的一颗决策数

决策数的生成是一个递归的过程，在决策树基本算法中有三种情况会导致递归返回：

当前节点包含的样本种类属于同一类别，无需划分
当前样本属性集为空，或者所有样本在所有属性上的取值相同，无法划分
当前节点包含的样本集合为空，不能划分

划分选择

决策树算法的关键在于如歌选择最优划分属性，随着划分的不断进行，我们希望决策树的分支节点所包含的样本尽可能的属于同一类别。

信息熵

熵的概念最早起源于物理学，用于度量一个热力学系统的无序程度。在信息论里面，熵是对不确定性的测量。但是在信息世界，熵越高，则能传输越多的信息，熵越低，则意味着传输的信息越少。
信息熵(information entropy)是度量样本集合纯度最常用的一种指标，假定当前样本集合 $D$ 中第 $k$ 类样本所占的比例为 $p_k(k=1,2,...,|y|)$ ,则 $D$ 的信息熵定义为：
$Ent(D)= - \Sigma_{k=1}^{|y|}p_k log_2p_k$
$Ent(D)$ 的值越小，则 $D$ 的纯度越高

信息增益与ID3算法

假定离散属性 $a$ 有 $V$ 个可能的取值 $\{a^1,a^2,...,a^V\}$ ，若使用 $a$ 来对样本集 $D$ 进行划分，则会产生 $V$ 个分支节点，之中第 $v$ 个节点包含了 $D$ 中所有在属性 $a$ 上取值为 $a^v$ 的样本，记为 $D^v$ ，我们可以计算出 $D^v$ 的信息熵，在考虑到不同的分支节点包含的样本数的不同，给分支节点赋予权重 $|D^v|/|D|$ ,
信息增益：
$Gain(D,a)=Ent(D)-\Sigma_1^V\frac{|D^v|}{|D|}Ent(D^v)$
$\frac{|D^v|}{|D|}Ent(D^v)$ 可记为 $Ent(a^v|a)$ 表示特征属性 $a$ 的条件下样本的条件熵,信息增益越大，则以为则使用属性 $a$ 来进行划分所获得的纯度越高，因此可以用来作为属性划分的依据
$a_*=argmin Gain(D,a) ,a \in A$
这也是ID3(Iterative Dichotomiser 3)算法的原理。
决策树ID3算法请参考：传送门

信息增益率与C4.5算法

C4.5决策树算法不直接使用信息增益，而是使用信息增益率来选择最优划分属性。
$Gain_ratio(D,a)=\frac{Gain(D,a)}{IV(a)}$
其中
$IV(a)=-\Sigma_{v=1}^V\frac{|D^v|}{|D|}log_2\frac{|D^v|}{|D|}$
$IV(a)$ 称为属性a的固有值，属性a的可能取值数目越多，则 $IV(a)$ 的值通常会越大。增益率准则对取值数目较少的属性有所偏好。
决策树C4.5算法：传送门

基尼指数与分类回归树

CART树(Classification and Regression Tree)使用基尼指数来选择属性的划分，通过基尼值来度量数据集的纯度
基尼值：
$Gini(D)=\Sigma_{k=1}^{|y|}\Sigma_{k^{'}\neq k}p_kp_k{'}=1-\Sigma_{k=1}^{|y|}p_k^2$
$Gini(D)$ 反映了从数据集 $D$ 中取出两个样本，不为同一种类的概率，因此 $Gini(D)$ 越小，数据集的纯度越高。
基尼指数：
$Gini_index(D,a)=\Sigma_{v=1}^V\frac{|D^v|}{|D|}Gini(D^v)$
于是我们在候选属性集合 $A$ 中选择使那个划分后基尼指数最小的那个属性作为最优划分属性。
CRAT算法：传送门

过拟合处理

在决策树学习中，为了尽可能正确分类训练样本，结点划分过程将不断重复，有时会造成决策树分支过多，导致过拟合，因此可以通过主动去掉一些分支来降低过拟合的风险。
剪枝的基本策略有：预剪枝和后剪枝

预剪枝

预剪枝是在决策树生成的过程中，对每个结点在划分前先进行预估，若当前结点的划分不能使决策树泛化性能提升，则停止划分并将当前结点标记为叶节点。

后剪枝

后剪枝是先从训练集中生成一颗完整的决策树，然后自底向上的对非叶子结点进行考察，若将改结点对应的子树替换为叶子结点能提高泛化能力，则进行替换。

连续值缺失值处理

连续值处理

由于连续属性的可能取值不再有限，因此不能直接根据连续属性的可能取值进行划分。我们可以使用离散化技术对其进行处理。
二分法：
给定样本集 $D$ ，和连续属性 $a$ ， $a$ 在 $D$ 上出现了n个不同的取值，
将其排序 $\{a^1,a^2,...,a^n\}$ ，然后基于划分点 $t$ 将样本划分为 $D_t^-$ 和 $D_t^+$ ， $D_t^-$ 包括在属性 $a$ 上取值小于 $t$ 的样本， $D_t^+$ 反之。通常将划分点设为该属性在训练集中出现额不大于中位点的最大值从而是的最终决策树使用的划分点都在训练集中出现过。
eg:
$T_a=\{\frac{a^i+a^{i+1}}{2}|1\le i\le n-1\}$
$Gain(D,a)=max\{Gain(D,a,t)|t \in T_a\}$
$Gain(D,a)=max\{Ent(D) - \Sigma_{\lambda\in \{+,-\}} \frac{|D_t^{\lambda}|}{|D|}Ent(D_t^{\lambda})|t \in T_a\}$
$Gain(D,a,t)$ 是样本 $D$ 基于划分点 $t$ 的信息增益，选择使得 $Gain(D,a,t)$ 最大化的划分点。

缺失值处理

现实任务中常常会遇到不完整的样本，也就是样本中的某些属性值缺失的情况，最简单的方法是直接去除缺失的数据，但是这是对数据信息的极大浪费，我们可以考虑下利用有缺失属性值的样本来进行学习。
需解决的问题：

在属性值缺失的情况下进行划分属性的选择
给定划分属性，若样本在该属性上的值缺失，如何进行划分

给定训练集 $D$ ,属性集 $a$ ,令 $\overline{D}$ 表示 $D$ 中在属性 $a$ 上没有缺失值的样本子集

对于问题一，根据 $\overline{D}$ 来判断属性 $a$ 的优劣，属性 $a$ 的取值 $\{a^1,...,a^V\}$ ，令 $\overline{D}^v$ 表示 $\overline{D}$ 在 $a$ 上取值为 $v$ 的样本子集， $\overline{D}_k$ 表示 $\overline{D}$ 中属于第 $k，(k=1,2,3...,|y|)$ 类的样本子集
$\overline{D}=\cup_{k=1}^{|y|}\overline{D}_k$ , $\overline{D}=\cup_{v=1}^{V}\overline{D}^v$ ,假定为每一个样本赋予一个权重 $w_x$
设

$\rho ={ \Sigma_{x \in \overline{D} } w_x } / { \Sigma_{x \in D } w_x }$
$\overline{p}_k ={ \Sigma_{x \in \overline{D}_k } w_x } / { \Sigma_{x \in D } w_x }$
$\overline{r}_v ={ \Sigma_{x \in \overline{D}^v } w_x } / { \Sigma_{x \in D } w_x }$

$\rho$ 表示属性 $a$ 上无缺样本所占比例， $\overline{p}_k$ 表示无缺样本中第 $k$ 类所占的比例, $\overline{r}_v$ 表示无缺样本中属性 $a$ 上取值为 $a^v$ 的所占的比例。
推广到信息增益公式上：

$Gain(D,a)=\rho * Gain(\overline{D},a)$
$Gain(D,a)=\rho *(Ent(\overline{D})-\Sigma_{v=1}^V \overline{r}_v Ent(\overline{D}^v))$
其中 $Ent(\overline{D}) = -\Sigma_{k=1}^{|y|} \overline{p}_k log_2\overline{p}_k$

对于问题二，样本 $x$ 在属性 $a$ 上的取值缺失，则将 $x$ 划分到所有额子结点中，将权值变为 $\overline{r}_v * w_x$ ,意思i将同一个样本以不同的概率划入到同的子结点中。

决策树算法总结
目录一、决策树算法思想二、决策树学习本质三、总结一、决策树（decision tree）算法思想：决策树...
100天搞定机器学习|Day23-25 决策树及Python实现
算法部分不再细讲，之前发过很多：【算法系列】决策树决策树（Decision Tree）ID3算法决策树（De...
决策树Decision Tree
决策树是一种解决分类问题的算法。常用的决策树算法有： ID3 算法 ID3 是最早提出的决策树算法，他...
Python学习——决策树中纯度算法的实现
决策树决策树算法是机器学习中的一个基础算法，该算法有着诸多的优点。在python中实现决策树，现阶段都已经集成中...
决策树算法
决策树决策树也是经常使用的数据挖掘算法，其不用了解机器学习的知识，就能搞明白决策树是如何工作的。决策树算法能够...
Machine Learning in Action:Decis
概述决策树这个算法比较接地气，就算你根本不懂机器学习算法也可以很好的理解决策树，决策树之前的算法就已经解释过了。...
通俗地说决策树算法（一）基础概念介绍
决策树算是比较常见的数据挖掘算法了，最近也想写点算法的东西，就先写个决策树吧。一. 什么是决策树决策树是什么，...
ID3和C4.5决策树算法总结及其ID3Python实现
ID3和C4.5决策树算法总结及其ID3Python实现 1.决策树的算法流程决策树的算法流程主要是：1.如果当...
机器学习6-决策树
一. 决策树概述 1.1 什么是决策树决策树输入: 测试集决策树输出: 分类规则(决策树) 1.2 决策树算法概...
数据分析方法-决策树
大家好，这篇文章我们探讨下，决策树算法的相关的知识，决策树是一种分类算法，现在也可以应用与回归，决策树算法的实现有...