基于支持向量機(jī)的文本分類算法的研究與實(shí)現(xiàn)

1、學(xué)號(hào)：2009030114哈爾濱師范大學(xué)學(xué)士學(xué)位論文題目基于支持向量機(jī)的文本分類算法研究與實(shí)現(xiàn)學(xué)生李慧穎指導(dǎo)教師李紅宇副教授年級(jí)2009級(jí)專業(yè)計(jì)算機(jī)科學(xué)與技術(shù)系別計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)科學(xué)與信息工程哈爾濱師范大學(xué)學(xué)士學(xué)位論文開題報(bào)告論文題目：基于支持向量機(jī)的文本分類算法研究與實(shí)現(xiàn)學(xué)生姓名：李慧穎指導(dǎo)教師：李紅宇級(jí)：2009級(jí)業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)2013年3月1日課題來源:指導(dǎo)教師指導(dǎo)選題課題研究的目的和意義：隨著計(jì)算機(jī)技術(shù)的飛速發(fā)展以及Internet的普及與應(yīng)用，互聯(lián)網(wǎng)上的電子文檔信息急劇增加。如何從大量的信息中快速、準(zhǔn)確地檢索到所需的信息資料，是人們普遍關(guān)心的問題，也是計(jì)算機(jī)工作者急需

2、解決的問題。面對(duì)如此復(fù)雜的問題，分類技術(shù)在信息檢索、信息過濾、數(shù)據(jù)挖掘等方面起著至關(guān)重要的作用。而網(wǎng)上的大部分信息以文本的形式存在，于是文本自動(dòng)分類技術(shù)就成為網(wǎng)上信息檢索和信息過濾的關(guān)鍵。另外，文本分類可以應(yīng)用到垃圾郵件的判定(spamornotspam),類別spam,not-spam；新聞出版按照欄目分類，類別政治，體育，軍事.;詞性標(biāo)注，類別名詞，動(dòng)詞，形容詞)；詞義排歧，類別詞義1,詞義2.)，文本檢索，文本過濾以及主題發(fā)現(xiàn)與跟蹤等。而從Springer全文電子期刊與IEL(IEE,IEEE)數(shù)據(jù)庫(kù)中，可以看到最近的期刊與國(guó)際會(huì)議論文，有大量的關(guān)于文本分類的文章，說明隨著大量的網(wǎng)上的電

3、子信息，文本分類仍是人們研究的熱點(diǎn)。面對(duì)網(wǎng)上的海量信息，傳統(tǒng)的做法是對(duì)網(wǎng)上信息進(jìn)行人工分類，并加以組織和整理，為人們提供一種相對(duì)有效的信息獲取手段。但是，這種傳統(tǒng)的人工分類的做法存在著許多弊端：一是耗費(fèi)大量的人力，物力和精力；二是存在分類結(jié)果一致性不高的問題。這就要求我們探索計(jì)算機(jī)自動(dòng)進(jìn)行文本分類的有效方法，使得分類的正確率提高。只有這樣才能保證檢索的查全率和準(zhǔn)確率都得到提高。文本自動(dòng)分類是人工智能技術(shù)和信息檢索技術(shù)相結(jié)合的研究領(lǐng)域，是進(jìn)行基于內(nèi)容的自動(dòng)信息管理的核心技術(shù)。文本分類是指根據(jù)一些已經(jīng)分配好類標(biāo)簽(這些類標(biāo)簽預(yù)先定義好)的訓(xùn)練文檔集合，來對(duì)新文檔分配類標(biāo)簽，其目的就是對(duì)文本集進(jìn)行合

4、理處理和組織，使得這些文本能夠按照類別區(qū)分開來。作為知識(shí)的組織工具，它為信息檢索提供了更高效的搜索策略和更準(zhǔn)確的查詢結(jié)果，其中，高效性在于用戶可以首先確定查詢的可能類別，以減小需進(jìn)一步匹配的文本數(shù)量：有效性在于相似的文本很可能與相同的查詢相關(guān)，這樣使得檢索的查全率和準(zhǔn)確率都得到了提高。國(guó)內(nèi)外同類課題研究現(xiàn)狀及發(fā)展趨勢(shì)：1.國(guó)外文本自動(dòng)分類主要經(jīng)歷了四個(gè)發(fā)展階段：第一階段(19581964):研究文本自動(dòng)分類的可能性；第二階段(19651974):進(jìn)入文本自動(dòng)分類的實(shí)驗(yàn)性階段；第三階段(19751998):文本自動(dòng)分類的實(shí)用性階段；第四階段(1990至今)：因特網(wǎng)文本自動(dòng)分類研究階段。在20世紀(jì)

5、80年代術(shù)以前，基于知識(shí)工程的方法一直在文本分類方法中占主導(dǎo)地位。這種方法是由專業(yè)人員手工編寫分類規(guī)則來表達(dá)領(lǐng)域?qū)＜宜鶕碛械闹R(shí)，將文檔分到某個(gè)給定的類別體系中。這種方法需要有領(lǐng)域?qū)＜?，還需要知識(shí)工程師手工編制大量的推理規(guī)則。其最典型的應(yīng)用是卡內(nèi)基集團(tuán)為路透社開發(fā)的Construe系統(tǒng)。90年代以來，隨著模式識(shí)別、機(jī)器學(xué)習(xí)、統(tǒng)計(jì)學(xué)習(xí)、數(shù)據(jù)挖掘等理論研究的發(fā)展，新型機(jī)器學(xué)習(xí)方法的不斷涌現(xiàn)，基于機(jī)器學(xué)習(xí)的分類技術(shù)開始取代基于知識(shí)工程的方法，成為文本分類的主流技術(shù)。2國(guó)內(nèi)文本自動(dòng)分類研究起步較晚，始于20世紀(jì)80年代初期。1981年侯漢清對(duì)計(jì)算機(jī)在文獻(xiàn)分類工作中的應(yīng)用作了探討，并介紹了國(guó)外在計(jì)算機(jī)管

6、理分類表、計(jì)算機(jī)分類檢索、計(jì)算機(jī)自動(dòng)分類、計(jì)算機(jī)編制分類表等方面的概況。此后，有越來越多的人借鑒國(guó)外的一些研究成果，結(jié)合中文的特點(diǎn)進(jìn)行中文文本自動(dòng)分類的研究。中科院計(jì)算所的李曉黎、史忠植等人應(yīng)用概念推理網(wǎng)進(jìn)行文本分類。復(fù)旦大學(xué)的周水庚等人用了N-gram方法對(duì)中文文本進(jìn)行分類嘗試，從文檔中提取N-gram屬性，然后用ON方法判別文本類別，擺脫了對(duì)詞典和切詞處理的依賴，實(shí)現(xiàn)文本分類的領(lǐng)域無關(guān)性和時(shí)間無關(guān)性。刁力力、石純一等用Boosting來組合決策樹(Stllnlps)的方法進(jìn)行文本分類。卜東波從信息粒度的角度來剖析聚類和分類技術(shù)，試圖使用信息粒度原理的框架來統(tǒng)一聚類和分類。龐劍峰等應(yīng)用向量空

7、問模型進(jìn)行了中文文本分類實(shí)驗(yàn)，并同時(shí)對(duì)文本分類所涉及的關(guān)鍵性技術(shù)，例如特征提取，不同機(jī)器學(xué)習(xí)方法等進(jìn)行了研究和探討，給出了評(píng)估方法和實(shí)驗(yàn)結(jié)果。之后他又驗(yàn)證了在文本分類系統(tǒng)中應(yīng)用反饋方法的可行性，給出了結(jié)合反饋方法的文本分類算法。課題研究的主要內(nèi)容和方法，研究過程中的主要問題和解決辦法：本文在研究文本分類和支持向量機(jī)理論的基礎(chǔ)上，針對(duì)支持向量機(jī)在樣本數(shù)目較多時(shí)其訓(xùn)練速度較慢的問題，針對(duì)支持向量機(jī)在樣本維數(shù)較高時(shí)其訓(xùn)練和分類速度較慢的問題，用哈爾小波變換對(duì)訓(xùn)練樣本和分類樣本向量進(jìn)行降維處理，降低支持向量機(jī)在模型訓(xùn)練和分類測(cè)試階段的運(yùn)算量，有效提高訓(xùn)練和分類的時(shí)間效率。本文在分析實(shí)驗(yàn)數(shù)據(jù)的基礎(chǔ)上對(duì)上

