基于支持向量的最近鄰文本分類方法

古麗娜孜·艾力木江，乎西旦·居馬洪，孫鐵利，梁義

文本分類(text classification，TC)是對一個(gè)文檔自動(dòng)分配一組預(yù)定義的類別或應(yīng)用主題的過程[1]。隨著數(shù)字圖書館的快速增長，TC已成為文本數(shù)據(jù)組織與處理的關(guān)鍵技術(shù)。數(shù)字化數(shù)據(jù)有不同的形式，它可以是文字、圖像、空間形式等，其中最常見和應(yīng)用最多的是文本數(shù)據(jù)，閱讀的新聞、社交媒體上的帖子和信息主要以文本形式出現(xiàn)。文本自動(dòng)分類在網(wǎng)站分類[2-3]、自動(dòng)索引[4-5]、電子郵件過濾[6]、垃圾郵件過濾[7-9]、本體匹配[10]、超文本分類[11-12]和情感分析[13-14]等許多信息檢索應(yīng)用中起到了重要的作用。數(shù)字化時(shí)代，在線文本文檔及其類別的數(shù)量越來越巨大，而TC是從數(shù)據(jù)海洋當(dāng)中挖掘出具有參考價(jià)值數(shù)據(jù)的應(yīng)用程序[15-16]。文本挖掘工作是政府工作、科學(xué)研究、辦公業(yè)務(wù)等許多應(yīng)用領(lǐng)域里書面文本的分析過程。樸素貝葉斯、k近鄰、支持向量機(jī)、決策樹、最大熵和神經(jīng)網(wǎng)絡(luò)等基于統(tǒng)計(jì)與監(jiān)督的模式分類算法在文本分類研究中已被廣泛應(yīng)用。提高文本分類效率的算法研究對web數(shù)據(jù)的開發(fā)應(yīng)用具有重要意義。

合理的詞干有助于提高文本分類的性能和效率[17-18]，特別是對于哈薩克語這樣的構(gòu)詞和詞性變化較復(fù)雜語言的文本分類而言，詞干的準(zhǔn)確提取極其重要。從同一個(gè)詞干可以派生出許多單詞，因此通過詞干提取還可以對語料庫規(guī)模進(jìn)行降維。文本文檔數(shù)量的巨大化和包含特征的多樣化，給文本挖掘工作帶來一定的困難。目前，眾多文本分類研究都是基于英文或中文，基于少數(shù)民族語言的文本分類研究相對較少[19]；但是國外對于阿拉伯語的文本分類工作比中國少數(shù)民族語言文本分類工作成熟[20–21]，投入研究的人員也較多。

哈薩克語言屬于阿爾泰語系突厥語族的克普恰克語支，中國境內(nèi)通用的哈薩克文借用了阿拉伯語和部分波斯文字母，而哈薩克斯坦等國家用的哈薩克文是斯拉夫文字。哈薩克文本跟中文不同的一點(diǎn)是哈薩克文文本單詞以空格分開的，這點(diǎn)類似于英文，都需要文本詞干提取過程。由于哈薩克語與英語語法體系不一樣，英文詞干提取規(guī)則還不能直接用到哈薩克語文本分類問題上，要研究適合哈薩克語語法體系的詞干提取規(guī)則之后才能實(shí)現(xiàn)哈薩克語文本的分類工作。哈薩克語具有豐富的形態(tài)和復(fù)雜的拼字法，因此哈薩克語文本分類系統(tǒng)的實(shí)現(xiàn)是有難度的。為了實(shí)現(xiàn)文本分類任務(wù)需要一定規(guī)模的語料庫，語料庫里語料的質(zhì)量直接影響文本分類的精度。到目前為止在哈薩克語中還沒有一個(gè)公認(rèn)的哈薩克文語料庫，當(dāng)然，也有不少人認(rèn)為新疆人民日報(bào)(哈文版)上的文本可以當(dāng)作文本分類語料庫。本文為了保證文本分類語料庫的規(guī)范化和文本分類工作的標(biāo)準(zhǔn)化，經(jīng)過認(rèn)真挑選中文標(biāo)準(zhǔn)語料庫里的部分語料文檔并對其進(jìn)行翻譯和新疆人民日報(bào)上的部分文檔來自行搭建了本研究的語料庫。本文在對前期研究里詞干提取程序詞干解析規(guī)則[22-24]進(jìn)行優(yōu)化改善的基礎(chǔ)上實(shí)現(xiàn)本研究的文本預(yù)處理，提出新的樣本測度指標(biāo)與距離公式，并結(jié)合SVM與KNN分類算法實(shí)現(xiàn)了哈薩克語文本分類。

