Top-k近似否定約束的發(fā)現(xiàn)

冉 艾 談子敬

(復(fù)旦大學(xué)計算機科學(xué)與技術(shù)學(xué)院 上海 200433)

0 引 言

互聯(lián)網(wǎng)的廣泛使用使得數(shù)據(jù)集的來源變得多樣化。很多用戶參與內(nèi)容生成或提供的數(shù)據(jù)集允許在互聯(lián)網(wǎng)上傳播和同步修改。比如維基百科、百度百科中詞條的解釋是面向全網(wǎng)開放編輯的，即允許所有網(wǎng)民進行自定義的修改。在上述操作過程中，數(shù)據(jù)的真實性或者準確性無法得到有效的保證。學(xué)術(shù)數(shù)據(jù)庫或者知識圖譜之中也經(jīng)常出現(xiàn)錯誤論文信息，比如信息缺失或論文重復(fù)記錄。數(shù)據(jù)一致性成了數(shù)據(jù)質(zhì)量的一個重要指標之一。發(fā)現(xiàn)數(shù)據(jù)里的約束，再使用數(shù)據(jù)約束去修復(fù)數(shù)據(jù)集已經(jīng)成了數(shù)據(jù)處理的基本流程。

數(shù)據(jù)約束對后續(xù)的數(shù)據(jù)處理非常重要，目前已有大量數(shù)據(jù)約束方面的研究。常見的數(shù)據(jù)約束包含字段級約束和表級約束。其中，字段級約束指只對單個元組或者單個字段有約束，比如域約束、檢查約束等；表級約束指定義在兩個元組間的多個字段的約束，常見有函數(shù)依賴、條件函數(shù)依賴、次序依賴和差分依賴等。在現(xiàn)實中，字段級約束與表級約束可以同時存在于同一個數(shù)據(jù)中，且數(shù)據(jù)間的關(guān)系不僅僅有等于或者不等，還有著大于、小于的次序關(guān)系。否定約束[1]是一個表達能力極強的數(shù)據(jù)依賴的形式，它滿足了以上的需求。常見的域約束、主鍵約束、函數(shù)依賴、條件函數(shù)依賴和次序依賴等都可以轉(zhuǎn)為相應(yīng)的否定約束形式。

在數(shù)據(jù)約束的相關(guān)工作中，數(shù)據(jù)約束的發(fā)現(xiàn)是一個基礎(chǔ)的問題。因為原始數(shù)據(jù)上會有數(shù)據(jù)與現(xiàn)實不一致，近似約束的發(fā)現(xiàn)也變得尤為重要。文獻[2-3]的實驗結(jié)果表示，一個數(shù)據(jù)集上面發(fā)現(xiàn)的否定約束往往數(shù)目是數(shù)以千計的，近似否定約束的結(jié)果往往更多[4,9]。為了得到具有更高語義的Top-k的近似否定約束，選擇評價否定約束剪枝指標變得非常必要。文獻[3]提出了兩個評價指標，但其得到的否定約束沒有考慮到數(shù)據(jù)相關(guān)性，得到的結(jié)果有可能會將毫無關(guān)系的變量放進同一個否定約束中。本文引入了信息論中的互信息評估指標，并且借鑒了文獻[5]中的無偏估計來評價兩個變量間的相關(guān)性。將這樣的相關(guān)性加入到近似否定約束發(fā)現(xiàn)的流程中，作為否定約束的一個評價指標之一，保證了得出的結(jié)果包含的變量具有較強的相關(guān)性。

本文的研究目標是在數(shù)據(jù)集上面發(fā)現(xiàn)Top-k的近似否定約束。在發(fā)現(xiàn)過程中加入信息論的指標來保證得到的否定約束中包含的屬性具有較好的相關(guān)性。提出可以實現(xiàn)Top-k近似否定約束的算法，在數(shù)據(jù)集上比較算法的時間和否定約束結(jié)果集性質(zhì)。

1 背景知識

1.1 否定約束

在給出否定約束的具體定義前，需要說明一些必要的記號。給定關(guān)系R及R上的實例I，記屬性集合為attr(R)={A1,A2,…,Am}。其中Ai表示一個屬性，其值域記為dom(Ai)，i∈{1,2,…,m}。一個元組t代表關(guān)系數(shù)據(jù)實例I中的一行，記t.A表示該元組在屬性A上的取值。

