第二章(示例学习)VIP免费

第二章示例学习壹.示例学习的问题描述（见表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)简记为叫做例子。其中VjDj∈。例如：对表2.1D1={高，矮}；D2={淡黄，红，黑}；D3={兰，褐}E=D1×D2×D3例子e=(矮，淡黄，兰）定义2.选择子是形为[xj=Aj]的关系语句，其中xj为第j个属性，AjDj;公式（或项）是选择子的合取式，即[xj=Aj],其中J{1,…,n};规则是公式的析取式，即，其中Li为公式。JjLili1一个例子e=满足选择子（公式、规则）的条件也称做选择子（公式、规则）覆盖该例子。例如：例子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个属性的取值...