基於圖的最大緊密度劃分的複合短語無監督識別方法與流程

2024-02-24 03:56:15

本發明屬於信息技術領域，具體涉及一種基於圖的最大緊密度劃分的複合短語無監督識別方法。

背景技術：

隨著多科學研究的逐步深入，現今學術界和研究者發表大量的研究成果呈海量爆炸性增長。如何自動化收集、整合、分析這些工作成為了學術界和工業界關注的問題。論文、書籍、技術報告、專利的題目、科技項目名稱等這一類短語在這裡統稱為複合短語。如何高效的從各類網絡語料中抽取需要的科技複合名詞實體，是自動化進行學術信息抽取、智慧財產權保護、科技資源資料庫在線建設與維護等諸多應用的基礎。

傳統意義上的命名實體是自然語言處理的基本任務抽取的對象，主要包括人名、地名、組織機構名、數字、計量單位等專有名詞。這些命名實體具有長度相對穩定、結構規範、命名規則統一的有利特點，這使得傳統的命名實體識別系統的F1-measure往往能達到90％以上，幾乎接近人類正常識別水平。而科技類名詞短語不同於人名和地名。科技類名詞往往內部結構複雜，內部包含嵌套的科技名詞實體。而且科技類名詞短語紛繁複雜，詞·語的出現與否本身具有極大的稀疏性，內部實體之間相互組合的冗餘度低。這類詞法結構導致識別該類命名實體的難度較大。這使得通過詞語本身隱式馬爾科夫輸入的方法不可行。由於複合短語相對於普通的命名實體(人名、地名、機構名)詞語本身詞法組成更加複雜，傳統的純手工角色標註容易導致標註錯誤，而且傳統方法依賴於手工標註數據，費時費力。

技術實現要素：

本發明的目的在於提供無監督的複合短語自動識別方法，為解決科技類短語手工標註數據費時費力的困難以及數據稀疏，冗餘度低的特點以及傳統的有監督方法效果較差，本文提出了一種無監督的基於圖的最大緊密度劃分的複合短語的高效識別方法。

本發明採用的技術方案如下：

一種基於圖的最大緊密度劃分的複合短語無監督識別方法，包括以下步驟：

1)採用詞性標註工具對輸入語料進行詞性標註和分詞；

2)將分詞後的輸入序列映射到有序的圖結構中，將語義緊密度高的詞語劃分到一個分段內，並使得整個圖的緊密度之和最大；

3)通過驗證各分段是否包含特徵詞，實現候選複合短語的最終識別。

進一步地，步驟2)通過動態規劃方法求解不同分段組合之間的緊密度，從而將整個輸入文本的緊密度之和最大化。

進一步地，步驟2)中分詞之間的緊密度包含：特殊符號緊密度、維基百科緊密度、以及詞性緊密度。

進一步地，步驟3)通過求解最小集合覆蓋問題來產生特徵詞集合。

本發明的關鍵點包括兩個方面：

1)針對設置對科技類複合名詞短語自身的特點，通過將輸入序列映射到有序的圖模型，通過尋找最大化緊密度的切分，從而將候選科技複合短語切分出來。

2)根據複合短語特徵詞中富含特徵詞這一重要特性，採用了前一階段的分段是否包含特徵詞來實現候選科技複合短語的最終識別。本發明採用了最小集合覆蓋的思想，來產生特徵詞集合。

本發明的有益效果如下：

本發明提供了一種無監督的基於圖的最大緊密度劃分的複合短語自動識別方法，能夠自動識別科技類複合短語，省時省力，相比於傳統的有監督方法，不需要大量標註語料，便於在線部署應用，是一種高效的科技類複合短語識別方法。

附圖說明

圖1是命名實體識別處理流程圖。

圖2是單詞圖分割例子示意圖。

圖3是二元運算計算示意圖。

圖4是681-NSPTA數據集上參數u對算法性能影響曲線圖，其橫坐標為參數u的值，縱坐標為算法性能值，其中Recall Rate表示查全率，Precision表示查準率，F1measure表示F1測度。

圖5是NSPTA數據集上參數u對算法性能影響曲線圖，其橫坐標為參數u的值，縱坐標為算法性能值。

