呂 航，Xiu Susie Fang，司蘇新，王 康

（東華大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，上海 201620）

0 引言

在過去的幾十年里，從搜索引擎、社交媒體平臺(tái)、眾包平臺(tái)等各種網(wǎng)絡(luò)渠道收集的數(shù)據(jù)量急劇增加。人們往往可以從不同的數(shù)據(jù)源收集同一實(shí)體的聲明信息，然而由于記錄錯(cuò)誤、機(jī)器故障、噪音、惡意攻擊等原因，這些信息可能會(huì)相互沖突。如果不解決這些沖突，從網(wǎng)絡(luò)上檢索到的信息將毫無用處。為了得到可靠的信息（即真實(shí)的事實(shí)），就需要研究多源數(shù)據(jù)的聚合技術(shù)。

近些年來，許多研究提出了多源數(shù)據(jù)聚合的方法。這些方法可以分為3類：

（1）迭代法。迭代計(jì)算來源的可靠性和聲明值的可信度。

（2）基于最優(yōu)化的方法。使每個(gè)聲明值與真實(shí)值之間的源加權(quán)距離最小。

（3）概率法。對源和聲明值的聯(lián)合分布進(jìn)行建模，使聯(lián)合分布可能性最大化。

雖然現(xiàn)有方法已取得了不錯(cuò)的效果，但大部分方法都忽視了實(shí)體屬性之間存在的各種關(guān)聯(lián)。研究可知，充分利用實(shí)體屬性之間的關(guān)聯(lián)能提升真值發(fā)現(xiàn)結(jié)果的準(zhǔn)確性。

這里通過表1中的實(shí)例來闡述這一點(diǎn)。由表1看到，實(shí)體具有年齡、出生日期、居住城市和郵編等屬性。這些屬性中存在如下關(guān)聯(lián)：年齡取決于出生日期，城市和郵編具有一一對應(yīng)關(guān)系。如果采用多數(shù)投票的方法，可能會(huì)在實(shí)體1的年齡屬性上得到錯(cuò)誤的結(jié)果為18歲。然而，通過考慮年齡和出生日期之間的依賴關(guān)系，就可以先獲得出生日期的真值，即2004年1月1日，從而得到正確的年齡為19歲。這說明如果在本文的方法中，能夠捕捉屬性間的關(guān)系，可以獲得更準(zhǔn)確的結(jié)果。

表1 實(shí)體的信息表Tab.1 Entity information table

考慮實(shí)體屬性相關(guān)性的真值發(fā)現(xiàn)研究仍處于起步階段，僅有的一些方法對實(shí)體屬性關(guān)系的捕捉還不全面，比如現(xiàn)有的研究集中于屬性的幾種特定關(guān)系，如時(shí)間關(guān)系、空間關(guān)系或常識(shí)，或?qū)傩灾g的關(guān)系采用數(shù)據(jù)間約束來表示。本文提出的異構(gòu)網(wǎng)絡(luò)模型不僅捕捉了數(shù)據(jù)源間的相似關(guān)系、數(shù)據(jù)源對聲明值的偏好選擇關(guān)系，還考慮了實(shí)體屬性的一般化關(guān)系來推斷實(shí)體屬性的真實(shí)值。接下來將基于2個(gè)真實(shí)世界數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果證明了本文的算法優(yōu)于現(xiàn)有方法。

1 圖嵌入模型

1.1 問題定義

1.2 異構(gòu)網(wǎng)絡(luò)

本節(jié)將創(chuàng)建4個(gè)網(wǎng)絡(luò)，這4個(gè)網(wǎng)絡(luò)一起構(gòu)建了一個(gè)大型的異構(gòu)網(wǎng)絡(luò)，如圖1所示，用于處理存在實(shí)體屬性關(guān)聯(lián)的真值發(fā)現(xiàn)問題。

圖1 異構(gòu)網(wǎng)絡(luò)Fig.1 Heterogeneous network

通過定義源與屬性值之間的網(wǎng)絡(luò)，能夠?qū)υ绰暶饕粋€(gè)屬性值的過程建模，這種建模可以將源的可靠性體現(xiàn)在其對聲明值的偏好選擇上。

