莫禮平，黃永琨

(吉首大學(xué)信息科學(xué)與工程學(xué)院，湖南 吉首 416000)

詞性標(biāo)注是指根據(jù)上下文內(nèi)容的語法關(guān)系，對句子中的各個單詞進(jìn)行詞性判定和標(biāo)注的過程.該過程是語料加工、語義分析、文本索引、文本分類、機(jī)器翻譯和信息檢索等自然語言信息處理應(yīng)用領(lǐng)域不可缺少的重要環(huán)節(jié)，對于消除單詞歧義、減少查詢模糊性、降低索引量、提高檢索效率有重要影響[1-2].詞性標(biāo)注方法可以分為規(guī)則類方法和統(tǒng)計類方法2大類：規(guī)則類方法通常采用人工方式編制復(fù)雜的詞性標(biāo)注規(guī)則系統(tǒng)，再依據(jù)這些標(biāo)注規(guī)則進(jìn)行詞性標(biāo)注；統(tǒng)計類方法主要利用相鄰詞性標(biāo)簽之間的同現(xiàn)概率及統(tǒng)計模型，借助標(biāo)注語料庫來實現(xiàn)詞性標(biāo)注.以隱馬爾可夫模型(Hidden Markov Model，HMM)和條件隨機(jī)場(Conditional Random Field，CRF)為代表的傳統(tǒng)統(tǒng)計模型用于詞性標(biāo)注能夠取得較好的標(biāo)注結(jié)果，但過于依賴人工設(shè)計的特征[3-4].近年興起的循環(huán)神經(jīng)網(wǎng)絡(luò)(Recurrent Neural Network，RNN)深度學(xué)習(xí)模型能夠?qū)⒃~的特征表示和詞性標(biāo)注過程納入到同一框架，極大地減少對人工設(shè)計特征的依賴[5].目前學(xué)術(shù)界的流行做法是，將長短期記憶(Long Short-Term Memory，LSTM)網(wǎng)、雙向長短期記憶(Bi-directional Long Short-Term Memory，BiLSTM)網(wǎng)等改進(jìn)型的RNN及其與卷積神經(jīng)網(wǎng)絡(luò)(Convolutional Neural Network，CNN)、CRF等模型組成的混合模型應(yīng)用于詞性標(biāo)注研究.近年來，學(xué)者關(guān)注較多的主要有BiLSTM-CRF，CNN-LSTM，LSTM-RNN-CRF和BiLSTM-CNN-CRF等混合模型，這些模型在面向漢語、朝鮮文、維吾爾文等語言文字的詞性標(biāo)注系統(tǒng)或測試集上均展示出顯著優(yōu)于傳統(tǒng)統(tǒng)計模型的標(biāo)注效果[6-10].

無論是基于傳統(tǒng)統(tǒng)計模型還是深度學(xué)習(xí)模型的詞性標(biāo)注方法，都依賴于訓(xùn)練用的標(biāo)注語料庫中語料的詞性標(biāo)注準(zhǔn)確性.利用詞性標(biāo)注規(guī)則優(yōu)化訓(xùn)練語料庫，是提高訓(xùn)練語料質(zhì)量的一種有效途徑.然而，人工編制的標(biāo)注規(guī)則依賴于編制者的主觀意識，標(biāo)注準(zhǔn)確率有待驗證.為了提高標(biāo)注準(zhǔn)確率，李曉黎等[11]根據(jù)上下文的相鄰詞及其詞性等信息來研究詞及詞性組合成的模式序列對詞性標(biāo)注的影響，提出應(yīng)用關(guān)聯(lián)規(guī)則挖掘Apriori算法自動獲取中文詞性標(biāo)注規(guī)則的方法，并將獲取的規(guī)則用于優(yōu)化訓(xùn)練語料庫，在一定程度實現(xiàn)了訓(xùn)練語料質(zhì)量的提升；然而，這種方法因時耗太長，僅適用于從小規(guī)模語料庫中提取詞性標(biāo)注規(guī)則.因此，筆者嘗試用FP-Growth算法從訓(xùn)練語料庫中自動獲取詞性標(biāo)注規(guī)則，以期為不同詞級規(guī)模的訓(xùn)練語料庫的優(yōu)化提供一種實用的詞性標(biāo)注規(guī)則獲取途徑.

