决策树学习分享.ppt

《决策树学习分享.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、机器学习第3章决策树学习2003.11.181机器学习-决策树学习译者：曾华军等作者：Mitchell讲者：陶晓鹏概论决策树学习是应用最广的归纳推理算法之一是一种逼近离散值函数的方法很好的健壮性能够学习析取表达式ID3,Assistant,C4.5搜索一个完整表示的假设空间归纳偏置是优先选择较小的树决策树表示了多个if-then规则2003.11.182机器学习-决策树学习译者：曾华军等作者：Mitchell讲者：陶晓鹏提纲决策树定义适用问题特征基本ID3算法决策树学习的归纳偏置训练数据的过度拟合更深入的话题2003.11.183机器学习-

2、决策树学习译者：曾华军等作者：Mitchell讲者：陶晓鹏决策树表示法决策树通过把实例从根节点排列到某个叶子节点来分类实例。叶子节点即为实例所属的分类树上每个节点说明了对实例的某个属性的测试节点的每个后继分支对应于该属性的一个可能值图3-1决策树代表实例属性值约束的合取的析取式。从树根到树叶的每一条路径对应一组属性测试的合取，树本身对应这些合取的析取。2003.11.184机器学习-决策树学习译者：曾华军等作者：Mitchell讲者：陶晓鹏决策树学习的适用问题适用问题的特征实例由“属性-值”对表示目标函数具有离散的输出值可能需要析取的描述训

3、练数据可以包含错误训练数据可以包含缺少属性值的实例问题举例根据疾病分类患者根据起因分类设备故障根据拖欠支付的可能性分类贷款申请分类问题核心任务是把样例分类到各可能的离散值对应的类别2003.11.185机器学习-决策树学习译者：曾华军等作者：Mitchell讲者：陶晓鹏基本的决策树学习算法大多数决策树学习算法是一种核心算法的变体采用自顶向下的贪婪搜索遍历可能的决策树空间ID3是这种算法的代表2003.11.186机器学习-决策树学习译者：曾华军等作者：Mitchell讲者：陶晓鹏基本的决策树学习算法（2）ID3的思想自顶向下构造决策树从“哪

4、一个属性将在树的根节点被测试”开始使用统计测试来确定每一个实例属性单独分类训练样例的能力ID3的过程分类能力最好的属性被选作树的根节点根节点的每个可能值产生一个分支训练样例排列到适当的分支重复上面的过程2003.11.187机器学习-决策树学习译者：曾华军等作者：Mitchell讲者：陶晓鹏表3-1用于学习布尔函数的ID3算法概要ID3(Examples,Target_attribute,Attributes)创建树的root节点如果Examples都为正,返回label=+的单节点树root如果Examples都为反,返回label=-的

5、单节点树root如果Attributes为空，那么返回单节点root，label=Examples中最普遍的Target_attribute值否则开始AAttributes中分类examples能力最好的属性root的决策属性A对于A的每个可能值vi在root下加一个新的分支对应测试A=vi令Examplesvi为Examples中满足A属性值为vi的子集如果Examplesvi为空在这个新分支下加一个叶子节点，节点的label=Examples中最普遍的Target_attribute值否则在新分支下加一个子树ID3（Examples

6、vi,Target_attribute,Attributes-{A}）结束返回root2003.11.188机器学习-决策树学习译者：曾华军等作者：Mitchell讲者：陶晓鹏最佳分类属性信息增益用来衡量给定的属性区分训练样例的能力ID3算法在增长树的每一步使用信息增益从候选属性中选择属性用熵度量样例的均一性熵刻画了任意样例集的纯度给定包含关于某个目标概念的正反样例的样例集S，那么S相对这个布尔型分类的熵为Entropy(S)=-p+log2p+-p-log2p-信息论中对熵的一种解释，熵确定了要编码集合S中任意成员的分类所需要的最少二进制

7、位数更一般地，如果目标属性具有c个不同的值，那么S相对于c个状态的分类的熵定义为Entropy(S)=2003.11.189机器学习-决策树学习译者：曾华军等作者：Mitchell讲者：陶晓鹏最佳分类属性（2）用信息增益度量期望的熵降低属性的信息增益，由于使用这个属性分割样例而导致的期望熵降低Gain(S,A)是在知道属性A的值后可以节省的二进制位数例子2003.11.1810机器学习-决策树学习译者：曾华军等作者：Mitchell讲者：陶晓鹏ID3算法举例表3-2…继续这个过程，直到满足以下两个条件中的一个所有的属性已经被这条路经包括与这

8、个节点关联的所有训练样例都具有相同的目标属性值2003.11.1811机器学习-决策树学习译者：曾华军等作者：Mitchell讲者：陶晓鹏决策树学习中的假设空间搜索观察ID3的搜