其他分类方法

第六章其他分类方法回顾：最简单的分段线性分类器：把各类划分为若干子类，以子类中心作为类别代表点，考查新样本到各代表点的距离并将它分到最近的代表点所代表的类。极端情况，将所有样本都作为代表点近邻法(Nearest-Neighbormethod)6.1近邻法(Nearest-NeighborMethod)6.1.1最近邻法样本集s=Rx,e),(x,0),・・・,(x,0)}N1122NNx.:样本，0：类别标号，0.=&2,…,c}TOC\o"1-5"\h\zi 1 i—xij样本x.与x•之间的距离5(x,X)—xij1j ij .对未知样本X，求SN中与之距离最近的样本X，(类别为0，)5(x,x')=min5(x,x)j=l,…,N j则将x分到0，类，即(3(x)=0，(或记作叫(x))——最近邻决策(一近邻决策)

另一种表达方法：3类判别函数i另一种表达方法：3类判别函数ig.(x)=m中—Xk||,kxk,k=1,…,Ni i i决策规则：fgj（x）=豐屮，thenX長最近邻法的错误率（渐近分析）结论：P*<P<P*「2—cp*「1Ic—1丿其中：P*：贝叶斯错误率P1：样本无穷多时最近邻法的错误率（渐近平均错误率）前提：样本集独立同分布6.1.2k-近邻法(kNN)最近邻法(一近邻法)的推广：找出x的k个近邻，看其中多数属于哪一类，则把x分到哪—类。一般表示：c类i，i1,,c，N个样本。ik.,i1，c%x的k个近邻中属于的样本数ii判别函数：gi(x)ki，i1,,cii决策规则：ifgj(x)maxki，thenxjJ 」1 丄 Ji1,,c

或者简化为 p*<p<2P*k问题存储量和计算量票数接近时风险较大，有噪声时风险加大有限样本下性能如何？改进：减少计算量和存储量引入拒绝机制根据实际问题修正投票方式如加权投票，否决票等如距离加权，考虑样本比例及先验概率等

6.1.3近邻法的快速算法近邻法在计算上的问题：需存储所有训练样本新样本需与每个样本做比较快速算法基本思想：把样本集分级分成多个子集（树状结构）每个子集（结点）可用较少几个量代表通过将新样本与各结点比较排除大量候选样本只有最后的结点（子集）中逐个样本比较，找出近邻

基本算法：分支定界算法（Branch-BoundAlgorithm）符号约定：X：结点p对应的样本子集pN：X中的样本数ppM：子集X中的样本均值（中心点）ppr=maxD（x，M）:x中离中心点最远的距离P7 1B：当前搜索到的最近邻距离1.事先把样本子集划分好(比如用1.事先把样本子集划分好(比如用聚类算法)，规则：1・对新样本x，结点Xp若D(x,M)>B+rpp则x的近邻不可能在X中p2.对新样本x，结点p中的样本xwXip若D(x,M)>B+D(x,M)p ip则xi不是x的最近邻i两大步：计算并存储X的M,r及D(x,M)p p p ip2.用分支定界算法搜索x的最近邻

搜索算法：（最近邻）1。 （初始化）置B=g、L二0,p二0（当前结点）。2。 （当前结点展开）把当前结点的直接子结点放入（当前水平的）一个目录表（活动表）中，对它们计算并存储D（兀M）。p（注意：活动表在每个水平上一个，下文均指当前水平的活动表）3。 （检验）对活动表中每个结点，若D（x,M）>B+r，则从表中去掉。p p规则1）4。 （回溯）若活动表中已无结点，则回到上一级，置L=L-1如L==0，则算法终止；如L丰0，则转3。；若活动表中有结点，则继续5。。5。 （选择最近结点）在目录表中选择最近结点（D（x,M）最小），记为p，以它为当前结点，若当前p水平l为最终水平，则转6。。否则，置L=L+1，转2。。

6。(检验)规则2)对当前结点p中的每个规则2)若D(x,M)>D(x,M)+B,则非最近邻;p ip否则，计算D(x,x),i若D(x,x)<B，则置NN=i，B二D(x,x)iifP中所有xi被检验过之后，转3。。算法终止时，输出x的最近邻仏和gxNN)=B(K-近邻时只须修正上述算法的第6。步)

应将它们从样本集中去掉。基本思路：考查样本是否为可能的误导样本，若是则从样本集中去掉——剪辑。考查方法是通过试分类，认为错分样本为误导样本基本做法：将样本集分为考试集XNT和参考集XNR：XN=XNTUXNR,XNTQXNR=0剪辑：用XNR中的样本对XNT中的样本进行近邻法分类剪掉xNT中被错分的样本，xNT中剩余样本构成剪辑样本集XNTE分类：利用XNTE和近邻法对未知样本x分类。思考：将样本集分为考试集和参考集是为了剪辑的独立性，但既然样本都是独立的，可否考虑下面的做法？（借鉴LOOCV）即：对XN中每个J，用所有其他样本对它分类，若分错则剪掉。

错误率分析(渐近错误率)若用最近邻剪辑，用最近邻分类，则错误率PiE(e1X)=2[1CIx)]即 P(e)<P(e)(P(elx)、P(e)是近邻法的错误率)二二2P(e)当P(e)很小时，如P(e)<0.1，则有P、e(e)而P(e)<2P* (p*为贝叶斯错误率)。故此时P1E(e)接近p*。

