設計基于SVM分類器

致 人類社會從工業(yè)時代到信息時代的過渡趨勢尤為明顯，促使人們對信息資源的重視越來越強，對信息獲取的需求也在不斷上升。如何從龐大的信息資源中迅速而準確地定位所需要的信息，成為當下社會研究的熱點。文本分類的出現(xiàn)與發(fā)展很好的解決了這一問題，大大提高了信息資源的使用效率，極大的減少了用戶的工作量，并且提高了文本信息的使用率，還能為社會帶來巨大的經(jīng)濟效益。文本分類是基于內(nèi)容的自動信息管理的技術(shù)。應用于信息過濾、信息檢索、搜索引擎、文本數(shù)據(jù)庫、數(shù)字管等領域，有著廣泛的應用前景。而SVM是基于統(tǒng)計學習理論的新一代機器學習技術(shù)，能很好地處理非線性、數(shù)、局部小樣本等實際的學習問題，并且利用核函數(shù)把非線性問題轉(zhuǎn)化為線性問題來解決，降低了算法的復雜度。現(xiàn)有的文本分類模型主要有決策樹（DecisionTreeDT、支持向量機、（SupportVectorMachine,簡稱SVM)神經(jīng)網(wǎng)絡算法網(wǎng)絡K-最鄰近法(KNN)、國外對于文本分類的研究起步比較早，19世紀50年代末，..Luhn提出詞頻思想并應用于文本分類中。1960年,ron教授發(fā)表了一篇論文《onrelvnc,probbilisticindxingandinformationrtrivl》，該 對文本的自動分類技術(shù)做了深入探討1962年.Borko等人提出因子分析法并用于文獻的自動分類1970年,Salton等學者提出了向量空間模型（ctorSpaceModel,簡稱為VS)，該模型將文本用一系列特征向量進行表示,大大降低了文本表示的復雜程度總的來說國外的文本分類技術(shù)發(fā)展主要分兩大階段，60~80年代，基于知識工程技術(shù)的方法；80年代后期至今，基于機器學習的方法。。國內(nèi)對于文本分類的研究起步較晚1980年教授從計算機管理分類計算機分類檢索、計算機自動分類、機編分類表等四個方面介紹了國外的發(fā)展狀況。隨后，也陸續(xù)出現(xiàn)了基于詞典法和基于專家系統(tǒng)的自動分類系統(tǒng)兩大類。等教授對基于詞典法的分類系統(tǒng)進行了研究。武等教授對基于專家系統(tǒng)的自動分類系統(tǒng)進行了研究等人用了n-grm方法對英文文本進行分類實現(xiàn)了文本分類的領19901998Joahims在文本分類技術(shù)中引入支持向量機(SV)，并實驗證明其高效性。。SVM近年來，對支持向量機的研究主要集中于支持向量機本身性質(zhì)的研究和完善以及加大支持向量機應用研究的深度和廣度兩方面。首先，理論基礎不斷擴展。統(tǒng)計學習理論的不斷完善和豐富，正則化理論的出現(xiàn)，理論，稀近理論等對于支持向?qū)⒋蟮亩我?guī)劃問題分解為一系列小的二次規(guī)劃問題，簡化了算法的運行成本。C-SVM系列算法、υ-SVM系列算法、n-lassSVM算法、RSVM算法、SM算法和LSSVM算法等變形算法通過增加函數(shù)項、變量或系數(shù)等方法使變形，形成具有某一方面優(yōu)勢或一定應用范圍的算法。最后，應用領域不斷擴大。目前，已經(jīng)成功應用于模式識別、回歸估計、數(shù)據(jù)融合等方面。支持向量機的應用發(fā)展應用如下：OsunaSVMSVM分類器完成人臉與臉的分類。利用了PCA在特征提取方面的有效性以及SVMSVM與最近鄰距離分類器相說話人識別屬于連續(xù)輸入信號的分類問題，引入隱式馬爾可夫模型HMM，建立SVMHMM的混合模型。HMMSVM適合于分類問題；HMM的結(jié)果反映了同類樣本的相似度，而SVM的輸出結(jié)果則體現(xiàn)了異類樣本間的文字/0～9UK心理測試自動分析系統(tǒng)中組合SVM和其他方法成功地進行了手寫數(shù)字的識別實驗。另外，在手寫漢字識別方面，高學等提出了一種基于SVM的手寫漢字的識別方法，SVM對手寫漢字識別的有效性。由于計算機自動抽取的圖像特征和人所理解的語義間存在巨大的差距，圖像檢索結(jié)果難以令人滿意。近年來出現(xiàn)了相關反饋方法，有關科研人員以SVM為分類器，在每次反饋中對用戶標記的正例和反例樣本進行學習，并根據(jù)學習所得的模型進行檢9918內(nèi)容：本文的任務是設計基于SVM第一章：介紹了本課題的研究目的意義，文本分類和SVM算法的國內(nèi)外研究現(xiàn) 第二章：對文本的預處理、特征表示、特征向量提取等分類過程做了簡單說明，并介紹了其他四種分類算法。第三章：介紹了支持向量機算法的基本概念和理論基礎，SVM算法在分本分類中第四章：成功設計了基于SVM的文本分類器，運用該分類器完成了分類任務，文本分類就是根據(jù)預先定義好的類別，按照一定的規(guī)則將文本集合中未知類別的文本自動確定一個類別，涉及數(shù)據(jù)挖掘、計算語義學、信息學、人工智能等個學科，法、數(shù)據(jù)挖掘技術(shù)和其它的新技術(shù)被應用到文本自動分類領域中，如：回歸模型、最近鄰分類器、規(guī)則學習算法、相關反饋技術(shù)、專家投票分類法、人工神經(jīng)網(wǎng)絡等。這些方法都能對一個預先分好類的文本集進行學習，獲取每個類別的特征，自動生成分類規(guī)則，建立一個文本分類器。文本分類的整體過程主要分為訓練過程和測試過程。利用訓練好的模型來對測試樣本進行分類，最終確定分類類別。本章主要分析文本分類過程的三大模塊，即文本預處理，特征表示以及特征向量提取。文本分類（Textcategorization）就是在給定分類類別的情況下，將未知類型的樣對分類器性能文本分類訓練過 文本分類測試過圖 分類體系結(jié)構(gòu)停用詞（StopWords）是指雖然在文本中出現(xiàn)的頻率很高，但是對分類效果來說沒有起到任何作用的詞。它的存在只會增大特征向量的維數(shù)，增加分類運算的復雜程度。通常意義上，停用詞基本可分為兩類。一類是功能詞，只在文本中起到結(jié)構(gòu)作用而沒有什么實際含義。比如the、a、n、tht、thoe等在文本中幫助描述名詞的限定ovrundraboveinon在整個語料庫中出現(xiàn)的頻率與在每篇文檔中出現(xiàn)的頻率大致相等的詞，對分類來說作用不大。詞頻統(tǒng)計為了能準確的表示訓練文本，基于統(tǒng)計學習理論的方法需要對每個單詞出現(xiàn)的頻率進行統(tǒng)計。一篇文本中，單詞是最小的單位，是能夠獨立活動并且有意義的語言成分。計算機的所有語言知識都來自機器詞典（給出詞的各項信息）、句則（以詞類的各種組合方式來描述詞的聚合現(xiàn)象）以及有關詞和句子的語義、語境知識庫。英文詞頻統(tǒng)計一般包括以下幾步：利用各種分隔符且分出詞；刪除數(shù)字和分隔符；所有單詞轉(zhuǎn)化成小寫；刪除停用表中的詞；所有詞都用其同型詞根表示。然后，計算機將自動識別文本中的單詞，進而統(tǒng)計詞頻并按出現(xiàn)的頻率排序，詞頻（termfrequn,TF,是指給定單詞在該文件中出現(xiàn)的次數(shù)，使用出現(xiàn)頻率較高的N個單詞來表示整個文檔，N就是該文本向量的維數(shù)。FSTij指示當前字符Sn個字符起和模式的第一個字符進行比較，若相等，則模式字符11用空間小且穩(wěn)定，但其消耗的時間與集合的大小成正比，算法效率低。基于查找樹的統(tǒng)計方法：一顆樹的度大于2，樹的每個節(jié)點不是包含一個或幾個關鍵字，而是含有組成關鍵字的符號。詞頻統(tǒng)計時，對集合中的每個詞同時進行處理，大大提高了統(tǒng)計效率。并且可根據(jù)實際需要在樹中查找、計算各個詞的相關信息。此方法的分為兩部分：樹的構(gòu)造算法和詞頻統(tǒng)計算法。人類的語言結(jié)構(gòu)是非常復雜的，所以需要將文本數(shù)據(jù)轉(zhuǎn)化成計算機可以識別和處理的形式，才能對數(shù)據(jù)進行分析和分類，這是文本分類最基本的問題。下面對布爾模型和向量空間模型這兩種特征表示的方法做一簡單介紹。布爾（Boolean）模型是基于集合論和布爾代數(shù)的一種比較簡單的文本表示模型，它是根據(jù)特征項是否在文本中出現(xiàn)來為特征項賦值，若特征項出現(xiàn)則為10。目前文本表示最常用的方法是向量空間模型（etorSpaceModelVSM，它是由.Slton于1988年SMT系統(tǒng)就是該模型的成功應用并且廣泛應用于文本信息處理領域。在向量空間模型中，將文檔空間看作是由一組正交特征矢量所形成的矢量空間，用一個向量來表示一個文本信息，使得文本成為特征空間中的一個點，在向量空間模型中文本集合成一個矩陣，也就是特征空間中點的集合。VSM文本()：是由訓練集、測試集組成的語料庫中的任意一篇文章，也特征項(featureterm)特征項權(quán)重(termweight)nD(,)，詞頻矩陣就是應用空間向量模型表示文本的一種形式。如表2.1表2 詞頻矩陣表示方 ………在詞頻矩陣中，wordi個j篇文本中出現(xiàn)的頻率。特征空間具有稀疏性、性等特點，這大大提高了文本分類的復雜程度，增加了分類時間，并且很大程度降低了文本分類的性能。在空間中，一部分特征對于分類來說是沒有任何作用的，甚至部分特征還可以誤導分類噪聲。所以在文本分類之前，應適當去除部分特征項，即降低文本特征空間的維數(shù)。特征選擇的任務就是從原然而，怎樣才能選擇出最適合的文本特征項呢？可分為兩步：首先應構(gòu)造出一個評估函數(shù)，對原始的特征集合中的每一個特征項進行計算，從而得到每一個特征項的評估函數(shù)值。然后，將所有特征項的評估函數(shù)值進行排列，選出適當?shù)木S數(shù)組成新的特征集合。總的來說，文本中所包含的信息越豐富，處理的語言層次就越高，其特征就越明顯，越有代表性。對于分類結(jié)果來說，準確率就會越高。TF-IDF(trmfrequency-invrsefrquency)詞頻-反轉(zhuǎn)文件頻率，是評估一個單詞在一個文件或一個語料庫中的重要程度。實際上，如果一個單詞在一個類的文本中出現(xiàn)的頻率越高，則說明該單詞能很好的代表這個類的文本特征，這樣的單詞就會被賦予較高的權(quán)重，并選擇該詞作為文本特征以區(qū)分其他類別。一個詞的重要性與該詞在文本中出現(xiàn)的頻率的增加而成正比，但與該詞在語料庫中出現(xiàn)的頻率的增加成反比。該算法認為文本頻數(shù)越小，它區(qū)別與其他文本的能力越強。TF表示一個單詞t在文本d中出現(xiàn)的頻率，即詞頻。IDF是逆向文件頻率，表示在所有文本中，包含單tIDFt能很好的區(qū)分類別。文本的分類算法是進行文本分類最的部分。目前，大部分的分類算法都是基于機器學習的方法。大致可分為三類：1.基于統(tǒng)計的方法，如K近鄰，樸素，支持向量機；2.3.KKK-NearestNeighborKNN)分類算法，是數(shù)據(jù)挖掘分類技術(shù)中最簡單的方法之一。具有算法簡單、功能穩(wěn)定、分類效率高等特點。被廣泛應用于文本分類領域。其訓練樣本就代表了類別的準確信息，而不管樣本是使用什么特征表示的。其基本思想是在給定新文檔后，計算新文檔特征向量和訓練文檔集中各個文檔的向量KK0KNN算法的思想是：如果一個樣本在特征空間中的k個最相鄰的樣本，其中的大多數(shù)都屬于某一個類別，則稱該樣本也屬于這個類別，且具有這個類別中樣本的特性。KNN近的一個或者幾個樣本的類別來決定待分類樣本所屬的類別。由于KNN來說，KNN方法較其他方法更為適合。樸素算樸素算法是利用概率統(tǒng)計學的知識來進行分類的，用于表示變量之間的依賴關系。該文檔屬于某個類別的概率等于文檔中每個詞屬于該類別的概率。而每個詞屬于該類別的概率又在一定程度上可以用這個詞在該類別訓練文檔中出現(xiàn)的次數(shù)（詞頻）來粗略估計。應用于大型數(shù)據(jù)庫中，方法簡單，效率高，速度快。定理將的先驗概率與后驗概率聯(lián)系起來。假定隨機向量x、的聯(lián)合pxp（x）p（)x為觀測向量，是未知參數(shù)向量，通過觀測向量獲得未知參數(shù)向量的統(tǒng)計，定理記做2.1SVMVapnik策面，使得正例和反例之間的邊緣被最大化。該算法以統(tǒng)計學習理論為基礎，更準確的說，支持向量機是結(jié)構(gòu)風險最小化的近似實現(xiàn)。這個原理基于這樣的事實：學習機器在測試數(shù)據(jù)上的誤差率（即泛化誤差率）VCSVMx(ix一概念是構(gòu)造支持向量機算法的關鍵。支持向量機是由算法從訓練數(shù)據(jù)中抽取的小的子集構(gòu)成。2.22.2決策樹（decisiontree)是一個預測模型，運用樹狀圖表示各決策的期望值，它反映的是對象屬性與對象值之間的一種映射關系。通過構(gòu)造樹來解決分類問題。首先利用訓練樣本集來構(gòu)造一棵決策樹，一旦樹建立起來，它就可以對未知的樣本進行分類。一個決策樹包含三種類型三個節(jié)點：決策節(jié)點---用矩形表示；機會節(jié)點---用圓形表示；終節(jié)點---用三角形表示。T0F212.3神經(jīng)網(wǎng)絡分兩種，一種是生物神經(jīng)網(wǎng)絡，一般指生物的大腦神經(jīng)元、細胞、觸點等組成的網(wǎng)絡，用于產(chǎn)生生物的意識，幫助生物進行思考和行動。另一種是人工神經(jīng)網(wǎng)絡（ArtificialNeuralNetworksANNs），也簡稱為神經(jīng)網(wǎng)絡（NNs）或稱作連接模型（ConnectionModel），它是一種模仿動物神經(jīng)網(wǎng)絡行為特征，進行分布式并行信息處理的算法數(shù)學模型。由眾多的神經(jīng)元可調(diào)的連接權(quán)值連接而成，具有大規(guī)模并行處理、分布式信息、良好的自組織習能力等特點。這種網(wǎng)絡依靠系統(tǒng)的復雜程度，通過調(diào)整內(nèi)部大量節(jié)點之間相互連接的關系，從而達到處理信息的目的。該網(wǎng)絡具備輸入層、隱含層與輸出層三個層次,每一個層次都包括很多神經(jīng)元,文本向量的維數(shù)決定輸入層的節(jié)點數(shù)目,輸出向量的維數(shù)決定輸出層的節(jié)點數(shù)目。輸入 隱含 輸出圖 BP神經(jīng)網(wǎng)絡拓撲結(jié)構(gòu)性能評價是文本分類中的重要環(huán)節(jié)。主要是率（recall）、準確（precision）、以及用于評價全局性能的宏平均（macro-average）（micro-average）10，2.2分類結(jié)果矩陣1ABRP率和準確率是對某一類別進行評價，反映了分類器的分類性能，這兩個指標是互補的，想要提高準確率，率就會將低，反之亦然。宏平均是每一類的分類性能指標的算術(shù)平均值，宏平均用MPMRmPmRiii宏平均是對類的平均，容易受小類影響，微平均是對文本的平均，容易受大類的影響。總索引、文本過濾、自動產(chǎn)生文檔元數(shù)據(jù)、單詞語義消歧、web資源的按層次分類組織SVMSVM算法有很堅實的理論基礎，SVM訓練的本質(zhì)是解決一個二次規(guī)劃問題（QuadrupleProgramming，指目標函數(shù)為二次函數(shù)，約束條件為線性約束的最優(yōu)化問題），得到的是全局最優(yōu)解，這使它有著其他統(tǒng)計學習技術(shù)難以比擬的優(yōu)越性。分類器的文本分類效果很好的分類器之一。同時使用核函數(shù)將原始的樣本空間向空間進行變換，能夠解決原始樣本線性不可分的問題。其缺點是核函數(shù)的選擇缺乏指SVM訓練速度極大地受到訓練集規(guī)模SVMChunking方法、OsunaSMO算法和交互SVM等。SVM全率方面都略優(yōu)于kNN及樸素方法。VCVC維是統(tǒng)計學習理論的一個概念，它描述了函數(shù)集或?qū)W習器的復雜性或者學習能力的一個重要指標。VC維越大，函數(shù)集合越大，其相應的學習能力就越強。VCVC維的直觀定義是：若存在一個樣本數(shù)量為h2^hhh+1的樣本集打散，則函數(shù)集的VCh。若對于任意的樣本數(shù)，總能找到VCR^23.1R^23.23.3 3.1R^23.2R^2R^2VC統(tǒng)計學習理論系統(tǒng)研究了各種類型的函數(shù)集，經(jīng)驗風險和實際風險之間的關系即推廣誤差邊界。對于兩類分類問題，經(jīng)驗風險和實際風險之間hVCn訓練誤差），另一部分稱作置信范圍，它和學VCVC置信范圍越大，導致真實風險與經(jīng)驗風險之間可能的差別越大。這就是為什么出現(xiàn)過學習現(xiàn)象的原因。機器學習過程不但要使經(jīng)驗風險最小，還要使VC維盡量縮小置信范圍才能取得較小的實際風險，即對未來樣本有較好的推廣性。h,n,當較小時，稱該樣本經(jīng)驗風險最小化原則是從處理大樣本數(shù)據(jù)問題出發(fā)的，這一原則的合理性可以通3.13.2n/h在結(jié)構(gòu)風險最小化中，先把函數(shù)集分解成函數(shù)子集序列：這樣，每一個子集的置信范圍都是相同的，在每一個子集中尋求最小經(jīng)驗風險，會隨著子集復雜程度的增加而減小。而要使期望風險達到最小，只需找到使最小經(jīng)驗風險和置信范圍之和達到最小值的子集即可。這個子集就是最優(yōu)函數(shù)。在結(jié)構(gòu)風險最小化原則下，一個分類器的設計過程包含兩個方面：一是函數(shù)模型的選擇；二是函數(shù)參數(shù)的選擇。1，如果屬于負類，則記為-1。若訓練集,這里或，樣本數(shù)為。支持向量機首先將向量映射到一個更的空間里，在其中建立最大間隔超平面，將數(shù)據(jù)分開；然后，在超平面兩邊再設立兩個互相平行的超平面；最后，分隔超平面，使兩個平行超平面的距離最大化。SVM如果數(shù)據(jù)是線性可分的，可找到兩個超平面，將空間中的訓練樣本點正確分為兩類，在它們之間沒有任何其他的樣本點，顯然，這樣的超平面有很多，假設這個超平面的法方向已經(jīng)給定，平行的向右上方或左下方移動這個超平面可以碰到某個訓練點的輸入，這樣就得到了兩個的超平面和，稱這兩個超平面為支持平面。而使這3.33.3三角形和圓形分別代表了訓練樣本集合中的兩類樣本，超平面能夠?qū)⑸鲜鰞深悩颖菊_地分隔開來，和分別平行于超平面,并且經(jīng)過了各類中離最近的樣本。這兩個超平面之間的距離為，因此需要最小化，因為這兩個超平面之間沒有任何樣本點，所以還需要滿足以下兩個條件中的一個：如果用一個線性函數(shù)可以將兩類樣本完全分開，則稱樣本為線性可分的。即存在最優(yōu)超平面，使得對于一個固定的超平面，參數(shù)()不是唯一確定的（相差一個常數(shù)因子），因此總能找到一對參數(shù)()，使得上述不等式中至少有一個以等式成立，為此，只需令到該超平面的最小距離為。SVM目標是發(fā)展一個計算上有效的過程，通過使用訓練樣本集，找到權(quán)值向量和偏置b，3.7其中，解中將只有一部分VapnikVCrSVMVC若訓練集是線性不可分的，或者事先不清楚它是否線性可分，希望找到一個最優(yōu)超平面，它使得整個訓練集合平均的分類誤差的概率達到最小。為此，引入一組新的非負變量給定訓練樣本，尋找權(quán)值向量和偏置b并且使得和最小化代價函數(shù)畢竟超平面的分類能力是有限的，為此需考慮分類曲面。Vapnik提出了核函數(shù)概念,就可以避免在特征空間中的運算。要解決非線性可分的情況，就是把樣本特征映射到特征空間中，如下圖： ，把映射到一個特征空間(Hilbert空間)中，然后在空間H中尋求最優(yōu)分類超平Lagrange

