2022机器学习公式详解.docx

机器学习公式详解1 .第1章绪论2 .第2章模型评估与选择3 .第3章线性模型4 .第4章决策树5 .第5章神经网络6 .第6章支持向量机7 .第7章贝叶斯分类器8 .第8章集成学习第9章案类10：第10章降维与度量学习11 .第11章特征选择与稀疏学习12 .第12章计算学习理论13 .第13章半监督学习14 .第14章概率图模型15 .第15章规则学习16 .第16章强化学习第1章绪论式(LI)(iXJ)-EP3)I(M)“)PSX,2o)A«cJ*-Y参见式(1.2)式(1.2)EeC)EEEP(Z)Kh(X)/(x)P(hIXX)/UT-E小)psx,&)El(MN)”(N)d/=EP（三）EPmI、£).；/，*-*A=权即P（三）EPslX£)-2MiyP(X).1K显然成立解析g：EEER)I(Mn)/(N)P(MX，匕)/ut×-×-EP(N)EEl(MN)P伍IX£)<4f-X/A=EP(x)X；P(h|X,£.)521(Mx)/W)aX-Xa，T：首先要知道此时我们假设f是任何能将样本映射到01的函数.存在不止一个/时，服从均匀分布，即每个，出现的概率相等.例如样本空间只有两个样本时，二(4H2)M=Z那么所有可能的真实目标函数，如下：A：/l(Nl)-OJI(XJ)-0；h'/2(x1)三O,(a)-1;h:(三)三lf3(2)O;/4：<1)=1</4(®2)=1.一共6司一1一d个可能的真实目标函数.所以此时通过算法已学习出来的模型桃曲对每个样本无论预测值为0还是1,都必然有一半的/与之预测值相等.例如，现在学出来的模型ME对皿的预测值为1,即MNJ=1,那么有且只有A和乙与H的预测值相等，也就是有且只Vl()(*)=br有一半的,与它预测值相等，所以r-.值得一提的是，在这里我们假设真实的目标函数f服从均匀分布，但是实际情形并非如此，通常我们只认为能高度拟合已有样本数据的函数才是真实目标函数，例如，现在已有的样本数据为«力。II大1)，那么此时后才是我们认为的真实目标函数，由于没有收集到或者压根不存在覆.0).(物.0)1但1/)15、0»(皿.1).(啊,1)怆类样本，所以hh。都不算是真实目标函数.这也就是“西瓜书''式(1.3)下面的第3段中“骑自行车”的例子所想表达的内容.第2章模型评估与选择式(2.20)AUC三-y(j,HJr*)*(y÷y(÷)解析在解释AHe式之前，需要先弄清楚RCr曲线的具体绘制过程.下面我们就举个例子，按照“西瓜书”图2.4下方给出的绘制方法来讲解一下RCr曲线的具体绘制过程.假设我们已经训练得到一个学习器现在用该学习器来对8个测试样本(4个正例，4个反例，即m+=E-=4)进行预测，预测结果为：(fl,0.77,+),加,0.62,-),(孙0.58,+),(4,047,+)(«5.0.47.-)J,0.33.-).(>.0.23.+).(».0.15.-)此处用表示样本，以和坐标(WS作出区分其中，和分别表示样本为正例和为反例，数字表示学习器/预测该样本为正例的概率，例如对于反例球说，当前学习器/()预测它是正例的概率为ns?.上面给出的预测结果已经按照预测值从大到小排序根据“西瓜书”上给出的绘制方法，首先需要对所有测试样本按照学习器给出的预测结果进行排序，接着将分类阈值设为一个不可能取到的最大值.显然，此时所有样本预测为正例的概率都一定小于分类阈值，那么预测为正例的样本个数为0,相应的真正例率和假正例率也都为0,所以我们可以在坐标00)处标记一个点.接下来需要把分类阈值从大到小依次设为每个样本的预测值，也就是依次设为077,0.62,0.58,0.47,0.33,0.23,0.15,然后分别计算真正例率和假正例率，再在相应的坐标上标记点，最后再将各个点用直线连接，即可得到RCC曲线.需要注意的是，在统计预测结果时，预测值等于分类阈值的样本也被算作预测为正例.例如，当分类阈值为C力时，测试样本/被预测为正例，由于它的真实标记也是正例，所以此时叫是一个真正例.为了便于绘图，我们将T轴(假正例率轴)的“步长”定为二，珊由(真正例率轴)的“步长”定为;根据真正例率和假正例率的定义可知，每次变动分类阈值时，若新增个假正例，那么相应的T轴坐标也就增加若新增j个真正例，那么相应的畸Ii坐标也就增加高.按照以上讲述的绘制流程，最终我们可以绘制出如图2/所示的RCC曲线.图2-1RoC曲线示意注：表示红色线段；表示蓝色线段；一表示绿色线段在这里，为了能在解析式(2.21)时复用此图，我们没有写上具体的数值，转而用其数学符号代替.其中绿色线段表示在分类阈值变动的过程中只新增了真正例，红色线段表示只新增了假正例，蓝色线段表示既新增了真正例也新增了假正例.根据AUa直的定义可知，此时的AlM值其实就是所有红色线段和蓝色线段与7轴围成的面积之和.观察图2-1可知，红色线段与了轴围成的图形恒为矩形，蓝色线段与了轴围成的图形恒为梯形.由于梯形面积式既能算梯形面积，也能算矩形面积，所以无论是红色线段还是蓝色线段，其与>轴围成的面积都能用梯形公式来计算：-TJ(弘+16+1)其中，一4为”高、的为“上底”，为“下底”.那么对所有红色线段和蓝色线段与7轴围成的面积进行求和，则有11l一rE(<Th4-，)(的物.t=l此即AUC式(2.21)X=焉E(l(x÷)</(z-)÷I(z÷)=/(X-)解析按照我们上述对式(2.20)的解析思路，La可以看作是所有绿色线段和蓝色线段与1/轴围成的面积之和，但从式(2.21)中很难一眼看出其面积的具体计算方式，因此我们进行恒等变形如下：J-(1(/(«*)</(*-)+I(三+)-/(»-)ar>,l>*-*D-'/=F1(x+)<(x")+i(x+)=(x)三+*ZHLe-CD-*11-=!W(n)<(n-)+I1(/-uf>一=5,卫Z1(x)<(x)÷2m+mu/M</>.小I()-(x)1.,n-在变动分类阈值的过程当中，如果有新增真正例，那么图21就会相应地增加一条绿色线段或蓝色线段，所以上式中的.K可以看作是在累加所有绿色和蓝色线段，相应地，后面的内容便是在求绿色线段或者蓝色线段与“轴围成的面积，即：÷y)三r,D-一，»-与式（2.20）中的求解思路相同，不论是绿色线段还是蓝色线段，其与Q轴围成的图形面积都1可以用梯形公式来进行计算，所以上式表示的依旧是一个梯形的面积公式.其中U即梯形的“高”，中括号内便是“上底+下底"，下面我们来分别推导一下“上底”（较短的底）和“下底”（较长的底）.由于在绘制RCr曲线的过程中，每新增一个假正例时T坐标也就新增一个步长，所以对于1“上底”，也就是绿色或者蓝色线段的下端点到轴的距离，长度就等于U乘以预测值大于/（n"的假正例的个数，即!E1(3)V/Gr)而对于“下底”，长度就等于二二乘以预测值大于等于人的假正例的个数，即m式(2.27)l(x÷)<(z-)+£I(x÷)=(-)J.一.1>-/严'< =maxfs.t.I,nlf,(l4>4<txm÷i'/解析截至2018年12月“西瓜书”第1版第30次印刷，式Q.27）应当勘误为E = nunc (：)d°WMm÷t ' /具体推导过程如下：由“西瓜书”中的上下文可知，对C<“进行假设检验，等价于本章附注中所述的对P«曲叁打假设检验，所以在“西瓜书”中求解最大错误率7等价于在附注中求C解事件最大发生频率由附注可知C=minCa.t.(：)曲f)"<°所以A=Inin?£(：)曲1一刖尸<.QC将上式中的二，二，Rl等价替换为F"门可得F=mineM.一句)*，V.M>ra÷l7)式(2.41)E(/:D)=Epl/|z:Pl-yp2=ED(/(a)-7(«)+/M-yo)a=Eo(/(»；D)一/(,)月+EDIV(Jr)-Jto/+ED2(fl.D)-fix)(7(X)ITd)=ED(/(室D)-f(x)s+Ed(/(»)-Vd)1=ED(/(®；。)-7(*)a+¾>I(7(®)-y+y-yp)a=%(/(z;D)-用)卉+%(/(X)-yt+ED电+2E(/(X)-J)(y-加)-%f(/(®；D)-/(x)t+(7(®)一»+如Rlto-一：减一个八公再加一个，属于简单的恒等变形-©：同一样，减一个再加一个u属于简单的恒等变形(§)-©：同一样，将最后一项利用期望的运算性质进行展开解析-：首先将中括号内的式子展开，有ED(/(«；D)-7(x)i+(7(®)-yo)i+2(/(室D)-/(x)(7(®)-yp).然后根据期望的运算性质EA-Y-EL：E1可将上式化为"(；D)-)j÷(/(«)-Vd)1+ED2(f(x;D)-f(x)(f(x)-yo)l.一：再次利用期望的运算性质将第3步得到的式子的最后一项展开，有ED2(/3；D)-加)(/(x)-yo)l-Ed2(x;D)-/(x)-/(»)-Ed|2(/(«D)-/(x)皿.首先计算展开后得到的第1项，有ED2U(MD)_/(«)-，(到=Ed2(三;D)加)-2/(®)-f(x).由于N)是常量，所以由期望的运算性质：E1r.A-13.1E÷B(其中AB均为常量)可得Ed2U(MD)-7(®)7(®)-2f(x)%f(x;D)-2(>)f(x)由式(2.37)可知E"(rD)l。0，所以Ep2(fx.D)-7(x1)f(*)=2.>)fix)-2px)./(x)=(接着计算展开后得到的第二项ED2(j(xD)-f(x)yo=2E11j(xD)yp-2(z)EDd>由于噪声和/无关，所以“工0和助是两个相互独立的随机变量.根据期望的运算性质EbVVl.EXEIW(其中讲口为相互独立的随机变量)可得ED2(/(工；D)-，)H=2Ed(z;。)2，(工)EDM=2E0/(«*。)1EDfol-2/(®)EDyo三2/(®)EdFvdI-2f(x)E11IvdI=0,所以“2(/3；0-，力)伊力-加)=%2(z;D)-/(z)f(x-Ed2(/3；D)-喇血=0+0nI：因为"工)和U均为常量，根据期望的运算性质，有中的第2项En(/(*)y)=(，y)'同理有中的最后一项(，一y)(y-沏)«2(f(x)-y)Ep-y11.由于此时假定噪声的期望为零，BIJEnfe-IZDl-O,所以2Ed(/(n)-(V-刖)-2(7(x)-j)-0=0.附注二项分布参数加勺检验1设某事件发生的概率为，D未知.做E次独立试验，每次观察该事件是否发生，以Ti己该事件发生的次数，则Y服从二项分布由m.D),现根据Y检验如下假设：Hq：PAi；HI:p>.由二项分布本身的特性可知：礴小，'取到较小值的概率越大.因此，对于上述假设，一个直观上合理的检验为夕：当YWr时接飘否则就拒绝Hn其中，CUN表示事件最大发生次数.此检验对应的功效函数为)-p(xO-1-P(XO氢A】_广由于“"越小，K取到较小值的概率越大”可以等价表示为：RX，C)是关于，的减函数，所以H(P)P(Xc=-c是关于的增函数，那么当禽时,MR)即Mri的上确界.又根据参考文献口中5.1.3的定义1.2可知，检验水平C默认取最小可能的水平，所以在给定检验水平C时，可以通过如下方程解得满足检验水平C的整数：更为严格的数学证明参见参考文献山中第二章习题7a=sup(p).显然，当D内时有Qt-Slip(p),即()对于此方程，通常不一定正好解得一个使得方程成立的整数C较常见的情况是存在这样一个倒吏得营(：)出(1-网广，Q此时，Q只能取万或者日+1.若门虹，则相当于升高了检验水平C；若C取自+】则相当于降低了检验水平m具体如何取舍需要结合实际情况，但是通常为了减小犯第一类错误的概率，会倾向于令Q取L下面考虑如何求解E易证%伉)是关于O的减函数，再结合上述关于不的两个不等式易推得C=minCs.t.E('：j(1<a参考文献陈希孺.概率论与数理统计M.合肥：中国科学技术大学出版社,2009.第3章线性模型式(3.5)甯i=2-Xeig)解析EEsb-VIyI«r,by已知七，所以¾a=£("«一"=£/®iTi/：1m=£2(弘一叼-b)(-引E2.(arf-yrr,÷r,)/mmmB1b!J/mm=2(wx<(yifc)zi三1Jl式(3.6)2(6-£(欢wxi)解析m/,，='，,-b)2已知七，所以>i三1三1/=2卜6"V2(y叼)式(3.7)£以q-工)解析令式(3.5)等于0,有wim0=10Xd-22(1-b)zj,MI口1初£»?=£的石_工蚂.fc=li=l11。、1?.1S由于令式(3.6)等于0可得,nr,又因为",占且,则b=#-Wi,代入上式可得wiinm»52«?-$2u-$2(s-vf)xi,i=l1-WEj?=E眄一旷£片+，£孙i=li=lUl曰i三1/i»lUlyJ2>=_£物Cq=Vift至Z/=£与、2片=将占白会和Mm三T白m£断（片）i=l（£）代入上式，即可得式(3.7)：如果要想用PythOn来实现上式的话，上式中的求和运算只能用循环来实现.但是如果能将上式向量化，也就是转换成矩阵（即向量）运算的话，我们就可以利用诸如NUmPy这种专门加速矩阵运算的类库来进行编写.下面我们就尝试将上式进行向量化.If?)=£将m/M代入分母可得mEM(XjT)-=LEdTEXii=m-M)'£(4-*)'又因为电一日点七楼汽EE.IWEX1T=J1=rm-jt=mj2=j2-JrF£r,则有£3(切片一.一ii+)二，一一.一总)ZZl(r)(.:必1-i)j若令r11；12i,j,-Ici/r.JI为去均值后的a三;V三(.Vi,L'',.,Va:,-"e-0)'T为去均值后的I/,代入上式可得N、ZJlJ的为彳加列的列向量吗Ml而式(3.10)-2X1(XwV)/w解析将入y-Xtr)T(1/,w展开可得EA=VrV-VirXw-wXv÷W1XXw对阖七导可得%_%_<T_g以&gTTDw)Z>w+o=O-XTu-XTy÷(XTX+XTX)W=2XT(Xiir-MarxxaxAjct矩阵微分式k=k=",F-=A+4)X式(327)Ea)=E(-+hj(÷Sq)1解析将式(3.26)代入式(3.25)可得m，三£m(lM>(稣+(1-*)M&例)I其中3)二"1二。,代入上式可得-E(In(MTl+I一机)一In(l+JTAt)由于30或1,则Z1(-h>(÷),1i-ln(l÷)5w=l两式综合可得K粉=E(y-b(l+-)由于此式仍为极大似然估计的似然函数，所以最大化似然函数等价于最小化似然函数的相反数，即在似然函数前添加负号即可得式(3.27).值得一提的是，若将式(3.26)改写为p(v,!z,:w,6)-(Pl;。)MA)住.6)3,再代入式(3.25)可得咐=WhI(3(禽;0)卢3(禽M尸)m£(玳M(P1出；户)+(1-断)加3(飘;Q)ferlVR=£(机(m(pi出；砌-m3(却0)+卜佃(0)I我MSD"(石砌=EmlD+h*()三EG#TZ-In(1+4*)U=I显然，此种方式更易推导出式(3.27).式(3.30)翳=-毕心-m知)解析此式可以进行向量化.令小工，"代入上式得1.4=1m=一弘)=X(6-Ir)=XT(PI(X-1/).式(332)j_9丁(耿1)(出一"1-3w(7o+7)w解析jw0-w1W(n+)WWT(Ee+)wIgF)TTI：WT(Eo+E)w3心I)TTTU外产9W(b+)W=w(-1)(-l)wW(2o+Si)W-式(3.37)SAW=XSttw解析由式(3.36),可定义拉格朗日函数为1.(w.X=wSw+AlwSuw-1).对f球偏导可得L(wt)(w,Sw)$Ad(WlS.to-1)wi)w+Ihn-(Sk÷Sj)w÷(Slr+Sj)w=IShW»2ASw.这是由于SbsLSs三令上式等于O即可得-2SfrW+2Sww-OSkW=ASMlM由于我们想要求解的只有ff,而拉格朗日乘子调体取值多少都无所谓，因此可以任意设定工来配合我们求解E注意到SbW=(il-1)(-w1如果我们令入IA"仆叫那么上式即可改写为SbW=A(4,-1),将其代入SAW=ASbuJ即可解得W=S("ii-J式(3.38)Sw=(o-J参见式(3.37)式(3.39)幡=S(一J参见式(3.37)式(3.43)Sb-St-SwN=-)3尸a=l解析由式(3.40)、式(3.41)、式(3.42河得：N«=£")(A-产-EE(x-j)(aB-i)1*i=J2f(<x.")(工-尸一(工-四)(N-M)T)=E(£(N.)(NT-")-(N-同M-用)IJx,/BBE(E(HNT-N"Jr+""JjCXr+N"J+"-iHE(E(_叩T-MXT+r+叩:+ixl-JlUwJG一£(-£叩丁一£",+£""+IXJGXX,EWT+EE出痔"Xa,»pX.-52(-mt"-mi+mtr+mii+mii-mltT)-E(-GM"T-ni1+mir+miil=Ern.(一四r+/)N-)(l-)1-1式(3.44)FWTSM)xU(WjSttW)解析此式是式(3.35)的推广形式，证明如下.设W-(叫孙r.lw.v.)Rd*'v11,其中皿Xm为d行1列的列向量，则INTtr(WTSsW)=EWTSmH-IKr(WSttW)=Ew7Swwi.*=所以式(3.44)可变形为N-IEwSbwiMXNT=rl对比式(3.35)易知，上式即式(3.35)的推广形式.式(3.45)SW=XS.W解析同式(3.35),此处也固定式(3.44)的分母为1,那么式(3.44)此时等价于如下优化问题minv-Ir(WTSM)a.tr(IVtSwIV)=1根据拉格朗日乘子法，可定义上述优化问题的拉格朗日函数1.(WR三-EWTSbW)+MEWTSleW)-1).根据矩阵微分式焉”(XTEX).(B+BT)X对上式关于侬偏导可得叫人)(tr(WSbW)Mtr(WTSM-1)HW-=OW十.W=-(Sb+SDIV÷(Su,÷Sj)W=2SltW.2SttW.这是由于SbS11SS2令上式等于n即可得-2SbW+2SWEOSlW=ASsW第4章决策树式(4.1)朗Ent(D)-22¼k«2P*-1解析下面证明OEEnt(D)lojy.已知集合毗信息焙的定义为叫Enl(D)-5¼log2pop*l.Vp=1其中，Iyl表示样本类别总数，小表示第1,类样本所占的比例，有匕.若令/瓜热：.，那么信息端Em(D)就可以看作一个11元实值函数，即Ent(D)=/(/,4)=-Enbg2SJlnoj,y-I其中W下面考虑求该多元函数的最值.首先我们先来求最大值，如果不考虑约束。fc】而仅考X4=1虑匕,则对方片)求最大值等价于如下最小化问题：RminErkIog2IrAns.t.=1.=l显然，在D¢q¢1时，此问题为凸优化问题.对于凸优化问题来说，使其拉格朗日函数的一阶偏导数等于0的点即最优解.根据拉格朗口乘子法可知，该优化问题的拉格朗日函数为«1.xl,xw,)J2zklog3x4÷其中，X为拉格朗日乘子.对H4.a分别关于4.棣一阶偏导数，并令偏导数等于O可得T胡犀T)卜。=】叫i÷rirz+A=OJrIhI2=r+市+A=O、.In=-log9一2In2；叫湛”唱位如“(£“)卜。nL-白；°mtit"'-"=工位斗-讣。5;"("NA)/gztlaz4+xt-ljj=0=>r*=1=1.整理一下可得(A=-log3x1-=-¾-="2xll"占.j-1=由以上两个方程可以解得1B=D=XB=丁又因为I还需满足约束D<4«1，显然所以，I=及=Q=;是满足所有约束的最优解，即当前最小化问题的最小值点，同时也是/3的最大值点.将 =项| =”弋入“5.4)中可得/f-.,-J="Vk-log：-=-n-IogJ-=l211n"WnFlnn。-1£以=1所以n.zJ在满足约束匕时的最大值为kf.Vx4=I下面求最小值.如果不考虑约束X而仅考虑D<q<L贝J"ei.，人)可以看作D个互不相关的一元函数的和，即/(j,1tr)£g(n),Jl其中，Eh)=-了a1。了hWnWL那么当trJo(n川/,分别取到其最小值时，)也就取到了最小值.所以接下来考虑分别求厂，各自的最小值，由于q(h)M7理/的定义域和函数表达式均相同，所以只需求出)的最小值也就求出了H羽)”/)的最小值.下面考虑求“工力的最小值，首先对MZl段于北求一阶和二阶导数，有4项)=-d;=-x-x=小)d(z1)一"四-春)1显然，当。*4*】时,""=-J11恒小于0,所以(Mi)是一个在其定义域范围内开口向下的凹函数，那么其最小值必然在边界取.分别取h=。和Ti=L代入方)可得计算信息燧时约定：若£=(1,贝/kH=Og()=-Ol0g9O=O="Uog9I=0所以，Mr力的最小值为0,同理可得“工。.”人)的最小值也都为0,即4、.xj的最»En=I.£Xfc=1小值为0.但是，此时仅考虑约束DMg<，而未考虑M.若考虑约束£；,那HVx*=l么方.工)的最小值一定大于等于。.如果令某、个n=1，那么根身约束y可知A=/一UI-".1nn0,将其代入方.)可得0k0-0/(0,0,.t0,l,0,.,0)-OloEoO-Okc4O0*0lkl-0k0所以=1,口，n-=n+=0一定是“方.z三)在满足约束En=IM和。，441的条件下的最小值点，此时/取到最小值o.综上可知，当方.匚)取到最大值时：片.乃此时样本集合纯度最低；当“，工.)取到最小值时：=L11=n=n1=.=。，此时样本集合纯度最高.式(4.2)Ga(D,a)=Ent(D)-石胃加(。)解析此为信息增益的定义式.在信息论中信息增益也称为互信息(参见本章附注)，表示已知一个随机变量的信息后另一个随机变量的不确定性减少的程度.所以此式可以理解为，在己知属性口的取值后，样本类别这个随机变量的不确定性减小的程度.若根据某个属性计算得到的信息增益越大，则说明在知道其取值后样本集的不确定性减小的程度越大，即“西瓜书”上所说的“纯度提升”越大.式(4.6)GiniJndex(D,)三GhIXDe)解析此为数据集冲属性。的基尼指数的定义，表示在属性的取值已知的条件下，数据集按照属性。的所有可能取值划分后的纯度.不过在构造CART决策树时并不会严格按照此式来选择最优划分属性，主要是因为CART决策树是一棵二叉树，如果用上面的式去选出最优划分属性，无法进一步选出最优划分属性的最优划分点.常用的CART决策树的构造算法如下：(1)考虑每个属性的每个可能取值力，将数据集D分为n-»和。*两部分来计算基尼指数，即GiniJDdex(Ra)Gini(Dzw)+璃巧；DU选择基尼指数最小的属性及其对应取值作为最优划分属性和最优划分点；重复以上两步，直至满足停止条件.下面以“西瓜书”中表4.2中西瓜数据集2.0为例来构造CART决策树，其中第一个最优划分属性和最优划分点的计算过程如下：以属性“色泽”为例，它有3个可能的取值：青绿,乌黑,浅白,若使用该属性的属性值是否等于“青绿”对数据集侬行划分，则可得到2个子集，分别记为次色泽=青绿）,M色泽州绿）.子集加包含编号H61S77）共6个33样例，其中正例占Pl=就反例占出=/子集R包含编号f2阎共5_611个样例，其中正例占PiTL反例占内=石，根据式（4.5）可计算出用“色泽二青绿”划分之后得到基尼指数为Giniindex。色泽=青绿）=×（-G）,-G）S×0-（）1-（n=-类似地，可以计算出不同属性取不同值的基尼指数如下：Ginijndex（11色泽=乌黑）=0.456Ginijndex（色泽=浅白）=0.426Gini_index（q根蒂=蜷缩）=0.456Gini_index（A根蒂=稍蜷）=0.496GinijhndeX（Jl根蒂=硬挺）=0.439Gini_indeX（A敲声=浊响）=0.450Gini_index（A敲声=沉闷）=0.494Gini_index（71敲声=清脆）=0.439Gini_indeX（A纹理=清晰）=0.286Gini_index（A纹理=稍稀）=0.437Gini_index（A纹理=模糊）=0.403Gini_index（A脐部=凹陷）=0.415GiniJndeX（A脐部=稍凹）=0.497GinLindeX（A脐部=平坦）=0.362Gini_indeX（C触感=硬挺）=0.494Gini_index（Z触感=软粘）=0.494.特别地，对于属性"触感''，由于它的可取值个数为2,所以其实只需计算其中一个取值的基尼指数即可.根据上面的计算结果可知，Gini_index(C纹理=清晰)=0286最小，所以选择属性“纹理”为最优划分属性并生成根节点，接着以“纹理=清晰”为最优划分点生成纹理=清晰)、M纹理清晰)两个子节点，对两个子节点分别重复上述步骤继续生成下一层子节点，直至满足停止条件.以上便是CART决策树的构建过程，从构建过程可以看出，CART决策树最终构造出来的是一棵二叉树CART除了决策树能处理分类问题以外，回归树还可以处理回归问题，附注中给出了CART回归树的构造算法.式(4.7)lin-l此式所表达的思想很简单，就是以每两个相邻取值的中点作为划分点.下面以“西瓜书”中表4.3中西瓜数据集3.0为例来说明此式的用法.对于“密度”这个连续属性，己观测到的可能取值为0.243,0.245,0.343,0360,0.403,0.437,0.481,0.556,0.593,0.608,0.634,0.639,0.657,0.666,0.697,0.719,0.774)共17个值,根据式(4.7)可0.243 + 0.2450.245 + 0.343知，此时,依次取1到16,那么“密度”这个属性的候选划分点集合为0.3600.4030.403+0.4371).437+0.4810.481IO.550.55610.5930.5.+0.6082'2'20.606+0.6340.634+0.6390.639+0.6570.657+0.6660.666+0.970.97+0.7190.71»+0.774式(4.8)Gain。)三maxGaiu(D.0.1)吃EIIt(D)-XEnt(D?)此式是式(4.2)用于离散化后的连续属性的版本，其中71由式(4.7)计算得来，X快示属性。的取值分别小于等于和大于候选划分点，时的情形，即当*=-时有勿=。?匕当=+时有山=。?乂.附注互信息1在解释互信息之前，需要先解释一下什么是条件熠.条件端表示的是在已知一个随机变量的条件下，另一个随机变量的不确定性.具体地，假设有随机变量讲口V且它们服从以下联合概率分布P(X=Y=的)=pij,i=1,2,ln,j=lt2.那么在已知那J条件下，随机变量阴J条件燃为EwylX)L£P,Em(YIX-jri)1i=l其中，用=PLV=Tj=12,凡互信息定义为信息焙和条件熠的差，它表示的是已知一个随机变量的信息后使得另一个随机变量的不确定性减少的程度.具体地，假设有随机变量期UY那么在已知的信息后，的不确定性减少的程度为l(y：X)=Ent(yO-Eiit(YlX).此即互信息的数学定义.CART回归树1假设给定数据集D=%Ih)其中工URd为榛特征向量，VR是连续型随机变量.这是一个标准的回归问题的数据集，若把每个属性视为坐标空间中的一个坐标轴，则/个属性就构成了一个潍的特征空间，而每个榛特征向量僦对应了彼的特征空间中的一个数据点.CART回归树的目标是将特征空间划分成若干个子空间，每个子空间都有一个固定的输出值，也就是凡是落在同一个子空间内的数据点叫它们所对应的输出值函相等，且都为该子空间的输出值.那么如何划分出若干个子空间呢？这里采用一种启发式的方法.任意选择一个属性/1,遍历其所有可能取值，根据下式找出属性“优划分点”V*=argminminE(yc)a+minE(IN-0尸1.Ge*(28BteJMaVV)中的样本畤寸应的输出值g均值，即Cl-ve(yixRl(OVtO)-S - ve(W* ft(a>v)-国前.总的遍历所有属性，找到最优划分属性/11然后根据尚最优划分点将特征空间划分为两个子空间，接着对每个子空间重复上述步骤，直至满足停止条件.这样就生成了一棵CART回归树，假设最终将特征空间划分为H个子空间小片一Ru,那么CART回归树的模型式可以表示为/（X）=TWRm）.m-1同理，其中的c示的也是集合A中的样本H；应的输出值的均值.此式直观上的理解就是,对于一个给定的样本，首先判断其属于哪个子空间，然后将其所属的子空间对应的输出值作为该样本的预测值.如参考文献1李航.统计学习方法M.北京：清华大学出版社,2012.第5章神经网络式(5.2)Atrl=Mu-v)rl解析此式是感知机学习算法中的参数更新式，下面依次给出感知机模型、学习策略和学习算法的具体介绍1感知机模型已知感知机由两层神经元组成，故感知机模型的式可表示为y=/Mixi_a)=fwrx-，)，其中，NURn,为样本的特征向量，是感知机模型的输入；9/是感知机模型的参数，wR",为权重，闩为阈值.假定f为阶跃函数，那么感知机模型的式可进一步表示为用M)代表阶跃函数y三wx-三f。书由于Fl维空间中的超平面方程为+Mj,+tt'MTa+6=11，Ti+=0.所以此时感知机模型式中的WT工A可以看作是n维空间中的一个超平面，将ri维空间划分为ICiZ-630和MJT"Wn两个子空间，落在前一个子空间的样本对应的模型输出值为b落在后一个子空间的样本对应的模型输出值为0,如此便实现了分类功能.感知机学习策略给定一个线性可分的数据集T(参见本章附注)，感知机的学习目标是求得能对数据集了中的正负样本完全正确划分的分离超平面“Jir自=(k假设此时误分类样本集合为MCr对任意一个误分类样本来说，当wx-(),模型输出值为。=1,样本真实标记为VO;反之，当Mj工一Q。时，模型输出值为0=0,样本真实标记为V-L综合两种情形可知，以下式恒成立：管一y）（ST工一©）所以，给定数据集T,其损失函数可以定义为1.(w.)-Ely-y)(w,X-¢).a”显然，此损失函数是非负的.如果没有误分类点，则损失函数值为0.而且，误分类点越少，误分类点离超平面越近，损失函数值就越小.因此，给定数据集T,损失函数皿例是关于S那的连续可导函数.