文章目录

系列文章决策树1 决策树算法简介2 决策树分类的原理2.1 信息熵2.2 决策树划分依据—信息增益(ID3)2.3 决策树划分依据—信息增益率(C4.5)2.4 决策树划分依据—基尼值和基尼指数(CART)2.5 小结决策树各个公式各算法优缺点如何评估分割点的好坏？决策树变量的两种类型3 CART减枝3.1 为什么需要剪枝？3.2 常用的剪枝方法预剪枝后剪枝小结-预剪枝和后剪枝优缺点4 特征工程—特征提取4.1 字典特征提取4.2 文本特征提取英文文本中文文本TF-IDF5 决策树算法API6 案例：泰坦尼克号乘客生存预测6.1 案例背景6.2 代码实现7 决策树可视化8 回归决策树8.1 原理概述8.2 算法描述8.3 简单例子8.4 决策树回归与线性回归的对比

系列文章

机器学习算法 01 —— K-近邻算法(数据集划分、归一化、标准化)

机器学习算法 02 —— 线性回归算法(正规方程、梯度下降、模型保存)

机器学习算法 03 —— 逻辑回归算法(精确率和召回率、ROC曲线和AUC指标、过采样和欠采样)

机器学习算法 04 —— 决策树(ID3、C4.5、CART，剪枝，特征提取，回归决策树)

机器学习算法 05 —— 集成学习(Bagging、随机森林、Boosting、AdaBost、GBDT)

机器学习算法 06 —— 聚类算法(k-means、算法优化、特征降维、主成分分析PCA)

机器学习算法 07 —— 朴素贝叶斯算法(拉普拉斯平滑系数、商品评论情感分析案例)

机器学习算法 08 —— 支持向量机SVM算法(核函数、手写数字识别案例)

机器学习算法 09 —— EM算法(马尔科夫算法HMM前置学习，EM用硬币案例进行说明)

机器学习算法 10 —— HMM模型(马尔科夫链、前向后向算法、维特比算法解码、hmmlearn)

决策树

学习目标：

掌握决策树实现过程知道信息熵的公式以及作⽤知道信息增益、信息增益率和基尼指数的作⽤知道ID3，C4.5，Cart算法的区别了解cart剪枝的作⽤知道特征提取的作⽤应⽤DecisionTreeClassifier实现决策树分类

1 决策树算法简介

决策树思想的来源⾮常朴素，程序设计中的if-else结构就是早期决策树用来分割数据的⼀种分类学习⽅法。

是⼀种树形结构，本质是⼀颗由多个判断节点组成的树其中每个内部节点表示⼀个属性上的判断每个分⽀代表⼀个判断结果的输出最后每个叶节点代表⼀种分类结果

用一个例子来说明：

为什么这个⼥⽣把年龄放在最上⾯进行判断呢？因为女生觉得男朋友的年龄是最重要的，这是⼥⽣通过定性的主观意识做出的觉得。那么如果需要对这⼀过程进⾏量化，该如何处理呢？ 此时需要⽤到信息论中的知识：信息熵，信息增益。

2 决策树分类的原理

在说明原理前，需要先了解一些其他概念。下面的划分依据，就是从算法的角度来说明，如何选择分支节点。

2.1 信息熵

在物理学上，熵是表示”混乱“的程度。一个系统越有序，熵值越低；系统越混乱或者分散，熵值越高。

1948年，香农提出了“信息熵”的概念。“信息熵”是度量样本集合纯度最常用的一项指标。从信息完整性角度来说，当系统的有序状态一致时，数据越集中的地方，熵值越小，数据越分散的地方，熵值越大。

信息熵的计算公式：

Ent(D)=−∑k=1nCkDlog⁡2CkD=−∑k=1npklog⁡2pk=−p1log⁡2p1−p2log⁡2p2...−pnlog2pnEnt(D)=-\sum\limits_{k=1}^n \frac{C^k}{D} \log_2 \frac{C^k}{D}=-\sum\limits_{k=1}^n p_k \log_2 p_k=-p_1\log_2p_1 -p_2\log_2p_2...-p_nlog_2p_n Ent(D)=−k=1∑n​DCk​log2​DCk​=−k=1∑n​pk​log2​pk​=−p1​log2​p1​−p2​log2​p2​...−pn​log2​pn​

其中，D是样本的总数量，CkC^kCk​是第K类样本的数量，pkp_kpk​是样本集合D中第K类样本所占比例。Ent(D)越小，则D的纯度越高。

下面举两个例子：

假设现在有16个球队，每个球队获得冠军的概率相同，我们最少要猜几次才能准确猜出球队会获得冠军？

通常的做法就是用二分法，先猜冠军是否在1-8号间，如果是就继续猜是否在1-4之间，依次类推，最终只需要猜4次，那么信息熵就是4。

如果通过上面公式进行计算：Ent(D)=16⋅(−116log⁡2116)=4Ent(D)=16\cdot(-\frac{1}{16} \log_2 \frac{1}{16})=4Ent(D)=16⋅(−161​log2​161​)=4​

假设有4个篮球队，它们获胜的概率分别是{1/2, 1/4, 1/8, 1/8}，根据公式算出信息熵。

2.2 决策树划分依据—信息增益(ID3)

信息增益：以某个特征划分数据集前后熵的差值。

由于熵可以表示样本集合的不确定性，熵越大，样本的不确定性就越大。因此，我们可以通过计算以某个特征划分了数据集之前的熵和之后的熵的差值，来判断这个特征划分数据集的效果。

假设，某个特征a是离散属性，有V个可能取值：a1,a2,...,aVa^1,a^2,...,a^Va1,a2,...,aV​​​​​​，现在用特征a来进行划分，就可能产生V个分支节点，考虑到不同的分支节点的样本数不同，所以每个分支节点的权重为∣DvD∣\mid \frac{D^v}{D} \mid∣DDv​∣​。

如此信息增益的公式为：

Gain(D,a)=Ent(D)−Ent(D∣a)=Ent(D)−∑v=1VDvDEnt(Dv)Gain(D, a)=Ent(D)-Ent(D|a)=Ent(D)- \sum\limits_{v=1}^V \frac{D^v}{D} Ent(D^v) Gain(D,a)=Ent(D)−Ent(D∣a)=Ent(D)−v=1∑V​DDv​Ent(Dv)

