古麗娜孜，孫鐵利，胡西旦，伊力亞爾，庫瓦特拜克

（1.伊犁師范學(xué)院電子與信息工程學(xué)院，新疆伊寧835000；2.東北師范大學(xué)計算機與信息科學(xué)學(xué)院，吉林長春130117）

一種基于改進KNN的哈薩克語文本分類

古麗娜孜1，2，孫鐵利2，胡西旦1，伊力亞爾1，庫瓦特拜克1

（1.伊犁師范學(xué)院電子與信息工程學(xué)院，新疆伊寧835000；2.東北師范大學(xué)計算機與信息科學(xué)學(xué)院，吉林長春130117）

將文本分類理論應(yīng)用于哈薩克語中，給出了哈薩克語文本預(yù)處理過程.介紹一種改進的KNN算法，并結(jié)合自己構(gòu)建的哈薩克語料集實現(xiàn)基于改進KNN算法的哈薩克語的文本分類.仿真實驗數(shù)據(jù)表明，該方法在哈薩克語的文本分類上獲得了較好的效果.

哈薩克語本分類；詞干提取；向量空間模型；相似度；KNN

0 引言

文本分類（Text Categorization）是一項基本的數(shù)據(jù)挖掘技術(shù)，是依照實現(xiàn)定義好的特定類別，為語料集中的每篇文檔確定一個所屬類.在文檔的組織和管理、搜索引擎對網(wǎng)頁的排序、數(shù)字圖書館、郵件的過濾、文本過濾、信息安全保密、自動文摘、分類新聞組等領(lǐng)域里文本分類發(fā)揮著重要的作用.

在文本自動分類技術(shù)方面，不同文種存在許多共性，但由于各語言語法結(jié)構(gòu)之間的差異，使得基于其他語言文本分類的研究成果，不能簡單地用于哈薩克文文本的分類問題上，絕大部分技術(shù)的工作原理只能作為參考，因此需要研究出適用于哈薩克語自己的文本分類理論體系.針對哈薩克語語法體系及其文本信息的獨有特性需要研究出適合哈薩克語文本的分類模型和方法，實現(xiàn)哈薩克語信息的智能挖掘.該研究對促進地區(qū)哈薩克族的科研、文化教育、宣傳出版等工作具有重要的意義和實際應(yīng)用價值.將文本分類理論運用到哈薩克語文本分類工作是我們開創(chuàng)性的特色研究.

目前文本分類算法主要有支持向量機（SVM）、盡近鄰算法（KNN）、Naive Bayes算法等.在文本表示方法中向量空間模型（VSM）的文本表示格式較直觀，所以大部分包括以上幾類文本分類方法一般都利用VSM來表示文本.當(dāng)直接應(yīng)用這些傳統(tǒng)分類方法來解決問題時一般都會存在缺點，因此大多數(shù)領(lǐng)域一般采取改進方法或者混合方法來達到最終目標(biāo).比如，KNN方法就是一種無參、簡單、穩(wěn)定性較高的方法.但是，KNN算法設(shè)計原理本身就簡單，在具體應(yīng)用時往往露出其懶性缺點.為了提高KNN方法效率，王煜、李楊、李榮陸等人對KNN方法進行更深入地研究，并提出快速KNN算法、索引表快速方法和基于密度的修剪方法等一系列的改進方法，并取得了較好的分類效果.本文提出通過減少樣本間相似度的計算量來解決KNN分類方法的巨大搜索空間困難的一種改進KNN方法.［1－11］

1 文本預(yù)處理

文本分類工作當(dāng)中首先對文本進行預(yù)處理，也就是讓計算機來表示出文本，之后才能對其進行特征抽取.

文本預(yù)處理主要是從文本中提取關(guān)鍵詞來表示文本的處理過程.在預(yù)處理過程中，首先要將連續(xù)的語句分隔為分散的有獨立意義的詞集，然后去除集合中的停用詞，獲得文本的關(guān)鍵詞集合.

