决策树学习资料

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

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

red^circle->positive

red^circle->A

blue->B;red^square->B

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

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

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

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

ForA的每一个可能的值vi

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

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

如果examplesi为空

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

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

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

其中pi为属于分类i的样本在S中所占比例2001年6月2日信息增益属性的信息增益是按该属性分割后熵的消减期望值：

其中Sv是S中属性A值为v的子集例子：big,red,circle:+small,red,circle:+small,red,square:-big,blue,circle:-2001年6月2日决策树归纳中的假设空间决策树可以表示任何离散函数，归纳就是在此空间内的搜索创建与数据一致的单一离散假设，所以无法提供置信度或构造有用的查询爬山式搜索存在局部最优问题。它可以保证找到符合任何无噪声数据集的树，但未必是最小的批量学习。每项决策需要一次数据集扫描，可提前结束学习以减少噪声影响2001年6月2日决策树学习中的误区树的深度应尽量小。但贪婪搜索可能无法找到最小树，顶层结点可能不是高区分度的2001年6月2日计算复杂度最坏情况是构构造出一棵完完全树，每条条路径都测试试了所有特征征各层i要对剩剩下的|A|-i个属性性计算最佳分分割一般来来说，，性能能与属属性个个数成成线性性关系系2001年年6月月2日日决策树树研究究的历历史1960’’s：：Hunt的完完全搜搜索决决策树树方法法（CLS）对对概念念学习习建模模1970后后期：：Quinlan发发明用用信息息增益益作为为启发发策略略的ID3方法法，从从样本本中学学习构构造专专家系系统同时，Breiman和Friedman开发的的CART（分分类与回回归树））方法类类似于ID31980’s：：对噪声声、连续续属性、、数据缺缺失、改改善分割割条件等等进行研研究1993：Quinlan的的改进决决策树归归纳包（（C4.5），，目前被被普遍采采用2001年6月月2日过度拟合合和修剪剪通过学习习训练数数据来构构造分类类树，可可能无法法达到最最好的泛泛化性能能，因为为噪声数据据的影响响某些决策策仅基于于少量数数据，与与客观事事实不符符合一个假设设H被称为对对于训练练数据是是过度拟拟合的，，指的是是如果存存在另一一个假设设H’，在训练集集上H的的误差比比H‘小，但但在测试试集上H’的误差比比H小2001年6月月2日过度拟合合与噪声声分类或属属性噪声声都会导导致过度度拟合增增加噪噪声实例例<<medium,green,circle>,+>（实实际为-）噪声也会会直接导导致样本本的冲突突(相同同描述，，不同分分类)。。应将叶叶结点标标号为主主要的分分类<<big,red,circle>,->(实际上上为+)若属性不不完备且且不足以以判别分分类时，，也可能能导致样样本的冲冲突2001年6月月2日避免过度度拟合的的方法需要修剪剪时的两两个基本本方法预修剪：支持度度不够则则停止树树的增长长后修剪：置信度度不够则则修剪掉掉该分支支子树是否否需要修修剪的判判别方法法：交叉检验验：保留部部分训练练数据用用于验证证统计测试试：通过训训练集的的统计来来判别最小描述述长度(MDL)：判别该假假设的复复杂度是是否比记记忆例外外情况的的复杂度度更高2001年6月月2日减小误差差的修剪剪一种后修修剪，交交叉验证证的方法法

将训训练数据据分割为为两个集集合：““生长””和“验验证”用用“生生长”数数据构建建一棵完完全树Until验验证数数据集合合上的精精度降低低do：Foreach树中中非叶结结点n临临时时修剪掉掉n下子子树，用用标号为为主要分分类的叶叶子代替替在在验证集集上计算算该树的的精度修修剪掉那那些对精精度影响响最大的的分支当训练集集很小时时，可能能会严重重损害分分类精度度最好能给给定合适适的结点点数，达达到最佳佳折衷2001年6月月2日连续属性性用分区方方法，将将连续值值映射为为离散值值结点分裂裂，以获获得最大大信息增增益达到最大大信息增增益的单单阈值分分裂算法法Foreach连续特征Ai根据Ai的值对样本排排序Foreach序列中的每对对Xi,Xi+1IfXi和Xi+1的分类不同将将Xi和Xi+1的中点作为可可能的阈值进进行检验，即即例如：长长度(L):10152128324050(已排序)

