大規(guī)模詞序列中基于頻繁詞集的特征短語抽取模型

余琴琴,彭敦陸,劉 叢

(上海理工大學(xué) 光電信息與計算機工程學(xué)院,上海 200093)

1 引 言

近年來,文本數(shù)據(jù)的處理越來越受人們關(guān)注,如何將非結(jié)構(gòu)化的文本轉(zhuǎn)化為結(jié)構(gòu)化數(shù)據(jù)是許多應(yīng)用中的關(guān)鍵步驟之一.文本數(shù)據(jù)的特征選擇和特征抽取是將文本數(shù)據(jù)轉(zhuǎn)化為結(jié)構(gòu)化數(shù)據(jù)的關(guān)鍵實現(xiàn)技術(shù).在文本處理中,特征抽取本質(zhì)上是選取能反映文檔內(nèi)容的重要詞匯或短語,也稱為關(guān)鍵詞抽取.利用抽取的詞匯或短語可以實現(xiàn)文本內(nèi)容輔助理解,因而特征抽取是信息檢索系統(tǒng)和自然語言處理的主要任務(wù)之一,在文本聚類、分類、摘要生成等方面具有廣泛用途[1].

盡管目前針對文本特征抽取的算法有很多,如TF-IDF、互信息、信息熵等,但這些算法不能體現(xiàn)文檔中共現(xiàn)詞之間的關(guān)系.與單個詞相比,短語表達(dá)的信息更豐富、更準(zhǔn)確,在辨識力和合理性方面也具有明顯優(yōu)勢.短語通常由兩個及以上的詞組成,事實表明,在不同文本中經(jīng)常共現(xiàn)的詞往往存在著一定的相關(guān)性[2].基于這一考慮,很多研究者使用關(guān)聯(lián)規(guī)則挖掘方法研究共現(xiàn)詞之間的關(guān)系,特別是針對詞序列中的頻繁詞集的挖掘?qū)斫馕谋緮?shù)據(jù)的內(nèi)容和情節(jié)具有重要意義.

傳統(tǒng)的關(guān)聯(lián)規(guī)則挖掘算法有很多,如Apriori、FP-Tree算法以及基于這兩個經(jīng)典算法改進(jìn)的一些算法,它們可以有效地挖掘數(shù)據(jù)庫中的頻繁項集,但是這類算法不能完全適用于詞序列的頻繁項集挖掘.在頻繁項集挖掘任務(wù)中,構(gòu)成事務(wù)的項集是不重復(fù)、無序的,而詞序列具有有序性的特點,使得無法直接使用傳統(tǒng)的頻繁項集算法挖掘來發(fā)現(xiàn)詞序中的頻繁詞項集.迄今,也有一些研究是針對文本序列挖掘展開的,這些研究是將相鄰詞進(jìn)行組合作為頻繁k-項集,但對于實際的文本序列,這種方式不能很好的體現(xiàn)頻繁詞項集所表達(dá)的語義.基于這一問題,在挖掘頻繁詞集時,不僅考慮相鄰詞的組合,還考慮不相鄰詞間的組合,這與本文處理的中文文本數(shù)據(jù)中組成短語的詞語通常不相鄰、共現(xiàn)率高的特點有關(guān).在中文詞序列中,有序詞可能在一個序列中重復(fù)出現(xiàn),還有同義詞這一因素的存在,使得挖掘頻繁詞項集成為挑戰(zhàn).另一方面,盡管頻繁項集的挖掘算法有很多,但隨著文本數(shù)據(jù)量的劇增,傳統(tǒng)集中式的頻繁項集挖掘算法無法保證計算效率,有必要研究新型分布式大規(guī)模的文本數(shù)據(jù)頻繁詞項集的挖掘算法.MapReduce是由Goolge提出的具有代表性的分布式并行計算編程模型,采用MapReduce模型可以高效地處理基于頻繁詞項集的文本序列特征抽取.目前,這方面研究開展得還不多,本文將MapReduce模型應(yīng)用到大規(guī)模詞序中的頻繁詞項集挖掘中,實現(xiàn)基于頻繁詞集的特征短語挖掘算法.結(jié)合實際法律文本處理應(yīng)用場景,采用海量案件文本數(shù)據(jù)進(jìn)行實驗驗證,表明所提算法具有較好的計算效果.