當(dāng)然，在書寫語法格式不同的語言文本中提取獨立意義的關(guān)鍵詞時，很顯然要采取不同的切分、組合的提取技術(shù).例如，英文文本需要提取詞干、中文文本需要切分詞等.鑒于哈薩克文文本信息的特性，即哈薩克文文本中詞與詞之間已經(jīng)是以空格分開的，所以我們不需要對其進行切分詞，但需對其進行提取詞干.

首先解決以下幾個重要問題：（1）由于各種語言語法體系結(jié)構(gòu)的不同，就不能簡單地套用以其他語言為背景建立的（如，英文，維文，蒙文等）文本詞干提取算法.我們必先研究實現(xiàn)適合哈薩克文語法體系的詞干提取算法.（2）為實現(xiàn)文本分類任務(wù)還需要一定規(guī)模的語料庫，但在哈薩克語言中到目前為止還沒有一個公認的哈文語料庫，必需先建設(shè)構(gòu)建一定量的語料集，為分類算法提供數(shù)據(jù)平臺.

文本預(yù)處理是影響文本分類準(zhǔn)確度的關(guān)鍵因素之一，只有解決了上述2個問題，才能標(biāo)注樣本，之后選擇最合適的文本分類算法實現(xiàn)分類任務(wù).由于篇幅問題下面對這兩環(huán)節(jié)只進行簡要介紹.

1.1 哈文預(yù)處理

哈薩克語的單詞都是通過單詞原形的后面或前面加附加成分構(gòu)成的，這就說明哈薩克語是一種典型的黏著語.因為這個特點，可以讓一個哈薩克語單詞對應(yīng)多個字符串形式.例如，哈薩克語中詞根（月亮），在其后加等各種附加成分后，可以演變出等多詞.但是，任何一種詞典規(guī)模都是有限的，不可能收錄所有的語法演變形式.所以，在哈薩克語預(yù)處理工作時，要找出單詞原形即詞干與相應(yīng)的多個字符串之間的連接對應(yīng)關(guān)系，也就是要找出文本中詞的原形.這就是哈薩克語詞的詞干提取過程.

哈薩克語分詞中，有些構(gòu)形附加成分單獨還可以表示一定的意義，所以除了詞干提取以外有時對構(gòu)形附加成分還要進行細切分，否則不能準(zhǔn)確領(lǐng)會整個單詞的含義，例如，詞“”中的“”就是一種附加成分，其含義是“山”的意思，而整詞“”是“火山”的意思；詞“”中的“”就是一種附加成分，其含義是“馬”的意思，而整詞“”是“平安”的意思.因此，對于哈薩克語詞干提取方法的研究應(yīng)和其構(gòu)形語素的分析同時進行.與此同時還需考慮原詞干連接處的邊界字母有時會發(fā)生一些變化的情形，即根據(jù)哈薩克語語法規(guī)則，在有些詞干后面連接需要的附加成分時，原詞干的連接處邊界字母會發(fā)生一些變化，如，；；；等，因而，在詞干表中找不到完全匹配的這些詞干，根據(jù)語法規(guī)則像這樣典型的情況還得加以分析并解決.在附加成分的切分和詞干提取過程中，出現(xiàn)歧義詞切分情況又是必然現(xiàn)象，所以本文算法同樣考慮到可能出現(xiàn)的幾種歧義詞現(xiàn)象并給出針對處理方法.

哈薩克語中除了少數(shù)從外來語引進的詞前綴以外，絕大部分單詞都是通過在原詞干的后面按一定規(guī)律連接各種詞綴構(gòu)成的.哈薩克語中的構(gòu)形附加成分之間也有嚴(yán)格的連接規(guī)則，這有助于對詞附加成分進行正確切分.名詞、動詞、形容詞、數(shù)詞、代詞和副詞中，名詞和動詞是哈薩克語中數(shù)量最多的詞類，由此，可以引用有限狀態(tài)轉(zhuǎn)錄機（Finite State Machine，F(xiàn)SM）來較方便地為哈薩克語單詞建立詞干模型.

