其他分類方法

第六章其他分類方法回顧：最簡單的分段線性分類器：把各類劃分為若干子類，以子類中心作為類別代表點，考查新樣本到各代表點的距離并將它分到最近的代表點所代表的類。極端情況，將所有樣本都作為代表點近鄰法(Nearest-Neighbormethod)6.1近鄰法(Nearest-NeighborMethod)6.1.1最近鄰法樣本集s=Rx,e),(x,0),???,(x,0)}N1122NNx.:樣本，0：類別標(biāo)號，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))——最近鄰決策(一近鄰決策)

另一種表達(dá)方法：3類判別函數(shù)i另一種表達(dá)方法：3類判別函數(shù)ig.(x)=m中—Xk||,kxk,k=1,…,Ni i i決策規(guī)則：fgj（x）=豐屮，thenX長最近鄰法的錯誤率（漸近分析）結(jié)論：P*<P<P*「2—cp*「1Ic—1丿其中：P*：貝葉斯錯誤率P1：樣本無窮多時最近鄰法的錯誤率（漸近平均錯誤率）前提：樣本集獨(dú)立同分布6.1.2k-近鄰法(kNN)最近鄰法(一近鄰法)的推廣：找出x的k個近鄰，看其中多數(shù)屬于哪一類，則把x分到哪—類。一般表示：c類i，i1,,c，N個樣本。ik.,i1，c%x的k個近鄰中屬于的樣本數(shù)ii判別函數(shù)：gi(x)ki，i1,,cii決策規(guī)則：ifgj(x)maxki，thenxjJ 」1 丄 Ji1,,c

或者簡化為 p*<p<2P*k問題存儲量和計算量票數(shù)接近時風(fēng)險較大，有噪聲時風(fēng)險加大有限樣本下性能如何？改進(jìn)：減少計算量和存儲量引入拒絕機(jī)制根據(jù)實際問題修正投票方式如加權(quán)投票，否決票等如距離加權(quán)，考慮樣本比例及先驗概率等

6.1.3近鄰法的快速算法近鄰法在計算上的問題：需存儲所有訓(xùn)練樣本新樣本需與每個樣本做比較快速算法基本思想：把樣本集分級分成多個子集（樹狀結(jié)構(gòu)）每個子集（結(jié)點）可用較少幾個量代表通過將新樣本與各結(jié)點比較排除大量候選樣本只有最后的結(jié)點（子集）中逐個樣本比較，找出近鄰

基本算法：分支定界算法（Branch-BoundAlgorithm）符號約定：X：結(jié)點p對應(yīng)的樣本子集pN：X中的樣本數(shù)ppM：子集X中的樣本均值（中心點）ppr=maxD（x，M）:x中離中心點最遠(yuǎn)的距離P7 1B：當(dāng)前搜索到的最近鄰距離1.事先把樣本子集劃分好(比如用1.事先把樣本子集劃分好(比如用聚類算法)，規(guī)則：1?對新樣本x，結(jié)點Xp若D(x,M)>B+rpp則x的近鄰不可能在X中p2.對新樣本x，結(jié)點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（當(dāng)前結(jié)點）。2。 （當(dāng)前結(jié)點展開）把當(dāng)前結(jié)點的直接子結(jié)點放入（當(dāng)前水平的）一個目錄表（活動表）中，對它們計算并存儲D（兀M）。p（注意：活動表在每個水平上一個，下文均指當(dāng)前水平的活動表）3。 （檢驗）對活動表中每個結(jié)點，若D（x,M）>B+r，則從表中去掉。p p規(guī)則1）4。 （回溯）若活動表中已無結(jié)點，則回到上一級，置L=L-1如L==0，則算法終止；如L豐0，則轉(zhuǎn)3。；若活動表中有結(jié)點，則繼續(xù)5。。5。 （選擇最近結(jié)點）在目錄表中選擇最近結(jié)點（D（x,M）最小），記為p，以它為當(dāng)前結(jié)點，若當(dāng)前p水平l為最終水平，則轉(zhuǎn)6。。否則，置L=L+1，轉(zhuǎn)2。。

6。(檢驗)規(guī)則2)對當(dāng)前結(jié)點p中的每個規(guī)則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被檢驗過之后，轉(zhuǎn)3。。算法終止時，輸出x的最近鄰仏和gxNN)=B(K-近鄰時只須修正上述算法的第6。步)

