周寧南 盛萬(wàn)興 劉科研 張 孝 王 珊

1（中國(guó)電力科學(xué)研究院 北京 100192）2（數(shù)據(jù)工程與知識(shí)工程教育部重點(diǎn)實(shí)驗(yàn)室（中國(guó)人民大學(xué)） 北京 100872）3（中國(guó)人民大學(xué)信息學(xué)院 北京 100872）（zhangxiao＠ruc．edu．cn）

大數(shù)據(jù)集成中確定數(shù)據(jù)準(zhǔn)確屬性值的WR方法

周寧南1，3盛萬(wàn)興1劉科研1張 孝2，3王 珊2，3

1（中國(guó)電力科學(xué)研究院 北京 100192）
2（數(shù)據(jù)工程與知識(shí)工程教育部重點(diǎn)實(shí)驗(yàn)室（中國(guó)人民大學(xué)） 北京 100872）3（中國(guó)人民大學(xué)信息學(xué)院 北京 100872）
（zhangxiao＠ruc．edu．cn）

大數(shù)據(jù)集成是提供高質(zhì)量數(shù)據(jù)以進(jìn)行決策的基礎(chǔ)．集成的一個(gè)關(guān)鍵環(huán)節(jié)是根據(jù)實(shí)體在數(shù)據(jù)庫(kù)中的不同元組確定其準(zhǔn)確屬性值．最新的R－topK方法在數(shù)據(jù)上實(shí)施人工設(shè)計(jì)的規(guī)則確定屬性值間的準(zhǔn)確程度，得到了相對(duì)準(zhǔn)確的屬性值．然而這種方法在處理多個(gè)可能的準(zhǔn)確值或設(shè)計(jì)的規(guī)則存在沖突等情況下需要較多人工交互．為此提出基于權(quán)重規(guī)則的WR（weighted－rule）方法確定大數(shù)據(jù)集成中數(shù)據(jù)的準(zhǔn)確屬性值．該方法為屬性值間準(zhǔn)確程度的判斷規(guī)則擴(kuò)充了權(quán)重，在準(zhǔn)確值發(fā)生沖突時(shí)避免了R－topK

方法中人工交互干預(yù)．基于追逐過(guò)程設(shè)計(jì)了約束條件推理算法，并證明它能夠在O（n2）內(nèi)推導(dǎo)出每對(duì)屬性值間的帶權(quán)重的準(zhǔn)確程度，形成推導(dǎo)準(zhǔn)確屬性值的約束條件．面對(duì)約束條件中可能的沖突，提出了目標(biāo)求解算法，在O（n）時(shí)間內(nèi)從所有屬性值組合中搜索最可能的準(zhǔn)確屬性值．在真實(shí)和合成數(shù)據(jù)集中進(jìn)行了充分的實(shí)驗(yàn)，驗(yàn)證了WR方法的效果和效率．WR方法較R－topK方法在性能上提高了3～15倍，在效果上提升7%～80%．

大數(shù)據(jù)集成；數(shù)據(jù)質(zhì)量；數(shù)據(jù)準(zhǔn)確性；數(shù)據(jù)清洗；權(quán)重規(guī)則

隨著大數(shù)據(jù)時(shí)代的到來(lái)，大數(shù)據(jù)集成［1］為政府、企業(yè)、個(gè)人根據(jù)數(shù)據(jù)進(jìn)行決策提供了數(shù)據(jù)基礎(chǔ)［2－3］．大數(shù)據(jù)集成由3個(gè)環(huán)節(jié)組成［1－2］．不同數(shù)據(jù)源中的數(shù)據(jù)經(jīng)過(guò)第1個(gè)環(huán)節(jié)模式匹配［3］被收集起來(lái)，并在第2個(gè)環(huán)節(jié)記錄連接［4－5］結(jié)束后按照相關(guān)的實(shí)體分類．面對(duì)前2個(gè)環(huán)節(jié)收集到的數(shù)據(jù)庫(kù)中同一實(shí)體e的記錄集合｛t1，t2，…，tk｝，大數(shù)據(jù)集成的第3個(gè)環(huán)節(jié)提出了數(shù)據(jù)的準(zhǔn)確性問(wèn)題［2］，即構(gòu)造目標(biāo)元組te，使得它對(duì)于每個(gè)屬性A，屬性值te［A］都最接近真實(shí)值．

一方面，數(shù)據(jù)的準(zhǔn)確性問(wèn)題在生產(chǎn)中具有迫切需求．據(jù)統(tǒng)計(jì)，不準(zhǔn)確的數(shù)據(jù)通常占企業(yè)數(shù)據(jù)的1%～5%，對(duì)于有些企業(yè)，不準(zhǔn)確率甚至高達(dá)30%［6］．據(jù)報(bào)道，在美國(guó)，不準(zhǔn)確的數(shù)據(jù)每年造成千億美元的損失［7］．為減少不準(zhǔn)確數(shù)據(jù)帶來(lái)的危害，數(shù)據(jù)倉(cāng)庫(kù)項(xiàng)目通常需要花費(fèi)30%～80%的經(jīng)費(fèi)和時(shí)間用于數(shù)據(jù)清洗［8］．

另一方面，數(shù)據(jù)的準(zhǔn)確性問(wèn)題仍然是目前數(shù)據(jù)庫(kù)中最具有挑戰(zhàn)性的問(wèn)題之一［4－5，9］．早期的工作主要集中在數(shù)據(jù)一致性等方面［5－6］．最新的方法R－topK［7］通過(guò)定義準(zhǔn)確性規(guī)則來(lái)確定最準(zhǔn)確的屬性值．但R－topK既不允許規(guī)則中存在沖突，也不允許某個(gè)實(shí)體存在超過(guò)一個(gè)的目標(biāo)元組．這導(dǎo)致它在運(yùn)行過(guò)程中需要不斷人工調(diào)整規(guī)則以及為規(guī)則不能覆蓋的屬性設(shè)計(jì)得分函數(shù)來(lái)計(jì)算top－K準(zhǔn)確的屬性值．

R－topK方法存在上述缺陷的根本原因在于：多源連接后的數(shù)據(jù)集中包含龐大的可能準(zhǔn)確的屬性值組合，而R－topK方法試圖利用規(guī)則推導(dǎo)出其中最準(zhǔn)確的屬性值．但是，當(dāng)推導(dǎo)出的準(zhǔn)確屬性值存在多個(gè)時(shí)，很難判斷這是因?yàn)榻o定實(shí)體本身存在多個(gè)準(zhǔn)確屬性值還是因?yàn)橐?guī)則間存在沖突．因此，遇到這種情況時(shí)R－topK方法會(huì)重新設(shè)計(jì)規(guī)則或top－K得分函數(shù)，其中較多的人工交互阻礙了其在大規(guī)模數(shù)據(jù)上的應(yīng)用．

