基于屬性模式的實體識別框架

何峰權等

摘要：很多領域都面臨實體識別問題，但現有解決框架缺乏通用性。提出了一種基于屬性模式的領域無關的實體識別框架。屬性的模式代表屬性與實體的一種關系，將模式分為四種類型分別處理，針對類型特點提出了更為通用的相似度計算方法。系統根據模式類型決定相似度計算策略，使系統具有更強的擴展性。該框架可以有效綜合利用各類屬性的特點進行實體識別，結果優于一般的基于屬性特征或基于實體關系的方法。

關鍵詞：實體識別； 屬性模式； 擴展性； 框架

中圖分類號：TP319.9 文獻標識碼：A文章編號：2095-2163（2014）01-0065-04

0引言

實體識別就是判別來自一個數據源或多個數據源的描述是否指向同一個實體。此問題由來已久，現已提出很多方法。解決實體識別問題所利用的信息可分為兩類，屬性特征信息和關系信息。基于屬性特征的方法最簡單、使用得也最多，但卻因屬性信息有限，在某些情況下并不足以提供高置信度的判斷結論。越來越多的方法開始利用屬性的關系或規則進行實體識別，但利用這種關系的方式卻各不相同，導致缺乏通用性。對每個實體識別問題都需要重新設計解決方案也必將是低效的，因而需要開展研究，予以改進。

本文將不同屬性與實體的關系模式概括為四種類型，通過模式類型決定相似度計算策略，再根據屬性的格式決定基本的相似度計算函數。系統將多個屬性的相似度組織成向量的形式表示，通過監督學習的方法形成判決器，最后在實體關系圖上完成迭代劃分。

1相關研究

文獻[1，2]研究了相似函數選擇和閾值確定問題。通過發現相似函數和閾值的冗余，去除不合適的相似函數和閾值設置。為了有效整合多種方法的優點，文獻[3]提出了一種按有監督學習的結果聚類分配權重的方法，為權重分配提供了新的思路，但選擇作為聚類的特征是經驗性的，是否可以推廣尚未確定。文獻[4]設計了一個領域無關的實體識別系統，可以通過學習的方式對數據的格式進行轉化，以滿足識別系統進行比較的需要。文獻[5]研究了利用合作者集合的相關性的方法，實驗證明其優于一般的非整體分析的方法。

2基于屬性模式的實體識別框架介紹

系統結構如圖1所示，主要分為以下幾個部分：

（1）相似度度量策略形成模塊。該模塊通過屬性的模式和數據格式自動地選擇相似度函數，形成相似度度量策略。

（2）相似度計算模塊。該模塊按照選擇的相似度函數計算實體對的相似度。

（3）判決器模塊。該模塊在訓練階段統計實體對的相似度分布情況，在實體劃分階段輔助判斷。

（4）實體關系圖。實體劃分階段在實體關系圖上迭代進行，每次完成實體合并以后，重新計算經過調整的實體對的相似度，直到所有相似邊都處理完畢，實體劃分結束。

3系統各部分的實現

3.1相似度計算策略的形成

為了實現系統的通用性，相似度計算策略必須領域無關地進行。為此分析了實體與屬性間的關系，按其特點進行了分類。利用各屬性的模式可以確定相似度計算的方法。

3.3實體劃分算法

實體劃分在實體關系圖上進行。實體關系圖的頂點表示記錄，邊表示實體對間的相似度，通過邊的操作進行實體劃分。

關系圖的頂點分為兩類，一類是原始頂點，其中只包含一條記錄；另一類是劃分過程中新形成的點，稱為超點，超點帶有表示實體的標簽，且包含此實體的記錄的集合。邊e代表的是實體對間存在相似，邊的權值為相似向量。原始關系圖中僅含原始頂點，當所有實體對的相似向量計算完畢，并建立起原始關系圖后，就可開始進行實體劃分了。

實體劃分算法主要過程為：從未標記邊中選擇相似度最大的邊，查詢判決器，若大于判斷閾值，則判為同一實體，合并相關頂點，即CLUSTER操作，有關邊的相似度則需要進行重新計算；否則即對邊做暫時標記。繼續在剩下未標記邊中尋找相似度值最大的邊，重復此過程。當沒有未標記邊剩余時，再對標記邊進行拆分操作SPLIT，直到無邊剩余。

CLUSTER操作主要是對頂點進行合并或創建。當邊的對象（e.O）與端點標簽相同時進行合并，否則就需要新建頂點。具體操作如表2所示。其中，邊所連接的記錄為x和y，記錄所在的頂點分別為u，v。頂點調整過程中，特別當頂點包含的記錄增多后，頂點的屬性集合增大，此屬性的相關度也可能增大，此時需要重新計算有關邊的相似度。

5結束語

本文提出了一種基于模式的實體識別方法，針對模式特點的相似度計算方法更具有通用性。以向量表示屬性的相似度，通過監督學習形成判決器。實體劃分階段每次選擇最相似的實體對，通過查詢判斷單元進行判斷，更新相關實體對的相似向量，并迭代進行實體劃分。實驗結果表明能自動有效地進行實體劃分。現存的問題包括平均劃分相似空間的方法不夠精細，用戶要求的準確率較高時，召回率較低。下一步的研究重點包括判斷器的劃分方式以及當用戶輸入較高判斷閾值情況下如何提高系統的召回率。

參考文獻：

[1]MENESTRINA D， WHANG S E， GARCIA-MOLINA H. Evaluation of entity resolution approaches on real-world match problems[C]//VLDB， 2010：208-219.

[2]WANG Jiannan， LI Guoliang， YU Xu ， et al. Entity matching： how similar is similar[C]//VLDB，2011：622-633.

[3]CHEN Z， KALASHNIKOV D V， MEHROTRA S.Exploiting context analysis for combining multiple entity resolution systems[C]//SIGMOD，2009：207-218.

[4]TEJADA S， KNOBLOCK C A， MINTON S. Learning domain-independent string transformation weights for high accuracy object identification[C]//Proc. Eighth ACM SIGKDD Intl Conf. Knowledge Discovery and Data Mining （KDD 02）， 2002.

[5]BHATTACHARYAI， GETOOR L. Collective entity resolution in relational Data[C]//TKDD， 2007. [1] [2] [3] [4] [5]