分类:-++-++-检查阈值：L<12.5,L<24.5,L<30,L<452001年6月2日替代属性选取取启发策略(增益比率)信息增益缺点点：偏爱那些些有大量值的的属性，产生生很多小而纯纯的子集，如如病人ID、姓名、日期等等要降低这些情情况下的增益益首先计算与分分类无关属性性的信息量，，即该属性的的熵其其中Si为S中具有属性A第i个值的子集。。某属性按值值分割样本越越平均，则SplitInfo越大增益比率利用用SplitInfo来避免选择这这些属性2001年6月2日增益比率细述述然而，当|Si|=|S|时SplitInfo可能很小甚至至为0，从而而导致信息比比率过大甚至至溢出C4.5对此进进行了改改进，它它计算每每个特征征的信息息增益，，对于超超过平均均增益的的特征，，再进一一步根据据增益比比率来选选取特征征2001年6月月2日缺失的属属性值属性值可可能未完完全给出出一种解决决方法是是根据已已有样本本属性值值的先验验概率来来对样本本计算属属性值分分布百分分比在训练练时，，缺失失的属属性会会按照照其分分布百百分比比逐个个计算算。例如，，给定定一个个缺失失了颜颜色属属性值值的正正例，，它将将被视视为0.6个red正例例、0.2个blue正正例和和0.2个个green正正例。。2001年年6月月2日日测试时的值值缺失若属性值未未给出，则则设定为??(通配配符)，然然后多路径径到达叶结结点，最后后计算分类类结果的各各分类权重重例如，<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日日属性开销有些领域中中，某些属属性比其它它属性更容容易获取其其值(例如如病人的体体温比其胆胆固醇水平平更容易得得到)尽可能采用用那些低开开销的属性性来分类在信息增益益中增加属属性开销是是有效的:在不降低精精度的同时时降低了平平均开销2001年年6月2日日递增式的决决策树归纳纳ID4和ID5可以以递增更新新已有的树树ID4有时时会丢弃某某些实例，，不保证和和历史训练练样本一致致ID5则保保证和ID3的决策策相同ID4速度度快，但精精度降低ID5速度度较快且精精度不变2001年年6月2日日决策树中的的重复部分分决策树比DNF更复复杂，因为为它常常存存在重复部部分范范式必必须分解为为析取范式式，导致了了重复子树树的出现解决：使用用复杂特征征或决策图图构造性归纳纳：原子特特征的逻辑辑组合或算算术组合2001年年6月2日日边缘算法决策树构造造性归纳的的叠代算法法边缘算法（（总是沿着着树的边缘缘走）Until没有新新的特征被被创建或到到达限定值值do使使用用当前的所所有特征从从训练集构构造决策树树从从边缘末端端(正例)两个特征征的联合来来创建新特特征将将这些新新特征加入入现有特征征集中，同同时扩展每每个样本的的描述以包包含所有新新特征2001年年6月2日日边缘示例2001年年6月2日日多重模型学习概念的的多重候选选定义最终决策是是基于多个个学习模型型的(加权权)投票2001年年6月2日日装袋(Bagging)用训练集的的不同样本本来训练同同一个学习习者，来创创建多重模模型(Breiman,1996)给定训练集集大小为n，通过从从原始数据据取样(用用替换方法法)，创建建m个不同同的训练集集(大小为为n)用简单的投投票方法来来合并这m个模型可用于任何何学习方法法减少了不稳稳定学习算算法的一般般化错误，，即当训练练数据轻微微改动时会会导致决策策结果剧烈烈变动的那那些学习方方法2001年年6月2日日引导(Boosting)另一个生成成多重模型型的方法———重复更更改同一个个学习算法法的数据对弱学习算算法(假设设的精度只只要超过1/2即可可)能保证证性能的改改进对样本加权权，每次叠叠代产生