1700534324
百面机器学习：算法工程师带你去面试 [:1700532186]
1700534325
百面机器学习：算法工程师带你去面试 03 决策树
1700534326
1700534327
1700534328
1700534329
场景描述
1700534330
1700534331
时间：早上八点，地点：婚介所。
1700534332
1700534333
“闺女，我又给你找了个合适的对象，今天要不要见一面？”
1700534334
1700534335
“多大？”“26岁。”
1700534336
1700534337
“长得帅吗？” “还可以，不算太帅。”
1700534338
1700534339
“工资高么？” “略高于平均水平。”
1700534340
1700534341
“会写代码吗？”“人家是程序员，代码写得棒着呢！”
1700534342
1700534343
“好，那把他联系方式发来吧，我抽空见一面。”
1700534344
1700534345
这便是中国特色相亲故事，故事中的女孩做决定的过程就是一个典型的决策树分类，如图3.13所示。通过年龄、长相、工资、是否会编程等属性对男生进行了两个类别的分类：见或不见。
1700534346
1700534347
1700534348
1700534349
1700534350
图3.13 女孩的分类决策过程
1700534351
1700534352
决策树是一种自上而下，对样本数据进行树形分类的过程，由结点和有向边组成。结点分为内部结点和叶结点，其中每个内部结点表示一个特征或属性，叶结点表示类别。从顶部根结点开始，所有样本聚在一起。经过根结点的划分，样本被分到不同的子结点中。再根据子结点的特征进一步划分，直至所有样本都被归到某一个类别（即叶结点）中。
1700534353
1700534354
决策树作为最基础、最常见的有监督学习模型，常被用于分类问题和回归问题，在市场营销和生物医药等领域尤其受欢迎，主要因为树形结构与销售、诊断等场景下的决策过程十分相似。将决策树应用集成学习的思想可以得到随机森林、梯度提升决策树等模型，这些将在第12章中详细介绍。完全生长的决策树模型具有简单直观、解释性强的特点，值得读者认真理解，这也是为融会贯通集成学习相关内容所做的铺垫。
1700534355
1700534356
一般而言，决策树的生成包含了特征选择、树的构造、树的剪枝三个过程，本节将在第一个问题中对几种常用的决策树进行对比，在第二个问题中探讨决策树不同剪枝方法之间的区别与联系。
1700534357
1700534358
知识点
1700534359
1700534360
信息论，树形数据结构，优化理论
1700534361
1700534362
问题1 决策树有哪些常用的启发函数？
1700534363
1700534364
难度：★★☆☆☆
1700534365
1700534366
我们知道，决策树的目标是从一组样本数据中，根据不同的特征和属性，建立一棵树形的分类结构。我们既希望它能拟合训练数据，达到良好的分类效果，同时又希望控制其复杂度，使得模型具有一定的泛化能力。对于一个特定的问题，决策树的选择可能有很多种。比如，在场景描述中，如果女孩把会写代码这一属性放在根结点考虑，可能只需要很简单的一个树结构就能完成分类，如图3.14所示。
1700534367
1700534368
1700534369
1700534370
1700534371
图3.14 以写代码为根节点属性的决策过程
1700534372
1700534373
从若干不同的决策树中选取最优的决策树是一个NP完全问题，在实际中我们通常会采用启发式学习的方法去构建一棵满足启发式条件的决策树。