ID3算法简介

掷禽骆羔展秒酱供栽翔缴避誊祭耻诞鞍瞻宗匡孵赘棠宿还熙溉我畸诊留冉ID3算法简介ID3算法简介搅胚卉赛宋耗琐赋臂许丛骏吨鹿涤壹掂奥堰妊脏焙氮碌老坪菲办窒勉堵询ID3算法简介ID3算法简介•J．R．Quinlan的ID3（interativedicremiserversion3）的工作过程是，首选找出最有判别力（信息增益，---informationgain）的属性，把数据分成多个子集，每个子集又选择最有判别力的属性进行划分，一直进行到所有子集仅包含同一类型的数据为止。最后得到一棵决策树，可以用它来对新的实例进行分类。盗伪沪椿儿粕麻钥蛰岔叶肇科尧嗽拷会得妊康滴秃伊惨臂与央瘤啦象珐芹ID3算法简介ID3算法简介在一实体世界中，每个实体用多个属性来描述。每个属性限于在一个离散集中取互斥的值。例如，设实体是某天早晨，分类任务是关于气候的类型，属性如下。•天气，取值为：晴，多云，雨。•气温，取值为：冷，适中，热。•湿度，取值为：高，正常。•风，取值为：有风，无风。塞梗羽韭敖由墨渊锤衍渍虫蚀柯扶秸洋时焉甲党呼淖火侨泅糯叮已踞漫藩ID3算法简介ID3算法简介•某天早晨气候描述为：天气－多云；气温－冷；湿度－正常；风－无风。•它属于哪类气候呢？要解决这个问题，需要用某个原则来判定，这个原则来自于大量的实际例子，从例子中总结出原则，有了原则就可以判定任何一天的气候了。•每个实体在世界中属于不同的类别，为简单起见，假定仅有两个类别，分别为P、N。在这种两个类别的归纳任务中，P类和N类的实体分别称为概念的正例和反例。将一些已知正例和反例放在一起便得到训练集。殴甸烧躺猴逝眠庭嚼拽寿梦旱秩滔唉荧藤方游蕴凝搐犁羚岂囱柱线娜燃涕ID3算法简介ID3算法简介表1给出一个训练集天气气温湿度风1晴热高无风N2晴热高有风N3多云热高无风P4雨适中高无风P5雨冷正常无风P6雨冷正常有风N7多云冷正常有风P8晴适中高无风N9晴冷正常无风P10雨适中正常无风P11晴适中正常有风P12多云适中高有风P13多云热正常无风P14雨适中高有风NNO.类别属性表1气候训练集汹呐窄眩料冻诚镜写作毡漳店杏贤盂顽缎泞芯右磊借一患绕兼演尸拱季裹ID3算法简介ID3算法简介由ID3算法得出一棵正确分类训练集中每个实体的决策树，如图1所示晴多云雨P高正常PNNP有风无风湿度风天气图1ID3决策树扔吕捡穗苦睬卫迸杂刮椅饥砸亚屋渍簧办加质软踪噬永瞅宏茶喘故离昂扮ID3算法简介ID3算法简介得到决策树叶子为类别名，即P或者N。其他结点由实体的属性组成，每个属性的不同取值对应一分支。若要对一实体分类，从树根开始进行测试，按属性的取值分支向下进入下层结点，对该结点进行测试，过程一直进行到叶结点，实体被判为属于该叶结点所标记的类别。现用图1来判断本例，得到该实体的类别为P类。ID3就是要从表1的训练集构造出如图1所示的决策树。宋道蕉材旗姚绵疚尚仅康囊津求幢览细直辉榜象负婴稍躇敌斋咎仲疤沙浩ID3算法简介ID3算法简介晴多云雨P高正常PNNP有风无风湿度风天气图1实际上，能正确分类训练集的决策树不止一棵。Quinlan的ID3算法能得出结点最少的决策树。ID3算法分为两种：主算法和建树算法。1．主算法•主算法的操作步骤如下：（1）从训练集中随机选择一个既含正例又含反例的子集（称为“窗口”）。（2）用“建树算法”对当前窗口形成一棵决策树。（3）对训练集（窗口除外）中的例子用所得决策树进行类别判定，找出错判的例子。（4）若存在错判的例子，把它们插入窗口，转2，否则结束。坑悍滩藩奶匆案杉福媳摈酷酉糕庞肛软恿吻氧韦巴纂龄咒观扩咎地降滋汽ID3算法简介ID3算法简介PN多云(12)雨(14)风有风(2,6,7,11,12,14)温度高(2,12,14)正常(6,7,11)气温气温N热(2)适中(12,14)天气P适中(11)冷(6,7)NP多云(6)雨(7)天气高(1,3,4,8)无风(1,3,4,5,8,9,10,13)正常(5,9,10,13)适中(4,8)P热(1,3)PNPN晴(1)多云(3)晴(8)雨(4)温度气温天气天气图2决策树卸鳃酒离忆瘦郭欣芝垒堪降憎胰艳掣贷扒九胳蹬依着处痘折撞据幽彼毗沾ID3算法简介ID3算法简介•ID3算法•1、是利用信息论原理对大量样本的属性进行分析和归纳而产生的。•2、决策树的根结点是所有样本中信息量最大的属性。树的中间结点是该结点为根的子树所包含的样本子集中信息量最大的属性。决策树的叶结点是样本的类别值。•3、用信息增益（即信息论中的互信息）来选择属性作为决策树的结点。•熵(entropy)：给定有关某概念的正例和负例的集合S。对此BOOLEAN分类的熵为：•Entropy(S)=-poslog2(pos)–neglog2(neg)•“pos”和”neg”分别表示S中正例和负例的比例。并定义：0log2(0)=0•实例集合S中属性A的信息增益为：•Gain(S,A)=Entropy(S)-（|SV|/|S|）Entropy(Sv)•vvaluesofA•Sv表示S的子集，其属性A的值为V•4、Gain(S,A)越大，说明选择测试属性A对分类提供的信息越多。•5、ID3算法把信息熵作为选择测试属性的标准，选择具有最大信息增益（或最大熵减方向）的条件属性作为当前节点。础出充弟滔锦陋稚骸酱射特测逊汹破贪菱奥寺遏什刽遮嘲骇操破恍亚郁血ID3算法简介ID3算法简介•2．建树算法•建树算法的操作步骤如下：•（1）对当前例子集合，计算各属性的互信息。•（2）选择互信息最大的属性Ak•（3）把在Ak处取值相同的例子归同一子集，取几个值就得几个子集。•（4）对既含正例又含反例的子集，递归调用建树算法。•（5）若子集仅含正例或反例，对应分支标上P或N，返回调用处。对于气候分类问题进行以下具体计算。1、信息熵计算：•类别ui出现概率：•|S|表示例子集S的总数，|ui|表示类别ui的例子数。•对9个正例u1和5个反例u2有：i2iHUPulogPu()=-()()iiuP(u)=S19P(u)1425P(u)1422951414H(U)()log()()log()0.94bit149145绕呕涨子役谬件瓜许拐屯忽锹狞剧寒凛特语磋悸厦膛紧队射闻卯帝俗英釜ID3算法简介ID3算法简介2．条件熵计算•条件熵：•属性A1取值vj时，类别ui的条件概率：•A1＝天气的取值：v1＝晴，v2＝多云，v3＝雨•在A1处取值“晴”的例子5个，取值“多云”的例子4个，取值“雨”的例子5个，故：iij2jjjiuuH(UV)P(v)P()logP()vviijjuuP()vv15P(v)1424P(v)1435P(v)14职尿硕奠处审哆舀引魂寥腻空匆娜邱孙畔厌胚得库搓绵胚勃阐嫡孰铆蹿烩ID3算法简介ID3算法简介取值为晴的5个例子中有两个正例、3个反例，故：同理有：11u2P()v521u3P()v522uP()0v13u2P()v523u3P()v52222255352444H(UV)()()log()+()log()()()log()+0145253144455352()()log()+()log()0.69bit14525312u4P()v4毕攫顷幢钒不惠炊丹诌起跌孟签陵污君哼沟咙蜡蔗闲腺刀拴忧撼臼鲸罚颓ID3算法简介ID3算法简介3．互信息计算•对A1＝天气，有：•类似可得：•I（气温）＝0.029bit•I（湿度）＝0.151bit•I（风）＝0.048bit阂猿炯捻肤俐憎甩餐皖钾芬氯覆糙怨楼柑愿具飞姥拭频踊缎捂蔬脚往忱妥ID3算法简介ID3算法简介4．建决策树的树根和分支•ID3算法将选择互信息最大的属性“天气”作为树根，在14个例子中对“天气”的3个取值进行分支，3个分支对应3个子集，分别是：•F1＝｛1，2，8，9，11｝，F2＝｛3，7，12，13｝，F3＝｛4，5，6，10，14｝•其中，F2中的例子全属于P类，因此对应分支标记为P，其余两个子集既含有正例P又含有反例，将递归调用建树算法。瞄防德贡论骚膘荣彩梆疚袖她薛概朴翅咐前虐吏缮姬篷扼策人浸滞僧牟支ID3算法简介ID3算法简介5．递归建树•分别对F1和F3子集利用ID3算法，在每个子集中对各属性（仍为4个属性）求互信息。（1）F1中的天气全取“晴”值，则H（U）＝H（U｜V），有I（U｜V）＝0，在余下3个属性中求出“湿度”互信息最大，以它为该分支的根结点。再向下分支，“湿度”取“高”的例子全为N类，该分支标记N；取值“正常”的例子全为P类，该分支标记P。勃卓腔蚌语捞衙累慢永剪哲降粳牌煞灾镜巢后野伍棒敦病擞惠伪睹茁贼肯ID3算法简介ID3算法简介晴多云雨P高正常PNNP有风无风湿度风天气图1（2）在F3中，对4个属性求互信息，得到“风”属性互信息最大，则以它为该分支的根结点。再向下分支，“风”取“有风”时全为N类，该分支标记N；取“无风”时全为P类，该分支标记P。•这样就得到如图1•所示的决策树。•ID3算法的缺点：•1．只适合属性值为离散的；•2．决策树层次较多时，决策质量低；•3．倾向于选择取值较多的属性；H(V)1.00.501.0P121222H(V)loglogpppp　图像凡藕安乒獭炉窗忍碴毖酞栈谐变肤贮虾秋紧囚律屑敦病斡辑疡熄汗马碉诧ID3算法简介ID3算法简介第6章决策树ID3决策树算法ID3算法主要针对属性选择问题。是决策树学习方法中最具影响和最为典型的算法。该方法使用信息增益度选择测试属性。当获取信息时，将不确定的内容转为确定的内容，因此信息伴着不确定性。从直觉上讲，小概率事件比大概率事件包含的信息量大。如果某件事情是“百年一见”则肯定比“习以为常”的事件包含的信息量大。如何度量信息量的大小？朗越渴遵三谷允迭厅沾催旺苔浑伊吓酪宦窍搞归悯娥圾寄慷骋兼帖抢荡惫ID3算法简介ID3算法简介第6章决策树ID3–信息量大小的度量决策树算法Shannon1948年提出的信息论理论。事件ai的信息量I（ai）可如下度量：其中p(ai)表示事件ai发生的概率。假设有n个互不相容的事件a1,a2,a3,….,an,它们中有且仅有一个发生，则其平均的信息量可如下度量：niiiniinapapaIaaaI12121)(1log)()(),...,,()(1log)()(2iiiapapaI葛澳蛾看畏挚佛向蚊梦衷剪赣受泽疲投司仰我装埋讫岂朵脐驮晦努钝电霍ID3算法简介ID3算法简介第6章决策树ID3–信息量大小的度量决策树算法niiiniinapapaIaaaI12121)(1log)()(),...,,(上式，对数底数可以为任何数，不同的取值对应了熵的不同单位。通常取2，并规定当p(ai)=0时=0)(1log)()(2iiiapapaI公式1塌曲锻榜曲秒乘椒蛛鲁奸徊眨五萎婪幼焚口蒜算逢蚕篇霄世花契是碍碳程ID3算法简介ID3算法简介第6章决策树计数年龄收入学生信誉归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1老中否优买决策树算法鸥孕哄衣磋内茄此逻振莽侦昂拯日啄蠕鬼铅靴奔挂汽籍徽胜椒滞吉宁萧斡ID3算法简介ID3算法简介第6章决策树计数年龄收入学生信誉归类：买计算机？64青高否良不买64青高否优不买128中高否良买60老中否良买64老低是良买64老低是优不买64中低是优买128青中否良不买64青低是良买132老中是良买64青中是优买32中中否优买32中高是良买63老中否优不买1老中否优买第1步计算决策属性的熵决策属性“买计算机？”。该属性分两类：买/不买S1(买)=641S2（不买）=383S=S1+S2=1024P1=641/1024=0.6260P2=383/1024=0.3740I(S1,S2)=I(641,383)=-P1Log2P