其中，Gain(D,a)Gain(D,a)Gain(D,a)表示特征a对数据集D的信息增益，Ent(D)Ent(D)Ent(D)​表示数据集D的信息熵，Ent(D∣a)Ent(D|a)Ent(D∣a)表示给定特征a条件下D的信息条件熵，DvD^vDv​是特征a中第v个分支节点包含的样本数，Ent(Dv)Ent(D^v)Ent(Dv)​表示数据集D中第v个分支节点的样本集的信息熵。

一般而言，信息增益越大，意味着使用特征a来进行划分所获得的“纯度提升“越大，著名的ID3决策树学习算法就是用信息增益为准则的。

相信这么个公式还是很难理解，下面举个例子来帮助说明。

现在有如下特征(左图，编号、性别、活跃度、用户是否流失)，右边统计图（positive表示正样本，用户已流失，negative负样本，用户未流失）。现在我们想知道，性别和活跃度这两个特征哪个对用户流失的影响更大。

计算整体信息熵：

计算类别信息熵-性别：

计算信息增益-性别：

计算类别信息熵-活跃度：

计算信息增益-活跃度：

得出结论：活跃度的信息增益远远大于性别，说明活跃度对用户流失的影响比性别大。在做特征选择或者数据分析时，我们重点考察活跃度这个指标。

2.3 决策树划分依据—信息增益率(C4.5)

在前面一节其实我们故意忽略了”编号“这一列，如果对编号也进行计算，可以得出其信息增益为0.9182，远大于活跃度，但很显然我们划分数据集不可能选择编号。

实际上，信息增益准则对可取值数⽬较多的属性有所偏好(编号有)，为减少这种偏好可能带来的不利影响，这也是C4.5决策树算法所采取的。

信息增益率：增益率是⽤前⾯的信息增益和特征a对应的**“固有值”(intrinsic value) 的⽐值来共同定义的。

Gain_ratio(D,a)=Gain(D,a)IV(a),其中IV(a)=−∑v=1VDvDlog⁡2DvDGain\_ratio(D, a) = \frac{Gain(D,a)}{IV(a)},其中IV(a)=- \sum\limits_{v=1}^V \frac{D^v}{D} \log_2 \frac{D^v}{D} Gain_ratio(D,a)=IV(a)Gain(D,a)​,其中IV(a)=−v=1∑V​DDv​log2​DDv​

IV(a)IV(a)IV(a)也称为分裂信息度量**，是用来考虑某种属性进行分裂时分支的数量信息和尺寸信息的，我们把这些信息也称为内在信息。

由于信息增益率=信息增益/内在信息，如此属性的信息随增益率随着内在信息的增⼤⽽减⼩（也就是说，如果这个属性本身不确定性就很⼤，那我就越不倾向于选取它），这样算是对单纯⽤信息增益的补偿。

特征a的可能取值数目越多（即V越大），则IV(a)IV(a)IV(a)的值也会越大，这样信息增益率就会越小，从一定程度上减少了对可取值数目较多的属性的偏好。

使用C4.5的好处：

⽤信息增益率来选择属性：克服了⽤信息增益来选择属性时偏向选择值多的属性的不⾜。

采⽤了⼀种后剪枝⽅法：避免树的⾼度⽆节制的增⻓，避免过度拟合数据。

对于缺失值的处理：

⼀种策略是赋给它结点n所对应的训练实例中该属性的最常⻅值，另外⼀种更复杂的策略是为缺失值属性列的每个可能值赋予⼀个概率。 例如，给定⼀个布尔属性A，如果结点n包含6个已知A=1和4个A=0的实例，那么A(x)=1的概率是0.6，⽽A(x)=0的概率是0.4。于是，实例x的60%被分配到A=1的分⽀，40%被分配到另⼀个分⽀。 C4.5就是采取这种方式。

回到上一节的例子，我们之前的流程是：

计算类别信息熵计算性别属性的信息熵(性别、活跃度)计算活跃度的信息增益(性别、活跃度)

现在新增一个步骤，计算信息增益率。

计算分裂信息度量，即IV(a)IV(a)IV(a)。

计算信息增益率

得出结论：活跃度的信息增益率更⾼⼀些，所以在构建决策树的时候，优先选择。通过这种⽅式，在选取节点的过程中，我们可以降低取值较多的属性的选取偏好。

如果对此还有点模糊，可以看下面第二个例子。

如下图，第⼀列为天⽓，第⼆列为温度，第三列为湿度，第四列为⻛速，最后⼀列该活动是否进⾏。 我们要解决：根据下⾯表格数据，判断在对应天⽓下，活动是否会进⾏？

将上面的各个特征属性进行整理，属性集合A={ 天⽓，温度，湿度，⻛速}， 类别标签有两个，类别集合L={进⾏，取消}。

现在，按照步骤进行计算信息增益率。

计算类别(整体)信息熵：类别信息熵表示的是所有样本中各种类别出现的不确定性之和。根据熵的概念，熵越⼤，不确定性就越⼤，把事情搞清楚所需要的信息量就越多。

计算各个属性的信息熵：每个属性的信息熵相当于⼀种条件熵。表示的是在某种属性的条件下，各种类别出现的不确定性之和。属性的信息熵越⼤，表示这个属性中拥有的样本类别越不“纯”。

计算信息增益：信息增益 = 熵 - 条件熵，在这⾥就是 类别信息熵 - 属性信息熵。它表示的是信息不确定性减少的程度。如果⼀个属性的信息增益越⼤，就表示⽤这个属性进⾏样本划分可以更好的减少划分后样本的不确定性，选择该属性就可以更快更好地完成我们的分类⽬标。信息增益就是ID3算法的特征选择指标。【如果现在这个例子也有编号列，1-14，对其计算的信息增益为0.940，依然会有问题】

计算分裂信息度量：

计算信息增益率：【如果这个例子有编号列，1-14，对其计算的信息增益率为0.940log⁡214≈0.247\frac{0.940}{\log_214} \approx 0.247log2​140.940​≈0.247】

