基于SVM和KNN的文本分類研究

張華鑫　龐建剛

（西南科技大學(xué)經(jīng)濟(jì)管理學(xué)院 ，四川 綿陽621000）

基于SVM和KNN的文本分類研究

張華鑫龐建剛

（西南科技大學(xué)經(jīng)濟(jì)管理學(xué)院 ，四川 綿陽621000）

本文在詳細(xì)介紹文本自動(dòng)分類流程的基礎(chǔ)上 ，通過實(shí)驗(yàn)對SVM和KNN兩種算法進(jìn)行比較研究，實(shí)驗(yàn)結(jié)果表明 ：SVM算法使用多項(xiàng)式核函數(shù)的分類準(zhǔn)確性高于使用徑向基核函數(shù)的分類準(zhǔn)確性 ，且多項(xiàng)式核函數(shù)的分類準(zhǔn)確性隨著參數(shù)q的增大而提高；SVM采用多項(xiàng)式核函數(shù)進(jìn)行分類的準(zhǔn)確性普遍高于采用KNN的分類準(zhǔn)確性；采用多項(xiàng)式核函數(shù)的SVM和KNN兩種算法對短文本的召回率高于對長文本的召回率。

文本分類 ；KNN；支持向量機(jī) ；核函數(shù)

將文本信息進(jìn)行分類能夠滿足人們在海量數(shù)據(jù)中查找數(shù)據(jù)的需求，但是隨著網(wǎng)絡(luò)技術(shù)的高速發(fā)展與廣泛應(yīng)用，電子文本信息呈級數(shù)增長，用人工方式對文本進(jìn)行分類將是一項(xiàng)繁重的工作，因此需要借助計(jì)算機(jī)對文本進(jìn)行自動(dòng)分類。20世紀(jì)50年代末，H.P.Lunhn首次在該領(lǐng)域提出將詞頻統(tǒng)計(jì)思想用于文本自動(dòng)分類的研究。20世紀(jì)90年代以后，研究者將機(jī)器學(xué)習(xí)算法用于文本自動(dòng)分類，主要的機(jī)器學(xué)習(xí)算法有決策樹 （Decision Tree）、Rocchio算法、KNN算法和支持向量機(jī) （Support Vector Machine，SVM）等。錢慶等［1］將KNN算法應(yīng)用于醫(yī)藥衛(wèi)生體制改革輿情監(jiān)測系統(tǒng)中，構(gòu)建了醫(yī)藥衛(wèi)生體制改革主體模型，利用該模型能夠有效提高醫(yī)藥衛(wèi)生體制改革輿情監(jiān)測系統(tǒng)主題信息自動(dòng)獲取、自動(dòng)分類的效率，但是該模型在進(jìn)行特征加權(quán)的時(shí)候采用的是TF－IDF方法，該方法的缺點(diǎn)在于低估了在一個(gè)類中頻繁出現(xiàn)的詞條，這樣的詞條能夠代表這個(gè)類的文本特征的，應(yīng)該賦予其較高的權(quán)重而不是與其他詞語同等對待。牛強(qiáng)等［2］在Web文本分類中引入KNN算法，利用 χ2統(tǒng)計(jì)量作為特征選擇評分函數(shù)，盡管該方法能夠取得不錯(cuò)的分類效果 ，在一定程度上滿足Web知識的需求，但是該方法在對類別差異不大的類別的識別能力較弱。張愛麗等［3］利用SVM算法構(gòu)造多類別的識別器，該分類器能較好地把大類別分類問題，有效地轉(zhuǎn)化為小類別識別問題的組合 ，降低錯(cuò)誤識別率。上述研究都側(cè)重于單一使用KNN算法或SVM算法 ，沒有對兩種算法進(jìn)行橫向比較 ，本文著重通過實(shí)驗(yàn)比較KNN和SVM兩種算法在中文文本分類中的性能差異。

1　文本預(yù)處理

1.1中文分詞

