机器学习决策树学习

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

可表示任意析取和合取范式，从而表示任意离散函数和离散特征可将实例分到多个分类(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<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即可)能保证证性能的的改进对样本