示例学习分享资料

《示例学习分享资料》由会员分享，可在线阅读，更多相关《示例学习分享资料（38页珍藏版）》请在装配图网上搜索。

1、1第二章第二章 示例学习示例学习示例学习的问题描述（见表示例学习的问题描述（见表2.1,表表2.2）二二.决策树学习（决策树学习（ID3算法）算法）ID3算法：算法：输入：例子集（正例、反例）；输入：例子集（正例、反例）；输出：决策树输出：决策树从树的根结点开始，每次都用从树的根结点开始，每次都用“最好的属性最好的属性”划分结点，直划分结点，直到所有结点只含一类例子为止。到所有结点只含一类例子为止。2例子号例子号高度高度头发头发眼睛眼睛类别类别1矮矮淡黄淡黄兰兰+2高高淡黄淡黄兰兰+3高高红红兰兰+4高高淡黄淡黄褐褐5矮矮黑黑兰兰6高高黑黑兰兰7高高黑黑褐褐8矮矮淡黄淡黄褐褐头发头发=淡黄淡黄

2、红色红色眼睛眼睛=蓝色蓝色 +头发头发=黑色黑色 眼睛眼睛=褐色褐色 表表2.13表表2.2DayOutlookTemperature Humidity WindClass1sunnyhotHighFalseN2sunnyhotHighTrueN3overcasthotHighFalseP4rainmildHighFalseP5raincoolNormalFalseP6raincoolNormalTrueN7overcastcoolNormalTrueP8sunnymildHighFalseN9sunnycoolnormalfalsep410RainMildNormal FalseP11Sun

3、nyMildNormal TrueP12OvercastMildHighTrueP13OvercastHotNormal FalseP14rainMildHighTrueN5outlooksunnyovercastrainhumiditypwindyhighnormalNPtruefalseNP1141-,2-,8-,9+,11+3+,7+,12+,13+4+,5+,6-,10+,14-1-,2-,8-9+,11+6-,14-4+,5+,10+62.信息增益信息增益 Gain(A)=I(p,n)-E(A)其中，其中，p、n是结点是结点node的正、反例个数。的正、反例个数。A要扩展结要扩展结点

4、点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-npnnpnnppnppnpIloglog22),(viiiiinpInpnpAE1),()(7根结点根结点:P=9,n=5bits 694.0),(145),(144),(145)(332211npIn

5、pInpIoutlookEbits 940.0145145149149)5,9(loglog22IGain(outlook)=0.940-E(outlook)=0.246bitsgain(temperature)=0.029 bitsgain(humidity)=0.151 bitsgain(windy)=0.048 bitsP1=2,n1=3 I(2,3)=0.971P2=4,n2=0 I(4,0)=0P3=3,n3=2 I(3,2)=0.971893.决策树学习的常见问题决策树学习的常见问题1）不相关属性）不相关属性(irrelevant attributes)属性属性A有有v个属性值，个

6、属性值，A的第的第I个属性值对应个属性值对应Pi个正例、个正例、ni个反个反例。例。2)不充足属性（不充足属性（Inadequate attributes)两类例子具有相同属性值。没有任何属性可进一步扩展决策两类例子具有相同属性值。没有任何属性可进一步扩展决策树。哪类例子多，叶结点标为哪类。树。哪类例子多，叶结点标为哪类。3）未知属性值）未知属性值“最通常值最通常值”办法办法 决策树方法决策树方法:把未知属性作为把未知属性作为“类类”，原来的类作为，原来的类作为“属属性性”,npnpnnnpnpppiiiiii212)()(iiiviiiinnnppp10 Bayesian 方法方法 按比例将

7、未知属性值例子分配到各子集中：按比例将未知属性值例子分配到各子集中：属性属性A有有v个值个值A1,Av,A值等于值等于Ai的例子数的例子数pi和和ni，未知属，未知属性值例子数分别为性值例子数分别为pu和和nu,在生成决策树时在生成决策树时Ai的例子数的例子数Pi+puratio ni+nuratio 4.属性选择标准属性选择标准nnNclassAiAprobi)|(115.Overfitting(过适合过适合)1213三三.规则学习算法规则学习算法1.基本概念：基本概念：定义定义1（例子）（例子）.设设E=D1D2 Dn 是是n维有穷向量空间，维有穷向量空间，其中其中 Dj是有穷离散符号集。

8、是有穷离散符号集。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为为公式。公式。JjLili114一个例子一个例

9、子e=满足选择子（公式、规则）的条件也满足选择子（公式、规则）的条件也称做选择子（公式、规则）覆盖该例子。称做选择子（公式、规则）覆盖该例子。例如：例如：例子例子e=满足选择子满足选择子头发头发=淡黄淡黄红红色色和和 眼睛眼睛=蓝色蓝色 ；满足公式；满足公式头发头发=淡黄淡黄红色红色 眼睛眼睛=蓝色蓝色。定义定义3：普化：普化(generalize):减少规则的约束，使其覆盖更多的减少规则的约束，使其覆盖更多的训练例子叫普化。训练例子叫普化。定义定义4：特化：特化(specialize):增加规则的约束，使其覆盖训练例增加规则的约束，使其覆盖训练例子较少叫特化。子较少叫特化。定义定义5：一致：

10、只覆盖正例不覆盖反例的规则被称为是一致：一致：只覆盖正例不覆盖反例的规则被称为是一致的。的。定义定义6：完备：覆盖所有正例的规则被称为是完备的。：完备：覆盖所有正例的规则被称为是完备的。152.GS算法：算法：GS算法算法输入：输入：例子集；例子集；输出：输出：规则；规则；原则：原则：（a)从所有属性中选出覆盖正例最多的属性值；从所有属性中选出覆盖正例最多的属性值；(b)在覆盖正例数相同的情况下，优先选择覆盖反例在覆盖正例数相同的情况下，优先选择覆盖反例少的属性值；少的属性值；设设PE,NE是正例，反例的集合。是正例，反例的集合。PE,NE是临时正，反例集。是临时正，反例集。CPX表示公式，表