由于中文句子的詞與詞之間沒有空格，因此在進(jìn)行文本分類的時(shí)候首先需要把句子分割成詞語。現(xiàn)有的中文分詞算法主要分為四大類：基于字符串匹配的分詞方法、基于理解的分詞方法、基于統(tǒng)計(jì)的分詞方法和基于語義的分詞方法。

1.2文本表示

文本信息是非結(jié)構(gòu)化數(shù)據(jù)，因此需要用數(shù)學(xué)模型把文本數(shù)據(jù)表示為計(jì)算機(jī)能夠處理的形式。常用的文本表示模型有布爾邏輯、概率模型 ，向量空間模型。其中向量空間模型是應(yīng)用較多且效果很好的模型。本文采用向量空間模型表示文本。向量空間模型的基本思想是將文本 di映射為空間中的一個(gè)特征向量V（di），V（di）=｛（ti1，wi1），（ti2，wi2），…，（tin，win）｝，其中 tik為文檔di第k個(gè)特征項(xiàng) ，wik為文檔di第k個(gè)特征項(xiàng)對應(yīng)的權(quán)重。本文采用TF－IDF方法作為特征加權(quán)的方法。TF－IDF方法的基本思想是：如果一個(gè)特征在特定的文本中出現(xiàn)的頻率越高，說明它區(qū)分該文本內(nèi)容屬性的能力越強(qiáng)；如果一個(gè)特征在文本中出現(xiàn)的范圍越廣，即該特征等概率出現(xiàn)在各個(gè)類別中，說明該特征區(qū)分內(nèi)容屬性的能力越低。

TF－IDF權(quán)重計(jì)算公式如下：

其中 ，tf（tik）表示特征項(xiàng) tik出現(xiàn)在文檔di中的頻數(shù) ，N為文本總數(shù)，ni為訓(xùn)練集中出現(xiàn)tik的文檔數(shù)。

但是該方法的缺陷在于如果一個(gè)詞條在一個(gè)類的文檔中頻繁出現(xiàn)，則說明該詞條能夠很好代表這個(gè)類的文本的特征，這樣的詞條應(yīng)該給它們賦予較高的權(quán)重，以此區(qū)別與其它類文檔。本研究在計(jì)算特征項(xiàng)的時(shí)候引入條件概率 ，改進(jìn)后TF－IDF公式如下：表示文檔 d中出現(xiàn)特征項(xiàng)tik時(shí)該文檔屬于Ci的概率，從改進(jìn)的公式可以看出如果某一個(gè)類 Ci中包含詞條tik的文檔數(shù)量大，而在其它類中包含詞條 t的文檔數(shù)量小的話，則 tik能夠代表Ci類的特征，該公式賦予該特征較高的權(quán)重。

2　特征降維

一篇文檔進(jìn)行分詞之后，特征項(xiàng)的維數(shù)一般在幾萬維以上，而大多數(shù)的特征項(xiàng)是冗余的或者不相關(guān)的，如何在保持分類準(zhǔn)確率變化不大的前提下降低特征維數(shù)是文本分類研究的一個(gè)重點(diǎn)領(lǐng)域。常用的特征選擇算法包括交互信息、χ2統(tǒng)計(jì)量、文檔頻率、幾率比、信息增益、期望交叉熵等。

信息增益是一種有效的特征算法。Wang Bin等［4］通過實(shí)驗(yàn)比較了幾率比、文檔頻率、信息增益3種特征選擇算法 ，結(jié)果表明信息增益相比前兩種算法能夠提取最優(yōu)特征子集。本文實(shí)驗(yàn)采用信息增益作為特征選擇方法，現(xiàn)將信息增益定義如下：

定義1：信息增益 （IG，Information Gain）是某一特征在文本中出現(xiàn)前后的信息熵之差。計(jì)算公式如下所示：

定義中 i表示類別總數(shù)，P（ci）表示類別 ci在所有文檔中出現(xiàn)的概率，P（T）表示特征 T在文檔中出現(xiàn)的概率，P（ci/T）表示當(dāng)文檔中包含特征 T時(shí)屬于類別ci的概率，P（ˉT）表示文檔中不包含 T時(shí)的概率，P（ci/ˉT）表示文檔中不包含特征 T時(shí)屬于類別ci的概率。

