基于多尺度的n-grams特征選擇加權(quán)及匹配算法

劉世興

(遼寧機(jī)電職業(yè)技術(shù)學(xué)院 信息工程系， 遼寧 丹東 118009)

0 引 言

n-grams語言模型的基本思想是將文本按照詞匯大小為n的滑動(dòng)窗口進(jìn)行操作，形成長度為n的詞匯片段序列，具有拼寫容錯(cuò)能力強(qiáng)、語種無關(guān)性[1-2]、不需詞典規(guī)則[3]及特征維度低[4]等優(yōu)點(diǎn)，因而廣泛應(yīng)用于大數(shù)據(jù)及人工智能領(lǐng)域，如：文本分類[5-6]、聚類[7]、拼音校驗(yàn)[8]、預(yù)測[9]、機(jī)器翻譯[10]、語音識別[11]、情感分析[12]及惡意軟件檢測[13]等。

作為n-grams語言模型的應(yīng)用前提，其選擇、加權(quán)及匹配算法一直是研究人員關(guān)注的重點(diǎn)。Maipradit等人[14]提出一種基于逆文本頻率的n-grams特征選擇算法，用于解決情感分類問題。該算法僅注重特征的選擇，沒有加權(quán)過程，分類性能提升幅度較小。Zhou等人[15]將n-grams模型進(jìn)行重構(gòu)，以解決特征選擇及加權(quán)問題。但重構(gòu)后的n-grams特征語義結(jié)構(gòu)遭到破壞，減少了原有特征包含的文本信息。Hwang等人[16]將n-grams特征的長度擴(kuò)大到5，用于長文本及海量文本的分類。但該方法只能用于特定文本，在中、短文本中，5-grams特征會產(chǎn)生更多的稀疏數(shù)據(jù)。

為優(yōu)化n-grams特征的選擇、加權(quán)及匹配算法，在不破壞n-grams結(jié)構(gòu)的前提下，增強(qiáng)n-grams特征的權(quán)值區(qū)分度，減少稀疏數(shù)據(jù)的產(chǎn)生，本文以詞性、語義及詞匯的內(nèi)在偏序關(guān)系為基礎(chǔ)，提出利用詞性的類分布和語義近似度結(jié)合傳統(tǒng)n-grams特征加權(quán)，達(dá)到區(qū)分特征權(quán)值的目的，通過權(quán)值過濾并選擇n-grams特征，在匹配過程中引入語義近似度，減少匹配過程中產(chǎn)生的稀疏數(shù)據(jù)。在美國當(dāng)代英語語料庫和北京BBC漢語語料庫中的實(shí)驗(yàn)結(jié)果表明，相比于引言中提到的3種算法，基于多尺度的n-grams特征選擇加權(quán)及匹配算法得到的特征質(zhì)量更高，并在分類器中的準(zhǔn)確率大幅提升。

1 多尺度n-grams特征選擇加權(quán)

傳統(tǒng)特征加權(quán)一般建立在文本中特征出現(xiàn)的頻率或概率的基礎(chǔ)上，如tf-idf、卡方檢驗(yàn)等。這類加權(quán)方法對于單獨(dú)的詞匯特征較為有效，但n-grams特征由多個(gè)詞匯組成，假設(shè)n個(gè)詞匯在文本中的出現(xiàn)概率為：p1，p2，……，pn，則這些詞匯同時(shí)出現(xiàn)在同一文本的概率為：

P=p1p2……pn.

(1)

由于每個(gè)詞匯的出現(xiàn)概率pk(1≤k≤n)值域?yàn)?0,1)，故概率P會隨著n的增加趨近于0，此時(shí)P為n個(gè)特征同時(shí)出現(xiàn)在同一文本中，并不考慮每個(gè)詞匯的順序和是否連續(xù)的情況，而n-grams特征是n個(gè)詞匯連續(xù)出現(xiàn)且順序不變，所以真正的n-grams特征出現(xiàn)概率要遠(yuǎn)遠(yuǎn)小于P甚至為0，而建立在此基礎(chǔ)上的傳統(tǒng)加權(quán)方法在訓(xùn)練集中會導(dǎo)致2個(gè)問題：

(1)特征權(quán)值都為趨于0的值，區(qū)分度不夠，難以選擇；

(2)在測試集中匹配時(shí)產(chǎn)生大量的0數(shù)據(jù)，即稀疏數(shù)據(jù)。

1.1 n-grams詞性分布加權(quán)