若用k近邻剪辑，用最近邻分类，则Pe(Pe(eIx)=kP(e|x)2[1-P(eIx)]k<Pe(eIx)1当kT8时Pe(e)收敛于p*(N应更快地趋向 )k多类情况，多类剪辑近邻错误率Pe(e1x)小于两类情况c重复剪辑样本足够多时，可多次重复剪辑，效果更好。一种重复剪辑算法一一MULTIEDIT：(散开)把xn随机划分为s个子集，X.…,X,s>31x(分类)用x对x中的样本分类，i=1,…,s(i+1)mad(s) i(剪辑)去掉(2)中错分的样本(混合)将剩下的样本合在一起，形成新的XN(XNE(终止)如果最后k次迭代都没有样本被剪掉，则停止；否则用新的XN转(1)。算法停止后，用最后的XNE作为分类的样本集6.1.5压缩近邻法主要用以减少计算量将xN分为X和X，开始时X中只有一个样本，X中为其余样本。考查X中每个sGsGG样本，若用X可正确分类则保留，否则移入X，……最后用X作分类的样本集。sss可与剪辑法配合使用。例：例：6.1.6可做拒绝决策的近邻法由于近邻法决策实际只取决于个别样本，因此有时风险较大，尤其是最近邻法和k近邻法当两类近邻数接近时，为此，可考虑引入拒绝决策。1方法很简单： 设某个k‘>*k+1)， 伙'<k)只有当x的k个近邻中有大于或等于k'个属于o类时，i才决策x「,，否则拒绝――简单多数n绝对多数拒绝决策同样可引入改进的近邻法中，比如剪辑近邻法6.2决策树与随机森林6.2.1非数值特征(nonmetricfeatures)•名义特征(nominalfeatures)■如性别、民族、职业、字符串中的字符、DNA序列中的核酸类型(A、C、G、T)等•序数特征(ordinalfeatures)如序号、分级等，是一种数值，有顺序，但不能看作是欧式空间中的数值•与研究目标之间呈非线性关系的数值特征比如年龄、考试成绩、温度等•区间(interval)数据取值是实数，可以比较大小，但没有一个“自然的”零，如温度汽车销售店客户情况的例子顾客编号年龄性别月收入是否购买121男4000否233女5000否330女3800否438女2000否525男7000否632女2500否720女2000否826女9000是932男5000是1024男7000否1140女4800否1228男2800否1335女4500否1433男2800是1537男4000是1631女2500否经过初步整理后的顾客数据顾客编号年龄性别月收入是否购买1<30男中否2三30女中否3三30女中否4三30女低否5<30男高否6三30女低否7<30女低否8<30女高是9三30男中是10<30男高否11三30女中否12<30男低否13三30女中否14三30男低是15三30男中是16三30女低否ID3方法香农熵(ShannonEntropy)kI=—(PlogP+PlogP+ +PlogP)=—PlogP121222k2ki2ii=1节点的熵不纯度汽车顾客的例子里，在不考虑任何特征时，I(16汽车顾客的例子里，在不考虑任何特征时，I(16,4)=——log| +log(16 2(16丿16如采用年龄作为根节点，则把所有样本分为两组162(16丿丿=0.8113Z. 1Qage―I(6,1)+__I(10,3)=0.7946age16 16不纯度减少量(信息增益InformationGain)：AI(16)=I(16,4)—I=0.0167ageage

—般地，AI(N)=I(N)-(PI(N)+PI(N)+ +PI(N)),其中P=NN。1122 m m mm'上例中，AI (16)=I(16,4)-1 =0.0972gender genderAI (16)二I(16,4)-1 二0.0177income income6.2.3过学习与决策树的剪枝过学习(overfitting)问题OvertlttmgmID3□aI i i i i i i i iae«- ___一一'~q；. f—ontiainingdata-itnsizeoftree先剪枝1）数据划分法2）阈值法3）信息增益的统计显著性分析

后剪枝（1）减少分类错误修剪法（2）最小代价与复杂性的折衷（3）最小描述长度（MDL）准贝”6.2.4随机森林Bootstrap（自举） ■■Sample1VotingBootstrapSample2BootstrapSampleNOrisiualDatasetDecision ■■Sample1VotingBootstrapSample2BootstrapSampleNOrisiualDatasetDecisionTree1TreeNTree2P(y=1|x)P(y=1|x)=ea+卩x1+e«+Px6.3罗杰斯特回归线性回归y=B+Bx+011罗杰斯特（Logistic）函数几率(odds)蔦二-“1-P(yIx)对数几率(logodds)ln|P(y1x)〔1-P(yIx)丿=a+Px罗杰斯特回归(LogisticRegression)logit(x)=lnP(yIx)—e卩0+p1x1+—P1+ePo+卩1x1+…+卩x

mm决策规则：若吨论):0,则:豊2罗杰斯特回归最基本的学习算法是最大似然法P(x,y)=P(yIx)y,h-P(yIx)(x)仝(x,y)p(x)TOC\o"1-5"\h\zii ii ii i ii il=打匚(x,y)Hp(x)ii ii=1 i=1对数似然函数L'(p)=ln(/'(p))=才{ylnP(yIx)+(1-y)ln(1-P(yIx))}i ii i iii=1最大似然估计量就是微分方程dL(P)dP=0的解。6.4Boosting方法AdaBoost算法给定N个训练样本｛x x｝，用f(x)G｛—l,l｝(m=1,…,M)表示M个弱分类器在样1N m本x上的输出，通过AdaBoost算法构造这M个分类器并进行决策的具体过程如下：1°初始化训练样本｛xx｝的权重w二1N,i=1,...,N。1 N if2°对m=1TM，重复以下过程利用｛w｝加权后的训练样本构造分类器f(x)g｛—1,1｝。(构造M个弱分类器im的具体算法可以不同，如分别