决策树模型

2019-01-03 本文已影响49人 Zimix

决策树

决策树里面最重要的就是节点和分裂条件，直接决定了一棵树的好坏。用一个简单的例子先说明一下：
来一段情景对话：
母亲：女儿，你也不小了，还没对象！妈很揪心啊，这不托人给你找了个对象，明儿去见个面吧！
女儿：年纪多大了？
母亲：25
女儿：长的帅不帅？
母亲：挺帅的！
女儿：收入高不高？有没有上进心？
母亲：收入还行，蛮有上进心！
$\vdots$
就这样女儿建立了一棵决策树：

这种简单的决策树，处处可见。女儿一步步选择重要特征（年龄、长相、收入等）并构建特征分割方式（年纪大小、长相帅不帅、收入高不高），让自己进行最优的决策。

决策树的构建过程
很显然，由上面的例子可以看到构建一个决策树需要如下步骤：
1、收集样本
没有要决策的对象，一切都是扯淡。就是例子中母亲托人找对象的过程。
2、选择特征-----构建节点
根据特征的重要度，来构建子节点，越重要的特征越靠近根节点。也就是女儿觉得那些条件最重要，当最重要的条件不满足，就没必要继续了。
3、特征的分裂方式-----分裂节点
根据特征的分裂方式，来划分数据集，也就是根据条件区别对待。就是年纪太大的压根就不予考虑，年龄合适的才进一步考察。
其实在实际构建树模型的时候，2和3是通过遍历的方式同时进行的。

上面的例子是主观的分裂节点，那么如何科学的构建节点分裂呢？下面来说明：
我们觉得什么样才算好，通俗来说就是通过越少的分裂，达到更好的区分度。用术语说就是当选择了这个条件之后，系统的不确定度下降最多。这个特征就是我们要重视的feature！在这里就不得不引入信息论中的一些知识了，主要是信息熵和不纯度，详情请参考我在语雀中总结的一一篇文档。
主要是通过以下几种算法来实现最优分裂的效果：

ID3算法

系统的信息熵是 $H(c)$ ，分别计算每个特征的条件熵 $H(c|x)$ ，然后得到每个条件的信息增益 $IG(x) = H(c) -H(c|x)$ 。通过判断每个特征的 $IG(x)$ 的大小来决定特征的重要度。所以ID3算法是基于信息增益，信息增益大，则越适合用来分类。在具体的特征分裂的时候，每个条件的分裂是遍历了所有的可能（离散值有多少个就有多少个可能），这是一种贪心算法。所以这个算法不支持连续特征，也是缺点之一。

C4.5算法

与ID3算法的思路基本相同，只是解决了ID3算法中的一些缺点，比如将连续值离散化从而支持连续型特征，采用信息增益比 $Gr(x) = IG(x)/H(x)$ 来代替ID3算法的信息增益，解决了信息增益偏向分支过多的特征。也补充了剪枝和补全缺失值的操作。

CART算法

简单来说，CART算法是不断的生成二叉树，能分类也能回归，因此也叫分类回归树。在生成分类树时，采用的是基尼系数 $Gini(c)$ ，也叫不纯度。生成回归树则采用的是节点样本的方差 $Var(x)$ 来做分裂标准。这些过程，3种算法都差不多，有区别的是CART算法如何生成二叉树？
CART对连续型属性的处理与C4.5差不多，也是先离散化。而对于离散型属性，理论上有多少个离散值就应该分裂成多少个节点。但CART是一棵二叉树，每一次分裂只会产生两个节点，怎么办呢？很简单，只要将其中一个离散值独立作为一个节点，其他的离散值生成另外一个节点即可。这种分裂方案有多少个离散值就有多少种划分的方法，举一个简单的例子：如果某离散属性一个有三个离散值x，y，z，则该属性的分裂方法有【x、(y，z)】，【y、(z，x)】，【z，(x，y)】，分别计算每种划分方法的基尼值或者样本方差确定最优的方法。原则就是通过一个条件将样本空间一分为二。

决策树的评价

分类树：
假定某个样本空间有 $k$ 类，对于生成好的一棵决策树的某叶子结点，假定该叶结点含有样本数目为 $m$ ，可以分别统计该叶子节点下每个分类的频数 $m_i (i \in k)$ 。每个类别的概率 $p_i = m_i/m$ ，于是这个叶子节点的信息熵就是 $H(t) = -p_ilog(p_i)$ 。信息熵越小，系统的区分度越明显。所以最终对于一棵分类树的评价可以用下面的公式来评判（ $w_t$ 叶子节点的权重，可以更具样本数目来决定）： $loss = \sum_{t\in{leaf}} w_t \cdot H(t)$ 对于不同的算法，并不完全都是用信息熵，也可以采用基尼系数来代替信息熵。
回归树：
假定某个样本空间，对于生成好的一棵决策树的某叶子结点，假定该叶结点含有样本数目为 $m$ ，计算这个叶子节点的方差 $Var(t) = \sum_{i=1}^m (x_i-\hat x)^2$ 。所以最终对于一棵回归树的评价可以用下面的公式来评判（ $w_t$ 叶子节点的权重，可以更具样本数目来决定）： $loss = \sum_{t\in{leaf}} w_t \cdot Var(t)$