2 相關(guān)工作

文本的特征抽取在文本挖掘領(lǐng)域占有重要的地位,許多關(guān)于自然語言處理(Natural Language Process,簡稱NLP)中都提倡運用文本特征項來表示文本,以達(dá)到降維的目的.國內(nèi)外已經(jīng)有很多關(guān)于特征抽取方法的研究,按照抽取粒度分為基于關(guān)鍵詞、關(guān)鍵短語和關(guān)鍵句子的抽取.與關(guān)鍵詞相比,關(guān)鍵短語表達(dá)的信息更豐富、更準(zhǔn)確,具有較高辨識力和合理性.在一些應(yīng)用場景,由于文本數(shù)據(jù)的長度受限,相對而言,抽取關(guān)鍵句子意義不大,所以許多工作更加注重抽取關(guān)鍵短語的方法研究.

根據(jù)特征抽取方法的發(fā)展,可將其分為兩大類,基于語法規(guī)則的方法和基于統(tǒng)計信息的方法.針對第一種方法,早期是通過科學(xué)家和語言學(xué)家寫出合理的語言規(guī)則,現(xiàn)在可以通過預(yù)定義一些詞性標(biāo)注規(guī)則來產(chǎn)生名詞性的短語.然而,這些基于規(guī)則的方法通常在領(lǐng)域范圍內(nèi)是受限的,往往還依賴某些NLP的特征,例如,采用句法依存解析樹來提高短語抽取的準(zhǔn)確性[3].在第二種方法中,文獻(xiàn)[4]提出了基于序列模式挖掘的文本語言模式識別方法,并將其運用于詩歌、信、小說等文本體裁,但對于其他領(lǐng)域的文本挖掘存在局限性.文獻(xiàn)[5]中F.Ye等人為解決采用傳統(tǒng)語言方法,將關(guān)鍵字作為彼此獨立的單元,相互間缺乏語義聯(lián)系的問題,提出面向領(lǐng)域的方法適用于某些特定領(lǐng)域,特別是充分利用關(guān)聯(lián)規(guī)則挖掘集成簡單、容易解釋和理解的優(yōu)勢,并能有效地實現(xiàn)捕捉數(shù)據(jù)集之間的重要關(guān)系.文獻(xiàn)[6,7]中研究了在文本集合上將頻率統(tǒng)計信息與語料庫的各種統(tǒng)計信息相結(jié)合來評估短語質(zhì)量.盡管此方法不依賴語言具體特性或特定領(lǐng)域的規(guī)則或大訓(xùn)練集,且可以有效地處理大規(guī)模語料庫,對于短語質(zhì)量的不確定性評估還存在問題.考慮到上述問題,在文獻(xiàn)[8]中Liu等人提出了SegPhrase算法和SegPhrase+算法,一種基于頻繁模式挖掘算法來發(fā)現(xiàn)有意義的短語,由于在挖掘短語的過程中,它們忽略了文本數(shù)據(jù)中詞的先后順序,產(chǎn)生了大量的候選短語,也未考慮詞的重要程度.為了彌補這一缺陷,通過短語的質(zhì)量評估方法來糾正基于頻繁模式挖掘方法進(jìn)行短語抽取的不足,以此達(dá)到提高短語抽取質(zhì)量的目的.還有許多的研究關(guān)注抽取短語的排名算法,但這些算法忽略了候選短語識別的正確性這一影響因素[9].

