基本的决策树学习算法 大多数决策树学习算法是一种核心算法 的变体 采用自顶向下的贪婪搜索遍历可能的决 策树空间 ID3是这种算法的代表 2003.11.18 机器学习-决策树学习译者:曾华军等作者: Mitchell讲者:陶晓鹏
2003.11.18 机器学习-决策树学习译者：曾华军等作者：Mitchell 讲者：陶晓鹏 6 基本的决策树学习算法 • 大多数决策树学习算法是一种核心算法 的变体 • 采用自顶向下的贪婪搜索遍历可能的决 策树空间 • ID3是这种算法的代表
基本的决策树学习算法(2) ID3的思想 自顶向下构造决策树 从“哪一个属性将在树的根节点被测试”开始 使用统计测试来确定每一个实例属性单独分类训练 样例的能力 D3的过程 分类能力最好的属性被选作树的根节点 根节点的每个可能值产生一个分支 训练样例排列到适当的分支 重复上面的过程 2003.11.18 机器学习-决策树学习译者:曾华军等作者: Mitchell讲者:陶晓鹏
2003.11.18 机器学习-决策树学习译者：曾华军等作者：Mitchell 讲者：陶晓鹏 7 基本的决策树学习算法（2） • ID3的思想 – 自顶向下构造决策树 – 从“哪一个属性将在树的根节点被测试”开始 – 使用统计测试来确定每一个实例属性单独分类训练 样例的能力 • ID3的过程 – 分类能力最好的属性被选作树的根节点 – 根节点的每个可能值产生一个分支 – 训练样例排列到适当的分支 – 重复上面的过程
表3-1用于学习布尔函数的D3算法概要 D3(Examples, Target attribute, Attributes) 创建树的root节点 如果 Examples都为正,返回abe+的单节点树root 如果 Examples都为反,返回habe-的单节点树root 如果 Attributes为空,那么返回单节点roo, labehExamples中最普遍的 Target attribute值 否则开始 A←- Attributes中分类 examples能力最好的属性 root的决策属性←A 对于A的每个可能值ⅵ 在root下加一个新的分支对应测试A=vi 令 Examples为 Examples中满足A属性值为v的子集 如果 Examples为空 在这个新分支下加一个叶子节点,节点的 label=Examples中最普遍的 bute值 否则在新分支下加一个子树ID3( Examples, Target attribute, Attributes-{A}) 结束 返回root 2003.11.18 机器学习-决策树学习译者:曾华军等作者: Mitchell讲者:陶晓鹏
2003.11.18 机器学习-决策树学习译者：曾华军等作者：Mitchell 讲者：陶晓鹏 8 表3-1 用于学习布尔函数的ID3算法概要 • ID3(Examples, Target_attribute, Attributes) • 创建树的root节点 • 如果Examples都为正,返回label=+的单节点树root • 如果Examples都为反,返回label=-的单节点树root • 如果Attributes为空，那么返回单节点root，label=Examples中最普遍的Target_attribute值 • 否则开始 – AAttributes中分类examples能力最好的属性 – root的决策属性A – 对于A的每个可能值vi • 在root下加一个新的分支对应测试A=vi • 令Examplesvi为Examples中满足A属性值为vi的子集 • 如果Examplesvi为空 – 在这个新分支下加一个叶子节点，节点的label=Examples中最普遍的 Target_attribute值 – 否则在新分支下加一个子树ID3（Examplesvi,Target_attribute,Attributes-{A}） • 结束 • 返回root
最佳分类属性 信息增益 用来衡量给定的属性区分训练样例的能力 ID3算法在增长树的每一步使用信息増益从候选属性中选择属性 用熵度量样例的均一性 熵刻画了任意样例集的纯度 给定包含关于某个目标概念的正反样例的样例集S,那么S相对这个 布尔型分类的熵为 Entropy (s=-p+log2p+-p-log p 信息论中对熵的一种解释,熵确定了要编码集合S中任意成员的分类 所需要的最少二进制位数 更一般地,如果目标属性具有c个不同的值,那么S相对于c个状态的 分类的熵定义为 Entropy(S)∑-pkgP 2003.11.18 机器学习-决策树学习译者:曾华军等作者: Mitchell讲者:陶晓鹏
2003.11.18 机器学习-决策树学习译者：曾华军等作者：Mitchell 讲者：陶晓鹏 9 最佳分类属性 • 信息增益 – 用来衡量给定的属性区分训练样例的能力 – ID3算法在增长树的每一步使用信息增益从候选属性中选择属性 • 用熵度量样例的均一性 – 熵刻画了任意样例集的纯度 – 给定包含关于某个目标概念的正反样例的样例集S，那么S相对这个 布尔型分类的熵为 Entropy(S)=-p+log2p+ - p-log2p- – 信息论中对熵的一种解释，熵确定了要编码集合S中任意成员的分类 所需要的最少二进制位数 – 更一般地，如果目标属性具有c个不同的值，那么S相对于c个状态的 分类的熵定义为 Entropy(S)= = − c i pi pi 1 2 log
最佳分类属性(2) 用信息增益度量期望的熵降低 属性的信息增益,由于使用这个属性分割样 例而导致的期望熵降低 Gain(S, A)=Entropys) Entropys) Gain(S,A)是在知道属性A的值后可以节省的 二进制位数 例子 2003.11.18 机器学习-决策树学习译者:曾华军等作者: Mitchell讲者:陶晓鹏
2003.11.18 机器学习-决策树学习译者：曾华军等作者：Mitchell 讲者：陶晓鹏 10 最佳分类属性（2） • 用信息增益度量期望的熵降低 – 属性的信息增益，由于使用这个属性分割样 例而导致的期望熵降低 – Gain(S,A)是在知道属性A的值后可以节省的 二进制位数 – 例子 = − ( ) ( ) | | ( , ) ( ) v Values A v v Entropy S S S Gain S A Entropy S