美文网首页
决策树算法

决策树算法

作者: 阿ashang | 来源:发表于2019-04-03 08:16 被阅读0次

一、通俗理解熵和基尼不纯度

1.信息熵

\quad熵度量事物的不确定性,越不确定的事物,它的熵就越大。随机变量Y的熵的表达式如下:
H(Y)= - \sum_{j=1}^m p_j\ log\ p_j
其中m代表了ym种可能的离散取值;p_j表示随机变量Y的概率分布,即p_j=P(Y=y_j),j=1,2...m

2.联合熵

由单个变量信息熵可推广至多个变量的联合熵,即:
H(X,Y)=\sum_{i=1}^n \sum_{j=1}^m p_{ij}\ log\ p_{ij}
其中p_{ij}表示随机变量(X,Y)的联合概率分布,即p_{ij}=P(X=x_i,Y=y_i) ,i=1,2...n,\ j=1,2...m.

3.条件熵

\quad条件熵定义为:给定随机变量X的条件下,随机变量Y的条件概率分布的熵对随机变量X的数学期望。
则根据定义可推导条件熵公式:
\quad\ H(Y|X)=\sum_{i=1}^n P(X=x_i) H(Y|X=x_i)

=- \sum_{i=1}^n P(X=x_i) \sum_{j=1}^m P(Y=y_j|X=x_i)logP(Y=y_j|X=x_i)

=- \sum_{i=1}^n \sum_{j=1}^m P(X=x_i,Y=y_j)logP(Y=y_j|X=x_i)

条件熵表示在已知随机变量X的情况下,随机变量Y的不确定性。

4.信息增益\互信息

信息增益 = 信息熵 - 条件熵,即
I(X)=H(Y)-H(Y|X)
表示在已知随机变量X的情况下,随机变量Y的不确定性减少的程度。ID3算法使用信息增益选择最优特征。

5.基尼不纯度

\quad 基尼不纯度:指随机抽取两个样本,其类别标记不一致的概率。
\quad 假设有k个类别,选中子集为第k个类别的概率为p_k,则基尼系数表达式为:
Gini(D)=\sum_{k=1}^K p_k(1-p_k)=1 - \sum_{k=1}^K p_k^2
假设有k个类别,随机抽取一个样本,类别j出现的概率为p_j;再随机抽取第二个样本,类别j出现的概率为p_j^2,假设k个类别出现的概率是相互独立的,则随机抽取两个样本出现类别一致的概率为\sum_{k=1}^K p_k^2,则类别不一致的概率为1 - \sum_{k=1}^K p_k^2。考虑极端情况p_k=1,基尼不纯度为0,数据集不确定性为0(即固定的属于某一类别)。
CART中使用Gini不纯度做特征选择,与信息增益的理念类似,在已知某特征A分布的情况下,基尼不纯度减小的程度作为最优特征划分的标准。

二、决策树分类算法

1.ID3

决策树的生成需要考虑特征选择方法及停止条件。
停止条件为:
\quad (1)子集中同属同一类标记y,例如所有样本同属0类或1类,不纯度为0,无需继续向下划分;
\quad (2)自顶而下已使用完所有特征;
\quad (3)小于给定信息增益划分的阈值。

ID3使用信息增益进行特征选择。算法过程为:
\quad 输入:数据集D=\{ (x^{(1)},y_1),(x^{(2)} , y_2),...(x^{(n)} , y_n) \},其中x^{(i)}=(x_1^{(i)} , x_2^{(i)} , ...x_d^{(i)})。数据集D|D|个样本,d个离散特征,特征集合为A=\{A_1,A_2...A_d\}
\quad 输出:决策树T

生成决策树过程:

(1)计算信息增益:
\quad首先计算数据集D整体的信息熵H(D),假设样本标记共有K个类别,|D_k|表示标记为k的样本个数,|D|表示总样本量;则
H(D)=-\sum_{k=1}^K P(Y=k)logP(Y=k)=-\sum_{k=1}^K \frac{|D_k|}{|D|} log\frac{|D_k|}{|D|}

\quad接下来计算条件熵,在选择特征A_j(特征集合A中任意一个特征)的情况下,计算数据集的信息熵,根据定义可得:
\quad\ H(D|A_j)
=-\sum_a P(A_j=a) \sum_{k=1}^K P(Y=k|A_j=a)logP(Y=k|A_j=a)
=-\sum_a \frac{|D_a|}{|D|} \sum_{k=1}^K \frac{|D_{ak}|}{|D_a|} log\frac{|D_{ak}|}{|D_a|}
其中a表示属性A_j可能的取值,|D_a|表示取值为a的样本个数,|D_{ak}|表示特征A_j取值为a且标记为k的样本个数。
\quad则信息增益为:I(A_j)=H(D)-H(D|A_j)

(2)分别计算特征集合A中各个特征对数据集D的信息增益I(A_j),选择其中信息增益最大的特征作为当前节点划分的特征。

(3)判断是否满足停止条件,若满足输出树T;不满足继续(1)(2)步向下划分。

缺点

a)在分裂特征的选择中,会偏向取值个数较多的特征;
b)只考虑了分类特征;
c)没有考虑缺失值的情况。

2.C4.5

