机器学习决策树学习课件

决策树学习编写：张磊决策树学习编写：张磊1决策树决策树是实例（表示为特征向量）的分类器。结点测试特征，边表示特征的每个值，叶结点对应分类。

可表示任意析取和合取范式，从而表示任意离散函数和离散特征可将实例分到多个分类(2)可以重写为规则，用析取范式（DNF）形式

red^circle->positive

red^circle->A

blue->B;red^square->B

green->C;red^triangle->C2001年6月2日决策树决策树是实例（表示为特征向量）的分类器。结点测试特征，2决策树学习实例用(属性-值)对表示。离散值处理简单，连续值可以划分区间。输出可以是离散的分类，也可以是实数（回归树）。能有效处理大量数据可处理噪声数据（分类噪声，属性噪声）属性值缺失，亦可处理2001年6月2日决策树学习实例用(属性-值)对表示。离散值处理简单，连续值可3基本决策树算法训练数据批处理，自顶向下递归构造决策树DTree(examples,attributes)

If所有样本属于同一分类，返回标号为该分类的叶结点

Elseif属性值为空，返回标号为最普遍分类的叶结点

Else选取一个属性，A，作为根结点

ForA的每一个可能的值vi

令examplesi为具有A=vi的样本子集

从根结点出发增加分支（A=vi)

如果examplesi为空

则创建标号为最普遍分类的叶结点

否则递归创建子树——调用DTree(examplesi,attributes-{A})2001年6月2日基本决策树算法训练数据批处理，自顶向下递归构造决策树20014根属性的选取决策树要尽可能小寻找一组数据对应的最小决策树是NP-hard的简单递归算法是贪婪启发式搜索，无法保证最优子集应尽可能“纯”，从而易于成为叶结点最常用的启发规则是基于信息增益(InformationGain)2001年6月2日根属性的选取决策树要尽可能小2001年6月2日5熵(Entropy)一组样本S对于二元分类的熵(混淆度)为：

其中p+和p-为S中的正例、反例所占比例若所有样本属于同一分类，则熵为0(定义0log0=0)若样本平均分布(p+=p-=0.5)，则熵最大(=1)可把熵视为对样本集分类进行编码所需的平均二进制位数，采用哈夫曼编码压缩，越普遍的分类编码越短对于多分类问题（假设有c个分类），则熵的推广定义：

其中pi为属于分类i的样本在S中所占比例2001年6月2日熵(Entropy)一组样本S对于二元分类的熵(混淆度)为：6信息增益属性的信息增益是按该属性分割后熵的消减期望值：

其中Sv是S中属性A值为v的子集例子：big,red,circle:+small,red,circle:+small,red,square:-big,blue,circle:-2001年6月2日信息增益属性的信息增益是按该属性分割后熵的消减期望值：

7决策树归纳中的假设空间决策树可以表示任何离散函数，归纳就是在此空间内的搜索创建与数据一致的单一离散假设，所以无法提供置信度或构造有用的查询爬山式搜索存在局部最优问题。它可以保证找到符合任何无噪声数据集的树，但未必是最小的批量学习。每项决策需要一次数据集扫描，可提前结束学习以减少噪声影响2001年6月2日决策树归纳中的假设空间决策树可以表示任何离散函数，归纳就是在8决策树学习中的误区树的深度应尽量小。但贪婪搜索可能无法找到最小树，顶层结点可能不是高区分度的2001年6月2日决策树学习中的误区树的深度应尽量小。但贪婪搜索可能无法找到最9计算复杂度最坏情况是构造出一棵完全树，每条路径都测试了所有特征

各层i要对剩下的|A|-i个属性计算最佳分割

一般来说，性能与属性个数成线性关系2001年6月2日计算复杂度最坏情况是构造出一棵完全树，每条路径都测试了所有特10决策树研究的历史1960’s：Hunt的完全搜索决策树方法（CLS）对概念学习建模1970后期：Quinlan发明用信息增益作为启发策略的ID3方法，从样本中学习构造专家系统同时，Breiman和Friedman开发的CART（分类与回归树）方法类似于ID31980’s：对噪声、连续属性、数据缺失、改善分割条件等进行研究1993：Quinlan的改进决策树归纳包（C4.5），目前被普遍采用2001年6月2日决策树研究的历史1960’s：Hunt的完全搜索决策树方法（11过度拟合和修剪通过学习训练数据来构造分类树，可能无法达到最好的泛化性能，因为噪声数据的影响某些决策仅基于少量数据，与客观事实不符合一个假设H被称为对于训练数据是过度拟合的，指的是如果存在另一个假设H’，在训练集上H的误差比H‘小，但在测试集上H’的误差比H小2001年6月2日过度拟合和修剪通过学习训练数据来构造分类树，可能无法达到最好12过度拟合与噪声分类或属性噪声都会导致过度拟合

