(完整版)ID3算法课件.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《(完整版)ID3算法课件.ppt》由用户(三亚风情)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 完整版 ID3 算法 课件
- 资源描述:
-
1、1决策树算法决策树算法23v决策树是用样本的属性作为结点,用属性的取值作为分支的树结构。v决策树的根结点是所有样本中信息量最大的属性。树的中间结点是该结点为根的子树所包含的样本子集中信息量最大的属性。决策树的叶结点是样本的类别值。决策树概念决策树概念4v决策树是一种知识表示形式,它是对所有样本数据的高度概括。v决策树能准确地识别所有样本的类别,也能有效地识别新样本的类别。5v首先找出最有判别力的属性,把样例分成多个子集,每个子集又选择最有判别力的属性进行划分,一直进行到所有子集仅包含同一类型的数据为止。最后得到一棵决策树。vJ.R.Quinlan的工作主要是引进了信息论中的信息增益,他将其称为
2、信息增益(information gain),作为属性判别能力的度量,设计了构造决策树的递归算法。v下面通过一个例子一个例子,说明ID3算法的基本思想。6 对于气候分类问题,属性为:天气(A1)取值为:晴,多云,雨 气温(A2)取值为:冷,适中,热 湿度(A3)取值为:高,正常 风(A4)取值为:有风,无风 一、一、ID3基本思想基本思想7v每个样例属于不同的类别,此例仅有两个类别,分别为P,N。P类和N类的样例分别称为正例和反例。将一些已知的正例和反例放在一起便得到训练集。v表表6.4.1给出一个训练集。由ID3算法得出一棵正确分类训练集中每个样例的决策树,见下图。8天 气湿 度风晴雨多云高
3、正常有风无风PNNPPBACKGO9v决策树叶子为类别名,即P 或者N。其它结点由样例的属性组成,每个属性的不同取值对应一分枝。v若要对一样例分类,从树根开始进行测试,按属性的取值分枝向下进入下层结点,对该结点进行测试,过程一直进行到叶结点,样例被判为属于该叶结点所标记的类别。10v现用图来判一个具体例子,某天早晨气候描述为:天气:多云 气温:冷 湿度:正常 风:无风 它属于哪类气候呢?v从图中可判别该样例的类别为P类。11ID3就是要从表的训练集构造图这样的决策树。实际上,能正确分类训练集的决策树不止一棵。Quinlan的ID3算法能得出结点最少的决策树12二、二、ID3算法算法 对当前例子
4、集合,计算各属性的信息增益;选择信息增益最大的属性Ak;把在Ak处取值相同的例子归于同一子集,Ak取几个值就得几个子集;对既含正例又含反例的子集,递归调用建树算法;若子集仅含正例或反例,对应分枝标上P或N,返回调用处。13实例计算实例计算 对于气候分类问题进行具体计算有:信息熵的计算信息熵的计算 信息熵:其中S是样例的集合,P(ui)是类别i出现概率:miiiuPuPSH1)(log)()(|)(SuuPii14|S|表示例子集S的总数,|ui|表示类别ui的例子数。对9个正例和5个反例有:P(u1)=9/14P(u2)=5/14H(S)=(9/14)log(14/9)+(5/14)log(1
5、4/5)=0.94bit15信息增益的计算公式:其中A是属性,Value(A)是属性A取值的集合,v是A的某一属性值,Sv是S中A的值为v的样例集合,|Sv|为Sv中所含样例数。)()()(),(AValuevvvSEntropySSSEntropyASGain 信息增益的信息增益的计算计算16属性属性Ai的信息增益的信息增益以属性A1为例,根据信息增益的计算公式,属性A1的信息增益为雨多云晴,1)()(),(vvvSEntropySSSEntropyASGainS=9+,5-/原样例集中共有14个样例,9个正例,5个反例S晴=2+,3-/属性A1取值晴的样例共5个,2正,3反S多云=4+,0
展开阅读全文