冉 艾 談子敬

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

0 引 言

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

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

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

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

1 背景知識

1.1 否定約束

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

定義1否定約束是形式為否定多個(gè)謂詞同時(shí)存在的實(shí)體約束語言。其表達(dá)式如下：

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

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

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

表1 稅收繳費(fèi)記錄

可以驗(yàn)證以下的否定約束成立：

φ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表明兩個(gè)元組在郵政編碼上相等時(shí)，元組所在的州名需要相等。φ2為主鍵約束，即兩個(gè)元組的姓名不能相等。φ3表示在同一個(gè)州中，收入越高則稅收率越高。

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

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

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

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

定義3將互信息量歸一化為互信息分?jǐn)?shù)：

1.3 相關(guān)工作

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

2 算 法

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

2.1 算法流程

首先利用數(shù)據(jù)轉(zhuǎn)換方法得到數(shù)據(jù)集I0，然后在數(shù)據(jù)集I0上計(jì)算相應(yīng)的否定約束。因?yàn)榛バ畔⒘坑?jì)算需要給定變量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. 擴(kuò)展分?jǐn)?shù)最高的屬性集top(Q)：

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

4. 更新當(dāng)前的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)是可以進(jìn)行大小比較的，所以在這些屬性上面需要考慮6個(gè)不同符號。但在一個(gè)特定的元組對中，屬性的值只包含大于、等于、小于三種不同的情況。這樣就可以通過將元組對改為只含-1、0、1三個(gè)數(shù)字的元組，-1表示小于或者字符型屬性上的不等，0表示相等，1表示大于。

考慮元組對，因?yàn)樵谛彰?、所在州上均不相等，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〉。因?yàn)樵紨?shù)據(jù)上會出現(xiàn)多個(gè)元組對轉(zhuǎn)為相同的新數(shù)據(jù)，所以使用出現(xiàn)次數(shù)(Count)來記錄原始數(shù)據(jù)元組轉(zhuǎn)換相同的次數(shù)。表1的12個(gè)元組對可以轉(zhuǎn)換為新數(shù)據(jù)，如表2所示。

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

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

2.3 相關(guān)性計(jì)算

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

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

定義3中的互信息分?jǐn)?shù)估計(jì)計(jì)算公式為：

(1)

(2)

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

(3)

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

(4)

2.4 評價(jià)函數(shù)

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

(5)

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

對于否定約束，文獻(xiàn)[1,3]還提出了兩個(gè)評價(jià)指標(biāo)，分別為覆蓋率與簡潔性。因?yàn)楹啙嵭钥梢灾苯佑糜趯傩约现?，本文打分函?shù)中只采用了簡潔性。后續(xù)的實(shí)驗(yàn)表明，即使算法中沒有考慮覆蓋率，得到的結(jié)果覆蓋率并不會比對比算法低太多。如果一個(gè)否定約束的包含的謂詞數(shù)目越多，則表明簡潔性越低。其計(jì)算公式為：

(6)

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

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

(7)

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

(8)

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

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

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

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

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

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

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

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

3.1 時(shí)間分析

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

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

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

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

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

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

3.2 性能分析

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

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

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

4 結(jié) 語

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

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

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