8、述方法的應(yīng)用效果做了總結(jié)。小波變換是對(duì)支持向量機(jī)用向量表示的樣本進(jìn)行加工處理。從應(yīng)用的出發(fā)點(diǎn)來看，其目的是為了提高訓(xùn)練和分類的時(shí)間效率，小波變換使用的策略則是降低向量的維數(shù)：從應(yīng)用的效果來看，小波變換的效果較好，且都在一定程度上降低了訓(xùn)練和分類時(shí)間，能夠更好的保證分類的準(zhǔn)確率。課題研究起止時(shí)間和進(jìn)度安排：1.起止時(shí)間：2013年1月2013年5月2進(jìn)度安排：12-292013-2-28確定論文題目，查找資料，撰寫開題報(bào)告根據(jù)課題研究的內(nèi)容，收集資料。3-22013-3-20深入探討該算法中的幾個(gè)經(jīng)典問題。2013-3-212013-4-10整理研究?jī)?nèi)容，并作進(jìn)一步的修改。2013-4-1120

9、13-5-4歸納總結(jié)，形成一份完整的課題論文。2013-5-8交論文，答辯。學(xué)士學(xué)位論文題目基于支持向量機(jī)的文本分類算法研究與實(shí)現(xiàn)學(xué)生李慧穎指導(dǎo)教師李紅宇副教授年級(jí)2009級(jí)專業(yè)計(jì)算機(jī)科學(xué)與技術(shù)系別計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)科學(xué)與信息工程哈爾濱師范大學(xué)2013年5月摘要：隨著計(jì)算機(jī)與通訊技術(shù)的飛速發(fā)展，互聯(lián)網(wǎng)上的電子文檔信息急劇增加。這就使得文本的自動(dòng)分類越來越受人們的重視，而支持向量機(jī)和文本分類問題有著良好的結(jié)合點(diǎn)從而使得基于支持向量機(jī)的文本分類成為這個(gè)領(lǐng)域的研究熱點(diǎn)。支持向量機(jī)是一種基于結(jié)構(gòu)風(fēng)險(xiǎn)最小化準(zhǔn)則的分類學(xué)習(xí)機(jī)模型，它的應(yīng)用十分廣泛。雖然支持向量機(jī)算法的性能在許多實(shí)際問題的應(yīng)用中得到

10、了驗(yàn)證，但是還存在著一些需要改進(jìn)的地方，如：訓(xùn)練算法速度慢測(cè)試階段運(yùn)算量大等。關(guān)鍵詞：支持向量機(jī)；文本分類；學(xué)習(xí)機(jī)模型目錄TOC o 1-5 h z HYPERLINK l bookmark10 第一章引言1 HYPERLINK l bookmark12 研究背景及意義1 HYPERLINK l bookmark14 國(guó)內(nèi)外研究現(xiàn)狀1 HYPERLINK l bookmark16 文本分類研究現(xiàn)狀1 HYPERLINK l bookmark18 SVM研究現(xiàn)狀2 HYPERLINK l bookmark20 文本內(nèi)容研究3 HYPERLINK l bookmark22 第二章文本分類4 HYP

11、ERLINK l bookmark24 文本自動(dòng)分類概述4 HYPERLINK l bookmark26 文本分類所涉及的技術(shù)領(lǐng)域4文本分類與自然語(yǔ)言處理4 HYPERLINK l bookmark28 文本分類與文本挖掘5 HYPERLINK l bookmark30 文本分類與機(jī)器學(xué)習(xí)5 HYPERLINK l bookmark32 文本分類與模式識(shí)別5 HYPERLINK l bookmark34 文本分類的關(guān)鍵技術(shù)6文本表示6 HYPERLINK l bookmark36 特征選擇7 HYPERLINK l bookmark38 權(quán)重計(jì)算9 HYPERLINK l bookmark40

12、 常用的文本分類算法9 HYPERLINK l bookmark42 文本分類的應(yīng)用11 HYPERLINK l bookmark44 第三章支持向量機(jī)13 HYPERLINK l bookmark46 支持向量機(jī)簡(jiǎn)介13 HYPERLINK l bookmark48 支持向量分類機(jī)14 HYPERLINK l bookmark50 線性可分問題14 HYPERLINK l bookmark52 近似線性可分問題15線性不可分問題15 HYPERLINK l bookmark56 支持向量機(jī)的應(yīng)用步驟16 HYPERLINK l bookmark58 基于支持向量機(jī)文本分類方法的優(yōu)勢(shì)17 HY

13、PERLINK l bookmark60 基于支持向量機(jī)文本分類方法中存在的問題17 HYPERLINK l bookmark62 第四章小波變換在支持向量機(jī)分類中的應(yīng)用19 HYPERLINK l bookmark64 問題的提出19 HYPERLINK l bookmark66 降維相關(guān)的研究工作19 HYPERLINK l bookmark68 小波分析20 HYPERLINK l bookmark70 離散小波變換20 HYPERLINK l bookmark72 小波的定義21 HYPERLINK l bookmark74 一維哈爾小波變換21 HYPERLINK l bookmar

14、k76 哈爾基函數(shù)22哈爾小波函數(shù)22 HYPERLINK l bookmark78 函數(shù)的規(guī)范化23 HYPERLINK l bookmark80 哈爾基的結(jié)構(gòu)24 HYPERLINK l bookmark82 哈爾小波變換的應(yīng)用24 HYPERLINK l bookmark84 哈爾小波變換的過程24 HYPERLINK l bookmark86 哈爾小波變換的應(yīng)用24 HYPERLINK l bookmark88 哈爾小波變換在本文中的應(yīng)用26小波變換的應(yīng)用27 HYPERLINK l bookmark90 實(shí)驗(yàn)及結(jié)果分析28實(shí)驗(yàn)平臺(tái)及環(huán)境28 HYPERLINK l bookmark9

15、2 實(shí)驗(yàn)步驟28 HYPERLINK l bookmark94 實(shí)驗(yàn)?zāi)康?9 HYPERLINK l bookmark96 結(jié)果分析29 HYPERLINK l bookmark98 第五章總結(jié)33 HYPERLINK l bookmark100 文本總結(jié)33 HYPERLINK l bookmark102 工作展望33 HYPERLINK l bookmark104 參考文獻(xiàn)：34Absatrct:.35 第一章引言研究背景及意義所謂的文本自動(dòng)分類，最初是應(yīng)信息檢索(InformationRetrieval,IR)系統(tǒng)的要求出現(xiàn)的。信息檢索系統(tǒng)要操縱許多的數(shù)據(jù)，而文本信息庫(kù)可能是相當(dāng)龐大的，

16、并且，用來表示文本內(nèi)容的詞匯數(shù)量又是成千上萬的。因此，在這種情況下，如果能夠提供文本集良好的組織與結(jié)構(gòu)，就能一定程度上簡(jiǎn)化文本的操縱。文本自動(dòng)分類系統(tǒng)的目的就是對(duì)文本集進(jìn)行有序組織，把相似的、文本組織在一起。它作為知識(shí)的組織工具，為信息檢索提供了更高效的搜索策略和更準(zhǔn)確的查詢結(jié)果。其中，高效性來自于用戶可以首先確定查詢的可能類別，以減小需進(jìn)一步匹配的文本數(shù)量。有效性在于相似的文本很可能與相同的查詢相關(guān)。這樣，檢索的查全率和準(zhǔn)確率都得到了提高。隨著全球計(jì)算機(jī)與通訊技術(shù)的飛速發(fā)展、互聯(lián)網(wǎng)絡(luò)的普及與應(yīng)用，文本自動(dòng)分類對(duì)于信息處理的意義變得更加重要。在互聯(lián)網(wǎng)中，電子文檔信息每天都在急劇的增加，通過網(wǎng)絡(luò)