圖6是681-NSPTA數據集上參數v對算法性能影響曲線圖，其橫坐標為參數v的值，縱坐標為算法性能值。

圖7是NSPTA數據集上參數v對算法性能影響曲線圖，其橫坐標為參數v的值，縱坐標為算法性能值。

圖8是681-NSPTA上滑動窗口大小對算法性能影響曲線圖，其橫坐標為滑動窗口大小，縱坐標為算法性能值。

圖9是NSPTA上滑動窗口大小對算法性能影響曲線圖，其橫坐標為滑動窗口大小，縱坐標為算法性能值。

具體實施方式

為使本發明的上述目的、特徵和優點能夠更加明顯易懂，下面通過具體實施例和附圖，對本發明做進一步說明。

1.科技複合短語特徵

基於對複合短語的觀察，發現有以下幾個特性：

(1)多成分組成：複合短語往往由多個詞語組成成分，例如：「兩系法雜交水稻研究與應用」中，對其進行分詞後，包含「兩系法」、「雜交」、「水稻」、「研究」、「應用」這幾個詞語組成成分。

(2)維基百科成分：由於複合短語本身的領域特性，其內部成分往往是由維基百科條目組成。仍以科技複合短語「兩系法雜交水稻研究與應用」為例，其中的「雜交」、「水稻」、「研究」、「應用」均為維基百科條目，由此可見，連續的維基百科條目可以作為從輸入序列切分科技複合短語的一個重要依據。

(3)特殊組成詞性：在科技複合短語中極少出現幾類詞性、例如系動詞、人稱代詞、感嘆詞、語氣詞，輸入序列的中若出現此類詞性，則依據無關性原則，來切分上下文輸入詞語序列。

根據以上幾個原則，我們提出基於圖的緊密度最大化劃分的原則：將一個輸入序列映射到一個有序的圖模型中。將前後具有緊密聯繫的詞語劃分到一個分段中，以將無關的成分與候選複合短語相分離。

2.科技複合短語識別流程

如圖1所示，本方法模型主要分為三部分：第一部分首先採用詞性標註工具對輸入語料進行詞性標註和分詞。第二部分通過計算分詞結果之間組合的緊密度，通過動態規劃求解不同分段組合結果之間的緊密度，將整個輸入文本的緊密度之和最大化。第三部分通過驗證分段是否包含特徵詞，從而篩選出需要的複合短語。

我們在這裡假定通過基本標點符號截取的輸入分詞序列前後由邊相連，構成一個有序的圖結構。在輸入的一段文本中，各個詞之間在語義上是關聯的，所有的分詞與關聯構成一個圖。從該分詞的序列中提取並組合合適的內容，如同對圖進行了切分。將切分後語義緊密度高的分配到一個分段內，使得整個圖的緊密度之和最大(如圖2所示)。

這裡定義整個輸入序列圖模型的緊密度為：

s.t.1≤|si|≤uwhere t＝s1s2···sm

其中，si代表每一個分段，|si|表示劃分分段si中包含分詞的個數，t表示分詞組成的分段，C(t)表示分段整體緊密度，C(si)表示單個分詞對應的緊密度，m表示分段的數目，u表示分段的最大長度。

為了求解所有分段方案的中最優方案，本發明提出基於動態規劃的分段劃分算法SCSeg(SCi-tech compound entities SEGment solutions)，對輸入序列求解全局的緊密度劃分方法。如下式，對於每一個分段，都有一個對應的分段的緊密度。我們遍歷每一個分割方案，將目標函數定義為各個分段緊密度之和，通過動態規劃求解目標函數最大值，從而對原輸入分詞序列求解最優劃分分段方案，進而得到文本中科技類複合短語與其他成分的最優的劃分方案。

其中，s1＝w1…wj，s2＝wj+1…wn

上式中，C(s)表示分詞組成的分段整體緊密度，s1,s2表示對該分段進一步分割得到的兩個子分段，wj表示輸入語句中中第j個分詞，u代表分段的最大長度，n表示語句中一共包含的分詞的數量。

整個輸入序列對應圖的分段整體緊密度計算公式為：

其中，C(w1，w2)代表分詞w1與w2之間的緊密度，s表示一個分段，|s|表示分段中分詞的個數。

基於此，本發明提出緊密度最大化的求解算法如下：

