監(jiān)督學(xué)習(xí)算法基礎(chǔ)知識整理

第三章監(jiān)督學(xué)習(xí)算法監(jiān)督學(xué)習(xí)又稱為分類(Classification)或者歸納學(xué)習(xí)(InductiveLearning)。幾乎適用于所有領(lǐng)域，包括文本和網(wǎng)頁處理。給出一個數(shù)據(jù)集D,機器學(xué)習(xí)的目標就是產(chǎn)生一個聯(lián)系屬性值集合A和類標集合C的分類/預(yù)測函數(shù)(Classification/PredictionFunction),這個函數(shù)可以用于預(yù)測新的屬性集合的類標。這個函數(shù)又被稱為分類模型(ClassificationModel)、預(yù)測模型(PredictionModel)。這個分類模型可以是任何形式的，例如決策樹、規(guī)則集、貝葉斯模型或者一個超平面。在監(jiān)督學(xué)習(xí)(SupervisedLearning)中，已經(jīng)有數(shù)據(jù)給出了類標；與這一方式相對的是無監(jiān)督學(xué)習(xí)(UnsupervisedLearning)，在這種方式中，所有的類屬性都是未知的，算法需要根據(jù)數(shù)據(jù)集的特征自動產(chǎn)生類屬性。其中算法中用于進行學(xué)習(xí)的數(shù)據(jù)集叫做訓(xùn)練數(shù)據(jù)集，當使用學(xué)習(xí)算法用訓(xùn)練數(shù)據(jù)集學(xué)習(xí)得到一個模型以后，我們使用測試數(shù)據(jù)集來評測這個模型的精準度。機器學(xué)習(xí)的最基本假設(shè)：訓(xùn)練數(shù)據(jù)的分布應(yīng)該與測試數(shù)據(jù)的分布一致。訓(xùn)練算法：訓(xùn)練算法就是給定一組樣本，我們計算這些參數(shù)的方法。本節(jié)簡要介紹以下幾種常用的機器學(xué)習(xí)算法，比如決策樹，樸素貝葉斯，神經(jīng)網(wǎng)絡(luò)，支持向量機，線性最小平方擬合，kNN，最大熵等。3.1兩類感知器見課本3.2多類感知器見課本3.3決策樹算法決策樹學(xué)習(xí)算法是分類算法中最廣泛應(yīng)用的一種技術(shù)，這種算法的分類精度與其他算法相比具有相當?shù)母偁幜?，并且十分高效。決策樹是一個預(yù)測模型；他代表的是對象屬性與對象值之間的一種映射關(guān)系。樹中每個節(jié)點表示某個對象屬性，而每個分叉路徑則代表的某個可能的屬性值，而每個葉結(jié)點則對應(yīng)從根節(jié)點到該葉節(jié)點所經(jīng)歷的路徑所表示的對象的值(類別)。決策樹僅有單一輸出，若欲有復(fù)數(shù)輸出，可以建立獨立的決策樹以處理不同輸出。如何構(gòu)造精度高、規(guī)模小的決策樹是決策樹算法的核心內(nèi)容。決策樹構(gòu)造可以分兩步進行。決策樹的生成：由訓(xùn)練樣本集生成決策樹的過程。一般情況下，訓(xùn)練樣本數(shù)據(jù)集是根據(jù)實際需要有歷史的、有一定綜合程度的，用于數(shù)據(jù)分析處理的數(shù)據(jù)集。樹以代表訓(xùn)練樣本的單個結(jié)點開始。如果樣本都在同一個類.則該結(jié)點成為樹葉，并用該類標記。否則，算法選擇最有分類能力的屬性作為決策樹的當前結(jié)點。4?根據(jù)當前決策結(jié)點屬性取值的不同，將訓(xùn)練樣本數(shù)據(jù)集分為若干子集，每個取值形成一個分枝。針對上一步得到的一個子集，重復(fù)進行先前步驟，形成每個劃分樣本上的決策樹。遞歸劃分步驟僅當下列條件之一成立時停止：給定結(jié)點的所有樣本屬于同一類。沒有剩余屬性可以用來進一步劃分樣本。以樣本組中個數(shù)最多的類別作為類別標記。AlgiJiithmdecisionTreefD,A,T)】 ifDcontainsonlytrainingexamplesofthesameclassqgCthenmakeTaleafnodelabeledwithclassy;dsdf.4—0thenmakeTaleafnodelabeledwithc$whichisthemostfrequentclassinDelse!!Dcontainsexamplesbelongingtoamixtureofclasses.Weselectasingle!!atcributetopartitionDintoSubsetssoLhateachsubseti￡purer-impurityEval-1(D);foreachattributeA,eA(={A坯…，禺})dopf三impurityEval-2(AhD)endfoiSelecte 衛(wèi)工，亠“thatgivesthebiggestimpurityreduction,computedusing-p占ifpo—<thresholdthen//屏甘docsnotsignificantlyreduceimpuritypGmakeTaleafnodelabeledwithCj,themostfrequentclassinD.dse // isabletoredixeimpurityp0MakeTadecisionnodeonLetthepossiblevaluesofbeV|,5卩對PartitionDintomdisjointsubsetsD^D》、…、basedonthemvaluesofAforeachD)in{DhD》,…,doi『0H0thimcreateabranch(edge)node7}forVjasachildnodeofJ;decisionTree(D^AT』/5丁)HA營也removedendifendfoi*endifendif決策樹的剪技：決策樹的剪枝是對上一階段生成的決策樹進行檢驗、校正和修下的過程，主要是用新的樣本數(shù)扼集(稱為測試數(shù)據(jù)集)中的數(shù)據(jù)校驗決策樹生成過程中產(chǎn)生的初步規(guī)則，將那些影響預(yù)衡準確性的分枝剪除。由于數(shù)據(jù)表示不當、有噪聲或者由于決策樹生成時產(chǎn)生重復(fù)的子樹等原因，都會造成產(chǎn)生的決策樹過大。因此，簡化決策樹是一個不可缺少的環(huán)節(jié)。尋找一棵最優(yōu)決策樹，主要應(yīng)解決以下3個最優(yōu)化問題：生成最少數(shù)目的葉子節(jié)點；生成的每個葉子節(jié)點的深度最?。?/p>