17、，人們可以很方便地共享巨大的信息資源。但網(wǎng)絡(luò)信息的快速膨脹使得給人們進(jìn)行信息查找的信息資源無法很有效的加以利用。面對(duì)網(wǎng)上的海量信息，傳統(tǒng)的做法是對(duì)網(wǎng)上信息進(jìn)行人工分類，并加以組織和整理，為人們提供一種相對(duì)有效的信息獲取手段。但是，這種人工分類的做法存在著許多弊端：一是耗費(fèi)大量的時(shí)間和精力。二是存在分類結(jié)果不精準(zhǔn)。即使分類人的語(yǔ)言素質(zhì)較高，但其分類結(jié)果仍然不盡相同。網(wǎng)絡(luò)信息的激增不僅增加了對(duì)于快速、自動(dòng)文本分類的迫切需求，而且又為基于機(jī)器學(xué)習(xí)的文本分類方法準(zhǔn)備了充分的準(zhǔn)備。支持向量機(jī)是由Vapnik領(lǐng)導(dǎo)的AT&TBell實(shí)驗(yàn)室研究小組在1995年提出的一種新的非常有潛力的分類技術(shù)，SVM是一種基

18、于統(tǒng)計(jì)學(xué)習(xí)理論的模式識(shí)別方法，主要應(yīng)用于模式識(shí)別領(lǐng)域。由于當(dāng)時(shí)這些研究尚不十分完善，在解決模式識(shí)別問題中往往趨于保守，且數(shù)學(xué)上比較艱澀，這些研究一直沒有得到充分的重視。直到90年代，統(tǒng)計(jì)學(xué)習(xí)理論(StatisticalLearningTheory，SLT)的實(shí)現(xiàn)和由于神經(jīng)網(wǎng)絡(luò)等較新興的機(jī)器學(xué)習(xí)方法的研究遇到一些重要的困難，比如如何確定網(wǎng)絡(luò)結(jié)構(gòu)的問題、過學(xué)習(xí)與欠學(xué)習(xí)問題、局部極小點(diǎn)問題等，使得SVM迅速發(fā)展和完善，在解決小樣本、非線性及高維模式識(shí)別問題中表現(xiàn)出許多特有的優(yōu)勢(shì)，并能夠推廣應(yīng)用到函數(shù)擬合等其他機(jī)器學(xué)習(xí)問題中。從此迅速的發(fā)展起來，現(xiàn)在已經(jīng)在許多領(lǐng)域(生物信息學(xué)，文本和手寫識(shí)別等)都取得

19、了成功的應(yīng)用。SVM的主要思想可以概括為兩點(diǎn)：它是針對(duì)線性可分情況進(jìn)行分析，對(duì)于線性不可分的情況，通過使用非線性映射算法將低維輸入空間線性不可分的樣本轉(zhuǎn)化為高維特征空間使其線性可分，從而使得高維特征空間采用線性算法對(duì)樣本的非線性特征進(jìn)行線性分析成為可能。它基于結(jié)構(gòu)風(fēng)險(xiǎn)最小化理論之上在特征空間中建構(gòu)最優(yōu)分割超平面，使得學(xué)習(xí)器得到全局最優(yōu)化，并且在整個(gè)樣本空間的期望風(fēng)險(xiǎn)以某個(gè)概率滿足一定上界。對(duì)學(xué)習(xí)算法的研究和改進(jìn)是目前SVM研究的主要內(nèi)容，在過去的十多年里，出現(xiàn)了很多SVM算法的改進(jìn)算法，從算法實(shí)現(xiàn)中優(yōu)化理論的改進(jìn)、核函數(shù)的構(gòu)造到算法參數(shù)的選擇等國(guó)內(nèi)外研究現(xiàn)狀文本分類研究現(xiàn)狀文本分類一般包括了文

20、本的表達(dá)、分類器的選擇與訓(xùn)練、分類結(jié)果的評(píng)價(jià)與反饋等過程，其中文本的表達(dá)又可細(xì)分為文本預(yù)處理、索引和統(tǒng)計(jì)、特征抽取等步驟。美國(guó)IBM公司的H.P.Luhn在20世紀(jì)50年代末對(duì)文本分類進(jìn)行研究，他提出了詞頻統(tǒng)計(jì)思想，后來被應(yīng)用在文本分類領(lǐng)域。60年代初，Maron在利用概率模型進(jìn)行文本分類方面做出了開創(chuàng)性的研究工作。Salton等人在70年代初提出了向量空間模型，由于該模型在良好的統(tǒng)計(jì)學(xué)方法基礎(chǔ)上簡(jiǎn)明地實(shí)現(xiàn)了對(duì)文本特性的抽象描述，從而成為文本分類處理的一種經(jīng)典模型。其后許多學(xué)者在這一領(lǐng)域進(jìn)行了卓有成效的研究。國(guó)外文本自動(dòng)分類主要經(jīng)歷了四個(gè)發(fā)展階段：第一階段(1958-1964)：研究文本自動(dòng)分

21、類的可能性；第二階段(1965-1974)：進(jìn)入文本自動(dòng)分類的實(shí)驗(yàn)性階段；第三階段(1975-1998)：文本自動(dòng)分類的實(shí)用性階段；第四階段(1990-至今)：因特網(wǎng)文本自動(dòng)分類研究階段。國(guó)內(nèi)文本自動(dòng)分類研究起步較晚，始于20世紀(jì)80年代初期。1981年侯漢清對(duì)計(jì)算機(jī)在文獻(xiàn)分類工作中的應(yīng)用作了探討，并介紹了國(guó)外在計(jì)算機(jī)管理分類表、計(jì)算機(jī)分類檢索、計(jì)算機(jī)自動(dòng)分類、計(jì)算機(jī)編制分類表等方面的概況。此后，有越來越多的人借鑒國(guó)外的一些研究成果，結(jié)合中文的特點(diǎn)進(jìn)行中文文本自動(dòng)分類的研究。中科院計(jì)算所的李曉黎、史忠植等人應(yīng)用概念推理網(wǎng)進(jìn)行文本分類。復(fù)旦大學(xué)的周水庚等人用了N-gram方法對(duì)中文文本進(jìn)行分類嘗

22、試，從文檔中提取N-gram屬性，然后用ON方法判別文本類別，擺脫了對(duì)詞典和切詞處理的依賴，實(shí)現(xiàn)文本分類的領(lǐng)域無關(guān)性和時(shí)間無關(guān)性。刁力力、石純一等用Boosting來組合決策樹(Stumps)的方法進(jìn)行文本分類。卜東波從信息粒度的角度來剖析聚類和分類技術(shù)，試圖使用信息粒度原理的框架來統(tǒng)一聚類和分類。龐劍峰等應(yīng)用向量空問模型進(jìn)行了中文文本分類實(shí)驗(yàn)，并同時(shí)對(duì)文本分類所涉及的關(guān)鍵性技術(shù)，例如特征提取、不同機(jī)器學(xué)習(xí)方法等進(jìn)行了研究和探討，給出了評(píng)估方法和實(shí)驗(yàn)結(jié)果。之后他又驗(yàn)證了在文本分類系統(tǒng)中應(yīng)用反饋方法的可行性，給出了結(jié)合反饋方法的文本分類算法。SVM研究現(xiàn)狀SVM由于分類效果比較好成為近幾年人們研

23、究的熱點(diǎn)SVM是建立在SLT的VC維理論和結(jié)構(gòu)風(fēng)險(xiǎn)最小化原理基礎(chǔ)上，根據(jù)有限樣本信息在模型復(fù)雜性(對(duì)特定樣本的學(xué)習(xí)精度)和學(xué)習(xí)能力(無錯(cuò)誤地識(shí)別樣本的能力)之間尋求一種折中，以期達(dá)到最佳的推廣性能。1995年，Vapnik在“TheNatureofStatisticalLearningTheory，一書中提出支持向量機(jī)的概念，并在“SupportVectorNetworks，一文中進(jìn)行了詳細(xì)的介紹。從那以后，關(guān)于支持向量機(jī)方面的文章如雨后春筍，逐漸成為國(guó)際上機(jī)器學(xué)習(xí)領(lǐng)域的研究熱點(diǎn)，吸引了國(guó)內(nèi)外眾多知名的專家Daniel和Gabriele提出了基于小波的核函數(shù)構(gòu)造方法：Atari和Wu設(shè)計(jì)了一種