1 關(guān)聯(lián)規(guī)則挖掘的相關(guān)定義及算法

1.1 相關(guān)定義

關(guān)聯(lián)規(guī)則挖掘[12]是指，從大量事務(wù)數(shù)據(jù)中挖掘出反映事務(wù)描述數(shù)據(jù)項之間相互依存和關(guān)聯(lián)的有價值的知識，發(fā)現(xiàn)存在于數(shù)據(jù)項或數(shù)據(jù)屬性間的有意義但事先未知且隱藏的關(guān)系.現(xiàn)引入如下關(guān)聯(lián)規(guī)則挖掘相關(guān)的定義[12]：

定義1數(shù)據(jù)庫中不可分割的最小單位信息稱為項目.

定義2一個數(shù)據(jù)庫中所有項目構(gòu)成的集合稱為項集，記作I={I1,I2,…,Im}.

定義3一系列具有唯一標(biāo)識的事務(wù)所組成的集合稱為事務(wù)數(shù)據(jù)庫，記作T={t1,t2,…,tn}.每一個事務(wù)ti包含的項集Ii都是I的子集.

定義4包含某個項集的事務(wù)個數(shù)稱為該項集的頻數(shù)(即支持度計數(shù)).

頻數(shù)反映了項集在不同事務(wù)中出現(xiàn)的次數(shù).

定義5形如X=>Y(其中XI且YI且X∩Y=?)的蘊(yùn)含式稱為關(guān)聯(lián)規(guī)則，其中X稱為規(guī)則前提，Y稱為規(guī)則結(jié)果.

關(guān)聯(lián)規(guī)則反映了Y中的項目跟隨X中的項目出現(xiàn)而出現(xiàn)的規(guī)律.

定義6事務(wù)集中同時包含項集X和Y的事務(wù)數(shù)與事務(wù)集中所有事務(wù)數(shù)之比稱為關(guān)聯(lián)規(guī)則X=>Y的支持度，記作S.

支持度反映X和Y中所含的項在事務(wù)集中的同現(xiàn)頻率.用戶指定規(guī)則必須滿足最小支持度閾值Smin，最小支持度閾值表示關(guān)聯(lián)規(guī)則的最低重要性.

定義7事務(wù)集中同時包含項集X和Y的事務(wù)數(shù)與包含X的事務(wù)數(shù)之比稱為關(guān)聯(lián)規(guī)則X=>Y的置信度，記作C.

置信度反映Y出現(xiàn)在包含X的事務(wù)集中的條件概率.用戶指定規(guī)則必須滿足最小置信度閾值Cmin，最小置信度閾值表示關(guān)聯(lián)規(guī)則的最低可靠性.

定義8若關(guān)聯(lián)規(guī)則X=>Y滿足S(X=>Y)≥Smin且C(X=>Y)≥Cmin，則稱之為強(qiáng)關(guān)聯(lián)規(guī)則；否則，稱之為弱關(guān)聯(lián)規(guī)則.

通常所說的關(guān)聯(lián)規(guī)則一般是指強(qiáng)關(guān)聯(lián)規(guī)則.

定義9事務(wù)數(shù)據(jù)庫的項集I中支持度不小于Smin的項集，稱為頻繁項集.

1.2 相關(guān)算法

關(guān)聯(lián)規(guī)則挖掘的關(guān)鍵在于發(fā)現(xiàn)所有頻繁項集.關(guān)聯(lián)規(guī)則挖掘算法基于項集空間理論，該理論的核心是頻繁項集的子集仍是頻繁項集，非頻繁項集的超集仍是非頻繁項集[12].Apriori算法和FP-Growth算法是挖掘頻繁項集的較經(jīng)典的算法，被廣泛應(yīng)用于商業(yè)、網(wǎng)絡(luò)安全等領(lǐng)域.