源與源之間的網(wǎng)絡(luò)定義為G＝（∪，E），這里是源的集合，E是源與源之間的邊，邊上定義了2種不同權(quán)重。第一種W為源S和源S對給定的同一實(shí)體的同一屬性做出相同的聲明值的數(shù)量，第二種D為這2個(gè)源對給定的同一實(shí)體的同一屬性做出不同的聲明值數(shù)量。

通過定義源與源之間的網(wǎng)絡(luò)，能夠挖掘源與源之間的相似性。如果相同聲明值權(quán)重W越大于不同聲明值權(quán)重D，則說明2個(gè)源越相似。同時(shí)結(jié)合源-屬性值網(wǎng)絡(luò)中捕捉的關(guān)系，源之間的關(guān)系表明了源提供可信聲明的偏好。

4種異構(gòu)網(wǎng)絡(luò)中捕捉的各種連接關(guān)系為規(guī)范化真值發(fā)現(xiàn)建模提供了更多的證據(jù)。

1.3 網(wǎng)絡(luò)的嵌入

在本節(jié)中，提出將4種異構(gòu)網(wǎng)絡(luò)嵌入到低維空間的處理方法。由于這個(gè)異構(gòu)的網(wǎng)絡(luò)由4個(gè)子網(wǎng)絡(luò)組成，這里采用的是對每個(gè)子網(wǎng)絡(luò)進(jìn)行嵌入，再嵌入整個(gè)異構(gòu)網(wǎng)絡(luò)的方法。

對于圖G的每一條邊，定義了源S和源S的聯(lián)合概率：

越高的條件概率p表明源S和源S具有越高的相似性。即源S和源S在同一實(shí)體屬性上做出相同聲明值的概率為p。

圖G對于每一條邊定義了2種不同的權(quán)重，在已知p的條件下，可以得到2種權(quán)重的條件概率：

研究用分布去解決數(shù)據(jù)稀疏問題。此處需用到的數(shù)學(xué)公式為：

其中，是函數(shù)，，是2個(gè)超參數(shù)。

通過最大化由源-源網(wǎng)絡(luò)得到的概率，能使具有相似可靠性的源在嵌入空間內(nèi)的距離相近。即最小化損失函數(shù)O：

圖G對于每一條邊定義了2種不同的權(quán)重，在已知p的條件下，可以得到2種權(quán)重的條件概率為：

接著提出用分布去解決數(shù)據(jù)稀疏問題。推理得出的數(shù)學(xué)公式為：

其中，是函數(shù)，，是2個(gè)超參數(shù)。

通過最大化屬性-屬性網(wǎng)絡(luò)得到的概率，能使具有關(guān)系的屬性在嵌入空間內(nèi)的距離相近。即最小化損失函數(shù)O：

通過定義實(shí)體屬性-實(shí)體屬性值之間的網(wǎng)絡(luò)，能將建模的實(shí)體屬性之間的關(guān)系體現(xiàn)在屬性值層面上。定義圖G上的2條邊上的屬性值成對出現(xiàn)的概率為：

本次研究的目標(biāo)是使源、實(shí)體屬性、實(shí)體屬性值的聯(lián)合概率最大化，等價(jià)于最小化損失函數(shù)O、O、O、O，即最小化O：

1.4 模型的學(xué)習(xí)

一種直觀的解法：可以同時(shí)使用所有子網(wǎng)絡(luò)來學(xué)習(xí)并更新各種嵌入的表示。即公式（13）的優(yōu)化，也就是通過合并所有子網(wǎng)絡(luò)的邊，并對邊抽樣，抽樣的概率與其在網(wǎng)絡(luò)中的權(quán)重成正比，再根據(jù)抽樣的邊對參數(shù)的嵌入表示進(jìn)行更新。但由于不同子網(wǎng)絡(luò)的權(quán)重是不可比的，因此迭代采樣每個(gè)子網(wǎng)絡(luò)的邊，基于偏導(dǎo)對每個(gè)子網(wǎng)絡(luò)的嵌入表示進(jìn)行更新。

緊接著，計(jì)算O關(guān)于源S的偏導(dǎo)：

通過式（14）～（16）對源，屬性值的嵌入表示的更新，能使可靠的源和可信度較高的屬性值在嵌入空間距離相近。