24、算法，他們通過對(duì)核函數(shù)的黎曼幾何分析，提出利用實(shí)驗(yàn)數(shù)據(jù)逐步修正己有的核函數(shù)，使之能更好地與實(shí)際問題相吻合；Cauwenberghs和Poggio研究了基于SVM的增量和減量學(xué)習(xí)問題；Diehl和Cauwenberghs提出了一個(gè)精確增量學(xué)習(xí)和自適應(yīng)SVM分類器的框架;Opper和Urban-czik對(duì)SVM學(xué)習(xí)帶噪聲的多項(xiàng)式規(guī)則進(jìn)行了研究，在核函數(shù)階數(shù)足夠高或者為超越函數(shù)時(shí)，漸近線和學(xué)習(xí)曲線由目標(biāo)規(guī)則決定而不是核函數(shù)，在這種情況下研究了訓(xùn)練誤差核推廣誤差的收斂性；Bordes等提出一種在線SVM算法LASVM，通過對(duì)樣本的主動(dòng)選擇提高了學(xué)習(xí)速度；Serifini等研究了基于梯度方法的SVM分解

25、算法中起作用集的選擇問題；此外，還有很多學(xué)者對(duì)SVM的算法進(jìn)行了研究，這里就不一一列舉了。Joachims和Dumais例等人于1998年開創(chuàng)了SVM在文本分類中應(yīng)用的先河。他們各自在不同語(yǔ)料庫(kù)中做了大量試驗(yàn)，結(jié)果表明SVM在文本分類的應(yīng)用中特別有效，并有很好的泛化性，克服了高維表示中的困難。此后，很多學(xué)者開始了這方面的研究，并取得了很多研究成果。目前，SVM己被越來越多地應(yīng)用到模式識(shí)別領(lǐng)域，如手寫體文字識(shí)別、人臉識(shí)別等在圖像壓縮和數(shù)據(jù)分類的應(yīng)用中，SVM也顯示出了較好的性能。而SVM在文本分類中的應(yīng)用，主要關(guān)注以下幾個(gè)方面：(1)提高支持向量機(jī)的計(jì)算速度，以便處理更大規(guī)模的文本分類問題；利用

26、最優(yōu)化技術(shù)改進(jìn)或改造SVM形式，簡(jiǎn)化計(jì)算過程；(3)利用結(jié)構(gòu)風(fēng)險(xiǎn)最小化原則、核思想和J下則化技術(shù)等改造傳統(tǒng)的線性算法，構(gòu)造出相應(yīng)的核形式，使之更適合文本分類等。但從現(xiàn)在研究來看，用于文本分類的核函數(shù)一經(jīng)確定(如多項(xiàng)式核和高斯核等)，其參數(shù)的選擇多是憑借經(jīng)驗(yàn)，或是在試驗(yàn)中一步一步的修正。通常這個(gè)選擇必須適用于具體的數(shù)據(jù)，在缺乏可靠的條件時(shí)，在應(yīng)用中需要使用驗(yàn)證集或者是交叉驗(yàn)證來設(shè)置這些參數(shù)。文本內(nèi)容研究本文主要研究基于支持向量機(jī)的文本分類算法，文中主要介紹了文本分類、支持向量機(jī)、聚類方法在支持向量機(jī)分類中的應(yīng)用、小波變換在支持向量機(jī)分類中的應(yīng)用等，結(jié)構(gòu)安排如下：第一章，引言。主要介紹了課題的研究

27、背景、研究意義、國(guó)內(nèi)外研究現(xiàn)狀，概述本論文的主要工作以及結(jié)構(gòu)安排。第二章，文本分類相關(guān)知識(shí)。由于基于支持向量機(jī)的文本分類是眾多文本分類方法中的一種，它以文本分類為基礎(chǔ)。因此本文對(duì)文本分類的相關(guān)知識(shí)做了詳細(xì)的介紹，如文本表示、特征選擇、權(quán)重計(jì)算、文本分類算法等文本分類的關(guān)鍵技術(shù)。第三章，支持向量機(jī)相關(guān)知識(shí)。支持向量機(jī)的應(yīng)用領(lǐng)域十分廣泛，文本分類只是其中一種比較典型的應(yīng)用。本文研究的是基于支持向量機(jī)的文本分類算法，所以也有必要介紹支持向量機(jī)的相關(guān)知識(shí)。本章中主要介紹了支持向量機(jī)的基本原理、支持向量分類機(jī)、支持向量機(jī)的核函數(shù)、支持向量機(jī)的應(yīng)用步驟以及支持向量機(jī)分類方法的優(yōu)缺點(diǎn)。第四章，小波變換在支持

28、向量機(jī)分類中的應(yīng)用。本章主要研究的是小波變換對(duì)支持向量機(jī)的輸入向量進(jìn)行降維，從而提高支持向量機(jī)的訓(xùn)練和分類的效率，在本章中首先對(duì)小波變換的基礎(chǔ)知識(shí)做了詳盡的介紹，其中包括：離散小波變換的基本原理、一維哈爾小波、哈爾小波變換的應(yīng)用過程等。接著本文著重分析了用哈爾小波變換在支持向量機(jī)分類中應(yīng)用，并在理論分析的基礎(chǔ)上構(gòu)造了實(shí)驗(yàn)系統(tǒng)。最后在分析實(shí)驗(yàn)數(shù)據(jù)的基礎(chǔ)上討論了小波變換應(yīng)用的效果。第五章，總結(jié)和展望。本章總結(jié)了通過實(shí)驗(yàn)得出的結(jié)論，并敘述了本文中所用方法的不足，對(duì)將來的工作進(jìn)行了展望第二章文本分類文本自動(dòng)分類概述文本自動(dòng)分類是對(duì)大量的非結(jié)構(gòu)化的文字信息（文本文檔、網(wǎng)頁(yè)等）按照給定的分類體系，根據(jù)文字

29、信息內(nèi)容分到指定的類別中去，是一種有指導(dǎo)的學(xué)習(xí)過程。文本自動(dòng)分類的過程總體上可劃分為訓(xùn)練和分類兩部分。訓(xùn)練的目的是通過樣本和類別之間的聯(lián)系構(gòu)造分類模型，使其用于分類。分類則是依據(jù)訓(xùn)練結(jié)果對(duì)未知樣本進(jìn)行分類，給出類別標(biāo)識(shí)的過程。具體流程如圖2.1所示，其中訓(xùn)練過程用實(shí)線表示，分類過程用虛線表示。圖2.1文本自動(dòng)分類過程文本分類所涉及的技術(shù)領(lǐng)域文本分類技術(shù)涉及到多個(gè)領(lǐng)域的知識(shí)，包括語(yǔ)言學(xué)中的自然語(yǔ)言處理、數(shù)據(jù)挖掘中的文本挖掘、計(jì)算機(jī)領(lǐng)域的機(jī)器學(xué)習(xí)和模式識(shí)別等。文本分類與自然語(yǔ)言處理自然語(yǔ)言處理是文本分類的基礎(chǔ)，文本分類主要借助了其文本處理相關(guān)技術(shù)，如分詞技術(shù)、N元模型等。中文自然信息處理發(fā)展至今可

30、以分為三個(gè)階段，字處理階段、詞處理階段和句處理階段。字處理研究?jī)?nèi)容包括漢字編碼、漢字識(shí)別、漢字輸入法和字處理軟件等。到目前為止，這些技術(shù)己經(jīng)比較成熟，字處理繼續(xù)研究的領(lǐng)域己經(jīng)不多，大多數(shù)科學(xué)家將研究方向移至詞處理和句處理的研究當(dāng)中。目前，詞處理階段上最成功、最典型、也最引人矚目的應(yīng)用領(lǐng)域是Internet上的搜索引擎，如Google、Yahoo和百度等，對(duì)一般的檢索都能返回不錯(cuò)的結(jié)果。其它正在研究的方向還包括文本過濾、個(gè)性化服務(wù)系統(tǒng)、語(yǔ)音識(shí)別等。在詞處理上的其他應(yīng)用還有文本自動(dòng)校對(duì)、漢字簡(jiǎn)繁體自動(dòng)轉(zhuǎn)換、自動(dòng)分詞等領(lǐng)域引。句處理上的應(yīng)用主要有兩個(gè)方面：一是機(jī)器翻譯，目前機(jī)器翻譯的質(zhì)量仍舊不能令人