针对ID3算法的缺点,提出了C4.5算法。
1.在选取分裂特征时采用信息增益比,即信息增益和特征熵的比值:
2.对连续特征做了离散化处理:
\quad将连续特征对应的n个样本取值按照从小到大的顺序排列,取相邻两个值的均值作为一个切分点,共有n-1个切分点,分别计算以这n-1个点作为切分点进行离散化后的特征的信息增益,取信息增益最大的点为最佳切分点。
3.对缺失值的情况分别做了处理:
(1)在选择划分特征时,部分样本在某些特征上有缺失:
\quad即在计算各个特征的信息增益时,部分样本在特征上没有取值,无法确定对应的样本量。采取的方法是在计算有缺失样本的特征的信息增益时,将数据依据在该特征上是否缺失分为两部分,对每个样本赋予权重,使用无缺失的部分计算加权信息增益,并乘以系数,系数为无特征缺失样本加权后占加权总样本的比例。
(2)已经选定了划分特征,根据特征进行分枝时,样本在该特征取值上有缺失:
\quad将缺失特征取值的样本同时划分入所有的叶子节点,同时按照叶子节点的样本占比赋予权重。

3.CART分类树

CART算法在C4.5的基础上进行了优化:
1.在划分特征的选择上采用Gini系数:
数据集DGini系数(度量数据集D的不纯度):
Gini(D)=\sum_{k=1}^K \frac{|D_k|}{|D|} (1-\frac{|D_k|}{|D|})

在给定特征A的条件下,DGini系数为:

Gini(D,A)=\frac{|D_1|}{|D|}Gini(D_1)+\frac{|D_2|}{|D|}Gini(D_2)

2.在连续特征的处理上使用Gini系数选择最优划分点
3.CART分类树都是二叉树,特征可以重复使用
4.剪枝算法(避免过拟合):
任意一棵树T_t,损失函数为:
C_\alpha(T_t)=C(T_t)+\alpha |T_t|

\quad等式右边第二部分|T_t|表示叶子节点的个数,代表模型复杂度,节点越多,生成的树越庞大,模型越复杂。\alpha为超参数,平衡成本和复杂度,\alpha越大,节点数越少。
\quad仅保留根节点时,C_\alpha(T)=C(T)+\alpha;判断在子节点t处是否需要剪枝,首先看剪枝前的损失函数为C_\alpha(T_t)=C(T_t)+\alpha |T_t|;当C_\alpha (T_t)>C_\alpha(T),剪枝;当C_\alpha (T_t)<C_\alpha(T),保留该分枝。随着\alpha的增大,当C_\alpha (T_t)=C_\alpha(T)时,达到临界值,此时\alpha=\frac{C(T)-C(T_t)}{|T_t| -1},树T有更小的损失函数且子节点个数更少,此时可对T_t进行剪枝,变为叶子节点T

由此可以计算出每个子节点是否剪枝的\alpha值,之后使用交叉验证选择最优的\alpha,输出剪枝后的树T

三、决策树的优缺点

优点:

1.简单易于理解,可解释性强;
2.基本不需要预处理,每次进行划分时只选择一个特征,不需要进行归一化;
3.CART输入特征可以是离散的或连续的,可自动处理缺失值;
4.对于异常点不敏感,容忍度高。

缺点:

1.每次只选择一个特征进行分裂,没有考虑到特征之间的相关性;
2.容易过拟合,导致泛化能力不强;
3.样本发生一点变化,就会导致树结构发生强烈改变。

四、回归树原理

ID3和C4.5都只能用于分类,CART既可用于分类,又可用于回归。
回归问题使用均方误差度量损失,回归树在分裂过程中需要确定分裂特征及特征值点。其过程为:
假设对于任意特征A,由划分点s将数据集划分为D_1、D_2两部分,划分后的损失函数为:
\sum_{x_i \in D_1} (y_i-c_1)^2+\sum_{x_i \in D_2} (y_i-c_2)^2
其中c_1、c_2分别对应数据集D_1、D_2的样本均值。
求解损失函数最小对应的特征A及划分点s
回归树生成后,采用最终叶子节点的均值或中位数做预测输出。

五、决策树防止过拟合方法

1.剪枝;
2.集成方法,如随机森林;
其次,结合停止条件来看:
2.控制满足分裂条件的不纯度的阈值(min_impurity_decrease);
3.控制叶子节点个数(max_leaf_nodes);
4.控制继续下一次划分时叶子节点的最小样本数(min_samples_split)。

六、决策树sklearn参数

from sklearn.tree import DecisionTreeClassifier

DT参数.png

参考
https://www.cnblogs.com/pinard/p/6050306.html
https://www.cnblogs.com/pinard/p/6053344.html
https://mp.weixin.qq.com/s/v7-hhDVJUQKgNECcgab1qg
https://www.zhihu.com/question/34075616

相关文章

  • 决策树算法总结

    目录 一、决策树算法思想 二、决策树学习本质 三、总结 一、决策树(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 决策树算法概...

  • 数据分析方法-决策树

    大家好,这篇文章我们探讨下,决策树算法的相关的知识,决策树是一种分类算法,现在也可以应用与回归,决策树算法的实现有...

网友评论

      本文标题:决策树算法

      本文链接:https://www.haomeiwen.com/subject/vvcibqtx.html