基于改進(jìn)的Prefixspan算法的中文文本新詞提取方法研究

李博涵 蔡永香 鄧舒穎 王督

摘要：該文嘗試將序列模式挖掘算法Prefixspan應(yīng)用于中文文本新詞提取中，針對(duì)Prefixspan算法挖掘出的序列模式不連續(xù)、挖掘出的序列模式項(xiàng)相互間存在包含關(guān)系等問題，對(duì)算法進(jìn)行改進(jìn)，采用語義特征與統(tǒng)計(jì)相結(jié)合的方法，實(shí)現(xiàn)了從中文語料中有效提取新詞。實(shí)驗(yàn)結(jié)果表明，該方法對(duì)于專業(yè)領(lǐng)域新詞的識(shí)別具有較高的準(zhǔn)確性。

關(guān)鍵詞：Prefixspan；序列模式挖掘；新詞提?。煌队皵?shù)據(jù)庫(kù)；新詞發(fā)現(xiàn)

中圖分類號(hào)：TP391 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2018）08-0160-04

1概述

新詞不僅僅指詞典的未登錄詞，更是指帶有大量修飾語的復(fù)合詞。

新詞發(fā)現(xiàn)在自然語言處理領(lǐng)域中的機(jī)器翻譯、信息檢索、文本分類、文本摘要、領(lǐng)域本體等領(lǐng)域都有廣泛的應(yīng)用。對(duì)中文文本中的新詞進(jìn)行正確發(fā)現(xiàn)、提取并加以利用，構(gòu)建專業(yè)領(lǐng)域?qū)I(yè)詞匯詞典，可以為進(jìn)一步信息過濾、內(nèi)容分類以及信息聚類提供幫助。關(guān)于新詞提取，目前主要的方法是通過對(duì)詞語在文本中各種特征進(jìn)行分析，利用監(jiān)督學(xué)習(xí)或者無監(jiān)督學(xué)習(xí)建立抽取模型，進(jìn)一步提取新詞。而新詞在文本中的特征主要可以分為語義特征與統(tǒng)計(jì)特征兩種，統(tǒng)計(jì)特征主要指的是詞語的一些通過數(shù)學(xué)統(tǒng)計(jì)得到特征，如詞頻、詞語位置、TFIDF值等。而語義特征指的是詞語的詞義特征，如詞語的詞性、詞匯鏈特征、詞語之間的相關(guān)度等。針對(duì)這兩類特征，通常分別采取基于語義特征的獲取方法或者基于統(tǒng)計(jì)的獲取方法，或者將二者結(jié)合起來。一般情況下，基于統(tǒng)計(jì)特征的新詞抽取方法相對(duì)比較簡(jiǎn)單、通用性比較強(qiáng)，如基于詞頻統(tǒng)計(jì)的抽取方法、基于TFIDF值的抽取方法，基于詞共現(xiàn)的抽取方法等；基于語義特征的方法一般比較復(fù)雜，抽取效果較好，但在構(gòu)成模式的規(guī)定上，新詞的構(gòu)成模式易與舊的構(gòu)成模式造成沖突，較難維護(hù)?，F(xiàn)在大多數(shù)研究者采用兩者結(jié)合的方法，發(fā)揮各自的優(yōu)勢(shì)，提高新詞發(fā)現(xiàn)的效果。

經(jīng)過對(duì)中文文本中出現(xiàn)的新詞分析發(fā)現(xiàn)，新詞的序列具有順序特征和連續(xù)性，且大多數(shù)以較長(zhǎng)的固定組合形式多次出現(xiàn)在語料中。序列模式挖掘算法適合挖掘這種出現(xiàn)頻率高的模式，但這種算法挖掘出的是離散型序列。本文對(duì)序列模式挖掘算法Prefixspan進(jìn)行改進(jìn)，使之適用于連續(xù)性序列模式的挖掘，并應(yīng)用于中文文本新詞提取中，并采用語義特征與統(tǒng)計(jì)相結(jié)合的方法實(shí)現(xiàn)從中文語料中提取新詞。實(shí)驗(yàn)結(jié)果表明，這種方法對(duì)于新詞的識(shí)別具有較強(qiáng)的準(zhǔn)確性。

2改進(jìn)的Prefixspan算法