本文在詞性有限狀態(tài)自動機的基礎(chǔ)上利用雙向全切分和詞法分析相結(jié)合的改進方法來實現(xiàn)了哈薩克語的詞干提取和構(gòu)形附加成分的細切分.通過采用改進逐字母二分詞典查詢方法來搜索詞干表，提高詞干提取效率.在上述研究工作的基礎(chǔ)上，實現(xiàn)哈薩克語單詞的詞干提取，解決了哈薩克語文本的讀取預(yù)處理問題.程序運行結(jié)果如圖1所示，圖1中很容易看到原詞及其切分后的詞干.

本文研究對詞干切分所做實驗的評測標(biāo)準(zhǔn)主要以附加成分切分的正確率（Precision1）和歧義詞切分排除率（Precision2）兩方面來進行定性評價的.這2種評估指標(biāo)分別為：

圖1 哈文詞干切分結(jié)果示例

詞干提取正確率

歧義詞切分正確率

表1為本文詞干提取所做實驗結(jié)果數(shù)據(jù)綜合分析表.

表1 詞干提取實驗結(jié)果綜合分析

根據(jù)表1中的實驗結(jié)果，我們可以得知本文提出的算法和處理方法具有較好的結(jié)果，達到了預(yù)期的研究目標(biāo).

當(dāng)然，這一算法依賴于原始詞典（詞庫），詞典的內(nèi)容直接影響切分正確率.比如，由于有些新詞匯（流行詞）還未錄入到詞典里，詞典詞匯較舊，就會直接影響切分效果.因此，詞典的建立與維護非常重要.因模型參數(shù)的訓(xùn)練不足，歧義詞切分概率尚不理想，在今后的研究工作中，有待提高模型參數(shù)的可信度.

為了達到如圖1所示的實驗?zāi)繕?biāo)結(jié)果，我們還做出了以下2項主要的基礎(chǔ)性準(zhǔn)備工作.

（1）以哈薩克語文本分類為主題.沿著實現(xiàn)哈薩克語詞干提取任務(wù)要求先籌備了對應(yīng)詞干表和附加成分表，而這表里已收錄了由新疆人民出版社出版的《哈薩克語詳解詞典》中的6萬多個哈薩克語詞干和438個哈薩克語附加成分.附加成分的詳細分類在附加成分切分階段進行詞法分析時非常有用.哈薩克語語法體系規(guī)定將附加成分分為構(gòu)形附加成分和構(gòu)詞附加成分兩大類.其構(gòu)詞附加成分分為動詞、形容詞、數(shù)詞和副詞附加成分等4種，而構(gòu)形附加成分分為謂語性人稱、格附加成分、領(lǐng)屬性人稱附加成分、復(fù)數(shù)附加成分等4種.

（2）關(guān)鍵環(huán)節(jié)是哈薩克語料庫的建設(shè).實現(xiàn)任何分類任務(wù)首先應(yīng)具備一定規(guī)模的語料庫，考慮到目前還沒有一個公認的哈薩克語料庫，為此本人通過翻譯中文公認語料庫里的部分文章內(nèi)容來構(gòu)建由交通、體育、農(nóng)業(yè)、藝術(shù)、政治等5類共200篇文本組成的本文研究的語料集.這一些列研究不論從理論角度還是從應(yīng)用角度都是非常重要的，在實際應(yīng)用中具有重要意義.

1.2 文本模型

為了讓計算機能夠直接處理文本，首先要將文本由大量字符構(gòu)成的字符串形式表示出來.向量空間模型是將文本由特征項和特征項權(quán)重組成的向量（W1，W2，…，Wm）形式表示出來的最經(jīng)典的文本形式化表示方法，其中Wi為第i個特征項的權(quán)重.一般運用以下TF－IDF公式［1］來計算特征權(quán)重.

