主要解决三个问题:
- 选择哪个属性作为根节点;
- 选择哪些属性作为子节点;
- 什么时候停止并得到目标状态,即叶节点。
剪枝
给决策树瘦身,防止“过拟合”和“欠拟合”发生。
剪枝可以分为“预剪枝”(Pre-Pruning)和“后剪枝”(Post-Pruning)。
- 预剪枝:预剪枝是在决策树构造时就进行剪枝。方法是在构造的过程中对节点进行评估,如果对某个节点进行划分,在验证集中不能带来准确性的提升,那么对这个节点进行划分就没有意义,这时就会把当前节点作为叶节点,不对其进行划分。
- 后剪枝:后剪枝就是在生成决策树之后再进行剪枝,通常会从决策树的叶节点开始,逐层向上对每个节点进行评估。如果剪掉这个节点子树,与保留该节点子树在分类准确性上差别不大,或者剪掉该节点子树,能在验证集中带来准确性的提升,那么就可以把该节点子树进行剪枝。方法是:用这个节点子树的叶子节点来替代该节点,类标记为这个节点子树中最频繁的那个类。
指标
- 纯度:可以把决策树的构造过程理解成为寻找纯净划分的过程。数学上,我们可以用纯度来表示,纯度换一种方式来解释就是让目标变量的分歧最小。
- 信息熵:表示了信息的不确定度,随机离散事件出现的概率存在着不确定性,为了衡量这种信息的不确定性,提出了信息熵的概念。
- 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(criterion='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 回归树。
发表评论