在進(jìn)行特征選擇時(shí)，一般設(shè)置一個(gè)閾值，剔除信息增益 （IG）的值小于閾值的特征項(xiàng)，保留大于閾值的特征值作為特征項(xiàng)。代六玲等［5］通過實(shí)驗(yàn)表明在保持準(zhǔn)確率變化很小的前提下可以保留原始特征空間維數(shù)的10%～20% ，剔除80%～90%的特征項(xiàng)。

3　文本分類算法

3.1支持向量機(jī)

支持向量機(jī) （Support Vector Machine，SVM）是Vapnik 于20世紀(jì)90年代提出一種基于統(tǒng)計(jì)學(xué)習(xí)理論的分類算法。因?yàn)镾VM算法是建立在統(tǒng)計(jì)學(xué)習(xí)理論VC維理論和結(jié)構(gòu)風(fēng)險(xiǎn)最小化原理基礎(chǔ)上的一種新機(jī)器學(xué)習(xí)方法 ，該算法在解決小樣本、非線性和高維模式識別問題中表現(xiàn)出許多特有的優(yōu)勢 ，并在很大程度上克服了 “維數(shù)災(zāi)難”和 “過學(xué)習(xí)”等問題，1998年，Joachims率先將Vapnik提出的支持向量機(jī) （Support Vector Machine，SVM）引入到文本分類中，并取得了不錯(cuò)的效果。對于兩分類情況，SVM的基本思想可以用圖1來說明，空心點(diǎn)和實(shí)心點(diǎn)分別表示不同的類別，H為分割超平面，H1和 H2分別表示各類中離分割超平面最近且平行的平面。H1和 H2上的點(diǎn)被稱作支持向量，H1和 H2之間的間距被稱為分類間隔 （Margin）。最優(yōu)分割超平面就是要求在正確分開不同類別的前提下 ，分類間隔最大 （Margin）。

圖1　RR最優(yōu)分割超平面簡圖

假設(shè)線性分類平面的形式為：

其中 w是分類權(quán)重向量，b是分類閾值。將判別函數(shù)進(jìn)行歸一化處理，使判別函數(shù)對于兩類樣本都滿足，即

其中yi是樣本的類別標(biāo)記，xi是相應(yīng)的樣本。

引入拉格朗日乘子 αi，根據(jù)Karush－Kuhn－Tucker （KKT）條件 ，上述問題可以轉(zhuǎn)化為在約束條件 （7）下使泛函w（α）最大化，泛函 w（α）的表達(dá)式如 （8）所示。

二次規(guī)劃可以求得αi，將αi帶入 （9）求得w

選擇不為零的αi，帶入 （10）中求得 b。

通過推導(dǎo)，決策函數(shù)變?yōu)橐韵率阶?/p>

把測試樣本帶入 （11）中，如果f（x）=1則屬于該類，否則不屬于該類。

3.2KNN算法

KNN算法是Cover和Hart于1968年提出一種基于統(tǒng)計(jì)的學(xué)習(xí)方法。該算法的基本思想是先把文檔用向量空間表示出來，當(dāng)對一篇待分類文檔進(jìn)行分類時(shí)，將這篇文檔與訓(xùn)練集中所有文檔進(jìn)行相似度計(jì)算，然后把計(jì)算結(jié)果按降序進(jìn)行排列，選取結(jié)果靠前K篇文檔，最后統(tǒng)計(jì)這 K篇文章所屬的類別，將所屬文章最多的類別作為待分類文檔的類別。

本文采用夾角余弦計(jì)算文本之間的相似度，KNN算法計(jì)算步驟如下：

（1）在文本分類訓(xùn)練階段，把訓(xùn)練集中的文本用向量空間模型表示為特征向量。

（2）將待分類樣本 di表示成和訓(xùn)練集中文本一致的特征向量。

（3）根據(jù)夾角余弦公式計(jì)算待分類樣本 di和每個(gè)訓(xùn)練集的距離 ，選擇與待分類樣本距離最近的 K個(gè)樣本作為di的K個(gè)最近鄰，余弦夾角公式如下所示：

