决策树与正则化超参数

2019-06-25 本文已影响0人 Cingti

星期二, 25. 六月 2019 09:43下午

博客理论部分参考李航《统计学习方法》第一版；
博客决策树部分主要讲CART树的生成和正则化结构以及python的实现和主要参数的意义；

CART为分类与回归树(classification and regression tree)的简称，CART假设决策树是二叉树，内部节点特征的取值为是和否。在决策树算法中，寻找最优决策树是一个NPC问题，即无法用计算机在多项式时间内，找出全局最优解，因此，大多数决策树算法都采用启发式的思想，在每一个节点上寻找局部最优解，于是，决策树得到的结果无法保证全局最优解。

注：NPC问题指的是计算机对于能否在多项式时间内求出问题的解是未知的，但是可以确定在多项式时间内验证这个解。

1.回归树的生成算法

回归树对应着输入空间的一个划分以及在划分的单元上的输出值。这里采用启发式的思想，选择第 $j$ 个变量 $x^{(j)}$ 和它的取值 $s$ ，作为切分变量和切分点，并定义切分得到的区域分别为 $R_1$ 和 $R_2$ :
$R_1(j,s)=\{x|x^{(j)}\leq s\}$
$R_2(j,s)=\{x|x^{(j)}> s\}$
然后寻找最优切分变量 $j$ 和最优切分点 $s$ ，这里采用MSE来计算，求解下式：
$\min \limits_{j,s} [\min \limits_{c_1}\sum \limits_{x_i\in R_1(j,s)}(y_i-c_1)^2+\min \limits_{c_2}\sum \limits_{x_i\in R_2(j,s)}(y_i-c_2)^2]$
对于固定输入变量 $j$ 可以找到最优切分点 $s$ 。遍历所有输入变量，找到最优的切分变量 $j$ ，构成一个 $(j,s)$ 对，依次将输入空间划分为两个区域，接着，重复上述过程，对每个区域重复上述过程，直到满足停止条件为止。

2.分类树的生成算法

分类树的生成算法和回归树类似，只是分类树用基尼指数选择最优特征，同时决定该特征的最优二值切分点。
在特征 $A$ 的条件下，集合 $D$ 的基尼指数的定义为：
$Gini(D,A)=\frac{|D_1|}{|D|}Gini(D_1)+\frac{|D_2|}{|D|}Gini(D_2)$
其中，样本集合 $D$ 根据特征 $A$ 是否取某一可能值 $a$ 被分割成 $D_1$ 和 $D_2$ 两部分；基尼指数 $Gini(D)$ 表示集合 $D$ 的不确定性，基尼系数 $Gini(D,A)$ 表示经 $A=a$ 分割后集合 $D$ 的不确定性。
对于给定的样本集合 $D$ ，其基尼指数为：
$Gini(D)=1-\sum_{k=1}^{K}(\frac{|C_k|}{|D|})^2$
其中， $C_k$ 是 $D$ 中属于第 $k$ 类的样本子集， $K$ 是类的个数。

3.Python下决策树函数的参数解释

《统计学习方法》中关于决策树的生长没有任何约束，这样的模型通常称为非参数模型，这样的树结构模型通常将根据训练数据调整自己，使自身能够很好的拟合数据，但是大多数会导致模型过拟合，因此在该书中采用剪枝的方法来控制过拟合。
DecisionTreeClassifier类和DecisionTreeRegressor类运用正则化超参数通过限制树模型的生长来控制过拟合。
本篇博客不介绍剪枝的内容，只介绍sklearn.tree下两个类的运用。

(1)DecisionTreeClassifier和DecisionTreeRegressor主要参数解释

max_depth: 树的深度;
min_samples_split: 节点在被分裂之前必须具有的最小样本数或最小样本占全部样本的比例;
min_samples_leaf: 叶节点具有的最小样本数或最小样本占全部样本的比例;
max_features: 节点在分裂时具有的最大特征数或最大特征数占全部特征的比例;
max_leaf_nodes: 叶节点的最大数量;
presort=False: 预分类(当数据少时可以加快训练过程,数据多时会减慢训练过程).

注：通过增大min_samples_split值和min_samples_leaf值或者减少max_features值和max_leaf_nodes,可以使模型有效控制过拟合

(2)采用export_graphviz对树结构的可视化

# -*- coding: utf-8 -*-

from sklearn.tree import DecisionTreeClassifier
from sklearn.datasets import load_iris
from sklearn.tree import export_graphviz

iris = load_iris()
X = iris.data
y = iris.target


tree_clf = DecisionTreeClassifier(
    max_depth=None,
    min_samples_split=2,
    min_samples_leaf=3,
    max_features=None,
    max_leaf_nodes=None,
    presort=False,
).fit(X, y)

export_graphviz(
    tree_clf,
    out_file="iris_tree.dot",
    feature_names=iris.feature_names,
    class_names=iris.target_names,
    rounded=True,
    filled=True,
)

执行完上述程序后，会在文件夹下生成iris_tree.dot文件，需要在cd到该文件夹下的终端，输入代码

dot -Tpng iris_tree.dot -o iris_tree.png

即可生成树状结构的.png图，效果如下。

iris_tree.png

第三篇未讲完部分会在后期补上，第五篇开始就会结合深度学习一起讲，欢迎留言

决策树与正则化超参数

1.回归树的生成算法

2.分类树的生成算法

3.Python下决策树函数的参数解释

猜你喜欢

热点阅读