Apriori算法采用“試探”策略，通過不斷地構(gòu)建、篩選候選集來挖掘頻繁模式集.Apriori算法原理簡單，易于實現(xiàn)，但其瓶頸在于，獲取較長的頻繁模式必須以生成大量的候選短頻繁模式為基礎(chǔ)，需要多次掃描原始數(shù)據(jù)庫.當(dāng)原始數(shù)據(jù)量較大且存放于磁盤時，磁盤I/O次數(shù)太多，導(dǎo)致Apriori算法效率低下.

FP-Growth算法可以突破上述瓶頸.它根據(jù)事務(wù)包含的數(shù)據(jù)項構(gòu)建FP-tree結(jié)構(gòu)，對原始數(shù)據(jù)進(jìn)行壓縮，并使用條件模式基FP-tree挖掘頻繁模式，掃描原始數(shù)據(jù)庫2遍即可完成頻繁模式集的挖掘任務(wù).不同事務(wù)所共享的數(shù)據(jù)項在FP-tree中以重疊路徑出現(xiàn)，路徑重疊越多，說明數(shù)據(jù)壓縮效果越好.FP-tree較小時，F(xiàn)P-Growth算法直接從內(nèi)存中獲取頻繁模式集；FP-tree較大時，F(xiàn)P-Growth算法根據(jù)包含某個數(shù)據(jù)項的所有事務(wù)來構(gòu)造投射數(shù)據(jù)庫，將大數(shù)據(jù)庫分解成幾個可以放到內(nèi)存中的小數(shù)據(jù)庫，再分別對這幾個小數(shù)據(jù)庫執(zhí)行FP-Growth算法.

2 詞性標(biāo)注規(guī)則挖掘問題描述

2.1 詞性標(biāo)注規(guī)則的相關(guān)定義

詞性標(biāo)注規(guī)則反映文本中相鄰詞及其詞性之間的相互依存性和關(guān)聯(lián)性，其形式可以設(shè)計為由條件和結(jié)果構(gòu)成的布爾關(guān)聯(lián)規(guī)則.為了便于描述，給出如下集合說明[11]：

(1)單詞集W={wi|i=1，2，…，n}，詞性標(biāo)簽集T={ti|i=1，2，…，n}，模式集I=W∪T，其中wi，ti分別表示第i個詞和第i個詞性標(biāo)簽.

(2)已標(biāo)注文本T′={(wi，ti)|wi∈W，ti∈T}，其中ti是詞wi在該文本中對應(yīng)的詞性標(biāo)簽.

(4)模式集P={pi|i=1，2，…，n，且pi∈I+}，其中pi是詞與詞性標(biāo)簽的組合串.

參考文獻(xiàn)[11-12]，進(jìn)一步給出如下定義：

定義10給定模式A∈P，若其長度L(A)=k，則稱A為k-模式.

最基本的模式是項集(即若干個項目的集合).

定義11給定模式A∈P，集合Z={B|B∈P，且L(A)=L(B)}，用f(A)表示A出現(xiàn)的頻率，f(Z)表示所有長度為L(A)的模式出現(xiàn)的總頻率，稱A在同長度模式中所占的比例為A的支持度，即S(A)=f(A)/f(Z)).

定義12給定最小支持度Smin，稱集合Sfreqpatt={A|A∈P，S(A)≥Smin}為頻繁模式集，其中元素A稱為頻繁模式.

定義13若A，B均為頻繁模式，且A，B之間有關(guān)聯(lián)(關(guān)聯(lián)規(guī)則記為A=>B)，則該規(guī)則的支持度為S(A=>B)，可信度C(A=>B)=P(B|A)=f(AB)/f(A)，其中f(AB)是模式A，B同時出現(xiàn)的頻率.

定義14給定最小可信度Cmin，若C(A=>B)≥Cmin，則稱關(guān)聯(lián)規(guī)則A=>B是值得信賴的規(guī)則.