給定一個(gè)序列或者由多個(gè)序列組成的序列數(shù)據(jù)庫(kù)，同時(shí)給定一個(gè)用戶指定的最小支持?jǐn)?shù)閾值，序列模式挖掘就是應(yīng)用數(shù)據(jù)挖掘技術(shù)找出所有出現(xiàn)次數(shù)不小于用戶設(shè)定閾值的子序列。

序列模式挖掘是由Agrawal和Srikant于1995年首先提出的，隨后他們提出了廣義序列模式（GSP）挖掘算法；序列模式挖掘的模式增長(zhǎng)方法PrefixSpan，以及它的前驅(qū)算法FreeSpan則由Han等人與2001年提出，其中PrefixSpan算法因包含更少的投影庫(kù)和子序列連接而被廣泛應(yīng)用于序列模式挖掘中，比GSP算法和FreeSpan算法性能更優(yōu)。國(guó)內(nèi)外的學(xué)者對(duì)PrefixSpan提出了很多優(yōu)化改進(jìn)方案。例如在陸介平等人提出的ISPBP算法，用增量數(shù)據(jù)庫(kù)來減小投影數(shù)據(jù)庫(kù)，提高了算法效率；張坤等提出的SPMDS算法，將投影數(shù)據(jù)庫(kù)是否相等的判定問題轉(zhuǎn)化為偽投影是否相等的問題，對(duì)前綴樹做索引，簡(jiǎn)化搜索代價(jià)；韓高偉針對(duì)現(xiàn)有的序列模式PrefixSpan算法提出了一種增量式數(shù)據(jù)流雙重加權(quán)序列模式算法DWC-SP-MDS，利用增量式方法更新挖掘結(jié)果，同樣提高了運(yùn)行效率。這些改進(jìn)的算法在運(yùn)行效率、內(nèi)存使用、算法可擴(kuò)展性上均有了優(yōu)化，但因?yàn)橥诰虺龅男蛄心Ｊ骄哂须x散型的特征，不能直接用于中文連續(xù)性文本模式的挖掘。

2.1 Prefixspan算法

Prefixspan是一種使用數(shù)據(jù)庫(kù)投影技術(shù)的深度優(yōu)先搜索算法，它具備處理大序列數(shù)據(jù)庫(kù)的能力。主要思路是：首先進(jìn)行頻繁項(xiàng)的產(chǎn)生和挖掘工作，使用頻繁前綴劃分空間，針對(duì)每一個(gè)頻繁項(xiàng)經(jīng)過投影，各自產(chǎn)生一個(gè)投影數(shù)據(jù)庫(kù)，從而生成投影數(shù)據(jù)庫(kù)集合。然后采用分治的策略，不斷產(chǎn)生更多、更小的投影數(shù)據(jù)庫(kù)，在各投影數(shù)據(jù)庫(kù)上進(jìn)行序列模式挖掘。相關(guān)基本概念如下：

序列數(shù)據(jù)庫(kù)S是元組的集合，其中id是序列標(biāo)識(shí)；s是一個(gè)序列。如果僅是序列s的子序列，則稱元組包含序列α。序列α在序列數(shù)據(jù)庫(kù)S中的支持度是指數(shù)據(jù)庫(kù)中包含僅的元組的個(gè)數(shù)，記作suppon（α）。給定一個(gè)正整數(shù)min_sup表示最小支持度，如果suppon（α）≥min_sup，序列僅在數(shù)據(jù)庫(kù)S中是頻繁的。頻繁序列就叫做序列模式。

Prefixspan的具體算法可參考文獻(xiàn)。

2.2改進(jìn)的Prefixspan算法

對(duì)中文文本尤其是科技新聞?lì)愇恼轮谐霈F(xiàn)的新詞進(jìn)行分析發(fā)現(xiàn)，構(gòu)成新詞的短語或字具有順序特征和連續(xù)性，且大多數(shù)以較長(zhǎng)的固定組合形式多次出現(xiàn)在語料中，運(yùn)用序列模式挖掘算法Prefixspan可以將這樣的固定組合的形式提取出來，但在實(shí)際應(yīng)用中仍存在以下兩方面的問題：

1）在構(gòu)建投影數(shù)據(jù)庫(kù)時(shí)，Prefixspan算法舍棄了對(duì)非頻繁項(xiàng)的存儲(chǔ)以及對(duì)投影序列數(shù)小于最小支持度的投影數(shù)據(jù)庫(kù)的掃描，然后依次從序列中的若干子序列中掃描是否存在頻繁項(xiàng)集。這種方式可以不用掃描不可能出現(xiàn)頻繁序列的子序列，但這樣獲取的序列模式是離散的，前后序列在原文本中可能是不連續(xù)的，這樣的模式不滿足詞語的連續(xù)性要求。

