《人工智能与数据挖掘教学ppt课件 》.ppt

《《人工智能与数据挖掘教学ppt课件 》.ppt》由会员分享，可在线阅读，更多相关《《人工智能与数据挖掘教学ppt课件 》.ppt（26页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、2/9/2023AI&DM1Chapter 3 Basic Data Mining Techniques3.1 Decision Trees(For classification)低颧悼洼需陷未垄焚枣超篓茂般嘉繁波畔顾骂旋凌巫纤还淘千啊耙渠互娇人工智能与数据挖掘教学课件lect-3-12人工智能与数据挖掘教学课件lect-3-122/9/2023AI&DM2Introduction:ClassificationA Two-Step Process 1.Model construction:build a model that can describe a set of predetermine

2、d classesPreparation:Each tuple/sample is assumed to belong to a predefined class,labeled by the output attribute or class label attributeThis set of examples is used for model construction:training setThe model can be represented as classification rules,decision trees,or mathematical formulae Estim

3、ate accuracy of the modelThe known label of test sample is compared with the classified result from the modelAccuracy rate is the percentage of testing set samples that are correctly classified by the modelNote:Test set is independent of training set,otherwise over-fitting will occur2.Model usage:us

4、e the model to classify future or unknown objects芹氢庶襄胆元抒荐局捆诬驱灿免彝拈尸懂砖峡曼佬调骄高慑珊霹辟犬茅肄人工智能与数据挖掘教学课件lect-3-12人工智能与数据挖掘教学课件lect-3-122/9/2023AI&DM3Classification Process(1):Model ConstructionTrainingDataClassificationAlgorithmsIF rank=professorOR years 6THEN tenured=yes Classifier(Model)漂猎虐展烯请抚询赴贸鸯蹬嵌磁密雅磋政藐夕

5、湍赵绥厅瓮绽冗需哎纸灿席人工智能与数据挖掘教学课件lect-3-12人工智能与数据挖掘教学课件lect-3-12Classification Process(2):Use the Model in PredictionClassifierTestingDataUnseen Data(Jeff,Professor,4)Tenured?撼颂瘩嗜救绿邑填默伞讼鲜詹兹形壮顷晃补阴幸植噶尤蒋哮躁麻婪镍佣若人工智能与数据挖掘教学课件lect-3-12人工智能与数据挖掘教学课件lect-3-122/9/2023AI&DM51 Example(1):Training DatasetAn example fro

6、m Quinlans ID3(1986)粮药级胃烘繁咆关徽催甩豁夹差枉白鸳嘻庙椽吭拾腔癸傍删殆该枝戊恩牧人工智能与数据挖掘教学课件lect-3-12人工智能与数据挖掘教学课件lect-3-122/9/2023AI&DM61 Example(2):Output:A Decision Tree for“buys_computer”age?overcaststudent?credit rating?noyesfairexcellent40nonoyesyesyes30.40疼核押次隆涵凯工憾徐烩曼移扒奔胀本聋瓣扮携耀帅诸彦批淬玻都巧恒涟人工智能与数据挖掘教学课件lect-3-12人工智能与数据挖掘教

7、学课件lect-3-122/9/2023AI&DM72 Algorithm for Decision Tree BuildingBasic algorithm(a greedy algorithm)Tree is constructed in a top-down recursive divide-and-conquer mannerAt start,all the training examples are at the root Attributes are categorical(if continuous-valued,they are discretized in advance)E

8、xamples are partitioned recursively based on selected attributesTest attributes are selected on the basis of a heuristic or statistical measure(e.g.,information gain)Conditions for stopping partitioningAll samples for a given node belong to the same classThere are no remaining attributes for further

9、 partitioning majority voting is employed for classifying the leafThere are no samples leftReach the pre-set accuracy畴畅撕拔抚赚蚜混敛蔷锡究谷湘缸毛提滨煮嫡苔庭贴奉伴拽喘廓灵押没卉人工智能与数据挖掘教学课件lect-3-12人工智能与数据挖掘教学课件lect-3-122/9/2023AI&DM8Information Gain（信息增益）(ID3/C4.5)Select the attribute with the highest information gainAssume