在下面的例1中，R－topK方法不能處理2個(gè)可能的準(zhǔn)確值．

例1．表1以著名運(yùn)動(dòng)員Michael Jordan為實(shí)體，從包含大數(shù)據(jù)的互聯(lián)網(wǎng)上收集了他在1994—1995賽季的得分情況．表2是一些官方機(jī)構(gòu)所維護(hù)的十分準(zhǔn)確的主數(shù)據(jù)［8］．主數(shù)據(jù)表明Michael Jordan在1994—1995賽季分別在籃球聯(lián)盟NBA和棒球聯(lián)盟SL打球．

Table 1 Point Table PTfor Michael Jordan in Season 1994—1995表1 Michael Jordan在1994—1995賽季得分情況表PT

Table 2 Master Data Table MDfor Michael Jordan表2 Michael Jordan的主數(shù)據(jù)表MD

通過(guò)對(duì)這部分?jǐn)?shù)據(jù)進(jìn)行觀察，R－topK認(rèn)為存在規(guī)則“同一聯(lián)盟的記錄中，場(chǎng)次越大，得分越準(zhǔn)確”．因此，考慮得分表PT中的第1條元組t1和第3條元組t3，由于t1［場(chǎng)次］＝16＞t3［場(chǎng)次］＝1①，所以元組t1的得分屬性值424被認(rèn)為比元組t3的得分屬性值19準(zhǔn)確，即t3［得分］≤得分t1［得分］．如果只考慮PT中前3個(gè)元組，我們能得到得分屬性上3個(gè)屬性值之間的準(zhǔn)確程度（19≤得分424≤得分772）．因此，如果PT表只包含表1中的前3個(gè)元組，R－topK可以得到得分屬性上最準(zhǔn)確的值772．

①在本文中，我們使用t［場(chǎng)次］表示元組t在“場(chǎng)次”屬性上的值，用≤得分表示符號(hào)左邊的屬性值的準(zhǔn)確程度弱于符號(hào)右邊的屬性值．

但是，由于Michael Jordan在1994—1995賽季同時(shí)在2個(gè)聯(lián)盟得分，因此聯(lián)盟屬性上目標(biāo)元組te存在2個(gè)準(zhǔn)確值：te［聯(lián)盟］＝NBA和te［聯(lián)盟］＝SL．R－topK方法稱這種情況不滿足“丘奇－羅斯（Church－Rosser）”性質(zhì)［10］①，不能處理這種情況．遺憾的是，判斷數(shù)據(jù)與規(guī)則是否滿足此性質(zhì)需要在運(yùn)行時(shí)判斷［7］，這導(dǎo)致R－topK方法在實(shí)際數(shù)據(jù)中需要多次人工設(shè)計(jì)規(guī)則和運(yùn)行．此外，對(duì)于目標(biāo)元組取值不唯一的情況，R－topK只能舍棄在相關(guān)屬性上定義規(guī)則，改為人工另行設(shè)計(jì)得分函數(shù)求top－K準(zhǔn)確的屬性值，這嚴(yán)重傷害了方法的準(zhǔn)確性，并帶來(lái)了大量人工交互．

為了克服R－topK方法的這些缺陷，我們給出的權(quán)重規(guī)則WR（weighted－rule）方法為每個(gè)準(zhǔn)確性規(guī)則設(shè)計(jì)了權(quán)重屬性，用來(lái)描述規(guī)則成立的可能性．利用這些權(quán)重，WR方法可以推導(dǎo)出更準(zhǔn)確的若干目標(biāo)元組．例如，我們?cè)诒鞵T和表MD上定義表3所示的規(guī)則．其中，R1表示在表MD中出現(xiàn)過(guò)的聯(lián)盟名稱也應(yīng)該出現(xiàn)在目標(biāo)元組中，這樣，我們可以得到te［聯(lián)盟］＝NBA和te［聯(lián)盟］＝SL；而R2表示在表PT的聯(lián)盟屬性值相同時(shí)，各元組的場(chǎng)次屬性值越大，相應(yīng)元組的得分屬性值越準(zhǔn)確．這樣，我們可以得到19≤得分424和51≤得分51等．注意，由于每條規(guī)則帶有權(quán)重，它們推出的準(zhǔn)確程度上的約束條件也帶有權(quán)重．2．2節(jié)詳細(xì)介紹了約束條件上權(quán)重的設(shè)置．

Table 3 Weighted Rules表3 擴(kuò)充權(quán)重后的規(guī)則

這些規(guī)則的權(quán)重由人工指定，當(dāng)人們對(duì)規(guī)則的正確性不肯定時(shí)，權(quán)重較?。?，如果我們對(duì)另一條規(guī)則R3“目標(biāo)元組的得分屬性值為19”不太肯定時(shí)，我們可以把它的權(quán)重設(shè)置為0．5．我們可以看到，R3和我們從R2得到的19≤得分424和51≤得分51存在矛盾．這時(shí)，R－topK方法不能判定19更準(zhǔn)確還是424或772更準(zhǔn)確．而WR方法利用約束條件上的權(quán)值求解目標(biāo)元組．例如，以〈Michael Jordal，127，SL，51〉和〈Michael Jordal，27，NBA，772〉為目標(biāo)元組遵循了權(quán)重較大的規(guī)則R1和R2；而以〈Michael Jordal，1，NBA，19〉為目標(biāo)元組雖然遵循了權(quán)重較小的規(guī)則R3，卻違反了權(quán)重較大的R1和R2．直覺(jué)上，遵循權(quán)重較大的規(guī)則的〈Michael Jordal，127，SL，51〉和〈Michael Jordal，27，NBA，772〉被判定為目標(biāo)元組．

另一點(diǎn)和R－TopK方法不同的是，指定權(quán)重后，WR方法就不再需要人工干預(yù)．

本文貢獻(xiàn)如下：

1）設(shè)計(jì)了支持多真值發(fā)現(xiàn)和沖突容忍的基于規(guī)則的準(zhǔn)確性推導(dǎo)方法．特別地，我們提出的為準(zhǔn)確性規(guī)則擴(kuò)充權(quán)重的WR方法克服了現(xiàn)有方法的缺陷，允許在規(guī)則間存在沖突、準(zhǔn)確屬性值不唯一等情況下尋找目標(biāo)元組．

2）給出了目標(biāo)元組求解的高效方法．我們解決了目標(biāo)元組求解中的重要問(wèn)題，包括：①證明了以不同順序?qū)嵤?quán)重的規(guī)則都能在O（n2）時(shí)間內(nèi)停止并得到同樣的結(jié)果；②將根據(jù)存在沖突的約束條件求解目標(biāo)元組的問(wèn)題表達(dá)成馬爾可夫邏輯網(wǎng)絡(luò)（Markov logic network，MLN）的推理問(wèn)題，并利用約束條件的性質(zhì)提出了O（n）時(shí)間的高效求解方法．

