机器学习--决策树算法

在生活中，“树”这一模型有很广泛的应用，事实证明，它在机器学习分类和回归领域也有着深刻而广泛的影响。在决策分析中，决策树可以明确直观的展现出决策结果和决策过程。如名所示，它使用树状决策模型。它不仅仅是在数据挖掘中用户获取特定目标解的策略，同时也被广泛的应用于机器学习。

如何使用树来表示算法

为此，我们考虑使用泰坦尼克号数据集的示例，以预测乘客是否会生存。下面的模型使用数据集中的3个特征/属性/列，即性别，年龄和SIBSP（配偶或儿童的数量）。这是一棵体现了人性光辉的决策树。

树的形状是一棵上下颠倒的决策树，叶子节点在下，根节点在上。在图像中，黑色中的粗体文本表示条件/内部节点，基于树分成分支/边缘。不再分裂的分支结束是决策/叶子，在这种情况下，乘客是否被死亡或幸存，分别表示为红色和绿色文本。

虽然，一个真实的数据集将有很多功能，这只是一个更大的树中的部分分支，但你不能忽略这种算法的简单性。该特征重要性是明确的，可以轻易查看决策关系。该方法更常见于来自数据的学习决策树，并且在树上被称为分类树，因为目标是将乘客分类为幸存或死亡，上面所展示的决策树就是分类树。回归树以相同的方式表示，例如用于预测房子价格的连续价值。通常，决策树算法被称为CART或分类和回归树。

那么，算法生成的背后发生了什么呢？如何生成一个决策树取决于选择什么特征和在何种情况下进行分裂，以及在什么时候停止。因为一棵树通常是随意生长的，你需要修剪它，让它看起来漂亮（研究如何生成决策树）。

ID3算法

ID3算法生成决策树

ID3算法（Iterative Dichotomiser 3）是决策树生成算法的一种，基于奥卡姆剃刀原理(简约原则)

。是Ross Quinlan发明的一种决策树算法，这个算法的基础就是上面提到的奥卡姆剃刀原理，越是小型的决策树越优于大的决策树，尽管如此，也不总是生成最小的树型结构，而是一个启发式算法。在信息论中，期望信息越小，那么信息增益

就越大，从而纯度就越高。ID3算法的核心思想就是以信息增益来度量属性的选择，选择分裂后信息增益最大的属性进行分裂（决策树分支）。该算法采用自顶向下的贪婪搜索遍历可能的决策空间。

假设你是水果商人，现在有一个客人来你的摊位购买西瓜，请你使用ID3构建一个决策树，帮助客人挑选一个好瓜。

凭借你的经验，你总结出了如下判断规律。

最大的属性进行分支

于是，我们可以得到了三个子结点，对于这三个子节点，我们可以递归的使用刚刚找信息增益最大的方法进行选择特征属性，比如：

，第一个分支结点可用属性集合

，基于

各属性的信息增益，分别求的如下：

于是我们可以选择特征属性为

三个特征属性中任选一个（因为他们三个相等并最大），其它俩个子结点同理，然后得到新一层的结点，再递归的由信息增益进行构建树即可 最终的决策树如下：

ID3算法虽然提出了新思路，但是还是有很多值得改进的地方。　　

• ID3没有考虑连续特征，比如长度，密度都是连续值，无法在ID3运用。这大大限制了ID3的用途。
• ID3采用信息增益大的特征优先建立决策树的节点。很快就被人发现，在相同条件下，取值比较多的特征比取值少的特征信息增益大。比如一个变量有2个值，各为1/2，另一个变量为3个值，各为1/3，其实他们都是完全不确定的变量，但是取3个值的比取2个值的信息增益大。如果校正这个问题呢？
• ID3算法对于缺失值的情况没有做考虑
• 没有考虑过拟合的问题

C4.5算法

使用 C4.5算法生成决策树

Ross Quinlan在C4.5算法中改进了上述4个问题。

• 对于第一个问题，不能处理连续特征， C4.5的思路是将连续的特征离散化。比如

个样本的连续特征

有

个，从小到大排列为

,则C4.5取相邻两样本值的平均数，一共取得

个划分点，其中第

个划分点

表示为：

。对于这

个点，分别计算以该点作为二元分类点时的信息增益。选择信息增益最大的点作为该连续特征的二元离散分类点。比如取到的增益最大的点为

,则小于

的值为类别

，大于

的值为类别

，这样我们就做到了连续特征的离散化。要注意的是，与离散属性不同的是，如果当前节点为连续属性，则该属性后面还可以参与子节点的产生选择过程。

• 第二个问题，信息增益作为标准容易偏向于取值较多的特征的问题。我们引入一个信息增益比

的变量，它是信息增益和特征熵的比值。特征数越多的特征对应的特征熵越大，可以校正信息增益容易偏向于取值较多的特征的问题。

• 对于第三个缺失值处理的问题，主要需要解决的是两个问题，一是在样本某些特征缺失的情况下选择划分的属性，二是选定了划分属性，对于在该属性上缺失特征的样本的处理。 对于第一个子问题，对于某一个有缺失特征值的特征

。C4.5的思路是将数据分成两部分，对每个样本设置一个权重（初始可以都为1），然后划分数据，一部分是有特征值

的数据

，另一部分是没有特征

的数据

. 然后对于没有缺失特征

的数据集

来和对应的

特征的各个特征值一起计算加权重后的信息增益比，最后乘上一个系数，这个系数是无特征

缺失的样本加权后所占加权总样本的比例。 对于第二个子问题，可以将缺失特征的样本同时划分入所有的子节点，不过将该样本的权重按各个子节点样本的数量比例来分配。比如缺失特征

的样本

之前权重为

，特征

有

个特征值

。

个特征值对应的无缺失

特征的样本个数为

.则

同时划分入

。对应权重调节为

。

• 对于第4个问题，C4.5引入了正则化系数进行初步的剪枝

客人对你挑选的西瓜很满意，这次要一次性购买多个西瓜，请你再用C4.5算法构建一个决策树帮助客人挑选西瓜

根据上面的ID3算法，我们已经求出了部分信息增益信息

参考资料

[1] Prashant Gupta. Decision Trees in Machine Learning [EB/OL] [2] scikit-learn 中文社区,决策树 [EB/OL] [3] 维基百科 ID3 算法 [EB/OL] [4] 苗煜飞,张霄宏.决策树C4.5算法的优化与应用[J].计算机工程与应用,2015,51(13):255-258+270. [5] 刘建平.决策树算法原理(上) [EB/OL] 博客园 [6] 行者.决策树--ID3 算法（一）[EB/OL] 博客园 [7] 忆臻.深入浅出理解决策树算法（二）-ID3算法与C4.5算法 [EB/OL] 知乎 [8] AI研究僧.【机器学习（三）】机器学习中：信息熵，信息增益，信息增益比，原理，案例，代码实现 [EB/OL] CSDN