08-2第八章机器学习-决策树ID3算法的实例解析

决策树模型排名挖掘主题算法得票数发表时间作者陈述人1分类C4.5611993Quinlan,J.RHiroshiMotoda2聚类k-Means601967MacQueen,J.BJoydeepGhosh3统计学习SVM581995Vapnik,V.NQiangYang4关联分析Apriori521994RakeshAgrawalChristosFaloutsos5统计学习EM482000McLachlan,GJoydeepGhosh6链接挖掘PageRank461998Brin,S.ChristosFaloutsos7集装与推进AdaBoost451997Freund,Y.Zhi-HuaZhou8分类kNN451996Hastie,TVipinKumar9分类NaïveBayes452001Hand,D.JQiangYang10分类CART341984L.BreimanDanSteinberg共有145人参加了ICDM2006Panel(会议的专题讨论),并对18种候选算法进行投票，选出了数据挖掘10大算法ICDM2006会议的算法投票结果信息的定量描述衡量信息多少的物理量称为信息量。若概率很大，受信者事先已有所估计，则该消息信息量就很小；若概率很小，受信者感觉很突然，该消息所含信息量就很大。信息量的定义根据客观事实和人们的习惯概念，函数f(p)应满足以下条件：1.f(p)应是概率p的严格单调递减函数，即当p1p2，f(p1)f(p2)；2.当p=1时，f(p)=0；3.当p=0时，f(p)=∞；4.两个独立事件的联合信息量应等于它们分别的信息量之和。对信息量的认识理解信息量的定义若一个消息x出现的概率为p，则这一消息所含的信息量为其中，对数的底大于1信息量单位以2为底时，单位为bit（binaryunit，比特）以e为底时，单位为nat（naturalunit，奈特）以10为底时，单位为hart（Hartley，哈特）pIlog抛一枚均匀硬币，出现正面与反面的信息量是多少？解：出现正面与反面的概率均为0.5，它们的信息量是I(正)=-lbp(正)=-lb0.5=1bI(反)=-lbp(反)=-lb0.5=1b抛一枚畸形硬币，出现正面与反面的概率分别是1/4，3/4，出现正面与反面时的信息量是多少？解：出现正面与反面的概率分别是1/4，3/4，它们的信息量是I(正)=-lbp(正)=-lb1/4=2bI(反)=-lbp(反)=-lb3/4=0.415b信源含有的信息量是信源发出的所有可能消息的平均不确定性，香农把信源所含有的信息量称为信息熵，是指每个符号所含信息量的统计平均值。m种符号的平均信息量为iiiiiixpxpxIxpXH)(log)()()()(抛一枚均匀硬币的信息熵是多少？解：出现正面与反面的概率均为0.5，信息熵是b1)5.0log5.05.0log5.0(log1iqiixpxpxH抛一枚畸形硬币，出现正面与反面的概率分别是1/4，3/4，出现正面与反面时的信息量是多少？解：出现正面与反面的概率分别是1/4，3/4，信息熵是b/symbol811.0)4/1log4/34/1log4/1(log1iqiixpxpxH例：气象预报8/18/14/12/1)(小雨大雨阴晴xpX12条件自信息量在事件yj出现的条件下，随机事件xi发生的条件概率为p(xi|yj)，则它的条件自信息量定义为条件概率对数的负值：)|(log)|(jijiyxpyxI13条件熵在给定yj条件下，xi的条件自信息量为I(xi|yj),X集合的条件熵H(X|yj)为)|()|()|(jiijijyxIyxpyXH–在给定Y(即各个yj)条件下,X集合的条件熵H(X|Y))|()()|(jjjyXHypYXH条件熵H(X|Y)表示已知Y后，X的不确定度是否适合打垒球的决策表天气温度湿度风速活动晴炎热高弱取消晴炎热高强取消阴炎热高弱进行雨适中高弱进行雨寒冷正常弱进行雨寒冷正常强取消阴寒冷正常强进行晴适中高弱取消晴寒冷正常弱进行雨适中正常弱进行晴适中正常强进行阴适中高强进行阴炎热正常弱进行雨适中高强取消是否进行垒球活动进行取消晴阴雨晴阴雨进行取消活动的熵活动有2个属性值，进行，取消。其熵为：H(活动)=-(9/14)*log(9/14)-(5/14)*log(5/14)=0.94进行取消已知户外的天气情况下活动的条件熵户外有三个属性值，晴，阴和雨。其熵分别为：H(活动|户外=晴)=-(2/5)*log2(2/5)-(3/5)*log2(3/5)=0.971H(活动|户外=阴)=-(4/4)*log2(4/4)=0H(活动|户外=雨)=-(3/5)*log2(3/5)-(2/5)*log2(2/5)=0.971进行取消晴阴雨已知户外时活动的条件熵H(活动|户外)=5/14*H(活动|户外=晴)+4/14*H(活动|户外=阴)+5/14*H(活动|户外=雨)=(5/14)*0.971+(4/14)*0+(5/14)*0.971=0.693晴阴雨平均互信息I(活动;户外)=H(活动)-H(活动|户外)=0.94-0.693=0.246是否适合打垒球的决策表天气温度湿度风速活动晴炎热高弱取消晴炎热高强取消阴炎热高弱进行雨适中高弱进行雨寒冷正常弱进行雨寒冷正常强取消阴寒冷正常强进行晴适中高弱取消晴寒冷正常弱进行雨适中正常弱进行晴适中正常强进行阴适中高强进行阴炎热正常弱进行雨适中高强取消活动的熵H(活动)=-(9/14)*lb(9/14)-(5/14)*lb(5/14)=0.94天气温度湿度风速活动阴炎热高弱进行雨适中高弱进行雨寒冷正常弱进行阴寒冷正常强进行晴寒冷正常弱进行雨适中正常弱进行晴适中正常强进行阴适中高强进行阴炎热正常弱进行晴炎热高弱取消晴炎热高强取消雨寒冷正常强取消晴适中高弱取消雨适中高强取消已知天气时活动的条件熵H(活动|天气)=5/14*H(活动|天气=晴)+4/14*H(活动|天气=阴)+5/14*H(活动|天气=雨)=(5/14)*0.971+(4/14)*0+(5/14)*0.971=0.693温度湿度风速天气活动寒冷正常弱晴进行适中正常强晴进行炎热高弱晴取消炎热高强晴取消适中高弱晴取消炎热高弱阴进行寒冷正常强阴进行适中高强阴进行炎热正常弱阴进行适中高弱雨进行寒冷正常弱雨进行适中正常弱雨进行寒冷正常强雨取消适中高强雨取消天气湿度风速温度活动阴高弱炎热进行阴正常弱炎热进行晴高弱炎热取消晴高强炎热取消雨高弱适中进行雨正常弱适中进行晴正常强适中进行阴高强适中进行晴高弱适中取消雨高强适中取消雨正常弱寒冷进行阴正常强寒冷进行晴正常弱寒冷进行雨正常强寒冷取消已知温度时活动的条件熵H(活动|温度)=0.911天气温度风速湿度活动阴炎热弱高进行雨适中弱高进行阴适中强高进行晴炎热弱高取消晴炎热强高取消晴适中弱高取消雨适中强高取消雨寒冷弱正常进行阴寒冷强正常进行晴寒冷弱正常进行雨适中弱正常进行晴适中强正常进行阴炎热弱正常进行雨寒冷强正常取消H(活动|湿度)=0.789已知湿度时活动的条件熵天气温度湿度风速活动阴寒冷正常强进行晴适中正常强进行阴适中高强进行晴炎热高强取消雨寒冷正常强取消雨适中高强取消阴炎热高弱进行雨适中高弱进行雨寒冷正常弱进行晴寒冷正常弱进行雨适中正常弱进行阴炎热正常弱进行晴炎热高弱取消晴适中高弱取消H(活动|风速)=0.892已知风速时活动的条件熵各互信息量I(活动;天气)=H(活动)-H(活动|天气)=0.94-0.693=0.246I(活动;温度)=H(活动)-H(活动|温度)=0.94-0.911=0.029I(活动;湿度)=H(活动)-H(活动|湿度)=0.94-0.789=0.151I(活动;风速)=H(活动)-H(活动|风速)=0.94-0.892=0.048天气温度湿度风速活动晴炎热高弱取消晴炎热高强取消阴炎热高弱进行雨适中高弱进行雨寒冷正常弱进行雨寒冷正常强取消阴寒冷正常强进行晴适中高弱取消晴寒冷正常弱进行雨适中正常弱进行晴适中正常强进行阴适中高强进行阴炎热正常弱进行雨适中高强取消温度湿度风速活动寒冷正常弱进行适中正常强进行炎热高弱取消炎热高强取消适中高弱取消温度湿度风速活动适中高弱进行寒冷正常弱进行适中正常弱进行寒冷正常强取消适中高强取消温度湿度风速活动炎热高弱进行寒冷正常强进行适中高强进行炎热正常弱进行阴晴雨天气温度湿度风速活动晴寒冷正常弱进行晴适中正常强进行晴炎热高弱取消晴炎热高强取消晴适中高弱取消阴炎热高弱进行阴寒冷正常强进行阴适中高强进行阴炎热正常弱进行雨适中高弱进行雨寒冷正常弱进行雨适中正常弱进行雨寒冷正常强取消雨适中高强取消ID3算法生成的决策树ID3算法ID3(A:条件属性集合，d:决策属性，U:训练集)返回一棵决策树{ifU为空，返回一个值为Failure的单结点；//一般不会出现这种情况，为了程序的健壮性ifU是由其值均为相同决策属性值的记录组成，返回一个带有该值的单结点；//此分支至此结束ifA为空，则返回一个单结点，其值为在U的记录中找出的频率最高的决策属性值；//这时对记录将出现误分类将A中属性之间具有最大I(d;a)的属性赋给a；将属性a的值赋给{aj|j=1,2,…,m}；将分别由对应于a的值的aj的记录组成的U的子集赋值给{uj|j=1,2,…,m}；返回一棵树，其根标记为a，树枝标记为a1,a2,…,am；再分别构造以下树：ID3(A-{a},d,u1)，ID3(A-{a},d,u2)，…，ID3(A-{a},d,um)；//递归算法}2003.11.1830决策树学习的常见问题决策树学习的实际问题确定决策树增长的深度处理连续值的属性选择一个适当的属性筛选度量标准处理属性值不完整的训练数据处理不同代价的属性提高计算效率针对这些问题，ID3被扩展成C4.52003.11.1831避免过度拟合数据过度拟合对于一个假设，当存在其他的假设对训练样例的拟合比它差，但事实上在实例的整个分布上表现得却更好时，我们说这个假设过度拟合训练样例定义：给定一个假设空间H，一个假设hH，如果存在其他的假设h’H，使得在训练样例上h的错误率比h’小，但在整个实例分布上h’的错误率比h小，那么就说假设h过度拟合训练数据。2003.11.1832避免过度拟合数据（2）导致过度拟合的原因一种可能原因是训练样例含有随机错误或噪声当训练数据没有噪声时，过度拟合也有可能发生，特别是当少量的样例被关联到叶子节点时，很可能出现巧合的规律性，使得一些属性恰巧可以很好地分割样例，但却与实际的目标函数并无关系。33避免过度拟合数据（3）避免过度拟合的方法及早停止树增长后修剪法两种方法的特点第一种方法更直观第一种方法中，精确地估计何时停止树增长很困难第二种方法被证明在实践中更成功2003.11.1834避免过度拟合数据（4）避免过度拟合的关键使用什么样的准则来确定最终正确树的规模解决方法使用与训练样例截然不同的一套分离的样例，来评估通过后修剪方法从树上修建节点的效用。使用所有可用数据进行训练，但进行统计测试来估计扩展（或修剪）一个特定的节点是否有可能改善在训练集合外的实例上的性能。使用一个明确的标准来衡量训练样例和决策树的复杂度，当这个编码的长度最小时停止树增长。2003.11.1835避免过度拟合数据（5）方法评述第一种方法是最普通的，常被称为训练和验证集法。可用数据分成两个样例集合：训练集合，形成学习到的假设验证集合，评估这个假设在后续数据上的精度方法的动机：即使学习器可能会被训练集合误导，但验证集合不大可能表现出同样的随机波动验证集合应该足够大，以便它本身可提供具有统计意义的实例样本。常见的做法是，样例的三分之二作训练集合，三分之一作验证集合。2003.11.1836错误率降低修剪将树上的每