分类算法之决策树(Decision tree)

左手的ㄟ右手 2021-09-13 23:24 291阅读 0赞

# 决策树引导 #

通俗来说，决策树分类的思想类似于找对象。现想象一个女孩的母亲要给这个女孩介绍男朋友，于是有了下面的对话：  
女儿：多大年纪了？

母亲：26。
    
      女儿：长的帅不帅？
    
      母亲：挺帅的。
    
      女儿：收入高不？
    
      母亲：不算很高，中等情况。
    
      女儿：是公务员不？
    
      母亲：是，在税务局上班呢。
    
      女儿：那好，我去见见。

这个女孩的决策过程就是典型的分类树决策。相当于通过年龄、长相、收入和是否公务员对将男人分为两个类别：见和不见。假设这个女孩对男人的要求是：30岁以下、长相中等以上并且是高收入者或中等以上收入的公务员，那么这个可以用下图表示女孩的决策逻辑（声明：此决策树纯属为了写文章而YY的产物，没有任何根据，也不代表任何女孩的择偶倾向，请各位女同胞莫质问我^\_^）：

![这里写图片描述][SouthEast]

上图完整表达了这个女孩决定是否见一个约会对象的策略，其中绿色节点表示判断条件，橙色节点表示决策结果，箭头表示在一个判断条件在不同情况下的决策路径，图中红色箭头表示了上面例子中女孩的决策过程。

这幅图基本可以算是一颗决策树，说它“基本可以算”是因为图中的判定条件没有量化，如收入高中低等等，还不能算是严格意义上的决策树，如果将所有条件量化，则就变成真正的决策树了。

有了上面直观的认识，我们可以正式定义决策树了：

**决策树（decision tree）是一个树结构（可以是二叉树或非二叉树）。其每个非叶节点表示一个特征属性上的测试，每个分支代表这个特征属性在某个值域上的输出，而每个叶节点存放一个类别。使用决策树进行决策的过程就是从根节点开始，测试待分类项中相应的特征属性，并按照其值选择输出分支，直到到达叶子节点，将叶子节点存放的类别作为决策结果。**

可以看到，决策树的决策过程非常直观，容易被人理解。目前决策树已经成功运用于医学、制造产业、天文学、分支生物学以及商业等诸多领域。知道了决策树的定义以及其应用方法，下面介绍决策树的构造算法。

--------------------

# 决策树的构造 #

不同于贝叶斯算法，决策树的构造过程不依赖领域知识，它使用属性选择度量来选择将元组最好地划分成不同的类的属性。所谓**决策树的构造**就是进行属性选择度量确定各个特征属性之间的拓扑结构。

**分裂属性分为三种不同的情况：**

1、属性是离散值且不要求生成二叉决策树。此时用属性的每一个划分作为一个分支。  
2、属性是离散值且要求生成二叉决策树。此时使用属性划分的一个子集进行测试，按照“属于此子集”和“不属于此子集”分成两个分支。  
3、属性是连续值。此时确定一个值作为分裂点split\_point，按照>split\_point和<=split\_point生成两个分支。

**构造决策树的关键性内容是进行属性选择度量**，属性选择度量是一种选择分裂准则，是将给定的类标记的训练集合的数据划分D“最好”地分成个体类的启发式方法，它决定了拓扑结构及分裂点split\_point的选择。

属性选择度量算法有很多，一般使用自顶向下递归分治法，并采用不回溯的贪心策略。例如，ID3 和 C4.5 这两种常用算法。

# 关于决策树的几点补充说明 #

**如果属性用完了怎么办**

在决策树构造过程中可能会出现这种情况：所有属性都作为分裂属性用光了，但有的子集还不是纯净集，即集合内的元素不属于同一类别。在这种情况下，由于没有更多信息可以使用了，一般对这些子集进行“多数表决”，即使用此子集中出现次数最多的类别作为此节点类别，然后将此节点作为叶子节点。

**关于剪枝**  
在实际构造决策树时，通常要进行剪枝，这时为了处理由于数据中的噪声和离群点导致的过分拟合问题。

**剪枝有两种：**

先剪枝——在构造过程中，当某个节点满足剪枝条件，则直接停止此分支的构造。  
后剪枝——先构造完成完整的决策树，再通过某些条件遍历树进行剪枝。

关于剪枝的具体算法这里不再详述，有兴趣的可以参考相关文献。

转载请注明张洋：[http://www.cnblogs.com/leoo2sk/archive/2010/09/19/decision-tree.html][http_www.cnblogs.com_leoo2sk_archive_2010_09_19_decision-tree.html]

[SouthEast]: /images/20210913/fd1e8248edc54d938d2575d6b798b082.png
[http_www.cnblogs.com_leoo2sk_archive_2010_09_19_decision-tree.html]: http://www.cnblogs.com/leoo2sk/archive/2010/09/19/decision-tree.html