【正文】 i++) //每一條樣本所含有的參數(shù)的初始化 { 。 for(i=0。 //無(wú)分類值的樣本 // 界面上顯示懲罰參數(shù) sprintf(temstr, 設(shè)定懲罰參數(shù) C : %.2f, train_parmsvm_c)。 //樣本數(shù) modelsvnum=1。 //alpha數(shù)組，每個(gè)樣本對(duì)應(yīng)一個(gè)alpha modelmaxid=maxid。 //偏超平面的閾值 modelsupvec[0]=0。 // 模式結(jié)構(gòu)體中的參數(shù)設(shè)置 modelupbound=0。 modelalpha = (double *)setmemory(sizeof(double)*(sumline+2))。 //每行分配一個(gè)內(nèi)存塊 train_parmvarbound = (double *)setmemory(sizeof(double)*sumline)。 a = (double *)setmemory(sizeof(double)*sumline)。 inconsistent = (long *)setmemory(sizeof(long)*sumline)。shrink,sumline,(long)10000)。 //最大特征分量序號(hào) train_parmnewvars=train_parmqsize。 //正負(fù)分類值計(jì)數(shù)器 SHRINK shrink。 //進(jìn)行縮減優(yōu)化的次數(shù) long *unlabeled,transduction。 //上界支持向量數(shù) double maxchange,*lin,*a。 //處理樣本時(shí)非固定部分 long misclassified(0)。ubingen, Germany[14] Mamoun Awad, Latifur Khan, Applications and Limitations of Support Vector Machines, Department of Computer Science, University of Texas at Dallas, USA.[15] Yiming Yang and Xin Liu, A reexamination of text categorization methods. School of Computer Science, Carnegie Mellon University. 1999, ACM 1581130961/99/0007[16] Nello Cristianini, Support Vector and Kernel Machines. BIOwulf Technologies, ICML 2001.[17] T. Mitchell. Machine Learning, McGrawHill Science/Engineering/Math。atsch, A Brief Introduction into Machine Learning. Friedrich Miescher Laboratory of the Max Planck Society, Spemannstra223。相信今后進(jìn)一步的研究可以充分地發(fā)揮支持向量機(jī)適用范圍廣，分類能力好等特點(diǎn)，并使其與其他分類方法結(jié)合使用，使分類效果和效率得到更大的提高。目前有人開(kāi)始研究利用人工智能和機(jī)器學(xué)習(xí)領(lǐng)域中其他一些成熟的技術(shù)與支持向量機(jī)進(jìn)行有機(jī)結(jié)合，進(jìn)而提高其分類能力，例如把支持向量機(jī)和二叉樹(shù)結(jié)合在一起得到多類別分類器[16]?；诮y(tǒng)計(jì)學(xué)習(xí)理論的支持向量機(jī)方法自提出以來(lái)就一直受到人們的關(guān)注，同時(shí)它也因?yàn)閼?yīng)用領(lǐng)域廣而成為當(dāng)今機(jī)器學(xué)習(xí)以及模式識(shí)別的一個(gè)研究熱門。4． 可以利用更好的優(yōu)化算法來(lái)加快分類器學(xué)習(xí)速度。因此為了提高分類機(jī)的學(xué)習(xí)能力和分類能力，可以在以后的程序中可以使用其他的更復(fù)雜的核函數(shù)。而在分類面最大化思想中，懲罰參數(shù)實(shí)際上是可以和分類面的法向量有關(guān)的，具體地說(shuō)，在線性分類機(jī)中可以讓 ， 在其他更復(fù)雜的支持向量機(jī)中也可以通過(guò)試驗(yàn)來(lái)確定懲罰參數(shù)的適用值。程序中不需要考慮如何實(shí)現(xiàn)向量空間模型，即不用考慮對(duì)實(shí)際文本（網(wǎng)頁(yè)）進(jìn)行特征分量化以及降維的工作。同時(shí)每個(gè)樣本中特征分量的個(gè)數(shù)也已經(jīng)得到有效的削減。4． 本支持向量分類器只進(jìn)行了初步的優(yōu)化，有限地提高了運(yùn)行速度。2． 本程序中的懲罰參數(shù)C是提前設(shè)置的，數(shù)據(jù)樣本集以及記錄運(yùn)行結(jié)果的文本的位置也是提前設(shè)定好的。以上這些優(yōu)點(diǎn)使得SVMs 成為一種非常有前途的、易于使用的文本分類器學(xué)習(xí)方法。支持向量機(jī)分類器的另一個(gè)優(yōu)點(diǎn)是它的健壯性（robustness），在前人所做的SVC與其他算法實(shí)現(xiàn)的分類器的對(duì)比實(shí)驗(yàn)中[1][7]，SVMs 都取得了很好的分類效果，并且避免了其他方法可能遇到的失敗。ve Bayes Classifier），KNN Classifier,神經(jīng)網(wǎng)絡(luò)（Neural Network Classifier）等。本文介紹了文本分類問(wèn)題中的支持向量機(jī)概念，并分別從理論和實(shí)驗(yàn)兩方面證明了支持向量機(jī)方法是能夠適用于文本分類任務(wù)的。第五章 論文結(jié)論本文實(shí)現(xiàn)了一個(gè)簡(jiǎn)單的基于支持向量機(jī)的文本分類器。但是支持向量機(jī)分類器相對(duì)于其他的分類方法，包括樸素貝葉斯方法，其分類效果更好好，分類器健壯性和抗噪音能力比其他常用分類器好。而該支持向量分類器僅對(duì)2000個(gè)已經(jīng)向量化且降維后的樣本進(jìn)行學(xué)習(xí)就用時(shí)20秒。對(duì)2000個(gè)文檔進(jìn)行學(xué)習(xí)所耗費(fèi)時(shí)間是20秒，2000個(gè)文檔中最多有特征分量283個(gè)。第一，SVC在對(duì)訓(xùn)練集進(jìn)行模式學(xué)習(xí)時(shí)沒(méi)有過(guò)多地考慮優(yōu)化的問(wèn)題，所以一些樣本對(duì)支持向量分類器起到了干擾作用。同時(shí)，在相同數(shù)據(jù)集下改變懲罰參數(shù)的值，優(yōu)化閾值等支持向量機(jī)參數(shù)，也會(huì)改變分類準(zhǔn)確率。圖49 有分類值樣本的分類測(cè)試結(jié)果圖410 無(wú)分類值樣本的分類測(cè)試結(jié)果圖 411 有分類值的測(cè)試樣本的分類結(jié)果文檔示例圖 412 無(wú)分類值的測(cè)試樣本的分類結(jié)果文檔示例 圖 413 混合型測(cè)試樣本的分類結(jié)果文檔示例本分類器實(shí)現(xiàn)的是對(duì)經(jīng)由特征分量提取和降維處理后的數(shù)據(jù)集，但處理樣本的時(shí)間跟其他種類的分類器相比仍然很長(zhǎng)，而且在對(duì)特征分量的選擇上沒(méi)有優(yōu)化處理過(guò)程。分類測(cè)試結(jié)束時(shí)，程序提示分類結(jié)果的保存方式，并詢問(wèn)是否察看結(jié)果文檔。結(jié)果文檔記錄了分類器對(duì)測(cè)試集中所有樣本的分類情況，包括樣本序號(hào)，樣本原有的分類值，經(jīng)分類器計(jì)算得到的分類值已經(jīng)分類正確情況等。分類測(cè)試的過(guò)程模擬了實(shí)際使用中的分類過(guò)程。圖48 程序?qū)y(cè)試集和測(cè)試結(jié)果的說(shuō)明當(dāng)程序開(kāi)始進(jìn)行分類測(cè)試時(shí)，首先檢測(cè)是否存在測(cè)試集和模式文檔。用戶點(diǎn)擊測(cè)試分類器時(shí)，程序彈出對(duì)話框?qū)y(cè)試集和測(cè)試結(jié)果的默認(rèn)路徑進(jìn)行提示，同時(shí)詢問(wèn)是否進(jìn)行分類器的分類測(cè)試。該程序可以對(duì)新的未賦予分類值的樣本進(jìn)行分類，其前提就是要在訓(xùn)練階段得到一個(gè)合適的模式（Model）。模式文檔的作用不僅僅是提供了對(duì)模式的文字說(shuō)明和記錄，同時(shí)也是最重要的一點(diǎn)是模式文檔是支持向量分類器分類測(cè)試階段的基本輸入之一。當(dāng)支持向量分類器訓(xùn)練結(jié)束時(shí)，程序詢問(wèn)是否打開(kāi)模式文檔，用戶可以選擇“確定”來(lái)調(diào)用寫字板打開(kāi)文本，也可以選擇“取消”直接進(jìn)入下一步操作。例如當(dāng)程序調(diào)用SvmTrain()進(jìn)行分類器訓(xùn)練時(shí)，就會(huì)顯示“開(kāi)始利用訓(xùn)練集進(jìn)行訓(xùn)練”，讀取文本，寫模式等過(guò)程都會(huì)有相應(yīng)的文字說(shuō)明，通過(guò)這些文字就可以知道支持向量分類器的訓(xùn)練過(guò)程和進(jìn)度。圖44 開(kāi)始訓(xùn)練支持向量機(jī)前要詢問(wèn)是否開(kāi)始訓(xùn)練時(shí)，訓(xùn)練過(guò)程中的一些運(yùn)算結(jié)果會(huì)顯示在界面上，其中包括訓(xùn)練集中樣本個(gè)數(shù)（包括正樣本個(gè)數(shù)，負(fù)樣本個(gè)數(shù)，未分配分類值樣本個(gè)數(shù)），懲罰參數(shù)C，調(diào)用支持向量機(jī)優(yōu)化器次數(shù)，支持向量的個(gè)數(shù)等。用戶也可點(diǎn)擊“否”使程序進(jìn)入等待狀態(tài)并在想要開(kāi)始進(jìn)行分類器的訓(xùn)練時(shí)再次開(kāi)始訓(xùn)練分類器。就訓(xùn)練階段而言，程序已經(jīng)默認(rèn)裝載了訓(xùn)練集所在路徑。以下就各部分的輸入輸出關(guān)系作以說(shuō)明：基本輸入訓(xùn)練集測(cè)試集模式基本輸出模式測(cè)試結(jié)果訓(xùn)練支持向量分類器階段測(cè)試支持向量分類器階段界面上文本顯示訓(xùn)練集，測(cè)試集路徑。與工具行功能相同單擊清除SDI中文字圖42 程序界面該支持向量機(jī)分類器的訓(xùn)練和測(cè)試工作被設(shè)計(jì)在同一界面下進(jìn)行，這樣就使得兩部分計(jì)算中得到的說(shuō)明文字可以在同一個(gè)界面上顯示出來(lái)，即在程序運(yùn)行期間可以看到訓(xùn)練階段和測(cè)試階段的運(yùn)行結(jié)果。界面的基本框架由VC自動(dòng)生成，對(duì)界面的編程主要體現(xiàn)在顯示文字和使用菜單上。該程序由C++編寫。同時(shí)該程序也可以對(duì)符合格式要求的新樣本進(jìn)行分類。特征分量編號(hào) 圖41 樣本示例測(cè)試集與訓(xùn)練集的樣本格式完全相同，數(shù)據(jù)集A中的測(cè)試集均為8個(gè)特征分量的樣本，為了能夠計(jì)算分類正確率該測(cè)試集中的樣本已經(jīng)帶有分類值。A數(shù)據(jù)集中的樣本是支持向量分類器的簡(jiǎn)單狀態(tài)，B數(shù)據(jù)集中的樣本則模擬了實(shí)際應(yīng)用中可能出現(xiàn)的特征分量數(shù)目不固定的情況。為了方便程序運(yùn)行A數(shù)據(jù)集中的每個(gè)樣本的特征分量數(shù)都是8個(gè)，用來(lái)編程階段的實(shí)驗(yàn)。后期使用了2600個(gè)樣本的數(shù)據(jù)集B，其中2000個(gè)樣本作為訓(xùn)練集，600個(gè)樣本作為測(cè)試集。）但是應(yīng)該指出，這種啟發(fā)式的方法并不是絕對(duì)準(zhǔn)確的。這種判知優(yōu)化的方法可以大大減少分類器的訓(xùn)練時(shí)間和使用核函數(shù)的頻率。同時(shí)，對(duì)于沒(méi)有優(yōu)化的樣本點(diǎn)，可以使用基于拉格朗日乘子評(píng)價(jià)的啟發(fā)式規(guī)則進(jìn)行猜測(cè)。這里使用了基于拉格朗日乘子評(píng)價(jià)（Lagrange Multiplier Estimate）的啟發(fā)式方法來(lái)判斷那些不可能成為支持向量的樣本以及上界支持向量。這種縮小樣本輸入的方法可以表示如下：假設(shè)下標(biāo)X表示非上界支持向量，下標(biāo)Y表示上界支持向量，下標(biāo)Z表示非支持向量。由此，縮小樣本輸入（Shrinkage）的過(guò)程就是在運(yùn)算過(guò)程中提早發(fā)現(xiàn)不可能成為支持向量的樣本和那些上界樣本。同樣，在有噪聲的情況下，很多支持向量的值是等于懲罰參數(shù)C的（上界上的支持向量）。對(duì)于大多數(shù)支持向量機(jī)分類器來(lái)說(shuō)，其得到的支持向量的個(gè)數(shù)往往比訓(xùn)練集中的樣本個(gè)數(shù)少很多。由于(112)式是對(duì)(110)式的一種改寫所以，對(duì)(112)式的優(yōu)化得到的解也可以應(yīng)用到(110)式中。（表達(dá)式(112)是對(duì)表達(dá)式(110)的一個(gè)優(yōu)化，考慮到固定樣本在一次樣本訓(xùn)練中是固定值，所以可以簡(jiǎn)化(112)式，只計(jì)算非固定的部分。對(duì)于第二個(gè)條件，則由選取非固定樣本的過(guò)程可以得到： (112). 。條件1只要在每次樣本訓(xùn)練時(shí)仔細(xì)檢查約束條件集：（，） 其中：是上界，是下界（110式是一個(gè)凸約束問(wèn)題。該算法必須滿足的兩點(diǎn)是：1． 僅當(dāng)細(xì)分到可以找到優(yōu)化了的二次分化方法后才退出。 將當(dāng)前運(yùn)算中的原始問(wèn)題分解為次一級(jí)二次分化（Sub Quadratic Programming），以非固定樣本作為二次分化的輸入樣本集求解。這種分割原始問(wèn)題為固定和非固定兩部分并由此解決二次分化問(wèn)題的算法是符合KT條件的（KuhnTucker Condition），它可以表述為：1 當(dāng)最優(yōu)化問(wèn)題可能引起過(guò)大內(nèi)存消耗等運(yùn)行困難時(shí)。在一次求解最優(yōu)化的過(guò)程中，非固定部分的數(shù)量是遠(yuǎn)遠(yuǎn)小于訓(xùn)練集中樣本總數(shù)的。這樣做的好處是可以把對(duì)內(nèi)存需求的指數(shù)級(jí)變化方式轉(zhuǎn)換為線性變化方式，而新得到的線性變化方式是與訓(xùn)練集中樣本個(gè)數(shù)和支持向量個(gè)數(shù)有關(guān)的。本程序中的細(xì)分最優(yōu)化計(jì)算的方法把最優(yōu)化問(wèn)題分解為固定部分和非固定部分兩部分。所以這里程序中使用的是把大問(wèn)題分解成小問(wèn)題的方法。為了敘述方便，設(shè)數(shù)組則(110)式寫為：. 可以看到，求解最優(yōu)化問(wèn)題時(shí)計(jì)算機(jī)的運(yùn)算效果是與訓(xùn)練集中樣本個(gè)數(shù)有關(guān)的即n條樣本時(shí)數(shù)組Q的大小是，就常用的Reuters21578或20 Newsgroups Data Set而言，其中的樣本數(shù)量都已經(jīng)達(dá)到10000條以上，對(duì)這樣的文本按照支持向量機(jī)方法分類會(huì)導(dǎo)致最優(yōu)化問(wèn)題完全耗費(fèi)內(nèi)存的問(wèn)題。對(duì)支持向量機(jī)分類器的訓(xùn)練過(guò)程是一個(gè)有界的（懲罰參數(shù)C）的二次分化問(wèn)題（A Quadratic Optimization Problem with Bound Constraints），即把支持向量機(jī)的決策函數(shù)變成了求解最優(yōu)化問(wèn)題： (110). (111)其中n為訓(xùn)練集中樣本條數(shù)，是一個(gè)n維的向量，每一個(gè)對(duì)應(yīng)一條樣本。以上介紹的三個(gè)主要功能部分的各個(gè)具體函數(shù)的代碼請(qǐng)參看源程序。該支持向量分類器使用線性核函數(shù)，所以Product()函數(shù)的功能就是求支持向量與測(cè)試集中的樣本的點(diǎn)積，即，其中已經(jīng)由StoreVector()函數(shù)求出，來(lái)自測(cè)試樣本，由Tokenizer()提取。StoreVector()求出的在分類過(guò)程中保持不變。其中和來(lái)自模式文檔，即由ScanModel()函數(shù)提取的支持向量，保存在MODEL model結(jié)構(gòu)體中。計(jì)算并在MODEL 結(jié)構(gòu)體中保存的值。最后與測(cè)試集中已有的分類值進(jìn)行對(duì)比，求出分類正確率。在SvmTest()函數(shù)中首先調(diào)用ReadLine()函數(shù)獲得“”和“”的行數(shù)信息，再利用ScanModel()函數(shù)從模式文本中得到模式參數(shù)，包括向量機(jī)的類型，核的類型，支持向量個(gè)數(shù)，特征向量個(gè)數(shù)，學(xué)習(xí)樣本個(gè)數(shù)，全部的支持向量等，得到的數(shù)據(jù)存儲(chǔ)在MODEL model結(jié)構(gòu)體中。CMainFrame::OnFileTest()指定測(cè)試集，模式文檔和測(cè)試結(jié)果文檔的路徑調(diào)用SvmTest()