生成的決策樹葉子節(jié)點最少且每個葉子節(jié)點的深度最小。例如，對于表3-1所示的貸款申請的數(shù)據(jù)集，可以學(xué)習(xí)到一種決策樹結(jié)構(gòu),表示為圖3-1。ID12ID123456789101112131415AgeOwnhouseCreditratingClassyoungfalsefalsefairXoyoungfalsefalsegoodXoyoungtruefalsegoodYesyoungtruetruefairYesyoungfalsefalsefairXomiddlefalsefalsefairXomiddlefalsefalsegood\omiddletruetnic呂oodYesmiddlefalsetrueexcellentYesmiddlefalsetrueexcellentYesoldfalsetrueexcellentYesoldfalsetrue呂oodYesoldtruefalsegoodYesoldtruefalseexcellentYesoldfalsefalsefairNd表3-1貸款申請數(shù)據(jù)根據(jù)數(shù)據(jù)集建立的一種決策樹結(jié)構(gòu)如下:Youngmiddle1HasJob?Ownhouse?Creditrating?7\truefalse/ xtrue/zxfalse\fairgoodexcellent1、YesNoYesNoNoYesYes(2/2)(3/3)(2/2)(1/1)(2/2)(2⑵圖3-1對應(yīng)與表3-1的決策樹樹中包含了決策點和葉子節(jié)點，決策點包含針對數(shù)據(jù)實例某個屬性的一些測試，而一個葉子節(jié)點則代表了一個類標。一棵決策樹的構(gòu)建過程是不斷的分隔訓(xùn)練數(shù)據(jù)，以使得最終分隔所得到的各個子集盡可能的純。一個純的子集中的數(shù)據(jù)實例類標全部一致。決策樹的建立并不是唯一的，在實際中，我們希望得到一棵盡量小且準確的決策樹。決策樹的典型算法有ID3,C4.5,CART（分類與回歸樹）等。依次得到改進。相對于其它算法，決策樹易于理解和實現(xiàn)，人們在通過解釋后都有能力去理解決策樹所表達的意義。決策樹可以同時處理不同類型的屬性，并且在相對短的時間內(nèi)能夠?qū)Υ笮蛿?shù)據(jù)源做出可行且效果良好的結(jié)果。3.4貝葉斯分類算法貝葉斯分類器的分類原理是通過某對象的先驗概率，利用貝葉斯公式計算出其后驗概率，即該對象屬于某一類的概率，選擇具有最大后驗概率的類作為該對象所屬的類。目前研究較多的貝葉斯分類器主要有四種，分別是：NaiveBayes、TAN、BAN和GBN?！鴾蕚渲R條件概率：設(shè)A,B是兩個事件，且Pr(A)>0稱Pr(BIA)二pr(AB)為在條件A下Pr(A)發(fā)生的條件事件B發(fā)生的條件概率。乘法公式：設(shè)Pr(A)>0則有Pr(AB)二Pr(BIA)Pr(A)TOC\o"1-5"\h\z\o"CurrentDocument"全概率公式：設(shè)隨機事件A],A2,...，An以及B滿足：⑴A],A2，…，An兩兩互不相容；(2)UA=S或者BuUA；(3)Pr(A)>0(n=l,2,...)，則有n nn=1 n=1Pr(B)=FPr(A)Pr(B|A)，稱為全概率公式。n nn=1全概率公式的應(yīng)用：把事件B看作是某一個過程的結(jié)果，把A1，A2,…，An看作該過程的若干個原因，根據(jù)歷史資料，每個原因發(fā)生的概率已知(即Pr(Ai)已知)，且每一個原因?qū)Y(jié)果的影響已知(即Pr(B|Ai)已知)則可用全概率公式計算結(jié)果發(fā)生的概率，即求Pr(B)。貝葉斯公式：設(shè)隨機事件A1，A2，…，An以及B滿足：(1)A1，A2，…，An兩兩互不相容；(2)UA=S或者BuUA；(3)Pr(A)>0(n=1,2,...)，則TOC\o"1-5"\h\zn nn=1 n=1PrAB=)PrAnB=—田(AJ APr(稱為貝葉斯公式。n PrB)￡P(guān)rBA)PAr()\o"CurrentDocument"j jn=1貝葉斯公式的使用：把事件B看作某一過程的結(jié)果，把A1，A2，…，An看作該過程的若干原因，根據(jù)歷史資料，每一原因發(fā)生的概率已知(即Pr(An)已知)，如果已知事件B已經(jīng)發(fā)生，要求此時是由第i個原因引起的概率，用貝葉斯公式(即求Pr(AJB))?！鴺闼刎惾~斯(NaiveBayes,NB)算法在貝葉斯分類中，在數(shù)據(jù)集合D中，令A(yù)1?A2,…A為用離散值表示的屬性1 2 n