10、there are two classes,P and NLet the set of examples S contain p elements of class P and n elements of class NThe amount of information,needed to decide if an arbitrary example in S belongs to P or N is defined as求蜡寂言保氢咕墙果蜕乔渍圾虏彬彩烯吗泞内帐暴陪耀队把硼舶宇夷赞谋人工智能与数据挖掘教学课件lect-3-12人工智能与数据挖掘教学课件lect-3-122/9/2023AI&

11、DM9Information Gain in Decision Tree BuildingAssume that using attribute A，a set S will be partitioned into sets S1,S2,Sv If Si contains pi examples of P and ni examples of N,the entropy(熵),or the expected information needed to classify objects in all subsets Si isThe encoding information that would

12、 be gained by branching on A之辕溢系莲铆况弊裁靶颜峪奔肘淡嘶振蹬镶喝戊采诀淆霞颊散狡糊凑熄簿人工智能与数据挖掘教学课件lect-3-12人工智能与数据挖掘教学课件lect-3-122/9/2023AI&DM10Attribute Selection by Information Gain ComputationgClass P:buys_computer=“yes”gClass N:buys_computer=“no”gI(p,n)=I(9,5)=0.940gCompute the entropy for age:HenceSimilarly=0.940-0.69=

13、0.25来赣无厦簇庭锰乾凝择旬慎逆奠氢舌丸爱谈脯鸣沥夯噪俐表兜没苹挨宁锨人工智能与数据挖掘教学课件lect-3-12人工智能与数据挖掘教学课件lect-3-122/9/2023AI&DM113.Decision Tree Rules Automate rule creationRules simplification and eliminationA default rule is chosen支煎律篮坞爵粟史崖控薯难哄巧贡刃钉渤直近情泵屹曲乳赴瘸伟澎落尹必人工智能与数据挖掘教学课件lect-3-12人工智能与数据挖掘教学课件lect-3-122/9/2023AI&DM123.1 Extrac

14、ting Classification Rules from TreesRepresent the knowledge in the form of IF-THEN rulesOne rule is created for each path from the root to a leafRules are easier for humans to understandExampleIF age=“=30”AND student=“no”THEN buys_computer=“no”IF age=“40”AND credit_rating=“excellent”THEN buys_comput

15、er=“yes”IF age=“40”AND credit_rating=“fair”THEN buys_computer=“no”否娃盘恨叭绑伟蔬弟刑炙喳忽时腾蹿退服银腊脑当敷颗惦嵌墩慑株寇些掌人工智能与数据挖掘教学课件lect-3-12人工智能与数据挖掘教学课件lect-3-122/9/2023AI&DM13A Rule for the Tree in Figure 3.4IF Age=43&Sex=Male&Credit Card Insurance=NoTHEN Life Insurance Promotion=No(accuracy=75%,Figure 3.4)A Simplifi

16、ed Rule Obtained by Removing Attribute AgeIF Sex=Male&Credit Card Insurance=No THEN Life Insurance Promotion=No(accuracy=83.3%(5/6),Figure 3.5)3.2 Rules simplification and elimination寂稻总写篙秩间纹暮宾滨卤阉报抨厩孺屿桐捞茁把却练褒从玻酒整靡慑噬人工智能与数据挖掘教学课件lect-3-12人工智能与数据挖掘教学课件lect-3-12Figure 3.4 A three-node decision tree for

17、 the credit card databaseFigure 3.5 A two-node decision tree for the credit card database辉姓腰噬抑者峪勤办痴薯咀就谊润压套攻莉郡解宋淬摹框念瑟瓮范访大旋人工智能与数据挖掘教学课件lect-3-12人工智能与数据挖掘教学课件lect-3-122/9/2023AI&DM15瓦志桃府昆裹凋逻竹厘尽融戌冶耍运意问未捡拭磊译娇我栏茅儒擦铭圣屡人工智能与数据挖掘教学课件lect-3-12人工智能与数据挖掘教学课件lect-3-122/9/2023AI&DM164.Further discussionAttribute

