机器学习-决策树ID算法的实例解析

1、整理ppt决策树模型决策树模型整理ppt排名排名挖掘主题挖掘主题算法算法得票数得票数发表时间发表时间作者作者陈述陈述人人1分类C4.5611993Quinlan, J.RHiroshi Motoda2聚类k-Means 601967MacQueen, J.BJoydeep Ghosh3统计学习SVM 581995Vapnik, V.NQiangYang4关联分析Apriori 521994Rakesh Agrawal Christos Faloutsos5统计学习EM482000McLachlan, GJoydeep Ghosh 6链接挖掘PageRank461998Brin, S.Chris

2、tos Faloutsos7集装与推进AdaBoost451997Freund, Y.Zhi-Hua Zhou 8分类kNN451996Hastie, TVipin Kumar 9分类Nave Bayes452001Hand, D.JQiang Yang 10分类CART341984L.BreimanDan Steinberg 共有145人参加了ICDM 2006 Panel (会议的专题讨论),并对18种候选算法进行投票，选出了数据挖掘10大算法ICDM 2006会议的算法投票结果会议的算法投票结果整理ppt信息的定量描述信息的定量描述整理ppt信息量的定义根据客观事实和人们的习惯概念，函数

3、f(p)应满足以下条件：f(p)应是概率p的严格单调递减函数，即当p1p2， f(p1)f(p2)；当p=1时，f(p)=0；当p=0时，f(p)=；1.两个独立事件的联合信息量应等于它们分别的信息量之和。整理ppt整理ppt整理pptiiiiiixpxpxIxpXH)(log)()()()(整理ppt b1) 5 . 0log5 . 05 . 0log5 . 0(log1iqiixpxpxH整理ppt b/symbol811. 0)4/1log4/34/1log4/1 (log1iqiixpxpxH整理ppt例：气象预报整理ppt12条件自信息量在事件yj出现的条件下，随机事件xi发生的条件

4、概率为p(xi | yj) ，则它的条件自信息量定义为条件概率对数的负值：)|(log)|(jijiyxpyxI整理ppt13条件熵条件熵在给定yj条件下，xi的条件自信息量为I(xi| yj), X集合的条件熵H(X|yj)为 在给定Y(即各个yj )条件下,X集合的条件熵H(X|Y)条件熵H(X|Y)表示已知Y后，X的不确定度整理ppt是否适合打垒球的决策表天气天气温度温度湿度湿度风速风速活动活动晴炎热高弱取消晴炎热高强取消阴炎热高弱进行雨适中高弱进行雨寒冷正常弱进行雨寒冷正常强取消阴寒冷正常强进行晴适中高弱取消晴寒冷正常弱进行雨适中正常弱进行晴适中正常强进行阴适中高强进行阴炎热正常弱进行

5、雨适中高强取消整理ppt是否进行垒球活动进行取消晴阴雨晴阴雨进行取消整理ppt活动的熵活动有2个属性值，进行，取消。其熵为：H(活动) = - (9/14)*log (9/14) - (5/14)*log (5/14) = 0.94进行取消整理ppt已知户外户外的天气情况下活动的条件熵户外户外有三个属性值，晴，阴和雨。其熵分别为：H(活动|户外=晴) = - (2/5)*log2(2/5) - (3/5)*log2(3/5) = 0.971H(活动|户外=阴) = - (4/4)*log2(4/4) = 0H(活动|户外=雨) = - (3/5)*log2(3/5)- (2/5)*log2(2

6、/5) = 0.971进行取消晴阴雨整理ppt已知户外户外时时活动的条件熵H(活动|户外)=5/14*H(活动|户外=晴)+4/14*H(活动|户外=阴) +5/14* H(活动|户外=雨)= (5/14)*0.971 + (4/14)*0 +(5/14)*0.971= 0.693晴阴雨整理ppt平均互信息I(活动;户外户外) = H(活动) - H(活动|户外) = 0.94- 0.693 = 0.246整理ppt是否适合打垒球的决策表天气天气温度温度湿度湿度风速风速活动活动晴炎热高弱取消晴炎热高强取消阴炎热高弱进行雨适中高弱进行雨寒冷正常弱进行雨寒冷正常强取消阴寒冷正常强进行晴适中高弱取消

7、晴寒冷正常弱进行雨适中正常弱进行晴适中正常强进行阴适中高强进行阴炎热正常弱进行雨适中高强取消整理ppt活动的熵H(活动) = - (9/14)*lb (9/14) - (5/14)*lb (5/14) = 0.94天气天气 温度温度 湿度湿度 风速风速 活动活动 阴 炎热 高 弱 进行 雨 适中 高 弱 进行 雨 寒冷 正常 弱 进行 阴 寒冷 正常 强 进行 晴 寒冷 正常 弱 进行 雨 适中 正常 弱 进行 晴 适中 正常 强 进行 阴 适中 高 强 进行 阴 炎热 正常 弱 进行 晴 炎热 高 弱 取消 晴 炎热 高 强 取消 雨 寒冷 正常 强 取消 晴 适中 高 弱 取消 雨 适中

8、高 强 取消 整理ppt已知天气时活动的条件熵H(活动|天气天气)=5/14*H(活动|天气天气=晴)+4/14*H(活动|天气天气=阴) +5/14* H(活动|天气天气=雨)= (5/14)*0.971 + (4/14)*0 +(5/14)*0.971= 0.693温度温度 湿度湿度 风速风速 天气天气 活动活动 寒冷 正常 弱 晴 进行 适中 正常 强 晴 进行 炎热 高 弱 晴 取消 炎热 高 强 晴 取消 适中 高 弱 晴 取消 炎热 高 弱 阴 进行 寒冷 正常 强 阴 进行 适中 高 强 阴 进行 炎热 正常 弱 阴 进行 适中 高 弱 雨 进行 寒冷 正常 弱 雨 进行 适中

9、正常 弱 雨 进行 寒冷 正常 强 雨 取消 适中 高 强 雨 取消 整理ppt天气天气 湿度湿度 风速风速 温度温度 活动活动 阴 高 弱 炎热 进行 阴 正常 弱 炎热 进行 晴 高 弱 炎热 取消 晴 高 强 炎热 取消 雨 高 弱 适中 进行 雨 正常 弱 适中 进行 晴 正常 强 适中 进行 阴 高 强 适中 进行 晴 高 弱 适中 取消 雨 高 强 适中 取消 雨 正常 弱 寒冷 进行 阴 正常 强 寒冷 进行 晴 正常 弱 寒冷 进行 雨 正常 强 寒冷 取消 已知温度时活动的条件熵H(活动|温度) = 0.911整理ppt天气天气 温度温度 风速风速 湿度湿度 活动活动 阴 炎

10、热 弱 高 进行 雨 适中 弱 高 进行 阴 适中 强 高 进行 晴 炎热 弱 高 取消 晴 炎热 强 高 取消 晴 适中 弱 高 取消 雨 适中 强 高 取消 雨 寒冷 弱 正常 进行 阴 寒冷 强 正常 进行 晴 寒冷 弱 正常 进行 雨 适中 弱 正常 进行 晴 适中 强 正常 进行 阴 炎热 弱 正常 进行 雨 寒冷 强 正常 取消 H(活动|湿度) = 0.789已知湿度时活动的条件熵整理ppt天气天气 温度温度 湿度湿度 风速风速 活动活动 阴 寒冷 正常 强 进行 晴 适中 正常 强 进行 阴 适中 高 强 进行 晴 炎热 高 强 取消 雨 寒冷 正常 强 取消 雨 适中 高 强

11、 取消 阴 炎热 高 弱 进行 雨 适中 高 弱 进行 雨 寒冷 正常 弱 进行 晴 寒冷 正常 弱 进行 雨 适中 正常 弱 进行 阴 炎热 正常 弱 进行 晴 炎热 高 弱 取消 晴 适中 高 弱 取消 H(活动|风速) = 0.892已知风速时活动的条件熵整理ppt各互信息量I(活动活动;天气天气) = H(活动活动) - H(活动活动|天气天气) = 0.94- 0.693 = 0.246I(活动活动;温度) = H(活动活动) - H(活动|温度) = 0.94- 0.911 = 0.029I(活动活动;湿度) = H(活动活动) - H(活动|湿度) = 0.94- 0.789 =

12、 0.151I(活动活动;风速) = H(活动活动) - H(活动|风速) = 0.94- 0.892 = 0.048整理ppt天气天气温度温度湿度湿度风速风速活动活动晴炎热高弱取消晴炎热高强取消阴炎热高弱进行雨适中高弱进行雨寒冷正常弱进行雨寒冷正常强取消阴寒冷正常强进行晴适中高弱取消晴寒冷正常弱进行雨适中正常弱进行晴适中正常强进行阴适中高强进行阴炎热正常弱进行雨适中高强取消温度温度 湿度湿度 风速风速 活动活动 寒冷 正常 弱 进行 适中 正常 强 进行 炎热 高 弱 取消 炎热 高 强 取消 适中 高 弱 取消 温度温度 湿度湿度 风速风速 活动活动 适中 高 弱 进行 寒冷 正常 弱 进

13、行 适中 正常 弱 进行 寒冷 正常 强 取消 适中 高 强 取消 温度 湿度 风速 活动 炎热 高 弱 进行 寒冷 正常 强 进行 适中 高 强 进行 炎热 正常 弱 进行 阴晴雨天气天气 温度温度 湿度湿度 风速风速 活动活动 晴 寒冷 正常 弱 进行 晴 适中 正常 强 进行 晴 炎热 高 弱 取消 晴 炎热 高 强 取消 晴 适中 高 弱 取消 阴 炎热 高 弱 进行 阴 寒冷 正常 强 进行 阴 适中 高 强 进行 阴 炎热 正常 弱 进行 雨 适中 高 弱 进行 雨 寒冷 正常 弱 进行 雨 适中 正常 弱 进行 雨 寒冷 正常 强 取消 雨 适中 高 强 取消 整理pptID3算

14、法生成的决策树整理pptID3算法ID3(A:条件属性集合，d:决策属性，U:训练集)返回一棵决策树if U为空，返回一个值为Failure的单结点；/一般不会出现这种情况，为了程序的健壮性if U是由其值均为相同决策属性值的记录组成，返回一个带有该值的单结点；/此分支至此结束if A为空，则返回一个单结点，其值为在U的记录中找出的频率最高的决策属性值；/这时对记录将出现误分类将A中属性之间具有最大I(d;a)的属性赋给a；将属性a的值赋给aj|j=1,2,m；将分别由对应于a的值的aj的记录组成的U的子集赋值给uj|j=1,2,m；返回一棵树，其根标记为a，树枝标记为a1, a2, am；再

15、分别构造以下树：ID3(A-a,d,u1)，ID3(A-a,d,u2)，ID3(A-a,d,um)；/递归算法2003.11.18整理ppt30决策树学习的常见问题决策树学习的实际问题确定决策树增长的深度处理连续值的属性选择一个适当的属性筛选度量标准处理属性值不完整的训练数据处理不同代价的属性提高计算效率针对这些问题，ID3被扩展成C4.52003.11.18整理ppt31避免过度拟合数据过度拟合对于一个假设，当存在其他的假设对训练样例的拟合比它差，但事实上在实例的整个分布上表现得却更好时，我们说这个假设过度拟合训练样例定义：给定一个假设空间H，一个假设hH，如果存在其他的假设hH，使得在训练

16、样例上h的错误率比h小，但在整个实例分布上h的错误率比h小，那么就说假设h过度拟合训练数据。2003.11.18整理ppt32避免过度拟合数据（2）导致过度拟合的原因一种可能原因是训练样例含有随机错误或噪声当训练数据没有噪声时，过度拟合也有可能发生，特别是当少量的样例被关联到叶子节点时，很可能出现巧合的规律性，使得一些属性恰巧可以很好地分割样例，但却与实际的目标函数并无关系。整理ppt33避免过度拟合数据（3）避免过度拟合的方法及早停止树增长后修剪法两种方法的特点第一种方法更直观第一种方法中，精确地估计何时停止树增长很困难第二种方法被证明在实践中更成功2003.11.18整理ppt34避免过度

17、拟合数据（4）避免过度拟合的关键使用什么样的准则来确定最终正确树的规模解决方法使用与训练样例截然不同的一套分离的样例，来评估通过后修剪方法从树上修建节点的效用。使用所有可用数据进行训练，但进行统计测试来估计扩展（或修剪）一个特定的节点是否有可能改善在训练集合外的实例上的性能。使用一个明确的标准来衡量训练样例和决策树的复杂度，当这个编码的长度最小时停止树增长。2003.11.18整理ppt35避免过度拟合数据（5）方法评述第一种方法是最普通的，常被称为训练和验证集法。可用数据分成两个样例集合：训练集合，形成学习到的假设验证集合，评估这个假设在后续数据上的精度方法的动机：即使学习器可能会被训练集合

18、误导，但验证集合不大可能表现出同样的随机波动验证集合应该足够大，以便它本身可提供具有统计意义的实例样本。常见的做法是，样例的三分之二作训练集合，三分之一作验证集合。2003.11.18整理ppt36错误率降低修剪将树上的每一个节点作为修剪得候选对象修剪步骤删除以此节点为根的子树，使它成为叶结点把和该节点关联的训练样例的最常见分类赋给它反复修剪节点，每次总是选取那些删除后可以最大提高决策树在验证集合上的精度的节点继续修剪，直到进一步的修剪是有害的为止数据分成3个子集训练样例，形成决策树验证样例，修剪决策树测试样例，精度的无偏估计如果有大量的数据可供使用，那么使用分离的数据集合来引导修剪2003.

19、11.18整理ppt37规则后修剪从训练集合推导出决策树，增长决策树直到尽可能好地拟合训练数据，允许过度拟合发生将决策树转化为等价的规则集合，方法是为从根节点到叶节点的每一条路径创建一条规则通过删除任何能导致估计精度提高的前件来修剪每一条规则按照修剪过的规则的估计精度对它们进行排序，并按这样的顺序应用这些规则来分类后来的实例2003.11.18整理ppt38规则后修剪（2）例子if (outlook=sunny)(Humidity=High) then PlayTennis=No考虑删除先行词(outlook=sunny)和(Humidity=High)选择使估计精度有最大提升的步骤考虑修剪第

20、二个前件2003.11.18整理ppt39规则后修剪（3）规则精度估计方法使用与训练集不相交的验证集基于训练集合本身被C4.5使用，使用一种保守估计来弥补训练数据有利于当前规则的估计偏置过程先计算规则在它应用的训练样例上的精度然后假定此估计精度为二项式分布，并计算它的标准差对于一个给定的置信区间，采用下界估计作为规则性能的度量评论对于大的数据集，保守预测非常接近观察精度，随着数据集合的减小，离观察精度越来越远不是统计有效，但是实践中发现有效2003.11.18整理ppt40规则后修剪（4）把决策树转化成规则集的好处可以区分决策节点使用的不同上下文消除了根节点附近的属性测试和叶节点附近的属性测试

21、的区别提高了可读性2003.11.18整理ppt41合并连续值属性ID3被限制为取离散值的属性学习到的决策树要预测的目标属性必须是离散的树的决策节点的属性也必须是离散的简单删除上面第2个限制的方法通过动态地定义新的离散值属性来实现，即先把连续值属性的值域分割为离散的区间集合2003.11.18整理ppt42合并连续值属性（2）例子，Temperature应该定义什么样的基于阈值的布尔属性选择产生最大信息增益的阈值按照连续属性排列样例，确定目标分类不同的相邻实例产生一组候选阈值，它们的值是相应的A值之间的中间值可以证明产生最大信息增益的c值位于这样的边界中（Fayyad1991）通过计算与每个候

22、选阈值关联的信息增益评估这些候选值方法的扩展连续的属性分割成多个区间，而不是单一阈值的两个空间2003.11.18整理ppt43小结和补充读物决策树学习为概念学习和学习其他离散值的函数提供了一个实用的方法ID3算法贪婪算法从根向下推断决策树搜索完整的假设空间归纳偏置，较小的树过度拟合问题ID3算法的扩展2003.11.18整理ppt44附录C4.5 is a software extension of the basic ID3 algorithm designed by Quinlan to address the following issues not dealt with by ID3

23、: Avoiding overfitting the data Determining how deeply to grow a decision tree. Reduced error pruning. Rule post-pruning. Handling continuous attributes. e.g., temperature Choosing an appropriate attribute selection measure. Handling training data with missing attribute values. Handling attributes w

24、ith differing costs. Improving computational efficiency. 整理ppt分类器评价标准预测准确度计算复杂度模型描述的简洁度：产生式规则整理ppt准确度分析一般采用召回率r(Recall)和精准率p(Precision)这两个指标衡量分类器的准确度。个好的分类器应同时具有较高的召回率和精准率，当然这两个指标一般情况下是互斥的，有时要根据需要在这两个指标间作某种权衡和妥协。整理ppt召回率r(Recall)和精准率p(Precision)为了定义这两个指标，引入分类中常用的两个基本概念，Relevant和Retrieved。Relevant：真正属于某类的集合Retrieved：判断属于某类的集合召回率反映了分类器正确分类的对