增加噪声实例<<medium,green,circle>,+>（实际为-）

噪声也会直接导致样本的冲突(相同描述，不同分类)。应将叶结点标号为主要的分类

<<big,red,circle>,->(实际上为+)若属性不完备且不足以判别分类时，也可能导致样本的冲突2001年6月2日过度拟合与噪声分类或属性噪声都会导致过度拟合

增加噪声实例<13避免过度拟合的方法需要修剪时的两个基本方法预修剪：支持度不够则停止树的增长后修剪：置信度不够则修剪掉该分支子树是否需要修剪的判别方法：交叉检验：保留部分训练数据用于验证统计测试：通过训练集的统计来判别最小描述长度(MDL)：判别该假设的复杂度是否比记忆例外情况的复杂度更高2001年6月2日避免过度拟合的方法需要修剪时的两个基本方法2001年6月2日14减小误差的修剪一种后修剪，交叉验证的方法

将训练数据分割为两个集合：“生长”和“验证”

用“生长”数据构建一棵完全树

Until验证数据集合上的精度降低do：

Foreach树中非叶结点n

临时修剪掉n下子树，用标号为主要分类的叶子代替

在验证集上计算该树的精度

修剪掉那些对精度影响最大的分支当训练集很小时，可能会严重损害分类精度最好能给定合适的结点数，达到最佳折衷2001年6月2日减小误差的修剪一种后修剪，交叉验证的方法

将训练数据分割为两15连续属性用分区方法，将连续值映射为离散值结点分裂，以获得最大信息增益达到最大信息增益的单阈值分裂算法

Foreach连续特征Ai

根据Ai的值对样本排序

Foreach序列中的每对Xi,Xi+1

IfXi和Xi+1的分类不同

将Xi和Xi+1的中点作为可能的阈值进行检验，即

例如：

长度(L):10152128324050(已排序)

分类:-++-++-检查阈值：L<12.5,L<24.5,L<30,L<452001年6月2日连续属性用分区方法，将连续值映射为离散值2001年6月2日16替代属性选取启发策略(增益比率)信息增益缺点：偏爱那些有大量值的属性，产生很多小而纯的子集，如病人ID、姓名、日期等要降低这些情况下的增益首先计算与分类无关属性的信息量，即该属性的熵

其中Si为S中具有属性A第i个值的子集。某属性按值分割样本越平均，则SplitInfo越大增益比率利用SplitInfo来避免选择这些属性

2001年6月2日替代属性选取启发策略(增益比率)信息增益缺点：偏爱那些有大量17增益比率细述然而，当|Si|=|S|时SplitInfo可能很小甚至为0，从而导致信息比率过大甚至溢出C4.5对此进行了改进，它计算每个特征的信息增益，对于超过平均增益的特征，再进一步根据增益比率来选取特征2001年6月2日增益比率细述然而，当|Si|=|S|时SplitInfo可18缺失的属性值属性值可能未完全给出一种解决方法是根据已有样本属性值的先验概率来对样本计算属性值分布百分比

在训练时，缺失的属性会按照其分布百分比逐个计算。例如，给定一个缺失了颜色属性值的正例，它将被视为0.6个red正例、0.2个blue正例和0.2个green正例。2001年6月2日缺失的属性值属性值可能未完全给出2001年6月2日19测试时的值缺失若属性值未给出，则设定为??(通配符)，然后多路径到达叶结点，最后计算分类结果的各分类权重

例如，

<big,??,circle>将得到0.6个正例，0.2+0.2=0.4个反例

<big,red,??>将得到0.2个正例，0.5+0.3=0.8个反例

<big,??,??>将得到0.6x0.2=0.12个正例，0.2+0.2+0.3+0.18=0.88个反例2001年6月2日测试时的值缺失若属性值未给出，则设定为??(通配符)，然后多20属性开销有些领域中，某些属性比其它属性更容易获取其值(例如病人的体温比其胆固醇水平更容易得到)尽可能采用那些低开销的属性来分类在信息增益中增加属性开销是有效的:

在不降低精度的同时降低了平均开销2001年6月2日属性开销有些领域中，某些属性比其它属性更容易获取其值(例如病21递增式的决策树归纳ID4和ID5可以递增更新已有的树ID4有时会丢弃某些实例，不保证和历史训练样本一致ID5则保证和ID3的决策相同ID4速度快，但精度降低ID5速度较快且精度不变2001年6月2日递增式的决策树归纳ID4和ID5可以递增更新已有的树200122决策树中的重复部分决策树比DNF更复杂，因为它常常存在重复部分

范式必须分解为析取范式，导致了重复子树的出现解决：使用复杂特征或决策图构造性归纳：原子特征的逻辑组合或算术组合2001年6月2日决策树中的重复部分决策树比DNF更复杂，因为它常常存在重复部23边缘算法决策树构造性归纳的叠代算法边缘算法（总是沿着树的边缘走）

Until没有新的特征被创建或到达限定值do

使用当前的所有特征从训练集构造决策树

从边缘末端(正例)两个特征的联合来创建新特征

将这些新特征加入现有特征集中，同时扩展每个样本 的描述以包含所有新特征2001年6月2日边缘算法决策树构造性归纳的叠代算法2001年6月2日24边缘示例2001年6月2日边缘示例2001年6月2日25多重模型学习概念的多重候选定义最终决策是基于多个学习模型的(加权)投票2001年6月2日多重模型学习概念的多重候选定义2001年6月2日26装袋(Bagging)用训练集的不同样本来训练同一个学习者，来创建多重模型(Breiman,1996)给定训练集大小为n，通过从原始数据取样(用替换方法)，创建m个不同的训练集(大小为n)用简单的投票方法来合并这m个模型可用于任何学习方法减少了不稳定学习算法的一般化错误，即当训练数据轻微改动时会导致决策结果剧烈变动的那些学习方法2001年6月2日装袋(Bagging)用训练集的不同样本来训练同一个学习者，27引导(Boosting)另一个生成多重模型的方法——重复更改同一个学习算法的数据对弱学习算法(假设的精度只要超过1/2即可)能保证性能的改进对样本加权，每次叠代产生一个新的假设，对那些导致最终假设精度变差的样本重新加权基本算法

给所有样本赋予一个初始权重

Forifrom1toTdo

从加权的样本中学习一个假设hi

减小那些与hi一致的样本的权重在测试时，每个假设会得到一个加权的投票(与训练数据上的精度成比例)2001年6月2日引导(Boosting)另一个生成多重模型的方法——重复更改28引导算法ForD中的每个样本，令其权重wi=1/|D|Fortfrom1toTdo

从加权样本中学习一个假设ht

计算ht的误差t，作为被错误分类样本的总权重

Ift>0.5then终止，else继续

令t=t/(1-t)

将ht正确分类出的样本的权重乘以t

权重归一化以保证总和为1在测试时，每个假设ht获得投票的权重为log(1/t)，票数最多的假设作为最终决策2001年6月2日引导算法ForD中的每个样本，令其权重wi=1/|D|2029多重模型的实验结果多决策树模型应用范围更广也更准确引导算法性能比装袋算法好引导算法偶尔也会降低性能2001年6月2日多重模型的实验结果多决策树模型应用范围更广也更准确2001年30演讲完毕，谢谢观看！演讲完毕，谢谢观看！31决策树学习编写：张磊决策树学习编写：张磊32决策树决策树是实例（表示为特征向量）的分类器。结点测试特征，边表示特征的每个值，叶结点对应分类。

可表示任意析取和合取范式，从而表示任意离散函数和离散特征可将实例分到多个分类(2)可以重写为规则，用析取范式（DNF）形式

red^circle->positive

red^circle->A

blue->B;red^square->B

green->C;red^triangle->C2001年6月2日决策树决策树是实例（表示为特征向量）的分类器。结点测试特征，33决策树学习实例用(属性-值)对表示。离散值处理简单，连续值可以划分区间。输出可以是离散的分类，也可以是实数（回归树）。能有效处理大量数据可处理噪声数据（分类噪声，属性噪声）属性值缺失，亦可处理2001年6月2日决策树学习实例用(属性-值)对表示。离散值处理简单，连续值可34基本决策树算法训练数据批处理，自顶向下递归构造决策树DTree(examples,attributes)

If所有样本属于同一分类，返回标号为该分类的叶结点

Elseif属性值为空，返回标号为最普遍分类的叶结点

Else选取一个属性，A，作为根结点

ForA的每一个可能的值vi

令examplesi为具有A=vi的样本子集

从根结点出发增加分支（A=vi)