3）充分的實(shí)驗(yàn)驗(yàn)證和分析．我們使用真實(shí)數(shù)據(jù)和合成數(shù)據(jù)驗(yàn)證了WR方法的效果和效率．特別地，WR方法在真實(shí)數(shù)據(jù)集上比最新方法快3～15倍，其準(zhǔn)確率和召回率比最新方法提高了7%～80%．

1 相關(guān)工作

目前數(shù)據(jù)準(zhǔn)確性方面的的大量工作可以分成基于數(shù)據(jù)一致性的方法和基于真值發(fā)現(xiàn)的方法這2類［11］．

1．1 基于數(shù)據(jù)一致性的方法

基于數(shù)據(jù)一致性的方法［12－17］假設(shè)數(shù)據(jù)應(yīng)該滿足一組約束．這些約束可以是對(duì)數(shù)據(jù)一致性的要求，比如數(shù)據(jù)應(yīng)該滿足數(shù)據(jù)的完整性約束等［13］，也可以是從收集到的數(shù)據(jù)中挖掘出的條件函數(shù)依賴［14］等．通過(guò)對(duì)收集到的數(shù)據(jù)進(jìn)行最少的操作使得這些約束被滿足后得到的數(shù)據(jù)被視為準(zhǔn)確數(shù)據(jù)．

比如，在文獻(xiàn)［15］中，條件函數(shù)依賴被視為數(shù)據(jù)應(yīng)滿足的約束，針對(duì)具體的函數(shù)依賴，元組可以修改函數(shù)依賴中被依賴部分的屬性值，也可以修改依賴部分的屬性值來(lái)滿足條件函數(shù)依賴．由于元組需要

①這里，“丘奇－羅斯”性質(zhì)指規(guī)則按任意順序施加最終得到的目標(biāo)元組唯一．進(jìn)行盡量少的修改使它滿足約束條件，但又需要避免與原來(lái)的元組過(guò)于相似，具體修改方式的選擇由對(duì)元組中屬性值正確性的估計(jì)和修改幅度共同決定．類似地，文獻(xiàn)［16］采用條件函數(shù)依賴作為數(shù)據(jù)需要滿足的約束，并將準(zhǔn)確值的尋找映射為超圖優(yōu)化問(wèn)題，其中啟發(fā)式的頂點(diǎn)覆蓋算法可以確定最少的需要修改的屬性值以滿足定義的函數(shù)覆蓋．最近，利用條件函數(shù)依賴推導(dǎo)準(zhǔn)確程度的關(guān)系也被用于尋找不準(zhǔn)確的屬性值［17］．

考慮到主數(shù)據(jù)的作用，R－topK方法［7］首次引入了屬性的準(zhǔn)確值需要滿足的規(guī)則，并將這些規(guī)則施加到數(shù)據(jù)中得到屬性值間準(zhǔn)確程度．它對(duì)不同屬性上的屬性值按照準(zhǔn)確程度進(jìn)行拓?fù)渑判?，?dāng)各個(gè)屬性上都有某個(gè)屬性值經(jīng)過(guò)拓?fù)渑判虼_認(rèn)準(zhǔn)確程度最高時(shí)，目標(biāo)元組由這些準(zhǔn)確程度最高的屬性值確定．當(dāng)存在某個(gè)屬性上有多個(gè)最準(zhǔn)確的值或規(guī)則間存在沖突時(shí)，此方法不能求出目標(biāo)元組．

與這些方法不同，我們擴(kuò)充了權(quán)重的規(guī)則不需要收集到的數(shù)據(jù)完全滿足各種依賴關(guān)系；同時(shí)，本文求解最滿足根據(jù)規(guī)則導(dǎo)出的準(zhǔn)確程度約束條件的目標(biāo)元組允許任意數(shù)量的目標(biāo)元組存在．

1．2 基于真值發(fā)現(xiàn)的方法

基于真值發(fā)現(xiàn)的方法［18－22］利用對(duì)數(shù)據(jù)源和數(shù)據(jù)進(jìn)行建模的方法判斷數(shù)據(jù)的準(zhǔn)確值．文獻(xiàn)［18］通過(guò)數(shù)據(jù)源的更新歷史和數(shù)據(jù)之間的重復(fù)程度利用隱馬爾可夫模型判斷數(shù)據(jù)之間的拷貝關(guān)系，并使用貝葉斯模型判斷準(zhǔn)確值．文獻(xiàn)［19］通過(guò)冗余記錄和時(shí)效約束在時(shí)間戳缺失的情況下輔助恢復(fù)數(shù)據(jù)的時(shí)序關(guān)系，幫助改善數(shù)據(jù)質(zhì)量．文獻(xiàn)［20］通過(guò)對(duì)數(shù)據(jù)源的可信性和數(shù)據(jù)內(nèi)容間的重復(fù)性對(duì)數(shù)據(jù)的準(zhǔn)確性建模．文獻(xiàn)［21］使用概率圖模型描述數(shù)據(jù)源間的可信程度，并為導(dǎo)致錯(cuò)誤屬性值的原因進(jìn)行建模．文獻(xiàn)［22］使用統(tǒng)計(jì)學(xué)習(xí)方法對(duì)數(shù)據(jù)分布進(jìn)行建模，并以此求出某些屬性上最可能的值．

和基于數(shù)據(jù)一致性的方法相比，本文的方法為約束或規(guī)則附加了它們成立的權(quán)重，這允許實(shí)際數(shù)據(jù)違反某些規(guī)則，提高了方法的準(zhǔn)確性．與基于真值發(fā)現(xiàn)的方法相比，我們的方法不需要指定數(shù)據(jù)源是否可靠和發(fā)現(xiàn)其中的時(shí)序關(guān)系．同時(shí)，本文直接求出目標(biāo)元組，而不是根據(jù)一些已知正確的屬性值求出另一些未知屬性的值．

2 求解目標(biāo)元組

求解目標(biāo)元組的過(guò)程分為2個(gè)部分：1）根據(jù)規(guī)則得到屬性值間準(zhǔn)確程度的約束條件及其權(quán)重；2）基于約束條件求解最有可能的屬性值組合作為目標(biāo)元組．下面，我們首先在2．1節(jié)中介紹擴(kuò)充權(quán)重后的規(guī)則，隨后的2．2節(jié)和2．3節(jié)分別介紹目標(biāo)元組求解的2個(gè)過(guò)程．

2．1 帶權(quán)重的規(guī)則

擴(kuò)充了權(quán)重的準(zhǔn)確規(guī)則和R－topK方法中的準(zhǔn)確規(guī)則類似，均通過(guò)元組間屬性的值或已判斷出準(zhǔn)確程度的屬性值判斷其他屬性上屬性值的相對(duì)準(zhǔn)確程度．