得出结论：天⽓的信息增益率最⾼，选择天⽓为分裂属性。发现分裂了之后，天⽓是“阴”的条件下，全是”进行“（这就叫"纯"），所以把它定义为叶⼦节点，选择不“纯”的结点继续分裂。在剩余的⼦结点当中重复过程1~5，直到所有的叶⼦结点⾜够"纯"。

while(当前节点"不纯")：1.计算当前节点的类别熵(以类别取值计算) 2.计算当前阶段的属性熵(按照属性取值吓得类别取值计算) 3.计算信息增益 4.计算各个属性的分裂信息度量 5.计算各个属性的信息增益率 end while 当前阶段设置为叶⼦节点

2.4 决策树划分依据—基尼值和基尼指数(CART)

CART决策树使用基尼指数来划分属性，数据集 D 的纯度可用基尼值来度量。

CART是Classification and Regression Tree的简称，这是⼀种著名的决策树学习算法，分类和回归任务都可⽤ 。

从数据集D中随机抽取两个样本，基尼值Gini(D)Gini(D)Gini(D)就是两个样本中类别标记不⼀致的概率。因此，基尼值越⼩，数据集D的纯度越⾼。

Gini(D)=∑k=1∣y∣∑k′≠kpkpk′=1−∑k=1∣y∣pk2Gini(D)= \sum\limits_{k=1}^{|y|} \sum\limits_{k'\neq k}p_kp_{k'}=1 - \sum\limits_{k=1}^{|y|}p^2_k Gini(D)=k=1∑∣y∣​k′​=k∑​pk​pk′​=1−k=1∑∣y∣​pk2​

其中，pk=DkDp_k=\frac{D^k}{D}pk​=DDk​，DDD表示样本的总数量，DkD^kDk表示第k类样本的数量。

通常，我们是利用基尼值来计算基尼指数Gini_index(x)Gini\_index(x)Gini_index(x)，然后根据基尼指数来划分数据集。

Gini_index(D,a)=∑k=1kDkDGini(Dk)Gini\_index(D,a)=\sum\limits_{k=1}^k \frac{D^k}{D} Gini(D^k) Gini_index(D,a)=k=1∑k​DDk​Gini(Dk)

下面，我们还是通过一个例子来说明计算过程。有下面一张表，分别计算三个特征(是否有房、婚姻状况、年收入)的基尼指数。

流程如下：

while(当前节点"不纯")：1.遍历每个变量的每⼀种分割⽅式，找到最好的分割点2.分割成两个节点N1和N2end while 每个节点⾜够“纯”为⽌

把数据集分为两类，这个例子是根据【是否拖欠贷款】来划分的。

计算是否有房的基尼指数：

计算婚姻状况的基尼指数：

由于基尼值是两个类别，而婚姻状况这里有三个类别，因此我们把婚姻状况特殊处理一下。将其分为三种，{(已婚，其他)，(单身，其他)，(离婚，其他)}，分别计算它们的基尼指数，然后取基尼指数最小的那类作为婚姻状况的基尼指数。即，选(已婚，其他)。

计算年收入基尼指数：

由于年收入是一个数值类型，不是离散属性，因此也需要特殊处理一下。⾸先对年收入按升序排序，然后从⼩到⼤依次⽤相邻值的中间值作为分隔将样本划分为两组。例如当⾯对年收⼊为60和70这两个值时，我们算得其中间值为65，以中间值65作为分割点求出基尼指数。最后，选择这些中间值中基尼指数最小的，作为年收入的基尼指数。即，选0.3。

婚姻状况和年收入的基尼指数都是0.3，先选第一个计算的就行，即用<婚姻状况>作为决策树根节点。

接下来重复上述步骤，重新对是否有房、年收入计算基尼指数。（注意：因为婚姻状况已经作为根节点，所以已婚和其他就把树划分了，从而我们重新计算时就去掉已婚的那四行数据）

第二次计算，是否有房的基尼指数：

第二次计算，年收入的基尼指数：

最终构造出决策树如下：

2.5 小结

决策树各个公式

信息熵

Ent(D)=−∑k−1npklog⁡2pkEnt(D)=-\sum\limits_{k-1}^n p_k \log_2 p_k Ent(D)=−k−1∑n​pk​log2​pk​

信息增益—ID3决策树

Gain(D,a)=Ent(D)−Ent(D∣a)=Ent(D)−∑v=1VDvDEnt(Dv)Gain(D,a)=Ent(D)-Ent(D|a)=Ent(D)-\sum\limits_{v=1}^V \frac{D^v}{D} Ent(D^v) Gain(D,a)=Ent(D)−Ent(D∣a)=Ent(D)−v=1∑V​DDv​Ent(Dv)

信息增益率—C4.5决策树

Gain_index=(D,a)=Gain(D,a)IV(a)Gain\_index=(D,a) = \frac{Gain(D,a)}{IV(a)} Gain_index=(D,a)=IV(a)Gain(D,a)​

基尼值

Gini(D)=∑k=1∣y∣∑k′≠kpkpk′=1−∑k=1∣y∣pk2Gini(D)= \sum\limits_{k=1}^{|y|} \sum\limits_{k'\neq k}p_kp_{k'}=1 - \sum\limits_{k=1}^{|y|}p^2_k Gini(D)=k=1∑∣y∣​k′​=k∑​pk​pk′​=1−k=1∑∣y∣​pk2​

基尼指数—CART决策树

Gini_index(D,a)=∑v=1VDvDGini(Dv)Gini\_index(D,a)=\sum\limits_{v=1}^V \frac{D^v}{D} Gini(D^v) Gini_index(D,a)=v=1∑V​DDv​Gini(Dv)

各算法优缺点

ID3:

ID3算法在选择根节点和各内部节点中的分⽀属性时，采⽤信息增益作为评价标准。信息增益的缺点是倾向于选择取值较多的属性，在有些情况下这类属性可能不会提供太多有价值的信息.

ID3算法只能对描述属性为离散型属性的数据集构造决策树。

C4.5：

产⽣的分类规则易于理解，准确率较⾼。

在构造树的过程中，需要对数据集进⾏多次的顺序扫描和排序，因⽽导致算法的低效。

此外，C4.5只适合于能够驻留于内存的数据集，当训练集⼤得⽆法在内存容纳时程序⽆法运⾏。

CART:

CART算法相⽐C4.5算法的分类⽅法，采⽤了简化的⼆叉树模型，同时特征选择采⽤了近似的基尼系数来简化计算。C4.5不⼀定是⼆叉树，但CART⼀定是⼆叉树。

什么是多变量决策树？

⽆论是ID3, C4.5还是CART,在做特征选择的时候都是选择最优的⼀个特征来做分类决策，但是⼤多数，分类决策不应该是由某⼀个特征决定的，⽽是应该由⼀组特征决定的。这样决策得到的决策树更加准确。这个决策树叫做多变量决策树(multi-variate decision tree)。在选择最优特征的时候，多变量决策树不是选择某⼀个最优特征，⽽是选择最优的⼀个特征线性组合来做决策。这个算法的代表是OC1，这⾥不多介绍。

如果样本发⽣⼀点点的改动，就会导致树结构的剧烈改变。这个可以通过集成学习⾥⾯的随机森林之类的⽅法解决。

如何评估分割点的好坏？

如果⼀个分割点可以将当前的所有节点分为两类，使得每⼀类都很“纯”，也就是同⼀类的记录较多，那么就是⼀个好分割点。

⽐如上一节的例⼦，“拥有房产”，可以将记录分成了两类，“是”的节点全部都没有拖欠贷款，⾮常“纯”；而“否”的节点，可以偿还贷款和⽆法偿还贷款的⼈都有，不是很“纯”，但是两个节点加起来的纯度之和与原始节点的纯度之差最⼤，所以按照这种⽅法分割。

构建决策树采⽤贪⼼算法，只考虑当前纯度差最⼤的情况作为分割点。

决策树变量的两种类型

数字型（Numeric）：变量类型是整数或浮点数，如前⾯例⼦中的“年收⼊”。⽤“>=”，“>”,“<”或“<=”作为分割条件（排序后，利⽤已有的分割情况，可以优化分割算法的时间复杂度）。

名称型（Nominal）：类似编程语⾔中的枚举类型，变量只能从有限的选项中选取，⽐如前⾯例⼦中的“婚姻情况”，只能是“单身”，“已婚”或“离婚”，使⽤“=”来分割。

3 CART减枝

3.1 为什么需要剪枝？

请看下图，随着决策树的增长，在训练集上的预测进度是单调上升的，然而在测试上的精度是先上升后下降。

为什么会出现这样的现象(这种现象也叫过拟合)？

存在噪声、样本冲突，即有错误的样本数据特征(或者叫属性)并不能完全作为分类标准巧合的规律性，数据量不够大

剪枝(pruning)是决策树中解决"过拟合"的主要手段。

在决策树学习中，为了尽可能正确分类训练样本，结点划分过程将不断重复，有时会造成决策树分⽀过多，这时就可能因训练样本学得"太好"了，以致于把训练集⾃身的⼀些特点当作所有数据都具有的⼀般性质⽽导致过拟合。因此，可通过主动去掉⼀些分⽀来降低过拟合的⻛险。

3.2 常用的剪枝方法

决策树剪枝的基本策略有"预剪枝" (pre-pruning)和"后剪枝"(post- pruning) 。

预剪枝是指在决策树⽣成过程中，对每个结点在划分前先进⾏估计，若当前结点的划分不能带来决策树泛化性能提升，则停⽌划分并将当前结点标记为叶结点。

后剪枝则是先从训练集⽣成⼀棵完整的决策树，然后⾃底向上地对⾮叶结点进⾏考察，若将该结点对应的⼦树替换为叶结点能带来决策树泛化性能提升，则将该⼦树替换为叶结点。

下面我们用周志华老师的《机器学习》书中案例进行说明。下图的将上面部分作为训练集，下面部分作为测试集，按照ID3进行属性划分选择，生成决策树。

预剪枝

⾸先，基于信息增益准则，我们会选取属性"脐部"来对训练集进⾏划分，并产⽣ 3 个分⽀，如下图所示。然⽽，是否应该进⾏这个划分呢？预剪枝要对划分前后的泛化性能进⾏估计。

在划分之前，所有样例集中在根结点。若不进⾏划分，该结点将被标记为叶结点，其类别标记为训练样例数最多的类别，假设我们将这个叶结点标记为"好⽠"。⽤前⾯表的测试集对这个单结点决策树进⾏评估。则编号为 {4，5，8} 的样例被分类正确。另外 4个样例分类错误，于是测试集精度为37∗100%=42.9%\frac{3}{7} ∗ 100\% = 42.9\%73​∗100%=42.9%在⽤属性"脐部"划分之后，上图中的结点2、3、4分别包含编号为 {1，2，3， 14}、 {6，7， 15， 17}、 {10， 16} 的训练样例，因此这 3 个结点分别被标记为叶结点"好⽠"、 “好⽠”、 “坏⽠”。此时，测试集中编号为 {4， 5， 8，11， 12} 的样例被分类正确，测试集精度为57∗100%=71.4%>42.9%\frac{5}{7} ∗ 100\% = 71.4\% > 42.9\%75​∗100%=71.4%>42.9%。于是，⽤"脐部"进⾏划分得以确定。然后，决策树算法应该对结点2进⾏划分，基于信息增益准则将挑选出划分属性"⾊泽"。然⽽，在使⽤"⾊泽"划分后，编号为 {5} 的测试集样本分类结果会由正确转为错误，使得测试集精度下降为 57.1%。于是，预剪枝策略将禁 ⽌结点2被划分。对结点3，最优划分属性为"根蒂"，划分后测试集精度仍为 71.4%. 这个 划分不能提升测试集精度，于是，预剪枝策略禁⽌结点3被划分。对结点4，其所含训练样例⼰属于同⼀类，不再进⾏划分。

于是，基于预剪枝策略从上表数据所⽣成的决策树如上图所示，其测试集精度为 71.4%。这是⼀棵仅有⼀层划分的决策树，亦称"决策树桩" (decision stump).

后剪枝

后剪枝先从训练集⽣成⼀棵完整决策树，继续使⽤上⾯的案例，从前⾯计算，我们知前⾯构造的决策树的测试集精度为42.9%。