如果examplesi为空

则创建标号为最普遍分类的叶结点

否则递归创建子树——调用DTree(examplesi,attributes-{A})2001年6月2日基本决策树算法训练数据批处理，自顶向下递归构造决策树200135根属性的选取决策树要尽可能小寻找一组数据对应的最小决策树是NP-hard的简单递归算法是贪婪启发式搜索，无法保证最优子集应尽可能“纯”，从而易于成为叶结点最常用的启发规则是基于信息增益(InformationGain)2001年6月2日根属性的选取决策树要尽可能小2001年6月2日36熵(Entropy)一组样本S对于二元分类的熵(混淆度)为：

其中p+和p-为S中的正例、反例所占比例若所有样本属于同一分类，则熵为0(定义0log0=0)若样本平均分布(p+=p-=0.5)，则熵最大(=1)可把熵视为对样本集分类进行编码所需的平均二进制位数，采用哈夫曼编码压缩，越普遍的分类编码越短对于多分类问题（假设有c个分类），则熵的推广定义：

其中pi为属于分类i的样本在S中所占比例2001年6月2日熵(Entropy)一组样本S对于二元分类的熵(混淆度)为：37信息增益属性的信息增益是按该属性分割后熵的消减期望值：

其中Sv是S中属性A值为v的子集例子：big,red,circle:+small,red,circle:+small,red,square:-big,blue,circle:-2001年6月2日信息增益属性的信息增益是按该属性分割后熵的消减期望值：

38决策树归纳中的假设空间决策树可以表示任何离散函数，归纳就是在此空间内的搜索创建与数据一致的单一离散假设，所以无法提供置信度或构造有用的查询爬山式搜索存在局部最优问题。它可以保证找到符合任何无噪声数据集的树，但未必是最小的批量学习。每项决策需要一次数据集扫描，可提前结束学习以减少噪声影响2001年6月2日决策树归纳中的假设空间决策树可以表示任何离散函数，归纳就是在39决策树学习中的误区树的深度应尽量小。但贪婪搜索可能无法找到最小树，顶层结点可能不是高区分度的2001年6月2日决策树学习中的误区树的深度应尽量小。但贪婪搜索可能无法找到最40计算复杂度最坏情况是构造出一棵完全树，每条路径都测试了所有特征

各层i要对剩下的|A|-i个属性计算最佳分割

一般来说，性能与属性个数成线性关系2001年6月2日计算复杂度最坏情况是构造出一棵完全树，每条路径都测试了所有特41决策树研究的历史1960’s：Hunt的完全搜索决策树方法（CLS）对概念学习建模1970后期：Quinlan发明用信息增益作为启发策略的ID3方法，从样本中学习构造专家系统同时，Breiman和Friedman开发的CART（分类与回归树）方法类似于ID31980’s：对噪声、连续属性、数据缺失、改善分割条件等进行研究1993：Quinlan的改进决策树归纳包（C4.5），目前被普遍采用2001年6月2日决策树研究的历史1960’s：Hunt的完全搜索决策树方法（42过度拟合和修剪通过学习训练数据来构造分类树，可能无法达到最好的泛化性能，因为噪声数据的影响某些决策仅基于少量数据，与客观事实不符合一个假设H被称为对于训练数据是过度拟合的，指的是如果存在另一个假设H’，在训练集上H的误差比H‘小，但在测试集上H’的误差比H小2001年6月2日过度拟合和修剪通过学习训练数据来构造分类树，可能无法达到最好43过度拟合与噪声分类或属性噪声都会导致过度拟合

增加噪声实例<<medium,green,circle>,+>（实际为-）

噪声也会直接导致样本的冲突(相同描述，不同分类)。应将叶结点标号为主要的分类

<<big,red,circle>,->(实际上为+)若属性不完备且不足以判别分类时，也可能导致样本的冲突2001年6月2日过度拟合与噪声分类或属性噪声都会导致过度拟合