本文試圖通過改進(jìn)傳統(tǒng)的頻繁項集挖掘算法來抽取高質(zhì)量的文本特征短語.傳統(tǒng)的頻繁項集挖掘算法按有無權(quán)重可分為兩類:無權(quán)重挖掘和加權(quán)挖掘.無權(quán)重挖掘代表算法有基于Apriori算法思想和基于模式增長思想(如FPGrowth);加權(quán)挖掘算法,即數(shù)據(jù)庫中的每個項集帶有不同的權(quán)重,權(quán)重表示他們的重要程度.考慮到詞序列中詞的先后順序,而且在領(lǐng)域文本數(shù)據(jù)中,每個詞的重要程度也不同,所以基于加權(quán)頻繁模式挖掘的思想,提出了一種基于詞序列的頻繁短語挖掘算法,挖掘出高質(zhì)量領(lǐng)域文本特征短語.在此基礎(chǔ)上,針對海量文本的抽取效率以及內(nèi)存消耗問題,將該算法結(jié)合MapReduce計算模型,實現(xiàn)大規(guī)模詞序列特征短語識別.

3 頻繁短語挖掘算法

在文本中,經(jīng)常同時出現(xiàn)的兩個或多個關(guān)鍵詞之間往往存在一定的相關(guān)性.在傳統(tǒng)的頻繁項集挖掘算法中,數(shù)據(jù)庫中各項具有同質(zhì)性,但在詞序列中,每個詞扮演著不同的成分,對文本內(nèi)容理解的重要性也不同,通常權(quán)重較大的一些詞較為重要,即反映的文本內(nèi)容能力較強,因此,在詞序列的頻繁項集挖掘中,采用改進(jìn)加權(quán)關(guān)聯(lián)規(guī)則算法挖掘有意義的特征短語.

3.1 問題描述

設(shè)∑={S1,S2,…,SN}為詞序列集,詞序列S由一個或多個有序的詞集組成,記為S={is1,is2,…,isn}.每個詞稱為一個詞項集,I={i1,i2,…,im}表示詞序列集中所有詞項集的集合.與之對應(yīng)的詞項集的權(quán)重集為W={wi1,wi2,…,wim},其中,wij表示了詞項集ij的重要程度,wij∈[0,1],j={1,2…,m}.設(shè)p為短語由一個或多個詞項集組成.指定最小加權(quán)支持度閾值和最小語義關(guān)聯(lián)強度閾值分別為wminsup和wminsaw.

定義1.詞項集X的加權(quán)支持度WS(X),表示詞序列集中包含該詞項集的詞序列權(quán)重的總和:

(1)

其中?ik∈X,Nx表示詞項集X在詞序列集中的計數(shù);N是詞序列集的總數(shù).

定義2.若詞序列中包含詞項集X∪Y,則其加權(quán)置信度WC(X→Y)為詞項集X∪Y的加權(quán)支持度與詞項集X的加權(quán)支持度的比值.計算公式如下:

(2)

定義3.若詞項集X為短語,則其語義關(guān)聯(lián)強度SAW(X)定義為:

SAW(X)=α·WS(X)+(1-α)·WC(X)

(3)

其中,|X|≥2為短語個數(shù),α是用來調(diào)整支持度與置信度之間的重要程度參數(shù),0<α<1.

定義4.順序性.若詞項集X和詞項集Y可組合成一個有意義的短語,則短語XY≠短語YX.例如:“被盜”、“手機”可分別組成兩個不同的短語,“被盜手機”和“手機被盜”.

定義5.無重復(fù)性.假定一個短語序列P={p1,p2,…,pl},則滿足pi∩pj=?,其中1≤i,j≤l,且i≠j.

定義6.同義性.如果詞項集X和詞項集Y為同義詞,則包含詞項集X或Y的短語序列P在詞序列中的計數(shù)為min {pi,Nx+Ny}.

定義7.若詞項集X的加權(quán)支持度大于最小加權(quán)支持度閾值,即WS(X)≥wminsup,則稱X為加權(quán)頻繁詞項集.

定義8.若詞項集X的語義關(guān)聯(lián)強度滿足最小語義關(guān)聯(lián)閾值,即SAW(X)≥wminsaw,則詞項集X被稱為特征短語.

3.2 頻繁短語挖掘算法