性質(zhì)1在文本中，n-grams特征在詞性、語義及詞匯三種狀態(tài)下包含的文本信息量存在如下的偏序關(guān)系：

{詞性語義詞匯}

證明以“我愛香蕉”為例，首先，經(jīng)過分詞后會被切分為“我”、“愛”和“香蕉”，屬于3-grams特征。當(dāng)該特征以詞性形式出現(xiàn)時(shí)，形式為“代詞-動(dòng)詞-名詞”，僅從該特征的詞性結(jié)構(gòu)來看，很難得到有用的文本信息。當(dāng)該特征以近似的語義詞出現(xiàn)時(shí)，以“我喜歡水果”為例，該3-grams特征與原特征近似度約為0.8，從中可以獲得一定量的文本信息，但具體喜歡什么水果難以從中得出結(jié)論，還需通過原特征中的具體詞匯做出準(zhǔn)確判斷，故詞性、語義及詞匯存在偏序關(guān)系，性質(zhì)得證。

為增強(qiáng)n-grams特征權(quán)值區(qū)分度并減少稀疏數(shù)據(jù)，充分利用性質(zhì)1中的偏序關(guān)系，提出多尺度加權(quán)的第一個(gè)尺度，即詞性分布加權(quán)。雖然詞性包含的文本分類信息非常有限，但當(dāng)其作為n-grams特征的詞性組合時(shí)，提供的文本分類信息要多于其單獨(dú)存在的情況。例如在新聞分類中，體育類新聞經(jīng)常出現(xiàn)某名運(yùn)動(dòng)員或球隊(duì)的名字后面接諸如：射門、投籃、運(yùn)球、擊打、獲勝、失利、退賽等詞匯，組成2-grams特征。而轉(zhuǎn)換為詞性是“名詞-動(dòng)詞”的形式，相比較于財(cái)經(jīng)類新聞和科技類新聞中常見的“某公司股價(jià)或財(cái)報(bào)”、“某省房地產(chǎn)”、“某國央行”及“某形容詞+某品牌手機(jī)”這類“名詞-名詞”或“形容詞-名詞”的形式，可見“名詞-動(dòng)詞”的n-grams詞性組合在體育類新聞的分布更為廣泛。綜上所述，使用標(biāo)準(zhǔn)差對詞性分布進(jìn)行衡量，如式(2)所示：

(2)

其中，n為待分類文本類別數(shù)；freqi為該詞性組合在第i個(gè)類中的出現(xiàn)頻率；freqavg為該詞性組合在n個(gè)類別中出現(xiàn)的平均頻率。由此給出尺度一，詞性分布加權(quán)算法，詳述如下。

算法1 詞性分布加權(quán)算法

輸入：待分類文本集合T{t1,t2,......,tm}，待分類文本類別數(shù)n

輸出：n-grams特征詞性組合權(quán)值集合Wpos{pos1,pos2,......,posk}

begin

使用ICTCLAS分詞接口對文本集合T進(jìn)行分詞

使用滑動(dòng)窗口法得到n-grams特征集合，進(jìn)行詞性化處理得到Wpos

for eachi:1 tok

Wpos[i] =Weight(posi)

end for

end

1.2 n-grams語義加權(quán)及匹配

語義作為性質(zhì)1中的偏序集元素，可以作為另一個(gè)尺度引入n-grams特征加權(quán)或匹配。在進(jìn)行語義加權(quán)及匹配時(shí)遵循如下原則，即相同長度的n-grams特征進(jìn)行語義加權(quán)或匹配。匹配過程中首先得到待加權(quán)的n-grams特征，如下所示：

word1-word2-……-wordn

從文本頭部開始，以長度n為窗口，得到與待加權(quán)特征長度相同的文本段，如下所示：

word1’-word2’-……-wordn’

進(jìn)行語義加權(quán)時(shí)，使用ICTCLAS語義計(jì)算接口，將word1與文本段中每個(gè)詞匯做語義近似度計(jì)算，取語義近似最大值simmax(word1)。當(dāng)出現(xiàn)如下兩種情況時(shí)將simmax(word1)值賦0：

(1)simmax(word1)小于0.5，表明n-grams特征中第一個(gè)詞匯與文本段不具備語義近似；

(2)word1為語義無關(guān)詞集合中的詞，如“的”、“了”、“地”等。

除上述兩種情況外，將simmax(word1)保留，繼續(xù)計(jì)算n-grams特征中第二個(gè)詞匯word2的語義近似值simmax(word2)。n-grams特征與第一個(gè)文本段的語義近似度計(jì)算如式(3)所示：