準(zhǔn)確性規(guī)則分為2種：

1）第1規(guī)則（α－規(guī)則或賦值規(guī)則），直接指定目標(biāo)元組中的屬性值，形式定義如下：

［ t（R（t）∧w→te［Ai］＝t［Ai］），p］，

其中，R（t）表示元組t應(yīng)被包含在某個(gè)關(guān)系中．w是下列3種謂詞組成的合取公式：①t1［Ai］op t2［Ai］，這里op是比較操作符≥，≤等；②ti［Aj］op c，這里c是常數(shù)；③t1≤Ait2，這里≤Ai的含義是t1在屬性Ai上的值t1［Ai］的準(zhǔn)確程度弱于t2在Ai上的值t2［Ai］．p（0＜p≤1）是人們對(duì)這條準(zhǔn)確規(guī)則成立的信心，p越大說(shuō)明目標(biāo)元組越應(yīng)該滿足該規(guī)則．

例2．以表3中的準(zhǔn)確性規(guī)則R1為例，元組t被包含在表MD中．元組需滿足的條件w為空，即直接指定目標(biāo)元組的某個(gè)屬性值．

2）第2規(guī)則（β－規(guī)則或支配規(guī)則），根據(jù)某些屬性上的值的大小或準(zhǔn)確性程度定義其他屬性上值的準(zhǔn)確性程度，形式定義如下：

［ t1，t2（R（t1）∧R（t2）∧w→t1≤Ait2，p］，

其中，R，w，p的含義和α－規(guī)則中的相同．

例3．以表3中的準(zhǔn)確性規(guī)則R2為例，w是上面提到的形如t1≤Ait2的第3種謂詞t1［場(chǎng)次］≤t2［場(chǎng)次］．

為了進(jìn)行后面的約束條件和準(zhǔn)確屬性值的推導(dǎo)，我們把上述2種規(guī)則中符號(hào)→左邊涉及到的屬性集合記為L(zhǎng)AS（R），右邊推斷出的屬性記為RA（R）．

2．2 推導(dǎo)約束條件

為規(guī)則擴(kuò)充權(quán)重屬性后，屬性值應(yīng)滿足的約束條件包括2部分，即準(zhǔn)確程度的約束和它對(duì)應(yīng)的權(quán)重．下面我們分別介紹：1）如何根據(jù)規(guī)則推斷出準(zhǔn)確程度的約束；2）如何求出這些約束條件相應(yīng)的權(quán)重．

2．2．1 推導(dǎo)準(zhǔn)確程度的約束

α－規(guī)則和β－規(guī)則分別可以推斷出2類約束條件：1）α－約束條件，形如［te［Ai］＝v，p］，以權(quán)重p確定了屬性Ai上某個(gè)值v與其他值間的準(zhǔn)確程度（v比其他值都更準(zhǔn)確）；2）β－約束條件，形如［t1≤Ait2，p］，以權(quán)重p確定了屬性Ai上2個(gè)屬性值t1［Ai］和t2［Ai］之間的準(zhǔn)確程度．我們定義每個(gè)約束條件c涉及到的屬性為CA（c）．本節(jié)求出約束條件中屬性的準(zhǔn)確程度．

準(zhǔn)確程度的獲得是一個(gè)迭代的過(guò)程，其獲得的方式分為2種：一種是通過(guò)將規(guī)則作用于數(shù)據(jù)，直接得到某個(gè)約束條件．例如，通過(guò)α－規(guī)則［ t（R（t）∧w→te［Ai］＝t［Ai］），p］，直接得出α－約束條件．另一種是通過(guò)已經(jīng)得到的約束條件推斷出新的約束條件．比如，根據(jù)β－規(guī)則［ t1，t2（R（t1）∧R（t2）∧w→t1≤Ait2，p］，如果已經(jīng)得到準(zhǔn)確程度t1≤Ait2和t2≤Ait3，那么就可以推斷出新的準(zhǔn)確程度t1≤Ait3．這樣通過(guò)對(duì)數(shù)據(jù)以及已經(jīng)得到的準(zhǔn)確程度施加規(guī)則得到新的準(zhǔn)確程度的過(guò)程稱為追蹤過(guò)程．

與以往追蹤方法面臨規(guī)則沖突就停止不同，本文的算法會(huì)繼續(xù)實(shí)施追蹤，因此追蹤過(guò)程能否結(jié)束是一個(gè)重要問(wèn)題．定理1表明無(wú)論規(guī)則的實(shí)施順序，迭代過(guò)程可以在O（｜A｜n2）時(shí)間內(nèi)終止，并得到相同的準(zhǔn)確程度．其中｜A｜是屬性的個(gè)數(shù)，n是相關(guān)實(shí)體的記錄數(shù)．

定理1．追蹤過(guò)程最多經(jīng)過(guò)O（｜A｜n2）次迭代收斂．

證明．若2次實(shí)施規(guī)則R得到的結(jié)果不同，則存在涉及LAS（R）中屬性的新增屬性值間準(zhǔn)確程度的偏序約束．因?yàn)闊o(wú)論新增的偏序?qū)εc已有的偏序?qū)κ欠駴_突，在｜A｜個(gè)屬性上最多有2｜A｜n2個(gè)偏序?qū)?，因此最多?jīng)過(guò)2｜A｜n2次迭代即可求出全部約束條件．證畢．

有了定理1的保證，我們?cè)O(shè)計(jì)了CC（construct constraints）算法構(gòu)造找出屬性值間準(zhǔn)確程度上的約束條件．

為了快速找到能施加的規(guī)則，算法CC首先為規(guī)則集合RS中的各個(gè)規(guī)則按照它們涉及到的屬性進(jìn)行劃分（行①）．我們約定2個(gè)規(guī)則R和R′之間存在依賴當(dāng)且僅當(dāng)｜LAS（R）∩RA（R′）｜或｜LAS（R′）∩RA（R）｜不為0．由于規(guī)則間有可能存在若干組無(wú)關(guān)的規(guī)則，我們每次迭代一起實(shí)施存在依賴的規(guī)則（行③～ 瑏瑤）．在對(duì)規(guī)則追蹤過(guò)程時(shí)，α－規(guī)則為目標(biāo)元組在屬性Ai上增加了一個(gè)可能取值te［Ai］（行 瑏瑣 瑏瑤）；β－規(guī)則在增加了一對(duì)屬性值上準(zhǔn)確程度的同時(shí)，還需要計(jì)算這時(shí)屬性Ai上準(zhǔn)確程度的傳遞閉包（行⑥～ 瑏瑣）．由于定理1已經(jīng)證明了追蹤過(guò)程最多經(jīng)過(guò)2｜A｜n2次迭代，上述過(guò)程直至沒(méi)有新的準(zhǔn)確程度約束出現(xiàn)時(shí)終止（行②）．注意，updateWeight使用2．2．2節(jié)中介紹的方法計(jì)算經(jīng)過(guò)傳遞閉包產(chǎn)生的約束條件的權(quán)重．