后剪枝⾸先考察结点6，若将其领衔的分⽀剪除则相当于把6替换为叶结点。替换后的叶结点包含编号为 {7， 15} 的训练样本，于是该叶结点的类别标记为"好⽠"，此时决策树的测试集精度提⾼⾄ 57.1%。于是，后剪枝策略决定剪枝，如下图所示。

然后考察结点5，若将其领衔的⼦树替换为叶结点，则替换后的叶结点包含编号为 {6，7，15}的训练样例，叶结点类别标记为"好⽠’，此时决策树测试集精度仍为 57.1%。于是，可以不进⾏剪枝。

对结点2，若将其领衔的⼦树替换为叶结点，则替换后的叶结点包含编号 为 {1， 2， 3， 14} 的训练样例，叶结点标记为"好⽠"此时决策树的测试集精度提⾼⾄ 71.4%. 于是，后剪枝策略决定剪枝。

对结点3和1，若将其领衔的⼦树替换为叶结点，则所得决策树的测试集 精度分别为 71.4% 与 42.9%，均未得到提⾼，于是它们被保留。

最终，基于后剪枝策略所⽣成的决策树就如上图所示，其测试集精度为 71.4%。

小结-预剪枝和后剪枝优缺点

预剪枝的剪枝方案：限制节点最⼩样本数、指定数据⾼度、指定熵值的最⼩值。

后剪枝决策树通常⽐预剪枝决策树保留了更多的分⽀。

⼀般情形下，后剪枝决策树的⽋拟合⻛险很⼩，泛化性能往往优于预剪枝决策树。

但后剪枝过程是在⽣成完全决策树之后进⾏的。 并且要⾃底向上地对树中的所有⾮叶结点进⾏逐⼀考察，因此其训练时间开销⽐未剪枝决策树和预剪枝决策树都要⼤得多。

4 特征工程—特征提取

在前面几篇博客中，用到的特征工程 特征预处理部分都是用的归一化、标准化，在决策树就是特征提取。

为了便于计算机理解数据，我们通常会进行特征提取，例如下面图片就是将一段文本转换为数字。

特征提取就是将任意数据（例如文本、图像）转换为可用于机器学习的数字特征，大致可以分为三类：

字典特征提取文本特征提取图像特征提取（深度学习中会介绍）

4.1 字典特征提取

对字典数据进行特征值化，通常是将其转换为One-Hot编码。（没错，就是Pandas里提到的）

先调用sklearn.feature_extraction.DictVectorizer(sparse=True,…)，用于实例化对象。其中sparse表示是否用稀疏矩阵。再利用实例化的对象调用fit_transform(X)，X就是传入的字典数据。可通过实例化的对象获取特征名称get_feature_names()

光说无益，看代码和结果来理解。

from sklearn.feature_extraction import DictVectorizerdef dictionary_demo():# 1. 获取字典数据data = [{'city': '北京', 'temperature': 100},{'city': '上海', 'temperature': 60},{'city': '深圳', 'temperature': 30}]# 2. 实例化转换器对象transfer = DictVectorizer(sparse=False)# 3. 开始转换，使用 One-Hot编码new_data = transfer.fit_transform(data)# 4. 查看数据# 4.1 打印特征名称print("特征名称：\n", transfer.get_feature_names())# 4.2 打印提取的数据print("One-Hot编码\n", new_data)if __name__ == '__main__':dictionary_demo()

sparse=False的结果：

sparse=True的结果：

sparse=True可以节约空间。假设有100行100列，但实际上One-Hot编码后，每一行只有一个1，其余都是0。这样很浪费空间，所以以坐标形式存储。

4.2 文本特征提取

英文文本

先调用sklearn.feature_extraction.text.CountVectorizer(stop_words=[])获取转换器对象，其中stop_words表示停用词，即不会被统计的词。

再调用fit_transform(data)开始提取，data是英文文本数据。返回的是英文单词的词频统计，不是one-hot编码。

可调用转换器对象的get_feature_names()方法，获取单词列表。

from sklearn.feature_extraction.text import CountVectorizerdef english_count_demo():"""英文文本特征提取:return:"""# 1. 获取文本数据data = ["life is short,i like python","life is too long,i dislike python"]# 2. 实例化转换器对象transfer = CountVectorizer() # 注意 没有sparse参数# 3. 开始转换，得到单词频率统计new_data = transfer.fit_transform(data)# 4. 查看数据# 4.1 打印特征名称print("特征名称：\n", transfer.get_feature_names())# 4.2 打印提取的数据print("频率统计(数组版)\n", new_data.toarray())print("频率统计(稀疏矩阵版)\n", new_data) # 直接就是sparse的结果if __name__ == '__main__':english_demo()

中文文本

实际上CountVectorizer()统计的原理是依据空格来划分，英文的每个单词都有空格分隔，但中文显然不是。所以我们需要先用一个库jieba对中文文本进行空格分词。