(3)

其中，n為n-grams特征中的詞匯個(gè)數(shù)，將特征中每個(gè)詞的最大語義近似值求和后平均到每個(gè)詞匯中，得到與文本段的最終語義近似結(jié)果。若文本t含有m個(gè)詞匯，即長度為m，則其在與長度為n的n-grams特征加權(quán)時(shí)，會分為m-n+1個(gè)文本段，則在該文本中得到的加權(quán)值即為m-n+1個(gè)文本段權(quán)值和。若訓(xùn)練集或測試集T中存在k個(gè)文本，則n-grams特征在k個(gè)文本中重復(fù)上述操作，得到的結(jié)果Similarity(n-grams,t)既可以作為訓(xùn)練集的特征加權(quán)，用于后續(xù)特征選擇，也可以作為測試集的匹配結(jié)果，避免稀疏數(shù)據(jù)。綜上所述給出尺度二，即語義加權(quán)及匹配算法，詳述如下。

算法2 語義加權(quán)及匹配算法

輸入：訓(xùn)練集或測試集文本T{t1,t2,......,tm}

輸出：語義加權(quán)或匹配后的n-grams特征值集合Wsim{w1,w2,......,wk}

begin

對文本T使用ICTCLAS分詞接口進(jìn)行分詞

使用滑動(dòng)窗口法得到n-grams特征集合F

for eachi:1 toF.size

for eachj:1 toT.size

Wsim(F[i]) =Wsim(F[i]) +Similarly(F[i],T[j])

end for

end for

end

1.3 多尺度的n-grams特征選擇加權(quán)及匹配算法

在給出前兩種尺度的n-grams特征加權(quán)方法后，結(jié)合傳統(tǒng)的tf-idf加權(quán)特征值，將3種尺度得到的權(quán)值求和，若結(jié)果小于閾值β，則舍棄該n-grams特征，否則保留。綜上所述，給出基于多尺度的n-grams特征選擇加權(quán)算法，詳述如下。

算法3 多尺度的n-grams特征選擇加權(quán)算法

輸入：訓(xùn)練集或測試集文本T{t1,t2,......,tm}

輸出：語義加權(quán)或匹配后的n-grams特征值集合W{w1,w2,......,wk}

begin

對文本T使用ICTCLAS分詞接口進(jìn)行分詞

使用滑動(dòng)窗口法得到n-grams特征集合F

根據(jù)詞性分布加權(quán)，得到n-grams詞性組合權(quán)值Wpos{pos1,pos2,......,posk}

根據(jù)語義加權(quán)，得到n-grams權(quán)值集合Wsim{sim1,sim2,......,simk}

根據(jù)傳統(tǒng)tf-idf加權(quán)方法得到權(quán)值集合Wtfidf{td1,td2,......tdk}

for eachi:1 tok

W[i] =Wpos[i] +Wsim[i] +Wtfidf[i]

ifW[i] <β

deleteW[i]

end if

end for

end

2 實(shí)驗(yàn)

本文研究采用的實(shí)驗(yàn)數(shù)據(jù)集分中英文兩種，即北京BBC漢語語料庫和美國當(dāng)代英語語料庫。使用支持向量機(jī)(Support Vector Machine，SVM)進(jìn)行分類性能評價(jià)，評價(jià)指標(biāo)包括準(zhǔn)確率(P)、召回率(R)和F值(F)。

2.1 北京BBC漢語語料庫實(shí)驗(yàn)

北京BBC漢語語料庫實(shí)驗(yàn)中，n-grams文本分類特征采用5-grams。在特征數(shù)分別為200、500、1 000、1 500、2 000、2 500和3 000時(shí)，對比引言中提到的3種n-grams特征選擇加權(quán)方法和本文方法的分類準(zhǔn)確率、召回率及F值，如圖1～圖3所示。從圖1～圖3中可以看到，4種方法在5-grams特征數(shù)不超過1 000時(shí)，準(zhǔn)確率、召回率和F值都呈上升趨勢。當(dāng)5-grams特征數(shù)量超過1 000時(shí)，逆文本頻率法和重構(gòu)法的分類性能呈現(xiàn)斷崖式下降，究其原因在于當(dāng)5-grams特征數(shù)量增多時(shí)，產(chǎn)生的稀疏數(shù)據(jù)也在增加，且增加速率相比于非稀疏數(shù)據(jù)要快，導(dǎo)致在特征數(shù)量達(dá)到3 000時(shí)，二者的準(zhǔn)確率不足70%。擴(kuò)展的5-grams方法由于其針對5-grams特征設(shè)計(jì)，在數(shù)量超過1 500后分類性能逐漸下降，但相比于逆文本頻率和重構(gòu)法，性能下降幅度較小，在5-grams特征數(shù)達(dá)到3 000時(shí)準(zhǔn)確率為82%。而本文方法由于從詞性、語義和詞匯三個(gè)尺度對n-grams特征進(jìn)行選擇加權(quán)及匹配，使得稀疏數(shù)據(jù)大幅減少，從圖3中可以看到，特征數(shù)量超過2 000時(shí)分類性能才開始下降，在特征數(shù)達(dá)到3 000時(shí)準(zhǔn)確率達(dá)到89%。

