Press "Enter" to skip to content

数据分析:决策树原理

本站内容均来自兴趣收集,如不慎侵害的您的相关权益,请留言告知,我们将尽快删除.谢谢.

主要解决三个问题:

 

 

    1. 选择哪个属性作为根节点;

 

    1. 选择哪些属性作为子节点;

 

    1. 什幺时候停止并得到目标状态,即叶节点。

 

 

剪枝

 

给决策树瘦身,防止“过拟合”和“欠拟合”发生。

 

剪枝可以分为“预剪枝”(Pre-Pruning)和“后剪枝”(Post-Pruning)。

预剪枝:预剪枝是在决策树构造时就进行剪枝。方法是在构造的过程中对节点进行评估,如果对某个节点进行划分,在验证集中不能带来准确性的提升,那幺对这个节点进行划分就没有意义,这时就会把当前节点作为叶节点,不对其进行划分。
后剪枝:后剪枝就是在生成决策树之后再进行剪枝,通常会从决策树的叶节点开始,逐层向上对每个节点进行评估。如果剪掉这个节点子树,与保留该节点子树在分类准确性上差别不大,或者剪掉该节点子树,能在验证集中带来准确性的提升,那幺就可以把该节点子树进行剪枝。方法是:用这个节点子树的叶子节点来替代该节点,类标记为这个节点子树中最频繁的那个类。

指标

 

 

    1. 纯度:可以把决策树的构造过程理解成为寻找纯净划分的过程。数学上,我们可以用纯度来表示,纯度换一种方式来解释就是让目标变量的分歧最小。

 

    1. 信息熵:表示了信息的不确定度,随机离散事件出现的概率存在着不确定性,为了衡量这种信息的不确定性,提出了信息熵的概念。

 

 

    1. p(i|t) 代表了节点 t 为分类 i 的概率,c代表结果有几种可能性。 信息熵越大,纯度越低。当集合中的所有样本均匀混合时,信息熵最大,纯度最低。

 

 

我们在构造决策树的时候,会基于纯度来构建。而经典的 “不纯度”的指标有三种,分别是 信息增益(ID3 算法)、信息增益率(C4.5 算法)以及基尼指数(Cart 算法) 。

 

1. ID3算法(信息增益):划分可以带来纯度的提高,信息熵下降

 

计算每个子节点的归一化信息熵,即按照 每个子节点在父节点中出现的概率(下图中的 \frac{|D_i|}{|D|} ) ,来计算这些子节点的信息熵,然后计算出该属性的信息增益。

D:父亲节点
D_i :子节点
Gain(D,a) : a 作为D(父亲)的属性选择

所以 ID3 有一个缺陷就是,有 些属性可能对分类任务没有太大作用 ,但是他们仍然可能会被选为最优属性。这种缺陷不是每次都会发生,只是存在一定的概率。在大部分情况下,ID3 都能生成不错的决策树分类。针对可能发生的缺陷,后人提出了新的算法进行改进。

 

2. C4.5算法(ID3改进):

使用信息增益率来代替信息增益

信息增益率=信息增益 / 属性熵

属性熵就是该属性自身的熵,如下例子中的温度属性熵如下计算:

 

采用悲观剪枝
离散化处理连续属性:C4.5 可以处理连续属性的情况,对连续的属性进行离散化的处理。比如打篮球存在的“湿度”属性,不按照“高、中”划分,而是按照湿度值进行计算,那幺湿度取什幺值都有可能。该怎幺选择这个阈值呢,C4.5 选择具有最高信息增益的划分所对应的阈值。
处理缺失值

ID3 算法的优点是方法简单,缺点是对噪声敏感。训练数据如果有少量错误,可能会产生决策树分类错误。C4.5 在 ID3 的基础上,用信息增益率代替了信息增益,解决了噪声敏感的问题,并且可以对构造树进行剪枝、处理连续数值以及数值缺失等情况,但是由于 C4.5 需要对数据集进行多次扫描,算法效率相对较低。

 

使用graphviz绘制决策树

 

 

from sklearn import tree
import sys
import os
import graphviz
import numpy as np
data = np.array([[1,1], [1,0], [0,1], [0,0]])
target = np.array([1,1,0,0]) # 数据标注
clf = tree.DecisionTreeClassifier(='entropy') # 创建决策树分类模型
clf = clf.fit(data, target) # 拟合数据
dot_data = tree.export_graphviz(clf, filled=True, out_file=None)
graph = graphviz.Source(dot_data)
graph

 

结果如下:

 

entropy代表信息增量
samples代表当前分类下的样本数目
value=[2, 0]是分类概率(是好苹果,不是好苹果)

CART决策树

基尼系数: 用来衡量一个国家收入差距的常用指标。当基尼系数大于 0.4 的时候,说明财富差异悬殊。基尼系数在 0.2-0.4 之间说明分配合理,财富差距不大。
基尼系数本身反应了样本的不确定度。 当基尼系数越小的时候,说明样本之间的差异性小 ,不确定程度低。 分类的过程本身是一个不确定度降低的过程,即纯度的提升过程。 所以 CART 算法在构造分类树的时候,会选择基尼系数最小的属性作为属性的划分。

公式如下:

 

 

P(C_k|t) 表示节点t属于类型 C_k 的概率,节点 t 的基尼系数为 1 减去各类别 C_k 概率平方和。

 

在 CART 算法中,基于基尼系数对特征属性进行二元分裂,假设属性 A 将节点 D 划分成了 D1 和 D2,如下图所示:

 

 

节点 D 的基尼系数等于子节点 D1 和 D2 的 归一化基尼系数之和 ,用公式表示为:

 

 

所以在属性 A 的划分下,节点 D 的基尼系数为:

 

 

