决策树学习

决策树学习DecisionTreeLearning决策树的思维方式一个女孩的母亲要给这个女孩介绍男朋友，于是有了下面的对话：女儿：多大年纪了？母亲：26。女儿：长的帅不帅？母亲：挺帅的。女儿：收入高不？母亲：不算很高，中等情况。女儿：是公务员不？母亲：是，在税务局上班呢。女儿：那好，我去见见。2女孩心中的决策树34什么是决策树？对数据进行分类的树型数据结构非叶节点：分类属性叶节点：类别决策树的学习根据训练数据形成相应的决策树归纳学习监督学习积极学习决策树的使用按照决策树上的分类属性逐层往下划分，直到叶节点，即获得概念（决策、分类）结果。5决策树学习基本思想根据训练数据选择分类属性，逐层构造决策树学习核心：分类属性的选择决策树构造算法output训练数据集合决策树input6如何选择分类属性：教室中谁是考研同学学生属性（姓名、年龄、性别、衣服颜色、籍贯、专业、图书类型）书类型考研书Yes没带书NoVC、JSP、java，ASPNo英语书？7决策树算法概述根据训练数据找一分类属性，尽可能将数据集分成类别“纯净”子集（单一类别）若子集还不纯净，再找另一属性继续划分（递归过程）停止分类的条件1.数据子集纯净：节点上的数据均对应于同一类别2.所有属性都已使用过分类属性的选择：启发式或统计方法8决策树的构造：ID3算法ID3(Examples，Target_attribute，Attributes)ID3(实例，目标属性，参考属性)–Examples即训练样例集。–Target_attribute是这棵树要预测的目标属性。–Attributes是学习决策树所需参考属性列表。ID3算法Step1.创建树的root节点Step2.如果Examples都为正(反),返回label=正(反)的单节点树rootStep3.如果Attributes为空，返回单节点树root，label=Example中最普遍的目标概念值，否则递归执行属性选择与数据划分操作（见下页）910Step3Step3.1设A为Attributes中分类样例能力最好的属性Step3.2令root的决策属性为AStep3.3对于A的每个可能值vi在root下加一个新的分支，对应于A=vi令Examplesvi为样例中满足A属性值为vi的子集如果Examplesvi为空，在这个新分支下加一个叶节点，节点的label=Examples中最普遍的Target值否则（Examplesvi不为空）在新分支下加一个子树：ID3(Examplesvi,Target,Attributes-{A})Step4.返回root11星期六上午是否适合打网球汤姆家附近有了网球场，他经常去那里看网球比赛但网球比赛是否举行，要根据天气情况而定汤姆可不想白跑一趟汤姆刚上学习了机器学习课程于是，他根据自己手工记录数据，设计了一个自动判断器。12“星期六上午是否适合打网球”目标属性13问题分析已知一组实例,求目标函数:f(outlook,Temperature,humidity,wind)playTennis（yes/no）14分类属性选择构造好的决策树的关键在于如何选择属性。最常用分类属性选择指标：信息增益(InformationGain)从候选属性中选择属性信息增益大的属性，其划分子集的纯度高（平均熵值小），分类能力强选择信息增益最大的属性作为分类属性15熵熵是描述事物无序性的参数，熵越大则无序性越强。事件越不确定，熵越大。2014年世界杯冠军事件是确定的，熵等于0。2010年世界杯冠军熵刻划了信息的不确定性熵16信息熵与不确定性一条信息的信息熵大小和它的不确定性有直接的关系。比如说，我们要搞清楚一件非常非常不确定的事，或是我们一无所知的事情，就需要了解大量的信息。相反，如果我们对某件事已经有了较多的了解，我们不需要太多的信息就能把它搞清楚。所以，从这个角度，我们可以认为，信息熵的度量就等于不确定性的多少。信息熵越大，不确定性也越大。“世界杯最终32强中哪支球队是冠军”的信息熵假如由于某种缘故，我错过了看世界杯。赛后我问一个知道比赛结果的同事。“哪支球队是冠军？”他不愿意直接告诉我，而要让我猜，并且我每猜一次，他要收一元钱才肯告诉我是否猜对了；那么我需要付给他多少钱才能知道谁是冠军呢?我可以把球队编上号，从0到31，然后提问：“冠军的球队在0-15号中吗?”假如他告诉我猜对了，我会接着问：“冠军在0-7号中吗?”假如他告诉我猜错了，我自然知道冠军队在8-17中。这样只需要五次，我就能知道哪支球队是冠军；谁是世界杯冠军这条消息的信息量只值五块钱；17“谁是世界杯冠军”信息量香农用“比特”（bit）这个概念来度量不确定性。一个比特是一位二进制数，这条信息的熵是五比特。25=32181111119从信息论角度熵是编码这条信息所需二进制位的个数样例分布越平均（混乱），熵越大样例分布不均衡（变纯），熵减小yes/no问题的熵20用熵度量样例的均一性（纯度）二分类事件熵的定义举例21如果目标属性具有c个不同值（类别），那么S相对于c个状态（c-wise）的分类的熵定义为：ciiippSEntropy12log)(pi是S中属于类别i的比例n分类事件的熵“世界杯32强谁是冠军”这条信息Entropy(S)=32×（-1/32)log2(1/32）=522用信息增益度量期望熵最低•其中Values(A)是属性A所有可能值的集合，是S中属性A的值为v的子集（也就是，={sS|A(s)=v}）。•第一项就是原来集合S的熵•第二项是用A分类S后熵的期望值。这个第二项描述的期望熵就是每个子集的熵的加权和，权值为属于Sv的样例占原始样例S的比例。信息增益的作用：度量引入该属性后使得信息量增加，熵减少能力。信息增益较大的属性将具有更好的区分能力23熵与信息增益举例1++--+---+--+-+-++-+---Entropy（S）=-(9/22)log2（9/22)–(13/22)log2（13/22）=-0.409×(-0.388)-0.59×(-0.229)=0.158691*0.13511=0.021S=[9+,13-]24熵与信息增益举例1Entropy（S）Entropy（Sred）Entropy（Syellow）colorGain（S，Color）=Entropy（S）-(9/22Entropy（Sred）+13/22Entropy（Syellow）)++--+---+--+-+-++-+---25熵与信息增益举例226PlayTennis例目标属性PlayTennis：yes和no两个值任务：根据其他属性来预测这个目标属性值。先考虑这个算法的第一步，创建决策树的最顶端结点。哪一个属性该在树上第一个被测试呢？计算每一个候选属性（也就是Outlook，Temperature，Humidity，和Wind）的信息增益，然后选择信息增益最高的一个作为分类属性。27PlayTennis例940.0145log145149log14922SEntropyvStrongWeakvvSEntropySSWindSEntropy,,;no3,yes3:;no2,yes6:strongweakSS892.000.1146811.0148146148,strongweakSEntropySEntropyWindSEntropy2829PlayTennis例048.0892.0940.0,WindSGain同理可得：246.0,OutlookSGain151.0,HumiditySGain029.0,eTemperaturSGain将以Outlook作为根节点的属性，该属性将把数据划分为三个子集30Humidity对于非终端节点，递归执行上述划分过程，直至：1）达到目标概念；2）所有属性包含在相应路径中，从而得到最终结果31决策树例：根据天气情况确定是否打网球（PlayTennis=yesorno）32决策树的知识表达规则集形式：Rule1：IFOutlook=SunnyANDHumidity=NormalTHENYesRule2：IFOutlook=OvercastTHENYesRule3：IFOutlook=RainANDWind=StrongTHENYes谓词逻辑：33过学习（overfitting）问题：由于噪声数据的存在或者由于训练样例太少，致使学习后的决策树对训练数据分类精度很高，但对其它数据的分类精度反而降低From“MachineLearning”,T.M.Mitchell34决策树剪枝（pruning）通过剪枝降低树的复杂性，以解决过学习问题两种途径预先剪枝在树生成的过程中根据一定的准则（如树已达到某高度）来决定是否继续扩张树。后剪枝待决策树完全生成以后再进行剪枝。35用于剪枝的数据集与生成决策树数据集不同的数据例如使用训练集2/3的数据生成树，另外1/3的数据用于剪枝交叉验证将训练集T分成互不相交且大小相等的k个子集T1，T2，…，Tk。对任意子集Ti，用T-Ti训练决策树，用Ti测试决策树的分类精度。36剪枝准则期望错误率最小思想：使在未知数据上的期望错误率最小过程：对树中的非叶节点计算其剪枝/不剪枝可能出现的期望错误率，比较后加以取舍最小描述长度(MinimumDescriptionLength,MDL)思想：“如无必要，勿增实体”（奥坎姆剃刀原则）过程：对决策树进行编码，编码位数最少的树最优37一个决策树学习实例•一组数据：客户（年收入、有房、储蓄账户、信用水平）•训练：生成决策树（计算模型）•应用：预测新客户信用水平是好还是差，银行据此决定是否向客户发放贷款收入大于5万元/年是否有无储蓄帐户是否房主是是否否批准不批准批准38小结决策树分类数据的树型结构决策树生成根据训练数据获得相应决策树(ID3)决策树剪枝通过降低树的复杂性获得好的推广性(MDL)39练习利用信息增益从候选属性中选择属性，信息增益最高的属性作为决策属性。已知训练例子：big,red,circle:+small,red,circle:small,red,square:big,blue,circle:+big,red,square:+small,blue,square:特征向量：size,color,shape求该集合S的熵和属性size、color及shape的信息增益决策树的根节点是哪个属性？40解答121log2121log2122SEntropy41vbigsmallvvSEntropySSSizeSEntropy,,;no3,yes0:;no0,yes3:smallbigSS00210216363,smallbigSEntropySEntropySizeSEntropyGain(S,size)=Entropy(S)-Entropy(S,size)=142vbuleredvvSEntropySSColorSEntropy,,;no1,yes1:;no2,yes2:blueredSS11621646264,blueredSEntropySEntropyColorSEntropyGain(S,color)=Entropy(S)-Entropy(S,size)=1-1=043vsquarecirclevvSEntropySSShapeSEntropy,,;no2,yes1:;no1,yes2:squarecircleSS276.0)32log3231log31(63)31log3132log32(636363,2222