其中：W（t，dˉ）為詞t在文本dˉ中的權(quán)重；tf（t，dˉ）為詞t在文本dˉ中的詞頻；ni為訓(xùn)練文本集中出現(xiàn)t的文本數(shù)；n為訓(xùn)練文本總數(shù).

通過以上處理和計算，文檔集可由m行n列的詞－文檔矩陣（Term－Document Matrix）表示出來：

式中：m為文檔集中所有不同詞的個數(shù)；aij為第i個詞在第j個文檔中出現(xiàn)的權(quán)重.不同的詞對應(yīng)矩陣A的不同的一行，每個文檔則對應(yīng)矩陣A的一列.

2 基于改進的KNN分類算法

2.1 KNN算法

KNN算法是一種簡單、有效、無參數(shù)的監(jiān)督分類算法.KNN算法不需要特殊的數(shù)據(jù)來描述規(guī)則，其規(guī)則本身就是數(shù)據(jù)樣本.算法原理就是根據(jù)待分類樣本的k個最近鄰樣本來預(yù)測未知樣本的類別.所以要使用KNN算法，必須明確最近鄰樣本的數(shù)目k和測量相似性的距離函數(shù)這2個基本因素.常用的有曼哈頓距離、歐氏距離等.關(guān)于計算文本相似度，一般都采用余弦公式，公式為：

其中Sim（di，dj）是文本di與dj之間的相似度，而wi，k是文本di中第k個特征的權(quán)重.

在具體分類時，先將待分類文本轉(zhuǎn)換成與訓(xùn)練樣本一致的向量空間模型；然后由公式（5）計算該文本與每個樣本之間的相似度；再取相似度最大的k個樣本，根據(jù)k個樣本由公式（6）來計算屬于每個類別的權(quán)重；最后將該文本歸屬到權(quán)重最大的那個類別中.

其中Sim（di，d）表示文本d與其k個最近文本di之間的相似度.

由以上公式可知，KNN算法先計算待測試文本與訓(xùn)練文本之間在該坐標(biāo)系中的Cosine距離，然后才依據(jù)測試文檔與訓(xùn)練文檔距離的遠近來確定類別，這就說明KNN算法的實質(zhì)就是以特征屬性權(quán)值作為特征空間的坐標(biāo)系測度，由此不難給出分類問題的數(shù)學(xué)模型.

KNN分類過程的數(shù)學(xué)描述：

定義判別函數(shù)為

分類的決策規(guī)則：

如果

則決策x∈Ci.其中：x為得分類文檔；n為總的類別數(shù)目；k為訓(xùn)練集中與x距離最近的文檔數(shù)（k≥1）；

Ci為訓(xùn)練集中類別；ki為屬于Ci類的文檔數(shù).

2.2 改進的KNN算法

傳統(tǒng)的KNN分類算法要求計算要測試的樣本與其他所有訓(xùn)練樣本之間的相似度，因此，要處理大規(guī)模數(shù)據(jù)，算法時效受影響［9－10］.本文提出了一種改進的KNN分類算法.該算法主要思想：最快速度找到n0個候選類別，然后將KNN算法應(yīng)用到這個由n0個候選類別為中心的新的數(shù)據(jù)區(qū)域里，這樣KNN算法的分類花的時間將會大大縮短.算法具體內(nèi)容可以下三大階段來描述.

初始化：總的類別數(shù)目n；n0＝0.

第一階段 基礎(chǔ)工作——計算算法指標(biāo)

step1：將每個類別的訓(xùn)練文本都表示成向量空間模型（即都以向量形式表示出來），分別求出各類別的均值向量，當(dāng)做各個類別各自的中心向量Ci；

