第八章机器学习决策树ID算法的实例解析

决策树模型决策树模型排名排名挖掘主题挖掘主题算法算法得票数得票数发表时间发表时间作者作者陈述陈述人人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.Christos 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会议的算法投票结果会议的算法投票结果信息信息的定量的定量描述描述衡量信息多少的物理量称为信息量。若概率很大，受信者事先已有所估计，则该消息信若概率很大，受信者事先已有所估计，则该消息信息量就很小；息量就很小；若若概率很小，受信者感觉很突然，该消息所含信息概率很小，受信者感觉很突然，该消息所含信息量就量就很大。很大。信息量的定义根据客观事实和人们的习惯概念，函数f(p)应满足以下条件：1.f(p)应是概率p的严格单调递减函数，即当p1p2，f(p1)f(p2)；2.当p=1时，f(p)=0；3.当p=0时，f(p)=；4.两个独立事件的联合信息量应等于它们分别的信息量之和。对信对信息量息量的的认识认识理解理解信息量的定义信息量的定义若一个消息若一个消息x x出现出现的概率的概率为为p p，则这一消息所含的信息量则这一消息所含的信息量为为其中，对数的底大于其中，对数的底大于1 1信息量信息量单位单位以以2 2为底时，单位为为底时，单位为 bitbit（binary unitbinary unit，比特，比特）以以e e为底时，单位为为底时，单位为 natnat（natural unitnatural unit，奈特，奈特）以以1010为底时，单位为为底时，单位为 harthart（HartleyHartley，哈特），哈特）抛一枚均匀硬币，出现正面与反面的信息量抛一枚均匀硬币，出现正面与反面的信息量是多少？是多少？解解：出现正面与反面的概率均为：出现正面与反面的概率均为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种符号的平均信息量为抛一枚均匀硬币的信息抛一枚均匀硬币的信息熵是多少？是多少？解解：出现正面与反面的概率均为：出现正面与反面的概率均为0.5，信息，信息熵是是抛一枚畸形硬币，出现正面与反面的概率分抛一枚畸形硬币，出现正面与反面的概率分别是别是1/4，3/4，出现正面与反面时的信息量出现正面与反面时的信息量是多少？是多少？解解：出现正面与反面的概率分别是：出现正面与反面的概率分别是1/4，3/4，信息，信息熵是是例：气象预报12条件自信息量在事件yj出现的条件下，随机事件xi发生的条件概率为p(xi|yj)，则它的条件自信息量定义为条件概率对数的负值：13条件熵条件熵在给定yj条件下，xi的条件自信息量为I(xi|yj),X集合的条件熵H(X|yj)为在给定Y(即各个yj)条件下,X集合的条件熵H(X|Y)条件熵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.971H(活动|户外=阴)=-(4/4)*log2(4/4)=0H(活动|户外=雨)=-(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.246I(活动活动;温度)=H(活动活动)-H(活动|温度)=0.94-0.911=0.029I(活动活动;湿度)=H(活动活动)-H(活动|湿度)=0.94-0.789=0.151I(活动活动;风速)=H(活动活动)-H(活动|风速)=0.94-0.892=0.048天气天气温度温度湿度湿度风速风速活动活动晴炎热高弱取消晴炎热高强取消阴炎热高弱进行雨适中高弱进行雨寒冷正常弱进行雨寒冷正常强取消阴寒冷正常强进行晴适中高弱取消晴寒冷正常弱进行雨适中正常弱进行晴适中正常强进行阴适中高强进行阴炎热正常弱进行雨适中高强取消温度温度 湿度湿度 风速风速 活动活动 寒冷 正常 弱 进行 适中 正常 强 进行 炎热 高 弱 取消 炎热 高 强 取消 适中 高 弱 取消 温度温度 湿度湿度 风速风速 活动活动 适中 高 弱 进行 寒冷 正常 弱 进行 适中 正常 弱 进行 寒冷 正常 强 取消 适中 高 强 取消 温度 湿度 风速 活动 炎热 高 弱 进行 寒冷 正常 强 进行 适中 高 强 进行 炎热 正常 弱 进行 阴晴雨天气天气 温度温度 湿度湿度 风速风速 活动活动 晴 寒冷 正常 弱 进行 晴 适中 正常 强 进行 晴 炎热 高 弱 取消 晴 炎热 高 强 取消 晴 适中 高 弱 取消 阴 炎热 高 弱 进行 阴 寒冷 正常 强 进行 阴 适中 高 强 进行 阴 炎热 正常 弱 进行 雨 适中 高 弱 进行 雨 寒冷 正常 弱 进行 雨 适中 正常 弱 进行 雨 寒冷 正常 强 取消 雨 适中 高 强 取消 ID3算法生成的决策树ID3算法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；再分别构造以下树：ID3(A-a,d,u1)，ID3(A-a,d,u2)，ID3(A-a,d,um)；/递归算法2003.11.1830决策树学习的常见问题决策树学习的实际问题确定决策树增长的深度处理连续值的属性选择一个适当的属性筛选度量标准处理属性值不完整的训练数据处理不同代价的属性提高计算效率针对这些问题，ID3被扩展成C4.52003.11.1831避免过度拟合数据过度拟合对于