張華鑫　龐建剛

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

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

張華鑫龐建剛

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

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

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

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

1　文本預(yù)處理

1.1中文分詞

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

1.2文本表示

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

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

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

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

2　特征降維

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

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

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

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

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

3　文本分類算法

3.1支持向量機

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

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

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

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

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

引入拉格朗日乘子 αi，根據(jù)Karush－Kuhn－Tucker （KKT）條件 ，上述問題可以轉(zhuǎn)化為在約束條件 （7）下使泛函w（α）最大化，泛函 w（α）的表達式如 （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)計的學(xué)習方法。該算法的基本思想是先把文檔用向量空間表示出來，當對一篇待分類文檔進行分類時，將這篇文檔與訓(xùn)練集中所有文檔進行相似度計算，然后把計算結(jié)果按降序進行排列，選取結(jié)果靠前K篇文檔，最后統(tǒng)計這 K篇文章所屬的類別，將所屬文章最多的類別作為待分類文檔的類別。

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

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

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

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

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

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

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

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

KNN算法的缺點：因為該算法是懶惰的學(xué)習算法，對兩個文本進行相似度計算的時候開銷比較大 ，分類速度不是特別理想。

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

4　文本評估方法

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

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

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

5　實驗結(jié)果與分析

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

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

表1　RRSVM分類結(jié)果

表2　RRKNN分類結(jié)果

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

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

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

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

7　結(jié) 語

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

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

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

［3］張愛麗 ，劉廣利 ，劉長宇 .基于SVM的多類文本分類研究［J］.情報雜志 ，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é)報，2004，18（1）：26－32.

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

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

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

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

［10］趙輝.論文本分類中特征選擇方法［J］.現(xiàn)代情報 ，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.

（本文責任編輯：孫國雷）

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－），男，情報學(xué)碩士研究生，研究方向：數(shù)據(jù)挖掘、競爭情報。

10.3969/j.issn.1008－0821.2015.05.014

TP301.6

A

1008－0821（2015）05－0073－05

2014－12－02

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