增加噪声实例<44避免过度拟合的方法需要修剪时的两个基本方法预修剪：支持度不够则停止树的增长后修剪：置信度不够则修剪掉该分支子树是否需要修剪的判别方法：交叉检验：保留部分训练数据用于验证统计测试：通过训练集的统计来判别最小描述长度(MDL)：判别该假设的复杂度是否比记忆例外情况的复杂度更高2001年6月2日避免过度拟合的方法需要修剪时的两个基本方法2001年6月2日45减小误差的修剪一种后修剪，交叉验证的方法

将训练数据分割为两个集合：“生长”和“验证”

用“生长”数据构建一棵完全树

Until验证数据集合上的精度降低do：

Foreach树中非叶结点n

临时修剪掉n下子树，用标号为主要分类的叶子代替

在验证集上计算该树的精度

修剪掉那些对精度影响最大的分支当训练集很小时，可能会严重损害分类精度最好能给定合适的结点数，达到最佳折衷2001年6月2日减小误差的修剪一种后修剪，交叉验证的方法

将训练数据分割为两46连续属性用分区方法，将连续值映射为离散值结点分裂，以获得最大信息增益达到最大信息增益的单阈值分裂算法

Foreach连续特征Ai

根据Ai的值对样本排序

Foreach序列中的每对Xi,Xi+1

IfXi和Xi+1的分类不同

将Xi和Xi+1的中点作为可能的阈值进行检验，即

例如：

长度(L):10152128324050(已排序)

分类:-++-++-检查阈值：L<12.5,L<24.5,L<30,L<452001年6月2日连续属性用分区方法，将连续值映射为离散值2001年6月2日47替代属性选取启发策略(增益比率)信息增益缺点：偏爱那些有大量值的属性，产生很多小而纯的子集，如病人ID、姓名、日期等要降低这些情况下的增益首先计算与分类无关属性的信息量，即该属性的熵

其中Si为S中具有属性A第i个值的子集。某属性按值分割样本越平均，则SplitInfo越大增益比率利用SplitInfo来避免选择这些属性

2001年6月2日替代属性选取启发策略(增益比率)信息增益缺点：偏爱那些有大量48增益比率细述然而，当|Si|=|S|时SplitInfo可能很小甚至为0，从而导致信息比率过大甚至溢出C4.5对此进行了改进，它计算每个特征的信息增益，对于超过平均增益的特征，再进一步根据增益比率来选取特征2001年6月2日增益比率细述然而，当|Si|=|S|时SplitInfo可49缺失的属性值属性值可能未完全给出一种解决方法是根据已有样本属性值的先验概率来对样本计算属性值分布百分比

在训练时，缺失的属性会按照其分布百分比逐个计算。例如，给定一个缺失了颜色属性值的正例，它将被视为0.6个red正例、0.2个blue正例和0.2个green正例。2001年6月2日缺失的属性值属性值可能未完全给出2001年6月2日50测试时的值缺失若属性值未给出，则设定为??(通配符)，然后多路径到达叶结点，最后计算分类结果的各分类权重

例如，

<big,??,circle>将得到0.6个正例，0.2+0.2=0.4个反例

<big,red,??>将得到0.2个正例，0.5+0.3=0.8个反例

<big,??,??>将得到0.6x0.2=0.12个正例，0.2+0.2+0.3+0.18=0.88个反例2001年6月2日测试时的值缺失若属性值未给出，则设定为??(通配符)，然后多51属性开销有些领域中，某些属性比其它属性更容易获取其值(例如病人的体温比其胆固醇水平更容易得到)尽可能采用那些低开销的属性来分类在信息增益中增加属性开销是有效的:

在不降低精度的同时降低了平均开销2001年6月2日属性开销有些领域中，某些属性比其它属性更容易获取其值(例如病52递增式的决策树归纳ID4和ID5可以递增更新已有的树ID4有时会丢弃某些实例，不保证和历史训练样本一致ID5则保证和ID3的决策相同ID4速度快，但精度降低ID5速度较快且精度不变2001年6月2日递增式的决策树归纳ID4和ID5可以递增更新已有的树200153决策树中的重复部分决策树比DNF更复杂，因为它常常存在重复部分

范式必须分解为析取范式，导致了重复子树的出现解决：使用复杂特征或决策图构造性归纳：原子特征的逻辑组合或算术组合2001年6月2日决策树中的重复部分决策树比DNF更复杂，因为它常常存在重复部54边缘算法决策树构造性归纳的叠代算法边缘算法（总是沿着树的边缘走）

Until没有新的特征被创建或到达限定值do

使用当前的所有特征从