决策树的工作原理
决策树的时候，会经历两个阶段：构造和剪枝。
构造
构造就是生成一棵完整的决策树。构造的过程就是选择什么属性作为节点的过程，那么在构造过程中，会存在三种节点：
- 根节点：就是树的最顶端，最开始的那个节点。在上图中，“天气”就是一个根节点；
- 内部节点：就是树中间的那些节点，比如说“温度”、“湿度”、“刮风”；
- 节点之间存在父子关系。比如根节点会有子节点，子节点会有子子节点，但是到了叶节点就停止了，叶节点不存在子节点。
那么在构造过程中，你要解决三个重要的问题：
剪枝
剪枝就是给决策树瘦身，这一步想实现的目标就是，不需要太多的判断，同样可以得到不错的结果。之所以这么做，是为了防止“过拟合”（Overfitting）现象的发生。
剪枝分类
- 预剪枝是在决策树构造时就进行剪枝。
- 后剪枝就是在生成决策树之后再进行剪枝，通常会从决策树的叶节点开始，逐层向上对每个节点进行评估。
信息熵（entropy）
它表示了信息的不确定度。在信息论中，随机离散事件出现的概率存在着不确定性。为了衡量这种信息的不确定性，信息学之父香农引入了信息熵的概念，并给出了计算信息熵的数学公式：
%3D-%5Csum%7Bi%3D0%7D%5E%7Bc-1%7Dp(i%7Ct)log_2p(i%7Ct)%0A#card=math&code=Entropy%28t%29%3D-%5Csum%7Bi%3D0%7D%5E%7Bc-1%7Dp%28i%7Ct%29log_2p%28i%7Ct%29%0A)
- $p(i|t)
t$ 为分类$ i$ 的概率
- 其中$ log_2$ 为取以 2 为底的对数。
说存在一种度量，它能帮我们反映出来这个信息的不确定度。当不确定性越大时，它所包含的信息量也就越大，信息熵也就越高。
信息熵越大，纯度越低。
我们在构造决策树的时候，会基于纯度来构建。而经典的 “不纯度”的指标有三种，分别是信息增益（ID3 算法）、信息增益率（C4.5 算法）以及基尼指数（Cart 算法）。
ID3 算法
ID3 算法计算的是信息增益，信息增益指的就是划分可以带来纯度的提高，信息熵的下降。
%3DEntropy(D)-%5Csum%7Bi%3D1%7D%5Ek%5Cfrac%7B%7CD_i%7C%7D%7B%7CD%7C%7DEntropy(D_i)%0A#card=math&code=Gain%28D%2Ca%29%3DEntropy%28D%29-%5Csum%7Bi%3D1%7D%5Ek%5Cfrac%7B%7CD_i%7C%7D%7B%7CD%7C%7DEntropy%28D_i%29%0A)
是父亲节点
是子节点
#card=math&code=Gain%28D%2Ca%29) 中的
作为 $D $节点的属性选择。
C4.5 算法
在 ID3 算法上进行改进的C4.5算法
- 采用信息增益率
因为 ID3 在计算的时候，倾向于选择取值多的属性。为了避免这个问题，C4.5 采用信息增益率的方式来选择属性。信息增益率 = \frac{信息增益}{属性熵}
当属性有很多值的时候，相当于被划分成了许多份，虽然信息增益变大了，但是对于 C4.5 来说，属性熵也会变大，所以整体的信息增益率并不大。
- 采用悲观剪枝
ID3 构造决策树的时候，容易产生过拟合的情况。在 C4.5 中，会在决策树构造之后采用悲观剪枝（PEP），这样可以提升决策树的泛化能力。
悲观剪枝是后剪枝技术中的一种，通过递归估算每个内部节点的分类错误率，比较剪枝前后这个节点的分类错误率来决定是否对其进行剪枝。这种剪枝方法不再需要一个单独的测试数据集。
- 离散化处理连续属性
C4.5 可以处理连续属性的情况，对连续的属性进行离散化的处理。C4.5 选择具有最高信息增益的划分所对应的阈值。
- 处理缺失值
针对数据集不完整的情况，C4.5 也可以进行处理。
CART 算法
CART 算法，英文全称叫做 Classification And Regression Tree，中文叫做分类回归树。ID3 和 C4.5 算法可以生成二叉树或多叉树，而 CART 只支持二叉树。同时 CART 决策树比较特殊，既可以作分类树，又可以作回归树。
分类树
分类树可以处理离散数据，也就是数据种类有限的数据，它输出的是样本的类别。
回归树
回归树可以对连续型的数值进行预测，也就是数据在某个区间内都有取值的可能，它输出的是一个数值。
CART 分类树的流程
决策树的核心就是寻找纯净的划分，因此引入了纯度的概念。
在属性选择上，我们是通过统计“不纯度”来做判断的，ID3 是基于信息增益做判断，C4.5 在 ID3 的基础上做了改进，提出了信息增益率的概念。CART 分类树只是属性选择的指标采用的是基尼系数。
基尼系数
基尼系数本身反应了样本的不确定度。
- 当基尼系数越小的时候，说明样本之间的差异性小，不确定程度低。
- 分类的过程本身是一个不确定度降低的过程，即纯度的提升过程。
- CART 算法在构造分类树的时候，会选择基尼系数最小的属性作为属性的划分。
假设 t 为节点，那么该节点的 GINI 系数的计算公式为：
%5D%5E2%0A#card=math&code=GINI%3D1-%5Csum_%7Bk%7D%5Bp%28C_k%7Ct%29%5D%5E2%0A)
#card=math&code=p%28C_k%7Ct%29)表示节点 t 属于类别
的概率
- 节点
的基尼系数为 1 减去各类别
CART 决策树的剪枝
CART 决策树的剪枝主要采用的是 CCP 方法，它是一种后剪枝的方法，英文全称叫做 cost-complexity prune，中文叫做代价复杂度。这种剪枝方式用到一个指标叫做节点的表面误差率增益值，以此作为剪枝前后误差的定义。用公式表示则是：
-C(T_t)%7D%7B%7CT_t%7C-1%7D%0A#card=math&code=%5Calpha%3D%5Cfrac%7BC%28t%29-C%28T_t%29%7D%7B%7CT_t%7C-1%7D%0A)
代表以 t 为根节点的子树
#card=math&code=C%28T_t%29)表示节点 t 的子树没被裁剪时子树
#card=math&code=C%28t%29) 表示节点 t 的子树被剪枝后节点 t 的误差
代子树
。
即：
因为我们希望剪枝前后误差最小，所以我们要寻找的就是最小值对应的节点，把它剪掉。这时候生成了第一个子树。重复上面的过程，继续剪枝，直到最后只剩下根节点，即为最后一个子树。
得到了剪枝后的子树集合后，我们需要用验证集对所有子树的误差计算一遍。可以通过计算每个子树的基尼指数或者平方误差，取误差最小的那个树，得到我们想要的结果。
总结
- ID3 算法
- 优点是方法简单，缺点是对噪声敏感。
- 训练数据如果有少量错误，可能会产生决策树分类错误。
- C4.5算法
- 在 ID3 的基础上，用信息增益率代替了信息增益，解决了噪声敏感的问题
- 可以对构造树进行剪枝、处理连续数值以及数值缺失等情况
- 由于 C4.5 需要对数据集进行多次扫描，算法效率相对较低
- CART 决策树，是一棵决策二叉树，既可以做分类树，也可以做回归树。
- 作为分类树，CART 采用基尼系数作为节点划分的依据，得到的是离散的结果，也就是分类结果；
- 作为回归树，CART 可以采用最小绝对偏差（LAD），或者最小二乘偏差（LSD）作为节点划分的依据，得到的是连续值，即回归预测结果。
三种决策树之间在属性选择标准上的差异：
| 算法 | 判断依据 |
|---|---|
| ID3算法 | 信息增益 |
| C4.5算法 | 信息增益率 |
| CART算法 | 分类树：基尼系数 回归树：偏差 |
sklearn实现
DecisionTreeClassifier(class_weight=None, criterion='entropy', max_depth=None,max_features=None, max_leaf_nodes=None,min_impurity_decrease=0.0, min_impurity_split=None,min_samples_leaf=1, min_samples_split=2,min_weight_fraction_leaf=0.0, presort=False, random_state=None,splitter='best')
criterion，对应的取值分别是 entropy 或者 gini
- entropy: 基于信息熵，也就是 ID3 算法，实际结果与 C4.5 相差不大
- gini：默认参数，基于基尼系数。CART 算法是基于基尼系数做属性划分的，所以 criterion=gini 时，实际上执行的是 CART 算法
分类树
from sklearn import treefrom sklearn.model_selection import train_test_splitfrom sklearn.metrics import accuracy_scorefrom sklearn.tree import DecisionTreeClassifierfrom sklearn.datasets import load_irisimport pandas as pd# 准备数据集iris=load_iris()# 获取特征集和分类标识features = iris.datalabels = iris.targetiris = load_iris()df = pd.DataFrame(iris.data, columns=iris.feature_names)df.head()
| sepal length (cm) | sepal width (cm) | petal length (cm) | petal width (cm) | |
|---|---|---|---|---|
| 0 | 5.1 | 3.5 | 1.4 | 0.2 |
| 1 | 4.9 | 3.0 | 1.4 | 0.2 |
| 2 | 4.7 | 3.2 | 1.3 | 0.2 |
| 3 | 4.6 | 3.1 | 1.5 | 0.2 |
| 4 | 5.0 | 3.6 | 1.4 | 0.2 |
# 随机抽取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)print("CART分类树准确率 %.4lf" % score)
CART分类树准确率 0.9600
dot_data = tree.export_graphviz(clf,out_file=None)
graph= graphviz.Source(dot_data)
graph
回归树
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_price, test_price = train_test_split(features, prices, test_size=0.33)
# 创建CART回归树
dtr=DecisionTreeRegressor()
# 拟合构造CART回归树
dtr.fit(train_features, train_price)
# 预测测试集中的房价
predict_price = dtr.predict(test_features)
# 测试集的结果评价
print('回归树二乘偏差均值:', mean_squared_error(test_price, predict_price))
print('回归树绝对值偏差均值:', mean_absolute_error(test_price, predict_price))
['CRIM' 'ZN' 'INDUS' 'CHAS' 'NOX' 'RM' 'AGE' 'DIS' 'RAD' 'TAX' 'PTRATIO'
'B' 'LSTAT']
回归树二乘偏差均值: 26.261257485029937
回归树绝对值偏差均值: 3.0293413173652692
dtr=dtr.fit(train_features, train_price)
dot_data = tree.export_graphviz(dtr,out_file=None)
graph= graphviz.Source(dot_data)
graph
分类树
from sklearn import tree
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
import pandas as pd
# 准备数据集
iris=load_iris()
# 获取特征集和分类标识
features = iris.data
labels = iris.target
iris = load_iris()
df = pd.DataFrame(iris.data, columns=iris.feature_names)
df.head()
| sepal length (cm) | sepal width (cm) | petal length (cm) | petal width (cm) | |
|---|---|---|---|---|
| 0 | 5.1 | 3.5 | 1.4 | 0.2 |
| 1 | 4.9 | 3.0 | 1.4 | 0.2 |
| 2 | 4.7 | 3.2 | 1.3 | 0.2 |
| 3 | 4.6 | 3.1 | 1.5 | 0.2 |
| 4 | 5.0 | 3.6 | 1.4 | 0.2 |
# 随机抽取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)
print("CART分类树准确率 %.4lf" % score)
CART分类树准确率 0.9600
dot_data = tree.export_graphviz(clf,out_file=None)
graph= graphviz.Source(dot_data)
graph
分类树
from sklearn import tree
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
import pandas as pd
# 准备数据集
iris=load_iris()
# 获取特征集和分类标识
features = iris.data
labels = iris.target
iris = load_iris()
df = pd.DataFrame(iris.data, columns=iris.feature_names)
df.head()
| sepal length (cm) | sepal width (cm) | petal length (cm) | petal width (cm) | |
|---|---|---|---|---|
| 0 | 5.1 | 3.5 | 1.4 | 0.2 |
| 1 | 4.9 | 3.0 | 1.4 | 0.2 |
| 2 | 4.7 | 3.2 | 1.3 | 0.2 |
| 3 | 4.6 | 3.1 | 1.5 | 0.2 |
| 4 | 5.0 | 3.6 | 1.4 | 0.2 |
# 随机抽取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)
print("CART分类树准确率 %.4lf" % score)
CART分类树准确率 0.9600
dot_data = tree.export_graphviz(clf,out_file=None)
graph= graphviz.Source(dot_data)
graph
回归树
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_price, test_price = train_test_split(features, prices, test_size=0.33)
# 创建CART回归树
dtr=DecisionTreeRegressor()
# 拟合构造CART回归树
dtr.fit(train_features, train_price)
# 预测测试集中的房价
predict_price = dtr.predict(test_features)
# 测试集的结果评价
print('回归树二乘偏差均值:', mean_squared_error(test_price, predict_price))
print('回归树绝对值偏差均值:', mean_absolute_error(test_price, predict_price))
['CRIM' 'ZN' 'INDUS' 'CHAS' 'NOX' 'RM' 'AGE' 'DIS' 'RAD' 'TAX' 'PTRATIO'
'B' 'LSTAT']
回归树二乘偏差均值: 26.261257485029937
回归树绝对值偏差均值: 3.0293413173652692
dtr=dtr.fit(train_features, train_price)
dot_data = tree.export_graphviz(dtr,out_file=None)
graph= graphviz.Source(dot_data)
graph
回归树
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_price, test_price = train_test_split(features, prices, test_size=0.33)
# 创建CART回归树
dtr=DecisionTreeRegressor()
# 拟合构造CART回归树
dtr.fit(train_features, train_price)
# 预测测试集中的房价
predict_price = dtr.predict(test_features)
# 测试集的结果评价
print('回归树二乘偏差均值:', mean_squared_error(test_price, predict_price))
print('回归树绝对值偏差均值:', mean_absolute_error(test_price, predict_price))
['CRIM' 'ZN' 'INDUS' 'CHAS' 'NOX' 'RM' 'AGE' 'DIS' 'RAD' 'TAX' 'PTRATIO'
'B' 'LSTAT']
回归树二乘偏差均值: 26.261257485029937
回归树绝对值偏差均值: 3.0293413173652692
dtr=dtr.fit(train_features, train_price)
dot_data = tree.export_graphviz(dtr,out_file=None)
graph= graphviz.Source(dot_data)
graph
若有收获，就点个赞吧
0 人点赞