step2：求出訓(xùn)練文本與該類中心向量Ci的最小相似度Minsim，定為一個未知樣本是否屬于該類的閾值；

step3：求出該類訓(xùn)練文本與該類中心向量Ci的平均相似度Avesim，當(dāng)做KNN分類選取代表樣本的參考依據(jù).

第二階段 劃出中心數(shù)據(jù)區(qū)域——快速得到文本x的n0個候選類別，其余的類別將不再考慮.

step4：取一個測試樣本x，計算該測試樣本與每個類別中心向量Ci之間的相似度Sim（x，Ci）；

step5：若Sim（x，Ci）≥Minsim，則認為Ci對應(yīng)的類可當(dāng)做候選類別，否則放棄該類并不再對該類進行處理；回到step4一直掃完所有測試樣本為止.

第三階段 KNN分類——完成n0個類別中的最后文本所屬類別.

改進算法優(yōu)點：經(jīng)過第二階段的處理，將會排除n－n0個類別，這樣測試樣本x就只能屬于n0個（n0≤n）個候選類別中一種，其目的就是快速排出明顯不是x所屬類別的那些訓(xùn)練樣本，減輕KNN的負擔(dān).

3 實驗結(jié)果及分析

文本分類工作中訓(xùn)練文本的質(zhì)量直接影響分類器性能，因此選擇訓(xùn)練文本是關(guān)鍵.KNN訓(xùn)練文本過程見圖1.訓(xùn)練文本集合大多都是公認的、經(jīng)人工分類的標(biāo)準(zhǔn)語料庫.但是，對于哈薩克語文本來說，到目前為止還沒有一個標(biāo)準(zhǔn)的語料庫，因此為了實現(xiàn)文本分類任務(wù)，首先要做好哈薩克語語料的建設(shè)工作.考慮到語料集的魯棒性，通過人工翻譯公認中文語料庫里部分文章來收集了本研究的語料集.所構(gòu)建的語料集由交通、體育、農(nóng)業(yè)、藝術(shù)、政治等5個類別的共200篇文本構(gòu)成，其中給每個類分別準(zhǔn)備了40篇文本.任意選取的120篇文本作為訓(xùn)練集，剩下80篇文本作為測試集.

對文本分類效果進行評估，其標(biāo)準(zhǔn)有查準(zhǔn)率、查全率：

圖2 KNN訓(xùn)練文本過程示例

這2個指標(biāo)能夠反映分類質(zhì)量的2個不同的方面，因此通過綜合考察這2項指標(biāo)可得一個新的評估指標(biāo)F1測試值，實驗結(jié)果如表2所示.

表2 綜合考察查準(zhǔn)率與查全率的實驗結(jié)果

實驗的總體效果比起性能較好的分類軟件來說有一定的差距.但本文研究以此效果來說明哈薩克文文本分類問題的可行性比成熟的其他文本分類技術(shù)和所達到的精度而言，還需迎接一系列挑戰(zhàn).改進算法在時效上也不是很理想，算法似乎以前期準(zhǔn)備階段所耗的時間代價來換來了較短的KNN分類時間，因而整體算法運轉(zhuǎn)時間還是較長.除此之外影響算法精度的還有以下幾方面的問題：（1）對哈語單詞的切分處理，提取詞干的準(zhǔn)確度同樣直接影響分類效果.由于被提出的哈薩克語詞干提取規(guī)則還不夠細致，文本內(nèi)容的表示受到影響，從而導(dǎo)致特征選擇的誤差.（2）由于自制語料的質(zhì)量和數(shù)量都不如已公認的標(biāo)準(zhǔn)語料集，會直接影響文本的最終分類.后續(xù)工作中有待增加文本數(shù)量，提高類別代表性.（3）所提出算法在劃出中心文本區(qū)域時，避免不了類別邊界處樣本的誤分、漏分或具有潛在特征樣本的誤分現(xiàn)象，而影響算法整體效率.