其中 ，w1i、w2i分別為文檔d1，d2向量中第 i個(gè)特征的權(quán)重值 ，Sim（d1，d2）的值越大說明兩個(gè)文本的相似度程度越高。

（4）統(tǒng)計(jì)每個(gè)類別所屬的文章數(shù)。

（5）將所屬文章最多的類別作為待分類文檔的類別

KNN算法的優(yōu)點(diǎn)：該算法無須知道各個(gè)特征值的分布 ，并且該算法構(gòu)建方法簡單，易于實(shí)現(xiàn)。

KNN算法的缺點(diǎn)：因?yàn)樵撍惴ㄊ菓卸璧膶W(xué)習(xí)算法，對兩個(gè)文本進(jìn)行相似度計(jì)算的時(shí)候開銷比較大 ，分類速度不是特別理想。

總體而言，KNN算法在文本分類領(lǐng)域得到廣泛應(yīng)用，并且KNN算法是目前眾多文本分類算法中分類效果較理想的算法之一。

4　文本評估方法

本文使用準(zhǔn)確率、查全率和綜合考慮準(zhǔn)確率和查全率的綜合分類率F1作為文本分類性能的評價(jià)指標(biāo)［6］。準(zhǔn)確率是指在分類器判定屬于類別 Ci中 ，確實(shí)屬于類別 Ci的文檔數(shù)所占比例，其公式表示如下：

查全率是指分類器正確分類的文本占原本屬于類別 Ci的文檔數(shù)的比例，其公式計(jì)算如下：

準(zhǔn)確率和查全率反映了分類質(zhì)量的兩個(gè)不同指標(biāo)，兩者必須綜合考慮，不可偏廢，因此用綜合分類率F1綜合考慮準(zhǔn)確率和查全率，其計(jì)算公式如下：

5　實(shí)驗(yàn)結(jié)果與分析

本實(shí)驗(yàn)使用Visual Studio 2013作為編程開發(fā)環(huán)境，采用ICTCLAS漢語分詞系統(tǒng)進(jìn)行分詞，隨機(jī)的從復(fù)旦中文語料庫中選取Education、Agriculture、Economy、Politics 4類樣本各120篇，其中60篇作為訓(xùn)練集、60篇作為測試集 ，4個(gè)類別的數(shù)據(jù)大小分別為70.8KB、706KB、825KB、1044KB，采用信息增益作為評分函數(shù)對文本進(jìn)行特征選擇。

SVM核函數(shù)分別采用多項(xiàng)式核函數(shù)和徑向基核函數(shù)，多項(xiàng)式核函數(shù)的形式為K（x，xi）=［（x*xi）+1）］q，多項(xiàng)式核函數(shù)只有一個(gè)參數(shù) q，當(dāng)采用不同的 q時(shí)，文本分類的性能有所波動(dòng) ，另外隨著參數(shù) q的增加，其訓(xùn)練所需的時(shí)間也隨之增加，本實(shí)驗(yàn)多項(xiàng)式的參數(shù) q分別取為2、3、 4；徑向基核函數(shù)的形式為徑向基核函數(shù)中，也只有一個(gè)核參數(shù) σ（在實(shí)驗(yàn)中我們?nèi)〉闹担宜淼氖菑较蚧膶挾?，它反映了函數(shù)圖像的寬度，σ越小，寬度越窄，函數(shù)越具有選擇性，本實(shí)驗(yàn) σ2取0.01、0.09、0.6。SVM分別使用多項(xiàng)式核函數(shù)和徑向基核函數(shù)進(jìn)行分類之后的結(jié)果如表1所示。KNN算法的 K值選擇為8，KNN分類結(jié)果如表2所示。

表1　RRSVM分類結(jié)果

表2　RRKNN分類結(jié)果

