machine learning tom mitchell中文版英文版课件机器学习courseware第二章

第二章示例学习示例学习的问题描述（见表2.1,表2.2）二.决策树学习（ID3算法）学习效果的衡量标准（示例学习的优化问题）ID3算法：输入：例子集（正例、反例）；输出：决策树从树的根结点开始，每次都用“最好的属性”划分结点，直到所有结点只含一类例子为止。3.信息增益结点nodei例子集C,p个正例n个反例结点nodei的“信息熵”例子号高度头发眼睛类别1矮淡黄兰+2高淡黄兰+3高红兰+4高淡黄褐–5矮黑兰–6高黑兰–7高黑褐–8矮淡黄褐–[头发=淡黄∨红色][眼睛=蓝色]→+[头发=黑色]∨[眼睛=褐色]→–表2.1表2.2DayOutlookTemperatureHumidityWindClass1sunnyhotHighFalseN2sunnyhotHighTrueN3overcasthotHighFalseP4rainmildHighFalseP5raincoolNormalFalseP6raincoolNormalTrueN7overcastcoolNormalTrueP8sunnymildHighFalseN9sunnycoolnormalfalsep10RainMildNormalFalseP11SunnyMildNormalTrueP12OvercastMildHighTrueP13OvercastHotNormalFalseP14rainMildHighTrueN根结点:P=9,n=4A是例子的一个属性，有V个值{a1,…av},用A扩展nodei结点把C分成V个子集{C1,…Cv},Ci对应ai(i=1,2,…V)。Ci含有pi个正例，ni个反例。“期望信息熵”为属性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-}P1=2,n1=3I(2,3)=0.971P2=4,n2=0I(4,0)=0P3=3,n3=2I(3,2)=0.971outlooksunnyovercastrainhumiditypwindyhighnormalNPtruefalseNP{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+}则“信息增益”Gain(A)=I(p,n)-E(A)Gain(outlook)=0.940-E(outlook)=0.246bits3.决策树学习的常见问题1）不合适属性（Inadequateattributes)两类例子具有相同属性值。没有任何属性可进一步扩展决策树。哪类例子多，叶结点标为哪类。3）未知属性①“最通常值”办法②按比例将未知属性例子分配到各子集中：属性A有值{A1,…,Av},A值等于Ai的例子数pi和ni，未知属性值例子数分别为pu和nu,在生成决策树时Ai的例子数Pi+pu·ratiotemperatureoutlookoutlookwindyppwindywindyphumidityNhumidityNppNwindypoutlookpcoolmildhotsunnyoverraintruefalsetruefalsesunnyoverraintruefalsehighnormalhighnormtruefalsesunnyoverrain三.聚集算法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个属性，AjDj;公式（或项）是选择子的合取式，即[xj=Aj],其中J{1,…,n};规则是公式的析取式，即，其中Li为公式。一个例子e=<V1,…Vn>满足选择子[xj=Aj]当且仅当Vj是Aj的元素，即VjAj;e满足一个公式当且仅当它满足该公式的每一个选择子；e满足一条规则当且仅当e满足该规则的至少一个公式。