2）Prefixspan算法挖掘出的滿足條件的序列模式項(xiàng)相互間可能存在包含關(guān)系，新詞發(fā)現(xiàn)需要對(duì)這種情況進(jìn)行篩選處理。

針對(duì)上述問題，我們進(jìn)行以下幾方面的改進(jìn)：

1）考慮到既要減少迭代次數(shù)，又要保證挖掘的序列模式具有連續(xù)性特征，在構(gòu)建投影數(shù)據(jù)庫(kù)時(shí)，需構(gòu)建兩個(gè)不同的頻繁序列集合，其一用于刪除非頻繁項(xiàng)，構(gòu)建一個(gè)初始的頻繁序列集合ItemSet1，在投影時(shí)不再掃描投影序列數(shù)小于最小支持度的投影數(shù)據(jù)庫(kù)；其二用于不刪除非頻繁項(xiàng)集，獲取當(dāng)前前綴在各個(gè)序列中的局部頻繁項(xiàng)，組成一個(gè)新的頻繁序列集合Item-Set2，用于對(duì)后續(xù)的滿足支持度要求的后綴進(jìn)行遞歸挖掘；在進(jìn)行投影數(shù)據(jù)庫(kù)的生成和掃描的過程中，省略在后續(xù)的多元素項(xiàng)中判斷是否包含此元素的步驟，只需要判斷當(dāng)前子序列中的下一個(gè)元素是否符合閾值要求即可，從而減少投影數(shù)據(jù)庫(kù)的規(guī)模及掃描投影數(shù)據(jù)庫(kù)的時(shí)間。

2）對(duì)挖掘出來的候選新詞集進(jìn)行進(jìn)一步的篩選，包括①候選新詞集中需舍棄掉模式序列個(gè)數(shù)為一的詞語，因?yàn)檫@些詞是分詞時(shí)就直接劃分出的詞，說明這些詞已經(jīng)在詞庫(kù)中存在，不是新詞；②詞性語義過濾；③當(dāng)候選詞之間存在包含的關(guān)系時(shí)，在滿足同等閾值的情況下，通常情況是短語越長(zhǎng)，內(nèi)涵越多，所以將被包含項(xiàng)舍棄掉。

3中文文本新詞提取方法

基于上述該改進(jìn)的Prefixspan方法，我們進(jìn)行中文文本新詞提取方法如下：

1）使用NLPIR漢語分詞系統(tǒng)對(duì)語料庫(kù)中的語料進(jìn)行分詞與詞性標(biāo)注準(zhǔn)確性，并將中文文本轉(zhuǎn)換為序列數(shù)據(jù)集；

2）利用改進(jìn)的Prefixspan算法從序列數(shù)據(jù)集中遞歸挖掘候選新詞集；

3）對(duì)得到的候選新詞集進(jìn)行篩選過濾，這包括對(duì)詞庫(kù)中已經(jīng)存在的舊詞過濾，對(duì)詞性語義過濾以及對(duì)有包含關(guān)系的詞語進(jìn)行取舍等；

4）將篩選得到的新詞加入新詞詞典。

中文文本新詞提取的方法實(shí)現(xiàn)主要由文本預(yù)處理模塊、新詞挖掘模塊、候選詞過濾模塊等三個(gè)子模塊組成。具體過程如圖1所示：

3.1文本預(yù)處理

中文語料的格式不一，在序列模式挖掘前需要進(jìn)行文本預(yù)處理。文本預(yù)處理包括分詞標(biāo)注和序列數(shù)據(jù)集轉(zhuǎn)換。分詞標(biāo)注是利用已有的詞庫(kù)對(duì)文本進(jìn)行分詞處理，為了方便進(jìn)一步的詞性語義過濾，還需要對(duì)詞性進(jìn)行標(biāo)注。本文是采用漢語分詞系統(tǒng)NLPIR的jna分詞包進(jìn)行分詞與詞性標(biāo)注，分詞的結(jié)果以“單詞/詞性”格式返回。

