馬志強(qiáng),張澤廣,閆 瑞,劉利民,馮永祥,蘇依拉
(內(nèi)蒙古工業(yè)大學(xué) 信息工程學(xué)院,內(nèi)蒙古 呼和浩特 010080)
基于N-Gram模型的蒙古語文本語種識(shí)別算法的研究
馬志強(qiáng),張澤廣,閆 瑞,劉利民,馮永祥,蘇依拉
(內(nèi)蒙古工業(yè)大學(xué) 信息工程學(xué)院,內(nèi)蒙古 呼和浩特 010080)
互聯(lián)網(wǎng)上蒙古語文本正在不斷地增加,如何讓網(wǎng)絡(luò)中的蒙古語內(nèi)容為搜索引擎和輿情分析等應(yīng)用提供服務(wù)引起了社會(huì)的高度關(guān)注。首先要解決如何采集網(wǎng)絡(luò)中蒙古語文本數(shù)據(jù),核心是準(zhǔn)確識(shí)別網(wǎng)絡(luò)中蒙古語文本的問題。該文提出了基于N-Gram模型的平均距離識(shí)別算法,建立了一個(gè)能夠?qū)δ繕?biāo)語種識(shí)別的實(shí)驗(yàn)平臺(tái)。實(shí)驗(yàn)結(jié)果表明,識(shí)別算法能夠很好地從中文、英文、蒙古文以及混合語言文本中識(shí)別出蒙古語文本,準(zhǔn)確率達(dá)到99.5%以上。
語種識(shí)別;N-Gram模型;平均距離識(shí)別算法;蒙古語文本
蒙古語是古老的民族語言之一,是內(nèi)蒙古自治區(qū)的通用語言文字。蒙古語語言文字是一種以詞為單位豎寫的語言,詞與詞之間用空格分開,采取從上到下,從左到右的書寫順序。蒙古語語言文字有33個(gè)字母,其中7個(gè)元音、17個(gè)基本輔音和9個(gè)借詞輔音。字母可以放置在詞首、詞中和詞尾等不同位置,構(gòu)成不同的詞[1-2]。同時(shí),蒙古語語言文字采用雙字節(jié)編碼,蒙古語語言文字也稱為蒙古文?;ヂ?lián)網(wǎng)上蒙古文內(nèi)容正在不斷增加,如何讓網(wǎng)絡(luò)中的蒙古文內(nèi)容為搜索引擎和輿情數(shù)據(jù)分析等應(yīng)用提供服務(wù)引起了社會(huì)的高度關(guān)注。為此,首先要解決如何采集網(wǎng)絡(luò)中蒙古語文本數(shù)據(jù),核心是準(zhǔn)確識(shí)別網(wǎng)絡(luò)中蒙古語文本的問題[3]。
蒙古文語種識(shí)別是一個(gè)文本語種分類問題[4]。研究者們?cè)谡Z種分類算法上開展了兩個(gè)方面的研究:基于規(guī)則方法的研究和基于統(tǒng)計(jì)方法的研究[4-8]。首先,在基于規(guī)則方法的研究中,需要人工總結(jié)出語言知識(shí)并將其轉(zhuǎn)換成系統(tǒng)規(guī)則[4],常見的具體做法就是利用特定語種中常見的字符串進(jìn)行正則表達(dá)式匹配[5]。但基于規(guī)則的方法存在以下缺點(diǎn):需要人工輔助和識(shí)別準(zhǔn)確率不穩(wěn)定[6-8]。其次,在基于統(tǒng)計(jì)方法的研究中,主要是基于N-Gram模型的文本語種識(shí)別算法研究[9-11]。文獻(xiàn)[4]提出了基于N-Gram的Bayes算法,能夠?qū)⒕S吾爾文從阿拉伯文、哈薩克文和柯爾克孜文等以阿拉伯字母為基礎(chǔ)書寫的類似文字中識(shí)別出來。最終網(wǎng)頁論壇的識(shí)別準(zhǔn)確率達(dá)到98.9%,微博客的識(shí)別準(zhǔn)確率達(dá)到96.6%。但它需要進(jìn)行多次計(jì)算,增加了返回結(jié)果的時(shí)間,降低了識(shí)別效率;文獻(xiàn)[6]提出了基于 N-Gram 模型的最小距離算法,具有容錯(cuò)性強(qiáng)、適合處理含有噪音的文檔及占用很小的存儲(chǔ)與計(jì)算。在語種識(shí)別上達(dá)到了一個(gè)99.8%,但在語種識(shí)別時(shí)針對(duì)多語種。文獻(xiàn)[5]針對(duì)漢、日等雙字節(jié)編碼語種,提出了基于字符層馬爾科夫語言模型的EM算法,取得了較高的識(shí)別率,但其針對(duì)的是詞間無空格分割的語種。
綜合計(jì)算性能與識(shí)別準(zhǔn)確率的考慮,在 N-Gram 模型上提出平均距離識(shí)別算法,建立了一個(gè)能夠?qū)δ繕?biāo)語種識(shí)別的實(shí)驗(yàn)平臺(tái)。實(shí)驗(yàn)結(jié)果表明,識(shí)別算法能夠很好的從中文、英文、蒙古文以及混合語言文本中識(shí)別出蒙古文,準(zhǔn)確率達(dá)到99.5%以上。
定義1 目標(biāo)語種文本可以表示成由音素、音節(jié)、字母或字組成的序列,形式化為C1C2…Ci-1CiCi+1…Cm-1Cm(1≤i≤m),Ci稱為最小分割單元[12]。文本的N元切分模型為集合G,G={gi|gi=CiCi+1…Ci+N-1,1≤i≤m-N+1,N≤m},N稱為滑動(dòng)窗口的長度。L=|G|,表示集合中元素的個(gè)數(shù)。目標(biāo)語種文本的N元切分模型如圖1所示。
圖1 目標(biāo)語種文本N元切分模型
當(dāng)N等于2、3和4時(shí),分別稱為二元(bigram)、三元(tri-gram)和四元(quad-gram)切分模型。例如,以蒙古文為例,圖2中的左側(cè)蒙古文文本(譯為: 內(nèi)蒙古)的bigrams、tri-grams和quad-grams如圖2中右側(cè)所示。
圖2 蒙古語文本切分模型樣例
定義2 統(tǒng)計(jì)N元切分模型中的gi,并按照降序排列,得到N元模型。訓(xùn)練模型稱為TM,測(cè)試文本模型稱為IM。gi在模型中的索引稱為位置,表示為 pos(gi)。TM中的位置表示為posTM(gi),IM中的位置表示為posIM(gi)
定義3gi在IM與TM的位置差的絕對(duì)值稱為gi的距離,即dis(gi),見式(1)。
(1)
其中find表示gi是否在TM模型中。當(dāng)find=1表示gi在TM中,find=0表示不在。
(2)
平均距離識(shí)別算法:
輸入: 訓(xùn)練模型TM,測(cè)試文本,閥值T。
輸出: 是否為目標(biāo)語種
Step1: 計(jì)算測(cè)試文本的N元測(cè)試模型IM; //具體見N元模型計(jì)算算法
Step2: for (i= 1;i≤ LIM;i++)
Step3: for (j= 1;j≤ LTM;j++)
Step4: Begin
Step5: if (find == 1)
Step6: dis(gi)=|posIM(gi)-posTM(gi)|;
Step7: else
Step8: dis(gi) = MAX;
Step9: DIS = DIS + dis(gi);
Step10: End;
Step13: 輸出測(cè)試文本為目標(biāo)語種;
Step14: else
Step15: 輸出測(cè)試文本為非目標(biāo)語種;
Step16: END;
N元模型計(jì)算算法:
輸入: 文本,N。//N表示滑動(dòng)窗口的大小
輸出: N元模型
Step1: 讀取文本,按照標(biāo)點(diǎn)符號(hào)提取句子S;
Step2: REPEAT
Step2: for (k= 1;k≤ L(Si)-N+1;k++) //L(Si)表示Si句子的長度
Step3: Begin
Step4:gk=CkCk+1...Ck+N-1;
Step5: count[gk]++;
Step6: End;
Step7: UNTIL全部句子處理完;
Step8: sort(count[g]); //按照gram出現(xiàn)次數(shù)降序排序
Step9: 輸出全部的gi和次數(shù)統(tǒng)計(jì);
Step10: END;
基于N-Gram的蒙古文文本語種識(shí)別過程如圖3所示。整個(gè)過程分為三個(gè)階段: 訓(xùn)練階段、測(cè)試文本預(yù)處理階段和識(shí)別階段。
圖3 基于N-Gram的蒙古語文本識(shí)別過程
在訓(xùn)練階段中,輸入N值與訓(xùn)練集,進(jìn)行基于N-Gram算法的模型訓(xùn)練,最終得出訓(xùn)練模型;在測(cè)試文本預(yù)處理階段,對(duì)于任意輸入的未知語種文本內(nèi)容,進(jìn)行N-Gram算法進(jìn)行切片,切片結(jié)束后并按照頻率進(jìn)行排序,得到預(yù)處理后的grams;在識(shí)別階段中,輸入預(yù)處理后的grams與訓(xùn)練模型,識(shí)別算法把計(jì)算結(jié)果與閥值進(jìn)行比較,最終得出分類結(jié)果。
識(shí)別過程中包括三個(gè)關(guān)鍵問題,分別是: N-Gram算法中的N值選取、訓(xùn)練模型的降維處理以及平均距離識(shí)別算法中參數(shù)的確定。
3.1 N的選取
由于蒙古語文本的語料庫無法從ODP等提供語料的人工目錄上去獲得,所以通過人為手工從互聯(lián)網(wǎng)上抽取網(wǎng)頁中的蒙古語文本,建立了大小為496KB的蒙古語文本語料庫作為訓(xùn)練集[13]。并分別采用bigram,tri-gram進(jìn)行訓(xùn)練,最后得出了bigram訓(xùn)練模型和tri-gram訓(xùn)練模型如圖4所示。
圖4 bigram與tri-gram訓(xùn)練模型圖
定義5 在訓(xùn)練模型中,min(x)代表前x個(gè)grams出現(xiàn)頻率的最小值,gc(y)代表頻率為y的gram總數(shù)。
從gram總數(shù)、min(x)、gc(y)以及訓(xùn)練時(shí)間四個(gè)方面對(duì)bigram與tri-gram訓(xùn)練模型進(jìn)行比較,比較結(jié)果如表1所示。
通過表1中數(shù)據(jù)可以看出: 與bigram相比,基于tri-gram的訓(xùn)練模型數(shù)據(jù)聚集程度較低,呈現(xiàn)出一定的稀疏性[14-15],最終采用N=2的模型。
表1 bigram與tri-gram的訓(xùn)練模型比較實(shí)驗(yàn)
3.2 模型降低維度處理
訓(xùn)練模型預(yù)處理的目的是為了得到一個(gè)優(yōu)質(zhì)的具有典型代表的訓(xùn)練模型,得出的訓(xùn)練模型既要求具有代表性,又能考慮后期的識(shí)別性能[16]。
定義6 初始的訓(xùn)練模型表示為TMI,TMI的長度表示為LTMI。用count(gi)表示gi出現(xiàn)的次數(shù);k表示TMI中的索引。在TMI中前k個(gè)gi出現(xiàn)的總次數(shù)nk表示為:
(3)
定義7 給定TMI,前t個(gè)grams出現(xiàn)次數(shù)與gram出現(xiàn)總次數(shù)的比值r表示為:
(4)
由式(4)可以得出: (1)f′(t)>0 (2)f″(t)<0 (3)漸近線為r=1。因此函數(shù)曲線隨著t的增長f(t)嚴(yán)格單調(diào)遞增且遞增程度逐漸下降,且逐漸趨近于r=1。函數(shù)曲線如圖5所示。
圖5 r=f(t)的函數(shù)曲線
定義8 已知(t0,r0)為曲線上的一點(diǎn),則在該點(diǎn)的斜率kt0表示為:
(5)
當(dāng)kt0≥1時(shí),前t0個(gè)grams具有明顯的聚集特性,當(dāng)kt0<1時(shí),前t0個(gè)grams開始表現(xiàn)出稀疏特性[17]。
根據(jù)定義8,分別令t0等于200,300與400,計(jì)算kt0,結(jié)果如表2所示。
通過表2可以得出,當(dāng)t0=300時(shí),kt0=1,證明前300個(gè)grams具有一定的聚集特性。 從而取前300個(gè)grams作為訓(xùn)練模型TM。
表2 kt0計(jì)算結(jié)果
3.3 平均距離識(shí)別算法中參數(shù)的確定
3.3.1MAX確定
給定r=f(t)的函數(shù)曲線,設(shè)(t0,r0)為曲線上的某一點(diǎn)。把位于(t0,+∞)區(qū)間內(nèi)的曲線等價(jià)于經(jīng)過(t0,r0)點(diǎn)的一條直線r=kt+b,其中k代表斜率,b代表與Y軸的交點(diǎn)。已知在t=t0處斜率為kt0,根據(jù)r=f(t)函數(shù)的曲線特性,在(t0,+∞)區(qū)間里k的取值范圍為:0 定義9 覆蓋性訓(xùn)練模型。覆蓋性訓(xùn)練模型TMA是一種理想狀態(tài),指包含了該目標(biāo)語種文本的所有g(shù)rams。包含的gram總數(shù)表示為LTMA。 根據(jù)定義9,設(shè)r=f(t)的函數(shù)曲線對(duì)X軸方向的最大值估計(jì)就是LTMA,則LTMA表示為: (6) 當(dāng)k=kt0時(shí),LTMA的值表示為l0。 顯然,LTMA的取值區(qū)間為(l0,+∞)。這里取最小值l0+1作為MAX。即: (7) 3.3.2 閥值確定 定義10 在訓(xùn)練模型TM中,能找到系統(tǒng)的gram的概率為w0,不能找到的概率為w1。如果找到,則該項(xiàng)距離取最大值d0,如果沒找到,則該項(xiàng)最大距離取d1。 根據(jù)定義10,并假設(shè)所有的目標(biāo)語種文本grams均能在TMI中找到。則如果是蒙古文,它的T值計(jì)算公式如式(8)所示。 (8) 首先,d0與d1的計(jì)算公式如式(9)所示。 (9) (10) 即如果找到,則找到的最大距離為LTM-1,否則最大距離為MAX。 其次,w0與w1的計(jì)算見式(11)與式(12): (11) (12) 其中,f(i),f(j)代表第i個(gè)與第j個(gè)gram對(duì)應(yīng)的頻率值。 最終,把計(jì)算得到的d0、d1、w0與w1帶入到式(8)中,計(jì)算閥值T。但該閥值只針對(duì)純文本的模式,如果在混合模式下,應(yīng)該適當(dāng)?shù)靥岣唛y值。 4.1 數(shù)據(jù)來源 4.1.1 訓(xùn)練數(shù)據(jù)來源 根據(jù)文獻(xiàn)[5-6],在文本語種識(shí)別方面,為了能夠有效地抽取文本特征,需要選擇一個(gè)合適大小的、能夠把特征抽取出來的訓(xùn)練集合。因此,訓(xùn)練集合來自于蒙科立網(wǎng)站(http://mng.ulaaq.com/)的20個(gè)欄目下的500篇文章,大小為496kb。 4.1.2 測(cè)試數(shù)據(jù)來源 蒙古文的網(wǎng)頁中經(jīng)?;煊兄形暮陀⑽?。因此,最終的測(cè)試語種類別有中文、英文和蒙古文。測(cè)試數(shù)據(jù)集包括單語種測(cè)試數(shù)據(jù)集與混合語種測(cè)試數(shù)據(jù)集[18]。測(cè)試數(shù)據(jù)來源于ODP(開源目錄索引),如表3 和表4所示。 表3 單語種測(cè)試數(shù)據(jù)集的組成 表4 混合語種測(cè)試數(shù)據(jù)集的組成 4.2 實(shí)驗(yàn)結(jié)果分析 針對(duì)蒙古語文本語種識(shí)別問題,本文采用識(shí)別準(zhǔn)確率(Accuracy Rate of Recognition,ARR)和誤判率(False Positive Rate,F(xiàn)PR)作為重要評(píng)價(jià)指標(biāo)。他們分別定義如下: (1) 識(shí)別準(zhǔn)確率(ARR),定義為將測(cè)試集中蒙古文文本判別為蒙古文的概率與非蒙古文文本判別為非蒙古文的概率之和。計(jì)算公式如式(13)所示。 ARR= (13) (2) 誤判率(FPR),定義為將測(cè)試集中蒙古文文本判別為非蒙古文的概率與非蒙古文文本判別為蒙古文的概率之和。計(jì)算公式如式(14)所示。 FPR= (14) 其中,NM→M表示將蒙古文文本判斷為蒙古文的數(shù)目,NM→N表示將蒙古文文本判斷為非蒙古文的數(shù)目,NN→N表示將非蒙古文文本判斷為非蒙古文的數(shù)目,NN→M表示將非蒙古文文本判斷為蒙古文的數(shù)目。 可見,ARR的值越高,F(xiàn)PR的值越低,則識(shí)別能力越強(qiáng)。 為了能夠更好地識(shí)別蒙古語文本,分別對(duì)單語種和混合語種文本進(jìn)行測(cè)試,并針對(duì)混合語種文本進(jìn)行閥值的確定。 (1) 分別對(duì)單語種文本中的長、短文本進(jìn)行測(cè)試,長短文本以200個(gè)字符長度為界限,測(cè)試文本長度用len表示。測(cè)試結(jié)果如表5所示。 表5 單語種文本測(cè)試結(jié)果 通過表5可以看出: ARR的值都相對(duì)較高,F(xiàn)PR的值都相對(duì)較低,即蒙古文能夠從中、英、蒙的單語種文本模式中以一個(gè)高的準(zhǔn)確率被識(shí)別。 (2) 對(duì)混合語種文本的閥值確定進(jìn)行實(shí)驗(yàn)。對(duì)混合語種文本中的蒙中、蒙英、中英和蒙中英分別進(jìn)行測(cè)試,蒙古文與其他語種文本的混合比例為1∶1。混合文本的平均長度為300個(gè)字符。在測(cè)試集相同的情況下,用不同的閥值對(duì)其進(jìn)行測(cè)試,以確定閥值。測(cè)試結(jié)果如表6所示。 表6 混合語種文本測(cè)試結(jié)果 通過表6可以看出: 只有當(dāng)T=385時(shí),ARR的值最高,F(xiàn)PR的值最低,即此時(shí)識(shí)別能力最強(qiáng)。因此,在混合文本下,閥值T設(shè)定為385。 結(jié)束語 本文通過對(duì)文本語種識(shí)別的深入分析與研究,并結(jié)合蒙古文的實(shí)際書寫特點(diǎn),對(duì)蒙古語文本語種識(shí)別展開了研究。首先,利用N-Gram模型進(jìn)行模型訓(xùn)練與測(cè)試文本預(yù)處理;然后,在識(shí)別階段,采用平均距離算法作為目標(biāo)語種識(shí)別算法,并搭建了一個(gè)目標(biāo)語種文本識(shí)別實(shí)驗(yàn)平臺(tái);最終,對(duì)單語種文本和混合語種文本進(jìn)行測(cè)試并對(duì)混合文本下的平均距離識(shí)別算法的閥值確定進(jìn)行實(shí)驗(yàn)研究,結(jié)果得到了一個(gè)較高的識(shí)別準(zhǔn)確率和一個(gè)較低的誤判率。但本文在混合語種文本測(cè)試中,測(cè)試集合中的蒙古文與其他語種文本的混合比例僅是≤1∶1,對(duì)混合比例>1∶1的混合文本語種識(shí)別還有待進(jìn)一步研究。 [1] 金良,散旦瑪,玉英.傳統(tǒng)蒙古文編碼及其應(yīng)用現(xiàn)狀分析[J].語文學(xué)刊,2012,4:16-18. [2] 清格爾泰.現(xiàn)代蒙古語語法[M].呼和浩特: 內(nèi)蒙古人民出版社,1999. [3] Denis Shestakov. Current Challenges in Web Crawling[C]//Proceedings of the 13th International Conference. ICWE 2013:518-521 . [4] 倪耀群,曹鵬,許洪波等.網(wǎng)絡(luò)維吾爾文判別及其文本長度下界的探討[J].中文信息學(xué)報(bào), 2012, 26(6):109-115. [5] 馮沖, 黃河燕, 陳肇雄等. 基于字符層馬爾科夫模型的多語種識(shí)別[J].計(jì)算機(jī)科學(xué),2006, 33(1): 226-228. [6] Cavnar, William B, John M. Trenkle. N-Gram-based text categorization[J]. Ann Arbor MI 48113.2 (1994): 161-175. [7] 付強(qiáng),宋彥,戴禮榮. 因子分析在基于GMM的自動(dòng)語種識(shí)別中的應(yīng)用[J]. 中文信息學(xué)報(bào),2009,23(4):77-81. [8] 劉偉偉,吉立新,李邵梅,何贊園. 基于區(qū)分加權(quán)干擾屬性投影的語種識(shí)別方法[J]. 中文信息學(xué)報(bào),2012,26(6):59-64. [9] 朱云霞. 結(jié)合聚類思想神經(jīng)網(wǎng)絡(luò)文本分類技術(shù)研究[J].計(jì)算機(jī)應(yīng)用研究, 2012,29(1): 155-157. [10] 劉巍巍,張衛(wèi)強(qiáng),劉加. 基于鑒別性向量空間模型的語種識(shí)別[J].清華大學(xué)學(xué)報(bào), 2013, 53(6): 796-799. [11] 李惠,劉穎. 基于語言模型和特征分類的抄襲判定[J].計(jì)算機(jī)工程, 2013, 39(5):230-234. [12] 張澤華, 苗奪謙, 錢進(jìn). 鄰域粗糙化的啟發(fā)式重疊社區(qū)擴(kuò)張方法[J]. 計(jì)算機(jī)學(xué)報(bào), 2013, 36(10): 2078-2086. [13] Grefenstette G. Comparing Two Language Identification Schemes[C]//Proceedings of the 3th International Conference on Statistical Analysis of Textual Data, Rome, Italy. 1995. [14] Pingali P, Varma V. Multi-lingual Indexing Support for CLIR using Language Modeling[J]. IEEE Data Eng. Bull., 2007, 30(1): 70-85. [15] Nguyen D T, Nguyen C T. Cross-Lingual Information Retrieval Model for Vietnamese-English Web Sites[C]//Proceedings of the Computer Modeling and Simulation, 2010. ICCMS’10. Second International Conference on. IEEE, 2010, 4: 254-257. [16] Malisiewicz T, Gupta A, Efros A A. Ensemble of exemplar-svms for object detection and beyond[C]//Proceedings of the Computer Vision (ICCV), 2011 IEEE International Conference on. IEEE, 2011: 89-96. [17] Chelba C. Exploiting syntactic structure for natural language modeling[J]. Johns Hopkins Universit, 2000: 225-231. [18] Lipka, Nedim, and Benno Stein. Identifying featured articles in Wikipedia: writing style matters. Proceedings of the 19th international conference on World wide web[C]//Proceedings of the ACM, 2010: 1147-1148. N-Gram Based Language Identification for Mongolian Text MA Zhiqiang, ZHANG Zeguang, YAN Rui, LIU Limin, FENG Yongxiang, SU Yila (School of Information Engineering, Inner Mongolia University of Technology, Hohhot, Inner Mongolia 010080, China) With the rapid increasing of Mongolian texts on the Internet, it is of practical significance to identify them before further processing. This paper proposes an average distance recognition algorithm based on N-Gram model, and an experimental platform is established. Experimental results show that the presented algorithm can identify Mongolian text from Chinese, English, or even mixed-language texts, with an accuracy of above 99.5%. language identification; N-Gram model; average distance recognition algorithm; Mongolian text 馬志強(qiáng)(1972-),碩士,副教授,主要研究領(lǐng)域?yàn)槊晒盼男畔z索、語音識(shí)別。E?mail:mzq_bim@163.com張澤廣(1988-),碩士研究生,主要研究領(lǐng)域?yàn)槊晒盼乃阉饕?。E?mail:zhangzeguang88@sina.com閆瑞(1988-),碩士研究生,主要研究領(lǐng)域?yàn)槊晒耪Z語音識(shí)別。E?mail:yanrui309@163.com 1003-0077(2016)01-0133-07 2014-09-01 定稿日期: 2014-10-20 國家自然科學(xué)基金(61363052);內(nèi)蒙古自治區(qū)自然科學(xué)基金(2014MS0608);內(nèi)蒙古自治區(qū)高等學(xué)??茖W(xué)研究項(xiàng)目(NJZY12052);內(nèi)蒙古工業(yè)大學(xué)重點(diǎn)基金(ZD201118) TP391 A4 實(shí)驗(yàn)設(shè)置與結(jié)果分析