1 文本特征提取

1.1 文本預(yù)處理

文本預(yù)處理在整個(gè)文本分類工作中扮演著最重要的角色，其處理程度直接影響到文本分類精度。因?yàn)樗菑奈臋n中抽取關(guān)鍵詞集合的過程，而關(guān)鍵詞的單獨(dú)抽取因語言語法規(guī)則的不同而不同，所以這層工作屬于技術(shù)含量較高的基礎(chǔ)性工作，需要設(shè)計(jì)人員熟練掌握語言語法規(guī)則和計(jì)算機(jī)編程能力。目前存在一個(gè)現(xiàn)實(shí)問題，即包括作者在內(nèi)的很多編程人員因研究工作的需要一般從事于中英文文字資料上的研究，所以對母語(哈薩克語)語法規(guī)則的細(xì)節(jié)不精通，對從小開始在漢語授課學(xué)校上學(xué)的編程人員情況則更嚴(yán)重，所以要實(shí)現(xiàn)詞干解析需要向語言學(xué)專家或相關(guān)人員全面請教，這也是影響哈薩克語文本分類工作進(jìn)展的一個(gè)客觀問題。

哈薩克語文字由24個(gè)輔音字母和9個(gè)元音字母的共有33個(gè)字母組成。因?yàn)楣_克語語法形式是在單詞原形前后附加一定附加成分來完成的，所以哈薩克語言屬于黏著語，即跟英文類似一個(gè)哈薩克語單詞對應(yīng)多種鏈接形式，因此對其一定要進(jìn)行詞干提取。

本文前期系列研究工作基本完成了哈薩克語文本詞干提取以及詞性標(biāo)注工作，已完成哈薩克語文本詞干表的構(gòu)建。該詞干表收錄了如圖1所示的由新疆人民出版社出版的《哈薩克語詳解詞典》中的60 000多個(gè)哈薩克語文本詞干和如圖2所示的438個(gè)哈薩克語文本詞干附加成分。

圖1 哈薩克語詞干Fig. 1 Kazakh text stem

圖2 哈薩克語附加成分Fig. 2 Additional components in Kazakh text

本文在前期準(zhǔn)備研究工作的基礎(chǔ)上，給出3種詞性的有限狀態(tài)自動(dòng)機(jī)，并采用詞法分析和雙向全切分相結(jié)合的改進(jìn)方法實(shí)現(xiàn)哈薩克語文本詞干的提取與單詞構(gòu)形附加成分的細(xì)切分。以改進(jìn)的逐字母二分詞典查詢機(jī)制對詞干表進(jìn)行搜索，提高詞干提取的效率。以概率統(tǒng)計(jì)的方法對歧義詞和未記載詞進(jìn)行切分。在此研究基礎(chǔ)上，設(shè)計(jì)實(shí)現(xiàn)了哈薩克語文本的詞法自動(dòng)分析程序，完成哈薩克語文本的讀取預(yù)處理。處理結(jié)果如圖3所示，上半窗體上顯示的是待切分的文檔原文，下半窗體上顯示是詞干切分后的結(jié)果。

圖3 哈薩克語文本詞干切分結(jié)果示例Fig. 3 Example segmentation results of the Kazakh text stem

1.2 特征處理

特征是文本分類時(shí)判別類別的尺度。模式識別的不同分類問題有不同的特征選擇方法，而在文本分類問題中常用到的方法有互信息(MI)、X2統(tǒng)計(jì)量(CHI)、信息增益(IG)、文檔頻率(DF)、卡方統(tǒng)計(jì)等[25]。這些方法各具優(yōu)點(diǎn)和不足之處。MI、IG和CHI傾向于低頻詞的處理，而DF則傾向于高頻詞的處理。目前，也有許多優(yōu)化改進(jìn)方法[26-28]，其中文本頻率比值法(document frequency ratio，DFR)以簡單、快捷等優(yōu)點(diǎn)克服了以上幾種方法存在的問題，綜合考慮了類內(nèi)外文本頻率，其計(jì)算公式為