节点 D 被属性 A 划分后的基尼系数越大,样本集合的不确定性越大,也就是不纯度越高。

 

如何使用CART算法来创建分类树

 

直接使用DecisionTreeClassifier这个类,创建这个类的时候,默认情况下 criterion 这个参数等于 gini,也就是按照基尼系数来选择属性划分,即默认采用的是 CART 分类树。

 

from sklearn.model_selection import train_test_split
from sklearn.metrics import accuracy_score
from sklearn.tree import DecisionTreeClassifier
from sklearn.datasets import load_iris
# 准备数据集
iris=load_iris()
# 获取特征集和分类标识
features=iris.data
labels=iris.target
# 随机抽取33%数据作为测试集,其余作为训练集
train_features, test_features, train_labels, test_labels=train_test_split(features, labels, test_size=0.33, random_state=0)
# 创建CART分类树
clf = DecisionTreeClassifier(criterion='gini')
# 拟合构造CART分类树
clf = clf.fit(train_features, train_labels)
# 用CART分类树做预测
test_predict = clf.predict(test_features)
# 预测结果与测试集结果作比对
score = accuracy_score(test_labels, test_predict)
score

 

CART 回归树的工作流程

 

CART 回归树划分数据集的过程和分类树的过程是一样的,只是回归树得到的预测结果是连续值,而且评判“不纯度”的指标不同。在 CART 分类树中采用的是基尼系数作为标准,那幺在 CART 回归树中,如何评价“不纯度”呢?实际上我们要根据样本的混乱程度,也就是样本的离散程度来评价“不纯度”。

 

样本的离散程度具体的计算方式是,先计算所有样本的均值,然后计算每个样本值到均值的差值。我们假设 x 为样本的个体,均值为 u。为了统计样本的离散程度,我们可以取差值的绝对值,或者方差。

其中差值的绝对值为样本值减去样本均值的绝对值: |X-\mu|
方差为每个样本值减去样本均值的平方和除以样本个数: s=\frac{\sum \left ( x-\mu \right )^2}{n}

所以这两种节点划分的标准,分别对应着两种目标函数最优化的标准,即用 最小绝对偏差(LAD) ,或者使用 最小二乘偏差(LSD) 。这两种方式都可以让我们找到节点划分的方法,通常使用最小二乘偏差的情况更常见一些。

 

# 预测波士顿房价
from sklearn.metrics import mean_squared_error
from sklearn.model_selection import train_test_split
from sklearn.datasets import load_boston
from sklearn.metrics import r2_score,mean_absolute_error,mean_squared_error
from sklearn.tree import DecisionTreeRegressor
boston = load_boston()
print(boston.feature_names)
# 获取特征集和房价
features=boston.data
prices=boston.target
# 随机抽取33%的数据作为测试集
train_features, test_features, train_prices, test_prices=train_test_split(features, prices, test_size=0.33)
# 创建回归树
dtr=DecisionTreeRegressor()
dtr.fit(train_features, train_prices)
predict_price=dtr.predict(test_features)
print('回归树二乘偏差均值:', mean_squared_error(test_prices, predict_price))
print('回归树绝对值偏差均值:', mean_absolute_error(test_prices, predict_price))

 

['CRIM' 'ZN' 'INDUS' 'CHAS' 'NOX' 'RM' 'AGE' 'DIS' 'RAD' 'TAX' 'PTRATIO'
 'B' 'LSTAT']
回归树二乘偏差均值: 20.5040119760479
回归树绝对值偏差均值: 2.9850299401197606

 

输出图片:

 

from IPython.display import Image  
import pydotplus
graph=pydotplus.graph_from_dot_data(dot_data)
Image(graph.create_png())

CART决策树剪枝

 

CART 决策树的剪枝主要采用的是 CCP 方法, 它是一种后剪枝的方法,英文全称叫做 cost-complexity prune。

 

这种剪枝方式用到一个指标叫做 节点的表面误差率增益值 ,以此作为剪枝前后误差的定义。

 

 

其中 Tt 代表以 t 为根节点的子树, C(T_t) 表示节点 t 的子树没被裁剪时子树 Tt 的误差, C(t) 表示节点 t 的子树被剪枝后节点 t 的误差, |T_t| 代子树 Tt 的叶子数,剪枝后,T 的叶子数减少了 |T_t|-1 。

 

所以节点的表面误差率增益值等于节点 t 的子树被剪枝后的误差变化除以剪掉的叶子数量。

 

因为我们希望剪枝前后误差最小,所以我们要寻找的就是最小α值对应的节点,把它剪掉。这时候生成了第一个子树。重复上面的过程,继续剪枝,直到最后只剩下根节点,即为最后一个子树。

 

得到了剪枝后的子树集合后,我们需要用验证集对所有子树的误差计算一遍。可以通过计算每个子树的基尼指数或者平方误差,取误差最小的那个树,得到我们想要的结果。

 

总结

 

CART 决策树,它是一棵决策二叉树,既可以做分类树,也可以做回归树。你需要记住的是,作为分类树,CART 采用基尼系数作为节点划分的依据,得到的是离散的结果,也就是分类结果;作为回归树,CART 可以采用最小绝对偏差(LAD),或者最小二乘偏差(LSD)作为节点划分的依据,得到的是连续值,即回归预测结果。

ID3 算法,基于信息增益做判断;
C4.5 算法,基于信息增益率做判断;
CART 算法,分类树是基于基尼系数做判断。回归树是基于偏差做判断。
工具:sklearn 中的 DecisionTreeClassifier 创建 CART 分类树,通过 DecisionTreeRegressor 创建 CART 回归树。

Be First to Comment

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注