集合，設(shè)C具有IC個不同值的類別屬性，即c1,c2,^,c|c|,我們設(shè)所有的屬性都是條件獨立于類別，給定一個測試樣例d觀察到屬性值a1到a⑷，其中ai是Ai可能的一個取值，那么預(yù)測值就是類別j使得Pr(C=c.I4幻,...比=。⑷)最大。c被稱為最大后驗概率假設(shè)。根據(jù)貝葉斯公式，有Pr(C二c)FIpr(A二aIC二c)TOC\o"1-5"\h\zj ii jPr(A=a A=aIC=c)=1 1 IAI IAI j百 可乙Pr(C=c)11Pr(A=aIC=c)k ii kk=1 i=1因為分母對每一個訓(xùn)練類別都是一樣的，所以如果僅僅需要總體上最可能的類別為所有測試樣例做預(yù)測，那么只需要上式的分子部分即可。通過下式來判斷最有可能的類別：c=argmaxPr(C=c?jc)FIpr(A=aIC=c=argmaxPr(C=c?jjiiji=1例如，假設(shè)我們有圖4-1中的訓(xùn)練數(shù)據(jù)，有兩個屬性A和B,還有類別C，對于一個測試樣例：A=mB=q求C=?ABCmbtmstgqthstgqtgqfgsfhbfhqfrnibf圖4-1訓(xùn)練數(shù)據(jù)計算如下：對于類別為t的概率Pr(C=t)1pr(A=aIC=t)=Pr(C=t)-Pr(A=mIC=t)-Pr(B=qIC=t)=-x-xjj 25j=11類似的，對于類別為f的概率1Pr(C=f)弘(Ajj=1因此C=t的可能性較大，因此將此種情況下的類別判斷為t。樸素貝葉斯分類將每篇文檔看作一“袋子”的詞，需要做以下假設(shè)，這也是稱作“樸素的”貝葉斯的由來：?文檔中的詞都是獨立于語境生成的。?單詞被生成的概率是與它在文檔中的位置無關(guān)的。?文檔的長度與類別是無關(guān)的。通過公式推導(dǎo)，最后可以得到分類函數(shù)Pr(cId)xPr(c汕Pr(wIc)i i jij=1其中，Pr(wIc)=一入+(wj'ci)_。Tf(w,c)是詞w在c.類訓(xùn)練文檔

j'九IVI+蘭TF(w,c) j' JJkik=1集中出現(xiàn)的頻率，九是一個因子，一般設(shè)為九=l/n,n為訓(xùn)練數(shù)據(jù)的總數(shù)，當九=1時，稱為拉普拉斯延續(xù)率。加入平滑算子的目的是解決不經(jīng)常出現(xiàn)的單詞零概率估計的問題，需要對概率進行平滑處理來避免出現(xiàn)0或1概率?！鴺闼刎惾~斯文本分類的優(yōu)缺點雖然樸素貝葉斯學(xué)習(xí)所做的大部分假設(shè)都與實際情況不符，但研究表明樸素貝葉斯學(xué)習(xí)仍然能產(chǎn)生準確的模型。樸素貝葉斯學(xué)習(xí)效率很高，它只需要對訓(xùn)練數(shù)據(jù)進行一次掃描就可以估計出所有需要的概率，所以樸素貝葉斯在文本分類中得到了廣泛的應(yīng)用。3.5k最近鄰算法(kNN算法)其他學(xué)習(xí)算法是從數(shù)據(jù)中得到一個模型，稱為迫切學(xué)習(xí)，因為他們在測試之前學(xué)習(xí)得到了數(shù)據(jù)對應(yīng)的模型。相反，k-近鄰(kNearestNeighbor，kNN)是一種惰性的學(xué)習(xí)方法，因為不需要從訓(xùn)練數(shù)據(jù)中學(xué)習(xí)得到模型。學(xué)習(xí)僅僅在測試樣例需要分類時發(fā)生。k近鄰的想法很直接但是在很多場合很有效，例如文本分類。它是如下實現(xiàn)的：令D為訓(xùn)練數(shù)據(jù)集。不需要對訓(xùn)練樣本做任何操作。當測試樣例d出現(xiàn)時，算法將d和D中所有訓(xùn)練樣例比較，計算它們之間的相似度(或者距離)。從D中選出前k個最相似(相近)的樣本。這個樣例集合被稱為k-近鄰。d的類別由k近鄰中最常見的類別決定。如圖6-1所示。

I-nearstneighbornearstneighbornearstneighborI-nearstneighbornearstneighbornearstneighbor圖6-1k-近鄰分類圖示優(yōu)點：kNN方法相當于非參數(shù)密度估計方法，在決策時只與極少量的相鄰樣本有關(guān)。另外，由于kNN方法主要靠周圍有限的鄰近的樣本，因此對于類域的交叉或重疊較多的非線性可分數(shù)據(jù)來說，kNN方法較其他方法更為適合。缺點：kNN的一個不足是判斷一個樣本的類別時，需要把它與所有已知類別的樣本都比較一遍，這樣計算開銷是相當大的。比如一個文本分類系統(tǒng)有上萬個類，每個類即便只有20個訓(xùn)練樣本，為了判斷一個新樣本的類別，也要做20萬次的向量比較。這個問題可以通過對樣本空間建立索引來彌補。kNN也有另一個不足是當樣本不平衡時，如一個類的樣本容量很大，而其他類樣本容量很小時，有可能導(dǎo)致當輸入一個新樣本時，該樣本的k個鄰居中大容量類的樣本占多數(shù)，導(dǎo)致分類錯誤。因此可以采用權(quán)值的方法（和該樣本距離小的鄰居權(quán)值大）來改進。產(chǎn)生了第一個不足。總結(jié)：目前常用的解決方法是事先對已知樣本點進行剪輯，事先去除對分類作用不大的樣本。該算法比較適用于樣本容量比較大的類域的自動分類，而那些樣本容量較小的類域采用這種算法比較容易產(chǎn)生誤分。3?6、支持向量機（SVM）支持向量機（SupportVectorMachine）是Cortes和Vapnik于1995年首先提出的，它在解決小樣本、非線性及高維模式識別中表現(xiàn)出許多特有的優(yōu)勢，并能夠推廣應(yīng)用到函數(shù)擬合等其他機器學(xué)習(xí)問題中。支持向量機方法是建立在統(tǒng)計學(xué)習(xí)理論的VC維理論和結(jié)構(gòu)風(fēng)險最小原理基礎(chǔ)上的，根據(jù)有限的樣本信息在模型的復(fù)雜（即對特定訓(xùn)練樣本的學(xué)習(xí)精度,Accuracy）和學(xué)習(xí)能力（即無錯誤地識別任意樣本的能力）之間尋求最佳折衷,以期獲得最好的推廣（泛化）能力?！鳹C維：是對函數(shù)類的一種度量，可以簡單的理解為問題的復(fù)雜程度，VC維越高，一個問題就越復(fù)雜。正是因為SVM關(guān)注的是VC維，后面可以看到，SVM解決問題的時候，和樣本的維數(shù)是無關(guān)的（甚至樣本是上萬維的都可以，這使得SVM很適合用來解決文本分類的問題，當然，有這樣的能力也因為引入了核函數(shù)）。核函數(shù)將原始的樣本空間向高維空間進行變換，能夠解決原始樣本線性不可分的問題?！Y(jié)構(gòu)風(fēng)險：機器學(xué)習(xí)本質(zhì)上就是一種對問題真實模型的逼近（選擇一個我們認為比較好的近似模型，這個近似模型就叫做一個假設(shè)），但毫無疑問，真實模型一定是不知道的，既然真實模型不知道，那么我們選擇的假設(shè)與問題真實解之間究竟有多大差距，我們就沒法得知。這個與問題真實解之間的誤差，就叫做風(fēng)險（更嚴格的說，誤差的累積叫做風(fēng)險）。我們選擇了一個假設(shè)之后（更直觀點說，我們得到了一個分類器以后），真實誤差無從得知，但我們可以用某些可以掌握的量來逼近它。最直觀的想法就是使用分類器在樣本數(shù)據(jù)上的分類的結(jié)果與真實結(jié)果（因為樣本是已經(jīng)標注過的數(shù)據(jù)，是準確的數(shù)據(jù)）之間的差值來表示。這個差值叫做經(jīng)驗風(fēng)險Remp（w）o以前的機器學(xué)習(xí)方法都把經(jīng)驗風(fēng)險最小化作為努力的目標，但后來發(fā)現(xiàn)很多分類函數(shù)能夠在樣本集上輕易達到100%的正確率，在真實分類時卻一塌糊涂（即所謂的推廣能力差，或泛化能力差）。此時的情況即便是選擇了一個足夠復(fù)雜的分類函數(shù)（它的VC維很高），能夠精確的記住每一個樣本，但對樣本之外的數(shù)據(jù)一律分類錯誤?；仡^看看經(jīng)驗風(fēng)險最小化原則我們就會發(fā)現(xiàn)，此原則適用的大前提是經(jīng)驗風(fēng)險要確實能夠逼近真實風(fēng)險才行，但實際上能逼近么？答案是不能，因為樣本數(shù)相對于現(xiàn)實世界要分類的文本數(shù)來說簡直九牛一毛，經(jīng)驗風(fēng)險最小化原則只在這占很小比例的樣本上做到?jīng)]有誤差，當然不能保證在更大比例的真實文本上也沒有誤差。統(tǒng)計學(xué)習(xí)因此而引入了泛化誤差界的概念，就是指真實風(fēng)險應(yīng)該由兩部分內(nèi)容刻畫，一是經(jīng)驗風(fēng)險，代表了分類器在給定樣本上的誤差；二是置信風(fēng)險，代表了我們在多大程度上可以信任分類器在未知文本上分類的結(jié)果。很顯然，第二部分是沒有辦法精確計算的，因此只能給出一個估計的區(qū)間，也使得整個誤差只能計算上界，而無法計算準確的值（所以叫做泛化誤差界，而不叫泛化誤差）。置信風(fēng)險與兩個量有關(guān)，一是樣本數(shù)量，顯然給定的樣本數(shù)量越大，我們的學(xué)習(xí)結(jié)果越有可能正確，此時置信風(fēng)險越?。欢欠诸惡瘮?shù)的VC維，顯然VC維越大，推廣能力越差，置信風(fēng)險會變大。（匹配的可能性越小）泛化誤差界的公式為：R（w}<Remp（w}+^（n/h）公式中R（w）就是真實風(fēng)險，Remp（w）就是經(jīng)驗風(fēng)險，①（n/h）就是置信風(fēng)險。統(tǒng)計學(xué)習(xí)的目標從經(jīng)驗風(fēng)險最小化變?yōu)榱藢で蠼?jīng)驗風(fēng)險與置信風(fēng)險的和最小，即結(jié)構(gòu)風(fēng)險最小。SVM正是這樣一種努力最小化結(jié)構(gòu)風(fēng)險的算法。▲支持向量機：是將向量映射到一個更高維的空間里，在這個空間里建立有一個最大間隔超平面。在分開數(shù)據(jù)的超平面的兩邊建有兩個互相平行的超平面。分隔超平面使兩個平行超平面的距離最大化。假定平行超平面間的距離或差距越大，分類器的總誤差越小。?先從最簡單的線性可分學(xué)習(xí)，如果一個線性函數(shù)能夠?qū)颖就耆_的分開，就稱這些數(shù)據(jù)是線性可分的（如圖5-1所示），否則稱為非線性可分的。在一維空間里線性函數(shù)就是一個點，在二維空間里就是一條直線，三維空間里就是一個平面，可以如此想象下去，如果不關(guān)注空間的維數(shù)，這種線性函數(shù)還有一個統(tǒng)一的名稱 超平面（HyperPlane）圖5-1線性可分的例子實際上，一個線性函數(shù)是一個實值函數(shù)（即函數(shù)的值是連續(xù)的實數(shù)），而我們的分類問題（例如這里的二元分類問題一一回答一個樣本屬于還是不屬于一個類別的問題）需要離散的輸出值，例如用1表示某個樣本屬于類別C1,而用0表示不屬于（不屬于C1也就意味著屬于C2），這時候只需要簡單的在實值函數(shù)的基礎(chǔ)上附加一個閾值即可，通過分類函數(shù)執(zhí)行時得到的值大于還是小于這個閾值來確定類別歸屬。（前面提到的兩類感知器類似）例如我們有一個線性函數(shù)g(x)=wx+b其中，x是樣本的向量表示，wx+b=0是超平面，w是超平面的法向量。超平面不止一個，例如和圖5-1中所示的超平面平行且可劃分類別的直線都是一個超平面，因此，使用“分類間隔”來區(qū)分超平面的好壞。定義一個樣本點到某個超平面的距離：8=y（wx+b）（稱為函數(shù)間隔），III進行歸一化，用旦和丄分別代替w和b,得8=—I（X，其中l(wèi)lwII是wIIw|| ||w|| ||wi的2-范數(shù)°（IIwII叫做向量w的范數(shù)，范數(shù)是對向量長度的一種度量。）歸一化后的8?稱作幾何間隔，表示點到超平面的歐氏距離。誤分次數(shù)與幾何間隔存在關(guān)i系:誤分次數(shù)＜迭代次數(shù)5是樣本集合到分類面的幾何間隔，R=maxllxII,i=l,...,n,即R是所有樣i本中（氣是以向量表示的第i個樣本）向量長度最長的值。誤分次數(shù)一定程度上代表分類器的誤差。所以幾何間隔越大，誤分次數(shù)的上界越小。因此要選擇幾何間隔最大的超平面作為支持向量機米用的超平面。HlOHOH2 、°O\O—□wOD」■O□□margin=2w||圖5-2支持向量機的超平面其中斗：wx+b=1；H：wx+b=O；H2：wx+b=-1支持向量：落在分類界面上的點（如落在H1和H2上的點）稱作支持向量。?如何尋找最佳超平面，即最大化幾何間隔，是訓(xùn)練階段的目標。要使用通過二次優(yōu)化問題（指目標函數(shù)為二次函數(shù)，約束條件為線性約束的最優(yōu)化問題），得到的是全局最優(yōu)解。由于：函數(shù)間隔：5i=yi（wxi+b）=lg（xi）l15二 Ig（x）l幾何間隔：HwHi可以看出幾何間隔與llwll是成反比的，因此最大化幾何間隔與最小化llwll等價。而我們常用的方法并不是固定llwll的大小而尋求最大幾何間隔，而是固定間隔即函數(shù)間隔，尋找最小的llwll。凡是求一個函數(shù)的最值的問題都可以稱為尋優(yōu)問題（也叫作一個規(guī)劃問題）,又由于找最大值的問題總可以通過加一個負號變?yōu)檎易钚≈档膯栴}，因此我們下面討論的時候都針對找最小值的過程來進行。一個尋優(yōu)問題最重要的部分是目標函數(shù)。例如我們想尋找最小的llwll這件事，就可以用下面完全等價的目標函數(shù)來表示，那就是：不難看出當IIwll2達到最小時，llwll也達到最小，反之亦然（前提當然是llwll描述的是向量的長度，因而是非負的）。之所以采用這種形式，是因為后面的求解過程會對目標函數(shù)作一系列變換，會使變換后的形式更為簡潔（如求導(dǎo)）。目標函數(shù)已求出，如果不考慮約束條件同樣會造成錯誤，例如，IIwII最小化可以為0值，反映在圖中，就是H1與H2兩條直線間的距離無限大，這個時候，所有的樣本點（無論正樣本還是負樣本）都跑到了H1和H2中間。所以要加入約束條件，約束條件就是在求解過程中必須滿足的條件，體現(xiàn)在我們的問題中就是樣本點必須在H1或H2的某一側(cè)（或者至少在H1和H2上），而不能在兩者中間。方便推導(dǎo)和優(yōu)化的目的我們把間隔固定為1這是指把所有樣本點中間隔最小的那一點的間隔定為1，也就意味著集合中的其他點間隔都不會小于1，按照間隔的定義，滿足這些條件就相當于讓下面的式子總是成立：yi[（w?xi）+b]-1$0（i=1,2,…,n）（n是總的樣本數(shù)）因此我們的兩類分類問題也被我們轉(zhuǎn)化成了它的數(shù)學(xué)形式，一個帶約束的最小值的問題：min斗11"『subjectto對（wx）]+b]-lM0（i=l,2,???,n）（n是總的樣本數(shù)）自變量就是W，而目標函數(shù)是w的二次函數(shù)，所有的約束條件都是w的線性函數(shù)，這種規(guī)劃稱二次規(guī)劃（QuadraticProgramming，QP），由于它的可行域是一個凸集，也是一個凸二次規(guī)劃（特點：有解，同時也可以找到）。含有了帶不等式的約束條件。將其轉(zhuǎn)化為帶等式的約束條件。使用拉格朗日理論求出條件極值。由于w由樣本和類別確定，用數(shù)學(xué)的語言描述，就是w可以表示為樣本的某種組合：w=ayx+ayx+...+ayx111 222 nnn這些a被稱為拉格朗日乘子，而xi是樣本點即向量，yi就是第i個樣本的標簽，n就是總樣本點的個數(shù)。其中只有支持向量樣本對應(yīng)的a不為0，其他a都為0。式子也可以用求和符號簡寫一下：因此原來的g（x）表達式可以寫為：g（x）=<W,X>r=l由于式子中只有xi和x是向量，因此一部分可以從內(nèi)積符號中拿出來，得到g（x）的式子為：3g（x）=》>M<p>+bi=l其中X是變量，也就是你要分類哪篇文檔，而所有的xi都是已知的樣本。所以對于新點x的預(yù)測，只需要計算它與訓(xùn)練數(shù)據(jù)點的內(nèi)積即可，這一點至關(guān)重要，是之后使用核函數(shù)進行非線性推廣的基本前提。由于非SupportingVector所對應(yīng)的系數(shù)a都是等于零的，因此對于新點的內(nèi)積計算實際上只要針對少量的“支持向量”而不是所有的訓(xùn)練數(shù)據(jù)。有該式還可以看出對w的求解轉(zhuǎn)化為對a求解。（對偶變量dualvariable的優(yōu)化問題：是解決此凸優(yōu)化問題的第二種更為高效的解--對偶變量的優(yōu)化求解。）完成了一個弱的SVM即只能處理線性的情況，不過，在得到了對偶dual形式之后，通過核函數(shù)（Kernel）推廣到非線性的情況就變成了一件非常容易的事情了。?核函數(shù)前面已經(jīng)了解到了SVM處理線性可分的情況，而對于非線性的情況，SVM的處理方法是選擇一個核函數(shù)K（；），通過將數(shù)據(jù)映射到高維空間，來解決在原始空間中線性不可分的問題。由于核函數(shù)的優(yōu)良品質(zhì)，這樣的非線性擴展在計算量上并沒有比原來復(fù)雜多少。當然，這要歸功于核函數(shù)一一除了SVM之外,任何將計算表示為數(shù)據(jù)點的內(nèi)積的方法，都可以使用核函數(shù)進行非線性擴展。在線性不可分的情況下，支持向量機通過某種事先選擇的非線性映射（核函數(shù)）將輸入變量映射到一個高維特征空間，在這個空間中構(gòu)造最優(yōu)分類超平面。我們使用SVM進行數(shù)據(jù)集分類工作的過程首先是同預(yù)先選定的一些非線性映射將輸入空間映射到高維特征空間（下圖很清晰的表達了通過映射到高維特征空間，而把平面上本身不好分的非線性數(shù)據(jù)分了開來）：Separationmayheeiisierinhrglierdimensionsconripl^jcinlowdimensions simpleinhigherdimensionsconripl^jcinlowdimensions simpleinhigherdimensions使得在高維屬性空間中有可能將訓(xùn)練數(shù)據(jù)實現(xiàn)超平面的分割，避免了在原輸入空間中進行非線性曲面分割計算。SVM數(shù)據(jù)集形成的分類函數(shù)具有這樣的性質(zhì)：它是一組以支持向量為參數(shù)的非線性函數(shù)的線性組合，因此分類函數(shù)的表達式僅和支持向量的數(shù)量有關(guān)，而獨立于空間的維度，在處理高維輸入空間的分類時，這種方法尤其有效。用一個二維平面中的分類問題作例子：我們把橫軸上端點a和b之間紅色部分里的所有點定為正類，兩邊的黑色部分里的點定為負類。試問能找到一個線性函數(shù)把兩類正確分開么？不能，因為二維空間里的線性函數(shù)就是指直線，顯然找不到符合條件的直線。但我們可以找到一條曲線，例如下面這一條：顯然通過點在這條曲線的上方還是下方就可以判斷點所屬的類別（你在橫軸上隨便找一點，算算這一點的函數(shù)值，會發(fā)現(xiàn)負類的點函數(shù)值一定比0大，而正類的一定比0?。＿@條曲線就是我們熟知的二次曲線，它的函數(shù)表達式可以寫為:它不是一個線性函數(shù)，轉(zhuǎn)換為線性函數(shù)，新建一個向量y和a：￡■"1_X,a■■這樣g(x)就可以轉(zhuǎn)化為f(y)=va,y>，實際上f(y)的形式就是：g(x)=f(y)=ay在任意維度(四維)的空間中，這種形式的函數(shù)都是一個線性函數(shù)(其中的a和y都是多(二)維向量，自變量y的次數(shù)不大于1)。而轉(zhuǎn)化最關(guān)鍵的部分就在于找到x到y(tǒng)的映射方法。具體到文本分類問題，文本被表示為上千維的向量，即使維數(shù)已經(jīng)如此之高，也常常是線性不可分的，還要向更高的空間轉(zhuǎn)化。Eg：舉具體文本分類的例子，看看這種向高維空間映射從而分類的方法如何運作，我們文本分類問題的原始空間是1000維的(即每個要被分類的文檔被表示為一個1000維的向量)，在這個維度上問題是線性不可分的。現(xiàn)在我們有一個2000維空間里的線性函數(shù)f(x')=vw',x'>+b它能夠?qū)⒃瓎栴}變得可分。式中的w'和x'都是2000維的向量，只不過w'是定值，而x'是變量，現(xiàn)在我們的輸入是一個1000維的向量X，分類的過程是先把x變換為2000維的向量x'，然后求這個變換后的向量x'與向量w'的內(nèi)積，再把這個內(nèi)積的值和b相加，就得到了結(jié)果，看結(jié)果大于閾值還是小于閾值就得到了分類結(jié)果。只關(guān)心那個高維空間里內(nèi)積的值，分類結(jié)果就算出來了。核函數(shù)K(w,x)接受低維空間的輸入值，卻能算出高維空間的內(nèi)積值vw',x'>。如果有這樣的函數(shù)，那么當給了一個低維空間的輸入x以后，g(x)=K(w,x)+b〃低維非線性函數(shù)f(x')=vw',x'>+b〃高維線性函數(shù)K(w,x)被稱作核函數(shù)(核，kernel)，核函數(shù)的基本作用就是接受兩個低維空間里的向量，能夠計算出經(jīng)過某個變換后在高維空間里的向量內(nèi)積值。高維線性分類器，它的形式應(yīng)該是：fax》唄VK>+bi=l可以用一個低維空間里的函數(shù)來代替，如下:g（H）=力oy店（抵x）+bi=if(x')和g(x)里的a,y,b是一樣的，凡是要求內(nèi)積的時候就用選定的核函數(shù)來算。這樣求出來的a再和選定的核函數(shù)一組合，就得到分類器。針對具體問題，如何選擇核函數(shù)對核函數(shù)的選擇？現(xiàn)在還缺乏指導(dǎo)原則！?引入松弛變量問題引入：如果使用核函數(shù)向高維空間映射后，問題仍然是線性不可分的。圓形和方形的點各有成千上萬個。假如，我們有另一個訓(xùn)練集，只比原先這個訓(xùn)練集多了一篇文章，映射到高維空間以后，也就多了一個樣本點，但是這個樣本的位置是這樣的：圖中黃色那個點，它是方形的丿因而它是負類的一個樣本，這單獨的一個樣本，使得原本線性可分的問題變成了線性不可分的。僅有少數(shù)點線性不可分叫做“近似線性可分”的問題。以我們?nèi)祟惖某ＷR來判斷，說有一萬個點都符合某種規(guī)律(因而線性可分)，有一個點不符合，那這一個點是否就代表了分類規(guī)則中我們沒有考慮到的方面呢(因而規(guī)則應(yīng)該為它而做出修改)？其實更有可能的是，這個樣本點壓根就是錯誤，是噪聲，是提供訓(xùn)練集的人工分類時不小心錯放進去的。所以我們會簡單的忽略這個樣本點，仍然使用原來的分類器，其效果絲毫不受影響。但這種對噪聲的容錯性是人的思維帶來的，程序可沒有。由于優(yōu)化問題的表達式中，要考慮所有的樣本點，在此基礎(chǔ)上尋找正負類之間的最大幾何間隔，而幾何間隔本身代表的是距離，是非負的，像上面這種有噪聲的情況會使得整個問題無解。這種解法其實也叫做“硬間隔”分類法，因為他硬性的要求所有樣本點都滿足和分類平面間的距離必須大于某個值。因此由上面的例子中也可以看出，硬間隔的分類法其結(jié)果容易受少數(shù)點的控制。解決方法就是引入松弛變量，允許一些點到分類平面的距離不滿足原先的要求。由于不同的訓(xùn)練集各點的間距尺度不太一樣，因此用間隔（而不是幾何間隔）來衡量有利于我們表達形式的簡潔。原先對樣本點的要求是：y[（wx）+b]>1（i=1,2,...,n）（n是樣本數(shù)）ii意思是離分類面最近的樣本點函數(shù)間隔也要比1大。如果要引入容錯性，就給1這個硬性的閾值加一個松弛變量，即允許yi[（wxi）+b]>1-^i（i=1,2,???，n）（n為樣本數(shù)）1/1/1/:i>0因為松弛變量是非負的，因此最終的結(jié)果是要求間隔可以比1小。但是當某些點出現(xiàn)這種間隔比1小的情況時（這些點也叫離群點），意味著放棄了對這些點的精確分類，而這對我們的分類器來說是種損失。但是放棄這些點也帶來了好處,那就是使分類面不必向這些點的方向移動，因而可以得到更大的幾何間隔（在低維空間看來，分類邊界也更平滑）。顯然我們必須權(quán)衡這種損失和好處。好處很明顯，我們得到的分類間隔越大，好處就越多?；仡櫸覀冊嫉挠查g隔分類對應(yīng)的優(yōu)化問題：win i||w||2subjectto耳Ki眄）+切一40W'F）5是總的樣本數(shù)），-Iw||22""就是我們的目標函數(shù)，越小越好，因而損失就必然是一個能使之變大的量。那如何來衡量損失，有兩種常用的方式￡匚2①i=1'

