李博涵 蔡永香 鄧舒穎 王督

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

關鍵詞：Prefixspan；序列模式挖掘；新詞提??；投影數據庫；新詞發(fā)現

中圖分類號：TP391 文獻標識碼：A 文章編號：1009-3044（2018）08-0160-04

1概述

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

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

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

2改進的Prefixspan算法

給定一個序列或者由多個序列組成的序列數據庫，同時給定一個用戶指定的最小支持數閾值，序列模式挖掘就是應用數據挖掘技術找出所有出現次數不小于用戶設定閾值的子序列。

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

2.1 Prefixspan算法

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

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

Prefixspan的具體算法可參考文獻。

2.2改進的Prefixspan算法

對中文文本尤其是科技新聞類文章中出現的新詞進行分析發(fā)現，構成新詞的短語或字具有順序特征和連續(xù)性，且大多數以較長的固定組合形式多次出現在語料中，運用序列模式挖掘算法Prefixspan可以將這樣的固定組合的形式提取出來，但在實際應用中仍存在以下兩方面的問題：

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

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

針對上述問題，我們進行以下幾方面的改進：

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

2）對挖掘出來的候選新詞集進行進一步的篩選，包括①候選新詞集中需舍棄掉模式序列個數為一的詞語，因為這些詞是分詞時就直接劃分出的詞，說明這些詞已經在詞庫中存在，不是新詞；②詞性語義過濾；③當候選詞之間存在包含的關系時，在滿足同等閾值的情況下，通常情況是短語越長，內涵越多，所以將被包含項舍棄掉。

3中文文本新詞提取方法

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

1）使用NLPIR漢語分詞系統(tǒng)對語料庫中的語料進行分詞與詞性標注準確性，并將中文文本轉換為序列數據集；

2）利用改進的Prefixspan算法從序列數據集中遞歸挖掘候選新詞集；

3）對得到的候選新詞集進行篩選過濾，這包括對詞庫中已經存在的舊詞過濾，對詞性語義過濾以及對有包含關系的詞語進行取舍等；

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

中文文本新詞提取的方法實現主要由文本預處理模塊、新詞挖掘模塊、候選詞過濾模塊等三個子模塊組成。具體過程如圖1所示：

3.1文本預處理

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

序列數據集轉換是將分詞與詞性標注后的語料轉換成可以進行模式挖掘的數據集序列。即需要將語料轉換為2.1描述的序列數據庫S的過程?？紤]到新詞可能會在一個句子中的若干分句多次出現，我們將每個分句都當做一個序列來進行處理。

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

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

將上述語料轉換為標準序列集，轉換的部分序列如表1所示：

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

ItemSet（字符項集類）

包含屬性為：字符ArrayListitems

按照Prefixspan改進算法，構建投影數據庫時，需構建兩個不同的頻繁序列集合來存儲序列以及元素，分別為ItemSet1與ItemSet2；具體的數據存儲結構如圖2所示。

改進的Prefixspan算法描述如下：

輸入：序列數據庫S和最小支持度閾值minSupportRate

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

方法：

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

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

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

3.3候選詞過濾

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

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

21詞性過濾

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

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

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

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

4方法檢驗

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

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