定義1否定約束是形式為否定多個謂詞同時存在的實體約束語言。其表達式如下：

φ:?tα,tβ∈R(p1∧p2∧…∧pk)

式中：p為一個謂詞表達式，表示為v1θv2;tα和tβ為數(shù)據(jù)表中的元組;θ為符號運算符，θ∈{=,≠,≤,≥,<,>}。謂詞表達式中的v1和v2指元組的值，即v1,v2∈T.A,T為tα或者tβ，A為任意屬性。否定約束表示約束中的謂詞不能同時為真，即不存在數(shù)據(jù)集中的元組或者元組對滿足否定約束中的所有謂詞。φ.pres表示φ中包含的謂詞構(gòu)成的集合。

例如，在表1中的稅收繳費記錄中，每一個記錄為一個稅收繳費，包含了元組編號(TID)及5個描述個人信息的屬性，分別為姓名(Name)、所在州(ST)、郵編(ZIP)、工資(SAL)、稅率(Rate)。

表1 稅收繳費記錄

可以驗證以下的否定約束成立：

φ1:(tα.ZIP=tβ.ZIP∧tα.ST≠tβ.ST)

φ2:(tα.Name=tβ.Name)

φ3:(tα.ST=tβ.ST∧tα.SAL>tβ.SAL∧tα.Rate

其中的否定約束φ1為函數(shù)依賴ZIP→ST表明兩個元組在郵政編碼上相等時，元組所在的州名需要相等。φ2為主鍵約束，即兩個元組的姓名不能相等。φ3表示在同一個州中，收入越高則稅收率越高。

定義2給定一個實例I0和否定約束φ，如果約束φ成立，稱φ為有效的否定約束。如果在任意的實例I中，均有φ成立，那么稱φ為平凡的否定約束。在實例I0中，如果不存在有效否定約束φ1滿足φ1.pres?φ.pres，則稱φ為最小的否定約束。

一個m維的數(shù)據(jù)集，可以得到不同的元組和屬性組合會有2m×(2m-1)種。因為謂詞可以有6個不同的符號，所以謂詞空間大小為P=6×2m×(2m-1)，所以否定約束的整體搜索空間為2P。

1.2 變量間相關(guān)性

衡量兩個變量間的相關(guān)性有很多種方法，比如數(shù)據(jù)的相關(guān)性系數(shù)、協(xié)方差矩陣。在信息論中，使用兩個變量間的互信息來評估兩個變量間包含的信息多少。如果變量間的互信息量高，說明變量間的相關(guān)性是非常強的。

定義3將互信息量歸一化為互信息分數(shù)：

1.3 相關(guān)工作

目前已有的相關(guān)研究主要如下。(1) 文獻[1]提出了否定約束的概念，文獻[2]描述了否定約束的發(fā)現(xiàn)算法，文獻[3,9]分別提出了否定約束的發(fā)現(xiàn)算法改進以及近似否定約束的發(fā)現(xiàn)。(2) 近似數(shù)據(jù)約束發(fā)現(xiàn)：文獻[4-5,8-9]分別提供了函數(shù)依賴、差分依賴及否定約束的近似發(fā)現(xiàn)算法。(3) 屬性間相關(guān)性計算：文獻[5-7]給出了不同情境下使用互信息計算方式。(4) 約束的修復(fù)使用：文獻[10]利用已有的約束進行修復(fù)數(shù)據(jù)。

2 算 法

在以往發(fā)現(xiàn)否定約束的文獻中，在數(shù)據(jù)集上面發(fā)現(xiàn)的非平凡的最小否定約束結(jié)果一般都是非常大的，一般都是成千上萬個。即使限定了不能進行跨列的屬性比較，得到的否定約束結(jié)果也會是數(shù)以千計。這么大的約束結(jié)果對后續(xù)數(shù)據(jù)約束的修復(fù)或者數(shù)據(jù)處理是非常不便的。所以在數(shù)據(jù)集上面查找Top-k的否定約束對后續(xù)的數(shù)據(jù)處理是有必要的。本文在文獻[2,5]的基礎(chǔ)上提出了在數(shù)據(jù)集上查找Top-k的近似否定約束的算法。因為數(shù)據(jù)集上兩個不同屬性進行比較是沒有太大實際意義的，所以本文主要考慮不跨列的謂詞組成的否定約束。包含跨列謂詞組成的Top-k否定約束發(fā)現(xiàn)只需要在數(shù)據(jù)集轉(zhuǎn)換流程做相應(yīng)的修改即可。

2.1 算法流程

首先利用數(shù)據(jù)轉(zhuǎn)換方法得到數(shù)據(jù)集I0，然后在數(shù)據(jù)集I0上計算相應(yīng)的否定約束。因為互信息量計算需要給定變量Y，所以算法假設(shè)選定了興趣屬性Y。如果沒有指定屬性，則簡單地將所有屬性輪流做興趣屬性即可得到全局上的Top-k結(jié)果。算法流程如算法1所示。

算法1否定約束發(fā)現(xiàn)算法Find_Bst

輸入：轉(zhuǎn)換后的數(shù)據(jù)表I0，興趣屬性Y，閾值α。

輸出：包含特定屬性Y的Top-k否定約束。

1. 初始化屬性集Q,DSCk。

3. 擴展分數(shù)最高的屬性集top(Q)：

Rs=extend(top(Q)),Q=Q op(Q)

4. 更新當前的Top-k集合：

DCSk=Top-k(DCSk∪Rs)

5. 更新目前的屬性集：

6. 重復(fù)步驟2-步驟5

7. 根據(jù)轉(zhuǎn)換后的數(shù)據(jù)表I0返回DSCk中屬性集生成的否定約束。

2.2 數(shù)據(jù)轉(zhuǎn)換

否定約束是在數(shù)據(jù)元組對的約束，函數(shù)依賴也是元組對上的數(shù)據(jù)約束。所以希望建立函數(shù)依賴和否定約束間的聯(lián)系使得將函數(shù)依賴上的算法能夠轉(zhuǎn)換到否定約束算法中。通過數(shù)據(jù)轉(zhuǎn)換可以將原始數(shù)據(jù)集上的否定約束轉(zhuǎn)換為新數(shù)據(jù)集上的依賴關(guān)系。

對于表1中的數(shù)據(jù)，由于姓名(Name)、所在州(ST)為字符串形式，即互相比較大小是沒有意義的。包含這些屬性的謂詞符號為相等或者不相等。郵編(ZIP)、工資(SAL)及稅率(Rate)是可以進行大小比較的，所以在這些屬性上面需要考慮6個不同符號。但在一個特定的元組對中，屬性的值只包含大于、等于、小于三種不同的情況。這樣就可以通過將元組對改為只含-1、0、1三個數(shù)字的元組，-1表示小于或者字符型屬性上的不等，0表示相等，1表示大于。

考慮元組對，因為在姓名、所在州上均不相等，t0的郵編大于t1的郵編，t0的工資大于t1的工資，t0的稅率大于t1的稅率，所以元組對轉(zhuǎn)換為新數(shù)據(jù)〈-1，-1，1，-1，1〉。同理元組對〈t1,t0〉轉(zhuǎn)換為新數(shù)據(jù)〈-1，-1，-1，1，-1〉。因為原始數(shù)據(jù)上會出現(xiàn)多個元組對轉(zhuǎn)為相同的新數(shù)據(jù)，所以使用出現(xiàn)次數(shù)(Count)來記錄原始數(shù)據(jù)元組轉(zhuǎn)換相同的次數(shù)。表1的12個元組對可以轉(zhuǎn)換為新數(shù)據(jù)，如表2所示。

表2 轉(zhuǎn)換后新數(shù)據(jù)

由表2可以看出，在屬性Name上面，所有的元組屬性均為-1，這表明在原始數(shù)據(jù)集表1中，所有的元組對的Name屬性不相等，即否定約束φ2成立。

2.3 相關(guān)性計算

現(xiàn)實數(shù)據(jù)集往往包含百萬以上的元組，直接在所有數(shù)據(jù)上計算變量間的相關(guān)性或者信息量會非常繁瑣，所以常常使用隨機抽樣的方法來評估互信息分數(shù)。目前有非常多的方法在抽樣數(shù)據(jù)上估計信息量。但是這些方法并不是無偏的估計，且誤差與變量值域大小密切相關(guān)。例如以表2中的數(shù)據(jù)進行估計，會產(chǎn)生非常大的誤差。本文采用文獻[5,7]提出的無偏估計。這樣的無偏估計誤差與抽取的變量包含的不同可能取值無關(guān)。這個性質(zhì)在本文算法中是非常必要的，因為本文轉(zhuǎn)換后的數(shù)據(jù)每一個屬性至多只有3個不同的取值。

對于變量X、Y，假設(shè)在數(shù)據(jù)中抽取出n個元組。在這n個元組上，X的不同取值有D種，Y的不同取值有C種。記X的值域為dom(X)={x1,x2,…，xD}，Y的值域為dom(Y)={y1,y2,…，yC}，使用ai表示在抽樣數(shù)據(jù)n個元組中X的值為xi的元組數(shù)目，對應(yīng)的bj表示在抽樣數(shù)據(jù)中Y的值為yj的元組數(shù)目。

定義3中的互信息分數(shù)估計計算公式為：

(1)

(2)

p(k)為一個超幾何分布的概率，計算公式為：

(3)

為了簡化計算過程，可使用遞推公式計算：

(4)

2.4 評價函數(shù)

錯誤率ER用來評判近似約束的好壞，即在數(shù)據(jù)集中有多少比例的元組對不滿足約束，計算式如下：

(5)

錯誤率越低說明近似約束越能描述出數(shù)據(jù)集的性質(zhì)，約束的適用性也越高。

對于否定約束，文獻[1,3]還提出了兩個評價指標，分別為覆蓋率與簡潔性。因為簡潔性可以直接用于屬性集合中，本文打分函數(shù)中只采用了簡潔性。后續(xù)的實驗表明，即使算法中沒有考慮覆蓋率，得到的結(jié)果覆蓋率并不會比對比算法低太多。如果一個否定約束的包含的謂詞數(shù)目越多，則表明簡潔性越低。其計算公式為：

(6)

式中：L為一個給定常數(shù)；φ.pres為否定約束中包含的謂詞集合;|φ.pres|為否定約束中謂詞個數(shù)。

為了使得否定約束具有更好的簡潔性，本文在定義3基礎(chǔ)上使用如下的打分函數(shù)：

(7)

式中：F(X;Y)為定義3中的評價分數(shù)；X為否定約束φ中除了Y以外的屬性組成的集合；φ.pres為否定約束包含的謂詞集合；λ為參數(shù)。一個否定約束集合打分定義為集合中包含的否定約束的最小打分，即f(DSCk)=min(f(dc)),dc∈DSCk。

(8)

2.5 屬性集合與約束轉(zhuǎn)換

前文的打分函數(shù)都是基于謂詞個數(shù)和包含的屬性，并沒有確定否定約束中各謂詞的符號。本文依據(jù)在轉(zhuǎn)換數(shù)據(jù)集中出現(xiàn)次數(shù)(如表2中的count屬性)的元組作符號選擇。這樣的選擇可以使得在抽樣數(shù)據(jù)中的錯誤率最小，保證約束的性質(zhì)。

對屬性集合X及Y，首先按照X和Y出現(xiàn)在數(shù)據(jù)集I0的所有取值在count屬性上的值進行由小到大進行排序。以count屬性上最小的取值作為基準符號，再逐個屬性考慮能否將符號進行擴展。比如屬性Y在最小的取值為-1或1時，考慮X上取值相同的時候，Y為0的count是否滿足可以進行符號擴展的條件。

以表2數(shù)據(jù)為例，考慮X={SAL},Y={Rate}。因為SAL和Rate均為數(shù)值型變量，那么在I0中的出現(xiàn)次數(shù)由小到大分別為：1次<1,-1>、<-1,1>、<-1,0>、<0,1>及4次<-1,-1>、<1,1>。選取<1,-1>為基準。假設(shè)選擇擴展的標準為滿足的count之和小于總元組對數(shù)的10%。此時的count為1是小于12×10%的。保持其他屬性取值不變，考慮能否將SAL的符號擴展為≥，即<0,-1>是否可以包含。因為I0中不包含<0,-1>，因此可以將SAL的符號擴展為≥。再考慮將Rate的符號擴展為≤是否可行。同樣因為<0,0>以及<1,0>不在I0中，所以可以擴展。最后得到的近似否定約束為：

(tα.SAL≥tβ.SAL∧tα.Rate≤tβ.Rate)

在這一過程中，count之和即為2.4節(jié)中定義的ER。文獻[7]提出的ER近似評估方法指出抽樣數(shù)據(jù)中可以有效估計原始數(shù)據(jù)集的錯誤率，且這個抽樣數(shù)據(jù)集是與原始數(shù)據(jù)集大小無關(guān)的。所以使用這樣的符號選擇方式也可以減少產(chǎn)生的近似否定約束在原始數(shù)據(jù)集上的錯誤率。

3 實 驗

實驗使用的環(huán)境為Intel(R) Core(TM) i7-7700-3.60 GHz的CPU,8 GB內(nèi)存，64位操作系統(tǒng)的計算機。使用的實驗數(shù)據(jù)是人工的稅務(wù)數(shù)據(jù)集Tax，以及描述字母的特征真實數(shù)據(jù)集LETTER，其中：Tax擁有7個字符型屬性，8個數(shù)字型屬性；LETTER包含1個字符型，11個數(shù)字型屬性。本文使用的默認數(shù)據(jù)集大小為50 KB，閾值α為0.4，K為10。

3.1 時間分析

文獻[3]提出利用覆蓋率及簡潔性打分函數(shù)進行剪枝，可以很好地得到分數(shù)高的Top-k否定約束。本文在其基礎(chǔ)上做些許改動后，使得其可以發(fā)現(xiàn)近似否定約束，作為對比算法Fast_Rank。因為覆蓋率的計算是一個復(fù)雜度為O(n2)的計算，導(dǎo)致計算時間非常長。在兩個數(shù)據(jù)集上,在不同的K取值時均可以觀察到對比時間明顯慢于本文算法Fast_Bst。下面給出了具體算法運行時間，圖1(a)為Tax數(shù)據(jù)結(jié)果，圖1(b)為LETTER數(shù)據(jù)結(jié)果。

圖1 Fast_Rank和Find_Bst的時間結(jié)果

本文的算法是基于抽樣數(shù)據(jù)的結(jié)果，即算法的運行時間取決于抽樣元組對數(shù)目r。故相較于Fast_Rank需要在全部數(shù)據(jù)上進行運算，本文算法Fast_Bst大幅度減少了運行時間。

圖2展示了算法時間與抽樣元組對數(shù)目r(K)及剪枝分數(shù)的閾值α的關(guān)系。

圖2 不同r和α取值的Find_Bst時間結(jié)果

可以看出運行時間與抽樣的元組對數(shù)目r成正比。當剪枝分數(shù)的閾值α越高時，滿足步驟2的剪枝越多,運行時間越短。

3.2 性能分析

使用的評測指標有錯誤率(ER)、簡潔性(Succ)和覆蓋率(coverage)。為了將錯誤率及簡潔性結(jié)果歸一化，圖3展示的結(jié)果是錯誤率(簡潔性)與結(jié)果中最高錯誤率(簡潔性)的比值ER′(Succ′)。比值越低說明錯誤率越低，簡潔性越差。

圖3 不同α取值和K的性能分析

圖3(a)為在數(shù)據(jù)集LETTER上面改變閾值α的三個評分指標的變化?？梢杂^察到當閾值變大時，覆蓋率沒有發(fā)生大的變化，但是錯誤率明顯提升，包含的謂詞數(shù)目因為擴展的概率變小，所以簡潔性變好。圖3(b)為Find_Bst算法和Fast_Rank算法在不同K上的運行結(jié)果的評價分數(shù)的比值?？梢杂^察到在K比較小的時候(K=5)，本文算法與Find_Bst算法結(jié)果有些許差距，當K變大時，差距趨向于減少?？傮w上本文的結(jié)果與對比算法的結(jié)果在評價指標上面非常接近。

4 結(jié) 語

否定約束用于描述屬性間的關(guān)系，相比其他的約束而言，具有更好的表達能力和更多能夠包含的符號。但是表達能力強導(dǎo)致了在數(shù)據(jù)集上會成立非常多的否

定約束。因為數(shù)據(jù)集有時候會出現(xiàn)誤讀誤寫以及用戶希望找尋與興趣屬性相關(guān)的否定約束時，只需要發(fā)現(xiàn)評分較高的Top-k近似否定約束即可。本文針對這個問題提出了利用屬性間的相關(guān)性以及否定約束的簡潔性分數(shù)做分支定界的剪枝函數(shù)。通過實驗，算法的時間優(yōu)勢非常明顯，得到的K個近似否定約束在評價指標上與對比算法基本一致。

未來工作還需要考慮跨列的否定約束的Top-k發(fā)現(xiàn)算法。針對包含跨列的否定約束，可以在數(shù)據(jù)轉(zhuǎn)換中進行相應(yīng)的修改，也可以在屬性集合與約束轉(zhuǎn)換中進行擴展。