11、示公式，F表示规则（概念描述）。表示规则（概念描述）。Ffalse;PE PE,NE NE,CPXtrue;按上述按上述(a)(b)两原则选出一个属性值两原则选出一个属性值V 0,设设V 0 为第为第j0个属个属性的取值，性的取值，CPXCPX Xj0=V0PE CPX覆盖的正例，覆盖的正例，NE CPX覆盖的反例，如果覆盖的反例，如果NE不为空，转不为空，转(3);否则，继续执行否则，继续执行(5);16(5)PEPEPE,F F CPX,如果如果PE=,停止，否则转停止，否则转(2);GS算法举例：算法举例：例子集见表例子集见表2.3学习结果：学习结果：ESR=normalAusculat

12、ion=bublelike X-ray=spotESR=normal3.AQ算法：算法：普化普化(generalize):特化特化(specialize):一致一致完备完备肺炎17noFeverCoughX-rayESRAuscultat.1highheavyFlackNormalBubblelike肺炎2mediuheavyFlackNormalBubblelike3lowslightSpotNormalDry-peep4highmediuFlackNormalBubblelike5mediuslightFlackNormalBubblelike1absentslightStripNorma

13、lNormal肺结2highheavyHoleFastDry-peep核3lowslightStripNormalNormal4absentslightSpotFastDry-peep5lowmediuflackfastNormal表表2.3 肺炎与肺结核两组病历肺炎与肺结核两组病历18noFeverCoughX-rayESRAuscultat.1highheavyFlackNormalBubblelike肺炎2mediuheavyFlackNormalBubblelike3lowslightSpotNormalDry-peep4highmediuFlackNormalBubblelike5m

14、ediuslightFlackNormalBubblelike1absentslightStripNormalNormal肺结核3lowslightStripNormalNormalESR=Normal19noFeverCoughX-rayESRAuscultat.1highheavyFlackNormalBubblelike肺炎2mediuheavyFlackNormalBubblelike34highmediuFlackNormalBubblelike5mediuslightFlackNormalBubblelike肺结核ESR=NormalAuscultat=Bubblelike20no

15、FeverCoughX-rayESRAuscultat.肺炎3lowslightSpotNormalDry-peep1absentslightStripNormalNormal肺结2highheavyHoleFastDry-peep核3lowslightStripNormalNormal4absentslightSpotFastDry-peep5lowmediuflackfastsNormal第二轮第二轮21noFeverCoughX-rayESRAuscultat.肺炎3lowslightSpotNormalDry-peep肺结核4absentslightSpotFastDry-peepX-