4 結(jié)論

本文介紹了一種基于改進KNN的哈薩克文文本分類的總體過程.在通過人工翻譯收集的哈薩克文語料集的基礎(chǔ)上編寫程序?qū)崿F(xiàn)了哈薩克文詞干解析提取，解決了哈薩克文文章的讀取預(yù)處理.用向量空間模型VSM來表示文本，基于改進KNN算法的基礎(chǔ)上最終實現(xiàn)了哈薩克文文本分類任務(wù)，但仍有一些地方需要完善，無論是哈薩克文詞干提取、語料集質(zhì)量，還是算法本身從性能、執(zhí)行效果上都有待于提高，在未來還需要進一步研究.

［1］ 冷明偉，陳曉云，譚國律.基于小樣本集弱學(xué)習(xí)規(guī)則的KNN分類算法［J］.計算機應(yīng)用研究，2011，28（3）：915－917.

［2］ GUO G，WANG H，BELL D.KNN model based approach in classification［C］.Berlin：Springer Verlag，2003：986－996.

［3］ GUO GONGDE，HUANG JIE，CHEN LIFEI.KNN model based incremental learning algorithim［J］.Pattern Recognition Artificial Intelligence，2010，23（5）：70l－707.

［4］ 王煜，白石，王正歐.用于Web文本分類的快速KNN算法［J］.情報學(xué)報，2007，26（1）：60－64.

［5］ 李揚，曾海泉，劉慶華，等.基于KNN的快速Web文檔分類［J］.小型微型計算機系統(tǒng)，2004，25（4）：725－729.

［6］ 李榮陸，胡運發(fā).基于密度的KNN文本分類器訓(xùn)練樣本裁剪方法［J］.計算機研究與發(fā)展，2004，41（4）：539－544.

［7］ ZHANG BIN，SRIHARI S N.Fast k－nearest neighbor classification using cluster－based trees［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2004，26（4）：525－528.

［8］ GHOSH A K，CHAUDHURI P，MURTHY C A.Multiscale classification using nearest neighbor density estimates［J］.IEEE Transactions on Systems，2006，36（5）：1139－1148.

［9］ 宋玲，馬軍，連莉，等.文檔相似度綜合計算研究［J］.計算機工程與應(yīng)用，2006，42（30）：160－163.

［10］ 周靖，劉晉勝.基于分類貢獻有效值的增量刪N模型修剪研究［J］.計算機工程與應(yīng)用，2012，48（3）：185－189.

［11］ 黃杰，郭躬得，陳黎飛.增量KNN模型的修剪策略研究［J］.小型微型計算機系統(tǒng)，2011，5（5）：845－849.

Textcategorization of Kazakh text based on improved KNN

Gulnaz1，2，SUN Tie－li2，Hurxida1，Yiliyar1，Kuwatbek1
（1.School of Electronics and Information Engineering，Yili Normal College，Yining 835000，China；2.School of Computer and Information Science，Northeast Normal University，Changchun 1300117，China）

Appling the theory of text categorization to the study of kazakh text，given the kazakh text pre－processing，introduce a improved KNN algorithm，implemented the Kazakh text preprocessing that based on the improved KNN method on the their own built kazakh data sets.The experimental results show that can obtain better classification performance in the kazakh text classification.

Kazakh text categorization；stemming；vector space model；similarity；KNN

TP 391.1 ［學(xué)科代碼］ 520·30

A

（責(zé)任編輯：石紹慶）

1000－1832（2014）02－0063－06

10.11672／dbsdzk2014－02－013

2013－09－01

國家自然科學(xué)基金資助項目（61363066）；教育部博士點基金資助項目（20110043110011）；吉林省科技發(fā)展計劃項目（20120302）；伊犁師范學(xué)院資助項目（2012YB017）.

古麗娜孜（1972—），女，講師，博士研究生，主要從事文本分類、模式識別、智能控制研究.