式中，對于詞t，N是訓(xùn)練文本數(shù)，ni是Ci類別中的文本數(shù)，DFi是Ci類別中包含詞t的文本數(shù)，而顯然是除了Ci類以外的別的類別中包含詞t的文本數(shù)。

通過詞頻統(tǒng)計(jì)、詞權(quán)重計(jì)算和文檔向量化表示等一系列的預(yù)處理工作之后才能運(yùn)用分類算法，所以對文本分類工作而言這些都是非常重要的階段性基礎(chǔ)工作。圖4所示的是每類文檔里(如體育類文檔中)每一個(gè)單詞(如“排球”)的總出現(xiàn)次數(shù)。圖5所示的是詞的權(quán)重計(jì)算結(jié)果，即統(tǒng)計(jì)某詞在判別文檔類別所屬關(guān)系中的隸屬度，當(dāng)然隸屬度越高說明該詞在文檔分類時(shí)的貢獻(xiàn)越大。最后把文檔由如圖6所示的形式向量化表示，生成分類問題的文檔向量，即“X號特征詞：該特征詞的特征向量”形式向量化表示。

圖4 詞頻統(tǒng)計(jì)結(jié)果Fig. 4 Term frequency statistical result

圖5 詞權(quán)重計(jì)算結(jié)果Fig. 5 Term weight computed result

圖6 文本向量文件Fig. 6 Text vector files

2 SVM與KNN方法

2.1 SVM方法

支持向量機(jī)(support vector machine，SVM)是在1995年由Cortes和Vapnik首次提出來的一種模式識別分類技術(shù)[29]。SVM是在統(tǒng)計(jì)學(xué)習(xí)理論(statistical learning theory，SLT)原理的基礎(chǔ)上發(fā)展起來的機(jī)器學(xué)習(xí)算法。SVM方法的重點(diǎn)在于在高維特征空間中能構(gòu)造函數(shù)集VC維盡可能小的最優(yōu)分類面，使得不同類別樣本在這分類面上分類上界最小化，從而保證分類算法的最優(yōu)推廣能力。圖7所示的是SVM方法的分類原理示意圖。SVM在有限訓(xùn)練樣本情況下，在學(xué)習(xí)機(jī)復(fù)雜度和學(xué)習(xí)機(jī)泛化能力之間找到一個(gè)平衡點(diǎn)，從而保證學(xué)習(xí)機(jī)的推廣能力[30]。

圖7 SVM 分類原理示意圖Fig. 7 SVM classification schematic diagram

根據(jù)樣本分布情況與樣本集維數(shù)，SVM算法的判別函數(shù)原理大致可分為線性可分與非線性可分兩種形式。

1)線性可分

帶有以式(2)所示訓(xùn)練樣本集的SVM線性可分分類問題的數(shù)學(xué)模型可通過式(3)來表示：

式中對應(yīng)ai≠0時(shí)的樣本點(diǎn)就是支持向量。因?yàn)樽顑?yōu)化問題解ai的每一個(gè)分量都與一個(gè)訓(xùn)練點(diǎn)相對應(yīng)，顯然所求得的劃分超平面僅僅與對應(yīng)ai≠0 時(shí)的那些訓(xùn)練點(diǎn) (xi·x)相關(guān)，而跟 ai=0 時(shí)的那些訓(xùn)練點(diǎn)沒有任何關(guān)系。相應(yīng)于ai≠0時(shí)的訓(xùn)練點(diǎn)(xi·x)里的輸入點(diǎn)xi就是支持向量，通常它們是全體樣本中的很少一部分。得出結(jié)論，最終分類分界面的法向量ω只受支持向量的影響，不受非支持向量訓(xùn)練點(diǎn)的影響。

2)非線性可分

為此，需要在式(3)中增加一個(gè)松弛變量ξi和懲罰因子C，從而式(3)變?yōu)?/p>

式中：ξi≥ 0；i = 1, 2, ···, n；C 為控制樣本對錯(cuò)分的調(diào)整因子，通常稱為懲罰因子。C越大，懲罰越重。