序列數(shù)據(jù)集轉(zhuǎn)換是將分詞與詞性標(biāo)注后的語料轉(zhuǎn)換成可以進(jìn)行模式挖掘的數(shù)據(jù)集序列。即需要將語料轉(zhuǎn)換為2.1描述的序列數(shù)據(jù)庫(kù)S的過程?？紤]到新詞可能會(huì)在一個(gè)句子中的若干分句多次出現(xiàn)，我們將每個(gè)分句都當(dāng)做一個(gè)序列來進(jìn)行處理。

以下面這段中文語料為例：

12月6日，俄羅斯西布爾公司派出技術(shù)人員到鎮(zhèn)海煉化參觀考察。標(biāo)志著鎮(zhèn)海煉化乙烯裂解裝置的在線實(shí)時(shí)優(yōu)化項(xiàng)目已成為海內(nèi)外同行業(yè)共同關(guān)注的焦點(diǎn)。

將上述語料轉(zhuǎn)換為標(biāo)準(zhǔn)序列集，轉(zhuǎn)換的部分序列如表1所示：

3.2利用改進(jìn)的Prefixspan算法進(jìn)行候選新詞發(fā)現(xiàn)

ItemSet（字符項(xiàng)集類）

包含屬性為：字符ArrayListitems

按照Prefixspan改進(jìn)算法，構(gòu)建投影數(shù)據(jù)庫(kù)時(shí)，需構(gòu)建兩個(gè)不同的頻繁序列集合來存儲(chǔ)序列以及元素，分別為ItemSet1與ItemSet2；具體的數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)如圖2所示。

改進(jìn)的Prefixspan算法描述如下：

輸入：序列數(shù)據(jù)庫(kù)S和最小支持度閾值minSupportRate

輸出：所有的符合的新詞集合

方法：

1）掃描序列數(shù)據(jù)庫(kù)S一次，得到模式序列個(gè)數(shù)為一的頻繁序列組成頻繁序列集合ItemSet，刪除其中的非頻繁項(xiàng)，并將頻繁項(xiàng)按其支持度從大到小排序，得到ItemSet1。其中，最小支持度min_sup=（最小支持度閾值minSupportRate*序列總數(shù)n（S））；

2）依次對(duì)頻繁項(xiàng)進(jìn)行投影，構(gòu)建相應(yīng)的投影數(shù)據(jù)庫(kù)，并對(duì)每一個(gè)投影數(shù)據(jù)庫(kù)遞歸地進(jìn)行挖掘。其中對(duì)每一個(gè)頻繁項(xiàng)，構(gòu)建相應(yīng)的投影數(shù)據(jù)庫(kù)，對(duì)投影數(shù)據(jù)庫(kù)掃描一次，刪除ItemSet1的局部非頻繁項(xiàng)，得到其局部頻繁項(xiàng)ItemSet2。判斷當(dāng)前前綴是否符合最小支持度閾值，如果符合，繼續(xù)迭代，對(duì)投影數(shù)據(jù)庫(kù)作關(guān)于ItemSet2中符合條件前綴的投影，此時(shí)的前綴為滿足條件的候選新詞；如果條件不滿足，則停止當(dāng)前頻繁項(xiàng)的遞歸，對(duì)下一頻繁項(xiàng)進(jìn)行最小支持度閾值的判斷；迭代中，局部頻繁項(xiàng)與上一步得到的除當(dāng)前頻繁前綴記為α以外的頻繁項(xiàng)是相同的；

3）判斷遞歸結(jié)束條件，得到候選新詞集。

3.3候選詞過濾

在候選詞過濾模塊中我們對(duì)候選新詞集進(jìn)行過濾，得到最終的新詞集加入新詞詞典。候選詞過濾主要包含三個(gè)主要方面：

1）候選新詞集中需舍棄掉模式序列個(gè)數(shù)為一的詞語，這樣的詞出現(xiàn)頻率雖然很高但不屬于新詞；

21詞性過濾

抽取出的候選新詞包含詞性信息，例如『構(gòu)建/v物/ng聯(lián)網(wǎng)/vi信息/n模型/n]，其詞性組合為[v+ng+vi+n+n]。我們實(shí)驗(yàn)采用的文本都是油氣行業(yè)新聞，通過分析總結(jié)油氣行業(yè)領(lǐng)域詞庫(kù)中詞匯的詞性組成結(jié)構(gòu)，得到了一些常見新詞的詞性組合模式，我們用這些詞性組合模式進(jìn)行候選新詞的過濾。

