論文閱讀：Robust Entity Resolution using Random Graphs
原文鏈接
參考資料：
數(shù)據(jù)中國(guó)
論文題目：Robust Entity Resolution using Random Graphs
發(fā)表時(shí)間：SIGMOD’18, June 10-15, 2018, Houston, TX, USA
論文作者：Sainyam Galhotra 、 Donatella Firmani、 Barna Saha 、Divesh Srivastava
Indroduction
論文的意思是利用隨機(jī)圖，來完成實(shí)體解析(Entity Resolution),那么何為實(shí)體解析呢？
根據(jù)《實(shí)體解析與信息質(zhì)量》，可以了解到：
實(shí)體解析（Entity Resolution）是一種用于判斷兩條記錄是否指向同一事物的過程。
實(shí)體這個(gè)術(shù)語描述了過程的目標(biāo)是真實(shí)世界的事物，比如某個(gè)人，地點(diǎn)或者物品。
而解析則描述了回答這樣的一個(gè)問題的過程：兩條不同記錄是否指向了同一個(gè)真實(shí)實(shí)體？
盡管實(shí)體解析的定義描述的是兩條記錄之間的關(guān)系，但事實(shí)上，這個(gè)定義也可以被延伸到一個(gè)更大的記錄集合上，相應(yīng)的，該過程的輸出則聚合了指向同一實(shí)體的所有記錄的子集/簇。在這樣的上下文中，ER的定義也可以解釋為：“識(shí)別并整合所有定義同一真實(shí)世界實(shí)體的記錄的過程”（Benjelloun,Garcia-Molina, Menestrina, et al., 2009）。
例如在上圖中，實(shí)體解析的意思就是，判斷出有哪一些表示的是同一個(gè)物體，比如上面的iPhone Two和iPhone 2表示的就是同一個(gè)手機(jī)。
又如上圖中，實(shí)體解析就是選出哪些照片表示的是同一個(gè)人，這里有古天樂，周星馳，張震。
Previous approach
這里介紹以前的方法，我們用上面提到的判斷照片是否是同一個(gè)人舉例，這樣做的前提是我們已經(jīng)得出了，這兩個(gè)照片是同一個(gè)人的概率是多少。怎么得出呢，微軟提供了這個(gè)服務(wù)。
Microsoft tool TwinsOrNot
可以在這個(gè)網(wǎng)站，上傳照片進(jìn)行對(duì)比識(shí)別。
在進(jìn)行完，上傳對(duì)比之后，我們可以得到，上面的概率圖，其中綠色就表示為同一個(gè)人概率超過0.5的，紅色就是低于0.5，線越粗，概率越高，紅色虛線說明概率極低。得到概率圖之后，就要在此圖上運(yùn)用方法找出所有同一個(gè)人的照片了。
在這種方法里，只要是綠色連接的照片我們就認(rèn)為是同一個(gè)人，以此來進(jìn)行劃分，得到結(jié)果。顯然這種方法并不準(zhǔn)確，高度依賴于事先判斷的概率，這里就把張震和周星馳當(dāng)作了同一個(gè)人。
每條邊上都有相似的概率，這種方法就是把概率特別相近的劃分到一起，當(dāng)作是同一個(gè)人。我們可以從上圖中看到，這種方法也是錯(cuò)誤的，它并沒有把所有的周星馳照片都找出來（因?yàn)槟贻p的周星馳和年老的周星馳相似概率并不高）。
正確的劃分得到的應(yīng)該是如圖所示的這樣，分成了三個(gè)組，找出了古天樂、周星馳、張震。
為了準(zhǔn)確的找出所有的人，引入了Oracle這個(gè)概念，并不是指的數(shù)據(jù)庫公司，而是表示為一種眾包的抽象。因?yàn)樵诤芏嗲闆r下，人去判斷是否相似，是要比計(jì)算機(jī)容易很多的。例如：
Online advertising = Internet ad
人們可以很快的判斷出這兩者都是網(wǎng)絡(luò)廣告的意思，但計(jì)算機(jī)卻很困難，所以提出的Oracle相當(dāng)于是一個(gè)系統(tǒng)，可以回到如下的問題。
而且我們假定，Oracle總是會(huì)回答正確。
我們有了Oracle，并且Oracle總是會(huì)給出正確的答案，顯然可以通過Oracle來回答兩張照片是否是同一個(gè)人這種問題。那應(yīng)該如何覺得詢問的順序呢？也就是應(yīng)該選擇哪兩張照片去詢問呢。
這里有兩種方式，其一就是普通的方式，隨機(jī)選取一對(duì)進(jìn)行詢問，顯然這種方法是耗時(shí)、耗力的。其二就是聰明的方法，根據(jù)概率的大小去進(jìn)行詢問，先詢問概率大的，因?yàn)樗麄兏赡苁峭粋€(gè)人。
通常來說，以前使用的方法就是按照邊的概率進(jìn)行詢問的方法。
在這里我們先訪問古天樂那條邊，得到的結(jié)果是是同一個(gè)人。
然后詢問其他的邊，得出了正確你的結(jié)果。
在詢問完成后，得出了正確的結(jié)果，完成了實(shí)體解析。
我們假設(shè)的是Oracle總是給出正確的結(jié)果，但是如果Oracle給出了錯(cuò)誤的結(jié)果，
例如在上圖中把周星馳和張震當(dāng)作一個(gè)人，那么我們最后的實(shí)體解析就是錯(cuò)誤的。
Our approach
以前的方法，都是假設(shè)Oracle一定會(huì)回答正確，但是實(shí)際情況中Oracle并不總能回答正確，會(huì)得到錯(cuò)誤的結(jié)果。所以這篇論文就提出了，一個(gè)糾正錯(cuò)誤的工具。
這是這篇論文中，實(shí)體解析的處理流程，實(shí)現(xiàn)進(jìn)行記錄的收集，也就是上圖的收集那些照片，再之后就是使用前文所講的策略，以及本文提出的糾錯(cuò)層。
這個(gè)糾錯(cuò)層的關(guān)鍵思想有兩方面：
1、在并入新結(jié)點(diǎn)時(shí)，進(jìn)行多次的判斷。
2、通過合并以及分裂過程來進(jìn)行糾錯(cuò)。
在并入新結(jié)點(diǎn)時(shí)，我們不再只是查詢一對(duì)，而是查詢?cè)S多對(duì)，如上圖中要將New Node并入其中時(shí)，我們會(huì)對(duì)許多對(duì)進(jìn)行判斷，如果相似的值達(dá)到了閾值，則認(rèn)為時(shí)一個(gè)人，將新結(jié)點(diǎn)放入其中。
合并過程主要是為了提高recall，也就是召回率，意思就是希望可以找到所有的同一個(gè)人照片。主要的過程就是，在兩個(gè)聚類中的結(jié)點(diǎn)，不斷的進(jìn)行詢問，判斷是否為一個(gè)人，然后決定是否合并。
在已經(jīng)完成的聚類里面，會(huì)存在Low confidence node ，就是紙盒部分結(jié)點(diǎn)連接，比如圖中的張震，這種結(jié)點(diǎn)，就很有可能，并不屬于這個(gè)聚類。所以我們應(yīng)該想辦法對(duì)其進(jìn)行判斷。
解決的辦法，就是判斷Low confidence node和其他結(jié)點(diǎn)的相似度，如圖中，判斷出不相似，那就將其剔除。
前文所說，這是一個(gè)糾錯(cuò)的工具，所以會(huì)有使用上面的不同，這里介紹了三種不同的使用方法：
使用方法一：
Eager:每一次查詢，都使用這個(gè)糾錯(cuò)的工具。這樣會(huì)降低效率，召回率降低，就是不
能找到所有的同一個(gè)人的照片，但是準(zhǔn)確度會(huì)變高。
使用方法二：
Lazy:不使用糾錯(cuò)的工具。這樣會(huì)讓準(zhǔn)確度降低，但是召回率變高。
使用方法三：
Adaptive pipeline:高概率的結(jié)點(diǎn)就不適用糾錯(cuò)工具，就是兩張已經(jīng)很相似的照片，不
會(huì)再使用工具詢問。
Experiments
上圖是在不同的數(shù)據(jù)集上做的實(shí)驗(yàn)，橫坐標(biāo)表示查詢的數(shù)量，縱坐標(biāo)表示效果，得分越高，效果越好，從圖中看出，Adaptive pipeline的效果是非常好的，僅次于理想情況。