傳統(tǒng)的加權(quán)頻繁模式挖掘算法,如MINWAL(O)、MINWAL(W)算法[10],因為每個項集的權(quán)值不同導(dǎo)致了加權(quán)頻繁項目集的子集可能不是加權(quán)頻繁項集,這使得其無法滿足Apriori算法中頻繁項向下封閉的性質(zhì).在此通過改進(jìn)加權(quán)支持度的計算方式,使其在產(chǎn)生頻繁項集時可以保持頻繁項集的向下封閉特性.此外,當(dāng)交易數(shù)據(jù)較大時,在頻繁項集的計算過程中會產(chǎn)生大量的候選項集,占用大量的內(nèi)存和計算時間,所以候選項的剪枝過程顯得尤為重要.文獻(xiàn)[11]中提出的FAMR算法是對Apriori算法在MapReduce環(huán)境上運行的改進(jìn).借鑒FAMR算法中通過篩選出1-頻繁項集過濾非頻繁項集減少候選項集和內(nèi)存消耗的思想,并結(jié)合詞序列集上順序性和重復(fù)性的特點對產(chǎn)生候選項進(jìn)行剪枝,將其運用到加權(quán)關(guān)聯(lián)規(guī)則算法中,本文提出基于詞序列的頻繁短語挖掘算法(WS-FPMA).

該算法的主要思想是:首先找出所有的1-頻繁詞項集,在下次掃描詞序列集時,將每個詞序列中的非頻繁詞項集進(jìn)行邏輯上的移除,然后在移除后的詞序列集上產(chǎn)生k-頻繁候選詞集.另外,在實際情況中,一個短語一般為兩個詞或三個詞組合而成.當(dāng)詞長度越長,即k越大時,滿足條件的k-詞項集也會越來越少.通過上述約束,兩次大量減少候選項集,會顯著提高算法的計算效率.算法的詳細(xì)描述見圖1.

圖1 WS-FPMA 算法Fig.1 Algorithm of WS-FPMA

算法說明:算法第(6)行表示在第k次掃描詞序列集時,將每個詞序列中的非頻繁的詞項集移除,然后產(chǎn)生k-項頻繁候選詞集.在生成k-頻繁詞項集時,根據(jù)定義4和定義5,應(yīng)滿足以下兩個條件:一是若詞序列中沒有重復(fù)出現(xiàn)的詞,則一個詞只能與其后面的詞進(jìn)行組合;二是若詞序列中有相同的詞重復(fù)出現(xiàn),則以第i個相同的詞(i>2)為分界線分別進(jìn)行組合,組合方法同上面一樣.需要注意的是,通常詞序列中每個詞都是具有不同的意義,即使重復(fù)出現(xiàn)在詞序列中的詞,不管出現(xiàn)幾次計數(shù)均為1,例如:無 駕駛 資格證 駕駛 小型 轎車,從第二個“駕駛”處劃分成兩部分,分別進(jìn)行組合,在計算“駕駛”的支持度計數(shù)時仍計算為1.算法第(7)行表示組合成候選頻繁詞集后,進(jìn)行支持度計數(shù)時,根據(jù)定義6來給出支持度的最后計數(shù)結(jié)果,避免了頻繁詞的同義詞作為非頻繁詞而被過濾掉的情況,這里的同義詞是根據(jù)《哈工大信息檢索研究室同義詞詞林?jǐn)U展版》中整理的同義詞典來判斷的.算法第(11)行表示將頻繁詞集生成滿足語義關(guān)聯(lián)強度的特征短語.

4 基于MapReduce的頻繁短語挖掘算法

