机器学习从原理到应用Chp8-决策树

第8章

决策树大纲决策树简介树的构建划分准则剪枝决策树模型是一种树状模型，可用于分类或回归树：分级，将一个复杂问题转化为若干个简单问题来解决（分而治之）对多类分类任务和多峰分布数据尤其适合树：由结点和有向边组成

结点：特征空间子集

边：划分规则

从根结点到叶子结点的有向边代表了一条决策路径。

决策树的路径是互斥并且完备的决策树简介决策树可视化工具：dtreeviz

https://explained.ai/decision-tree-viz/index.html/parrt/dtreeviz/tree/master例：鸢尾花分类的决策树叶子结点叶子结点叶子结点例：决策树用于回归大纲决策树简介树的构建划分准则剪枝决策树构建初始化：构建根结点，将所有训练数据放在根结点，并根结点加入叶子结点列表；若叶子结点列表为空，算法结束，返回生成的决策树；否则从叶子结点列表中挑选1个叶子结点，

2.1：若该叶子结点的样本集合已足够纯净，计算该叶子结点的预测值，并将其从叶子结点列表中删除（不再划分）；

2.2:否则，对该叶子结点进行近一步划分：

（1）对每个特征的每个可能的划分方式，尝试将该结点的样本集合进行划分，计算划分后数据的纯净度和划分的分数；（2）从第（1）步所有的划分中，选择一个最优划分（分数最高），将训练数据划分成若干子集，每个子集为当前结点的子结点，并将这些子结点加入叶子结点列表，同时将当前结点从叶子结点列表中删除；决策树构建选择一个合适的树结构

二叉树、多叉树确定在每个非叶子结点上要使用的特征所有特征（训练性能更好）、随机选择特征子集（更快，测试性能可能也不差）在每个非叶子结点上选择合适的决策规则划分点的选择：精确搜索/穷举所有可能的划分点（训练性能更好）、近似搜索/直方图（更快，测试性能可能也不差）划分点的评价准则：信息熵增益、信息熵增益率、Gini指数、带正则的Gini指数停止划分条件足够纯净、最大深度、最大叶子结点数目、结点的最小样本数目、…剪枝大纲决策树简介树的构建划分准则剪枝

决策树熵&经验熵

条件熵&经验条件熵

信息增益

划分前：经验信息熵为1划分后：经验信息熵为0例：信息增益日志密度L好友密度F是否使用真实头像H账号是否真实Rssnonoslyesyeslmyesyesmmyesyeslmyesyesmlnoyesmsnonolmnoyesmsnoyesssyesno

日志密度L:

账号真实的概率账号不真实的概率

信息增益日志密度L好友密度F是否使用真实头像H账号是否真实Rssnonoslyesyeslmyesyesmmyesyeslmyesyesmlnoyesmsnonolmnoyesmsnoyesssyesno

信息增益率

Gini指数：无需log，计算更快为什么不用错误率？错误率曲线分两个区间，在每个区间是直线，如果划分后的子结点和父结点在同一条直线上，则划分后错误率不会下降，从而无法进一步分裂结点。Gini指数

两类分类的不纯度度量熵的曲线也分两个区间，但在每个区间是向上凸起，划分后子结点的熵的平均会比分裂前的熵小，从而可以继续分裂结点，直到达到分裂停止标准。

父结点包含10个样本，其中正负样本数目分别为7，3，则例：错误率vs.Gini指数

左子结点：包含5个样本，其中正负样本数目分别为3，2例：错误率vs.熵/Gini指数

右子结点：包含5个样本，其中正负样本数目分别为4，1例：错误率vs.熵/Gini指数

分裂后的平均：分裂前：例：错误率vs.熵/Gini指数

分裂后错误率没变，熵减少

分类回归树（ClassificationAndRegressionTree，CART）例：离散型特征日志密度L好友密度F是否使用真实头像H账号是否真实Rssnonoslyesyeslmyesyesmmyesyeslmyesyesmlnoyesmsnonolmnoyesmsnoyesssyesno

widthheightClass7.09.5Orange6.96.0Orange6.66.6Orange6.56.6Lemon6.06.6Lemon6.99.6Lemon例：连续型特征根据特征width的取值，对所有样本进行排序得到可能的阈值为：6.25，6.55，6.75,6.95widthheightClass6.06.6Lemon6.56.6Lemon6.66.6Orange6.96.0Orange6.99.6Lemon7.09.5Orange对每个可能的阈值，计算划分后的Gini指数：

例：连续型特征根据特征height的取值，对所有样本进行排序得到可能的阈值为：6.3，8.05，9.55widthheightClass6.96.0Orange6.06.6Lemon6.56.6Lemon6.66.6Orange7.09.5Orange6.99.6Lemon对每个可能的阈值，计算划分后的Gini指数：