16、ray=Spot22noFeverCoughX-rayESRAuscultat.肺炎3lowslightSpotNormalDry-peep肺结核X-ray=spotESR=normal233.AQ算法：输入：例子集、参数#SOL、#CONS、Star的容量m、优化标准；输出：规则；1）Pos和NEG分别代表正例和反例的集合 从Pos中随机地选择一例子e 生成例子e相对于反例集NEG的一个约束Star(reduced star),G(e|NEG,m),其中元素不多于m个。在得到的star中，根据设定的优化标准LEF找出一个最优的公式D。若公式D完全覆盖集合Pos,则转 否则，减少Pos的元素使

17、其只包含不被D覆盖的例子。从步骤开始重复整个过程。生成所有公式D的析取，它是一个完备且一致的概念描述。242)Star生成:Induce方法例子e的各个选择符被放入PS(partial star)中,将ps中的元素按照优化标准排序.在ps中保留最优的m个选择符.对ps中的选择符进行完备性和一致性检查,从ps中取出完备一致的描述放入SOLUTION表中,若SOLUTION表的大小大于等于参数#SOL,则转.一致但不完备的描述从ps中取出放入表CONSISTENT中,若CONSISTENT表的大小大于等于参数#COS,则转;对每个表达式进行特殊化处理,所有得到的表达式根据优化标准排列,仅保留m个最

18、优的.重复步骤,.得到的一般化描述按优先标准排序,保留m个最优的表达式构成约束Star(e|NEG,m).举例:例子集:表2.3#SOL=225#CONS=2M=2优化标准:正例数/反例数种子 :Fever=highCough=heavyX-ray=flackESR=normalAuscultation=bubblelike第一轮:（进入Induce算法）Ps:Fever=high Cough=heavy X-ray=flack ESR=normal Ausculation=bubblelike 保留m个表达式Auscultation=bubblelike 一致的表达式,放入CONSISTEN

19、T中X-ray=flack 1e26特化;x-ray=flackESR=normal X-ray=flack x-ray=flackCough=heavy x-ray=flackFever=high 保留2个表达式，2个表达式均为一致的,放入CONSISTENT中,按优先标准排序CONSISTENT中表达式,保留m(2)个表达式.Ausculation=bubblelike x-ray=flackESR=normal（出Induce算法）选出一个最优的作为DD:Auscultation=bubblelike将D覆盖的正例去掉.去掉 第一轮结束.第二轮:种子 :Fever=lowCough=sl

20、ightx-ray=spotESR=normalAuscultation=dry-peep 5421,eeee3e27Ps:fever=low Cough=slight x-ray=spot ESR=normal Ausculation=dry-peep 保留m(2)个表达式:ESR=normal x-ray=spot 特殊化:ESR=normal fever=low ESR=normal ESR=normal Cough=slight ESR=normal Ausculation=dry-peep x-ray=spot ESR=normal x-ray=spot Ausculation=dr

21、y-peep x-ray=spot x-ray=spot fever=low x-ray=spot Cough=slight 28保留m(2)个表达式x-ray=spot ESR=normalx-ray=spot fever=low上面2个表达式都是一致的,放入CONSISTENT表中,按优先标准排序,并选出一个最优的作为DD:x-ray=spot ESR=normal将D覆盖的正例从pos中去掉,去掉 ,pos空.生成规则:Ausculation=bubblelike x-ray=spot ESR=normal肺炎算法结束.3e294.扩张矩阵：定义1(扩张矩阵)：已知e+=及反例矩阵NE.

22、对每一jN,用“死元素”*对 在NE中第j列的所有出现做代换，这样得出的矩阵叫做正例e+在反例NE背景下的扩张矩阵。记为EM(e+|NE),或简记为EM(e+)。表2.7正例矩阵与反例矩阵n1v,v jvkX1X2X3kX1X2X310001101212020103100311040024112500130 X1 X2 X3 X1 X2 X3 X1 X2 X3 X1 X2 X3 1 1 *0 *1 1 *2 *0 *0 *0 3 1 *1 0 4 1 2 *2 1 *5 *0 0 0 *EM()EM()EM()EM()图2.2 正例在反例背景下的扩张矩阵定义2:在一个扩张矩阵中，由分别来自不同