其中n都是樣本的數(shù)目。兩種方法沒有大的區(qū)別。如果選擇了第一種，得到的方法的就叫做二階軟間隔分類器，第二種就叫做一階軟間隔分類器。把損失加入到目標函數(shù)里的時候，就需要一個懲罰因子（cost，也就是libSVM的諸多參數(shù)中的C）,原來的優(yōu)化問題就變成了下面這樣：minminsubjecttoy[(wx)+b]>1-Q(i=1,2,...,n)(n是樣本數(shù))(式1)i i iQ>0這個式子有這么幾點要注意：一、 并非所有的樣本點都有一個松弛變量與其對應(yīng)。實際上只有“離群點”才有，沒離群的點松弛變量都等于0（對負類來說，離群點就是在前面圖中，跑到H2右側(cè)的那些負樣本點，對正類來說，就是跑到H1左側(cè)的那些正樣本點）。二、 松弛變量的值實際上標示出了對應(yīng)的點到底離群有多遠，值越大，點就越遠。三、 懲罰因子C決定了你有多重視離群點帶來的損失，顯然當所有離群點的松弛變量的和一定時，C越大，對目標函數(shù)的損失也越大，此時就表示非常不愿意放棄這些離群點，最極端的情況是把C定為無限大，這樣只要稍有一個點離群，目標函數(shù)的值變成無限大，讓問題變成無解，這就退化成了硬間隔問題。四、 懲罰因子C不是一個變量，整個優(yōu)化問題在解的時候，C是一個你必須事先指定的值，指定這個值以后，解一下，得到一個分類器，然后用測試數(shù)據(jù)看看結(jié)果怎么樣，如果不夠好，換一個C的值，再解一次優(yōu)化問題，得到另一個分類器，再看看效果，如此就是一個參數(shù)尋優(yōu)的過程，但這和優(yōu)化問題本身決不是一回事，優(yōu)化問題在解的過程中，C一直是定值。五、 盡管加了松弛變量，解它的過程比起原始的硬間隔問題來說是一樣的。從大的方面說優(yōu)化問題解的過程，就是先試著確定一下w，也就是確定了前面圖中的三條直線，這時看看間隔有多大，又有多少點離群，把目標函數(shù)的值算一算，再換一組三條直線，再把目標函數(shù)的值算一算，如此往復(fù)（迭代），直到最終找到目標函數(shù)最小時的w。松弛變量和核函數(shù)的引入都是為了解決線性不可分的問題。松弛變量進一步解決線性不可分問題。以文本分類為例。在原始的低維空間中，樣本相當?shù)牟豢煞?，無論你怎么找分類平面，總會有大量的離群點，此時用核函數(shù)向高維空間映射一下，雖然結(jié)果仍然是不可分的，但比原始空間里的要更加接近線性可分的狀態(tài)（即達到了近似線性可分的狀態(tài)），此時再用松弛變量處理那些少數(shù)的離群點，就簡單有效得多了。本節(jié)中的（式1）是支持向量機最最常用的形式。至此一個比較完整的支持向量機框架就有了。簡單說來，支持向量機就是使用了核函數(shù)的軟間隔線性分類法。?SVM用于多類分類SVM是一種典型的兩類分類器，即它只回答屬于正類還是負類的問題。而現(xiàn)實中要解決的問題，往往是多類的問題（少部分例外，例如垃圾郵件過濾，就只需要確定“是”還是“不是”垃圾郵件），比如文本分類，比如數(shù)字識別。如何由兩類分類器得到多類分類器，在此有三種方法。以文本分類為例，現(xiàn)成的方法有很多，其中最好就是一次性考慮所有樣本，次性求解的方法計算量實在太大，基本實現(xiàn)不了。①一類對其余的方法，就是每次仍然解一個兩類分類的問題。比如我們有5個類別，第一次就把類別1的樣本定為正樣本，其余2,3,4,5的樣本合起來定為負樣本，這樣得到一個兩類分類器，它能夠指出一篇文章是還是不是第1類的；第二次我們把類別2的樣本定為正樣本，把1，3,4,5的樣本合起來定為負樣本，得到一個分類器，如此下去，我們可以得到5個這樣的兩類分類器（總是和類別的數(shù)目一致）。文章分類時，挨個分類器進行分類，最終確定文章的類別。這種方法的好處是每個優(yōu)化問題的規(guī)模比較小，而且分類的時候速度很快（只需要調(diào)用5個分類器就知道了結(jié)果）。但有時也會出現(xiàn)兩種很尷尬的情況，

例如拿一篇文章問了一圈，每一個分類器都說它是屬于它那一類的，或者每一個分類器都說它不是它那一類的，前者叫分類重疊現(xiàn)象，后者叫不可分類現(xiàn)象。分類重疊時隨便選一個結(jié)果都可，或者看看這篇文章到各個超平面的距離，哪個遠就判給哪個。不可分類時很難解決，由于各個類別的樣本數(shù)目是差不多的，但“其余”的那一類樣本數(shù)總是要數(shù)倍于正類，這就人為的造成了“數(shù)據(jù)集偏斜”問題。一對一的方法，還是解兩類分類問題，還是每次選一個類的樣本作正類樣本，而負類樣本則變成只選一個類，這就避免了偏斜。過程就是算出這樣一些分類器，第一個只回答“是第1類還是第2類”，第二個只回答“是第1類還是第3類”，第三個只回答“是第1類還是第4類”，如此下去。這樣的分類器應(yīng)該有5X4/2=10個（通式是，如果有k個類別，則總的兩類分類器數(shù)目為k（k-1）/2）。