例4．以表3中的規(guī)則R2為例，假設(shè)它的某次實(shí)施增加了“424比773的準(zhǔn)確程度弱”這樣的約束條件；如果之前的迭代已經(jīng)滿足如“19比424的準(zhǔn)確程度弱”的約束條件，則根據(jù)傳遞性我們得到“19比773的準(zhǔn)確程度弱”這樣的準(zhǔn)確程度約束．

2．2．2 計(jì)算約束條件的權(quán)重

2．2．1節(jié)中，規(guī)則不同的實(shí)施順序得到相同的準(zhǔn)確程度；本節(jié)中，我們來(lái)確定這些準(zhǔn)確程度的權(quán)重．

屬性值和它們之間的準(zhǔn)確程度可以用圖表示．例1中得分屬性上的4對(duì)準(zhǔn)確程度約束19≤得分424，19≤得分772，424≤得分772和51≤得分51如圖1所示．我們把每個(gè)屬性值的所有存在的取值視為節(jié)點(diǎn)，2個(gè)節(jié)點(diǎn)中有邊當(dāng)且僅當(dāng)這2個(gè)點(diǎn)存在于某個(gè)準(zhǔn)確程度約束中，邊的權(quán)重為準(zhǔn)確程度約束的權(quán)重．可以發(fā)現(xiàn)這4個(gè)約束可以根據(jù)圖的連通性分成2組．

Fig．1 An example for constraint condition．圖1 一個(gè)約束條件的例子

由于圖中包含了得分屬性上的所有取值，我們可以如下計(jì)算每個(gè)屬性值的正確權(quán)重：

2．3 推導(dǎo)目標(biāo)元組

在本節(jié)中，我們將根據(jù)約束條件求解最可能的目標(biāo)元組．這個(gè)問(wèn)題可以形式化為MLN的推理問(wèn)題［23］．我們首先形式化目標(biāo)元組的求解問(wèn)題，然后針對(duì)應(yīng)用一般MLN求解器求解目標(biāo)元組的不足，基于約束條件的特點(diǎn)提出求解目標(biāo)元組的優(yōu)化算法．

2．3．1 基于約束條件求解目標(biāo)元組

MLN廣泛用于根據(jù)一組變量間已有的規(guī)則和權(quán)重求解這組變量最可能的取值［24］．我們發(fā)現(xiàn)可以將本文求解目標(biāo)元組的問(wèn)題表達(dá)成MLN上的推理問(wèn)題．利用MLN首先給出某個(gè)元組t成為目標(biāo)元組的可能性，并由此搜索最可能的目標(biāo)元組．

根據(jù)MLN，某個(gè)元組t成為目標(biāo)元組的可能性與該元組滿足約束條件的個(gè)數(shù)和權(quán)重有關(guān)，其概率

其中，out（node）和in（node）分別代表節(jié)點(diǎn)node的出度和入度．當(dāng)某個(gè)節(jié)點(diǎn)出度不為0時(shí)，它對(duì)應(yīng)的屬性值在已有約束中已經(jīng)比另一屬性值準(zhǔn)確程度弱，因此它們對(duì)應(yīng)的權(quán)重為0．注意，該節(jié)點(diǎn)對(duì)應(yīng)的權(quán)重為0并不意味著該節(jié)點(diǎn)對(duì)應(yīng)的屬性值不可能出現(xiàn)在目標(biāo)元組中，因?yàn)榈?種約束條件可以直接定義這些屬性值存在于目標(biāo)元組的權(quán)重．我們會(huì)直接加入這些約束條件（算法1行 瑏瑤），并在求解算法中對(duì)它們特殊考慮（算法2行④）．

那些只有入度的節(jié)點(diǎn)，在包含它的連通分量做拓?fù)渑判蛞院蟠嬖谌舾稍袋c(diǎn)到它的簡(jiǎn)單路徑．根據(jù)權(quán)重計(jì)算方法，屬性值772對(duì)應(yīng)的權(quán)重是每條路徑對(duì)應(yīng)的權(quán)重的平均值，而每條路徑的權(quán)重為該路徑上準(zhǔn)確程度約束的權(quán)重的乘積．

例5．以圖1中為約束“19≤得分772”計(jì)算權(quán)重為例，與“得分”屬性值772對(duì)應(yīng)的節(jié)點(diǎn)具有2條從源點(diǎn)（“得分”屬性值1對(duì)應(yīng)的節(jié)點(diǎn)）到它的簡(jiǎn)單路徑：19→424→772和19→772．因此，其權(quán)重是：化因子，pi是某條約束條件對(duì)應(yīng)的權(quán)重，ni（t）＝1時(shí)表示元組t滿足這個(gè)約束條件，ni（t）＝0時(shí)表示t不滿足．求解目標(biāo)元組可以看作搜索某一使得P（t＝te｜rules）最大的元組t：

這已經(jīng)被證明是一個(gè)NP－h(huán)ard問(wèn)題，但存在高效的求解器，如MaxWalkSAT［25］．這些求解器的基本方法是對(duì)某元組各個(gè)屬性的賦值檢查對(duì)約束條件的符合與違反程度，并因此修正對(duì)元組屬性的賦值．限于篇幅，我們這里僅給出應(yīng)用MLN求解目標(biāo)元組的一般方法，2．3．2節(jié)詳細(xì)介紹針對(duì)約束條件進(jìn)行優(yōu)化后的求解算法．

2．3．2 目標(biāo)元組求解優(yōu)化

求解過(guò)程中貪心和隨機(jī)策略結(jié)合使用避免了陷入局部最優(yōu)解．但是，在求解目標(biāo)元組時(shí)會(huì)導(dǎo)致可能屬性值很多、算法運(yùn)行時(shí)間長(zhǎng)的問(wèn)題．本節(jié)中我們介紹如何通過(guò)對(duì)屬性的劃分加速目標(biāo)元組的求解．

我們的方法中一共有2類約束條件，它們都針對(duì)一個(gè)屬性，因此優(yōu)化問(wèn)題可以重寫(xiě)為

其中，piAi表示CA為Ai的約束條件，niAi（t）表示元組t是否滿足這條約束條件①．

如算法TS（target solver）所示，基于重寫(xiě)的優(yōu)化問(wèn)題，我們可以得到高效的目標(biāo)元組求解算法．

①由于滿足權(quán)重較大的元組也許會(huì)違反很多權(quán)重較小的元組，因此該問(wèn)題不是通常的top－K問(wèn)題．

