10.决策树学习

1机器学习—决策树学习2•决策树学习概述•决策树学习的适用问题•决策树建树算法•决策树学习中的假设空间搜索•决策树学习的归纳偏置•决策树学习的常见问题OUTLINE3决策树学习概述•决策树归纳是归纳学习算法中最简单也是最成功的算法之一——好的入门•决策树以事物的属性描述集合作为输入，输出通常是一个分类(离散的输出)——一般是二值分类(真或假)，是一种逼近离散值函数的方法4决策树学习示例•例子：星期六上午是否适合打网球–属性={outlook，Temperature,humidity，wind}–属性值={sunny,overcast,rain,hot,mild,cool,high,normal,strong,weak}5决策树学习示例——训练样例DayOutlookTemperatureHumidityWindPlayTennisD1SunnyHotHighWeaknoD2SunnyHotHighStrongnoD3OvercastHotHighWeakyesD4RainMildHighWeakyesD5RainCoolNormalWeakyesD6RainCoolNormalStrongnoD7OvercastCoolNormalStrongyesD8SunnyMildHighWeaknoD9SunnyCoolNormalWeakyesD10RainMildNormalWeakyesD11SunnyMildNormalStrongyesD12OvercastMildHighStrongyesD13OvercastHotNormalWeakyesD14RainMildHighStrongno返回6决策树学习示例——决策树表示•决策树–通过把实例从根节点排列到某个叶子节点来分类实例–叶子节点即为实例所属的分类–树上每个节点说明了对实例的某个属性的测试–节点的每个后继分支对应于该属性的一个可能值HighNormalStrongWeakOutlookWindHumiditySunnyOvercastRainYesNoYesNoYes7OutlookWindHumiditySunnyOvercastRainHighNormalStrongWeakYesNoYesNoYes决策树学习示例——决策树未见实例:Outlook=Sunny,Temp=Warm,humidity=high,Wind=Strong8决策树学习示例——决策树表示•决策树代表实例属性值约束的合取的析取式。从树根到树叶的每一条路径对应一组属性测试的合取，树本身对应这些合取的析取HighNormalStrongWeakOutlookWindHumiditySunnyOvercastRainYesNoYesNoYes9HighNormalStrongWeakOutlookWindHumiditySunnyOvercastRainYesNoYesNoYes决策树学习示例——决策树表示上面决策树对应于以下表达式:（Outlook=sunny∧Humidity=normal）∨（Outlook=overcast)∨（Outlook=rain∧Wind=weak)10•决策树学习概述•决策树学习的适用问题•决策树建树算法•决策树学习中的假设空间搜索•决策树学习的归纳偏置•决策树学习的常见问题OUTLINE11决策树学习的适用问题•决策树适合具有以下特征的学习：–实例是由“属性-值”对表示的——固定的属性+离散或连续的取值–目标函数具有离散的输出值–析取表达式–训练数据可以包含错误——决策树学习的鲁棒性好–训练数据可以包含缺少属性值的实例•问题举例–根据疾病分类患者–根据起因分类设备故障•分类问题–核心任务是把样例分类到各可能的离散值对应的类别12•决策树学习概述•决策树学习的适用问题•决策树建树算法•决策树学习中的假设空间搜索•决策树学习的归纳偏置•决策树学习的常见问题OUTLINE13决策树建树算法•决策树学习包括2个步骤：–从实例中归纳出决策树(建立决策树)–利用决策树对新实例进行分类判断•如何建立决策树：–大多数决策树学习算法是一种核心算法的变体–采用自顶向下的贪婪搜索遍历可能的决策树空间–ID3是这种算法的代表14决策树建树算法（1）•ID3算法的基本思想：–自顶向下构造决策树–从“哪一个属性将在树的根节点被测试”开始–使用统计测试来确定每一个实例属性单独分类训练样例的能力15决策树建树算法（2）•ID3算法的构造过程–初始时，决策树根节点包括所有的训练样例–分类能力最好的属性被选作树的根节点–根节点的每个可能值产生一个分支，训练样例排列到适当的分支–对于每一个分支，重复上面的过程•算法的终止条件：–所有的属性已经被这条路经包括；–与这个节点关联的所有训练样例都具有相同的目标属性值（即它们的熵为0）16决策树建树算法（3）ID3(Examples,Target_attribute,Attributes)•创建树的root节点•如果Examples都为正,返回label=+的单节点树root•如果Examples都为反,返回label=-的单节点树root•如果Attributes为空，那么返回单节点root，label=Examples中最普遍的Target_attribute值•否则开始–AAttributes中分类examples能力最好的属性–root的决策属性A–对于A的每个可能值vi•在root下加一个新的分支对应测试A=vi•令Examplesvi为Examples中满足A属性值为vi的子集•如果Examplesvi为空–在这个新分支下加一个叶子节点，节点的label=Examples中最普遍的Target_attribute值–否则在新分支下加一个子树ID3（Examplesvi,Target_attribute,Attributes-{A}）•结束•返回root17属性选择•决策树中的每个节点都代表一定的属性，这些属性如何在决策树中排布是值得认真研究的—决策树建树算法中的属性选择方案的目标是为了最小化最终树的深度，从而使用尽可能少的判断步骤来分类某个实例•在决策树算法中，属性排序以信息论中的熵概念为理论基础—属性提供的期望信息量18熵与不确定性•信息论中用熵表示事物的不确定性，同时也是信息含量的表示——熵值越大，表示不确定性越大，同时信息量越多；反之则不确定性越小，信息量越小19熵和决策树•Quinlan于1983年提出决策树算法ID3时使用熵的概念来提高决策树分类的效率：–开始，决策树的树根对应于最大的不确定状态，表示在分类之前对被分类的对象一无所知–随着每个属性的不断判断，向树的叶子方向前进，即相当于选择了其中的一棵子树，其不确定状态就减小了–到达叶子节点，分类完成，此时不确定性为零20•要提高决策树的分类效率，就相当于要求熵值下降的更快/这样，ID3算法的实质就是构造一棵熵值下降平均最快的决策树•熵值下降表明不确定性减小的思想可以应用到许多情况，例如：自然语言中的各种歧义是一种不确定性，而从不确定性走向确定性就是歧义减小/如果不确定性消失也就是熵值为零，则说明已经消除了歧义，选择了某个明确的符号表示/因此可以应用决策树算法来消歧熵和决策树（2）21熵和决策树（3）•用熵度量样例的均一性–熵刻画了任意样例集的纯度–给定包含关于某个目标概念的正反样例的样例集S，那么S相对这个布尔型分类的熵为–更一般地，如果目标属性具有c个不同的值，那么S相对于c个状态的分类的熵定义为)(log)(log)(020121ppppSEntropy其中，p1是在S中正例的比例，p0是在S中反例的比例ciiippSEntropy12)(log)(22熵和决策树（4）•熵值计算举例：例如：“PlayTennis”中S是一个关于某布尔概念的14个样例的集合，包括9个正例和5个反例[9+，5-]。那么S相对于这个布尔分类的熵为：训练数据集940.0)14/5(log14/5)14/9(log)14/9(])5,9([22Entropy23熵和决策树——熵函数变化曲线•熵值分析：–如果S的所有成员属于同一类，那么S的熵为0–如果S中正反样例的数量相等时（或者：S中各类样例等比例时），熵值为1–如果S集合中正反例的数量不等时，熵介于0和1之间24信息增益•用信息增益度量期望的熵降低–属性的信息增益（属性分类训练数据的能力的度量标准），由于使用这个属性分割样例而导致的期望熵降低–一个属性A相对样例集合S的信息增益Gain(S,A)为：)()(),()(vAValuesvvSEntropySSSEntropyASGain其中，Values(A)是属性A所有可能值得集合，Sv是S中属性A的值为v的子集上述等式中：第一项为原集合S的熵，第二项是用A分类S后熵的期望值即每个子集的熵的加权和。25•上式中第二项的值应该越小越好，因为越小说明S相对于属性A作分解以后而造成的熵下降越快（根据前面的解释，熵下降越快就是不确定性减少越快），换句话说Gain(S,A)越大越好•决策树建树算法的要点是——在构造决策树的每一层次时，从尚未检测的属性中选择信息增益Gain(S,A)大的属性进行分解信息增益（1）26举例——PlayTennis•学习任务：星期六上午是否适合打网球•目标函数PlayTennis具有yes和no两个值，我们将根据其它属性来预测这个目标函数值•决策树建树算法第一步，创建决策树的最顶端节点：哪个属性在树上第一个被测试呢？ID3算法计算每一个候选属性（Outlook,Temperature,Humidity和Wind）的信息增益，然后选择信息增益最高的一个。27举例——PlayTennis（1）•计算属性Wind的信息增益–Values(Wind)=Weak,StrongS=[9+,5-]Sweak=[6+,2-]Sstrong=[3+,3-]–信息增益)()(),(},{vstrongweakvvSEntropySSSEntropyWindSGain=Entropy(S)-(8/14)Entropy(Sweak)-(6/14)Entropy(Sstrong)=0.940-(8/14)0.811-(6/14)1.00=0.048S:[9+,5]E=0.940windweakstrong[6+,2][3+,3]E=0.811E=1.00Gain(S,Wind)=0.940(8/14)0.811(6/14)1.028举例——PlayTennis（2）•同理，其它属性的信息增益–Gain(S,Outlook)=0.246–Gain(S,Humidity)=0.151–Gain(S,Wind)=0.048–Gain(S,Temperature)=0.029根据信息增益标准，属性Outlook在训练样例上提供了对目标函数PlayTennis的最好预测。所以，Outlook被选作根节点的决策属性，并为它的每一个可能值在根节点下创建分支。29举例——PlayTennis（3）{D1,D2,…,D14}S:[9+,5]OutlookSunnyOvercastRain{D3,D7,D12,D13}[4+,0]{D1,D2,D8,D9,D11}[2+,3]{D4,D5,D6,D10,D14}[3+,2]?哪一个属性应在这里被测试Yes?•Ssunny={D1,D2,D8,D9,D11}–Gain(Ssunny,Humidity)=0.970-(3/5)0.0-(2/5)0.0=0.970–Gain(Ssunny,Temperature)=0.970-(2/5)0.0-(2/5)1.0-(1/5)0.0=0.570–Gain(Ssunny,Wind)=0.970-(2/5)1.0-(3/5)0.918=0.01930举例——PlayTennis（4）•上述决策树构建的终止条件：–所有的属性已经被这条路经包括；–与这个节点关联的所