[發明專利]一種基于唯一性約束的Deep Web實體識別方法

有效

• 申請號: 201210330860.2
• 申請日: 2012-09-10
• 公開（公告）號: CN103257983A
• 公開（公告）日: 2013-08-21
• 發明（設計）人: 趙朋朋;辛潔;陸姍姍;鮮學豐;崔志明
• 申請（專利權）人: 蘇州大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 南京經緯專利商標代理有限公司 32200
• 代理人: 曹毅

技術領域

本發明涉及一種信息集成技術的方法，尤其涉及一種關于唯一性約束的Deep?Web實體識別方法。

背景技術

??據統計，Web上蘊含的信息量以每年30%的速度增長。很多領域擁有大量數據源并且部分數據重疊。不同數據源提供同一實體的信息，它們可能以不同方式表示同一屬性值，有的數據源甚至提供錯誤的屬性值。數據集成中的一個重要環節就是連接并融合指向同一實體的不同記錄。

?在實踐中，很多屬性滿足唯一性約束，即每個實體（或者大多數實體）在這些屬性上具有唯一值，如圖書的名稱、出版社、ISBN（國際標準書號）等。但是，有時這些數據不是都滿足唯一性約束，可能是因為一些數據源提供錯誤的屬性值，也可能因為少數的例外情況（例如有些圖書的ISBN有兩種：ISBN-10和ISBN-13）。傳統的實體識別方法（方法一）一般分為兩步：1）記錄連接(Record?Linkage)，即連接那些可能指向同一實體的記錄集合。記錄連接在過去一段時間內已經被廣泛研究，在某種程度上，每個記錄集合需要隱式地保持數據的一致性或者顯式地強制數據的唯一性。然而當錯誤值存在時，記錄匹配的準確度明顯下降；2）數據融合(Data?Fusion)，即合并每個記錄集合，并對每個實體的屬性解決可能存在的數據沖突從而確定正確的屬性值。數據融合是一個新的領域，它研究如何合并連接的記錄和解決沖突。最近，在沖突解決的方法中，已經提出了考慮數據源精準度和數據源之間依賴性的高級技術。

?然而，方法一存在三個問題：第一，錯誤的屬性值可能會導致錯誤的實體識別；第二，方法一由于強制唯一性約束會錯過其他正確的屬性值；第三，為每個實體的記錄集合進行局部的數據融合可能會忽略重要的全局證據。

發明內容

為解決上述問題，本發明提供一種基于唯一性約束的Deep?Web實體識別方法，不僅僅是記錄連接和數據融合兩方面的簡單結合，而是將它們無縫地集成在k部圖聚類中。

為實現上述技術目的，達到上述技術效果，本發明通過以下技術方案實現：

一種基于唯一性約束的Deep?Web實體識別方法，包括以下步驟：

步驟1）唯一性約束定義

?硬性唯一性約束

?設????????????????????????????????????????????????是領域上的一組實體，為上的一個屬性。如果中的每個實體在屬性上具有唯一的值，包括空值，那么定義一個在上關于的唯一性約束，表示為；

?軟性唯一性約束?

?設是領域上的一組實體，是上的一個屬性。一個在上關于的軟性唯一性約束定義為，其中是一個實體在上有多個值的上限邊界概率，是上的一個值被多個實體共享的上限邊界概率；

?k部圖編碼

?設是一組實體，是上的k個唯一性屬性,是一組為提供數據的數據源，那么的部圖編碼是一個無向圖，使得

·?中的每個結點表示屬性的一種值表述方式，由中的某個數據源提供；

·?每條邊(，，，)表示存在一條記錄使得和都屬于這條記錄，并將提供這樣記錄的數據源集合記為；

?編碼的解決方案

?設是實體集合上由數據源集合提供的一個部圖編碼，那么該編碼的解決方案包含兩部分：

·?對于每個，存在一個的聚類，使得中的每一類別表示屬性的一個唯一值；

·?對于每個類別對和(，，，)，當且僅當它們屬于中的同一實體時，存在一條邊連接和；

步驟2）基于唯一性約束的實體識別

（a）硬性約束下的聚類算法

??給定一個聚類，它的索引定義如下：

??其中表示和之間的距離，

??具體過程如下：

（1）初始化，首先根據相似性為每個屬性聚類，然后，在鍵值屬性的類別集合和非鍵值屬性的類別集合之間應用Hungarian算法找到具有最強關聯的一對一的匹配關系；

（2）調整，對于每個結點，在不改變其它結點所屬類別的前提下，計算將分配到每個類別后的索引，將分配到使得索引最小的那個類別中；

（3）收斂檢查，重復執行（2），直到聚類結果不再改變為止；

??（b）軟性約束下的匹配算法?

?軟性約束下的匹配問題可以歸結為下面的介于鍵值屬性和每個軟性唯一性屬性之間的優化問題：

?

???具體過程如下：

（1）結點選擇，考慮屬性