由表1可知采用不同的核函數(shù)對于支持向量機(jī)的分類效果影響非常明顯，當(dāng)使用多項(xiàng)式核函數(shù)時(shí)最高的分類準(zhǔn)確率達(dá)到89.83%，最高的召回率達(dá)到91.67%，而采用徑向基函數(shù)時(shí)最高的分類準(zhǔn)確率僅為65.71%，最高的召回率為86.67%，并且可以從表中明顯看出 ，支持向量機(jī)使用徑向基函數(shù)進(jìn)行分類的效果非常不明顯，達(dá)不到人們預(yù)期的效果。因此當(dāng)選擇支持向量機(jī)作為分類算法時(shí)，采用什么樣的核函數(shù)，核函數(shù)選擇什么樣的參數(shù)對于分類至關(guān)重要。

由表1、表2的實(shí)驗(yàn)結(jié)果可見，當(dāng)SVM選擇多項(xiàng)式作為核函數(shù)時(shí)，查全率、準(zhǔn)確率、F1三個(gè)評價(jià)指標(biāo)普遍高于采用傳統(tǒng)KNN分類之后的結(jié)果。

筆者分析可能有以下幾個(gè)原因：（1）支持向量機(jī)算法能夠?qū)?shù)據(jù)映射到高維空間，當(dāng)數(shù)據(jù)映射到高維空間之后 ，就可以對原始空間不能線性分類的樣本進(jìn)行分類，這就降低了樣本被誤分的概率 ；（2）本實(shí)驗(yàn)沒有選擇合適數(shù)量的訓(xùn)練樣本數(shù)量，因?yàn)槿绻?xùn)練樣本過小，在測試階段出現(xiàn)的特征詞將不會出現(xiàn)在訓(xùn)練階段選擇的特征項(xiàng)當(dāng)中 ，但是如果訓(xùn)練樣本過大，將會出現(xiàn) “過學(xué)習(xí)”的現(xiàn)象，因此后期將會對樣本數(shù)量對兩種算法分類性能的影響進(jìn)一步深入研究；（3）越靠近訓(xùn)練樣本的測試樣本應(yīng)該給予較重的權(quán)重 ，但是本實(shí)驗(yàn)采用傳統(tǒng)的KNN算法，該算法給予前K個(gè)最近鄰?fù)瑯拥臋?quán)重 ，因此有必要對前 K個(gè)最近鄰樣本賦予不同的權(quán)重 ，且前 K個(gè)最近鄰樣本的權(quán)重進(jìn)隨著距離的增大單調(diào)遞減。

傳統(tǒng)觀念認(rèn)為小類別的信息量無法與大類別抗衡，其信息容易淹沒在大類別中 ，導(dǎo)致小類別文檔被大量誤分，通過本實(shí)驗(yàn)結(jié)果可以發(fā)現(xiàn)在準(zhǔn)確率相差不大的前提下，采用多項(xiàng)式核函數(shù)的SVM算法和KNN算法對于數(shù)據(jù)量最小的Education（70.8KB）分類的召回率和F1兩個(gè)指標(biāo)均高于對數(shù)據(jù)量最大的Politics（1 044KB）進(jìn)行分類之后的召回率和F1。通過查看訓(xùn)練集和測試集的原始文本，Education類別的文檔長度普遍少于其他3個(gè)類別。很有可能是長文本包含了大量與類別無關(guān)的信息 ，從而導(dǎo)致類別相關(guān)的詞語被無關(guān)信息所淹沒，而在進(jìn)行短文本編輯的時(shí)候，作者會選擇與類別最相關(guān)的詞進(jìn)行寫作，因此在進(jìn)行分類的時(shí)候 ，短文本的分類準(zhǔn)確率高于長文本。

7　結(jié) 語

本文通過對SVM和KNN算法進(jìn)行文本分類性能比較研究，核函數(shù)是影響SVM分類效果的一個(gè)重要因素，當(dāng)SVM選擇多項(xiàng)式作為核函數(shù)時(shí)，分類的準(zhǔn)確度優(yōu)于KNN分類算法，同時(shí)本實(shí)驗(yàn)發(fā)現(xiàn)兩種算法對短文本的分類準(zhǔn)確率均高于對長文本的分類準(zhǔn)確率。針對研究存在的不足，后期準(zhǔn)備在以下3個(gè)方面進(jìn)行改進(jìn)：（1）針對常用的徑向基核函數(shù)和多項(xiàng)式核函數(shù)各自存在的優(yōu)缺點(diǎn)，將二者結(jié)合構(gòu)造新的核函數(shù)，并嘗試構(gòu)建適合文本分類的核函數(shù)；（2）對KNN的算法的前 K個(gè)近鄰賦予不同的權(quán)重；（3）研究如何克服類別樣本數(shù)據(jù)量分布不均勻?qū)Ψ诸悳?zhǔn)確率的影響。