對于源-源網(wǎng)絡(luò)，同樣計(jì)算源S關(guān)于O的偏導(dǎo)：

通過對源的嵌入表示的更新，能使具有相似可靠性的源在嵌入空間相近。

對于實(shí)體屬性-實(shí)體屬性網(wǎng)絡(luò)，同樣計(jì)算實(shí)體屬性T關(guān)于O的偏導(dǎo)：

通過對實(shí)體屬性的嵌入表示的更新，能使具有關(guān)聯(lián)的實(shí)體屬性在嵌入空間相近。

計(jì)算O關(guān)于t的偏導(dǎo)：

計(jì)算O關(guān)于a的偏導(dǎo)：

計(jì)算O關(guān)于an的偏導(dǎo)：

通過式（19）～（22）對實(shí)體屬性、屬性值的嵌入表示更新讓滿足實(shí)體屬性之間關(guān)聯(lián)的屬性值在嵌入空間靠近實(shí)體屬性。

綜上所述，就可使用隨機(jī)梯度下降（SGD）方法去更新實(shí)體屬性、源、屬性的嵌入表示。

1.5 真值的推斷

在模型學(xué)習(xí)中，得到了屬性值嵌入、源嵌入和屬性嵌入，同時(shí)對于各種嵌入的優(yōu)化讓真值嵌入和真實(shí)屬性值嵌入在嵌入空間中接近。因此通過計(jì)算集合V中每個(gè)屬性值和真值之間的相似性，相似性最高的屬性值即為屬性的真實(shí)值。

但是由于本文算法是無監(jiān)督的，并沒有真值的嵌入。為了構(gòu)造真值嵌入，文中采用對所有屬性多數(shù)投票來找到真實(shí)值，對得到的真實(shí)值的集合按照真實(shí)值的可信度進(jìn)行排序，從排序的真實(shí)值集合選取前個(gè)真實(shí)值并取其平均值作為真值的嵌入。

2 實(shí)驗(yàn)

研究采用Python（3.6）實(shí)現(xiàn)了所有的基線方法和本文提出的模型（GETD），所有的實(shí)驗(yàn)都是在Intel Core i5-7200U CPU＠2.50 GHz的電腦上運(yùn)行的。

2.1 數(shù)據(jù)集

（1）Restaurant：該數(shù)據(jù)集包括來自5個(gè)源提供的信息。每個(gè)餐廳是一個(gè)實(shí)體，每個(gè)實(shí)體有5個(gè)分類屬性：餐廳名稱、建筑編號、街道名稱、郵政編碼和電話號碼。

（2）Weather：該數(shù)據(jù)集包含9個(gè)來源提供的信息，每個(gè)城市是一個(gè)實(shí)體，每個(gè)實(shí)體具有30個(gè)分類屬性，即一個(gè)月內(nèi)的天氣情況。

真實(shí)數(shù)據(jù)集的統(tǒng)計(jì)結(jié)果見表2。

表2 真實(shí)數(shù)據(jù)集的統(tǒng)計(jì)Tab.2 The statistics of real-world datasets

2.2 評價(jià)指標(biāo)

錯(cuò)誤率（）：推斷的實(shí)體屬性真實(shí)值與中不同的數(shù)量占的百分比，越小的錯(cuò)誤率表明實(shí)驗(yàn)結(jié)果越好。

2.3 對比算法

（1）Majority Voting：該方法認(rèn)為在所有源中出現(xiàn)次數(shù)最多的聲明值為真值。

（2）TruthFinder：通過給定源的可靠性，去推斷真值，再根據(jù)真值去推斷源的可靠性，迭代更新源的可靠性和真值至收斂。

（3）CRH：將真值發(fā)現(xiàn)視為一個(gè)最優(yōu)化問題，采取兩步迭代更新，一步更新源權(quán)重，一步更新值的可信度。

（4）CATD：采用最優(yōu)化的方法解決真值發(fā)現(xiàn)問題，將源的權(quán)重采用置信區(qū)間的方式建模，以解決數(shù)據(jù)稀疏問題。

（5）CASE：通過使用一種嵌入方法，解決真值發(fā)現(xiàn)問題，但不考慮屬性之間的關(guān)系。