返回中C(st)值最大的劃分方案作為最優劃分

該算法為動態規划算法，共有兩個參數：u：分段的最大長度，v：遞推求解的候選集合大小。上述算法用自然語言描述如下：

1)假設當前句子包含的分詞數為n，算法從1到n-1之間逐個遞歸遍歷切分得到的子分段之和，其中參數u是為了限制每個子分段中包含分詞的最大數量；

2)算法從1到n-1之間存儲之前劃分的子分段的前υ個最優劃分，當算法進行下一次遞歸時，會在已經存儲的最優劃分方案中遞歸查找，以求解當前子分段的前υ個最優劃分；

3)遞歸進行這一過程，直到在句子分詞的末尾，從而得到整個句子的前υ個最優劃分。

3.分詞之間的緊密度計算

通過對科技複合短語的分析，本發明將分詞之間的緊密度劃分為特殊符號緊密度、維基百科緊密度以及詞性的緊密度。

我們定義分詞之間的緊密度的計算公式為

C(w1，w2)＝(Csm(w1，w2)+Cwt(w1，w2))×Cp2v(w1，w2)

其中Csm代表特殊符號緊密度，Cwt代表維基百科緊密度，Cp2v代表詞性的緊密度。

特殊符號緊密度：科技複合短語、例如論文與專利題目等往往由特殊符號包圍，基於此現象，位於特殊符號內的分詞節點應當具有更高的緊密度。我們定義特殊符號緊密度為其中Ds(w1，w2)代表詞w1與詞w2之間間隔的分詞個數，為表徵w1與w2之間是否位於同一對特殊符號內的布爾函數。

維基百科緊密度：由上述科技複合短語的維基百科特性可知，連續的維基百科條目為科技複合短語的可能性較大。這裡定義維基百科緊密度為。

其中I(w)為表徵詞w是否為維基百科條目的布爾函數，s』表示位於詞w1與詞w2之間的分詞組成的分段，|s|表示分段s中分詞的個數。

詞性緊密度：由科技複合短語中特殊組合詞性特性可知，部分詞性極少出現在科技複合短語中。基於此觀察，本發明引入word2vec模型，將詞性標註(POS)後的科技複合短語的輸入序列作為訓練word2vector的模型(以下簡稱pos2vec)，這裡定義詞性緊密度為。

這裡在分子加1是為了保證Cp2v(w1，w2)恆為正。其中，Sc表示詞w1和w2對應詞性在隱式空間內的餘弦相似度，p(ω1),p(ω2)表示詞w1和w2對應的詞性，表示詞w1和w2對應詞性在隱式空間的向量。

4.科技複合短語的驗證

在切分後的候選科技複合短語實體中，需要對候選的集合進行判斷。注意到科技類科技複合短語中包含一類特殊的高頻詞語、例如上述短語中的「技術」、「研究」和「應用」。我們將這一類詞語稱為科技複合短語的特徵詞。特徵詞集合規模過大會導致過匹配非複合短語。而特徵詞集合規模過小又會導致遺漏。為了解決上述問題，我們基於最小集合覆蓋問題，進行特徵詞集合的生成。所謂最小集合覆蓋，是指給定全集U，以及一個包含n個集合且這n個集合的併集為全集的集合S。集合覆蓋問題是要找到S中最小的子集，使得他們的併集等於全集U，並且子集的規模最小。給定科技名詞短語集合，記訓練集為P＝{p1，p2，...，pn}，其中pi為第i條文本標題。通過對P進行分詞處理後可以獲取一個詞典數據W＝{w1，w2，...，wm}，其中wi為詞典中第i個單詞。關係類型的特徵詞提取可以轉化為在詞典中尋找一個滿足最小覆蓋的子集S，使得S滿足：

1.集合S能夠覆蓋集合P，即P的每條語料pi中至少有一個單詞在S中出現；

2.S中元素個數最小。由於求解最小集合覆蓋問題是一個NP-hard問題。這裡採用貪心算法求解特徵詞的覆蓋問題。

