祁祥威

（西南交通大學(xué)制造業(yè)產(chǎn)業(yè)鏈協(xié)同與信息化支撐技術(shù)四川省重點(diǎn)實(shí)驗(yàn)室，成都 611756）

0 引言

實(shí)體解析（entity resolution，ER）是一種用于識(shí)別數(shù)據(jù)集中多個(gè)數(shù)據(jù)記錄是否為同一現(xiàn)實(shí)世界實(shí)體的技術(shù)。隨著時(shí)代的發(fā)展，實(shí)體解析成為了大數(shù)據(jù)應(yīng)用中數(shù)據(jù)清洗和數(shù)據(jù)集成的關(guān)鍵技術(shù)之一［1］，并且在信息檢索、人工智能、機(jī)器學(xué)習(xí)、數(shù)據(jù)庫等各個(gè)領(lǐng)域中都受到了相當(dāng)?shù)闹匾暋?/p>

目前實(shí)體解析技術(shù)在各個(gè)領(lǐng)域都有不同的適用于其領(lǐng)域的方法，但還是以統(tǒng)計(jì)學(xué)中的概率決策為主，即，計(jì)算記錄之間屬性值的相似度，根據(jù)相似值與預(yù)設(shè)的屬性級(jí)閾值或記錄級(jí)閾值，判斷兩條記錄是否匹配［2］。

而數(shù)據(jù)空間是以圖數(shù)據(jù)庫為基礎(chǔ)的數(shù)據(jù)管理系統(tǒng)，集成了大量異質(zhì)數(shù)據(jù)，沒有統(tǒng)一的語義［3］，無法將不同的記錄的屬性值進(jìn)行一一對應(yīng)，從而無法進(jìn)行基于統(tǒng)計(jì)學(xué)的實(shí)體解析。但數(shù)據(jù)空間中存有實(shí)體之間的關(guān)系，從實(shí)體之間的關(guān)系入手可以有效地進(jìn)行數(shù)據(jù)空間的實(shí)體解析任務(wù)。

1 相關(guān)技術(shù)

1.1 數(shù)據(jù)空間

數(shù)據(jù)空間是為了應(yīng)對海量異構(gòu)的數(shù)據(jù)，由Franklin 提出的一個(gè)概念：一個(gè)數(shù)據(jù)空間由一系列相關(guān)的異構(gòu)資源對象集和資源對象間的關(guān)聯(lián)關(guān)系集組成，包含某個(gè)組織或個(gè)體相關(guān)的一切信息，這些信息可以以任意形式，在任意地方存儲(chǔ)；在將數(shù)據(jù)加入到數(shù)據(jù)空間之前，無需像關(guān)系數(shù)據(jù)庫事先為其定義嚴(yán)格的關(guān)系模式，直接將數(shù)據(jù)源加入數(shù)據(jù)空間，并以pay-as-you-go模式實(shí)現(xiàn)數(shù)據(jù)的管理［4］。數(shù)據(jù)空間主要具有數(shù)據(jù)優(yōu)先、模式滯后的特點(diǎn)［5］，即優(yōu)先集成數(shù)據(jù)，隨著數(shù)據(jù)的不斷加入再進(jìn)行數(shù)據(jù)模式的演化。

1.2 實(shí)體關(guān)系模型

實(shí)體關(guān)系模型是一種描述現(xiàn)實(shí)世界中實(shí)體之間關(guān)系的模型，通常被應(yīng)用于數(shù)據(jù)庫設(shè)計(jì)和數(shù)據(jù)建模領(lǐng)域。實(shí)體通常指從現(xiàn)實(shí)生活抽象出的一種有區(qū)分性的概念，可以指向具體的物體，如房子、車，也可以是一種邏輯上的概念，如交易、訂單。而關(guān)系則描述了實(shí)體之間的連接方式，一般有三種：“一對一”“一對多”和“多對多”。

2 算法實(shí)現(xiàn)

利用實(shí)體間關(guān)系進(jìn)行實(shí)體解析的思想比較簡單。首先，找到兩側(cè)的實(shí)體至少有一個(gè)具有唯一性的關(guān)系，即，實(shí)體之間“一對一”或“一對多”的關(guān)系，稱為“決策關(guān)系”。將決策關(guān)系兩端的只能有一個(gè)出度或入度的結(jié)點(diǎn)（這里表示的是數(shù)據(jù)記錄）稱為決策結(jié)點(diǎn)。例如，“顧客”“酒店房間”之間的“預(yù)訂”關(guān)系，就可以稱為決策關(guān)系，而“酒店房間”則稱為決策結(jié)點(diǎn)。因?yàn)樵谶@個(gè)關(guān)系中，“顧客”可以預(yù)訂多個(gè)“酒店房間”，但是“酒店房間”不能被多個(gè)“顧客”預(yù)訂（見圖1）。