（6）CTD：將真值發(fā)現(xiàn)視為一個(gè)最優(yōu)化問題，同時(shí)使用數(shù)據(jù)庫約束來捕捉屬性關(guān)聯(lián)的方法。

2.4 實(shí)驗(yàn)設(shè)置

為了確保公平的對比，研究運(yùn)行了一系列的實(shí)驗(yàn)來為每個(gè)基線方法設(shè)定最優(yōu)的參數(shù)。對于本文的方法，設(shè)置嵌入維度為12。對于SGD方法，設(shè)置學(xué)習(xí)率為0.1。設(shè)置函數(shù)中和為1.1。對于真值的推斷步驟中值設(shè)為3%。

2.5 實(shí)驗(yàn)結(jié)果

在表3和表4中列出了不同真值發(fā)現(xiàn)算法在Restaurant數(shù)據(jù)集和Weather數(shù)據(jù)集上實(shí)驗(yàn)3次的運(yùn)行結(jié)果及平均的錯(cuò)誤率。從實(shí)驗(yàn)結(jié)果中，可以看到本文提出的GETD方法在2個(gè)真實(shí)世界數(shù)據(jù)集上都優(yōu)于其他方法，這是因?yàn)檫@些基線方法大多都沒有考慮屬性之間的關(guān)系，只是單純地考慮數(shù)據(jù)源的可靠性或相似性，并不能捕捉屬性之間的關(guān)系，導(dǎo)致實(shí)驗(yàn)精度不夠。CTD算法雖然考慮了屬性之間的關(guān)系，但是算法的reduction部分并未考慮迭代，導(dǎo)致了精度的丟失。本文提出的GETD模型在考慮源的可靠性與源的相似性的基礎(chǔ)上，全面捕捉了一般化的屬性關(guān)系，能夠更加精準(zhǔn)地挖掘底層數(shù)據(jù)之間的關(guān)聯(lián)。

表3 基于Restaurant數(shù)據(jù)集的對比結(jié)果Tab.3 Comparison results based on Restaurant dataset

表4 基于Weather數(shù)據(jù)集的對比結(jié)果Tab.4 Comparison results based on Weather dataset

2.6 不同L值對實(shí)驗(yàn)結(jié)果的影響

通過在Restaurant數(shù)據(jù)集上采用不同值，研究該參數(shù)對實(shí)驗(yàn)結(jié)果準(zhǔn)確性的影響。在這個(gè)實(shí)驗(yàn)中采用實(shí)驗(yàn)效果最好的CTD作為對比算法。實(shí)驗(yàn)結(jié)果如圖2所示，當(dāng)值低于2%時(shí)，GETD的錯(cuò)誤率較高，效果不如CTD，但當(dāng)值較大時(shí)，本文的方法始終優(yōu)于CTD算法。根據(jù)實(shí)驗(yàn)結(jié)果，文中將設(shè)置3%。

圖2 Restaurant數(shù)據(jù)集上不同L值對錯(cuò)誤率的影響Fig.2 Influence of different L on error rate in Restaurant dataset

3 結(jié)束語

本文采用基于異構(gòu)網(wǎng)絡(luò)的圖嵌入方法解決了存在屬性關(guān)聯(lián)的真值發(fā)現(xiàn)問題。提出的模型構(gòu)建了4個(gè)異構(gòu)網(wǎng)絡(luò)，包括源-屬性值、源-源、實(shí)體屬性-實(shí)體屬性和實(shí)體屬性-實(shí)體屬性值網(wǎng)絡(luò)。同時(shí)，通過源-屬性值網(wǎng)絡(luò)捕捉源可靠性與屬性值可信度的關(guān)系、源-源網(wǎng)絡(luò)捕捉源之間的相似性關(guān)系、實(shí)體屬性-實(shí)體屬性網(wǎng)絡(luò)捕捉屬性之間的關(guān)系，實(shí)體屬性-實(shí)體屬性值網(wǎng)絡(luò)將建模的實(shí)體屬性之間的關(guān)系體現(xiàn)在屬性值層面上，對每個(gè)子網(wǎng)絡(luò)采取隨機(jī)梯度下降的方法來更新嵌入表示，最后根據(jù)嵌入表示來推斷真值。在2個(gè)真實(shí)世界數(shù)據(jù)集上的實(shí)驗(yàn)證明了該模型的有效性。