將求解訓練集P的最小覆蓋單詞集S問題記為WLAN(Words with the LeAst Number)。我們通過以下方法求解特徵詞的最小覆蓋集合。通過訓練集P和詞典W可以構造一個m×n維的二值矩陣M，若詞典中第i個單詞wi在pj中出現過則Mij＝1，否則Mij＝0。首先如圖3，定義二元運算符計算結果為去掉矩陣中M第i行以及所有第j列中非0元素Mij≠0，j∈[i，n]，組成的新矩陣。如圖3所示，P＝{p1，p2，p3}為三條同類型的標題語料，分詞後得到含有4個單詞的詞典W＝{w1，w2，w3，w4}，構造矩陣M。如果選擇單詞w2，則的計算結果為刪除M的第2行和第1列中非0元素所在的列，得到矩陣M′。利用運算符以使用動態規劃的方法來求得問題的最優解。本發明中採用貪心算法計算問題的近似最優解，計算過程如下：

構造布爾矩陣M，對訓練語料中所有科技複合短語看作矩陣M的列向量，對於訓練語料中所有科技複合短語中所有的分詞構成矩陣M的列向量的行向量。若一個單詞在某條科技複合短語中出現，則把其對應結果置為1。

矩陣M作為初始輸入值，令單詞集

選擇M中1數量最多的一行，假設為第i行，計算S＝S∪wi；

令並將其作為下一步輸入；

重複上述兩個步驟直到M為空矩陣為止，此時單詞集S即所求的最小覆蓋集，即得到了科技複合短語的特徵詞集合。

然後利用該特徵詞集合，通過驗證分段是否包含特徵詞，從而篩選出需要的複合短語。

5.本發明的效果

本發明利用包含從2005年到2014年的獲得國家科技進步獎(National Science and Technology Progress Award between)的科技項目作為輸入，爬取並選取1869條語料數據作為實驗數據(以下簡稱為NSTPA)，其中每一條語料包含一個或者多條複合短語。在其中本發明選取了681條數據(以下簡稱為681-NSTPA)，前後共投入四名志願者，花了兩個月的時間，做了隱式馬爾科夫模型的角色標註。訓練集與測試集採用十折交叉驗證的方法，另外，本發明從搜狗新聞語料中選取766條數據(以下簡稱為SOUGOU)，其中不包含任何科技複合短語。我們定義單條查全率為、查準率如下：

這裡，eij與分別代表正確的科技複合短語與提取出的科技複合短語，代表eij與的公共字串長度。如果eij與均為空，則我們定義Re(ti)＝Pr(ti)＝1；若eij非空而為空，Re(ti)＝0，Pr(ti)＝1；若非空而eij為空，Re(ti)＝1，Pr(ti)＝0。總體查全率和查準率定義為：

表1.實驗方法及數據集對比

由表1可以看出，在681-NSTPA對比數據集上，本發明的基於圖的最大緊密度劃分的複合短語的識別方法(SCSegVal)好於基於隱式馬爾科夫的方法(HMM)，在完整的數據集NSTPA以及SOUGOU上，取得了80.2％的查全率、80.8％的查準率、80.5％的F1測度以及100％的查全率、55.22％的查準率、71.15％的F1測度。

下面說明切分文本動態求解參數設定：

切分文本的算法有兩個參數，分段最大長度u、候選集合大小v。另外我們控制前後圖中相連的點的個數在一個滑動窗口內。如圖4至圖9所示，發現以下規律：

根據圖4、圖5可以看出，查全率、查準率、F1測度隨著u增大而增大。隨著u增大，查全率、查準率、F1測度增長速度減慢，隨後停滯不前，這表明當u大於科技複合短語時，算法的性能不在增長。

根據圖6、圖7可以看出，當v增長時，算法總體性能輕微增長，其中準確率在一個階段內輕微下降，隨後增長。造成這一現象的原因是，由於候選集合的增大，算法輕微陷入局部最優，隨後由於候選集合的繼續增大，算法擺脫局部最優。

根據圖8、圖9可以看出，當隨著滑動窗口的增加，算法性能急劇增加，但是窗口到達一定規模後，算法性能增長趨於停滯。這表明為了減小內存與時間消耗，適當縮減滑動窗口大小，不會明顯降低算法的性能。

以上實施例僅用以說明本發明的技術方案而非對其進行限制，本領域的普通技術人員可以對本發明的技術方案進行修改或者等同替換，而不脫離本發明的精神和範圍，本發明的保護範圍應以權利要求書所述為準。