在詞性匹配時(shí)，可優(yōu)先采取對(duì)第一個(gè)詞的詞性以及最后一個(gè)詞的詞性進(jìn)行控制，以提高效率。例如新詞通常情況下不以介詞（p）結(jié)尾，通常以名詞（n）結(jié)尾；當(dāng)詞語由[m+q]即數(shù)次和量詞組合而成時(shí)，予以舍棄。

3）當(dāng)保留下來的候選詞之間存在包含的關(guān)系時(shí)，在滿足同等閾值的情況下，通常情況下是短語越長(zhǎng)，內(nèi)涵越多，因此，我們將被包含項(xiàng)舍棄掉。我們過濾的步驟是，先對(duì)前綴相同的候選新詞進(jìn)行包含項(xiàng)過濾，如“大慶油田”與“大慶油田采油六廠”，我們可以將“大慶油田”過濾掉，保留“大慶油田采油六廠”為新詞；再對(duì)前綴不同的包含項(xiàng)過濾，如“山東銷售分公司”與“潤(rùn)滑油山東銷售分公司”，我們將“山東銷售分公司”過濾掉，保留“潤(rùn)滑油山東銷售分公司”為新詞。

通過上述方法保留下來的詞作為新詞加入新詞詞典。

4方法檢驗(yàn)

以油氣行業(yè)新聞作為對(duì)象進(jìn)行方法檢驗(yàn)，本文以中國(guó)石油新聞網(wǎng)2017年12月份的三篇新聞為提取對(duì)象進(jìn)行方法檢驗(yàn)，并與用NLPIR進(jìn)行新詞發(fā)現(xiàn)的結(jié)果進(jìn)行了對(duì)比。這三篇新聞標(biāo)題分別為：“華南成品油管網(wǎng)輸量首次突破2000萬噸”、“金陵石化油品質(zhì)量升級(jí)改造項(xiàng)目通過竣工驗(yàn)收”、“荊門石化連續(xù)重整裝置開創(chuàng)國(guó)內(nèi)首次在線換劑”。實(shí)驗(yàn)結(jié)果如表2所示。從表中可以看出：1）隨著最小支持度閾值的增大，采用本文方法發(fā)現(xiàn)的新詞從較長(zhǎng)的序列模式中分離保留下來，越來越精煉，這些詞作為新詞還是很有道理的；2）與NLPIR所發(fā)現(xiàn)的新詞結(jié)果相比較，兩者的重疊度還是較大的，當(dāng)最小支持度閾值較大時(shí)，部分NLPIR發(fā)現(xiàn)的詞在本文方法結(jié)果中沒有，如序號(hào)為1的文檔中NLPIR發(fā)現(xiàn)的新詞“優(yōu)化管道運(yùn)行，管輸，輸量”在本方法中最小支持度閾值設(shè)為0.17時(shí)沒被發(fā)現(xiàn)，但在閾值設(shè)置較小時(shí)（最小支持度閾值設(shè)為0.13時(shí)），這些詞都被發(fā)現(xiàn)了，這說明本文方法發(fā)現(xiàn)模式序列的能力是具備的，關(guān)鍵是采用適當(dāng)?shù)淖钚≈С侄乳撝怠Ａ硗庖泊嬖诓捎帽疚姆椒òl(fā)現(xiàn)的新詞在NL-PIR中沒被發(fā)現(xiàn)的情況，如序號(hào)為3的文檔中，本文方法發(fā)現(xiàn)的“在線換劑”，NLPIR就沒有發(fā)現(xiàn)，我們對(duì)原文檢查發(fā)現(xiàn)，該詞在原文中出現(xiàn)了5次，人工可以判定該詞為新詞。

前面的實(shí)驗(yàn)分析結(jié)果表明，本文提出的基于改進(jìn)的Prefixs-pan算法的中文文本新詞提取方法對(duì)于專業(yè)領(lǐng)域新詞的識(shí)別具有較強(qiáng)的準(zhǔn)確性，采用這種方法來完善詞庫(kù)具有可行性。只是最小支持度閾值的選取目前還是靠經(jīng)驗(yàn)給定，因此還需要進(jìn)一步優(yōu)化，達(dá)到能夠根據(jù)環(huán)境條件自動(dòng)進(jìn)行參數(shù)調(diào)整，來提高該方法的運(yùn)行效率。