决策树

机器学习

学习地址

  1. 理论篇
  2. 实战篇

关于数据

数据集矩阵X:

  • 和之前接触到的数据集一样，m个样本（X(1)，X(2)，X(3)，…），每个样本有n个特征，即数据集是一个m×n的矩阵。

数据集划分：

  • 我们可以从这个原始数据集中随机选取70%作为训练集/测试集，另30%作为验证集。

决策树模型

  • 决策树模型类似一个二叉树，非叶节点都是判定点/决策点，所有样本都在叶节点，根据非叶节点划分，预测最终所属分类
  • 决策树是一种基本的分类与回归方法，学习通常包含三个步骤：特征选择、决策树的生成和决策树的剪枝。
  • 一个关键的议题就是该从这n个特征中选取哪个特征作为根节点的分裂点呢？这个涉及到决策树一个很重要的一个概念：信息熵

输出y

  • 决策树生成并优化之后，所有样本数据就可以通过这个二叉树进行分类了，确定最终归属

熵理论

首先引入之前做的总结：浅谈互信息与熵

熵是从热力学引入过来的，最初描述一个系统的混乱程度。在这里，可以理解为一个事件的不确定性。
先从信息量说起，信息量顾名思义就是一个信息或者说一个子事件(可能)的信息量，比如：马云破产、国足夺冠，这种概率很小的事件包含的信息量很大。
而我们要研究一整个范围称为一个事件的话，这些子事件就是若干可能的情况，比如我们研究天气，有若干种可能的情况，每种情况有一个概率，但不难理解总的概率之和为1。
那么，假设某种可能事件x发生的概率为p(x)，那么这个可能事件所包含的信息量的度量方式就是：I(X)=-log p(x)。再回到熵，我们要知道我们所研究的这整个事件的不确定性，其实称之为信息熵就是这些子事件/可能的 信息量的期望。用H(X)来度量整体事件X的信息熵，H(X)=-p(x)log p(x )

条件熵

  • 定义H(Y|X)，也等于H(X,Y) - H(X)，其中H(X,Y)表示X，Y的联合熵，具体计算详见之前引用
  • 含义：X确定的情况下，确定Y所需要的信息量，即Y的不确定性
  • 需要注意的是，联合概率联合熵是对称的，而条件熵和条件概率一样是不对称的

决策树理论

  1. 决策树是一种树形判定结构，每个非叶节点都是表示对一种属性(特征)的测试，每个分支代表一个测试输出，而每个叶节点代表一种类别
  2. 决策树学习采用自顶向下的递归方法，其基本思想是以信息熵为度量构造一颗熵值下降最快的树，到叶子节点处的熵值为零（完全确定），每个叶节点中的实例都属于同一类
  3. 容易理解这颗判定树越到底层不确定性就越少
  4. 决策树的优点是可以进行自学习
信息增益 - ID3

上图：
信息增益

互信息

互信息

决策树标记

  • 记： 数据集记为D，样本数m=|D|
  • 记：最终叶节点个数为K，即有K个分类CK
  • 记：根据不同的特征将数据集划分为{D1, … , Dn }
  • 记：子集Di中属于类Ck的样本集合为Dik
  • 以上若干标记符号加绝对值符号表示取集合数量

ID3流程

  1. 计算数据集D的经验熵H(D)=-∑(|Ck| ÷ |D|) × In(|Ck| ÷ |D|)
  2. 遍历所有特征，对于每个特征Ai，计算经验条件熵H(D|Ai)
  3. 计算信息增益G(D,Ai)=H(D)-H(D|Ai)
  4. 选择信息增益最大的当做根节点的分裂特征
  5. 关于经验条件熵的计算如图
    经验条件熵
    信息增益计算
信息增益率C4.5 与 Gini系数

Gr(D,A)=g(D,A)÷H(A)
Gini=∑pk(1-pk) = 1-∑pk2 = 1-∑(|Ck|÷|D|)2

决策树评价

决策树评价

决策树实例

scikit-learn建模基本流程

sklearn借口调用

