演示文稿第二章1

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

2、dClass1sunnyhotHighFalseN2sunnyhotHighTrueN3overcasthotHighFalseP4rainmildHighFalseP5raincoolNormalFalseP6raincoolNormalTrueN7overcastcoolNormalTrueP8sunnymildHighFalseN9sunnycoolnormalfalsep10RainMildNormalFalseP11SunnyMildNormalTrueP12OvercastMildHighTrueP13OvercastHotNormalFalseP14rainMildHighTru

3、eNI ( p, n) = -p p + nlogp-2 p + nnp + nlogn2 p + n14根结点:P=9,n=414I (9,5) = - 9 log9 -2 145 log52 14= 0.940 bitsvA是例子的一个属性，有V个值a1, av, 用A扩展nodei结点 把C分成V个子集C1, Cv, Ci对应ai (i=1,2, V)。 Ci含有pi个正例，ni个反例。 “期望信息熵”为E( A) = pi + ni I ( p , n )i=1p + nii属性outlook,有三个值，sunny,overcast,rain,用outlook扩展根结点得到三个子集C1

4、,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.971 P2=4, n2=0I(4,0)=0 P3=3, n3=2I(3,2)=0.971E(outlook) = 5 I ( p , n ) +4 I ( p , n ) + 5 I ( p , n )14= 0.694 bits1114221433114outlooksunnyovercastrain1-,2-,8-,9+,11+3+,7+,12+,13+4+,5+,6-,10+,14-humiditypwindyhighnorm

5、altruefalse1-,2-,8-9+,11+6-,14-4+,5+,10+NPNP则“信息增益”Gain(A)=I(p,n)-E(A)Gain(outlook)=0.940-E(outlook)=0.246bits3. 决策树学习的常见问题1）不合适属性（Inadequate attributes)两类例子具有相同属性值。没有任何属性可进一步扩展决策树。哪类例子多，叶结点标为哪类。3）未知属性“最通常值”办法 按比例将未知属性例子分配到各子集中：属性A有值A1,Av, A值等于Ai的例子数pi和ni，未知属性值例子数分别为pu和nu, 在生成决策树时Ai的例子数Pi+puratiocoo

6、lmildhottemperatureoutlookoutlookwindy sunnyoverrainsunnyoverraintruefalsehighppwindywindyphumidityNhumiditytruetruefalse falsehighnormalnormNppNwindypoutlookptruefalsesunnyoverrain三. 聚集算法1. 基本概念：定义1 （例子）. 设E=D1D2 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; 公式（或项）是选择子的合取式，即ljJxj=Aj,其中 J 1, ,n; 规则是公式的析取式，即公式。i =1Li，其中Li为一个例子e=满足选择子xj=Aj当且仅当Vj是Aj的元素，即Vj Aj; e满足一个公式当且仅当它满足该公式的每一个选择子；e满