23、行的m个非死元素连接组成它的一条路（径）路（径）；在两个以上的扩张矩阵中，具有相同值的对应的非死元素叫做它们的公共元素公共元素；在两个或两个以上扩张矩阵中出现的路叫公共路公共路；具有公共路的两个扩张矩阵叫做相交相交的，否则叫做不相交的。1e2e3e4e315.算法AE1优先选择“最大公共元素”，即在最多数目的扩张矩阵中出现的元素。6.广义扩张矩阵与AE9算法 广义扩张矩阵：已知反例矩阵NE和一个公式L=对NE的每一列jN,N=1,2,n,如果j J,则用死元素“*”对NE中第j列的所有元素做代换；如果jJ,则用“*”对NE中第j列属于Aj的所有元素做代换。这样得到的矩阵叫做公式L的广义扩张矩阵

24、。记为EM(L).必选元素：设EM(L)是一致公式L的扩张矩阵，如果在EM(L)中的某一行中只有一个非死元素，则该元素叫做必选元素。公式的合并：已知公式 及公式F=则将L和F对应的选择子的取值合并得到一个新的公式，叫做L和F的合并，记为LF。即LF=.AxjjJjLjjJjBX jjjJJjBAXAxjjJj32定理2.1 公式L覆盖公式A又覆盖公式B，当且仅当它覆盖A B。定理2.2 一个例子集合被一个一致的规则所覆盖，则这些例子的合并也是一致的。33x1x2x3x4公式L0,30,11,311111202223312244033NE(a)公式L(L=X1=0 3X2=0 1X3=1 3)与

25、反例矩阵NEX1X2X3X4公式1*22*2*4*34L的扩张矩阵EM(L)箭头经过的路对应于公式X11,4X32=X1=0,2,3X3=0,1,3算法AE9(1)从正例集PE中选择一个种子e.Fe,path,CPE.(2)做F的扩张矩阵EM(F)。如果有必选元素则放入path中，同时删去NE中该必选元素出现的行（反例），如果NE空则终止；如非空则删去PE和CPE中出现该必选元素的对应行，重复执行直至EM(F)中不存在必选元素为止。(3)如果PE非空，检查PE中的每一正例，看它与F的合并是否是一致公式；如不是则从PE中删去该正例；若是则保留一个覆盖正例数目最多的一个合并取代F,将PE中被F覆盖

26、的正例放入CPE中，重复步骤(2)和(3),直至PE变空。(4)如果PE空而CPE非空，则检查CPE中的每一个正例，看它与F合并后是否为一致公式，若不是则从CPE中删去该正例；35若是则生成合并公式，保留一个覆盖最多正例的合并取代F,从CPE中删去被新的F覆盖的正例，重复(2),(4)直至CPE 变空。(5)此时PE和CPE均空，但NE非空，做EM(F).将其中含有最多非死元素的列中的非死元素放入path中，并从NE中删去含这些非死元素的行，重复这一过程，直到NE变空。将path转变为相应的公式。36应用举例将表2.7的第一个反例改为选择第一个正例 做种子，F ,path,CPE.(2)做F的

27、扩张矩阵EM(F),如下图(a)0,0,01e1eX1X2X3公式F00011*22*311*41125*(a)X1X2X3公式F0,10,201 *(b)37path path l22,l53,(3)将路径转变为公式x2 1x3 1删去路径对应的反例，因PE与CPE中没有该必选元素出现，所以PE与CPE不动(4)PE非空，做F F ()=,F是一致的。做F F ()=,F是一致的。继续合并F F ()=,F是一致的。继续合并F F ()=,F是不一致的。从PE中删除 ,保留覆盖最多正例的F=。CPE=,做EM(F),如图(b)所示Path=l22,l53,l13,将Path转变为公式x2 1x3 1,2=x2=0,2x3=0 公式与CPE中例子一致。第二轮：对 执行上面过程。e2e1e3e4e1e2e3e4e438参考文献：1.Induction of Decision Trees,Machine Learning 1:81-106,1986.2.Machine learning:An Artificial Intelligence Approach Edited by R.S.Michalski P39-135.3.归纳学习算法，理论，应用 洪家荣 P.1-33