雖然原理看起來簡單，然而在分類問題的訓(xùn)練樣本不充足或不能保證訓(xùn)練樣本質(zhì)量的情形下確定非線性映射是很困難的，那么如何確定非線性映射呢？SVM通過運(yùn)用核函數(shù)概念解決這個(gè)問題，核函數(shù)是SVM的其他分類算法無法替代的獨(dú)特功能。

SVM通過引入一個(gè)核函數(shù)K(xi·x)，將原低維的分類問題空間映射到高維的新問題空間中，使核函數(shù)代替內(nèi)積運(yùn)算，這個(gè)高維空間就稱為Hilbert空間。引入核函數(shù)以后的最優(yōu)分類函數(shù)為

2.2 KNN方法

KNN(K nearest neighbor)分類法是基于實(shí)例的學(xué)習(xí)算法，它需要所有的訓(xùn)練樣本都參與分類[31]。在分類階段，利用歐氏距離公式，將每個(gè)測試樣本與和它鄰近的k個(gè)訓(xùn)練樣本進(jìn)行比較，然后將測試樣本歸屬到票數(shù)最多的那一類里[32]。KNN算法是根據(jù)測試樣本最近的k個(gè)樣本點(diǎn)的類別信息來對該測試樣本類型進(jìn)行判別，所以k值的選取非常重要。k值若太小，測試樣本特征不能充分體現(xiàn)；k值若太大，與測試樣本并不相似的個(gè)別樣本也可能被包含進(jìn)來，這樣反而對分類不利。KNN算法在分類決策上只憑k個(gè)最鄰近樣本類別確定待分樣本的所屬類。目前，對于k值的選取還沒有一個(gè)全局最優(yōu)的篩選方法，這也是KNN方法的弊端，具體操作時(shí)，根據(jù)先驗(yàn)知識先給出一個(gè)初始值，然后需要根據(jù)仿真分類實(shí)驗(yàn)結(jié)果重新調(diào)整，調(diào)整k值的操作有時(shí)一直到分類結(jié)果滿足用戶需求為止。該方法原理可由式(7)表示：

式(7)表明將測試樣本di劃入到k個(gè)鄰近類別中成員最多的那個(gè)類別里。

在使用KNN算法時(shí)，還可由其他策略生成測試樣本的歸屬類，如式(8)也是被廣泛使用的公式：

當(dāng)x(j∈ci時(shí)，；當(dāng)xjci時(shí)，；是測試樣本di和它最近鄰xj之間的余弦相似度。余弦相似度測量是由一個(gè)向量空間中兩個(gè)向量之間角余弦值來定義的。式(8)說明測試樣本di被歸到k個(gè)最近鄰類里相似性最大那個(gè)類別里。

一般情況下，不同類別訓(xùn)練樣本的分布是不均勻的，同樣不同類別的樣本數(shù)量也可能不一樣。所以，在分類任務(wù)中，KNN中k參數(shù)的一個(gè)固定值可能會(huì)導(dǎo)致不同類別之間的偏差。例如，對于式(7)，一個(gè)較大的k值使得方法運(yùn)行結(jié)果過擬合，反過來一個(gè)較小的k值使得方法模型性能不穩(wěn)定。實(shí)際上，k的值通常由交叉驗(yàn)證技術(shù)來獲取。然而，像在線分類等情況，就不能用交叉驗(yàn)證技術(shù)，只能給出經(jīng)驗(yàn)值，因此k值的選定很重要。

KNN雖是簡單有效的分類方法，但不能忽略以下兩方面的問題：1)由于KNN需要保留分類過程中的所有相似性計(jì)算實(shí)例，從而隨著訓(xùn)練集規(guī)模的增多，其計(jì)算量也會(huì)增加，在處理較大規(guī)模數(shù)據(jù)集分類時(shí)方法的時(shí)間復(fù)雜度會(huì)達(dá)到不可接受的程度[33]，這是KNN方法的主要缺點(diǎn)；2) KNN方法分類的準(zhǔn)確性可能受到訓(xùn)練數(shù)據(jù)集中特性的無關(guān)性和噪聲數(shù)據(jù)的影響，若考慮這些因素其分類效果也許更好。

3 基于SV-NN的哈薩克語文本分類算法