圖1 3種引言方法與本文方法在SVM中的準(zhǔn)確率

Fig. 1 Accuracy of three introduction methods and the proposed methods in SVM

圖2 3種引言方法與本文方法在SVM中的召回率

Fig. 2 The recall rate of three introduction methods and the proposed method in SVM

圖3 3種引言方法與本文方法在SVM中的F值

Fig. 3 TheFvalue of three introduction methods and the proposed method in SVM

2.2 美國當(dāng)代英語語料庫

在美國當(dāng)代英語語料庫中，分別對比引言中的3種方法和本文方法在2-、3-、4-及5-grams特征時(shí)產(chǎn)生的稀疏數(shù)據(jù)數(shù)量和占比，見表1～表4。從表1～表4中可以明顯看出，當(dāng)特征為2-grams且特征數(shù)量不超過2 000時(shí)，引言中的2種方法稀疏數(shù)據(jù)并不嚴(yán)重，占比不超過20%，當(dāng)特征數(shù)量達(dá)到3 000時(shí)，稀疏數(shù)據(jù)逐漸增加，分別達(dá)到32.7%和28.4%。而本文方法在稀疏數(shù)據(jù)的抑制上效果較好，在2-grams特征數(shù)量達(dá)到3 000時(shí)，占比僅為11.9%。當(dāng)n-grams特征中n值分別為3時(shí)，逆文本頻率法在特征數(shù)為200時(shí)，稀疏數(shù)據(jù)的占比就達(dá)到了20%以上，重構(gòu)法在特征數(shù)為500時(shí)稀疏數(shù)據(jù)占比超過20%，而當(dāng)特征數(shù)量達(dá)到3 000時(shí)，2種引言方法的稀疏數(shù)據(jù)占比接近50%，已經(jīng)不適合作為分類特征。相比而言，本文方法在特征數(shù)達(dá)到3 000時(shí)，稀疏數(shù)據(jù)占比仍然保持在20%以下。當(dāng)n值達(dá)到4和5時(shí)，引言方法在特征數(shù)量超過1 000后都產(chǎn)生了占比接近于50%的稀疏數(shù)據(jù)，無法作為分類特征進(jìn)行分類建模。而本文方法在特征數(shù)達(dá)到3 000的情況下，4-grams和5-grams時(shí)的稀疏數(shù)據(jù)占比分別為23.3%和29.4%，遠(yuǎn)低于引言方法。

表1 3種方法在2-grams特征時(shí)的稀疏數(shù)據(jù)量及所占比例

表2 3種方法在3-grams特征時(shí)的稀疏數(shù)據(jù)量及所占比例

表3 3種方法在4-grams特征時(shí)的稀疏數(shù)據(jù)量及所占比例

表4 4種方法在5-grams特征時(shí)的稀疏數(shù)據(jù)量及所占比例

3 結(jié)束語

針對n-grams特征選擇加權(quán)及匹配過程中的權(quán)值區(qū)分度低和稀疏數(shù)據(jù)多的問題，本文利用詞性、語義和詞匯的內(nèi)在偏序關(guān)系，提出使用詞性分布、語義和詞匯的多尺度n-grams特征選擇加權(quán)及匹配算法。該算法在有效降低稀疏數(shù)據(jù)量的同時(shí)，能夠在特征加權(quán)過程中增強(qiáng)權(quán)值區(qū)分度，便于選擇優(yōu)質(zhì)特征。對比實(shí)驗(yàn)結(jié)果表明，本文方法得到的n-grams特征在分類性能和稀疏數(shù)據(jù)控制上均有大幅提升，有利于進(jìn)一步推廣n-grams特征的應(yīng)用領(lǐng)域。