實際應(yīng)用中,運用在進(jìn)行頻繁模式挖掘時,隨著原始數(shù)據(jù)量的快速增長,會使得挖掘算法的問題集中提高執(zhí)行效率和I/O負(fù)載上.特別地,在單處理器上即使使用優(yōu)化后的串行算法也無法滿足挖掘性能的需求,利用多處理器系統(tǒng)進(jìn)行并行計算,是提高挖掘效率的有效途徑[12].第3部分中提出WS-FPMA算法,隨著數(shù)據(jù)量的增加,會發(fā)生內(nèi)存溢出而終止,而且運行的時間也難以保證.基于上述考慮,下面對該算法進(jìn)行改進(jìn),實現(xiàn)并行環(huán)境下對大規(guī)模的詞序列集進(jìn)行頻繁詞集挖掘的計算.

4.1 MR-FPMA算法框架

給定一個詞序列數(shù)據(jù)集,采用MapReduce的并行計算環(huán)境,對WS-FPMA算法進(jìn)行MapReduce改造,需要經(jīng)過2步來完成特征短語的挖掘,圖2描述了算法的基本計算模型.具體過程如下:

第1步.并行產(chǎn)生1-項頻繁詞項集.此過程多節(jié)點并行掃描一次數(shù)據(jù)庫,統(tǒng)計其中每個詞的次數(shù),得到大于支持度閾值的1-項頻繁詞集.

第2步.并行產(chǎn)生k-項頻繁詞項集.在上一步的基礎(chǔ)上對詞序列集掃描時進(jìn)行邏輯上的修剪,每個節(jié)點上的各詞序列產(chǎn)生滿足組合條件的k-項候選頻繁詞集,通過設(shè)定的閾值篩選滿足條件的k-項頻繁詞集作為輸出結(jié)果.

圖2 MR-FPMA流程Fig.2 MR-FPMA process

4.2 并行產(chǎn)生1-項頻繁詞項集

對應(yīng)于WS-FPMA算法中的第2到第4步可通過一個MapReduce過程獲得1-項頻繁詞集.在Map階段讀取詞序列集,輸出中key為每個詞項集,將該詞的權(quán)重和出現(xiàn)的次數(shù)作為value.Reduce函數(shù)負(fù)責(zé)將相同的key合并,統(tǒng)計每個詞的總次數(shù),并判斷是否大于設(shè)定的支持度閾值,將大于閾值的詞的作為輸出結(jié)果,算法偽代碼如圖3.

圖3 產(chǎn)生1-項頻繁詞算法Fig.3 Algorithm of 1-frequent words

4.3 并行挖掘k-項頻繁詞項集

從圖2中可看出,該階段的處理過程和上階段基本一致,只是Map階段有所不同.Map函數(shù)將上階段產(chǎn)生的1-項頻繁詞集作為一個全局共享的輸入數(shù)據(jù),同時接收詞序列集.對存在多個1-頻繁詞項集的詞序列,依次按該序列中出現(xiàn)先后順序?qū)㈩l繁詞項集進(jìn)行組合生成長度為2-k的候選詞項集.將候選詞項集作為key,候選詞項集的權(quán)重和和出現(xiàn)次數(shù)作為value,value的計算方式依然采用定義6進(jìn)行計算.處理完后,將具有相同key值的候選項集發(fā)送到同一個Reduce節(jié)點進(jìn)行合并產(chǎn)生最終結(jié)果,其實現(xiàn)方式與第一步相同.這一階段的Map函數(shù)的偽代碼見圖4.

圖4 產(chǎn)生k-項頻繁詞Map函數(shù)Fig.4 Map function for generating k-frequent words

5 實驗結(jié)果與分析

5.1 數(shù)據(jù)集

實驗中使用的數(shù)據(jù)集是從全國各級法院網(wǎng)站下載的真實案件裁判文書集,該數(shù)據(jù)集有300萬篇覆蓋10大主要罪名的判決書.

圖5 文本預(yù)處理的流程圖Fig.5 Preprocess for judicial documents

