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

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

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

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

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

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

將文本分類理論應用于哈薩克語中，給出了哈薩克語文本預處理過程.介紹一種改進的KNN算法，并結合自己構建的哈薩克語料集實現基于改進KNN算法的哈薩克語的文本分類.仿真實驗數據表明，該方法在哈薩克語的文本分類上獲得了較好的效果.

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

0 引言

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

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

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

1 文本預處理

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

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

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

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

文本預處理是影響文本分類準確度的關鍵因素之一，只有解決了上述2個問題，才能標注樣本，之后選擇最合適的文本分類算法實現分類任務.由于篇幅問題下面對這兩環節只進行簡要介紹.

1.1 哈文預處理

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

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

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

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

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

圖1 哈文詞干切分結果示例

詞干提取正確率

歧義詞切分正確率

表1為本文詞干提取所做實驗結果數據綜合分析表.

表1 詞干提取實驗結果綜合分析

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

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

為了達到如圖1所示的實驗目標結果，我們還做出了以下2項主要的基礎性準備工作.

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

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

1.2 文本模型

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

其中：W（t，dˉ）為詞t在文本dˉ中的權重；tf（t，dˉ）為詞t在文本dˉ中的詞頻；ni為訓練文本集中出現t的文本數；n為訓練文本總數.

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

式中：m為文檔集中所有不同詞的個數；aij為第i個詞在第j個文檔中出現的權重.不同的詞對應矩陣A的不同的一行，每個文檔則對應矩陣A的一列.

2 基于改進的KNN分類算法

2.1 KNN算法

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

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

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

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

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

KNN分類過程的數學描述：

定義判別函數為

分類的決策規則：

如果

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

Ci為訓練集中類別；ki為屬于Ci類的文檔數.

2.2 改進的KNN算法

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

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

第一階段 基礎工作——計算算法指標

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

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

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

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

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

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

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

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

3 實驗結果及分析

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

對文本分類效果進行評估，其標準有查準率、查全率：

圖2 KNN訓練文本過程示例

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

表2 綜合考察查準率與查全率的實驗結果

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

4 結論

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

［1］ 冷明偉，陳曉云，譚國律.基于小樣本集弱學習規則的KNN分類算法［J］.計算機應用研究，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］.情報學報，2007，26（1）：60－64.

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

［6］ 李榮陸，胡運發.基于密度的KNN文本分類器訓練樣本裁剪方法［J］.計算機研究與發展，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］.計算機工程與應用，2006，42（30）：160－163.

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

［11］ 黃杰，郭躬得，陳黎飛.增量KNN模型的修剪策略研究［J］.小型微型計算機系統，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 ［學科代碼］ 520·30

A

（責任編輯：石紹慶）

1000－1832（2014）02－0063－06

10.11672／dbsdzk2014－02－013

2013－09－01

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

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