width>6.552Lemons1Lemon,3Oranges

建树过程是一个自顶向下的递归过程。递归的停止条件划分带来的损失的减小太小树的深度超过了最大深度叶子结点数目超过了最大数目左／右分支的样本分布足够纯净左／右分支中样本数目足够少划分停止条件大纲决策树简介树的构建划分准则剪枝

剪枝

叶子结点数目正则因子对所有叶子结点求和

=

对所有样本求和（一个样本总会落入某个叶子结点）

剪枝

蓝色虚线框内未剪枝部分费用不变，故而在此忽略

剪枝

对一系列子树，计算其在验证集上的性能验证集上性能最好的剪枝树胜出

验证集

Scikit-Learn中对剪枝的支持path=clf.cost_complexity_pruning_path(X_train,y_train)ccp_alphas,impurities=path.ccp_alphas,path.impuritiesclfs=

[]forccp_alphainccp_alphas:

clf=

DecisionTreeClassifier(random_state=0,ccp_alpha=ccp_alpha)

clf.fit(X_train,y_train)

clfs.append(clf)train_scores=

[clf.score(X_train,y_train)

forclfinclfs]test_scores=

[clf.score(X_test,y_test)

forclfinclfs]

容易解释对特征预处理要求少（理论上）能处理离散值和连续值混合的输入（实际需根据具体工具包的要求）对特征的单调变换不敏感

（只与数据的排序有关）能自动进行特征选择可扩展到大数据规模决策树模型的优点正确率不高：建树过程过于贪心可作为Boosting的弱学习器（深度不太深）模型不稳定（方差大）：输入数据小的变化会带来树结构的变化

Bagging

&随机森林当特征数目相对样本数目太多时，容易过拟合决策树模型的缺点DecisionTreeClassifier决策树算法特有的参数：criterion、splitter、max_features

max_depth、max_leaf_nodes

min_samples_split、min_samples_leaf、min_weight_fraction_leaf、min_impurity_decrease、min_impurity_split、ccp_alphaclass

sklearn.tree.DecisionTreeClassifier(*,

criterion='gini',

splitter='best',

max_depth=None,

min_samples_split=2,

min_samples_leaf=1,

min_weight_fraction_leaf=0.0,

max_features=None,

random_state=None,

max_leaf_nodes=None,

min_impurity_decrease=0.0,

class_weight=None,

ccp_alpha=0.0)

DecisionTreeClassifier参数参数说明备注criterion权衡划分质量的指标‘gini’（默认）：Gini指数‘entropy’：熵splitter划分方式：‘best’（默认）：在特征的所有划分点中找出最优值‘random’：在一些随机划分点中找最优分裂点‘best‘适合样本量不大的时候，如果样本数据量非常大，推荐’random’

。max_features如果样本特征数不多，如小于50，用默认的“None”即可。如果特征数非常多，可以控制分裂时考虑的最大特征数，以控制决策树的生成时间。DecisionTreeClassifier参数参数说明备注max_depth树的最大深度。None（默认），在建树时不限制树的深度，直到每个叶子结点都是纯净的或叶子结点的样本数目小于min_samples_split。数据少或者特征少的时候可以默认值。如果模型样本量多，特征也多的情况下，推荐限制最大深度，具体的取值取决于数据的分布。常用的可以取值10-100之间。max_leaf_nodes最大叶子节点数目。以最好优先（best-first）的方式生成树时，用该参数限制叶子结点数目。None（默认）:不限制叶子结点数目。如果不为None，则忽略max_depth。min_samples_split对中间结点进行分裂的最小样本数。整数：样本绝对数目浮点数：样本百分比默认值为2如果样本量数量级非常大，则推荐增大该参数。如10万样本，min_samples_split=10。min_samples_leaf叶子节点包含的最小样本数。整数：样本绝对数目浮点数：样本百分比默认值为1如果某叶子节点数目小于该参数，则会和兄弟节点一起被剪枝。min_samples_split约为min_samples_leaf的2倍。DecisionTreeClassifier参数参数说明备注min_weight_fraction_leaf叶子结点所有样本权重和的最小值。默认值为0，不考虑权重约束。当没有设置sample_weight

时，每个样本的权重相等。如果某叶子结点样本权重和小于该参数，则会和兄弟结点一起被剪枝。min_impurity_decrease结点划分最小不纯度下降量。如果结点划分带来的的不纯度下降小于这个阈值，则该结点不再划分，为叶子结点

。class_weight每个类别的权重：{class_label:weight}。如果不给定，所有类别的权重均1.“balanced”模式：自动调整权重。n_samples/(n_classes*np.bincount(y))还可以设置样本权重（fit函数）random_state随机种子ccp_alpha后剪枝中结点有效性的阈值

。Deci