整理自《极客时间——数据分析》课程
image.png
一.决策树的工作原理
在做决策树时，需要经历两个阶段：构造和剪枝。
构造
构造的过程就是选择什么属性作为节点的过程。注意，叶节点是决策结果。
剪枝
剪枝就是给决策树瘦身，这一步想实现的目标就是，不需要太多的判断，同样可以得到不错的结果。之所以这么做，是为了防止“过拟合”（Overfitting）现象的发生。
造成过拟合的原因之一就是因为训练集中样本量较小。若选择的属性太多，会完美的把训练集中的样本分类，但是其在真实场景中不一定能够正常工作，泛化能力较差。
剪枝分为预剪枝和后剪枝。
预剪枝是在决策树构造时就进行剪枝。方法是在构造的过程中对节点进行评估，如果对某个节点进行划分，在验证集中不能带来准确性的提升，那么对这个节点进行划分就没有意义，这时就会把当前节点作为叶节点，不对其进行划分。
后剪枝就是在生成决策树之后再进行剪枝，通常会从决策树的叶节点开始，逐层向上对每个节点进行评估。如果剪掉这个节点子树，与保留该节点子树在分类准确性上差别不大，或者剪掉该节点子树，能在验证集中带来准确性的提升，那么就可以把该节点子树进行剪枝。
纯度与信息熵
纯度
可以把决策树的构造过程理解成为寻找纯净划分的过程。数学上，我们可以用纯度来表示，纯度换一种方式来解释就是让目标变量的分歧最小。
比如有3个集合：
集合一：6天都去玩
集合二：4天去玩，2天不玩
集合三：3天玩，3天不玩
则纯度排序：集合一 > 集合二 > 集合三
信息熵
信息熵表示信息的不确定度。
信息熵的公式如下：
image.png
信息熵越大，纯度越低。
决策树的构造
在构造决策树的时候，会基于纯度来构建。而经典的 “不纯度”的指标有三种，分别是信息增益（ID3 算法）、信息增益率（C4.5 算法）以及基尼指数（Cart 算法）。
ID3算法
ID3 算法计算的是信息增益，信息增益指的就是划分可以带来纯度
的提高，信息熵的下降。它的计算公式，是父亲节点的信息熵减去所有子节点的信息熵。在计算的过程中，我们会计算每个子节点的归一化信息熵，即按照每个子节点在父节点中出现的概率，来计算这些子节点的信息熵。
以下为信息增益的计算公式：
image.png
我们需要计算不同属性的信息增益，并选择其中最大的作为父节点，这样可以得到纯度高的决策树。
一层一层的往下进行计算和分裂。
ID3 有一个缺陷就是，有些属性可能对分类任务没有太大作用，但是他们仍然可能会被选为最优属性。这种缺陷不是每次都会发生，只是存在一定的概率。在大部分情况下，ID3 都能生成不错的决策树分类。针对可能发生的缺陷，后人提出了新的算法进行改进。
C4.5算法（ID3改进）
采用信息增益率
因为 ID3 在计算的时候，倾向于选择取值多的属性。为了避免这个问题，C4.5 采用信息增益率的方式来选择属性。信息增益率 = 信息增益 / 属性熵。
当属性有很多值的时候，相当于被划分成了许多份，虽然信息增益变大了，但是对于 C4.5来说，属性熵也会变大，所以整体的信息增益率并不大。
采用悲观剪枝
ID3 构造决策树的时候，容易产生过拟合的情况。在 C4.5 中，会在决策树构造之后采用悲观剪枝（PEP），这样可以提升决策树的泛化能力。
离散化处理连续属性
C4.5 可以处理连续属性的情况，对连续的属性进行离散化的处理。
C4.5 选择具有最高信息增益的划分所对应的阈值。
处理缺失值
总结
ID3 算法的优点是方法简单，缺点是对噪声敏感。训练数据如果有少量错
误，可能会产生决策树分类错误。C4.5 在 ID3 的基础上，用信息增益率代替了信息增益，解决了噪声敏感的问题，并且可以对构造树进行剪枝、处理连续数值以及数值缺失等情况，但是由于 C4.5 需要对数据集进行多次扫描，算法效率相对较低。
二.CART算法
Classification And Regression Tree，中文叫做分类回归树。
CART 只支持二叉树。同时 CART 决策树比较特殊，既可以作分类
树，又可以作回归树。
什么是分类树？什么是回归树呢？
一棵决策树，想要基于数据判断这个人的职业身份，这个就属于分类
树，因为是从几个分类中来做选择。如果是给定了数据，想要预测这个人的年龄，那就属于回归树。
CART分类树工作流程
决策树的核心是寻找纯净的划分，因此引入了纯度的概念。实际上 CART 分类树与 C4.5 算法类似，只是属性选择的指标采用的是基尼系数。
基尼系数本身反应了样本的不确定度。当基尼系数越小的时候，说明样本之间的差异性小，不确定程度低。分类的过程本身是一个不确定度降低的过程，即纯度的提升过程。所以 CART 算法在构造分类树的时候，会选择基尼系数最小的属性作为属性的划分。
image.png
image.png
如何使用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.fit(train_features, train_labels)
#用CART分类树做预测
test_predict = clf.predict(test_features)
#预测结果与测试集结果做比对
score = accuracy_score(test_labels, test_predict)
print("cart分类树准确率 %.4lf" % score)
CART回归树的构造流程
CART回归树划分数据集的过程和分类树的过程是一样的，只是回归树得到的预测结果是连续值，而且评判“不纯度”的指标不同。在CART分类树中采用的是基尼系数作为标准，那么在CART回归树中，根据样本的混乱程度，也就是样本的离散程度来评价“不纯度”。
样本的离散程度具体的计算方式是，先计算所有样本的均值，然后计算每个样本值到均值的差值。我们假设x为样本的个体，均值为u。为了统计样本的离散程度，我们可以取差值的绝对值，或者方差。
image.png
所以这两种节点划分的标准，分别对应着两种目标函数最优化的标准，即用最小绝对偏差（LAD），或者使用最小二乘偏差（LSD）。
from sklearn.model_selection import train_test_split
from sklearn.metrics import mean_squared_error
from sklearn.metrics import r2_score, mean_absolute_error, mean_squared_error
from sklearn.tree import DecisionTreeRegressor
from sklearn.datasets import load_boston
#准备数据
boston = load_boston()
#获取特征集和分类标识
features = boston.data
prices = boston.target
#随机抽取33%的数据作为测试集，其余为训练集
train_features, test_features, train_price, test_price = train_test_split(features, prices, test_size=0.33)
#创建CART回归树
clf = DecisionTreeRegressor()
#拟合构造CART回归树
clf.fit(train_features, train_price)
#用CART分类树做预测房价
predict_price = clf.predict(test_features)
#预测结果与测试集结果做比对
print('回归树二乘偏差均值:', mean_squared_error(test_price, predict_price))
print('回归树绝对值偏差均值:', mean_absolute_error(test_price, predict_price))
三.决策树的应用
在金融行业可以用决策树做贷款风险评估，医疗行业可以用决策树生成辅助诊断，电商行业可以用决策树对销售额进行预测等。
四.K折交叉验证
这里可以使用 K 折交叉验证的方式，交叉验证是一种常用的验证分类准确率的方法，原理是拿出大部分样本进行训练，少量的用于分类器的验证。K 折交叉验证，就是做 K 次交叉验证，每次选取 K 分之一的数据作为验证，其余作为训练。轮流 K 次，取平均值。
K 折交叉验证的原理是这样的：
- 将数据集平均分割成 K 个等份；
- 使用 1 份数据作为测试数据，其余作为训练数据；
- 计算测试准确率；
- 使用不同的测试集，重复 2、3 步骤。
网友评论