實驗任務(wù)是抽取出案件的案情特征短語,在正式抽取之前,需要對實驗數(shù)據(jù)進(jìn)行預(yù)處理,圖5是進(jìn)行預(yù)處理的流程圖.在提取出每篇判決書中關(guān)于案情描述的段落文本后,對段落文本進(jìn)行分詞,去除停用詞、用TF-IDF過濾掉一些低頻詞及通用詞.然后,以主要的標(biāo)點符號,包括逗號、分號、句號,將分詞后的文本劃分成多個序列,對每個序列利用詞性標(biāo)注去除人名、地名、時間等,每個序列中僅保留動詞和名詞詞性的詞語.處理后的詞序列與短語的順序性(定義4),使得所有候選短語均與組成短語的詞集在文本中出現(xiàn)的順序保持一致,這樣可以保證對短語有較好的語法規(guī)則約束.

5.2 實驗結(jié)果分析

實驗中短語的最大詞語數(shù)N設(shè)置為3較為符合中文短語的特點,共做了三組實驗.第一組考察不同閾值下WS-FPMA算法抽取短語的數(shù)目;第二組利用準(zhǔn)確率和召回率指標(biāo)衡量該算法同其他短語抽取算法比較抽取短語的效果;第三組將該算法與抽取短語結(jié)果較為優(yōu)秀的算法SegPhrase算法進(jìn)行比較計算效率,并驗證該算法在并行環(huán)境下的MR-FPMA算法的計算效率的提升.下面對實驗結(jié)構(gòu)進(jìn)行分析.

實驗1.不同閾值下WS-FPMA算法的實現(xiàn)效果.

通常,不同的閾值對頻繁詞項集數(shù)和特征短語數(shù)目的挖掘結(jié)果有很大的影響.在此,為將計算過程中的產(chǎn)生短語數(shù)控制在一個合適的范圍,便于考察抽取短語的質(zhì)量,隨機抽取了部分文檔6.54M(10類文檔共1萬篇)進(jìn)行了本實驗,將WS-FPMA算法和Apriori算法進(jìn)行對比測試,實驗結(jié)果如圖6.

圖6 不同閾值在頻繁詞集數(shù)上的比較Fig.6 Number of frequent words with different thresholds

從圖6可見wminsup變化時,頻繁詞集的數(shù)目變化情況.總體來看,兩種算法都是wminsup越大,得到的頻繁詞集數(shù)目越少.但在支持度閾值一定時,提出的WS-FPMA算法比Apriori算法得到的頻繁詞集要少,通過具體驗證發(fā)現(xiàn)這些頻繁詞集都是有效詞集.因為每個詞項集具有不同的權(quán)重,且重要的詞具有較高的權(quán)重,所以挖掘出的頻繁詞項集質(zhì)量較高,而不是返回一些頻率較高但表征性較弱的詞項集.圖6中當(dāng)閾值在0.35至0.4之間時,曲線較為平緩,且挖掘的頻繁詞集較為有效,因此實驗中將wminsup分別設(shè)置為0.35,0.38和0.4對挖掘出的短語數(shù)目和質(zhì)量進(jìn)行了專門的考察.

支持度和置信度反映了關(guān)聯(lián)程度的強弱,若閾值設(shè)置得過低,會將關(guān)聯(lián)關(guān)系較弱的規(guī)則也放入到結(jié)果集中;若設(shè)置得過高,則導(dǎo)致結(jié)果集中的規(guī)則過少不能反映實際情況.而定義3中wminsaw是支持度、置信度的加權(quán)和,參數(shù)α為權(quán)重取值的重要因子.綜上,本實驗中結(jié)合頻繁詞項集的共現(xiàn)關(guān)系特征,將α設(shè)置為{0.45,0.5,0.55}、wminsaw設(shè)置為{0.35,0.4,0.45}.根據(jù)二者與wminsup的組合關(guān)系,分別進(jìn)行了三組共九個實驗考察了它們對挖掘出的短語數(shù)目的影響.從圖7中可看出,當(dāng)α = 0.45時,其挖掘短語的數(shù)目較多,隨著支持度閾值wminsup和語義關(guān)聯(lián)強度閾值wminsaw的增大,短語的數(shù)目逐漸減少.當(dāng)wminsaw=0.4時,雖然其短語數(shù)目相對較少,卻體現(xiàn)出短語之間的共現(xiàn)性和相關(guān)性,并保留了較多的高質(zhì)量短語.隨著wminsaw繼續(xù)增大,抽取的短語質(zhì)量較高但數(shù)量較少,會導(dǎo)致部分特征短語被忽略了.由此可見,將wminsup、wminsaw和α分別設(shè)置為0.35、0.4和0.45較為合理.