在CC算法中，每個(gè)約束條件c已經(jīng)根據(jù)CA（c）進(jìn)行了劃分（算法1中行⑤⑦）．在算法2中，我們?cè)趯傩訟i上只考慮圖1中沒(méi)有出度的節(jié)點(diǎn)所對(duì)應(yīng)的屬性值以及α－約束條件中明確規(guī)定的屬性值（行③④）．這是因?yàn)槿绻豢紤]β－約束，具有出度的節(jié)點(diǎn)不會(huì)比包含它的連通分量中出度為0的節(jié)點(diǎn)代表的屬性值更準(zhǔn)確．只有當(dāng)α－約束條件直接要求目標(biāo)元組取這些節(jié)點(diǎn)的屬性值時(shí)，它們才可能成為準(zhǔn)確的屬性取值．對(duì)于這些可能的取值，我們計(jì)算它們對(duì)規(guī)則的違反程度（行⑤～⑨）．最后，目標(biāo)元組由各個(gè)屬性上最可能的取值組成（行 瑏瑡）．由于出度不為0的節(jié)點(diǎn)成為候選屬性值的情況不超過(guò)α－約束的個(gè)數(shù)，算法2計(jì)算各屬性上準(zhǔn)確值的時(shí)間復(fù)雜度是O（n）．

例6．根據(jù)例5得到的場(chǎng)次屬性上的準(zhǔn)確程度約束，我們得到A場(chǎng)次．V＝｛127，27｝，類似地，有A場(chǎng)次．V＝｛772，51｝等．最終，利用各個(gè)屬性上的準(zhǔn)確屬性值的笛卡兒積和現(xiàn)有元組進(jìn)行交集，我們得到例1中的2個(gè)目標(biāo)元組：〈Michael Jordal，127，SL，51〉和〈Michael Jordal，27，NBA，772〉．

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

本節(jié)中我們同時(shí)使用真實(shí)和合成數(shù)據(jù)驗(yàn)證本文方法的性能與效果．我們使用最新方法R－topK作為基線方法．特別地，實(shí)驗(yàn)說(shuō)明了下述問(wèn)題：1）本文為規(guī)則擴(kuò)充權(quán)重后的方法比只使用規(guī)則的推理方法更高效；2）本文設(shè)計(jì)的存在沖突的規(guī)則提升了尋找準(zhǔn)確值的效果；3）本文中各規(guī)則權(quán)重的設(shè)置是健壯的．

3．1 實(shí)驗(yàn)環(huán)境與數(shù)據(jù)集描述

我們使用C＋＋實(shí)現(xiàn)本文方法WR，實(shí)驗(yàn)環(huán)境是一臺(tái)Linux服務(wù)器，英特爾至強(qiáng)E5645 2．4GHz處理器，8GB內(nèi)存，1TB SATA硬盤．除了R－topK方法用于進(jìn)行性能和效果的比較外，我們還實(shí)現(xiàn)了其他具有代表性的若干方法：DeduceOrder［18］，copyCEF［16］以及對(duì)屬性值進(jìn)行計(jì)數(shù)的voting方法．

我們使用3個(gè)被廣泛使用的公開(kāi)數(shù)據(jù)集（Med，CFP和Rest）以及合成數(shù)據(jù)集（Syn）．公開(kāi)數(shù)據(jù)集分別包含了不同公司的醫(yī)藥銷售數(shù)據(jù)、論文征稿數(shù)據(jù)和餐廳營(yíng)業(yè)數(shù)據(jù)．合成數(shù)據(jù)集由向例1中的PT和MD表添加隨機(jī)選中的數(shù)據(jù)產(chǎn)生．它們的數(shù)據(jù)大小和使用規(guī)則的情況如表4所示：

Table 4 Dataset and Rules表4 數(shù)據(jù)集及使用的規(guī)則

3．2 運(yùn)行時(shí)間

我們使用Med，CFP，Syn共3個(gè)數(shù)據(jù)集測(cè)試本文的方法和最新方法針對(duì)不同大小的元組個(gè)數(shù)和不同數(shù)量的規(guī)則情況下的運(yùn)行時(shí)間．

圖2使用Med和CFP數(shù)據(jù)集在規(guī)則數(shù)量大致相同時(shí)測(cè)試2種方法在不同元組個(gè)數(shù)情況下的運(yùn)行時(shí)間．這2種方法的運(yùn)行時(shí)間包括2部分，即尋找約束條件及目標(biāo)元組求解．

Fig．2 Performance comparison of WR and R－topKin real dataset．圖2 真實(shí)數(shù)據(jù)集上WR與R－topK方法的性能對(duì)比

從圖2（a）可以看出，2種方法計(jì)算約束條件的時(shí)間相當(dāng)，其中WR方法由于還要計(jì)算約束條件的權(quán)重，用時(shí)比R－topK方法多10%左右．但由于R－topK還需要運(yùn)行top－K算法，用時(shí)遠(yuǎn)遠(yuǎn)超過(guò)WR算法求解目標(biāo)元組的時(shí)間．這是因?yàn)镽－topK方法需要為很多屬性值求可能性，但通過(guò)對(duì)遵循和違反約束條件情況的分析，本文的目標(biāo)元組求解算法過(guò)濾掉了大部分需要在最新的方法中考慮的屬性值．

圖2（b）使用CFP數(shù)據(jù)集的結(jié)果也可以看出，在數(shù)據(jù)規(guī)模大幅增加的情況下，WR具有比R－topK用時(shí)少的趨勢(shì)．當(dāng)數(shù)據(jù)集中元組數(shù)增多從而每個(gè)屬性上可能的屬性值增多時(shí)，WR算法用了更少的時(shí)間．

圖3使用Syn數(shù)據(jù)集測(cè)試元組數(shù)量、規(guī)則數(shù)量以及主數(shù)據(jù)規(guī)模對(duì)WR性能的影響，它們的初始值分別被設(shè)為3×107，3×106，3×103．圖3（a）～（c）是依次修改這3個(gè)變量的實(shí)驗(yàn)結(jié)果．為簡(jiǎn)潔起見(jiàn)，圖3中分別用Ntuples和Nrules表示元組數(shù)和規(guī)則數(shù)．

Fig．3 Performance of WR approach in Syn dataset．圖3 Syn數(shù)據(jù)集上WR方法性能實(shí)驗(yàn)

圖3（a）中，數(shù)據(jù)規(guī)模每增加1 000萬(wàn)個(gè)元組，運(yùn)行時(shí)間增加小于2s，這部分增加的時(shí)間主要來(lái)自于約束條件的尋找；而圖3（b）顯示主數(shù)據(jù)規(guī)模對(duì)運(yùn)行時(shí)間影響不大；圖3（c）中，每增加1 000個(gè)規(guī)則，運(yùn)行時(shí)間增長(zhǎng)2s左右．圖3中的數(shù)據(jù)說(shuō)明WR方法對(duì)數(shù)據(jù)規(guī)模、規(guī)則個(gè)數(shù)是可擴(kuò)展的．

3．3 準(zhǔn)確性