from sklearn.feature_extraction.text import CountVectorizerimport jiebadef cut_word(text):"""中文分词:param text:字符串文本，例如"我爱北京天安门":return: 空格分隔的字符串，例如"我 爱 北京 天安门""""# jieba.cut() 返回一个对象# list() 将对象转为一个字符串数组，例如["我", "爱", "北京", "天安门"]# " ".join() 将字符串数组用空格拼接，例如 "我 爱 北京 天安门"text = " ".join(list(jieba.cut(text))) # 默认cut(cut_all=False)，False表示精确模式，适合文本分析；True可以成词的词语都扫描出来，速度快，但是不能解决歧义。return textdef chinese_count_demo():"""中文文本特征提取:return:"""# 1. 获取文本数据data = ["⼀种还是⼀种今天很残酷，明天更残酷，后天很美好，但绝对⼤部分是死在明天晚上，所以每个⼈不要放弃今天。","我们看到的从很远星系来的光是在⼏百万年之前发出的，这样当我们看到宇宙时，我们是在看它的过去。"]# 2. 实例化转换器对象transfer = CountVectorizer() # 注意 没有sparse参数# 3. 开始转换，得到单词频率统计list = []for str in data:list.append(cut_word(str))new_data = transfer.fit_transform(list)# 4. 查看数据# 4.1 打印特征名称print("特征名称：\n", transfer.get_feature_names())# 4.2 打印提取的数据print("频率统计(数组版)\n", new_data.toarray())# print("频率统计(稀疏矩阵版)\n", new_data) # 直接就是sparse的结果if __name__ == '__main__':chinese_demo()

效果如下：

TF-IDF

前面无论是英文文本还是中文文本，都是利用CountVectorizer()来统计词频，显然只是得到词频还不足以用来分类，一个词并不能直接划分一个文章类型，那么该如何处理呢？

TF-IDF的主要思想是：如果某个词或短语在一篇文章中出现的概率高，且在其他文章中出现概率低，就认为这个词或短语可以用来分类文章。

词频(TF，Term Frequency)：指一个词语在这篇文章中出现的频率。假如一篇文章中共有100个词，词语"喜欢"出现了5词，那么”喜欢“的词频就是5/100=0.05。

逆向文档频率(IDF，Inverse Document Frequency)：是一个词语普遍重要性的度量，其值等于文章总数除以这个词在多少篇文章里出现过的次数，再取以10为底的对数。假如现在有10,000,000篇文章，其中10000里出现过“喜欢”这个词，那么IDF=lg⁡10,000,00010000=3IDF=\lg\frac{10,000,000}{10000}=3IDF=lg1000010,000,000​=3

公式：TF−IDF=TF⋅IDFTF-IDF=TF \cdot IDFTF−IDF=TF⋅IDF，所以“喜欢”对于这篇文章的TF-IDF的分数为0.05⋅3=0.150.05 \cdot 3=0.150.05⋅3=0.15

根据，TF-IDF分数，我们可以判断这个词对于一篇文章的重要程度。

API用法和CountVectorizer(stop_words=[])一样，换成TfidfVectorizer(stop_words=[])就行。

from sklearn.feature_extraction.text import TfidfVectorizerimport jiebadef cut_word(text):"""中文分词:param text:字符串文本，例如"我爱北京天安门":return: 空格分隔的字符串，例如"我 爱 北京 天安门""""# jieba.cut() 返回一个对象# list() 将对象转为一个字符串数组，例如["我", "爱", "北京", "天安门"]# " ".join() 将字符串数组用空格拼接，例如 "我 爱 北京 天安门"text = " ".join(list(jieba.cut(text)))return textdef chinese_tfidf_demo():"""中文文本特征提取:return:"""# 1. 获取文本数据data = ["⼈⽣苦短，我喜欢Python", "⽣活很慢，我不喜欢Python"]# 2. 实例化转换器对象transfer = TfidfVectorizer() # 可以用stop_words不统计某些词# 3. 开始转换，得到单词频率统计list = []for str in data:list.append(cut_word(str))new_data = transfer.fit_transform(list)# 4. 查看数据# 4.1 打印特征名称print("特征名称：\n", transfer.get_feature_names())# 4.2 打印提取的数据print("TF-IDF(数组版)\n", new_data.toarray())if __name__ == '__main__':chinese_tfidf_demo()

结果：

5 决策树算法API

sklearn.tree.DecisionTreeClassifier(criterion=’gini’, max_depth=None,random_state=None)

criterion：决策树划分依据的选择。可选"gini"即基尼指数(默认)，或者"entropy"即信息增益。

min_samples_split：内部节点在划分所需要的最小样本数。

这个值限制了⼦树继续划分的条件，如果某节点的样本数少于min_samples_split，则不会继续再尝试选择 最优特征来进⾏划分。 默认是2。如果样本量不⼤，不需要管这个值。如果样本量数量级⾮常⼤，则推荐增⼤这个值。(大概10万的样本，设置个10就差不多了)

min_samples_leaf：叶子节点最少样本数

这个值限制了叶⼦节点最少的样本数，如果某叶⼦节点数⽬⼩于样本数，则会和兄弟节点⼀起被剪枝。默认是1，可以输⼊最少的样本数的整数，或者最少样本数占样本总数的百分⽐。如果样本量不⼤，不需要管这个值。如果样本量数量级⾮常⼤，则推荐增⼤这个值。(大概10万的样本，设置个5就差不多了)

max_depth：决策树最大深度

决策树的最⼤深度，默认可以不输⼊，如果不输⼊的话，决策树在建⽴⼦树的时候不会限制⼦树的深度。⼀般来说，数据少或者特征少的时候可以不管这个值。如果模型样本量多，特征也多的情况下，推荐限制这个最⼤深度，具体的取值取决于数据的分布。常⽤的可以取值10-100之间。

random_state：随机数种子

6 案例：泰坦尼克号乘客生存预测

6.1 案例背景

泰坦尼克号沉没是历史上最臭名昭着的沉船之⼀。194⽉15⽇，在她的处⼥航中，泰坦尼克号在与冰⼭相撞后沉没，在2224名乘客和机组⼈员中造成1502⼈死亡。这场耸⼈听闻的悲剧震惊了国际社会，并为船舶制定了更好的安全规定。造成海难失事的原因之⼀是乘客和机组⼈员没有⾜够的救⽣艇。尽管幸存下沉有⼀些运⽓因素，但有些⼈⽐其他⼈更容易⽣存，例如妇⼥，⼉童和上流社会。 在这个案例中，我们要求您完成对哪些⼈可能存活的分析。特别是，我们要求您运⽤机器学习⼯具来预测哪些乘客幸免于悲剧。

案例来自Kaggle：/c/titanic/overview

数据集下载：/download/qq_39763246/21108566

6.2 代码实现

机器学习流程：

获取数据数据处理特征工程机器学习模型评估

下面按照流程逐一实现。

获取数据：同时发现Age中存在数据缺失

import pandas as pdimport numpy as npfrom sklearn.model_selection import train_test_splitfrom sklearn.feature_extraction import DictVectorizerfrom sklearn.tree import DecisionTreeClassifier, export_graphviz# 1. 获取数据titanic = pd.read_csv("./data/titanic_train.csv")

数据基本处理：确定特征值和目标值、缺失值处理、数据集划分

# 2. 数据基本处理# 2.1 确定特征值和目标值x = titanic[["Pclass", "Age", "Sex"]] # 楼层、年龄、性别（不是总说女人和小孩先走么）y = titanic["Survived"] # 是否生还# 2.2 缺失值处理x["Age"].fillna(x["Age"].mean(), inplace=True) # 发现Age里有大量缺失值，所以不能删除NaN，而是用平均值替换# 2.3 数据集划分x_train, x_test, y_train, y_test = train_test_split(x, y, test_size=0.2, random_state=22)

特征工程：这里是对进行字典提取

# 3. 特征工程 - 特征提取 字典提取(one-hot编码)# 把数据x、y转换成字典数据 x.to_dict(orient="records")，才能提取 # [{"Pclass": "1", "Age": 29.00, "Sex": "female"}]transfer = DictVectorizer(sparse=False) x_train = transfer.fit_transform(x_train.to_dict(orient="records"))x_test = transfer.fit_transform(x_test.to_dict(orient="records"))

机器学习

# 4. 机器学习 - 决策树# 4.1 生成估计器对象estimator = DecisionTreeClassifier()# 4.2 模型训练estimator.fit(x_train, y_train)

模型评估

# 5. 模型评估print("精确度：", estimator.score(x_test, y_test))print("预测值：\n", estimator.predict(x_test))

7 决策树可视化

导入模块from sklearn.tree import export_graphviz执行tree.export_graphviz(estimator,out_file='tree.dot’,feature_names=[‘’,’’])，其中feature_names是特征名称，我们特征取到不同的值也要传进去。将生成的文件tree.dot里的内容粘贴到网站/里

下面进行演示：

import pandas as pdimport numpy as npfrom sklearn.model_selection import train_test_splitfrom sklearn.feature_extraction import DictVectorizerfrom sklearn.tree import DecisionTreeClassifier, export_graphviz# 1. 获取数据titanic = pd.read_csv("./data/titanic_train.csv")# 2. 数据基本处理x = titanic[["Pclass", "Age", "Sex"]]y = titanic["Survived"] x["Age"].fillna(x["Age"].mean(), inplace=True)x_train, x_test, y_train, y_test = train_test_split(x, y, test_size=0.2, random_state=22)# 3. 特征工程 - 特征提取 字典提取(one-hot编码)transfer = DictVectorizer(sparse=False) x_train = transfer.fit_transform(x_train.to_dict(orient="records"))x_test = transfer.fit_transform(x_test.to_dict(orient="records"))# 4. 机器学习 - 决策树estimator = DecisionTreeClassifier(max_depth=6)estimator.fit(x_train, y_train)# 5. 决策树可视化export_graphviz(estimator, "./data/tree.dot", feature_names=['Age','Pclass', 'Sex=male','Sex=female'])

文件内容如下：

将内容复制粘贴到网站，生成的决策树如下：

8 回归决策树

该小结参考自CSDN：/Albert05/article/details/81865261

之前我们曾提到过，数据类型可以分为两类：连续型数据和离散型数据(例如特征性别，可取值是男和女，正是如此，特征工程才是特征提取，而不是标准化)。面对不同类型的数据时，决策树也会分为两类：

分类决策树和回归决策树前者主要用于处理离散型数据，后者主要用于处理连续型数据。

所谓回归，就是根据特征向量来决定对应的输出值。回归树就是将特征空间划分成若干单元，每一个划分单元有一个特定的输出。因为每个结点都是“是”和“否”的判断，所以划分的边界是平行于坐标轴的。对于测试数据，我们只要按照特征将其归到某个单元，便得到对应的输出值。

举个例子，左边为对二维平面划分的决策树，右边为对应的划分示意图，其中c1,c2,c3,c4,c5是对应每个划分单元的输出。

如现在对一个新的向量(6,6)决定它对应的输出。第一维分量6介于5和8之间，第二维分量6小于8，根据此决策树很容易判断(6,6)所在的划分单元，其对应的输出值为c3.

8.1 原理概述

不管是回归决策树还是分类决策树，都会存在两个核⼼问题：

如何选择划分点？

如何决定叶节点的输出值？

假如我们有n个特征，每个特征有si(i∈(1,n))s_i(i \in (1, n))si​(i∈(1,n))个取值，那我们遍历所有特征， 尝试该特征所有取值，对空间进⾏划分，直到取到特征j的取值s，使得损失函数最⼩，这样就得到了⼀个划分点。用公式来描述就是：

minj,s[minc1Loss(yi,c1)+minc2Loss(yi,c2)]min_{j,s}[min_{c_1} Loss(y_i, c_1) + min_{c_2} Loss(y_i, c_2)] minj,s​[minc1​​Loss(yi​,c1​)+minc2​​Loss(yi​,c2​)]

其中，Loss(yi,c1)Loss(y_i, c_1)Loss(yi​,c1​)表示损失函数。

假如将输入空间划分为M个单元(R1,R2...RmR_1,R_2...R_mR1​,R2​...Rm​)，那么每个区域的输出值就是cm=avg(yi∣xi∈Rm)c_m=avg(y_i|x_i \in R_m)cm​=avg(yi​∣xi​∈Rm​)，也就是该区域内所有点y值的平均数。

这句话可能不好理解，我们举个例子。

如下图所示，假如我们想要对楼内居民的年龄进行回归，我们将楼划分为3个区域(R1,R2,R3R_1,R_2,R_3R1​,R2​,R3​)。

区域R1R_1R1​的输出c1c_1c1​就是第一列四个居民的年龄的平均值。区域R2R_2R2​的输出c2c_2c2​就是第二列四个居民年龄的平均值。区域R3R_3R3​的输出c3c_3c3​就是第三四列八个居民年龄的平均值。

8.2 算法描述

输入：训练集D

输出：回归决策树f(x)f(x)f(x)

在训练数据集所在的输入空间中，递归的将每个区域划分为两个子区域并决定每个子区域上的输出值，构建二叉决策树。

选择最优切分特征j与切分点s，求解：

minj,s[minc1∑xi∈R1(j,s)(yi−c1)2+minc2∑xi∈R2(j,s)(yi−c2)2]min_{j,s}[min_{c_1} \sum\limits_{x_i \in R_1(j, s)}(y_i-c_1)^2 + min_{c_2} \sum\limits_{x_i \in R_2(j, s)}(y_i - c_2)^2] minj,s​[minc1​​xi​∈R1​(j,s)∑​(yi​−c1​)2+minc2​​xi​∈R2​(j,s)∑​(yi​−c2​)2]

遍历特征j，对固定的切分特征j扫描切分点，选择能使上式达到最小的一对(j,s)(j, s)(j,s)

根据选定的(j,s)(j,s)(j,s)划分区域，并决定相应的输出值：

R1(j,s)=x∣x(j)≤s,R2(j,s)=x∣x(j)>cm=1N∑x1∈Rm(j,s)yi,x∈Rm,m=1,2R_1(j, s)=x|x^{(j)} \le s, R_2(j,s)=x|x^{(j)} \gt \\ c_m=\frac{1}{N} \sum\limits_{x_1 \in R_m(j,s)} y_i, x \in R_m, m=1,2 R1​(j,s)=x∣x(j)≤s,R2​(j,s)=x∣x(j)>cm​=N1​x1​∈Rm​(j,s)∑​yi​,x∈Rm​,m=1,2

继续对两个子区域调用 1和2，直到满足条件。

将输入空间划分为M个区域R1,R2,...RMR_1, R_2, ... R_MR1​,R2​,...RM​，生成决策树：

f(x)=∑m=1McmI(x∈Rm)f(x)=\sum\limits_{m=1}^M c_mI(x \in R_m) f(x)=m=1∑M​cm​I(x∈Rm​)

8.3 简单例子

为了更好理解回归决策树算法，下面举个构建树的例子。

训练数据如下表。

（1）先选择最优的切分特征j与最优切分点s

在本数据集中只有一个特征x，所以最优切分特征就是x。

我们考虑9个切分点[1.5, 2.5, 3.5, 4.5, 5.5, 6.5, 7.5, 8.5, 9.5]，损失函数定义为平方损失函数Loss(y,f(x))=(f(x)−y)2Loss(y,f(x))=(f(x)-y)^2Loss(y,f(x))=(f(x)−y)2，将前面9个切分点异常带入下面公式，其中cm=avg(yi∣xi∈Rm)c_m=avg(y_i|x_i \in R_m)cm​=avg(yi​∣xi​∈Rm​)。

计算子区域输出值

例如，取s=1.5，此时R1=1,R2=2,3,4,5,6,7,8,9,10R_1=1,R_2=2,3,4,5,6,7,8,9,10R1​=1,R2​=2,3,4,5,6,7,8,9,10，这两个区域的输出值分别为：c1=5.56， c2=(5.7 + 5.91 + 6.4 + 6.8 + 7.05 + 8.9 + 8.7 + 9 + 9.05)/9=7.50。

同理，得到其他各切分点的子区域输出值，如下表：

计算损失函数，找到最优切分点

把c1，c2的值带入到平方损失函数Loss(y,f(x))=(f(x)−y)2Loss(y, f(x))=(f(x)-y)^2Loss(y,f(x))=(f(x)−y)2。

当s=1.5时，L(1.5)=(5.56−5.56)2+[(5.7−7.5)2+(5.91−7.5)2+...+(9.05−7.5)2]=15.72L(1.5)=(5.56-5.56)^2+[(5.7-7.5)^2+(5.91-7.5)^2+...+(9.05-7.5)^2]=15.72L(1.5)=(5.56−5.56)2+[(5.7−7.5)2+(5.91−7.5)2+...+(9.05−7.5)2]=15.72

同理，得到其他切分点的损失函数，如下表：

显然取s=6.5时，损失函数m(s)最小，所以第一个划分变量是(j=x,s=6.5)(j=x,s=6.5)(j=x,s=6.5)

（2）用选定的(j,s)(j,s)(j,s)划分区域，并决定输出值：

两个区域分别是：R1={1,2,3,4,5,6}，R2={7,8,9,10}R_1=\lbrace1,2,3,4,5,6\rbrace，R_2=\lbrace 7, 8, 9, 10 \rbraceR1​={1,2,3,4,5,6}，R2​={7,8,9,10}输出值cm=avg(yi∣xi∈Rm)c_m=avg(y_i|x_i \in R_m)cm​=avg(yi​∣xi​∈Rm​)，c1=6.24，c2=8.91

（3）用（1）、（2）继续划分：

​ 对R1继续划分

​ 取切分点[1.5, 2.5, 3.5, 4.5, 5.5]，则各区域的输出值cmc_mcm​如下表

​ 计算损失函数m(s)

（4）生成回归树。假设在生成三个区域后停止划分，那么最终得到的回归树形式如下：

8.4 决策树回归与线性回归的对比

# -*- coding = utf-8 -*-# @Time : /8/16 11:11 下午# @Author : zcy# @File : DecisionTreeRegressor.py# @Software : PyCharmimport numpy as npimport matplotlib.pyplot as pltfrom sklearn.tree import DecisionTreeRegressorfrom sklearn import linear_model# ⽣成数据# 不用reshape，获取的数据是从1到10的一维列表，reshape(-1,1)将其转为1到10的二维列表。（-1表示自动计算行，1表示每行仅1列）x = np.array(list(range(1, 11))).reshape(-1, 1) # 必须要二维才能进行训练y = np.array([5.56, 5.70, 5.91, 6.40, 6.80, 7.05, 8.90, 8.70, 9.00, 9.05])# 训练模型 （用三组 进行对照）model1 = DecisionTreeRegressor(max_depth=1) # 最大深度为1的回归决策树model2 = DecisionTreeRegressor(max_depth=3) # 最大深度为3的回归决策树model3 = linear_model.LinearRegression() # 线性回归model1.fit(x, y)model2.fit(x, y)model3.fit(x, y)# 模型预测# ⽣成1000个数作为测试集，⽤于预测模型X_test = np.arange(0.0, 10.0, 0.01).reshape(-1, 1) # 从0开始，到10为止，步长为0.01的二维列表。y_1 = model1.predict(X_test)y_2 = model2.predict(X_test)y_3 = model3.predict(X_test)# 结果可视化plt.figure(figsize=(10, 6), dpi=100)plt.scatter(x, y, label="data")plt.plot(X_test, y_1, label="max_depth=1")plt.plot(X_test, y_2, label="max_depth=3")plt.plot(X_test, y_3, label='liner regression')plt.xlabel("data")plt.ylabel("target")plt.title("Decision Tree Regression")plt.legend()plt.show()