决策树的剪枝

决策树对训练属于有很好的分类能力，但是对于未知的测试集未必有好的分类能力，泛化能力弱，即可能发生过拟合现象。为防止过拟合，我们需要进行剪枝。三种决策树的剪枝过程算法相同，区别是对于当前树的评价标准不同。
剪枝分为预剪枝和后剪枝：
预剪枝：
在树还没有完全分裂完成的时候，设定阈值，停止分裂：
（1）每一个结点所包含的最小样本数目，例如10，则该结点总样本数小于10时，则不再分；
（2）指定树的高度或者深度，例如树的最大深度为4；
（3）指定结点的熵小于某个值，不再划分。
后剪枝：
在树已经完全分裂之后，进行剪枝：
由完全树 $T_0$ 开始，剪枝部分结点（叶子节点，或者子节点）得到 $T_1$ ，再次剪枝部分结点得到 $T_2$ ...，直到剩下树根的树（就是根节点） $T_k$ ；在验证数据集上对这 $k$ 个树分别评价，选择损失函数最小的树 $T_a$ 。

C4.5采用悲观剪枝方法(PEP)
悲观剪枝认为如果决策树的精度在剪枝前后没有影响的话，则进行剪枝。怎样才算是没有影响？如果剪枝后的误差小于剪枝前经度的上限，则说明剪枝后的效果更佳，此时需要子树进行剪枝操作。
CART采用代价复杂度剪枝方法(CCP)
代价复杂度选择节点表面误差率增益值最小的非叶子节点，删除该非叶子节点的左右子节点，若有多个非叶子节点的表面误差率增益值相同小，则选择非叶子节点中子节点数最多的非叶子节点进行剪枝。

决策好的一棵树，除去叶子节点后有 $\{ T_0,T_1,T_2,T_3,...,T_{k-1},T_k\}$
计算每个子节点剪枝后的表面误差率增益 $\{ \alpha_0,\alpha_1,\alpha_2,\alpha_3,...,\alpha_{k-1},\alpha_k\}$
$\alpha = \frac{loss(t)-loss(T)}{leaf(T)-1}$
$loss(t)$ 剪枝后的损失函数
$loss(T)$ 剪枝前的损失函数
$leaf(T)$ 剪枝前T节点下面的叶子节点数
$T_i$ = Min( $\{ \alpha_0,\alpha_1,\alpha_2,\alpha_3,...,\alpha_{k-1},\alpha_k\}$ )，剪枝最小的子节点 $T_i$ 。

随机森林----一片决策树森林

这个可以当作是决策树解决过拟合的一种方式。随机的采用样本的某些特征构建多棵简单的决策树，然后预测结果是这么多棵决策树预测结果的综合。用于分类就多数表决，用于回归就是取平均值。不想多说。
决策树单独作为一个算法的效果不是特别好，更多的是在集成算法种充当内核。比如xgboost、adboost之类的。

code

基于sklearn.tree模块
分类树：

from sklearn import datasets
from sklearn.tree import DecisionTreeClassifier

# 使用自带的iris数据
iris = datasets.load_iris()
X = iris.data[:, [0, 2]]
y = iris.target

# 创建模型

'''
    常用参数说明：
    criterion="gini"    ----    'entropy'-->信息熵，'gini'-->基尼系数
    splitter="best"     ----    'best'-->全局最优分裂，'random'-->随机选择局部最优点
    max_depth=None      ----    设定树深度
    min_samples_split=2 ----    内部节点停止分裂的最小样本数
    min_samples_leaf=1  ----    叶子节点的最小样本数，如果实际值小于它，则会和兄弟节点一起被剪枝
    max_features=None,  ----    分裂的时候要考虑的样本特征比例
    max_leaf_nodes=None,----    最大叶子节点数
'''
clf = DecisionTreeClassifier(max_depth=4)

# 训练模型
clf.fit(X, y)

回归树：

from sklearn.datasets.california_housing import fetch_california_housing
from sklearn.tree import DecisionTreeRegressor

# 使用波士顿房价数据
housing = fetch_california_housing()
X = housing.data[:, [6, 7]]
y = housing.target

'''
criterion="mse" ----    和分类树一样，评价指标，'mse'是均方误差，'mae'是绝对值误差
'''
# 创建模型
dtr = tree.DecisionTreeRegressor(max_depth = 2)

# 训练模型
dtr.fit(x, y)

随机森林：

from sklearn.ensemble import RandomForestClassifier
from sklearn import datasets

# 使用自带的iris数据
iris = datasets.load_iris()
X = iris.data
y = iris.target

'''
树的基本参数设定和分类树差不多
n_estimators=10,    ----    建立多少棵树
bootstrap=True,     ----    是统计学中的一种重采样技术，可以简单理解成是有放回地抽样
oob_score=False,    ----    是否使用带外样本进行模型验证
n_jobs=1,           ----    并行job个数，1：CPU有多少core，就启动多少job
warm_start=False,   ----    热启动，决定是否使用上次调用该类的结果然后增加新的。
'''
rftcl = RandomForestClassifier()

rftcl.fit(x,y)

参考