31、滿意。二是漢語(yǔ)語(yǔ)法分析，大家在使用微軟字處理軟件的時(shí)候都會(huì)發(fā)現(xiàn)它能夠提示一些英文語(yǔ)法錯(cuò)誤，但對(duì)中文語(yǔ)法的提示往往是不正確的。總的來說，在自然語(yǔ)言處理領(lǐng)域中字平臺(tái)研究已快成為過去；句平臺(tái)上的研究還很薄弱，離實(shí)用還有一段距離；而詞平臺(tái)上的研究，難度較句平臺(tái)容易，已經(jīng)出現(xiàn)了一些成果，也是現(xiàn)在繼續(xù)研究的重點(diǎn)。文本分類與文本挖掘文本的知識(shí)發(fā)現(xiàn)最早是由Feldman和Dagan首先提出來的，又稱為文本數(shù)據(jù)挖掘。文本數(shù)據(jù)挖掘不僅是在單獨(dú)文本中提取所需信息，同時(shí)也包括分析文檔集合的模式和趨勢(shì)。文本挖掘不同于數(shù)據(jù)挖掘，數(shù)據(jù)挖掘面對(duì)的是結(jié)構(gòu)化數(shù)據(jù)，采用的方法大多是非常明確的定量方法。而文本挖掘處理的是非結(jié)構(gòu)化的文

32、本，由于語(yǔ)言本身的特點(diǎn)有其需要解決的特殊問題。因此，決定它采用的方法與數(shù)據(jù)挖掘不同，它經(jīng)常使用的方法來自自然語(yǔ)言理解和文本處理領(lǐng)域。與信息檢索(InformationRetrieval)、文本聚類(TextClustering)等一樣，文本分類也屬于文本挖掘(TextMining)的范疇，可以看成是文本挖掘中的一項(xiàng)基本任務(wù)。文本分類與機(jī)器學(xué)習(xí)文本分類是機(jī)器學(xué)習(xí)的應(yīng)用領(lǐng)域。機(jī)器學(xué)習(xí)是計(jì)算機(jī)程序針對(duì)某一類問題T從經(jīng)驗(yàn)E中學(xué)習(xí)，它的性能用P來衡量。很多的學(xué)者認(rèn)為使機(jī)器具有推廣性(具有小的測(cè)試錯(cuò)誤率)的唯一因素是使它在訓(xùn)練集上的錯(cuò)誤率最小。文本分類就是一個(gè)有指導(dǎo)的學(xué)習(xí)過程。它根據(jù)一個(gè)已經(jīng)被標(biāo)注了類別的

33、訓(xùn)練文本集合，找到文本特征和文本類別之間的關(guān)系模型，然后利用這種學(xué)習(xí)得到的關(guān)系模型對(duì)新的文本進(jìn)行類別判斷?？梢孕问交拿枋鰹椋杭僭O(shè)有一組文本概念類C和一組訓(xùn)練文本D。文本概念類和文本庫(kù)中的文本可能滿足某一概念層次關(guān)系h?？陀^上，存在著一個(gè)目標(biāo)概念T,有：T:DC這里，T把一個(gè)文本實(shí)例映射為某一個(gè)類。對(duì)D中的文本d-T(d)是已知的。通過有指導(dǎo)地對(duì)訓(xùn)練文本集的學(xué)習(xí)，可以找到一個(gè)近似于T的模型H：H:D-C在某些情況下最優(yōu)的目標(biāo)函數(shù)是沒有的，只能退而求其次。對(duì)于任何分類，最優(yōu)的目標(biāo)函數(shù)是指錯(cuò)誤率最小。對(duì)于一個(gè)新文本d-H(d)表示對(duì)d的分類結(jié)果。一個(gè)分類系統(tǒng)的建立或者說分類學(xué)習(xí)的目的就是尋找一個(gè)和

34、T最相近的H。即給定一個(gè)評(píng)估函數(shù)f,學(xué)習(xí)的目標(biāo)應(yīng)使T和H滿足：Min(ZD|)f(f(T(di)-H(di)imI機(jī)器學(xué)習(xí)中最重要的一些目標(biāo)函數(shù)的逼近算法如LMS、貝葉斯方法也被用到文本分類中。文本分類與模式識(shí)別通常把通過對(duì)某具體的個(gè)別事物進(jìn)行觀測(cè)所得到的具有時(shí)間和空間分布的信息稱為模式，而把模式所屬的類別或同一類中模式的總體稱為模式類(或簡(jiǎn)稱為類)。也有人習(xí)慣于把模式類稱為模式，而把具體的模式稱為樣本模式識(shí)別就是指用計(jì)算機(jī)實(shí)現(xiàn)人的模式識(shí)別能力，用機(jī)器去完成人類智能中通過視覺、聽覺、觸覺等感官去識(shí)別外界環(huán)境的自然信息的那些工作。模式識(shí)別的目的就是要尋找每一類的特殊的屬性或建立類與類之間的邊界，

35、使類與類之間可以很好的區(qū)分。在文本分類中，每一類文本可以看作一個(gè)模式，該類文本的總體構(gòu)成一個(gè)模式類，一個(gè)個(gè)文本都是樣本。模式識(shí)別有兩種基本的方法統(tǒng)計(jì)模式識(shí)別方法和句法模式識(shí)別方法。文本分類中主要使用統(tǒng)計(jì)模式識(shí)別方法，一方面由于以語(yǔ)義分析(句法模式識(shí)別)為手段遇到空前的困難，另一方面統(tǒng)計(jì)模式識(shí)別實(shí)現(xiàn)簡(jiǎn)單，出現(xiàn)了巨大的進(jìn)展。一般來講，一個(gè)模式識(shí)別系統(tǒng)主要由三部分組成，如圖2.2所示：預(yù)處理特征選擇識(shí)別算法圖2.2模式識(shí)別系統(tǒng)結(jié)構(gòu)輸入模式分類系統(tǒng)果描述T預(yù)處理指將現(xiàn)實(shí)世界的信息轉(zhuǎn)換成計(jì)算機(jī)所能夠接受的數(shù)字量。在中文文本分類過程中，則是將非結(jié)構(gòu)化的文本轉(zhuǎn)換為能夠用來進(jìn)行處理的結(jié)構(gòu)化形式。特征選擇指對(duì)滿

36、足識(shí)別要求的樣本根據(jù)識(shí)別方法，抽取其特征項(xiàng)作為識(shí)別的依據(jù)。這個(gè)過程的處理主要考慮兩個(gè)問題：一是要求選擇出來的特征能夠足夠代表這個(gè)樣本；二是要求它們的數(shù)量要盡量少。這個(gè)方面的研究也稱為“特征項(xiàng)降維”?，F(xiàn)在的文本分類所使用的特征選擇方法己經(jīng)有許多，如信息增益、互信息、交叉嫡等。識(shí)別算法則是將抽取出來的樣本特征創(chuàng)建一個(gè)用來區(qū)分類別的模型，文本分類中通常使用向量空間模型，通過識(shí)別算法得到的就是一個(gè)分類系統(tǒng)。模式識(shí)別研究的通常是一些通用的分類算法，其中許多算法都可以應(yīng)用在文本分類中如：Rocchio(中心向量方法)、NaiveBayes(樸素貝葉斯方法)、KNN(KNearstNeigllborK近鄰方

37、法)、DecisionTree(決策樹方法)、SVM等等。文本分類的關(guān)鍵技術(shù)文本表示從本質(zhì)上講，文本是一個(gè)由眾多字符構(gòu)成的字符串，無法被學(xué)習(xí)算法直接用于訓(xùn)練或分類。要將機(jī)器學(xué)習(xí)運(yùn)用于文本分類問題，首先需要將作為訓(xùn)練和分類對(duì)象的文本，轉(zhuǎn)化為機(jī)器學(xué)習(xí)算法易于處理的形式，即運(yùn)用各種文本特征表示方法，文本特征表示是指以一定特征項(xiàng)來代表文本，在文本分類時(shí)只需對(duì)這些特征項(xiàng)進(jìn)行處理，從而實(shí)現(xiàn)對(duì)非結(jié)構(gòu)化文本的處理?，F(xiàn)有文本分類技術(shù)的前提假設(shè)是特征和文本類別概念密切相關(guān)，特征表示模型有多種，常用的有概率模型、潛在語(yǔ)義索引模型、向量空間模型等。向量空間模型是近年來應(yīng)用較多且效果較好的方法之一。貝葉斯概率模型貝葉斯

38、概率模型是用概率架構(gòu)來表示特征項(xiàng)，將訓(xùn)練實(shí)例1分解為特征向量X和決策類別C；該模型假定特征向量的各分量間相對(duì)于決策變量是相對(duì)獨(dú)立的，也就是說各分量獨(dú)立地作用于決策變量。盡管這個(gè)假定在一定程度上限制了貝葉斯模型的適用范圍，然而在實(shí)際應(yīng)用中，以指數(shù)級(jí)降低了貝葉斯網(wǎng)絡(luò)構(gòu)建的復(fù)雜性。在很多領(lǐng)域即使違背這種假定的條件下，貝葉斯概率模型也表現(xiàn)出相當(dāng)?shù)慕研院透咝?，已?jīng)成功地應(yīng)用到分類、聚類中。潛在語(yǔ)義索引模型潛在語(yǔ)義索引模型LSI(LatentSemanticIndex)模型是由Dumais，F(xiàn)urnas，Landaver和Harshman于1990年提出，也用向量表示特征項(xiàng)，但是每一個(gè)向量代表一個(gè)“概