DecisionTree重要参数
  1. criterion：用来决定计算方法，可选["entropy", "gini"]，默认基尼系数
  2. 比起基尼系数，信息熵对不纯度更加敏感，对不纯度的惩罚最强。但是在实际使用中，信息熵和基尼系数的效果基本相同。信息熵的计算比基尼系数缓慢一些，因为基尼系数不涉及对数。
  3. random_state: 随机性，一旦这个参数指定值那么每次运行结果都是确定的，默认随机
  4. splitter: 控制决策树中随机选项，可选[best, random]，best表示虽然决策树在分枝时虽然是随机的但优先选取更重要的特征进行分枝（重要性可以通过属性feature_importances_查看），而random在分枝时会更随机，树可能会更深，同时也可以防止 过拟合
建树
1
2
3
from sklearn.tree import DecisionTreeClassifier # 导入分类树
from sklearn.datasets import load_wine  # 数据集
from sklearn.model_selection import train_test_split # 区分训练集和测试集
简单实例化
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
# 导入数据集
wine=load_wine() # Load and return the wine dataset (classification)
'''
wine.data 是特征
wine.feature_names 是属性
print(wine.feature_names) ['alcohol', 'malic_acid', 'ash',..., 'proline'] totally 13
wine.target 是标签
print(wine.target_names) # ['class_0' 'class_1' 'class_2']
print(wine.data.shape) # (178, 13)
print(wine.target.shape) # (178,)
'''

# 完整数据集
data=pd.concat([pd.DataFrame(wine.data),pd.DataFrame(wine.target)],axis=1)
'''
print(data.shape) # (178, 14)  # DataFrame
'''

# 划分测试集和训练集，其中30%作为测试集，注意赋值顺序固定
X_train,X_test,Y_train,Y_test=train_test_split(wine.data,wine.target,test_size=0.3)
'''
print(X_train.shape) # (124, 13)
'''

# 实例化
clf=DecisionTreeClassifier(criterion='entropy')
# 使用训练集训练模型
clf=clf.fit(X_train,Y_train)
# 调用接口导出我们所需要的数据，比如精确度
score=clf.score(X_test,Y_test)
print(score) # 0.9259259259259259
剪枝参数

为了让决策树有更好的泛化性（在测试集上表现同样好），需要对决策树进行剪枝。剪枝策略对决策树影响巨大，正确的剪枝策略是优化决策树算法的核心。

  1. max_depth=: 限制树的最大深度，超过设定深度的树枝全部剪掉
  2. min_samples_leaf=和min_samples_split=: 前者限定一个节点在分枝后每个子节点都必须包含至少min_samples_leaf个训练样本，否则将会被剪掉；后者限定一个节点至少包含min_samples_split个训练样本，这个节点才会被分枝，否者分枝不会被发生
  3. max_features=和min_impurity_decrease=: 前者限制分枝时考虑的特征个数，超过限制个数的特征都会被舍弃，用来限制高维度过拟合，但如果不知道属性重要性强行剪去特征可能会导致学习不足；后者限制信息增益的大小，信息增益小于设定数值分枝不会发生
超参数曲线

实际就是根据调参将结果绘制出来，衡量模型表现
例如：以深度作为参数，精确度作为衡量指标

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from sklearn.tree import DecisionTreeClassifier # 导入分类树
from sklearn.datasets import load_wine  # 数据集
from sklearn.model_selection import train_test_split # 区分训练集和测试集
import pandas as pd
import matplotlib.pyplot as plt

# 导入数据集
wine=load_wine() # Load and return the wine dataset (classification)
# 划分数据集
X_train,X_test,Y_train,Y_test=train_test_split(wine.data,wine.target,test_size=0.3)

score=[]
for i in range(10):
    clf = DecisionTreeClassifier(max_depth=i+1
                                 ,criterion='entropy'
                                 ,random_state=30
                                )
    clf = clf.fit(X_train, Y_train)
    score .append(clf.score(X_test, Y_test))

plt.plot(range(1,11),score,'r',label="max_depth")
plt.legend(loc="best")
plt.show()

超参数曲线
根据上图可以明显地观察到max_depth取值为3就可以了

重要属性和接口

这里的属性是指算法模型训练之后能够查看的各种模型的性质

  1. clf.apply(X_test)：返回每个测试样本所在叶子节点的索引
  2. clf.predict(X_test)：返回每个测试样本的预测结果
总结

总结