机器学习第3章_决策树学习

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

1、第3章决策树学习(Decision-TreeAlgorithm)概论决策树学习是应用最广的归纳推理算法之一是一种逼近离散值函数的方法很好的健壮性能够学习析取表达式ID3,Assistant,C4.5搜索一个完整表示的假设空间归纳偏置是优先选择较小的树决策树表示了多个if-then规则提纲决策树定义适用问题特征基本ID3算法决策树学习的归纳偏置训练数据的过度拟合更深入的话题决策树表示法决策树通过把实例从根节点排列到某个叶子节点来分类实例。叶子节点即为实例所属的分类树上每个节点说明了对实例的某个属性的测试节点的每个后继分支对应于该属性的一个可能

2、值图3-1决策树代表实例属性值约束的合取的析取式。从树根到树叶的每一条路径对应一组属性测试的合取，树本身对应这些合取的析取。(Outlook=Sunny∧Humidity=Normal)∨(Outlook=Overcast)∨(Outlook=Rain∧Wind=Weak)DecisionTreeforPlayTennis决策树学习的适用问题适用问题的特征实例由“属性-值”对表示目标函数具有离散的输出值可能需要析取的描述训练数据可以包含错误训练数据可以包含缺少属性值的实例问题举例根据疾病分类患者根据起因分类设备故障根据拖欠支付的可能性分类贷

3、款申请分类问题核心任务是把样例分类到各可能的离散值对应的类别基本的决策树学习算法大多数决策树学习算法是一种核心算法的变体采用自顶向下的贪婪搜索遍历可能的决策树空间ID3是这种算法的代表基本的决策树学习算法（2）ID3的思想自顶向下构造决策树从“哪一个属性将在树的根节点被测试”开始使用统计测试来确定每一个实例属性单独分类训练样例的能力ID3的过程分类能力最好的属性被选作树的根节点根节点的每个可能值产生一个分支训练样例排列到适当的分支重复上面的过程表3-1用于学习布尔函数的ID3算法概要ID3(Examples,Target_attribute

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

5、在这个新分支下加一个叶子节点，节点的label=Examples中最普遍的Target_attribute值否则在新分支下加一个子树ID3（Examplesvi,Target_attribute,Attributes-{A}）结束返回root最佳分类属性信息增益(InformationGain)用来衡量给定的属性区分训练样例的能力ID3算法在增长树的每一步使用信息增益从候选属性中选择属性用熵度量样例的均一性熵刻画了任意样例集的纯度给定包含关于某个目标概念的正反样例的样例集S，那么S相对这个布尔型分类的熵为信息论中对熵的一种解释，熵确定了要编

6、码集合S中任意成员的分类所需要的最少二进制位数更一般地，如果目标属性具有c个不同的值，那么S相对于c个状态的分类的熵定义为Entropy(S)=S的所有成员属于同一类，Entropy(S)=0；S的正反样例数量相等，Entropy(S)=1；S的正反样例数量不等，熵介于0，1之间最佳分类属性（2）用信息增益度量期望的熵降低属性的信息增益，由于使用这个属性分割样例而导致的期望熵降低Gain(S,A)是在知道属性A的值后可以节省的二进制位数例子:+:+

7、uare>::2+,2:E=1sizebigsmall1+,11+,1E=1E=1Gain=1(0.51+0.51)=02+,2:E=1colorredblue2+,10+,1E=0.918E=0Gain=1(0.750.918+0.250)=0.3112+,2:E=1shapecirclesquare2+,10+,1E=0.918E=0Gain=1(0.750.918+0.250)=0.311最佳分类属性Outlook??YesSunnyOvercastRainD1

8、,2,8,9,11D3,7,12,13D4,5,6,11,14D1~14[9+,5-][2+,3-][4+,0-][3+,2-]什么属性？ID3算法第一步后形成的部分决策树ID3