圖7 不同閾值在挖掘短語數(shù)上的比較Fig.7 Number of phrases with different thresholds

實驗2.WS-FPMA算法在準(zhǔn)確率和召回率上的比較.

為了驗證所提出的基于詞序列挖掘關(guān)鍵短語算法(WS-FPMA)抽取效果,將該算法與已有KEA算法[13]、TextRank算法[14]和SegPhrase算法進(jìn)行比較,結(jié)果如表1和圖8所示.

表1 各算法的抽取結(jié)果示例Table 1 Examples of extraction results

首先以對段落“被告人張某攜帶一把彈簧刀在福州市晉安區(qū)鼓山鎮(zhèn)某店門口,乘坐被害人宋某所駕駛的某出租車,當(dāng)車行駛至倉山區(qū)義序望峰路上的偏僻處時,張某將該車車鑰匙拔下,并持刀、架在被害人宋某的脖子上進(jìn)行威脅,搶走被害人宋某身上一部聯(lián)想A60型手機及現(xiàn)金人民幣91元.”抽取為例,從表1中可見:

KEA和TextRank算法只能抽取出單個詞語,無法抽取短語,對原文本的語義表達(dá)較弱,而SegPhrase和WS-FPMA算法抽取的是頻繁詞或短語,但相比前者WS-FPMA抽取的結(jié)果更加完整,能夠更好地表達(dá)原文的語義.

從圖8可以看出,四種算法的總體趨勢是相似的,即準(zhǔn)確率和召回率呈現(xiàn)出負(fù)相關(guān)關(guān)系.通過比較可見,提出的WS-FPMA算法的計算效果要優(yōu)于其它三種算法.由于考慮單個詞在詞序列中的實際語義,以及同義詞的計數(shù),實驗表明,所提算法抽取較多的短語,且在召回率一定的情況下,具有較高的準(zhǔn)確率.

圖8 召回率和準(zhǔn)確率上的比較Fig.8 Comparison of precision and recall

實驗3.考察MR-FPMA算法的計算效率.

為說明前文提出的在MapReduce環(huán)境下實現(xiàn)WS-FPMA的并行計算方法,在計算效率上有著顯著的提高,本組實驗分別選取SegPhrase算法、WS-FPMA算法與之進(jìn)行比較.

圖9 運行時間的比較Fig.9 Comparison of runtime for different size of data

圖9顯示的實驗結(jié)果可以看出,所有算法隨著文檔數(shù)據(jù)量的不斷增加,算法的運行時間會越來越長.在相同計算規(guī)模下,SegPhrase算法需要的計算時間最長,這是因為其在候選短語挖掘時產(chǎn)生了大量的非頻繁候選集.WS-FPMA算法在數(shù)據(jù)量不是很大的情況下,其運行性能要比SegPhrase略高一點.但在文檔量逐漸增大時,會發(fā)生內(nèi)存溢出的問題,所以運行時間量無法確定.由于MR-FPMA算法是基于 MapReduce計算模型的,不會出現(xiàn)內(nèi)存溢出的問題,同時還具有較好的可伸縮性.圖9表明,采用8個Reduce節(jié)點的MR-FPMA-8和比采用5個Reduce節(jié)點節(jié)點的MR-FPMA-5具有更好的性能,且在實驗過程中未出現(xiàn)內(nèi)存溢出現(xiàn)象.

6 結(jié) 論

