问题一: 机器学习的基本流程( 四 ) _机器学习

一般而言，决策树的生成包含了特征选择、树的构造、树的剪枝三个过程，本节将在第一个问题中对几种常用的决策树进行对比，在第二个问题中探讨决策树不同剪枝方法之间的区别与联系.
问题1 在构建决策树过程中有哪些优化方法
我们知道，决策树的目标是从一组样本数据中，根据不同的特征和属性，建立一棵树形的分类结构.我们既希望它能拟合训练数据，达到良好的分类效果，同时又希望控制其复杂度，使得模型具有一定的泛化能力.对于一个特定的问题，决策树的选择可能有很多种.
从若干不同的决策树中选取最优的决策树是一个NP完全问题，在实际中我们通常会采用启发式学习的方法去构建一棵满足启发式条件的决策树.
常用的决策树算法有ID3、C4.5、CART，它们构建树所使用的启发式函数各是什么？除了构建准则之外，它们之间的区别与联系是什么？
分析与解答
首先，我们回顾一下这几种决策树构造时使用的准则.
■ ID3—— 最大信息增益
对于样本集合D D D, 类别数为K K K, 数据集D D D 的经验熵表示为
H ( D ) = ? ∑ k = 1 K ∣ C k ∣ ∣ D ∣ log ? 2 ∣ C k ∣ ∣ D ∣ H(D)=-\sum_{k=1}^{K} \frac{\left|C_{k}\right|}{|D|} \log _{2} \frac{\left|C_{k}\right|}{|D|} H(D)=?k=1∑K?∣D∣∣Ck?∣?log2?∣D∣∣Ck?∣?
其中C k C_{k} Ck? 是样本集合D D D 中属于第k k k 类的样本子集,∣ C k ∣ \mid C_{k}\mid ∣Ck?∣ 表示该子集的元素个数,∣ D ∣ \mid D \mid ∣D∣ 表示样本集合的元素个数.
然后计算某个特征A A A 对于数据集D D D 的经验条件樀H ( D ∣ A ) H(D \mid A) H(D∣A) 为
H ( D ∣ A ) = ∑ i = 1 n ∣ D i ∣ ∣ D ∣ H ( D i ) = ∑ i = 1 n ∣ D i ∣ ∣ D ∣ ( ? ∑ k = 1 k ∣ ∣ D i k ∣ ∣ D i ∣ log ? 2 ∣ D i k ∣ ∣ D i ∣ ) , H(D \mid A)=\sum_{i=1}^{n} \frac{\left|D_{i}\right|}{|D|} H\left(D_{i}\right)=\sum_{i=1}^{n} \frac{\left|D_{i}\right|}{|D|}\left(-\sum_{k=1}^{k} \mid \frac{\left|D_{i k}\right|}{\left|D_{i}\right|} \log _{2} \frac{\left|D_{i k}\right|}{\left|D_{i}\right|}\right), H(D∣A)=i=1∑n?∣D∣∣Di?∣?H(Di?)=i=1∑n?∣D∣∣Di?∣?(?k=1∑k?∣∣Di?∣∣Dik?∣?log2?∣Di?∣∣Dik?∣?),
其中,D i D_{i} Di? 表示D D D 中特征A A A 取第i i i 个值的样本子集,D i k D_{i k} Dik? 表示D i D_{i} Di? 中属于第k k k 类的样本子集.
于是信息增益g ( D , A ) g(D, A) g(D,A) 可以表示为二者之差, 可得
g ( D , A ) = H ( D ) ? H ( D ∣ A ) . g(D, A)=H(D)-H(D \mid A) . g(D,A)=H(D)?H(D∣A).
■ C4.5——最大信息增益比
特征A A A 对于数据集D D D 的信息增益比定义为
g R ( D , A ) = g ( D , A ) H A ( D ) , g_{R}(D, A)=\frac{g(D, A)}{H_{A}(D)}, gR?(D,A)=HA?(D)g(D,A)?,
其中
H A ( D ) = ? ∑ i = 1 n ∣ D i ∣ ∣ D ∣ log ? 2 ∣ D i ∣ ∣ D ∣ H_{A}(D)=-\sum_{i=1}^{n} \frac{\left|D_{i}\right|}{|D|} \log _{2} \frac{\left|D_{i}\right|}{|D|} HA?(D)=?i=1∑n?∣D∣∣Di?∣?log2?∣D∣∣Di?∣?
称为数据集D D D 关于A A A 的取值熵.
■ CART——最大基尼指数（Gini）
Gini描述的是数据的纯度, 与信息熵含义类似.
Gini ? ( D ) = 1 ? ∑ k = 1 n ( ∣ C k ∣ ∣ D ∣ ) 2 . \{Gini}(D)=1-\sum_{k=1}^{n}\left(\frac{\left|C_{k}\right|}{|D|}\right)^{2} . Gini(D)=1?k=1∑n?(∣D∣∣Ck?∣?)2.
CART在每一次迭代中选择基尼指数最小的特征及其对应的切分点进行分类. 但与ID3、C4.5不同的是, CART是一颗二叉树, 采用二元切割法, 每一步将数据按特征A A A 的取值切成两份, 分别进入左右子树.特征A A A 的 Gini指数定义为
Gini ? ( D ∣ A ) = ∑ i = 1 n ∣ D i ∣ ∣ D ∣ Gini ? ( D i ) . \{Gini}(D \mid A)=\sum_{i=1}^{n} \frac{\left|D_{i}\right|}{|D|} \{Gini}\left(D_{i}\right) \text {. } Gini(D∣A)=i=1∑n?∣D∣∣Di?∣?Gini(Di?).