本文提出一種組合分類方法，把SVM算法當(dāng)作KNN算法的訓(xùn)練階段，這樣可以避免k參數(shù)的選擇。組合分類方法結(jié)合了SVM算法的訓(xùn)練和KNN算法的學(xué)習(xí)階段。首先運(yùn)用SVM算法對所有訓(xùn)練樣本進(jìn)行一次訓(xùn)練獲得每一類別的少量的支持向量(support vectors，SVs)，在測試階段使用最近鄰分類器進(jìn)行測試并分類測試樣本，即計(jì)算出新測試樣本與每個(gè)類別SVs平均距離值后對其進(jìn)行對比分析，該測試樣本與哪一類別SVs平均距離值點(diǎn)離得最近就把它歸為該類別中。分類決策依據(jù)是各類別SVs平均距離值后對其與測試點(diǎn)之間距離的數(shù)值分析，所以簡稱該算法為支持向量與最近鄰方法(the support vector of nearest neighbor，SV-NN)。

3.1 SV-NN算法描述及流程圖

假設(shè)共有n個(gè)類別，每個(gè)類別含有m個(gè)支持向量。

SVM: T1→svij；//通過使用 SVM 定義每個(gè)類別的支持向量。

while(k＜l)

{ 輸入 xk；

利用式(9)計(jì)算xk與svij之間的距離(Dk)；

利用式(10)計(jì)算xk與svij之間的平均距離(averDk)；

SV-NN 分類算法：

Start:

{ integer i, j,k,l；

利用式(11)計(jì)算xk與svij之間最小平均距離

將xk劃入到基于的最近類別；

k=k+1;

}

}

End

SV-NN分類方法的工作流程如圖8所示。

3.2 SV-NN 算法實(shí)現(xiàn)

1)將所有訓(xùn)練點(diǎn)映射到向量空間，并通過傳統(tǒng)SVM確定每一個(gè)類別的支持向量。

式中：支持向量svij是從輸入文檔中提取的(共有n個(gè)類，每個(gè)類別含有m個(gè)支持向量)。確定每一類的支持向量之后，其余的訓(xùn)練點(diǎn)可以消除。

2)使用歐氏距離公式(9)計(jì)算測試樣本xk與由1)生成的每一類支持向量svij之間的距離。

圖8 SV-NN分類方法工作原理Fig. 8 SV-NN classification approach working principle diagram

3)使用式(10)計(jì)算測試樣本xk與每一類支持向量svij之間的平均距離：

4）計(jì)算最短平均距離minD，并將測試樣本xk劃入到最短平均距離對應(yīng)的那一類中。

即輸入點(diǎn)被確認(rèn)為與svij之間最短平均距離值對應(yīng)的正確類。

重復(fù)步驟2)～4)，直到所有的測試樣本分類完為止。

4 實(shí)驗(yàn)結(jié)果與評價(jià)