從大規(guī)模的文本數(shù)據(jù)中提取出特征短語,在海量文本數(shù)據(jù)挖掘和分析中具有重要理論研究意義和實現(xiàn)應(yīng)用價值.通過分析發(fā)現(xiàn),中文文本語句中的詞語存在著有序性、可重復(fù)性和同義性等特點,結(jié)合詞語在句子中的角色表達(dá),通過對加權(quán)頻繁詞集算法進(jìn)行改進(jìn),提出基于詞序列的頻繁短語挖掘算法——WS-FPMA.同時,為了保證處理海量文本數(shù)據(jù)的計算效率,利用MapReduce計算模型思想,提出了基于MapReduce的頻繁短語挖掘算法——MR-FPMA.實驗表明,WS-FPMA可以較好地提升特征短語的挖掘質(zhì)量,但其內(nèi)存消耗較大.實驗表明,無論是計算效率,還是挖掘效果,MR-FPMA均有較好的表現(xiàn).在今后的工作中,將研究短語質(zhì)量評估的量化模型,通過對所提算法進(jìn)行優(yōu)化,以獲得更高的計算效率和更好的計算效果.

：

[1] Zakariae A M,Bouchra F,Brahim O.Automatic keyphrase extraction:an overview of the state of the art[C].2016 4th IEEE International Colloquium on Information Science and Technology(CiSt),2016:306-313.

[2] Xu Ya-bin,Li Zhuo,LV Fei-fei,et al.Rapid discovery of new topics in microblogs based on frequent words sets clustering[J].Systems Engineering Theory and Practice,2014(S1):276-282.

[3] Koo T,Pérez X C,Collins M.Simple semi-supervised dependency parsing[C].Association for Computational Linguistics,2008:595-603.

[4] Quiniou S,Cellier P,Charnois T,et al.What about sequential data mining techniques to identify linguistic patterns for stylistics[C].International Conference on Computational Linguistics and Intelligent Text Processing,2012:166-177.

[5] Ye F,Xiong J,Xu L.A text association rules mining method based on concept algebra[C].Green Computing and Communications,IEEE,2013:2153-2158.

[6] Danilevsky M,Wang C,Desai N,et al.Automatic construction and rankingoftopicalkeyphrasesoncollectionsofshortdocuments[M].Proceedings of the 2014 SIAM International Conference on Data Mining,2014:398-406.

[7] El-Kishky A,Song Y,Wang C,et al.Scalable topical phrase mining from text corpora[J].Proceedings of the Vldb Endowment,2014,8(3):305-316.

[8] Liu J,Shang J,Wang C,et al.Mining quality phrases from massive text corpora[C].ACM SIGMOD International Conference on Management of Data.ACM,2015:1729-1744.

[9] Ali C B,Wang R,Haddad H.A two-level keyphrase extraction approach[M].Computational Linguistics and Intelligent Text Processing,Springer International Publishing,2015:390-401.

[10] Cai C H,Fu A W C,Cheng C H,et al.Mining association rules with weighted items[C].Database Engineering and Applications Symposium,1998,Proceedings,IDEAS′98,International,IEEE,2000:68-77.

[11] Yu R M,Lee M G,Huang Y S,et al.An efficient frequent patterns mining algorithm based on MapReduce framework[C].International Conference on Software Intelligence Technologies and Appliations,2014:1-5.

[12] Cui Yan,Bao Zhi-qiang.Survey of association rule mining [J].Application Research of Computers,2016,33(2):330-334.

[13] Witten I H,Paynter G W,Frank E,et al.KEA:practical automatic keyphrase extraction[C].ACM Conference on Digital Libraries,August 11-14,1999,Berkeley,Ca,Usa.DBLP,1999:254-255.

[14] Mihalcea R,Tarau P.TextRank:bringing order into texts[J].Unt Scholarly Works,2004:404-411.

附中文參考文獻(xiàn)：

[2] 徐雅斌,李 卓,呂非非,等.基于頻繁詞集聚類的微博新話題快速發(fā)現(xiàn)[J].系統(tǒng)工程理論與實踐,2014(S1):276-282.

[12] 崔 妍,包志強.關(guān)聯(lián)規(guī)則挖掘綜述[J].計算機應(yīng)用研究,2016,33(2):330-334.