［1］錢慶，安新穎 ，代濤.主體追蹤在醫(yī)藥衛(wèi)生體制改革輿情監(jiān)測系統(tǒng)中的應(yīng)用 ［J］.圖書情報(bào)工作 ，2011，55（16）：46－49.

［2］牛強(qiáng)，王志曉 .基于KNN的Web文本分類的研究 ［J］.計(jì)算機(jī)應(yīng)用與軟件 ，2007，24（10）：210－211.

［3］張愛麗 ，劉廣利 ，劉長宇 .基于SVM的多類文本分類研究［J］.情報(bào)雜志 ，2004，（9）：6－10.

［4］Wang Bin，JonesG JF，Pan Wen Feng.Using online Linear classifier to filter span emails［J］.Pattern Analysis&Application，2006，（9）：339－351.

［5］代六玲，黃河燕，陳肇雄 .中文文本分類中特征抽取方法的比較研究 ［J］.中文信息學(xué)報(bào)，2004，18（1）：26－32.

［6］胡濤，劉懷亮 .中文文本分類中一種基于語義的特征降維方法［J］.現(xiàn)代情報(bào) ，2011，31（11）：46－50.

［7］張小艷，宋麗平.論文本分類中特征選擇方法 ［J］.現(xiàn)代情報(bào) ，2009，29（3）：131－133.

［8］Cortes C，Vapnik V.Support－Vector Networks［J］.Machine Learning，1995，（20）：273－297.

［9］卜凡軍 ，錢雪忠 .基于向量投影的KNN文本分類算法 ［J］.計(jì)算機(jī)工程與設(shè)計(jì) ，2009，30（21）：4939－4941.

［10］趙輝.論文本分類中特征選擇方法［J］.現(xiàn)代情報(bào) ，2013，33（10）：70－74.

［11］Sebastiani F.Machine learning in automated text categorization［J］. ACM Computing Surveys，2002，34（1）：1－47.

［12］侯漢清.分類法的發(fā)展趨勢簡論 ［M］.北京 ：中國人民大學(xué)出版社，1981.

［13］G.Salton.Introduction to Modern Information Retrieval.McGraw－Hill，1983.

（本文責(zé)任編輯：孫國雷）

Research on Text Classification Based on SVM and KNN

Zhang Huaxin Pang Jiangang
（College of Economy and Management，Southwest University of Science and Technoloy，Mianyang 621000，China）

This papermade a comparison between SVM and KNN on text classification after illustrating the procedures in text classification.The experimental results showed that the accuracy of SVM by using Polynomial kernel function is higher than thatby using Radial Basis function，besides，theaccuracy of the former increaseswhen the parameterq getsbigger；theaccuracy of SVM by using Polynomial kernel function isgenerally higher than thatby using KNN；the accuracy of SVM and KNN both have higher recallof short text than long text.

text－classification；KNN；SVM；kernel－function

張華鑫 （1991－），男，情報(bào)學(xué)碩士研究生，研究方向：數(shù)據(jù)挖掘、競爭情報(bào)。

10.3969/j.issn.1008－0821.2015.05.014

TP301.6

A

1008－0821（2015）05－0073－05

2014－12－02

本文系四川省社科基金項(xiàng)目 “產(chǎn)業(yè)技術(shù)創(chuàng)新戰(zhàn)略聯(lián)盟知識共享機(jī)制研究”（批準(zhǔn)號 ：SC13E012）和四川省教育廳項(xiàng)目 “眾包式網(wǎng)絡(luò)社區(qū)大眾協(xié)同創(chuàng)新項(xiàng)目”（批準(zhǔn)號：12SB0258）研究成果之一。