定義15從模式集I中取k-模式Ii=(a1a2，…，ak-1ak)，其中第k個詞wk的詞性標(biāo)簽ak∈T，則詞性標(biāo)注規(guī)則定義為

(1)

(1)式的含義是，若串中的前k-1個詞或詞標(biāo)簽組成的序列為模式(a1a2，…，ak-1ak)，則取ak為第k個詞wk的詞性標(biāo)簽.

定義16給定大于Smin的正數(shù)M，若規(guī)則A=>B的支持度S(A=>B)B為個性規(guī)則，反之稱為共性規(guī)則；若個性規(guī)則A=>B滿足C(A=>B)>Cmin，則稱之為個性可靠規(guī)則；若共性規(guī)則A=>B滿足C(A=>B)>Cmin，則稱之為共性可靠規(guī)則.

2.2 詞性標(biāo)注規(guī)則設(shè)計

應(yīng)用關(guān)聯(lián)規(guī)則挖掘算法自動獲取詞性標(biāo)注規(guī)則的過程，就是從已標(biāo)注詞性的訓(xùn)練語料庫中挖掘不同長度的頻繁模式，并根據(jù)挖掘結(jié)果生成共性可靠的詞性標(biāo)注規(guī)則的過程.規(guī)則的適用范圍和可靠程度分別用支持度和可信度表示.簡便起見，本研究中只討論長度最多為3的前制約情況，即由前面的1個或2個詞的詞性來確定當(dāng)前詞的詞性.表1給出了對于不同長度頻繁模式生成的詞性標(biāo)注規(guī)則的形式及示例.

表1 對于不同長度頻繁模式生成的詞性標(biāo)注規(guī)則的形式及示例

3 詞性標(biāo)注規(guī)則獲取方法設(shè)計

3.1 基本原理

利用關(guān)聯(lián)規(guī)則挖掘FP-Growth算法獲取詞性標(biāo)注規(guī)則，本質(zhì)上就是以詞性標(biāo)注訓(xùn)練語料庫作為事務(wù)數(shù)據(jù)庫，從事務(wù)數(shù)據(jù)庫中挖掘由詞與詞性標(biāo)簽的組合串構(gòu)成的強(qiáng)關(guān)聯(lián)規(guī)則的過程.該過程可分為候選模式集計算、頻繁模式集獲取和關(guān)聯(lián)規(guī)則生成3個階段.首先，用FP-Growth算法掃描事務(wù)數(shù)據(jù)庫，構(gòu)建用于存儲候選模式集的模式前綴樹FP-tree，獲取訓(xùn)練集中每個句子各個長度的模式，以得到候選模式集；然后，構(gòu)建條件模式基FP-tree，從候選模式集中挖掘大于Smin的各種長度模式的頻繁模式集；最后，按定義15對每個頻繁模式構(gòu)建形如“(a1a2，…，ak-1ak)=>(wk，ak)”的關(guān)聯(lián)規(guī)則，若該規(guī)則滿足C((a1a2，…，ak-1ak)=>(wk，ak))>Cmin，則得到一條有效的詞性標(biāo)注規(guī)則，將其加入規(guī)則庫.

3.2 過程描述

Step 1 若S′為空集，則轉(zhuǎn)step 7.

Step 4 若K-L+1>M，則取出“(wL，tL)，… ，(wL+W-1，tL+W-1)”，L←M；否則，取出“(wL，tL)，… ，(wK，tK)”，L←K-L+1，繼續(xù)構(gòu)建模式前綴樹.

Step 5 Forj=2 TOL循環(huán)執(zhí)行“從模式前綴樹中取長度為j且包含(wL，tL)的模式串P；Pcount←Pcount+1；Scandpatt←Scandpatt∪{P}；Nsum[j]←Nsum[j]+1”.

Step 6L←L+1，轉(zhuǎn)step 3.

Step 7 若Scandpatt為空集，則轉(zhuǎn)step 10.

Step 8 取P∈Scandpatt，構(gòu)建條件模式基樹，Scandpatt←Scandpatt-{P}.

