【机器学习】决策树（上）——从原理到算法实现

                     

前言：决策树（Decision Tree）是一种基本的分类与回归方法，本文主要讨论分类决策树。决策树模型呈树形结构，在分类问题中，表示基于特征对实例进行分类的过程。它可以认为是if-then规则的集合，也可以认为是定义在特征空间与类空间上的条件概率分布。相比朴素贝叶斯分类，决策树的优势在于构造过程不需要任何领域知识或参数设置，因此在实际应用中，对于探测式的知识发现，决策树更加适用。

一、决策树模型
1.定义
    分类决策树模型是一种描述对实例进行分类的树形结构。决策树由结点和有向边组成。结点有两种类型：内部节点和叶节点，内部节点表示一个特征或属性，叶节点表示一个类。
    分类的时候，从根节点开始，对实例的某一个特征进行测试，根据测试结果，将实例分配到其子结点；此时，每一个子结点对应着该特征的一个取值。如此递归向下移动，直至达到叶结点，最后将实例分配到叶结点的类中。
    举一个通俗的栗子，各位立志于脱单的单身男女在找对象的时候就已经完完全全使用了决策树的思想。假设一位母亲在给女儿介绍对象时，有这么一段对话：

母亲：给你介绍个对象。女儿：年纪多大了？母亲：26。女儿：长的帅不帅？母亲：挺帅的。女儿：收入高不？母亲：不算很高，中等情况。女儿：是公务员不？母亲：是，在税务局上班呢。女儿：那好，我去见见。

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10

这个女生的决策过程就是典型的分类决策树。相当于对年龄、外貌、收入和是否公务员等特征将男人分为两个类别：见或者不见。假设这个女生的决策逻辑如下：

    上图完整表达了这个女孩决定是否见一个约会对象的策略，其中绿色结点（内部结点）表示判断条件，橙色结点（叶结点）表示决策结果，箭头表示在一个判断条件在不同情况下的决策路径，图中红色箭头表示了上面例子中女孩的决策过程。
    这幅图基本可以算是一棵决策树，说它“基本可以算”是因为图中的判定条件没有量化，如收入高中低等等，还不能算是严格意义上的决策树，如果将所有条件量化，则就变成真正的决策树了。（以上的决策树模型纯属瞎编乱造，不代表任何女生的择偶观，旨在直观理解决策树，各位女同志无须在此挑刺。。。）

2.决策树与if-then规则
    现在我们可以更抽象一些。决策树可以看成一个if-then规则的集合：由决策树的根结点到叶结点的每一条路径构建一条规则；路径上的内部结点的特征对应着规则的条件，而叶结点对应着分类的结论。决策树的路径和其对应的if-then规则集合是等效的，它们具有一个重要的性质：互斥并且完备。这里的意思是说：每一个实例都被一条路径或一条规则所覆盖，而且只被一条规则所覆盖。

3.决策树与条件概率分布
    决策树还是给定特征条件下类的条件概率分布的一种表示。该条件分布定义在特征空间的划分（partition）上，特征空间被划分为互不相交的单元（cell），每个单元定义一个类的概率分布就构成了一个条件概率分布。决策树的一条路径对应于划分中的一个单元。决策树所表示的条件概率分布由各个单元给定条件下类的条件概率分布组成。给定实例的特征X，一定落入某个划分，决策树选取该划分里最大概率的类作为结果输出。如图：

图(a)表示该实例的特征向量是二维的（即具有两个特征），图(b)表示给定特征X X，定义为集合D