我們使用3個(gè)真實(shí)數(shù)據(jù)Med，CFP，Rest比較WR方法和4種最新的已有方法（DeduceOrder，copyCEF，voting，R－topK）的準(zhǔn)確性．我們只考慮只具有一個(gè)目標(biāo)元組的實(shí)體以有利于這些方法．

并非所有方法都在3個(gè)真實(shí)數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn)：1）DeduceOrder方法需要數(shù)據(jù)集中存在CFD，但Med數(shù)據(jù)集中不存在這種函數(shù)依賴；2）copyCEF方法需要在數(shù)據(jù)集中尋找重復(fù)的數(shù)據(jù)，它所需要的數(shù)據(jù)只有Rest數(shù)據(jù)集中存在；3）剩下的voting，R－topK，WR方法在3個(gè)數(shù)據(jù)集上都進(jìn)行了實(shí)驗(yàn)．

1）Med數(shù)據(jù)集上的結(jié)果．

voting，R－topK和我們的方法找到的目標(biāo)元組中正確的分別占45%，80%，90%．其中R－topK方法也考慮過(guò)在WR方法中被判定為目標(biāo)元組的若干元組，但由于這些元組和其他目標(biāo)元組存在規(guī)則上的沖突，R－topK方法為了讓規(guī)則滿足大多數(shù)目標(biāo)元組，將它們舍棄．

2）CFP數(shù)據(jù)集上的結(jié)果．

CFP數(shù)據(jù)集的結(jié)果和Med數(shù)據(jù)集的結(jié)果類似，voting，DeduceOrder，R－topK，WR找到的目標(biāo)元組中正確的分別占37%，0%，70%，89%．由于CFP數(shù)據(jù)從多個(gè)數(shù)據(jù)源爬取得到，為它設(shè)計(jì)規(guī)則很難避免沖突，這時(shí)WR方法比R－topK方法的效果更好．

3）Rest數(shù)據(jù)集上的結(jié)果．

Rest數(shù)據(jù)集只需要判斷一個(gè)屬性值是否準(zhǔn)確，因此我們使用準(zhǔn)確率、召回率和F1－measure［26］來(lái)比較我們的方法和現(xiàn)有方法的效果．

如表5所示，DeduceOrder實(shí)現(xiàn)了100%的準(zhǔn)確率，但只有15%的召回率，因此F1－measure只有0．26．而voting方法的召回率可以達(dá)到74%，但其準(zhǔn)確率只有60%．copyCEF在具有不同時(shí)期冗余數(shù)據(jù)的Rest數(shù)據(jù)集上可以實(shí)現(xiàn)準(zhǔn)確率和召回率的平衡（分別是76%和85%），因此收獲了較高的F1－measure值0．83．但基于規(guī)則的R－top K方法和WR方法更好．由于WR允許對(duì)若干規(guī)則的違反，其準(zhǔn)確率92%和召回率95%都高于目前最新方法R－topK的81%和90%．

Table 5 Accuracy Comparison on Rest Dataset表5 Rest數(shù)據(jù)集上的準(zhǔn)確性比較

3．4 沖突與權(quán)重敏感程度

我們?cè)?個(gè)真實(shí)數(shù)據(jù)集上測(cè)試了規(guī)則的沖突情況和我們的方法對(duì)規(guī)則權(quán)重的敏感程度．圖4顯示了我們的方法在3個(gè)數(shù)據(jù)集上分別有10%，13%，17%的規(guī)則是存在沖突的．這些沖突的規(guī)則在R－topK算法中只能被去掉，當(dāng)我們把這些規(guī)則去掉后，WR的準(zhǔn)確率和召回率有了5%～10%的下降．

Fig．4 Ratio of rule confliction．圖4 沖突規(guī)則比率

為了檢查WR方法是否對(duì)規(guī)則的權(quán)重敏感．我們對(duì)各個(gè)規(guī)則的權(quán)重進(jìn)行小范圍的隨機(jī)調(diào)整，然后檢測(cè)WR方法的準(zhǔn)確性．3個(gè)數(shù)據(jù)集的準(zhǔn)確性隨權(quán)重變化的情況類似，限于篇幅，我們只在圖5中展示Rest數(shù)據(jù)集上的情況．可以看出，當(dāng)規(guī)則的權(quán)重在10%的范圍內(nèi)改變時(shí)，Rest數(shù)據(jù)集上準(zhǔn)確率和召回率的影響不超過(guò)5%．其中，準(zhǔn)確率隨著離最優(yōu)的權(quán)重幅度越遠(yuǎn)，準(zhǔn)確率均勻下降．但召回率在權(quán)重小幅度上升時(shí)下降較慢，而在權(quán)重小幅度下降時(shí)下降較快，這是因?yàn)榇蟛糠忠?guī)則不存在沖突，但小部分存在沖突的規(guī)則會(huì)產(chǎn)生以下正確的目標(biāo)元組．當(dāng)全部規(guī)則的權(quán)重都小幅度下降時(shí)，這部分元組會(huì)被其他元組取代，導(dǎo)致召回率快速下降．

Fig．5 Sensitivity of weight in rules in Rest dataset．圖5 Rest數(shù)據(jù)集對(duì)權(quán)重敏感程度

4 結(jié)束語(yǔ)

為尋找實(shí)體相對(duì)準(zhǔn)確的屬性值這一大數(shù)據(jù)集成中的關(guān)鍵步驟，本文提出了為規(guī)則擴(kuò)充權(quán)重的WR方法，它克服了現(xiàn)有方法在多準(zhǔn)確值發(fā)現(xiàn)和不支持沖突規(guī)則的缺陷．特別地，為實(shí)施帶權(quán)重規(guī)則推導(dǎo)約束條件的追蹤過(guò)程，我們提出了在O（n2）時(shí)間停止的算法，為基于約束條件搜索準(zhǔn)確屬性值的問(wèn)題，提出基于馬爾可夫邏輯網(wǎng)絡(luò)（MLN）的線性高效求解算法．真實(shí)數(shù)據(jù)集與合成數(shù)據(jù)集上的充分實(shí)驗(yàn)證明WR方法在性能上有3～15倍的提升，在目標(biāo)元組的準(zhǔn)確率和召回率上提高了7%～80%．

［1］Dong Xin Luna，Srivastava D．Big data integration［C］??Proc of ICDE 13．Piscataway，NJ：IEEE，2013：1245 1248

［2］Dong Xin Luna，Srivastava D．Big data integration［J］．Proceedings of the VLDB Endowment，2013，6（11）：1188 1189

［3］Bellahsene Z，Bonifati A，Rahm E．Schema Matching and Mapping［M］．Berlin：Springer，2011

［4］Gelman I．Setting priorities for data accuracy improvements in satisficing decision－making scenarios：A guiding theory［J］．Decision Support System，2010，48（1）：507 520

