第二章(示例学习)

第二章示例学习一.示例学习的问题描述（见表2.1,表2.2）二.决策树学习（ID3算法）1.ID3算法：输入：例子集（正例、反例）；输出：决策树从树的根结点开始，每次都用“最好的属性”划分结点，直到所有结点只含一类例子为止。例子号高度头发眼睛类别1矮淡黄兰+2高淡黄兰+3高红兰+4高淡黄褐–5矮黑兰–6高黑兰–7高黑褐–8矮淡黄褐–[头发=淡黄∨红色][眼睛=蓝色]→+[头发=黑色]∨[眼睛=褐色]→–表2.1表2.2DayOutlookTemperatureHumidityWindClass1sunnyhotHighFalseN2sunnyhotHighTrueN3overcasthotHighFalseP4rainmildHighFalseP5raincoolNormalFalseP6raincoolNormalTrueN7overcastcoolNormalTrueP8sunnymildHighFalseN9sunnycoolnormalfalsep10RainMildNormalFalseP11SunnyMildNormalTrueP12OvercastMildHighTrueP13OvercastHotNormalFalseP14rainMildHighTrueNoutlooksunnyovercastrainhumiditypwindyhighnormalNPtruefalseNP{1…14}{1-,2-,8-,9+,11+}{3+,7+,12+,13+}{4+,5+,6-,10+,14-}{1-,2-,8-}{9+,11+}{6-,14-}{4+,5+,10+}2.信息增益Gain(A)=I(p,n)-E(A)其中，p、n是结点node的正、反例个数。A要扩展结点node的属性，pi、ni是C被A划分成的V个子集{C1,…Cv}的正、反例个数。属性outlook,有三个值，{sunny,overcast,rain},用outlook扩展根结点得到三个子集{C1,C2,C3}。C1={1-,2-,8-,9+,11+},C2={3+,7+,12+,13+},C3={4+,5+,6-,10+,14-}npnnpnnppnppnpIloglog22),(viiiiinpInpnpAE1),()(根结点:P=9,n=5bits694.0),(145),(144),(145)(332211npInpInpIoutlookEbits940.0145145149149)5,9(loglog22IGain(outlook)=0.940-E(outlook)=0.246bitsgain(temperature)=0.029bitsgain(humidity)=0.151bitsgain(windy)=0.048bitsP1=2,n1=3I(2,3)=0.971P2=4,n2=0I(4,0)=0P3=3,n3=2I(3,2)=0.9713.决策树学习的常见问题1）不相关属性(irrelevantattributes)属性A有v个属性值，A的第I个属性值对应Pi个正例、ni个反例。2)不充足属性（Inadequateattributes)两类例子具有相同属性值。没有任何属性可进一步扩展决策树。哪类例子多，叶结点标为哪类。3）未知属性值①“最通常值”办法②决策树方法:把未知属性作为“类”，原来的类作为“属性”,''npnpnnnpnpppiiiiii'2'1'2')()(iiiviiiinnnppp③Bayesian方法④按比例将未知属性值例子分配到各子集中：属性A有v个值{A1,…,Av},A值等于Ai的例子数pi和ni，未知属性值例子数分别为pu和nu,在生成决策树时Ai的例子数Pi+pu·rationi+nu·ratio4.属性选择标准nnNclassAiAprobi)|(5.Overfitting(过适合)三.规则学习算法1.基本概念：定义1（例子）.设E=D1×D2×…×Dn是n维有穷向量空间，其中Dj是有穷离散符号集。E中的元素e=(V1,V2,…,Vn)简记为Vj叫做例子。其中Vj∈Dj。例如：对表2.1D1={高，矮}；D2={淡黄，红，黑}；D3={兰，褐}E=D1×D2×D3例子e=(矮，淡黄，兰）定义2.选择子是形为[xj=Aj]的关系语句，其中xj为第j个属性，AjDj;公式（或项）是选择子的合取式，即[xj=Aj],其中J{1,…,n};规则是公式的析取式，即，其中Li为公式。JjLili1一个例子e=V1,…Vn满足选择子（公式、规则）的条件也称做选择子（公式、规则）覆盖该例子。例如：例子e=矮，淡黄，兰满足选择子[头发=淡黄∨红色]和[眼睛=蓝色]；满足公式[头发=淡黄∨红色][眼睛=蓝色]。定义3：普化(generalize):减少规则的约束，使其覆盖更多的训练例子叫普化。定义4：特化(specialize):增加规则的约束，使其覆盖训练例子较少叫特化。定义5：一致：只覆盖正例不覆盖反例的规则被称为是一致的。定义6：完备：覆盖所有正例的规则被称为是完备的。2.GS算法：GS算法输入：例子集；输出：规则；原则：（a)从所有属性中选出覆盖正例最多的属性；(b)在覆盖正例数相同的情况下，优先选择覆盖反例少的属性值；设PE,NE是正例，反例的集合。PE’,NE’是临时正，反例集。CPX表示公式，F表示规则（概念描述）。(1)F←false;(2)PE’←PE,NE’←NE,CPX←true;(3)按上述(a)(b)两规则选出一个属性值V0,设V0为第j0个属性的取值，CPX←CPX∧[Xj0=V0](4)PE’←CPX覆盖的正例，NE’←CPX覆盖的反例，如果NE’不为空，转(3);否则，继续执行(5);(5)PE←PE\PE’,F←F∨CPX,如果PE=,停止，否则转(2);GS算法举例：例子集见表2.3学习结果：[ESR=normal][Ausculation=bublelike]∨[X-ray=spot][ESR=normal]3.AQ算法：1)普化(generalize):2)特化(specialize):3)一致4)完备肺炎noFeverCoughX-rayESRAuscultat.1highheavyFlackNormalBubblelike肺炎2mediuheavyFlackNormalBubblelike3lowslightSpotNormalDry-peep4highmediuFlackNormalBubblelike5mediuslightFlackNormalBubblelike1absentslightStripNormalNormal肺结2highheavyHoleFastDry-peep核3lowslightStripNormalNormal4absentslightSpotFastDry-peep5lowmediuflackfastsNormal表2.3肺炎与肺结核两组病历noFeverCoughX-rayESRAuscultat.1highheavyFlackNormalBubblelike肺炎2mediuheavyFlackNormalBubblelike3lowslightSpotNormalDry-peep4highmediuFlackNormalBubblelike5mediuslightFlackNormalBubblelike1absentslightStripNormalNormal肺结核3lowslightStripNormalNormal[ESR=Normal]noFeverCoughX-rayESRAuscultat.1highheavyFlackNormalBubblelike肺炎2mediuheavyFlackNormalBubblelike34highmediuFlackNormalBubblelike5mediuslightFlackNormalBubblelike肺结核[ESR=Normal][Auscultat=Bubblelike]noFeverCoughX-rayESRAuscultat.肺炎3lowslightSpotNormalDry-peep1absentslightStripNormalNormal肺结2highheavyHoleFastDry-peep核3lowslightStripNormalNormal4absentslightSpotFastDry-peep5lowmediuflackfastsNormal第二轮noFeverCoughX-rayESRAuscultat.肺炎3lowslightSpotNormalDry-peep肺结核4absentslightSpotFastDry-peep[X-ray=Spot]noFeverCoughX-rayESRAuscultat.肺炎3lowslightSpotNormalDry-peep肺结核[X-ray=spot][ESR=normal]3.AQ算法：输入：例子集、参数#SOL、#CONS、Star的容量m、优化标准；输出：规则；1）Pos和NEG分别代表正例和反例的集合①从Pos中随机地选择一例子②生成例子e相对于反例集NEG的一个约束Star(reducedstar),G(e|NEG,m),其中元素不多于m个。③在得到的star中，根据设定的优化标准LEF找出一个最优的公式D。④若公式D完全覆盖集合Pos,则转⑥⑤否则，减少Pos的元素使其只包含不被D覆盖的例子。从步骤①开始重复整个过程。⑥生成所有公式D的析取，它是一个完备且一致的概念描述。2)Star生成:Induce方法例子e的各个选择符被放入PS(partialstar)中,将ps中的元素按照各种标准排序.在ps中保留最优的m个选择符.对ps中的选择符进行完备性和一致性检查,从ps中取出完备一致的描述放入SOLUTION表中,若SOLUTION表的大小大于参数#SOL,则转.一致但不完备的描述从ps中取出放入表CONSISTENT中,若CONSISTENT表的大小大于参数#COS,则转;对每个表达式进行特殊化处理,所有得到的表达式根据优化标准排列,仅保留m个最优的.重复步骤,.得到的一般化描述按优先标准排序,保留m个最优的表达式构成约束Star(e|NEG,m).举例:例子集:表2.3#SOL=2#CONS=2M=2优化标准:正例数/反例数种子:[Fever=high][Cough=heavy][X-ray=flack][ESR=normal][Auscultation=bubblelike]第一轮:（进入Induce算法）Ps:[Fever=high]2,1[Cough=heavy]2,1[X-ray=flack]4,1[ESR=normal]5,2[Ausculation=bubblelike]4,0保留m个表达式[Auscultation=bubblelike]一致的表达式,放入CONSISTENT中[X-ray=flack]1e特化;[x-ray=flack][ESR=normal]4,0[X-ray=flack][x-ray=flack][Cough=heavy]2,0[x-ray=flack][Fever=high]2,0保留2个表达式，2个表达式均为一致的,放入CONSISTENT中,按优先标准排序CONSISTENT中表达式,保留m(2)个表达式.[Ausculation=bubblelike][x-ray=flack][ESR=normal]（出Induce算法）选出一个最优的作为DD:[Auscultation=bubblelike]将D覆盖的正例去掉.去掉第一轮结束.第二轮:种子:[Fever=low][Cough=slig