Step 9 從條件模式基樹根出發(fā)，逐個檢查i-模式，若(Pcount/Nsum[i])>Smin，則執(zhí)行Sfreqpatt←Sfreqpatt∪{P}，再轉(zhuǎn)step 7；否則，直接轉(zhuǎn)step 7.

Step 10 若Sfreqpatt為空集，則算法結(jié)束.

Step 11 任取P=(a1a2，…，ak-1ak)∈Sfreqpatt，Sfreqpatt←Sfreqpatt-{P}.

Step 12 若ak∈T且C(a1a2，…，ak-1ak)>Cmin，則先將“if (a1a2，…，ak-1ak) then (wk，ak)”加入到詞性標(biāo)注規(guī)則集，再轉(zhuǎn)step 10；否則，直接轉(zhuǎn)step 10.

Step 1～6對應(yīng)候選模式集生成步驟，step 7～10對應(yīng)頻繁模式集計算步驟，step 11～12實現(xiàn)從頻繁模式集中提取詞性標(biāo)注規(guī)則并加入到規(guī)則集.

4 仿真對比實驗

為了驗證基于FP-Growth算法的詞性標(biāo)注規(guī)則獲取方法(方法1)的可行性和有效性，將其與基于Aprior算法的詞性標(biāo)注規(guī)則獲取方法(方法2)進(jìn)行對比實驗.實驗在Intel(R)Core(TM)i7-4720 HQ CPU @ 2.60 GHz、8G 內(nèi)存、Win10 操作系統(tǒng)條件下進(jìn)行，采用 Python3.8.5 編程實現(xiàn)算法；訓(xùn)練語料庫選用來自 https:∥github.com/liwenzhu/corpusZh的已標(biāo)注詞性的中文語料庫corpusZh.支持度和可信度均設(shè)置為0.7，針對0.1萬、0.2萬、1萬、10萬、100萬詞級規(guī)模的訓(xùn)練語料庫得到的對比實驗結(jié)果見表2.

表2 對比實驗結(jié)果

由表2可知：

(1)對于 0.1萬、0.2萬和1萬詞級規(guī)模的訓(xùn)練語料庫，方法1和方法2獲取的詞性標(biāo)注規(guī)則條數(shù)相等，但耗時存在萬倍以上差別.

(2)對于10萬和100萬詞級規(guī)模的訓(xùn)練語料庫，方法2在本實驗環(huán)境下運行時出現(xiàn)內(nèi)存異?，F(xiàn)象，無法獲取任何規(guī)則；但方法1在754 s內(nèi)從10萬詞級語料庫中成功獲取3 741條規(guī)則，在697 834 s內(nèi)從100萬詞級語料庫中獲取35 286條規(guī)則.

顯然，方法1可行且效率優(yōu)于方法2.

5 結(jié)語

為了提高詞性標(biāo)注模型所需的訓(xùn)練語料的質(zhì)量，筆者設(shè)計了一種基于FP-Growth算法的詞性標(biāo)注規(guī)則自動獲取新方法，并以中文詞性標(biāo)注規(guī)則自動獲取為例，將新方法與基于Apriori算法的詞性標(biāo)注規(guī)則獲取方法進(jìn)行了對比實驗.實驗結(jié)果表明，新方法能夠有效彌補(bǔ)基于Apriori算法的詞性標(biāo)注規(guī)則獲取方法因多次掃描數(shù)據(jù)庫而導(dǎo)致的耗時長、效率低，且僅適用于萬詞級以下小規(guī)模語料庫的不足，即使是面對百萬詞級語料庫，依然可以在合理的時間內(nèi)獲取有效的詞性標(biāo)注規(guī)則.顯然，基于FP-Growth算法的方法適用于從較大規(guī)模、已標(biāo)注的訓(xùn)練語料庫中以關(guān)聯(lián)規(guī)則的形式獲取詞性標(biāo)注知識，能為后續(xù)詞性標(biāo)注技術(shù)的研究提供新思路.