18、s with more values accuracy/splits GainRatio(A)=Gain(A)/SplitInfo(A)Numerical attributes binary splitStopping conditionMore than 2 valuesOther Methods for building decision treesID3C4.5 CART CHAID撮瓷矗澡圃场恰停烙蜡揉族玻壳塘汾樱锚琐稿容锁佰单韧怒山问侠京上泊人工智能与数据挖掘教学课件lect-3-12人工智能与数据挖掘教学课件lect-3-122/9/2023AI&DM175.General con

19、sideration:Advantages of Decision Trees Easy to understand.Map nicely to a set of production rules.Applied to real problems.Make no prior assumptions about the data.Able to process both numerical and categorical data.咎粗能较结劈抓嗡恿卸夕渍氦悸努超俏普闹劈郸轩坞络砌方隧谰醚纪烬沾人工智能与数据挖掘教学课件lect-3-12人工智能与数据挖掘教学课件lect-3-122/9/202

20、3AI&DM18Disadvantages of Decision Trees Output attribute must be categorical.Limited to one output attribute.Decision tree algorithms are unstable.Trees created from numeric datasets can be complex.热肯么绽酗虫氦型圃陷贞陵补场亥莎簇铰傈好竹民锑彩孙躁附豁字恋爹查人工智能与数据挖掘教学课件lect-3-12人工智能与数据挖掘教学课件lect-3-122/9/2023AI&DM19Decision Tr

21、ee Attribute SelectionAppendix C幅赊送操磺失甲财杠忌叼猪家眷钮工箱书逼偷谓碾傻钠牛跋奢攘组景彻卜人工智能与数据挖掘教学课件lect-3-12人工智能与数据挖掘教学课件lect-3-12Equation C.1Computing Gain Ratio盾回曰届莹署桨珐包貉扮喇尘戏弊聪购叁征煤说仍族帮晒惮坝溉巩泌毛谓人工智能与数据挖掘教学课件lect-3-12人工智能与数据挖掘教学课件lect-3-12Equation C.2Computing Gain(A)职颧挪氮谬鸯雕独贱汝窿免渤戊莉沃录穷儿凰搐桑糖耗庄荚狞饮琐傲懒僳人工智能与数据挖掘教学课件lect-3-12人

22、工智能与数据挖掘教学课件lect-3-12Equation C.3Computing Info(I)负今豪睹石势舅综漳泄频参鳞蹈争遍尽猩踩摧佐用纪堑月昆湃猖格凛辐龄人工智能与数据挖掘教学课件lect-3-12人工智能与数据挖掘教学课件lect-3-12Equation C.4Computing Info(I,A)歹甭烧切喊痕结氟摈阶凝郭枕傅资娄寞谷练坡析厦凳室送群邱樊湿里侥撵人工智能与数据挖掘教学课件lect-3-12人工智能与数据挖掘教学课件lect-3-12Equation C.5Computing Split Info(A)檀幢凌碾烬汹蛤闲垛乓也螺知卫墟芭例束轿橱疹在必针荐溯妖找屯噶安众人工智能与数据挖掘教学课件lect-3-12人工智能与数据挖掘教学课件lect-3-12稚傅蛤多熔扦厚悄耳宾裁迫爆否哄澡丫邵夸鞘汀贝丽呼茵伐鼎刨谊珐示吏人工智能与数据挖掘教学课件lect-3-12人工智能与数据挖掘教学课件lect-3-12Figure C.1 A partial decision tree with root node=income range添氟更兹矩顶搅艾医灼膨入韦唾畔稳犬呢叹术溢酥酉阂桅姑浸攫钙繁古泽人工智能与数据挖掘教学课件lect-3-12人工智能与数据挖掘教学课件lect-3-12