1700534359
1700534360
信息论，树形数据结构，优化理论
1700534361
1700534362
问题1 决策树有哪些常用的启发函数？
1700534363
1700534364
难度：★★☆☆☆
1700534365
1700534366
我们知道，决策树的目标是从一组样本数据中，根据不同的特征和属性，建立一棵树形的分类结构。我们既希望它能拟合训练数据，达到良好的分类效果，同时又希望控制其复杂度，使得模型具有一定的泛化能力。对于一个特定的问题，决策树的选择可能有很多种。比如，在场景描述中，如果女孩把会写代码这一属性放在根结点考虑，可能只需要很简单的一个树结构就能完成分类，如图3.14所示。
1700534367
1700534368
1700534369
1700534370
1700534371
图3.14 以写代码为根节点属性的决策过程
1700534372
1700534373
从若干不同的决策树中选取最优的决策树是一个NP完全问题，在实际中我们通常会采用启发式学习的方法去构建一棵满足启发式条件的决策树。
1700534374
1700534375
常用的决策树算法有ID3、C4.5、CART，它们构建树所使用的启发式函数各是什么？除了构建准则之外，它们之间的区别与联系是什么？
1700534376
1700534377
分析与解答
1700534378
1700534379
首先，我们回顾一下这几种决策树构造时使用的准则。
1700534380
1700534381
■ ID3—— 最大信息增益
1700534382
1700534383
对于样本集合D，类别数为K，数据集D的经验熵表示为
1700534384
1700534385
1700534386
1700534387
1700534388
（3.18）
1700534389
1700534390
其中Ck是样本集合D中属于第k类的样本子集，|Ck|表示该子集的元素个数，|D|表示样本集合的元素个数。
1700534391
1700534392
然后计算某个特征A对于数据集D的经验条件熵H(D|A)为
1700534393
1700534394
1700534395
，
1700534396
1700534397
（3.19）
1700534398
1700534399
其中，Di表示D中特征A取第i个值的样本子集，Dik表示Di中属于第k类的样本子集。
1700534400
1700534401
于是信息增益g(D,A)可以表示为二者之差，可得
1700534402
1700534403
1700534404
．
1700534405
1700534406
（3.20）
1700534407
1700534408
这些定义听起来有点像绕口令，不妨我们用一个例子来简单说明下计算过程。假设共有5个人追求场景中的女孩，年龄有两个属性（老，年轻），长相有三个属性（帅，一般，丑），工资有三个属性（高，中等，低），会写代码有两个属性（会，不会），最终分类结果有两类（见，不见）。我们根据女孩有监督的主观意愿可以得到表3.1。