應(yīng)將它們從樣本集中去掉?；舅悸罚嚎疾闃颖臼欠駷榭赡艿恼`導(dǎo)樣本，若是則從樣本集中去掉——剪輯?？疾榉椒ㄊ峭ㄟ^試分類，認(rèn)為錯分樣本為誤導(dǎo)樣本基本做法：將樣本集分為考試集XNT和參考集XNR：XN=XNTUXNR,XNTQXNR=0剪輯：用XNR中的樣本對XNT中的樣本進(jìn)行近鄰法分類剪掉xNT中被錯分的樣本，xNT中剩余樣本構(gòu)成剪輯樣本集XNTE分類：利用XNTE和近鄰法對未知樣本x分類。思考：將樣本集分為考試集和參考集是為了剪輯的獨(dú)立性，但既然樣本都是獨(dú)立的，可否考慮下面的做法？（借鑒LOOCV）即：對XN中每個J，用所有其他樣本對它分類，若分錯則剪掉。

錯誤率分析(漸近錯誤率)若用最近鄰剪輯，用最近鄰分類，則錯誤率PiE(e1X)=2[1CIx)]即 P(e)<P(e)(P(elx)、P(e)是近鄰法的錯誤率)二二2P(e)當(dāng)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當(dāng)kT8時Pe(e)收斂于p*(N應(yīng)更快地趨向 )k多類情況，多類剪輯近鄰錯誤率Pe(e1x)小于兩類情況c重復(fù)剪輯樣本足夠多時，可多次重復(fù)剪輯，效果更好。一種重復(fù)剪輯算法一一MULTIEDIT：(散開)把xn隨機(jī)劃分為s個子集，X.…,X,s>31x(分類)用x對x中的樣本分類，i=1,…,s(i+1)mad(s) i(剪輯)去掉(2)中錯分的樣本(混合)將剩下的樣本合在一起，形成新的XN(XNE(終止)如果最后k次迭代都沒有樣本被剪掉，則停止；否則用新的XN轉(zhuǎn)(1)。算法停止后，用最后的XNE作為分類的樣本集6.1.5壓縮近鄰法主要用以減少計算量將xN分為X和X，開始時X中只有一個樣本，X中為其余樣本?？疾閄中每個sGsGG樣本，若用X可正確分類則保留，否則移入X，……最后用X作分類的樣本集。sss可與剪輯法配合使用。例：例：6.1.6可做拒絕決策的近鄰法由于近鄰法決策實際只取決于個別樣本，因此有時風(fēng)險較大，尤其是最近鄰法和k近鄰法當(dāng)兩類近鄰數(shù)接近時，為此，可考慮引入拒絕決策。1方法很簡單： 設(shè)某個k‘>*k+1)， 伙'<k)只有當(dāng)x的k個近鄰中有大于或等于k'個屬于o類時，i才決策x「,，否則拒絕――簡單多數(shù)n絕對多數(shù)拒絕決策同樣可引入改進(jìn)的近鄰法中，比如剪輯近鄰法6.2決策樹與隨機(jī)森林6.2.1非數(shù)值特征(nonmetricfeatures)?名義特征(nominalfeatures)■如性別、民族、職業(yè)、字符串中的字符、DNA序列中的核酸類型(A、C、G、T)等?序數(shù)特征(ordinalfeatures)如序號、分級等，是一種數(shù)值，有順序，但不能看作是歐式空間中的數(shù)值?與研究目標(biāo)之間呈非線性關(guān)系的數(shù)值特征比如年齡、考試成績、溫度等?區(qū)間(interval)數(shù)據(jù)取值是實數(shù)，可以比較大小，但沒有一個“自然的”零，如溫度汽車銷售店客戶情況的例子顧客編號年齡性別月收入是否購買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否經(jīng)過初步整理后的顧客數(shù)據(jù)顧客編號年齡性別月收入是否購買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方法香農(nóng)熵(ShannonEntropy)kI=—(PlogP+PlogP+ +PlogP)=—PlogP121222k2ki2ii=1節(jié)點的熵不純度汽車顧客的例子里，在不考慮任何特征時，I(16汽車顧客的例子里，在不考慮任何特征時，I(16,4)=——log| +log(16 2(16丿16如采用年齡作為根節(jié)點，則把所有樣本分為兩組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過學(xué)習(xí)與決策樹的剪枝過學(xué)習(xí)(overfitting)問題OvertlttmgmID3□aI i i i i i i i iae?- ___一一'~q；. f—ontiainingdata-itnsizeoftree先剪枝1）數(shù)據(jù)劃分法2）閾值法3）信息增益的統(tǒng)計顯著性分析

后剪枝（1）減少分類錯誤修剪法（2）最小代價與復(fù)雜性的折衷（3）最小描述長度（MDL）準(zhǔn)貝”6.2.4隨機(jī)森林Bootstrap（自舉） ■■Sample1VotingBootstrapSample2BootstrapSampleNOrisiualDatasetDecision ■■Sample1VotingBootstrapSample2BootstrapSampleNOrisiualDatasetDecisionTree1TreeNTree2P(y=1|x)P(y=1|x)=ea+卩x1+e?+Px6.3羅杰斯特回歸線性回歸y=B+Bx+011羅杰斯特（Logistic）函數(shù)幾率(odds)蔦二-“1-P(yIx)對數(shù)幾率(logodds)ln|P(y1x)〔1-P(yIx)丿=a+Px羅杰斯特回歸(LogisticRegression)logit(x)=lnP(yIx)—e卩0+p1x1+—P1+ePo+卩1x1+…+卩x

mm決策規(guī)則：若噸論):0,則:豊2羅杰斯特回歸最基本的學(xué)習(xí)算法是最大似然法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對數(shù)似然函數(shù)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ùn)練樣本｛x x｝，用f(x)G｛—l,l｝(m=1,…,M)表示M個弱分類器在樣1N m本x上的輸出，通過AdaBoost算法構(gòu)造這M個分類器并進(jìn)行決策的具體過程如下：1°初始化訓(xùn)練樣本｛xx｝的權(quán)重w二1N,i=1,...,N。1 N if2°對m=1TM，重復(fù)以下過程利用｛w｝加權(quán)后的訓(xùn)練樣本構(gòu)造分類器f(x)g｛—1,1｝。(構(gòu)造M個弱分類器im的具體算法可以不同，如分別