通常，語料庫里語料的質(zhì)量與數(shù)量直接影響文本分類算法的分類性能。中、英文等其他語言文本分類研究都有標(biāo)準(zhǔn)的語料庫，而哈薩克語文本分類工作卻還沒有一個(gè)公認(rèn)的標(biāo)準(zhǔn)語料庫。本文考慮到文本分類工作的規(guī)范性和語料的標(biāo)準(zhǔn)性，由中文標(biāo)準(zhǔn)語料部分文檔的翻譯和挑選新疆日報(bào)(哈文版)上的部分文檔來搭建了本研究的語料庫。在前期研究里，同樣是通過翻譯收集語料集的，只是其規(guī)模小了點(diǎn)，本文的語料工作算是對前期研究語料集的補(bǔ)充和優(yōu)化完善。前期研究語料集語料文檔只有5類文檔，本文擴(kuò)充到8類文檔。通過跟語言學(xué)專家們的多次溝通，選擇具有代表性的文檔，同時(shí)對詞干提取程序解析規(guī)則也作了適當(dāng)?shù)恼{(diào)整。雖然本文所構(gòu)建的語料庫還不能稱得上“標(biāo)準(zhǔn)”詞語，但對現(xiàn)階段哈薩克語文本分類任務(wù)的完成具有實(shí)際應(yīng)用價(jià)值。

本文把語料集規(guī)模擴(kuò)大到由計(jì)算機(jī)、經(jīng)濟(jì)、教育、法律、醫(yī)學(xué)、政治、交通、體育等8類共1 400個(gè)哈薩克語文檔組成的小型語料集，如表1所示。數(shù)據(jù)集被分為兩個(gè)部分。880個(gè)文檔(63%)用于訓(xùn)練，520個(gè)文檔用于測試(37%)。

表1 數(shù)據(jù)集Table 1 Data set

本文文本分類實(shí)驗(yàn)評價(jià)指標(biāo)采用了召回率、精度和F1這3種評價(jià)方法。精度評價(jià)是指比較實(shí)際文本數(shù)據(jù)與分類結(jié)果，以確定文本分類過程的準(zhǔn)確程度，是文本分類結(jié)果是否可信的一種度量。高精度意味著一個(gè)算法返回更相關(guān)的結(jié)果，高召回率代表著一個(gè)算法返回最相關(guān)的結(jié)果，所以文本分類工作期望獲得較高的精度和召回率。

本文在前期研究中搭建的哈薩克文語料集的補(bǔ)充完善以及對其詞干提取程序提取規(guī)則細(xì)節(jié)的優(yōu)化改善基礎(chǔ)上實(shí)現(xiàn)了本研究哈薩克語文本的預(yù)處理。分類任務(wù)的實(shí)現(xiàn)運(yùn)用了SVM、KNN與本文提出的SV-NN算法，并對3種算法分類精度進(jìn)行了較全面的對比分析。通過對表2和圖9上的仿真實(shí)驗(yàn)數(shù)字的對比分析，發(fā)現(xiàn)SVM算法優(yōu)于KNN算法，而SV-NN算法優(yōu)于SVM 算法。SV-NN方法F1指標(biāo)除了教育類和法律類以外在其他類上的F1指標(biāo)都高于都SVM、KNN對應(yīng)指標(biāo)。SVM、KNN和SV-NN平均分類精度分別為0.754、0.731和0.778，這說明本文提出算法對所有類別文檔詞的召回率和區(qū)分度較穩(wěn)定。本研究提出的算法模型繼承了SVM算法在有限樣本情況下也能獲得較好分類精度的優(yōu)點(diǎn)，另外，本算法沒有去定義KNN算法的k參數(shù)，也沒有跟所有類所有訓(xùn)練樣本進(jìn)行距離運(yùn)算。所以，本研究提出的算法無論從算法復(fù)雜度的分析還是算法收斂速度的分析都是有效的。當(dāng)然，總體精度還是沒有像中、英文等其他語言文本分類精度那么理想，因?yàn)樯婕昂芏喾矫娴囊蛩?，如研究語料庫語料文檔數(shù)量、每一類文檔本身的質(zhì)量、詞干表里已錄用的詞干數(shù)量和質(zhì)量、詞干提取程序解析規(guī)則的細(xì)節(jié)等，但目前所獲得的分類精度比前期系列研究成果理想，本算法的文本分類性能有了很大的提升也較好地提高了召回率。

表2 SVM、KNN、SV-NN的分類精度對比Table 2 SVM KNN and SV–NN comparison of classification accuracy

圖9 分類精度的對比分析（每一類別均含175篇文檔）Fig. 9 Comparative analysis of classification accuracy (each category contains 175 documents)

5 結(jié)束語

本文在前期系列研究中所搭建的哈薩克文語料集和詞干提取程序的優(yōu)化完善基礎(chǔ)上實(shí)現(xiàn)了哈薩克語文本的預(yù)處理。分類任務(wù)的實(shí)現(xiàn)上運(yùn)用了模式識別的3種分類算法，并對3種分類算法分類精度進(jìn)行了較全面的對比分析。通過仿真實(shí)驗(yàn)客觀數(shù)字的對比分析，說明本文提出算法的優(yōu)越性。本文算法對所有類別文檔詞的召回率和區(qū)分度較穩(wěn)定。本文算法在繼承SVM算法的分類優(yōu)越性基礎(chǔ)上，還有效避免了KNN算法設(shè)置k參數(shù)的麻煩和跟所有訓(xùn)練樣本進(jìn)行距離計(jì)算而帶來的巨大時(shí)間復(fù)雜度，進(jìn)而保證了分類算法的收斂速度。

本研究仍有許多待優(yōu)化完善的問題，本文接下來的研究工作中將系統(tǒng)地研究并解決影響文本分類精度的階段性問題，獲得滿意的分類精度。