設(shè)計(jì)基于SVM分類器

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

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