1、决策树算法概述
决策树学习是应用的最广的归纳推理算法之一。它是一种逼近离散值函数的方法，对噪声有很好的健壮性且能够学习析取表达式。决策树一般都是自上而下的来生成的，并用了贪婪的搜索遍历方法进行遍历。每个决策或事件（即自然状态）都可能引出两个或多个事件，导致不同的结果，把这种决策分支画成图形很像一棵树的枝干，故称决策树。
贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。
2、决策树表示法
决策树通过把实例从根节点排列到某个叶子节点来分类实例，叶子节点即为实例所属的分类，树上的每个节点指定了对实例的某个属性的测试，并且每个节点的每一个后继分支对 应于该属性的一个可能的值。分类实例的方法是从这棵树的根节点开始，测试这个节点指定的属性，然后按照给定实例的该属性值对应的树枝向下移动。然后这个过程在以新的节点为根的子树上重复。下面给出一棵典型的学习到的决策树。这棵决策树根据天气情况分类“星期六上午是否适合打网球”。例如下面的实例将被沿着这棵决策树的最左分支向下排列，因而被判定为反例（也就是这棵树预测这个实例PlayTennis=No）。
图1
<Outlook=Sunny,Temperature=Hot,Humidity=High,Wind=Strong>
通常决策树代表实例属性值约束的合取式（conjunction）的析取式（disjunction）。从树根到树叶的每一条路径对应一条属性测试的合取，树本身对应这些合取的析取。如上图表示的决策树对应于以下表达式：
(Outlook=Sunny Humidity=Normal)
( Outlook=Overcast)
( Outlook=Rain Wind=Weak )
3、决策树学习的适用问题
决策树学习适用于具有以下特征的问题：
（1）实例是由“属性——值”对表示的：实例是用一系列固定的属性和它们的值来描述的。
（2）目标函数具有离散的输出值：如最后的结果是布尔函数的分类。
（3）可能需要析取的描述：如上例所代表的析取式。
（4）训练数据可以包含错误。
（5）训练数据可以包含缺少属性值的实例。
现实中有很多的实例都可以运用到决策树学习中。对于这些问题，核心任务都是要把样例分类到各可能的离散值对应的类别（category）中，因此经常被称为分了问题（classification problem）。
4、基本的决策树学习算法
大多数以开发的决策树算法是一种核心算法的变体。该算法采用自顶向下的贪婪搜索遍历可能的决策树空间。这种方法是ID3（Quinlan 1986）和后继的C4.5算法（Quinlan 1993）的基础，也是我们应该掌握的重点。
基本的ID3算法通过自顶向下构造决策树来进行学习。构造过程是从“哪一个属性将在根结点被测试？”这个问题开始的。为此我们可以使用统计测试来确定每一个实例属性单独分类训练样例的能力。分类能力最好的属性被选作树的根节点的测试，然后为根节点属性的每个可能值产生一个分支，并把训练样例排列到适当的分支（也就是该属性值对应的分支）
之下。然后重复整个过程，用每个分支节点关联的训练样例来选取在该节点被测试的最佳属性。这形成了对合格决策树的贪婪搜索，也就是算法从不回溯重复考虑以前的选择。
下面给出该算法的一个简化版本——专门用来学习布尔值函数（即概念学习）。
ID3（Examples是,Target_attribute,Attributes）
Examples即训练样例集。Target_attribute是这棵树要预测的目标属性。Attributes是除目标属性外供学习到的决策树测试的属性列表。返回一棵能正确分类给定Example的决策树。
·创建树的Root节点
·如果Examples都为正，那么返回label=+的单节点树Root
·如果Examples都为负，那么返回label=-的单节点树Root
·如果Attributes为空，那么返回单节点树Root，label=Examples中最普遍的Target_attribut
e值
·否则开始
·A<——Attributes中分类能力最好的属性
·Root的决策属性<——A
·对于A的每个可能值vi
·在Root下加一个新的分支对应测试A= vi
·令Examples vi为Examples中满足A属性值为vi的子集
·如果Examples vi为空
·在这个新的分支下加一个叶子及节点，节点的label=Examples中最普遍的arget
_attribute值
·否则在这个新的分支下接一个子树ID3
（Examplesvi arget_attribute Attributes-{A}）
·结束
·返回
4.1哪个属性是最佳的分类属性
ID3算法的核心问题是选取在树的每个节点要测试的属性。又希望选择的是最有助于分类实例的属性。因而如何衡量属性的价值标准就需要有一个统一的规定。这里我们定义一个统计属性，称为“信息增益”。用来衡量给定的属性区分训练样例的能力。ID3算法在增长树的每一步使用这个信息增益标准从候选属性中选择属性。
4.1.1．用熵度量样例的均一性
信息论中广泛使用的一个度量标准,这里我们可以用来定义信息增益，它就是熵（entrop），它刻画了任意样例集的纯度（purity）。给定包含关于某个目标概念的正反样例的样例集S，那么S相对这个布尔函数的熵就可以用一个公式来计算：
Entrop(S)=-p log2p -p- log2 p-
其中p 是在S中的正例的比例，P- 是S中反例的比例。此外还有还定义0log0=0。
如果目标属性具有c个不同的值，那么s 相对于c个状态（c-wise）的分类熵定义为：
Entrop(S)=ilog2pi
其中pI是S中属于类别i的比例。
4.1.2. 用信息增益度量期望的熵降低
有了熵作为衡量训练样例集合纯度的标准，就可以定义属性分类训练数据的能力的度量标准。这个标准就是“信息增益”（information gain）。简单的说一个信息增益就是由于使用
这个属性分割样例而导致的期望熵降低。更精确的说，一个属性A相对训练样例集合S的信息增益Gain(S,A)被定义为：
Gain(S,A)=Entropy(S) -
其中Values(A)是属性A所有可能值的集合。Sv是S中属性A的值为v的子集（也就是，Sv={sS|A(s)=v}）。
信息增益正式ID3算法增长树的每一步中选择最佳属性的度量标准。
4.2举例
为了演示ID3算法的具体操作，我们考虑以下表的训练数据所代表的学习任务。目标属性Play Tennis对于不同的星期六上午具有yes和no两个值，我们将根据其他属性来预测这个目标属性值。先考虑这个算法的第一步，创建决策树的最顶端结点。ID3算法计算每一个候选属性的信息增益，然后选择信息增益最高的一个。
所有四个属性的信息增益为：
Gain(S,Outlook)=0.246
Gain(S,Humidity)=0.151
Gain(S,Wind)=0.048
Gain(S,Temperature)=0.029
S来自下表的训练样例的集合
目标概念PlayTennis的训练样例
Day Outlook Temperature Humidity Wind PlayTennis