其次，在數(shù)據(jù)空間中，查詢所有與決策結(jié)點(diǎn)具有決策關(guān)系的結(jié)點(diǎn)，在這些結(jié)點(diǎn)之間增加一個(gè)“匹配”關(guān)系（見圖2）。

圖2 基于實(shí)體關(guān)系進(jìn)行匹配

最后，將結(jié)點(diǎn)進(jìn)行分組合并。具體過程如下：

（1）為每一個(gè)結(jié)點(diǎn)分配一個(gè)整數(shù)ID 作為標(biāo)識(shí)；

（2）將這個(gè)ID 傳送到與之具有“匹配”關(guān)系的相鄰的結(jié)點(diǎn)；

（3）使用從相鄰結(jié)點(diǎn)接收到的最小值ID 作為結(jié)點(diǎn)的新ID；

（4）重復(fù)步驟（2）、（3）直到?jīng)]有可以更新的ID；

（5）將具有相同ID的結(jié)點(diǎn)分為一組；

（6）對于每組內(nèi)的結(jié)點(diǎn)，保留其中一個(gè)并使其繼承其它結(jié)點(diǎn)的屬性，刪除其它的結(jié)點(diǎn)。

3 實(shí)驗(yàn)結(jié)果與分析

目前對于異質(zhì)數(shù)據(jù)的實(shí)體解析任務(wù)，尚未有公認(rèn)的數(shù)據(jù)集，因此，根據(jù)研究對象的特點(diǎn)，構(gòu)建了包含顧客和房間兩種對象的小規(guī)模數(shù)據(jù)集作為實(shí)驗(yàn)數(shù)據(jù)，見表1。

表1 包含顧客和房間兩種對象的小規(guī)模實(shí)驗(yàn)數(shù)據(jù)集

如表1所示，顧客擁有的不同屬性用于表達(dá)數(shù)據(jù)空間中集成的異質(zhì)數(shù)據(jù)，即，沒有統(tǒng)一的語義。將上述數(shù)據(jù)進(jìn)行前文所描述的算法，則可以得到?jīng)Q策實(shí)體類型為房間，決策結(jié)點(diǎn)為結(jié)點(diǎn)1、結(jié)點(diǎn)2和結(jié)點(diǎn)3。

本文以Neo4J為基礎(chǔ)進(jìn)行算法的驗(yàn)證。數(shù)據(jù)的初始狀態(tài)如圖3所示。

圖3 Neo4j中數(shù)據(jù)初始狀態(tài)

通過上文所述算法過程，如圖4 所示，Costomer 4、Costomer 5 和Costomer 6 之間增加了“Matches”關(guān)系，而Costomer 7 和Costomer 8之間增加了“Matches”關(guān)系。最后通過連通分量算法進(jìn)行冗余結(jié)點(diǎn)的刪除，得到如圖5所示的結(jié)果。可以看出，該算法簡潔有效。

圖4 Neo4j中進(jìn)行匹配后的數(shù)據(jù)

圖5 進(jìn)行屬性繼承和刪除冗余結(jié)點(diǎn)后的數(shù)據(jù)

4 結(jié)語

實(shí)體解析是一個(gè)領(lǐng)域性較強(qiáng)的問題，不同的領(lǐng)域有著適合該領(lǐng)域的方法。對于結(jié)構(gòu)性較強(qiáng)的數(shù)據(jù)，可以采用基于屬性值相似度計(jì)算的辦法。但是在數(shù)據(jù)空間中，大量的數(shù)據(jù)是異質(zhì)，沒有統(tǒng)一的語義，無法運(yùn)用類似的實(shí)體解析方法。本文針對這個(gè)問題，從數(shù)據(jù)空間中的數(shù)據(jù)關(guān)系入手，提出了基于實(shí)體關(guān)系的實(shí)體解析方法，并通過構(gòu)建小規(guī)模數(shù)據(jù)集驗(yàn)證了算法的有效性。但是對于缺少?zèng)Q策關(guān)系的數(shù)據(jù)，本算法則有一定的局限性，有待后續(xù)研究。