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。
1700534409
1700534410
表3.1 5个候选对象的属性以及女孩对应的主观意愿
1700534411
1700534412
1700534413
1700534414
年龄
1700534415
1700534416
长相
1700534417
1700534418
工资
1700534419
1700534420
写代码
1700534421
1700534422
类别
1700534423