39、念”，就是通常所說的“概念空間模型”。LSI使用一種數(shù)學(xué)上的“奇異值分解即(Singular、ValueDecomposition,SVD)”技術(shù)，把文檔投影到一個(gè)具有潛在語(yǔ)義的“特征.文本”多維空上,共現(xiàn)特征、同義特征投影在同一維上，非共現(xiàn)特征、非同義特征在不同的維上，這樣就會(huì)出現(xiàn)沒有共同的特征的文本間也會(huì)有較高的相似度。向量空間模型向量空間模型(VectorSpaceModel)是由GerardSalton和McGill于1969年提出的，并最早成功應(yīng)用于信息檢索領(lǐng)域，后來又在文本分類領(lǐng)域得到了廣泛的運(yùn)用。向量空間模型的基本思想是以向量來表示文本：(WWWn)，其中Wi為第i個(gè)特征項(xiàng)1,2

40、,的權(quán)重。那么選取什么作為特征項(xiàng)呢？一般可以選擇字、詞或詞組。根據(jù)前人經(jīng)驗(yàn)，普遍認(rèn)為選取詞作為特征項(xiàng)要優(yōu)于字和詞組。因此，要將文本表示為向量空間中的一個(gè)向量，就首先要將文本分詞，由這些詞作為向量的維數(shù)來表示文本。最初的向量表示完全是0、1形式，即：如果文本中出現(xiàn)了該詞，那么文本向量的該維為1,否則為0。這種方法無法體現(xiàn)這個(gè)詞在文本中的作用程度，所以逐漸0、1被更精確的詞頻代替。詞頻分為絕對(duì)詞頻和相對(duì)詞頻，絕對(duì)詞頻，即使用詞在文本中出現(xiàn)的頻率表示文本，相對(duì)詞頻為歸一化的詞頻，其計(jì)算方法主要運(yùn)用TFIDF公式，它是一種文本的詞集表示法，所有的詞從文本中抽取出來，而不考慮詞間的次序和文本的結(jié)構(gòu)。目前

41、存在多種TF-IDF公式，一種比較普遍的TF-IDF公式：(2.1)f(t,d)*log(N：n+0.01)W(t,d)=匸斯工tf(t,d)*log(Nn)+0.01)ed其中，W(t,d)為詞t在文本d中的權(quán)重，而tf(t,d)為詞t在文本d中的詞頻，N為訓(xùn)練文本的總數(shù)，Nt訓(xùn)練文本集中出現(xiàn)t的文本數(shù)，分母為歸一化因子。另外還存在其他的TF-IDF公式，例如:(2.2)(1+logtf(t,d)*log(Nn)W(t,d)=222迄(1+logtf(t,d)*log(Nn)2ed221該公式中參數(shù)的含義與式(2.1)相同。向量空間模型的一個(gè)基本假設(shè)是，一份文本所屬的類別僅與某些特定的單詞或

42、詞組在該文檔中出現(xiàn)的頻數(shù)有關(guān)，而與這些單詞或詞組在該文本中出現(xiàn)的位置或順序無關(guān)。也就是說，如果將構(gòu)成文本的各種語(yǔ)義單位(如單詞、詞組)統(tǒng)稱為“特征項(xiàng)”，以及特征項(xiàng)在文本中出現(xiàn)的次數(shù)稱為“詞頻”，那么一份文本中蘊(yùn)涵的各個(gè)特征項(xiàng)的頻率信息足以用來對(duì)其進(jìn)行正確的分類。這一假設(shè)對(duì)于文本的主題分類而言是恰當(dāng)?shù)?，而?duì)于其他方面的文本分類，如流派、作者等識(shí)別問題就不那么可靠了。向量空間模型中，一個(gè)文本表示為特征空間中的一個(gè)向量，這個(gè)向量也稱為文本向量。文本向量中每一維對(duì)應(yīng)于文本中的一個(gè)特征，它的權(quán)重為該向量維對(duì)應(yīng)的特征在文本中的權(quán)重。特征選擇目前主流的文檔表示方法是向量空間模型。向量空間模型中，一篇文檔表示

43、為特征空間中的一個(gè)向量，這個(gè)向量也稱為文檔向量。文檔向量中每一維對(duì)應(yīng)于文檔中的一個(gè)特征，它的權(quán)值為該向量維對(duì)應(yīng)的特征在文檔庫(kù)中的權(quán)值，一般采用TF-IDF方法計(jì)算。若使用詞語(yǔ)作為文本特征，那么文本的特征向量會(huì)達(dá)到上萬維甚至數(shù)十萬維的大小，在此一個(gè)高維空間上對(duì)文本分類所使用的學(xué)習(xí)算法進(jìn)行訓(xùn)練，顯得既不經(jīng)濟(jì)又無必要，因此必須通過特征選擇來進(jìn)行維數(shù)壓縮，特征選擇經(jīng)常會(huì)使用特征獨(dú)立性假設(shè)來簡(jiǎn)化特征選擇，以達(dá)到計(jì)算時(shí)間和計(jì)算質(zhì)量的折衷。因此，目前在對(duì)文本的特征空間所采取的特征選擇算法一般是構(gòu)造一個(gè)評(píng)價(jià)函數(shù)，對(duì)特征集中的每個(gè)特征進(jìn)行獨(dú)立的評(píng)估。這樣每個(gè)特征都獲得一個(gè)評(píng)估分，然后對(duì)所有的特征按照其評(píng)估分的大

44、小進(jìn)行排序，選取預(yù)定數(shù)目的最佳特征作為結(jié)果的特征子集在中文文本分類中，文本集經(jīng)過分詞后變成詞集，然后經(jīng)過去掉停用詞粗降維得到特征集。但是特征集仍然是個(gè)高維的特征空間，對(duì)于所有的分類算法來說維數(shù)都太大。因此，我們面臨尋求一種有效的特征抽取方法，以降低特征空間的維數(shù)，提高分類的效率和精度。特征選擇的目的是除去特征集中不能較好表示有效信息的特征，以提高分類準(zhǔn)確度和減少計(jì)算復(fù)雜度。常見的特征選擇方法有以下四種：文檔頻率(DF)、信息增益(IG)、互信息(MI)、X2統(tǒng)計(jì)量(CHI)等。這些方法的基本思想都是對(duì)每一個(gè)特征即詞條，計(jì)算它的某種統(tǒng)計(jì)的度量值，然后設(shè)定一個(gè)閾值T,把度量值小于T的那些特征過濾掉

45、，剩下的即認(rèn)為是有效特征。下面分別介紹這幾種特征選擇算法。文檔頻率(DocumentFrequency，DF)2.3)單次出現(xiàn)的文檔數(shù)DF(W)=-訓(xùn)練集的文檔總數(shù)文檔頻數(shù)是最簡(jiǎn)單的評(píng)估函數(shù)，其值為訓(xùn)練集合中出現(xiàn)此詞的文本數(shù)占總的文本數(shù)的概率。DF評(píng)估函數(shù)的理論假設(shè)是：稀有單詞要么不含有用信息，要么太少而不足以對(duì)分類產(chǎn)生影響；要么是噪音，所以可以刪去。雖然它在計(jì)算量上比其它的評(píng)估函數(shù)小得多，但是在實(shí)際運(yùn)用中它的效果卻是出奇地好。需要注意的是，在特征選擇之前必須將停用詞去掉，僅保留與主題相關(guān)的詞匯。躑估函數(shù)也存在缺點(diǎn)，比如稀有單詞可能在某一類文本中并不稀有，而且包含著重要的判斷信息。在實(shí)際運(yùn)用中