SVMm3.43.4支持向量機示意K(),或者是一個映射()，把樣本空間映射到一個甚至無窮維的特征空間中（Hilbert空間），使得在原來的樣本空間中非線性可分的問題轉(zhuǎn)化為在特征空間中的線性可分的問題。簡單地說，就是升維和線性化。選擇不同的核函數(shù)或者不同的映射以及相應的Hilbert將空間的內(nèi)積運算轉(zhuǎn)化為低的核函數(shù)計算，巧妙地解決了“維數(shù)”等問題，并且核函數(shù)的運用，無需知道非線性變換函數(shù)的形式和參數(shù)，大大減小了工作量。abaabab—到二的映為了用線性的學習器學個非線性的關系，需要選擇一個非線性特征集，其中，是從輸入空間到某個特征空間的映射。所以，建立非學習器分兩步，首先使H線性學習器的一個重要性質(zhì)是可以表達成對偶形式。假設函數(shù)可以表達為訓練點的線性組合，因此決策規(guī)則可以用測試點和訓練點的內(nèi)積來表示：式中，為輸入樣本，即測試樣本，為訓練樣本，即支持向量，為訓練樣本的數(shù)量。SVM4徑向基核函數(shù)：K(x,y)=exp(-|x-SVM算法是針對二值分類問題的，處理多分類問題時，常常被轉(zhuǎn)化成二值分類問該方法是通過構(gòu)造一系列二分類器來解決多分類問題的。對于k類分類問題構(gòu)造k個SVM分類器，其中，第i個SVM分類器是通過將屬于第i類的樣本視為正類，將ii圖3- 基于離散判別i圖3- 基于連續(xù)判別的為了解決離散的不可分區(qū)域問題，InoueAbe在給定的樣本中，任意選取兩個樣本，構(gòu)造一個二值的SVMKk(k-1)/2SVMijijijkk3-10SVMpnik1995年提出，基于統(tǒng)計學習理論的之上，以VC維理論和結(jié)構(gòu)風險最小化原則為基礎，根據(jù)有限的樣本信息在模型的復雜性（即對特定訓練的樣本的學習精度）和學習能力（即無錯誤地識別任意樣本的能力）之間尋求最佳折中，以期獲得最佳的推廣力。與傳統(tǒng)的機器學習方法相比，SVMVCSVM算法的理論基礎是非線性映射,SVM利用內(nèi)積核函數(shù)代替向空間的非線性映射，克服了特征空間中的維數(shù)問題。SVMSVM要空間小，算法魯棒性（Robust）強。盡管在文本分類領域中，SVM分類算法具備很多的優(yōu)勢，但是到目前為止，該算在對樣本數(shù)比較大的二次規(guī)劃問題進行求解時，支持向量機模型的訓練速度比較慢,難以保證較高的實時性要求。的支持向量,SVM分類器的準確度降低。支持向量機還存在構(gòu)造學習器及分類效率低的缺點。在訓練分類器時，SVM的著眼點在于兩類的交界部分，那些混雜在另一類中的點往往無助于提高分類器的性能,反而會大大增加訓練器的計算負擔，同時它們的存在還可能造成過學習，使泛化能力減弱。總SVM一個在特征空間中構(gòu)造線性分類超平面的問題。SVMSVM（乘子），所謂“最小優(yōu)化”的最大好處就是使得我們可以用解析的方法求解每一個最小規(guī)模的優(yōu)化問題，從而完全避免了迭代算法。當然，這樣一次“最小優(yōu)化”Lagrange乘子的最終結(jié)果，但會使目標函數(shù)向極小值邁進一步。我們再對其它Lagrange乘子做最小優(yōu)化，KKT條件時，目標函數(shù)達到最小，算法結(jié)束。兩個Lagrange我們在這里不妨設正在優(yōu)化的兩Lagrange乘子對應的樣本正是第一個和第二個Lagrangeα1α2，在其他乘子不改變的情況下，它們的約束條件應表達為正方形內(nèi)的一條4.1：α1α2表示α2求無條件極值，如果目標函數(shù)是嚴格上凹的，最小值就一定在這一極值點（極值點在區(qū)間內(nèi)）或在區(qū)間端點（極值點在區(qū)間外）。α2確定后，α1也就確定下來了。因此我們先找到α2優(yōu)化區(qū)間的上下限制，再在這個區(qū)間中α2求最小值。SMO算SMO算法的目的無非是找出f(x)，這個函數(shù)能讓我們把輸入的數(shù)據(jù)x進行分類，將一個凸二次規(guī)劃問題轉(zhuǎn)換成下列形式（KKT條件）其中是日乘子對于（1）的情況，表明是正常分類，在邊界內(nèi)部；對于（2）的情況，表明了是支持向量，在邊界上（3）KKT（2）（3）以下幾種情況出現(xiàn)將會出現(xiàn)不滿，但是則是不滿足的,而原本，但是則是不滿足的而原本，但是或者；則表明不滿足的，而原本應該是所以要找出不滿足KKT的這些并更新這些但這些又受到另外一個約束即通過另一個方法，即同時更新和，滿足以下等就能保證和0的約束。利用上面的式子消得到一個關于單變量的一個凸二次規(guī)劃問題，不考慮其約束。,可以得其解為其中表示舊值，然后考慮約束，可得a的解析解為：輸入是是一個數(shù)組，組中每一個值表示一個特征。輸出是A類還是類。（正類還是負類）SMO的優(yōu)即使很多日乘子在界上，SMO仍然能較好的處理SMOSVMSMOSVM的計SVM的計算可以表示為簡單的內(nèi)積，而非線性核的和。SMOSVM訓C0.61.0C很大，那么分類器將力圖通過分割超平面對所有的樣例都正確分類。小圓點標注的是支持向量。如果數(shù)據(jù)集非線性可分，支持向量會在超平面附近成團。歷時四個月的畢業(yè)設計即將結(jié)束，大學四年的學生生涯也將告一段落。首先，感謝老師對我的指導，感謝老師抽出寶貴時間給我們答疑解惑，老師認真負責的態(tài)度給我留下了深刻的印象。每次都很耐心并及時地解決我們課題上所遇到的問題，祝老師工作順利，桃李滿天下。同時，還要感謝同組其他五位同學對我的支持與鼓勵，在我遇到時，給我加最后，感謝大學四年給過我?guī)椭乃欣蠋煟抢蠋焸兊恼J真工作和無私奉獻才讓我學到了如此多的知識，并運用到的中。感謝老師們。[1],.支持向量機及其算法研究[J].與信息化[2].基于SVM的中文文本分類系統(tǒng)的研究與實現(xiàn)[D].吉林大學,[3],.文本信息自動分類系統(tǒng)ITC98(Ⅰ):ITC總體結(jié)構(gòu)與編碼子系統(tǒng)[J].中國學報,1999,4(4):74-77.[4].分類法的發(fā)展趨勢簡論[J].科學,1981(1):58-[5].中文文本分類相關算法的研究與實現(xiàn)[D].西學,.SVMD].哈爾濱工程大學,瓦普.統(tǒng)計學習理論的本質(zhì)[M].,,呂宏偉.基于SVMJ].電腦知識與技術(shù):學術(shù)交流,2006(3):162-162..基于SVM的文本分類系統(tǒng)中特征選擇與權(quán)重計算算法的研究[D].太原理工大學,2011..基于優(yōu)化理論的支持向量機學習算法研究[D].西安電子科技大學,王國勝.支持向量機的理論與算法研究[D].郵電大學,.統(tǒng)計學習理論與支持向量機方法[J].第二師范學院學報,26(2):14-,,.中文文本分類系統(tǒng)的設計與實現(xiàn)[C]//2006年全 集(三).2006:262-265.,汪東升,.基于VSM的中文文本分類系統(tǒng)的設計與實現(xiàn)[J].學報:自然科學版,2003,43(9):1288-1291.2.b=function[b,alphas]=smoSimple(data,class,2.b=3.[m,n]=4.4.alphas=6.while6.while(iter< alphasChanges= for ek=fxk- fxk=(alphas.*class)'*data*data(k,:)' ek=fxk- if(((ek*class(k)<toler)&&(alphas(k)<C))||((ek*class(k)>toler)&&(alphas(k)> j= fxj=(alphas.*class)'*data*data(j,:)'+ %f= ej=fxj- temp_k= if(class(k)~= if(class(k)~= L=max(0,alphas(j)- H=min(C,C+alphas(j)- L L=max(0,alphas(k)+alphas(j)- H=min(C,alphas(k)+ ifL== eta=2.0*data(k,:)*data(j,:)'-data(k,:)*-data(j,:)* ifeta>= alphas(j)=alphas(j)-class(j)*(ek-ej)/alphas(j)=clipalpha(alphas(j),H,if(abs(alphas(j)-temp_j)<alphas(k)=alphas(k)+class(k)*class(j)*(temp_j--b1=b-ek-class(k)*(alphas(k)-temp_k)*data(k,:)*(alphas(j)-temp_j)*data(k,:)*-b2=b-ej-class(k)*(alphas(k)-temp_k)*data(k,:)*(alphas(j)-temp_j)*data(j,:)*if(alphas(k)>0&&alphas(k)<b=elseif(alphas(j)>0&&alphas(j)<b=b=(b1+alphasChanges=alphasChanges+ iter=iter+ iter=iter+ iter= index= function index= index= index= functionres=clipalpha(a,H, ifa> a= ifa< a= res res= 2.1.2.4.4.load6.6.[r,c]=7.Test=8.8.Label= [b,alphas]=smoSimple(Test,Label,0.6,0.001, %% axis([-2 axis([-212-8 fork= hold ifData(k,3)== % for for ifalphas(k)~= hold QX= QX= y=(-W(1).*Data(:,1:1)-b) [m,n]=1.function[b,res_alphas]=rbf_smoP(data,class,C, [m,n]= iter= entireSet= oS=init(data, oS=init(data,class,C,toler,m, while(((iter<maxIter)&&(alphaPairsChanged>0))||(entireSet== ifentireSet== ifentireSet== fork= [ret,oS]=innerL(k, alphaPairsChanged=alphaPairsChanged+ iter=iter+ nonBoundIs= fork= nonBoundIs=[nonBoundIs if((oS.alphas(k)<C) nonBoundIs=[nonBoundIs fork= fork= index= [ret,oS]=innerL(index, alphaPairsChanged=alphaPairsChanged+ iter=iter+ entireSet= if entireSet= elseifalphaPairsChanged== entireSet= b= res_alphas= functionK=kernelTrans(X,A, [m,n]= forj= forj= deltaRow=X(j,:)- K(j)=deltaRow* K K=exp(K./(- alphas= function alphas= b= b= oS.data= oS.C= oS.C= oS.toler= oS.m= oS.b= oS.b= oS.eCache= oS.K= oS.K(:,j)= for oS.K(:,j)= function[ret,oS]=innerL(k, Ei=calcEk(oS,if(((oS.class(k)*Ei<oS.toler)&&(oS.alphas(k)<oS.C))||((oS.class(k)*Ei>oS.toler)&&k)> temp_k= [j,Ej]= temp_k= temp_j= L=max(0,oS.alphas(j) L=max(0,oS.alphas(j)- H=min(oS.C,oS.C+oS.alphas(j)- H=min(oS.C,oS.alphas(j)+ L= H=min(oS.C,oS.alphas(j)+ ifL== ret= eta eta=2.0*oS.K(k,j)-oS.K(k,k)- i