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

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

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

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

1 文本特征提取

1.1 文本預(yù)處理

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

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

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

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

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

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

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

1.2 特征處理

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

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

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

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

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

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

2 SVM與KNN方法

2.1 SVM方法

支持向量機(support vector machine，SVM)是在1995年由Cortes和Vapnik首次提出來的一種模式識別分類技術(shù)[29]。SVM是在統(tǒng)計學(xué)習(xí)理論(statistical learning theory，SLT)原理的基礎(chǔ)上發(fā)展起來的機器學(xué)習(xí)算法。SVM方法的重點在于在高維特征空間中能構(gòu)造函數(shù)集VC維盡可能小的最優(yōu)分類面，使得不同類別樣本在這分類面上分類上界最小化，從而保證分類算法的最優(yōu)推廣能力。圖7所示的是SVM方法的分類原理示意圖。SVM在有限訓(xùn)練樣本情況下，在學(xué)習(xí)機復(fù)雜度和學(xué)習(xí)機泛化能力之間找到一個平衡點，從而保證學(xué)習(xí)機的推廣能力[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時的樣本點就是支持向量。因為最優(yōu)化問題解ai的每一個分量都與一個訓(xùn)練點相對應(yīng)，顯然所求得的劃分超平面僅僅與對應(yīng)ai≠0 時的那些訓(xùn)練點 (xi·x)相關(guān)，而跟 ai=0 時的那些訓(xùn)練點沒有任何關(guān)系。相應(yīng)于ai≠0時的訓(xùn)練點(xi·x)里的輸入點xi就是支持向量，通常它們是全體樣本中的很少一部分。得出結(jié)論，最終分類分界面的法向量ω只受支持向量的影響，不受非支持向量訓(xùn)練點的影響。

2)非線性可分

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

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

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

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

2.2 KNN方法

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

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

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

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

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

KNN雖是簡單有效的分類方法，但不能忽略以下兩方面的問題：1)由于KNN需要保留分類過程中的所有相似性計算實例，從而隨著訓(xùn)練集規(guī)模的增多，其計算量也會增加，在處理較大規(guī)模數(shù)據(jù)集分類時方法的時間復(fù)雜度會達到不可接受的程度[33]，這是KNN方法的主要缺點；2) KNN方法分類的準確性可能受到訓(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í)階段。首先運用SVM算法對所有訓(xùn)練樣本進行一次訓(xùn)練獲得每一類別的少量的支持向量(support vectors，SVs)，在測試階段使用最近鄰分類器進行測試并分類測試樣本，即計算出新測試樣本與每個類別SVs平均距離值后對其進行對比分析，該測試樣本與哪一類別SVs平均距離值點離得最近就把它歸為該類別中。分類決策依據(jù)是各類別SVs平均距離值后對其與測試點之間距離的數(shù)值分析，所以簡稱該算法為支持向量與最近鄰方法(the support vector of nearest neighbor，SV-NN)。

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

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

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

while(k＜l)

{ 輸入 xk；

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

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

SV-NN 分類算法：

Start:

{ integer i, j,k,l；

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

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

k=k+1;

}

}

End

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

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

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

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

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

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

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

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

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

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

4 實驗結(jié)果與評價

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

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

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

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

本文在前期研究中搭建的哈薩克文語料集的補充完善以及對其詞干提取程序提取規(guī)則細節(jié)的優(yōu)化改善基礎(chǔ)上實現(xiàn)了本研究哈薩克語文本的預(yù)處理。分類任務(wù)的實現(xiàn)運用了SVM、KNN與本文提出的SV-NN算法，并對3種算法分類精度進行了較全面的對比分析。通過對表2和圖9上的仿真實驗數(shù)字的對比分析，發(fā)現(xiàn)SVM算法優(yōu)于KNN算法，而SV-NN算法優(yōu)于SVM 算法。SV-NN方法F1指標除了教育類和法律類以外在其他類上的F1指標都高于都SVM、KNN對應(yīng)指標。SVM、KNN和SV-NN平均分類精度分別為0.754、0.731和0.778，這說明本文提出算法對所有類別文檔詞的召回率和區(qū)分度較穩(wěn)定。本研究提出的算法模型繼承了SVM算法在有限樣本情況下也能獲得較好分類精度的優(yōu)點，另外，本算法沒有去定義KNN算法的k參數(shù)，也沒有跟所有類所有訓(xùn)練樣本進行距離運算。所以，本研究提出的算法無論從算法復(fù)雜度的分析還是算法收斂速度的分析都是有效的。當(dāng)然，總體精度還是沒有像中、英文等其他語言文本分類精度那么理想，因為涉及很多方面的因素，如研究語料庫語料文檔數(shù)量、每一類文檔本身的質(zhì)量、詞干表里已錄用的詞干數(shù)量和質(zhì)量、詞干提取程序解析規(guī)則的細節(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ǔ)上實現(xiàn)了哈薩克語文本的預(yù)處理。分類任務(wù)的實現(xiàn)上運用了模式識別的3種分類算法，并對3種分類算法分類精度進行了較全面的對比分析。通過仿真實驗客觀數(shù)字的對比分析，說明本文提出算法的優(yōu)越性。本文算法對所有類別文檔詞的召回率和區(qū)分度較穩(wěn)定。本文算法在繼承SVM算法的分類優(yōu)越性基礎(chǔ)上，還有效避免了KNN算法設(shè)置k參數(shù)的麻煩和跟所有訓(xùn)練樣本進行距離計算而帶來的巨大時間復(fù)雜度，進而保證了分類算法的收斂速度。

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