46、一般并不直接使用DF評(píng)估函數(shù)，常把它作為評(píng)判其它評(píng)估函數(shù)的標(biāo)準(zhǔn)。信息增益(informationGain，IG)信息增益通過統(tǒng)計(jì)某個(gè)特征項(xiàng)在一篇文檔中出現(xiàn)或不出現(xiàn)的次數(shù)來預(yù)測(cè)文檔的類別。它是一種基于熵的評(píng)估方法，涉及較多的數(shù)學(xué)理論和復(fù)雜的熵理論公式，定義為某特征項(xiàng)為整個(gè)分類所能提供的信息量，不考慮任何特征的熵與考慮該特征后的熵的差值。他根據(jù)訓(xùn)練數(shù)據(jù)，計(jì)算出各個(gè)特征項(xiàng)的信息增益，刪除信息增益很小的項(xiàng)，其余的按照信息增益從大到小排序。其描述如下：；P(C.W)LP(C/W)小八IG(W)=P(W)P(C.W)logi+P(W)XP(C.-W)logi(2.4)iP(C)iP(C)iii其中P(Ci

47、/W)表示文本中出現(xiàn)詞W時(shí)，文本屬于類別Ci的概率，同樣P(Ci/W)表示文中不出現(xiàn)詞W時(shí)文本屬于類別Ci的概率；P(Ci)表示類別出現(xiàn)的概率；P(W)表示詞W在整個(gè)文本訓(xùn)練集中出現(xiàn)的概率。信息增益是一種在機(jī)器學(xué)習(xí)領(lǐng)域應(yīng)用較為廣泛的特征選擇方法。它從信息論角度出發(fā)，用各個(gè)特征的取值情況來劃分學(xué)習(xí)樣本空間，然后根據(jù)所獲信息增益的多寡來選擇相應(yīng)的特征?；バ畔?MutualInformation，MI)(2.5)P(WC)MI=XP(C)logiP(W)i詞條和類別的互信息體現(xiàn)了詞條與類別的相關(guān)程度，是一種廣泛用于建立詞關(guān)聯(lián)統(tǒng)計(jì)模型的標(biāo)準(zhǔn)。如果詞W在某個(gè)類別Ci中出現(xiàn)的概率高，而在其它類別中出現(xiàn)的概

48、率低，則W將獲得較高的互信息，也就有可能被選取為類別Ci的特征。X2統(tǒng)計(jì)量(CHI)PPN(AD-BC)2(26)CHI(W)=XP(C)X2(W,C)=XP(C)(2.6)iii(A+C)(B+D)(A+B)(C+D)ii其中A表示詞W在類別Ci中出現(xiàn)的頻度；B表示詞W在除Ci以外的其它類別中出現(xiàn)的頻度,C表示除W以外的其它詞在類別Ci中出現(xiàn)的頻度；D表示除W外的其它詞在除Ci以外的其它類別中出現(xiàn)的頻數(shù)。該方法類似于互信息MI,詞的X2(CHI)統(tǒng)計(jì)值比較了詞對(duì)一個(gè)類別的貢獻(xiàn)和對(duì)其余類別的貢獻(xiàn)，以及詞和其它詞對(duì)分類的影響。當(dāng)詞礦與類別C,互相獨(dú)立時(shí)，ADBC=O,X2(CHI)的值為O；若A

49、DBCO,說明詞W與類別Ci正相關(guān)，即該詞出現(xiàn)說明某個(gè)類別很可能出現(xiàn);反之，若ADBC1i=1,m3.4)進(jìn)一步，支持向量機(jī)方法首先求解該問題的對(duì)偶問題最小化形式，minmm乙乙yyaa(x,x)ijijijai=1j=1ms.t.Xya=0iii=1a0i=1,m(3.5)i然后根據(jù)對(duì)偶問題的解得到原問題的解，具體求解過程就是根據(jù)原始問題的Lagrange函數(shù)以及KKT條件可以計(jì)算得到：w=$yax:選擇a的一個(gè)分量ao,iiii=1b=xa(、，從而來確定決策函數(shù)。算法具體的步驟如下:b=yy.(xx)jiiiji=1算法1線性可分支持向量分類機(jī)(1)構(gòu)造并求解最優(yōu)化問題minmm乙乙yy

50、aa(x,x)ijijijai=1j=1ms.t.Tya=0iii=1a0i=1mi(3.6)得最優(yōu)解a=(a1a)T；n計(jì)算W=yax,選擇a.的一個(gè)分量a.0,b=y一ya.(xx)iiijjjjjiji=1i=1構(gòu)造分類超平面(wx)+b=O，由此得到?jīng)Q策函數(shù)f(x)=sgn(W*x)+b)(3.7)“支持向量”是指訓(xùn)練集中的某些訓(xùn)練點(diǎn)的輸入x。事實(shí)上，最優(yōu)化問題(3.6)的解ja的每一個(gè)分量a都與一個(gè)訓(xùn)練點(diǎn)相對(duì)應(yīng)，顯然算法1所構(gòu)造的分類超平面，僅僅依賴于那些a；不為零的訓(xùn)練點(diǎn)(x,y),而與相應(yīng)于a為零的訓(xùn)練點(diǎn)無關(guān)。所以我們特別關(guān)心相應(yīng)ij于a不為零的訓(xùn)練點(diǎn)(x,y),并稱這些訓(xùn)練點(diǎn)的

51、輸入x為支持向量。顯然，只有支持向量jiji對(duì)最終求得的分類超平面的法方向w有影響，而與非支持向量無關(guān)。近似線性可分問題用一條直線也能大體上(大體上意味著有某一個(gè)或者很少的幾個(gè)點(diǎn)劃分錯(cuò)誤)把訓(xùn)練集正確分開，這類問題稱為近似線性可分問題，這時(shí)仍可以考慮用線性分類學(xué)習(xí)機(jī)。具體求解方法類似線性可分問題，其步驟如下：算法2近似線性可分支持向量分類機(jī)選擇適當(dāng)?shù)膽土P參數(shù)c0,構(gòu)造并求解最優(yōu)化問題mina12i=1j=1yyaa(xijijimx)一乙ajjj=1ms.t.乙ya=0ii3.8)i=10aci=1,mi得最優(yōu)解a=(a1am)T1m計(jì)算W=Tya.xiiii=1選擇a的一個(gè)分量0a1ii1g

52、0,i=1,m(3.10)i這里M=(x),是特征空間日中的輸入向量。類似，引入它的對(duì)偶問題的極小化形式:1j1mmmmin乙乙yyaak(xx)一乙a(3.11)2ijijijjai=1j=1j=1ms.t.乙ya=0iii=1(3.12)0aci=1,m(3.13)i令矩陣H(i,j)=yyK(x,y)，其中i,j=1,2,.J,即稱為核函數(shù)矩陣，它是一個(gè)ijij半正定的對(duì)稱矩陣，第一個(gè)約束條件式(312)稱為超線性約束條件，第二個(gè)約束條件式(313)稱為超立方體約束條件。這里K(x,x)=(x)(x)(3.14)ijjj稱為核函數(shù)，有關(guān)核函數(shù)的進(jìn)一步討論可參見本文后面的有關(guān)討論。類似前面

53、的求解方法，通過求解對(duì)偶問題來確定最終的決策函數(shù)，這樣得到標(biāo)準(zhǔn)支持向量分類機(jī)算法。算法3支持向量分類機(jī)(c-svc)選擇核函數(shù)K(x,x)和懲罰參數(shù)C,構(gòu)造并求解最優(yōu)化問題ijmina丄2j=1i=1j=1ms.t.乙ya=0iii=10aci=1,mi(3.15)得最優(yōu)解a=(a1am)T1m(2)選擇a的一個(gè)分量0a.C;并據(jù)此計(jì)算b=y一工ya.K(xx)jjjjiji=1(3)求得決策函數(shù)：f(x)=sgn(工yaK(x,x)+b)。iiiji=1支持向量機(jī)的應(yīng)用步驟在使用svM方法來解決實(shí)際問題時(shí),首先要從具體問題獲取訓(xùn)練數(shù)據(jù)并進(jìn)行預(yù)處理,然后需要選擇合適的核函數(shù)和相應(yīng)的參數(shù)，最后用