［5］Getoor L，Machanavajjhala A．Entity resolution：Theory，practice ＆open challenges［J］．Proceedings of the VLDB Endowment，2012，5（12）：2018 2019

［6］Fan Wenfei．Querying Big Social Data［M］．Berlin：Springer，2013：14 28

［7］Cao Yang，F(xiàn)an Wenfei，Yu Wenyuan．Determining the relative accuracy of attributes［C］??Proc of SIGMOD 13．New York：ACM，2013：565 576

［8］Radcliffe J，White A．Key issues for master data management，G00210255［R］．Stanford，CT：Gartner，2008

［9］Fan Wenfei，Geerts F，Nan Tang，et al．Inferring data currency and consistency for conflict resolution［C］??Proc of ICDE 13．Piscataway，NJ：IEEE，2013：470 481

［10］Abiteboul S，Hull R，Vianu V．Foundations of Databases［M］．Reading，MA：Addison－Wesley，1995

［11］Yakout M，Elmagarmid A，Berti－Equille L．Don t be SCAREd：Use scalable automatic repairing with maximal likelihood and bounded changes［C］??Proc of ACM SIGMOD 13．New York：ACM，2013：553 564

［12］Firestone J．Enterprise information portals and knowledge management［M］．New York：Routledge，2003

［13］Bertossi L，Arenas M，Chomicki J．Consistent query answers in inconsistent databases［C］??Proc of PODS 99．New York：ACM，1999：68 79

［14］Fan Wenfei，Geerts F，Kementsietsidis A．Conditional functional dependencies for capturing data inconsistencies［J］．IEEE Trans on Database System，2008，33（1）：1 48

［15］Kolahi S，Lakshmanan L．On approximating optimum repairs for functional dependency violation［C］??Proc of ICDT 09．New York：ACM，2009：53 62

［16］Ma Shuai，F(xiàn)an Wenfei，Cong Gao．Improving data quality：Consistency and accuracy［C］??Proc of PVLDB 07．Berlin：Springer，2007：315 326

［17］Blanco L，Crescenzi V，Merialdo P，et al．Probabilistic models to reconcile complex data from inaccurate data sources［C］??Proc of AISE 10．Berlin：Springer，2010：83 97

［18］Dong Xin Luna，Berti－Equille L，Srivastava D．Truth discovery and copying detection in a dynamic world［C］?? Proc of VLDB 09，Berlin：Springer，2009：562 573

［19］Li Mohan，Li Jianzhong，Gao Hong．Evaluation of data currency［J］．Chinese Journal of Computers，2012，35（11）：2348 2360（in Chinese）（李默涵，李建中，高宏．?dāng)?shù)據(jù)時(shí)效性判定問(wèn)題的求解算法［J］．計(jì)算機(jī)學(xué)報(bào)，2012，35（11）：2348 2360）

［20］Galland A，Abiteboul S，Marian A，et al．Corroborating information from disagreeing views［C］??Proc of WSDM．New York：ACM，2010：131 140

［21］Koudas N，Sarawagi S，Srivastava D．Record linkage：Similarity measures and algorithms［C］??Proc of ACM SIGMOD 06．New York：ACM，2006：802 803

［22］Fan Wenfei，Geerts F．Foundations of Data Quality Management［M］．San Rafael，CA：Morgan Claypool Publishers，2012：1 20

［23］Richardson M，Domingos P．Markov logic networks［J］．Machine Learning，2006，62（1）：107 136

［24］Domingos P，Lowd D．Markov Logic：An Interface Layer for Artificial Intelligence［M］．San Rafael，CA：Morgan Claypool Publishers，2009

［25］Manya F，Argelich J．Exact Max－SAT solvers for overconstrained problems［J］．Journal of Heuristics，2006，12（4）：375 392

［26］Baeza－Yates R，Ribeiro－Neto B．Modern Information Retrieval［M］．New York：ACM，1999

Zhou Ningnan，born in 1990．Currently PhD candidate at Renmin University of China．His research interest includes high performance database． Sheng Wanxing，born in 1965．Received his BSc，MSc and PhD degrees from Xi＇an Jiaotong University．Full professor in China Electric Power Research Institute（CEPRI），Beijing，China，since 1997．His research interests include renewable energy generation and grid－connected technologies． Liu Ke－yan，born in 1979．Received his PhD degree in electrical engineering from Beihang University in 2007．Currently，senior researcher in China Electric Power Research Institute．His current research interests include distributed generation（DG），planning and operation analysis of distribution systems，power system computation method and simulation．

Zhang Xiao，born in 1972．PhD．Associated professor at Renmin University of China．His research interests include database architecture and big data management．

Wang Shan，born in 1944．Master．Professor and PhD supervisor at Renmin University of China．Her research interests include high performance database，main memory database and data warehouse．

WR Approach：Determining Accurate Attribute Values in Big Data Integration

Zhou Ningnan1，3，Sheng Wanxing1，Liu Ke－yan1，Zhang Xiao2，3，and Wang Shan2，31（China Electric Power Research Institute，Beijing100192）2（Key Laboratory of Data Engineering and Knowledge Engineering（Renmin University of China），Ministry of Education，Beijing100872）3（School of Information，Renmin University of China，Beijing100872）

Big data integration lays the foundation for high quality data－driven decision．One critical section thereof is to determine the accurate attribute values from records in data pertaining to a given entity．The state－of－the－art approach R－topKargues to design rules to decide relative accuracy among the attribute values and thus obtain accurate values．Unfortunately，in cases where multiple true values or conflicted rules exist，it requires rounds of human intervention．In this paper，we propose a weighted rule（WR）approach for determining accurate attribute values in big data integration．Each rule is augmented with weight and thus avoid human intervention when conflicts occur．This paper designs a chase procedure－based inference algorithm，and proves that it can figure out weighted constraints over relative accuracy among attribute values in O（n2），which introduces constraints for finding accurate data values．Taking conflicts among constraints into consideration，this paper proposes an O（n）algorithm to discover accurate attribute values among the combination of data values．We conduct extensive experiments under real world and synthetic datasets，and the results demonstrate the effectiveness and efficiency of WR approach．WR approach boosts performance by

TP311

2014－11－24；

2015－03－24

國(guó)家“九七三”重點(diǎn)基礎(chǔ)研究發(fā)展計(jì)劃基金項(xiàng)目（2014CB340403）；國(guó)家電網(wǎng)公司研究項(xiàng)目（EPRIPDKJ［2014］3763號(hào)）

This work was supported by the National Basic Research Program of China（973Program）（2014CB340403）and the Project of State Grid Corporation of China Research Program（EPRIPDKJ［2014］No．3763）．

張孝（zhangxiao＠ruc．edu．cn）

factor of 3 15xand improves effectiveness by 7%80%．Key words big data integration；data quality；data accuracy；data cleaning；weighted rules