[發明專利]一種借助圖隨機游走的開放類別命名實體抽取方法及裝置

有效

• 申請號: 201310745097.4
• 申請日: 2013-12-30
• 公開（公告）號: CN103678703B
• 公開（公告）日: 2017-01-11
• 發明（設計）人: 劉康;趙軍;齊振宇
• 申請（專利權）人: 中國科學院自動化研究所
• 主分類號: G06F17/30
• 分類號: G06F17/30;G06F17/27
• 代理公司: 中科專利商標代理有限責任公司11021
• 代理人: 宋焰琴

技術領域

本發明涉及自然語言處理技術領域，是一種從大規模文本語料中抽取開放類別命名實體的方法及裝置。

背景技術

命名實體在人類語言中傳遞著重要信息，它的識別和抽取是自然語言處理研究中的關鍵技術之一。開放類別命名實體抽取技術的目標是從海量、冗余、異構、不規范的網絡數據中抽取開放類別的命名實體，進而構建開放類別命名實體列表。這些開放類別命名實體列表在工業界和學術界都具有重要用途。因此，開放類別命名實體抽取技術具有重要的理論意義和實用價值。

傳統的開放類別命名實體抽取系統一般采取模板的方法：通過分析種子實體在語料中的上下文得到模板；接下來使用模板從語料中抽取候選實體；然后將候選實體和種子實體用各自匹配的模板加以表示，在模板空間上計算每個候選實體與種子實體的相似度；最后將該相似度作為該候選實體的置信度，并根據置信度對候選實體排序作為最終結果。

傳統的基于模板的開放類別命名實體抽取方法，在計算候選實體置信度時沒有考慮種子的影響，也沒有考慮不同模板在質量上的差別。因此，不能很好地計算候選實體的置信度。

發明內容

為了克服現有技術存在的缺陷，本發明提出了一種借助圖隨機游走的開放類別命名實體抽取方法和裝置，實現了從大規模文本語料中進行開放類別命名實體的抽取。

根據本發明的一個方面，提出了一種借助圖隨機游走的開放類別命名實體抽取方法，該方法包括步驟：步驟1，分析種子在語料中的上下文得到模板；步驟2，使用模板從語料抽取候選實體；步驟3，根據種子實體、模板和候選實體之間的關系來構造圖；步驟4，在圖上使用隨機游走算法計算候選實體的置信度。

優選地，步驟1進一步包括：取上下文窗口大小為3，即取種子出現的前三個詞項與后三個詞項構成模板放入模板池中。

優選地，過濾掉模板池中只出現過一次的模板。

優選地，步驟2進一步包括：依次取出模板池中的模板，將語料中匹配模板的字符串抽取出來放入候選實體池，同時記錄<候選-模板>之間的匹配關系。

優選地，在步驟2，濾掉模板池中只出現過一次的模板。

優選地，在步驟3，圖由節點和邊組成，節點分為三類：種子實體、模板和候選實體，每個種子實體、模板或候選實體在圖中都表示為一個節點，邊分為兩類：第一類是種子實體與根據該種子實體學到的模板之間用邊連接；第二類是候選實體與抽取該候選實體的模板之間用邊連接，由此得到一個無向圖，作為圖隨機游走的輸入。

優選地，步驟4進一步包括：

步驟41，構建初始狀態矩陣，在該步驟，初始狀態矩陣P₀的初始值使用如下方法計算：

其中|S|為種子集合大小，根據上述初始化方式得到的初始狀態矩陣P₀，各列元素之和等于1；

步驟42，構建狀態轉移矩陣M，在該步驟，首先構建(m+n)*(m+n)維方陣M₀，其中m為實體類節點的個數，n為模板類節點的個數，M₀中每一行記錄一個節點與其他節點的連接情況，M₀(ij)表示第i個節點和第j個節點之間的關系，i和j為整數，其取值范圍均為[1,m+n]，M₀(ij)的值設定如下：

之后對M₀的每一行進行歸一化得到狀態轉移矩陣M，使得M每一行的元素的和等于1；

步驟43，候選實體置信度計算，在該步驟，使用迭代的方法計算穩定狀態矩陣P_*，根據上一輪迭代結果P_t計算本輪迭代結果P_t+1，具體計算公式如下：

P_t+1＝0.5*M^T*P_t+0.5*P₀

當在t＝T時刻，|P_t+1-P₁|≤ε或者T＞iter時，迭代停止，則P_*＝P_t+1。這里ε表示預設的一個更新誤差，在本發明中ε＝0.001。iter表示預設的迭代次數，本方法取iter＝500。P_*中候選實體對應節點的概率值則作為該節點的置信度。