54、求得的最佳參數(shù)來訓(xùn)練SVM,其基本步驟簡(jiǎn)述如下：將實(shí)際問題數(shù)據(jù)化 一般來說SVM只能處理數(shù)值類型的數(shù)據(jù)，從實(shí)際問題中提取的樣本如果含有像字符串類型、類別類型、范圍類型等非數(shù)值屬性，都需要先通過某些方式轉(zhuǎn)換為數(shù)值類型來表達(dá)。進(jìn)行數(shù)據(jù)規(guī)格化對(duì)數(shù)據(jù)集進(jìn)行規(guī)格化(Scaling)是很重要的。它的主要作用是避免數(shù)值范圍較大的屬性的影響力過大以致數(shù)值范圍較小的屬性可能根本不起作用。另一方面，規(guī)格化也可以降低數(shù)值運(yùn)算的復(fù)雜性，通常將每個(gè)屬性值按比例縮放到-1,1或者0,1范圍內(nèi)。訓(xùn)練樣本數(shù)據(jù)和測(cè)試樣本數(shù)據(jù)需要進(jìn)行同樣比例的縮放。選擇核函數(shù)常用的核函數(shù)有線性核、多項(xiàng)式核、RBF核和Sigmoid核等很多種，各

55、有不同的優(yōu)點(diǎn)和適用場(chǎng)合。在這幾種核函數(shù)中，計(jì)算最快的是線性核，在訓(xùn)練集特別大或?qū)傩蕴貏e多的情況下也可以快速地訓(xùn)練出結(jié)果，但它只有在近似線性可分的情況下才能取得滿意的效果。多項(xiàng)式核計(jì)算也較快，其函數(shù)值可能趨向無窮大或者零，跨度非常大，在一些情況下有可能造成計(jì)算困難：Sigmoid核不是正定核，在有些情況下通用性不夠。RBF核函數(shù)具有良好的性能，在缺乏問題先驗(yàn)知識(shí)時(shí)其適應(yīng)性是最好的，它能夠處理非線性的情況，而在參數(shù)取某些特定值時(shí)，又和線性核或Sigmoid核具有相似的性能。RBF核的另一個(gè)優(yōu)點(diǎn)是它只有一個(gè)核參數(shù)，比多項(xiàng)式核和Sigmoid核少，在選擇參數(shù)時(shí)的比較方便。尋找最優(yōu)參數(shù)訓(xùn)練SVM時(shí)要考慮

56、兩種參數(shù)：核參數(shù)和懲罰參數(shù)C。參數(shù)的選擇并沒有通用的先驗(yàn)知識(shí)，需要在一定范圍內(nèi)進(jìn)行搜索以找到好的參數(shù)組合。由統(tǒng)計(jì)學(xué)習(xí)理論可知，得到高的訓(xùn)練正確率并不能保證在未來的測(cè)試中具有高的預(yù)測(cè)精度，因此對(duì)不同參數(shù)組合訓(xùn)練所得的SVM需要進(jìn)行模型選擇，以取得推廣能力最強(qiáng)的SVM模型。用最優(yōu)參數(shù)來訓(xùn)練SVM模型經(jīng)過測(cè)試確認(rèn)學(xué)習(xí)精度較好的SVM模型將被用于解決實(shí)際問題。3.4基于支持向量機(jī)文本分類方法的優(yōu)勢(shì)文本分類的特點(diǎn)有：文本分類所需要處理的樣本空間非常龐大，即便通過簡(jiǎn)化，僅考慮詞，而不考慮詞的次序不同、斷句等的不同所表達(dá)的含義的不同，樣本的維數(shù)也很咼；文本向量非常稀疏;文本特征之間存在較大的相關(guān)性;文本訓(xùn)練

57、樣本集中存在較多噪音；不同文本類別的訓(xùn)練樣本數(shù)目往往存在較大差別。文本分類的這些特點(diǎn)，使得很多分類算法的效果不好。與其它文本分類算法相比，支持向量機(jī)主要具有如下優(yōu)勢(shì)：文本數(shù)據(jù)向量維數(shù)很咼，對(duì)于咼維問題，支持向量機(jī)具有其它機(jī)器學(xué)習(xí)方法不可比擬的優(yōu)勢(shì)；文本向量特征相關(guān)性大，許多文本分類算法建立在特征獨(dú)立性假設(shè)基礎(chǔ)上，受特征相關(guān)性的影響較大，而支持向量機(jī)對(duì)于特征相關(guān)性不敏感；文本向量存在咼維稀疏問題，一些文本分類算法不同時(shí)適合于稠密特征矢量與稀疏特征矢量的情況，但支持向量機(jī)對(duì)此不敏感；文本分類樣本收集困難、內(nèi)容變化迅速，支持向量機(jī)能夠找出包含重要分類信息的支持向量，是強(qiáng)有力的增量學(xué)習(xí)和主動(dòng)學(xué)習(xí)工具，

58、在文本分類中具有很大的應(yīng)用潛力。3.5基于支持向量機(jī)文本分類方法中存在的問題支持向量機(jī)從被廣泛重視到現(xiàn)在只有十多年的時(shí)間，已經(jīng)提出的很多關(guān)于支持向量機(jī)的訓(xùn)練算法，從訓(xùn)練時(shí)間和分類精度兩種角度進(jìn)行優(yōu)化。其中還存在很多尚未解決或尚未充分解決的問題，需要進(jìn)一步完善和改進(jìn)以適應(yīng)實(shí)際應(yīng)用的需要，支持向量機(jī)在實(shí)際應(yīng)用中、尤其在文本分類等類別和樣本數(shù)目多、噪音多的應(yīng)用中存在的主要問題包括：(1)對(duì)于需要求解二次規(guī)劃問題的支持向量機(jī)模型，當(dāng)樣本數(shù)目較多時(shí)，其訓(xùn)練速度較慢。尤其對(duì)于訓(xùn)練樣本和支持向量數(shù)目多的分類問題，支持向量機(jī)的分類和訓(xùn)練速度過慢，這一點(diǎn)限制了支持向量機(jī)的應(yīng)用，成為支持向量機(jī)方法進(jìn)入大規(guī)模實(shí)用化

59、階段的瓶頸。如何進(jìn)一步改進(jìn)和完善支持向量機(jī)模型及其訓(xùn)練算法，是支持向量機(jī)研究中的熱點(diǎn)問題。向量維數(shù)較高時(shí)其訓(xùn)練和分類速度較慢。支持向量機(jī)中核函數(shù)及參數(shù)的選擇沒有好的確定的方法，仍然憑經(jīng)驗(yàn)尋求。不同的核函數(shù)對(duì)應(yīng)的支持向量集合有所不同，而支持向量的少量丟失都會(huì)引起分類精度的下降，大規(guī)模文本分類中在減少樣本數(shù)目時(shí)怎樣保證不丟失支持向量仍然是個(gè)難點(diǎn)。第四章小波變換在支持向量機(jī)分類中的應(yīng)用問題的提出在機(jī)器學(xué)習(xí)中，對(duì)于一個(gè)學(xué)習(xí)任務(wù)，待學(xué)習(xí)的目標(biāo)函數(shù)的復(fù)雜程度取決于特征的表示形式和特征空間的維數(shù)。另一方面，特征空問的大小除了影響計(jì)算復(fù)雜度以外，還影響著學(xué)習(xí)機(jī)器的泛化能力。據(jù)我們所知，一個(gè)學(xué)習(xí)機(jī)的泛化能力與所

60、使用的函數(shù)有關(guān)，也與特征的維數(shù)有密切關(guān)系的。過高的特征維數(shù)是產(chǎn)生過度擬合問題的一個(gè)重要因素。通常來講，計(jì)算復(fù)雜度和對(duì)數(shù)據(jù)過度擬合的問題是一般分類器都無可避免和必須解決的問題，但支持向量機(jī)模型則完美地解決這兩個(gè)問題：通過引入核函數(shù)，從原始空間向高維特征空間作隱式映射，解決了計(jì)算復(fù)雜度與文本表示需要高維特征的矛盾；另一方面，根據(jù)統(tǒng)計(jì)學(xué)習(xí)理論，支持向量機(jī)的泛化能力只取決于實(shí)例的個(gè)數(shù)，包含所有實(shí)例的球體半徑，最小邊界的最大值等幾個(gè)因素決定，而與特征空間的維數(shù)無關(guān)。同時(shí)，人們也對(duì)文本分類任務(wù)中，以向量空間模型表示文本時(shí)的性質(zhì)進(jìn)行了深入的研究。這些性質(zhì)包括：向量空間的高維性、文檔向量的稀疏性，特征之間的實(shí)