祁丹蕊,宋韶旭,2,3,王建民,2,3

1(清華大學(xué) 軟件學(xué)院,北京 100084)

2(大數(shù)據(jù)系統(tǒng)軟件國(guó)家工程實(shí)驗(yàn)室,北京 100084)

3(北京信息科學(xué)與技術(shù)國(guó)家研究中心,北京 100084)

1 引 言

1.1 問(wèn)題背景

為什么科爾伯特不是總統(tǒng)?為什么Travelocity并沒(méi)有告訴我Drake Hotel也是芝加哥可以作為備選的落腳點(diǎn)?為什么 Frank Sinatra沒(méi)有棕色的眼睛?現(xiàn)實(shí)世界中,很多沒(méi)有發(fā)生的事情都有非常明確的原因.了解為什么該發(fā)生的事情沒(méi)有發(fā)生,是我們理解世界的正常方式.在數(shù)據(jù)庫(kù)領(lǐng)域和軟件系統(tǒng)領(lǐng)域,這種問(wèn)題經(jīng)常是這種形式:為什么這個(gè)程序是不完整的?為什么這個(gè)元組沒(méi)有出現(xiàn)在查詢的結(jié)果集?由于在用戶得到結(jié)果之前需要對(duì)數(shù)據(jù)進(jìn)行較多步驟的計(jì)算,所以這種問(wèn)題的答案較難尋找.

數(shù)據(jù)起源,或者可以叫做一段數(shù)據(jù)的歷史信息,曾經(jīng)被用于研究解釋數(shù)據(jù)從哪里來(lái)[1-3]和在原始數(shù)據(jù)變成結(jié)果集的過(guò)程中都發(fā)生了什么[4-7].對(duì)于這些信息的整合,可以幫助我們理解為什么某些元組并沒(méi)有出現(xiàn)在結(jié)果集中[4,7,8].數(shù)據(jù)起源在這些工作中可以幫助人們解釋一些結(jié)果集中非正常的結(jié)果.

對(duì)于數(shù)據(jù)庫(kù)用戶,一個(gè)常見(jiàn)的場(chǎng)景是這些編程人員被問(wèn)為什么一條或者多條用戶認(rèn)為會(huì)有的數(shù)據(jù)并未出現(xiàn)在查詢結(jié)果里.用戶會(huì)猜想為什么.比如,一個(gè)查詢的結(jié)果集是空的或者為什么同樣的查詢沒(méi)有返回相同的結(jié)果值.當(dāng)查詢用來(lái)定義多視圖的時(shí)候,用戶可能會(huì)問(wèn)為什么.例如,一個(gè)雇員的信息在雇員注冊(cè)的視圖和工資名單的視圖中都沒(méi)有.經(jīng)常地,編程人員的第一反應(yīng)是查看是否是查詢本身的錯(cuò)誤,比如條件太嚴(yán)格篩掉了部分可能結(jié)果,或者采用的 outer-join本來(lái)應(yīng)該是 inner-join.然而,如果查詢的表示方式是正確的,下一步編程人員要考慮的事情就是研究數(shù)據(jù)源,確定是否用戶期望的結(jié)果數(shù)據(jù)真的在數(shù)據(jù)源中有出現(xiàn).我們將這種形式的解釋,即這種用數(shù)據(jù)來(lái)解釋不在結(jié)果集中的元組的方式,叫做依賴數(shù)據(jù)的解釋.在本文中,主要研究依賴數(shù)據(jù)的解釋.

例1:考慮表1中的關(guān)系和查詢Q1:

查詢后的結(jié)果見(jiàn)表2.用戶知道在查詢結(jié)果中,應(yīng)該有一個(gè)發(fā)射溫度為78華氏度的飛機(jī),時(shí)間順序應(yīng)是第12位,但是這個(gè)元組并沒(méi)有出現(xiàn)在查詢的結(jié)果集中.用戶可能會(huì)問(wèn),為什么元組(6,78,12)沒(méi)有出現(xiàn)?如果向原來(lái)的數(shù)據(jù)表插入元組(6,_,78,_,12),元組(6,78,12)就可以出現(xiàn)在查詢結(jié)果集中,其中,“_”代表此屬性可以取數(shù)據(jù)域中的任意值.我們根據(jù)觀察表格發(fā)現(xiàn),屬性No.ETD和 Pressure都屬于整數(shù)域,而如果用戶也需要這兩個(gè)屬性值的一個(gè)合理推斷,那么向原來(lái)的數(shù)據(jù)表插入元組(6,0,78,200,12)就可以看做是一個(gè)解釋.若無(wú)法推斷出精確屬性值,否定某些可能的屬性值,如向原來(lái)數(shù)據(jù)表中加入(6,?2,78,200,12)也可以看做是一個(gè)合理的解釋.

為了令沒(méi)有出現(xiàn)在結(jié)果中的期望元組成為Q1的查詢結(jié)果,枚舉可能的缺失元組是一種可行的方案.但是在這些被枚舉的可能中,存在著大量不合理的解釋,通常違反唯一性約束或者源數(shù)據(jù)庫(kù)內(nèi)部的約束,如函數(shù)依賴和條件函數(shù)依賴.

利用數(shù)據(jù)庫(kù)內(nèi)部的約束可以初步約減一些不合理的解釋,如文獻(xiàn)[9-11]利用唯一性約束對(duì)得到的解釋進(jìn)行了約減,但在較大數(shù)據(jù)集上,利用數(shù)據(jù)庫(kù)內(nèi)部規(guī)則進(jìn)行約減雖然有一定效果,但仍然會(huì)返回大量的解釋(如文獻(xiàn)[9]在本文中所使用的Airfoil Self-Noise上,在只有兩個(gè)待修復(fù)屬性的條件下,仍然返回37 856條解釋),使得用戶無(wú)法確認(rèn)解釋是否合理.

另外,在返回的解釋中存在非常多利用變量表示的屬性,即取屬性域中的任意值均可.對(duì)于用戶來(lái)說(shuō),此種解釋的參考價(jià)值不大,所以生成用戶可以理解的排序后的實(shí)例解釋非常重要.

Table 1 Challenger USA space shuttle O-ring dataset表1 挑戰(zhàn)者號(hào)美國(guó)航天飛機(jī)O型圈數(shù)據(jù)集

Table 2 Query results表2 查詢結(jié)果

1.2 主要貢獻(xiàn)

本文在以前工作的基礎(chǔ)上,做出了如下主要貢獻(xiàn).

· 重新定義了Why-not問(wèn)題解釋的格式,使得呈獻(xiàn)給用戶的解釋不含變量,使得解釋更容易被理解;

· 在多屬性的情況下,可能的值域會(huì)很大,為了避免數(shù)據(jù)稀疏性問(wèn)題,提出將數(shù)據(jù)表示為兩兩比較關(guān)系,以{0,1}表示兩個(gè)元組在某個(gè)屬性上是否相等,從而支持更有效的概率模型學(xué)習(xí);

· 利用統(tǒng)計(jì)方法計(jì)算兩兩關(guān)系概率分布,定義基于兩兩關(guān)系概率的支持度(support)與置信度(confidence),并根據(jù)這些度量對(duì)候選解釋進(jìn)行相應(yīng)的篩選和排序;

· 利用分類和回歸方法計(jì)算兩兩關(guān)系概率分布.統(tǒng)計(jì)方法在計(jì)算概率分布時(shí)未能充分考慮不同程度的屬性關(guān)系.在分類和回歸方法后,不同程度的屬性間關(guān)系被考慮,使得最后返回的解釋排序結(jié)果更加合理.結(jié)合回歸方法并考慮不同程度的屬性間關(guān)系后,我們提出了3種算法;

· 在不同數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果證明:利用統(tǒng)計(jì)、分類和回歸方法計(jì)算兩兩關(guān)系概率分布的方法,可以為用戶尋找Why-not問(wèn)題的解釋并返回較為高質(zhì)量的解釋.

1.3 論文結(jié)構(gòu)

本文第 2節(jié)對(duì)相關(guān)工作進(jìn)行具體介紹.第 3節(jié)給出本文的一些通用基礎(chǔ)定義和問(wèn)題的形式化定義.解釋的統(tǒng)計(jì)學(xué)特征定義將與利用統(tǒng)計(jì)學(xué)方法尋找候選解釋和它們的概率分布的算法一起在第4節(jié)中說(shuō)明.第5節(jié)呈現(xiàn)結(jié)合機(jī)器學(xué)習(xí)分類方法的尋找候選解釋及其概率分布的算法和3種結(jié)合回歸方法尋找候選解釋及其概率分布的算法.在第6節(jié)中將給出不同算法在真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果的比較.最后,在第7節(jié)中對(duì)本文的工作進(jìn)行總結(jié),并對(duì)未來(lái)的工作進(jìn)行展望.

2 相關(guān)工作

2.1 Why-not問(wèn)題

現(xiàn)今,數(shù)據(jù)量正在快速地增長(zhǎng).數(shù)據(jù)庫(kù)管理系統(tǒng)從不同的數(shù)據(jù)源中抽取數(shù)據(jù),聚合數(shù)據(jù)并將它們添加到數(shù)據(jù)庫(kù)中.但是數(shù)據(jù)源常常不具有很好的質(zhì)量.由于數(shù)據(jù)源的低質(zhì)量和低一致性,用戶或者數(shù)據(jù)科學(xué)家們經(jīng)常會(huì)面臨一種問(wèn)題:當(dāng)他們?cè)谝粋€(gè)數(shù)據(jù)庫(kù)上執(zhí)行查詢的時(shí)候,一些他們期望的答案并沒(méi)有出現(xiàn)在返回的查詢結(jié)果中.繼而用戶可能會(huì)詢問(wèn)為什么一個(gè)或者多個(gè)元組沒(méi)有在查詢結(jié)果集中出現(xiàn),也就是 Why-not問(wèn)題.顯然,為數(shù)據(jù)科學(xué)家或者用戶提供針對(duì)于缺失元組的解釋,可以幫助他們更好地理解或修復(fù)數(shù)據(jù)庫(kù).這種問(wèn)題其實(shí)是數(shù)據(jù)起源問(wèn)題的一個(gè)擴(kuò)展,最早在文獻(xiàn)[12]中被提出.

2.2 缺失答案解釋

現(xiàn)今,已經(jīng)有很多方法來(lái)解決簡(jiǎn)化數(shù)據(jù)轉(zhuǎn)換分析問(wèn)題,并使用戶更容易理解和驗(yàn)證其行為和語(yǔ)義,包括數(shù)據(jù)沿襲[13]和更一般的數(shù)據(jù)來(lái)源[14]、子查詢結(jié)果檢查[15]、可視化[16]或轉(zhuǎn)換規(guī)范簡(jiǎn)化[17].本文中提到的工作屬于數(shù)據(jù)來(lái)源研究的范疇,重點(diǎn)是一個(gè)特定的子解決方案,旨在解釋查詢結(jié)果中的缺失答案,也就是解釋為什么某些數(shù)據(jù)不存在.

缺失答案(MA)[10]在給出單個(gè)缺少的元組和單個(gè)選擇項(xiàng)目連接(SPJ)查詢后,計(jì)算基于實(shí)例的解釋.事實(shí)上,它重寫查詢,使得重寫查詢的結(jié)果對(duì)應(yīng)于指定的缺失答案的所有可能的基于實(shí)例的解釋.基于實(shí)例的說(shuō)明插入或更新源數(shù)據(jù),并且可以通過(guò)信任表(屬性)來(lái)減少需要被進(jìn)行插入(更新)的數(shù)據(jù).

Artemis[9]擴(kuò)展了MA算法,使得它適用于一組涉及選擇、投影、連接、聯(lián)合和聚合(SPJUA查詢)的非嵌套SQL查詢.此外,可以指定多個(gè)缺失答案.計(jì)算的基于實(shí)例的解釋描述了插入源數(shù)據(jù)的所有可能的方案,以便可以同時(shí)解釋所有缺失答案.Artemis也考慮了修建解釋的副作用.副作用在根據(jù)基于實(shí)例的解釋更改源數(shù)據(jù)后,新增的結(jié)果除了指定的缺失答案之外,還會(huì)有其他的結(jié)果顯示在查詢的結(jié)果中.

Meliou等人統(tǒng)一了查詢結(jié)果和缺失答案中存在數(shù)據(jù)的基于實(shí)例的解釋[18].不使用數(shù)據(jù)來(lái)源[14],解決方案利用了因果關(guān)系和責(zé)任關(guān)系.此文詳細(xì)研究了基于因果關(guān)系和責(zé)任的聯(lián)合查詢解釋的復(fù)雜性,Meliou等人在文獻(xiàn)[18]中還將現(xiàn)有數(shù)據(jù)的一種具體類型的解釋統(tǒng)一為缺少數(shù)據(jù)的一種特定類型的解釋.

Why-not[12]計(jì)算基于查詢的解釋.首先,給出一個(gè)缺失答案,它識(shí)別源數(shù)據(jù)庫(kù)中包含常量值的元組,或者滿足缺失答案的條件,而不是查詢結(jié)果中的任何元組譜系的一部分[3].這些元組中的值稱為兼容元組,通過(guò)查詢運(yùn)算符被跟蹤,以識(shí)別哪些運(yùn)算符將它們作為輸入,而不是輸出.在文獻(xiàn)[12]中,該算法被證明適用于涉及選擇,投影、連接和聯(lián)合(SPJU查詢)中的某一個(gè)查詢.

NedExplain[19]類似于 Why-not,跟蹤源數(shù)據(jù)庫(kù)的元組,然而它不限制將兼容的元組限制到不是任何結(jié)果元組譜系的源元組.基于這種修改的基本假設(shè)和基于查詢解釋的新穎形式定義,NedExplain計(jì)算一個(gè)比Why- not更全面、正確和詳細(xì)的解釋集合,并支持涉及選擇、投影、加入和聚合(SPJA查詢)以及SPJA查詢的聯(lián)合.

ConQueR[20]輸出基于修改的解釋.給定一組缺失答案,SPJUA查詢和源數(shù)據(jù)庫(kù),它首先確定產(chǎn)生缺失答案的必要源數(shù)據(jù)是否可用,這與Why-not類似.然后更改SQL查詢,使得所有缺失答案成為輸出的一部分,而副作用最小化.即在進(jìn)行查詢修改時(shí),原始查詢結(jié)果中存在的元組必須保留,只有最少數(shù)量的不是缺失答案的附加元組可以被允許出現(xiàn)在結(jié)果中.

最近已經(jīng)提出了計(jì)算針對(duì)關(guān)系和SQL查詢之外的查詢基于修改的解釋算法.在考慮副作用的同時(shí),計(jì)算基于修改的解釋的一種算法專門解答Why-not的Top-k查詢問(wèn)題[21].這個(gè)算法重點(diǎn)在于改變k或偏好權(quán)重,使缺失答案出現(xiàn)在查詢結(jié)果中.Islam等人在文獻(xiàn)[22]中提出了解決方案,回答了Why-not的反向Skyline查詢問(wèn)題.

2.3 條件函數(shù)依賴

此節(jié)將介紹條件函數(shù)依賴的基礎(chǔ)定義[23]和它的一些有趣的統(tǒng)計(jì)學(xué)特征[24],即支持度和置信度.后文將基于條件函數(shù)依賴的統(tǒng)計(jì)學(xué)特征重新定義解釋的統(tǒng)計(jì)學(xué)特征.

2.3.1 基礎(chǔ)定義

一個(gè)在關(guān)系R上的條件函數(shù)依賴φ是一個(gè)元組R(X→Y,Tp),其中,

·X,Y是attr(R)中的一系列屬性;

·R(X→Y)是一個(gè)標(biāo)準(zhǔn)函數(shù)依賴,又可以被叫做嵌在φ中的函數(shù)依賴;

·Tp是一個(gè)具有X和Y中所有屬性的表,又可以被叫做φ的模式表,其中,對(duì)于每個(gè)元組t的任意的在X或Y中的屬性A,t[A]為一個(gè)在dom(A)中的常數(shù)‘a(chǎn)’或者是一個(gè)未命名的變量‘_’.如果屬性A在X和Y中都出現(xiàn)了,則我們用t[AL]和t[AR]來(lái)表示左邊和和右邊的A.當(dāng)已知關(guān)系R時(shí),我們將φ寫為(X→Y,Tp).

關(guān)系R的一個(gè)實(shí)例I滿足條件函數(shù)依賴φ,定義為,當(dāng)且僅當(dāng)對(duì)于實(shí)例I中的每對(duì)元組ti,tj,和條件函數(shù)依賴φ的模式表Tp中的每個(gè)元組,如果成立,那么成立.即:如果t1[X]和t2[Y]相等并且他們都與模式tc[Y]相配,那么t1[Y]和t2[Y]一定相等并且他們都與模式tc[Y]相配.此外,如果Σ是條件函數(shù)依賴的一個(gè)集合,我們說(shuō)當(dāng)且僅當(dāng)對(duì)Σ中的每一個(gè)條件函數(shù)依賴φ,都有.

2.3.2 統(tǒng)計(jì)學(xué)特征

(1) 支持度

顯然,經(jīng)常一起出現(xiàn)的值有更多可能性是相關(guān)的,支持度就是基于這種思想的一種頻率度量.關(guān)系R中的條件函數(shù)依賴φ=(X→A,tP)的支持度是R與φ相配的部分元組的數(shù)量占全部元組數(shù)量的比例,表示為support(φ,R),可定義為

其中,s是R中與φ相配的部分元組的數(shù)量,N是關(guān)系R中的元組數(shù).

(2) 置信度

在很多情況下,有一些在支持度集中的元組在導(dǎo)因X處相同,但是在結(jié)果A處不相同.可以考慮每種不同的導(dǎo)因值單獨(dú)地屬于支持度集.可以將一個(gè)(完全實(shí)例化的)先行x作為一個(gè)組相關(guān)聯(lián)的行集合,或者可以叫做“x組”.為了滿足CFD,每個(gè)組中的所有行必須具有相同的結(jié)果值.

下面我們定義關(guān)系R的一個(gè)條件函數(shù)依賴的置信度:Cφ(R),它是可以保留的支持度集的最大分?jǐn)?shù),因此在刪除所有其他行之后,支持度集的其余部分滿足嵌入的函數(shù)依賴.

不失一般性,我們可以將關(guān)系R看做一個(gè)或多個(gè)行的集合ri=(xi,yi),其中,xi∈X是導(dǎo)因值,yi∈Y是結(jié)果值,并且其他的屬性都不需要予以考慮.定義關(guān)系R中的總元組數(shù)為N.定義Nx為||ri:xi=x||,即具有相同導(dǎo)因值x的元組的個(gè)數(shù)(x組的大小),Nx,y為,并且定義R中φ的支持度集為sφ(R),即:

那么support(φ,R)也可以被同時(shí)定義為||sφ(R)||,那么:

2.4 利用兩兩比較方法尋找函數(shù)依賴

受利用兩兩比較方法尋找函數(shù)依賴的算法啟發(fā),我們簡(jiǎn)化了解決問(wèn)題的統(tǒng)計(jì)學(xué)方法,并為與機(jī)器學(xué)習(xí)算法結(jié)合提供了可能.本節(jié)簡(jiǎn)略概述利用兩兩比較方法尋找函數(shù)依賴的3種算法.

傳統(tǒng)尋找函數(shù)依賴的算法都是基于lattice的算法.Lopes等人提出的DEP-MINER[25]從有相同值的屬性集中推斷出所有最小的函數(shù)依賴.這些屬性集被稱為 agree集,它們的補(bǔ)集叫做 disagree集.Wyss等人提出的FASTFD算法[20]是DEP-MINER算法的一個(gè)改進(jìn).但是相似的是,FASTFD算法也是基于agree集來(lái)得到最小的函數(shù)依賴.在計(jì)算agree集之后,FASTFD采用了一種不同的策略,即計(jì)算disagree集來(lái)代替DEP-MINER中最慢的步驟.而在求agree集時(shí),兩種算法都需要將數(shù)據(jù)庫(kù)中的元組進(jìn)行一一對(duì)比來(lái)找具有相同值的屬性集.

Flach和Savnik提出的FDEP算法[26]不同于前面提到的兩種算法.FDEP算法成功地將數(shù)據(jù)庫(kù)中的元組一一進(jìn)行比較從而找到最小的函數(shù)依賴.

3 基礎(chǔ)定義

為了方便對(duì)下文的理解,我們將闡述在整個(gè)論文中通用的一些基礎(chǔ)定義,并給出相應(yīng)的示例作為解釋.

3.1 用戶的問(wèn)題

若給定數(shù)據(jù)庫(kù)D,一個(gè)用戶在數(shù)據(jù)庫(kù)D上執(zhí)行了查詢query并且得到了一系列元組query[D]作為執(zhí)行查詢的答案.假設(shè)有一種情況,用戶發(fā)現(xiàn)一些他期待會(huì)出現(xiàn)在答案里的元組并沒(méi)有出現(xiàn)在答案中,用戶可能就會(huì)問(wèn)一個(gè)問(wèn)題:為什么我期望的元組沒(méi)有出現(xiàn)在答案中.例如,例 1中提到的問(wèn)題“為什么元組(6,78,12)沒(méi)有出現(xiàn)”,即可以稱為一個(gè)用戶問(wèn)題.

3.2 基礎(chǔ)定義

若給定一個(gè)數(shù)據(jù)庫(kù)D,假設(shè)在數(shù)據(jù)庫(kù)D中有x個(gè)關(guān)系,則將這x個(gè)關(guān)系記為T1,T2,…,Tx.對(duì)于每個(gè)在數(shù)據(jù)庫(kù)D中的關(guān)系Tk,有mk個(gè)屬性,可定義為A1,A2,...,Amk,則關(guān)系Tk可以記為Tk(A1,A2,...,Amk).若考慮將關(guān)系的下標(biāo)和屬性的下標(biāo)綜合起來(lái),可以定義是第j個(gè)關(guān)系的第i個(gè)屬性.對(duì)于每個(gè)Tk,假設(shè)有nk個(gè)元組在關(guān)系中,則這n個(gè)元組可被記為t1,t2, ...,tnk,若如前文所述與關(guān)系的下標(biāo)結(jié)合,可以定義tij是第j個(gè)關(guān)系的第i個(gè)元組.

定義1(待調(diào)試場(chǎng)景).一個(gè)待調(diào)試場(chǎng)景S可以被定義成為具有3個(gè)元素的元組〈query,D,E〉.D的具體含義是上文中提到的原始數(shù)據(jù)庫(kù).query的具體含義是用戶在原始數(shù)據(jù)庫(kù)上執(zhí)行的查詢.E的具體含義代表了一個(gè)沒(méi)有出現(xiàn)在query[D]但是出現(xiàn)在用戶的問(wèn)題中的元組.

例2:如例1中所示,此處待調(diào)試場(chǎng)景S就可以被表示成〈Q1,挑戰(zhàn)者號(hào)美國(guó)航天飛機(jī)O型圈數(shù)據(jù)集,(6,78,12)〉.

定義2(缺失元組).一個(gè)消失元組可以被定義為元組d-tuple=〈d1,d2,…,db〉.值得注意的是,在d-tuple中的每一個(gè)屬性值都應(yīng)該為一個(gè)常量或者變量,其中,〈d1,d2,…,db〉代表用戶在數(shù)據(jù)庫(kù)D上進(jìn)行查詢后得到的結(jié)果的屬性.

例3:如例1中例子提到,此處消失元組d-tuple=(6,78,12).

定義3(解釋).若給定一個(gè)待調(diào)試場(chǎng)景S,一個(gè)解釋可被定義為一個(gè)帶符號(hào)的元組的集合,記為

例4:對(duì)于例1中的例子,元組(6,0,78,200,12)可以作為Why-not問(wèn)題的一個(gè)合法解釋,并且此解釋未知屬性全部為積極值.同時(shí),元組(6,0,78,?50,12)也可以作為另一種合法解釋,其中有一個(gè)未知屬性為消極值.更進(jìn)一步,元組(6,?0,78,?50,12)仍然為一個(gè)合法解釋,此處所有的未知屬性都為消極值.

定義4(解釋模板).若給定在數(shù)據(jù)庫(kù)D上執(zhí)行的查詢Q,一個(gè)解釋的解釋式樣可以被定義為從查詢和消失元組中提取的需要被新加入原始數(shù)據(jù)庫(kù)的元組有限集.

在Pattern(Rk)中,應(yīng)是常量或者變量.對(duì)于一組確定的原始數(shù)據(jù)庫(kù)D,查詢query和消失元組d-tuple,有且只有一種解釋式樣.

從解釋式樣中可知,在Tk中的屬性可以被分為兩類:一類是已知屬性,另一類是未知屬性.假設(shè)Tk中的未知屬性共有l(wèi)個(gè),則對(duì)于關(guān)系Tk,它可以被表示成.其中,代表未知屬性,代表已知屬性.

例5:對(duì)于例1,由于d-tuple=(6,78,12),分別對(duì)應(yīng)例1數(shù)據(jù)集中的No.O-rings,Temp和Order屬性,則此數(shù)據(jù)集的解釋式樣可以表示成為(6,N2,78,N3,12)

定義5(解釋概率).一個(gè)解釋的概率,或者說(shuō)一個(gè)解釋會(huì)被添加進(jìn)原始數(shù)據(jù)庫(kù)的概率,記為P(e),可以被定義為一種聯(lián)合概率:

特別地,如果假設(shè)原始數(shù)據(jù)庫(kù)中所有的關(guān)系都是獨(dú)立的,即關(guān)系之間沒(méi)有外鍵等關(guān)系,那么可以得到如下的解釋概率表達(dá)式:

進(jìn)一步地,如果假設(shè)原始數(shù)據(jù)庫(kù)中所有關(guān)系的所有屬性之間都是獨(dú)立的,即屬性之間沒(méi)有類 FD或者 CFD的函數(shù)依賴限制,那么可以得到如下的解釋概率表達(dá)式:

定義6(整體列表).解釋的整體列表是一個(gè)由有順序的元組組成的列表,記為,(e3,P(e3)),...}.其中,P(e1)>P(e2)>P(e3)>….

在整體列表Lall中,有一類比較特殊的解釋,它們的特點(diǎn)是沒(méi)有任何消極值.在整體列表中找到所有這樣的解釋并對(duì)他們進(jìn)行排序,就可以得到解釋的正列表.同理,也可以得到解釋的負(fù)列表.

定義7(正列表).解釋的正列表是一個(gè)由有順序的元組組成的列表,記為,.其中,中無(wú)消極值

定義8(負(fù)列表).解釋的正列表是一個(gè)由有順序的元組組成的列表,記為,.其中,中無(wú)消極值

4 基于概率模型的解釋排序

本節(jié)重點(diǎn)討論利用基礎(chǔ)的統(tǒng)計(jì)學(xué)方法尋找解釋的兩種算法:第 1種是未經(jīng)任何變化從原始數(shù)據(jù)進(jìn)行概率推理,第2種是在兩兩比較方法的基礎(chǔ)上對(duì)數(shù)據(jù)進(jìn)行概率推理.對(duì)于這兩種算法,首先都會(huì)對(duì)算法整體進(jìn)行概述,再詳細(xì)解釋算法并給出偽代碼.為了便于理解,還會(huì)給出相應(yīng)運(yùn)算實(shí)例.

4.1 從原始數(shù)據(jù)進(jìn)行概率推理

4.1.1 算法概述

給定原始數(shù)據(jù),原始查詢和用戶在A?+1,...,Am的Why-not問(wèn)題,可以通過(guò)將未知屬性的可能值進(jìn)行分組,并通過(guò)古典概型和條件概率計(jì)算方式得到未知屬性的不同可能值在已知屬性的值已經(jīng)得到的條件下出現(xiàn)的概率.對(duì)上述算法下的概率進(jìn)行排序,即可以得到對(duì)未知屬性的可能值(即解釋的可能值)進(jìn)行排序的結(jié)果,排序的結(jié)果從上到下可解釋為解釋的合理程度.

4.1.2 從原始數(shù)據(jù)進(jìn)行概率推理算法

算法的輸入值為原始數(shù)據(jù)庫(kù),用戶在原始數(shù)據(jù)庫(kù)上執(zhí)行的查詢和缺失答案,在接受輸入后,算法主要執(zhí)行以下步驟.

· 步驟1:統(tǒng)計(jì)所有屬性值的聯(lián)合概率.

首先,根據(jù)原始數(shù)據(jù)庫(kù)中的數(shù)據(jù)進(jìn)行分組統(tǒng)計(jì).若對(duì)關(guān)系T(A1,…,Am)中的數(shù)據(jù)進(jìn)行分組統(tǒng)計(jì),那么對(duì)于關(guān)系T中的任意兩個(gè)元組ti和tj,如果對(duì)于任意的屬性Ak,都有ti[Ak]=tj[Ak],那么ti和tj即可以被分為一組.對(duì)于關(guān)系T分成的多個(gè)組,假設(shè)某個(gè)組中包含的元組數(shù)為num,相應(yīng)的屬性值分別為a1,…,am,關(guān)系T中的元組數(shù)為N,則:

· 步驟2:統(tǒng)計(jì)己知屬性值的聯(lián)合概率.

對(duì)于所有已知屬性值,按照步驟1中描述的方法統(tǒng)計(jì)聯(lián)合概率.首先,設(shè)所有已知屬性的值為,即:對(duì)于關(guān)系T中的任意元組ti,如果對(duì)于任意的已知屬性Ak,都有ti[Ak]=p[Ak],若以numknown代表已知屬性的值等于p中已知屬性值的元組個(gè)數(shù),則其數(shù)量可以加1.則聯(lián)合概率為:

· 步驟3:尋找候選解釋.

由步驟2,我們得到了一組已知屬性值全部相等的元組.但是它們的未知屬性值可能不相等,這些不相等的未知屬性值與已知屬性值進(jìn)行結(jié)合,就構(gòu)成了候選的解釋.

· 步驟4:計(jì)算不同候選解釋在已知屬性值條件下的概率.

從步驟2中得到的已知屬性值全部相等的元組集合中,可以獲得候選解釋.這些候選解釋也將這個(gè)集合分成了很多獨(dú)立的組.在這些組里,任意兩個(gè)元組的所有屬性值全部相等.假設(shè)某一組中,所有未知屬性的值為a1,...,a?,因此,

· 步驟5:排序概率,得到合理解釋順序.

對(duì)于所有不同的候選解釋,經(jīng)過(guò)上述的步驟,都可以得到在已知屬性值條件下的條件概率.對(duì)得到的這些條件概率進(jìn)行排序并返回這些解釋,即為最后的結(jié)果.

在介紹了以上步驟后,給出算法的偽代碼如下.

算法1.從原始數(shù)據(jù)進(jìn)行概率推理.

輸入:原始數(shù)據(jù)庫(kù)中的關(guān)系T,查詢Q,缺失答案q;

輸出:整體列表Lall.

4.1.3 算法實(shí)例描述

例1中的Why-not問(wèn)題中,未知屬性為No.ETD和Pressure,若要從源數(shù)據(jù)進(jìn)行概率推理,首先得到已知屬性的值分別為

首先在表1中尋找是否有與 3個(gè)屬性值完全相等的元組.尋找后發(fā)現(xiàn)沒(méi)有找到,則從源數(shù)據(jù)進(jìn)行概率推理的方法并不能給出一個(gè)合理的解釋.即,尋找到的解釋的準(zhǔn)確率為0.

若此處找到了3個(gè)屬性值完全相等的元組,則繼續(xù)在這些元組中對(duì)于不同的No.ETD和Pressure的組合值進(jìn)行分組,計(jì)算條件概率并排序,即可以得到最終的排好序的解釋.

4.1.4 算法問(wèn)題分析

上述算法最大的問(wèn)題在于分組的步驟中,當(dāng)數(shù)據(jù)集的數(shù)據(jù)量很大或者所有屬性中有至少一個(gè)屬性為鍵值時(shí),分組的數(shù)量可能會(huì)非常多.由此帶來(lái)的稀疏性問(wèn)題會(huì)使得候選的解釋非常少,或者候選解釋的概率都非常小且差別不大,無(wú)法進(jìn)行有效的排序以返回有意義的列表.

4.2 依據(jù)兩兩比較結(jié)果進(jìn)行概率推理

4.2.1 算法概述

在此算法中,將利用兩兩比較的比較結(jié)果進(jìn)行概率推理.對(duì)于源數(shù)據(jù)庫(kù)中任意兩個(gè)的元組,將他們的屬性一一進(jìn)行對(duì)比:若屬性值相等,則記為1;否則記為0.將得到的結(jié)果組成一張新的兩兩比較結(jié)果表,利用此表和第4.1節(jié)中的方法,可以算出在兩兩比較結(jié)果表中解釋的基本分布.參照CFD的支持度和置信度的定義,定義解釋的支持度和置信度,并且通過(guò)對(duì)支持度的篩選,首先排除一些可能性非常小的解釋,繼而在支持度達(dá)到標(biāo)準(zhǔn)的解釋中間尋找置信度符合標(biāo)準(zhǔn)的解釋并排序,得到最終結(jié)果.

4.2.2 依據(jù)兩兩比較結(jié)果進(jìn)行概率推理算法

算法的輸入值為原始數(shù)據(jù)庫(kù),用戶在原始數(shù)據(jù)庫(kù)上執(zhí)行的查詢和缺失答案,在接受輸入后,算法主要執(zhí)行以下步驟.

· 步驟1:計(jì)算兩兩比較結(jié)果表.

首先根據(jù)原始數(shù)據(jù)庫(kù)中的關(guān)系T(A1,…,Am)計(jì)算基于其的pari-wise比較表,記為S(B1,…,Bm).對(duì)于T中的任意兩個(gè)元組ti和tj,若對(duì)于其中的某個(gè)屬性Ak有ti[Ak]=tj[Ak],那么S中的元組tij[Bk]=1(表示T中ti和tj比較);否則,tij[Bk]=0.在將T中全部元組進(jìn)行比后得到個(gè)元組,即S.

· 步驟2:根據(jù)兩兩比較結(jié)果表統(tǒng)計(jì)聯(lián)合概率.

在得到兩兩比較結(jié)果表S后,按照第4.1節(jié)中統(tǒng)計(jì)所有屬性聯(lián)合概率的方法,可以初步統(tǒng)計(jì)所有屬性的聯(lián)合概率.假設(shè)兩兩比較結(jié)果表被分成了多個(gè)組,其中一個(gè)組對(duì)應(yīng)的所有屬性值為b1,b2,…,bm,包含的元組數(shù)為numb,則:

由于兩兩比較結(jié)果表S中全部為0/1值,所以將Why-not問(wèn)題p中已知屬性的值與原數(shù)據(jù)表進(jìn)行對(duì)比,得到一張新的0/1表,其中的元組q1,…,qn是將Why-not問(wèn)題p中己知屬性的值與t1,…,tn中的已知屬性值進(jìn)行比較后得到的結(jié)果.

接著,計(jì)算兩兩比較結(jié)果表S中已知屬性的聯(lián)合概率,即計(jì)算Q中屬性的聯(lián)合概率,具體步驟類似于第 4.1節(jié).在計(jì)算過(guò)Q中屬性的聯(lián)合概率后,對(duì)于任意的元組ti,有:

· 步驟3:對(duì)每個(gè)解釋計(jì)算支持度和置信度.

解釋的支持度和置信度是在對(duì)解釋排序時(shí)需要采用的非常重要的評(píng)價(jià)指標(biāo).首先,仿照條件函數(shù)依賴,定義解釋的支持度和置信度.

對(duì)于一個(gè)解釋e,它的支持度被定義為

置信度被定義為

其中,對(duì)所有j=1,…,l,當(dāng)e包含否定符號(hào)?時(shí),fe[Bj]=0;其余情況下,fe[Bj]=1.

· 步驟4:尋找候選解釋.

從步驟3中得到所有解釋的支持度以及置信度值后,需要根據(jù)支持度和置信度值篩選候選解釋.在尋找候選解釋時(shí),我們?cè)试S用戶提供一個(gè)閾值η,當(dāng)解釋的支持度值大于η時(shí),此解釋可作為一個(gè)候選解釋.

對(duì)所有候選解釋按照其置信度值進(jìn)行排序,即可得到返回的整體列表.

在介紹了以上步驟后,給出算法的偽代碼見(jiàn)算法2.

算法2.根據(jù)兩兩比較結(jié)果進(jìn)行概率推理.

輸入:兩兩比較結(jié)果表S,Why-not問(wèn)題比較表Q,缺失答案q,閾值η;

輸出:整體列表Lall.

4.2.3 算法實(shí)例描述

如例1中例子所示,首先,需要計(jì)算兩張兩兩比較結(jié)果表,一張是表1中元組內(nèi)部進(jìn)行兩兩比較的結(jié)果表S,一張是Why-not問(wèn)題中已知屬性與表1中所有元組的已知屬性值進(jìn)行比較的結(jié)果Q.

首先,呈現(xiàn)如何計(jì)算S.以表1中的第1個(gè)元組和第2個(gè)元組為例,他們的No.O-rings和Pressure兩個(gè)屬性值相等,而其他的屬性值不相等,則在S中即可以插入一條元組(1,0,0,1,0),仍分別對(duì)應(yīng)表1中的5個(gè)屬性.然后再以表1中的第1個(gè)元組和第3個(gè)元組為例,他們的No.O-rings,No.ETD和Pressure這3個(gè)屬性值相等,則S中又可以插入一條元組(1,1,0,1,0).如此計(jì)算后,得到完整的S;再對(duì)屬性的順序進(jìn)行重排,將未知屬性放在前,已知屬性放在后,即可得到最終的兩兩比較結(jié)果表S,表1的部分兩兩比較結(jié)果表見(jiàn)表3.

Table 3 Pair-wise table of Challenger USA space shuttle O-ring dataset表3 挑戰(zhàn)者號(hào)美國(guó)航天飛機(jī)O型圈數(shù)據(jù)集的兩兩比較結(jié)果表

然后,呈現(xiàn)如何計(jì)算Q.以表1中的第1個(gè)元組為例,與Why-not問(wèn)題中的No.O-rings,Temp,Order這3個(gè)屬性值進(jìn)行對(duì)比.他們的No.O-rings屬性值相等,而其他的屬性值不相等,則在Q中即可以插入一條元組(1,0,0),分別對(duì)應(yīng) No.O-rings,Temp,Order這 3個(gè)屬性.然后再以表1中的第 2個(gè)元組為例,與 Why-not問(wèn)題中的 No.O-rings,Temp,Order這3個(gè)屬性值進(jìn)行對(duì)比,No.O-rings屬性值相等,而其他的屬性值不相等,則在Q中又可以插入一條元組(1,0,0).如此計(jì)算后,得到完整的Q.表1與Why-not問(wèn)題進(jìn)行兩兩比較后的表見(jiàn)表4.

Table 4 Why-not pair-wise table of Challenger USA space shuttle O-ring dataset表4 挑戰(zhàn)者號(hào)美國(guó)航天飛機(jī)O型圈數(shù)據(jù)集與Why-not問(wèn)題的兩兩比較結(jié)果表

從表4中可以得到:

而從表3中可以得到:

繼而,對(duì)每個(gè)候選解釋,計(jì)算他們的支持度和置信度.在例 1中,候選解釋(6,0,78,50,12),(6,1,78,50,12),(6,0,78,100,12),(6,1,78,200,12),(6,2,78,200,12),(6,0,78,200,12),再結(jié)合4種0,1值的可能組合,如對(duì)于(6,0,78,50,12),可衍生出(6,-0,78,50,12),(6,0,78,-50,12),(6,-0,78,-50,12)另外 3種候選解釋,最終可以得到所有候選解釋.根據(jù)支持度和置信度的定義,可得到如表5所示的針對(duì)每個(gè)解釋的支持度和置信度值,篩選掉支持度小于等于 1的解釋后,對(duì)置信度進(jìn)行排序,即可得到解釋的整體列表.

Table 5 Support and confidence表5 支持度和置信度

4.2.4 算法問(wèn)題分析

上述算法的最大問(wèn)題在于數(shù)據(jù)集很大時(shí),不同的屬性對(duì)最后得到的條件概率的貢獻(xiàn)是不同的.若在中有一個(gè)屬性非常明顯地影響了其他屬性,另外一個(gè)屬性與其他屬性都獨(dú)立,顯然,對(duì)于這個(gè)屬性對(duì)結(jié)果沒(méi)有什么貢獻(xiàn).而影響了其他屬性,對(duì)最后得到的概率影響是巨大的.

5 概率模型學(xué)習(xí)

本節(jié)重點(diǎn)討論將統(tǒng)計(jì)學(xué)方法的思想與機(jī)器學(xué)習(xí)的方法結(jié)合尋找解釋.基于此思路,我們提出了兩大類算法.

· 第1類算法是與分類結(jié)合的算法,用高級(jí)的多分類算法來(lái)預(yù)測(cè)聯(lián)合概率;

· 第 2類算法是與回歸結(jié)合的算法,在此類算法中,基于不同屬性關(guān)系間的假設(shè),我們提出了 3種不同的算法:第1種是簡(jiǎn)單地從已知屬性值與未知屬性值的回歸式中進(jìn)行概率推理;第2種是選定一個(gè)未知屬性并將其余未知屬性也作為回歸的一部分,進(jìn)行選定屬性的概率推理;第 3種鏈?zhǔn)酵评矸椒ㄊ姑恳粋€(gè)已求解出的未知屬性值聯(lián)合已知屬性值作為即將要被求解的未知屬性值的前提條件.

對(duì)于兩類算法,首先都會(huì)對(duì)算法整體進(jìn)行概述,再詳細(xì)解釋算法并給出代碼.值得注意的是,上述算法全部基于第4節(jié)求出的兩兩比較結(jié)果表S.

5.1 分類

5.1.1 方法概述

對(duì)于兩兩比較結(jié)果表,可以將已知屬性值作為特征,將未知屬性值不同的 1/0組合看做不同的分類,利用較高級(jí)的多分類方法,比如 SVM,學(xué)習(xí)出一個(gè)關(guān)于已知屬性值和未知屬性值的分類模型.之后,對(duì)于這個(gè)學(xué)習(xí)出的分類模型,將第4節(jié)中提到的Why-not問(wèn)題和源數(shù)據(jù)表進(jìn)行對(duì)比后的對(duì)比表Q中的元組q1,…,qn一一代入分類模型中,得到不同條件下的屬于不同分類的未知屬性取值的概率.具體偽代碼見(jiàn)算法3.

算法3.與分類方法結(jié)合.

輸入:兩兩比較結(jié)果表S,Why-not問(wèn)題對(duì)比表Q,Why-not問(wèn)題q;

5.1.2 算法實(shí)例描述

由于與分類結(jié)合的方法和與回歸結(jié)合的方法在求支持度值和置信度值的方法和第 4節(jié)相同,所以這些方法與前面的概率推理方法有區(qū)別的地方在于如何求取概率的步驟,實(shí)例中只說(shuō)明到求取概率結(jié)束的步驟,剩余步驟方法與第4.2.3節(jié)中的方法相同.

在得到表3和表4之后,對(duì)于表3,可以將已知屬性No.O-rings,Temp和Order在表3中的1/0值作為特征值,將未知屬性No.ETD,Pressure的1/0組合值,即01,00,10,11作為4種類別,進(jìn)行多分類操作.

在多分類操作之后,對(duì)于表4中的每一種元組值(表4中只有1種元組值),將其代入多分類結(jié)果的模型,即可得到如下的概率:

5.2 聯(lián)合回歸

在所有聯(lián)合回歸方法中,利用多元線性回歸尋找屬性之間的關(guān)系,完成分類的作用,并利用邏輯回歸推理各個(gè)類別的概率.

5.2.1 回歸方法簡(jiǎn)介

線性回歸的最簡(jiǎn)單情景是只有一個(gè)純量的預(yù)測(cè)變量x和一個(gè)純量的結(jié)果變量y,這種線性回歸被稱為簡(jiǎn)單線性回歸.擴(kuò)展簡(jiǎn)單線性回歸至多向量型的預(yù)測(cè)變量(記為X),即可稱多元線性回歸.在現(xiàn)實(shí)世界中的幾乎所有用到線性回歸的場(chǎng)景,都是多元線性回歸.值得注意的是,在多元線性回歸中,y仍然是純量,但在多變量線性回歸中,y可以是一個(gè)向量.

5.2.2 邏輯回歸簡(jiǎn)介

在統(tǒng)計(jì)學(xué)中,邏輯回歸是一個(gè)因變量有類別的回歸模型,且因變量應(yīng)為二元因變量,即只能取0值或者1值.二元邏輯回歸模型通常被用來(lái)估計(jì)在一個(gè)或多個(gè)預(yù)測(cè)變量的條件下,二元因變量屬于每一種分類的概率.邏輯回歸中所用到的邏輯函數(shù)如下:

5.2.3 簡(jiǎn)單回歸方法

簡(jiǎn)單回歸方法的思想是:只考慮未知屬性的分類在已知屬性條件值下的概率值,不考慮未知屬性之間的關(guān)系.即:假設(shè)未知屬性和已知屬性之間存在相關(guān)關(guān)系,但未知數(shù)屬性之間彼此獨(dú)立.所以簡(jiǎn)單回歸方法分為如下步驟.

· 步驟1:對(duì)兩兩比較結(jié)果表S進(jìn)行回歸.

我們已知,未知屬性在兩兩比較結(jié)果表中用B1,...,B?表示,已知屬性在兩兩比較結(jié)果表中用B?+1,...,Bm表示.對(duì)于每一個(gè)未知屬性,都可以通過(guò)多元線性回歸找到其與已知屬性的線性關(guān)系,即,對(duì)于每一個(gè),都有:

· 步驟2:代入Q表中元組值,得到不同屬性在不同條件下分類的概率值.

在得到每個(gè)未知屬性和已知屬性的線性關(guān)系后,將Q表中的元組qi(1≤i≤n)代入各個(gè)關(guān)系式中,得到每一個(gè)在qi取值條件下相應(yīng)的Bj,將Bj取值代入邏輯函數(shù),可得.

具體算法的偽代碼見(jiàn)算法4.

算法4.簡(jiǎn)單回歸方法.

輸入:兩兩比較結(jié)果表S,Why-not問(wèn)題對(duì)比表Q,Why-not問(wèn)題q;

· 算法實(shí)例描述

對(duì)于例 1中的例子,在得到表3后,由于已知屬性為 No.O-rings,Temp和 Order,未知屬性為 No.ETD 和Pressure,則對(duì)于表3中的數(shù)據(jù),將No.ETD那一列的數(shù)據(jù),對(duì)所有已知屬性列的數(shù)據(jù)做回歸;對(duì)未知屬性Pressure也執(zhí)行同樣的操作,可以得到:

對(duì)于表4中的每一種元組值(只有 1種元組值),將其代入回歸結(jié)果的模型,可以得到No.ETD=0.60,Pressure=0.45.將兩種值帶入邏輯回歸的式子中,即可求得:

則:

同理,可以得到:

5.2.4 聯(lián)合回歸方法

此節(jié)中,介紹聯(lián)合回歸方法.聯(lián)合回歸方法的思想是,綜合考慮某個(gè)未知屬性在其他所有已知和未知屬性的條件下的概率值.此方法考慮了未知屬性之間的部分關(guān)系,即:假設(shè)未知屬性和已知屬性之間存在相關(guān)關(guān)系,且未知屬性和未知屬性之間也存在相關(guān)關(guān)系.所以,聯(lián)合回歸方法分為如下步驟.

· 步驟1:選取一個(gè)未知屬性,對(duì)兩兩比較結(jié)果表S進(jìn)行回歸.

· 步驟2:代入Q表中元組值,得到不同屬性在不同條件下分類的概率值.

在得到特定未知屬性Bj和其他屬性的線性關(guān)系后,將Q表中的元組qi(1≤i≤n)代入各個(gè)關(guān)系式中,得到在qi取值條件下相應(yīng)的Bj,將Bj取值代入邏輯函數(shù),可得:

具體算法的偽代碼見(jiàn)算法5.

算法5.聯(lián)合回歸方法.

輸入:兩兩比較結(jié)果表S,Why-not問(wèn)題對(duì)比表Q,Why-not問(wèn)題q;

· 算法實(shí)例描述

聯(lián)合回歸方法與簡(jiǎn)單回歸方法在回歸的步驟上不同.對(duì)于例 1中的例子,在得到表3后,由于已知屬性為No.O-rings,Temp和Order,未知屬性為No.ETD和Pressure,則對(duì)于表3中的數(shù)據(jù),將No.ETD那一列的數(shù)據(jù),對(duì)其他所有屬性列(包含所有已知屬性和未知屬性)的數(shù)據(jù)做回歸;對(duì)未知屬性Pressure也執(zhí)行同樣的操作,可得:

對(duì)于表4中的每一種元組值(表4中只有1種元組值),將其代入回歸結(jié)果的模型,可以得到:

解方程后得No.ETD=0.60,Pressure=0.45.將兩種值帶入邏輯回歸的式子中,即可求得:

則:

同理,可以得到:

5.2.5 鏈?zhǔn)交貧w方法

鏈?zhǔn)交貧w方法的思想是,按順序考慮未知屬性的分類在已知屬性條件值和已求出分類概率的未知屬性值的條件下的概率值.此方法考慮未知屬性之間的關(guān)系,即:假設(shè)未知屬性和已知屬性之間存在相關(guān)關(guān)系,且未知數(shù)屬性和未知屬性之間也存在相關(guān)關(guān)系.所以,鏈?zhǔn)交貧w方法分為如下步驟.

· 步驟1:選取一個(gè)未知屬性,對(duì)兩兩比較結(jié)果表S進(jìn)行回歸.

我們已知,未知屬性在兩兩比較結(jié)果表中用B1,...,B?表示,已知屬性在兩兩比較結(jié)果表中用B?+1,...,Bm表示.若選定一個(gè)未知屬性B1,都可以通過(guò)多元線性回歸找到其與已知屬性的線性關(guān)系,即:

· 步驟2:代入Q表中元組值,得到不同屬性在不同條件下分類的概率值.

在得到特定未知屬性B1和其他屬性的線性關(guān)系后,將Q表中的元組qi(1≤i≤n)代入各個(gè)關(guān)系式中,得到在qi取值條件下相應(yīng)的B1,將B1取值代入邏輯函數(shù),可得P(B1=1|B[?+1]=qi[B?+1],...,B[m] =qi[Bm]).

· 步驟3:基于之前求過(guò)的未知屬性和已知屬性值求新的未知屬性分類概率.

在得到特定未知屬性B1和已知屬性的線性關(guān)系后,假設(shè)下一步需要求另一特定未知屬性B2的分類概率,首先執(zhí)行步驟1,得到:

具體算法的偽代碼如下.

算法6.鏈?zhǔn)交貧w方法.

輸入:兩兩比較結(jié)果表S,Why-not問(wèn)題對(duì)比表Q,Why-not問(wèn)題q;

· 算法實(shí)例描述

鏈?zhǔn)交貧w方法與其他回歸方法也是在回歸的步驟上不同.對(duì)于例1中的例子,在得到表3后,由于已知屬性為No.O-rings,Temp和Order,未知屬性為No.ETD和Pressure,則對(duì)于表3中的數(shù)據(jù),將No.ETD那一列的數(shù)據(jù),先對(duì)所有已知屬性列的數(shù)據(jù)做回歸,可以得到:

對(duì)于表4中的每一種元組值(表4中只有1種元組值),將其代入回歸結(jié)果的模型,可以得到No.ETD=0.60.繼續(xù)將Pressure屬性對(duì)包括No.ETD和所有已知屬性列進(jìn)行回歸,可以得到:

對(duì)于表4中的每一種元組值(表4中只有1種元組值),結(jié)合No.ETD=0.60將其代入回歸結(jié)果的模型,可以得到Pressure=0.45,則:

同理,可以得到:

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

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

6.1.1 使用數(shù)據(jù)集

本文的實(shí)驗(yàn)中,利用了UCI Machine Learning Repository中的Airfoil Self-Noise,SkillCraft1和WineQuality這3個(gè)數(shù)據(jù)集.具體信息參見(jiàn)表6.

Table 6 Used datasets表6 使用數(shù)據(jù)集

值得注意的是:在本文的實(shí)驗(yàn)中,由于涉及到算法的中文名都較長(zhǎng),所以實(shí)驗(yàn)圖例中采用不同算法名稱的英文翻譯的縮寫,具體算法對(duì)應(yīng)信息見(jiàn)表7.

Table 7 Algorithm names表7 算法對(duì)應(yīng)名稱

6.1.2 實(shí)驗(yàn)環(huán)境

本實(shí)驗(yàn)在以下環(huán)境中進(jìn)行:處理器:2.5GHz Intel Core i7;內(nèi)存:16GB 1600MHz DDR3;操作系統(tǒng):MacOS 10.11.6;數(shù)據(jù)庫(kù)系統(tǒng):MySQL.

6.2 排序質(zhì)量對(duì)比

6.2.1 數(shù)據(jù)集設(shè)置

在進(jìn)行排序質(zhì)量對(duì)比的實(shí)驗(yàn)時(shí),首先在 3個(gè)不同的數(shù)據(jù)集上運(yùn)行了本文中提到的兩種不同的算法.而對(duì)于此實(shí)驗(yàn),需要知道 3種不同數(shù)據(jù)集中的未知屬性數(shù)和其數(shù)據(jù)類型,作為衡量數(shù)據(jù)集實(shí)驗(yàn)難度的標(biāo)準(zhǔn).具體信息見(jiàn)表8.

Table 8 Dataset setting of experiment of ranking quality表8 排序質(zhì)量實(shí)驗(yàn)數(shù)據(jù)集設(shè)置

6.2.2 質(zhì)量衡量方法

本實(shí)驗(yàn)中,將最原始的數(shù)據(jù)集表格作為正確的參考值.不失一般性,對(duì)實(shí)驗(yàn)在每一個(gè)數(shù)據(jù)集上的查詢都要進(jìn)行100次實(shí)驗(yàn),即:在每一次實(shí)驗(yàn)中,隨機(jī)選取原始查詢結(jié)果中出現(xiàn)的元組作為Why-not問(wèn)題,并在源數(shù)據(jù)庫(kù)中刪除掉相應(yīng)元組.然后,利用刪除掉上述相應(yīng)元組的數(shù)據(jù)庫(kù)對(duì)Why-not問(wèn)題進(jìn)行解釋,得到解釋結(jié)果的正列表.對(duì)于每一種算法得到的解釋結(jié)果的正列表,標(biāo)記與被刪除掉的源數(shù)據(jù)相同的元組出現(xiàn)的位置.在重復(fù) 100次實(shí)驗(yàn)后,選取top-1～top-100的位置,將這些位置中出現(xiàn)的正確元組數(shù)量相對(duì)于100次實(shí)驗(yàn)取均值,即可得到6種不同算法在不同數(shù)據(jù)集上的質(zhì)量.

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

由于在 3種數(shù)據(jù)集上,與多分類(SVM)結(jié)合的方法運(yùn)行時(shí)間過(guò)長(zhǎng),不能得到可觀的結(jié)果,故3種數(shù)據(jù)集上的質(zhì)量曲線圖中,只有除了與多分類(SVM)結(jié)合的方法之外的5種方法.

· Airfoil Self-Noise數(shù)據(jù)集

Airfoil Self-Noise數(shù)據(jù)集的6個(gè)屬性中,只有兩個(gè)屬性為整數(shù),其余均為實(shí)數(shù).實(shí)驗(yàn)選取的未知屬性也為實(shí)數(shù)屬性.從圖1(a)中可以看到:直接從原始數(shù)據(jù)進(jìn)行概率推理的方法在 1 500條具有實(shí)數(shù)的數(shù)據(jù)中,已經(jīng)顯現(xiàn)出了數(shù)據(jù)域過(guò)大從而導(dǎo)致稀疏性的危害,即top-100中,命中的解釋的個(gè)數(shù)為0.但當(dāng)我們將過(guò)大的實(shí)數(shù)數(shù)據(jù)域通過(guò)兩兩比較壓縮到{0,1}后再進(jìn)行簡(jiǎn)單的概率推理,得到的結(jié)果就會(huì)比直接從原始數(shù)據(jù)進(jìn)行概率推理好很多.當(dāng)與簡(jiǎn)單的統(tǒng)計(jì)機(jī)器學(xué)習(xí)方法結(jié)合后,除了與多分類方法結(jié)合的算法運(yùn)行過(guò)慢,與回歸結(jié)合的 3種方法都在和兩兩比較概率推理差不多的時(shí)間內(nèi)生成了結(jié)果,并得到了非常顯著的準(zhǔn)確率的提升.其中,聯(lián)合回歸方法在結(jié)果上稍優(yōu)于簡(jiǎn)單回歸方法,符合基礎(chǔ)統(tǒng)計(jì)學(xué)理論.鏈?zhǔn)交貧w方法在 top-10的排序質(zhì)量的表現(xiàn)上不如其他兩種與回歸結(jié)合的方法,主要原因是由于第2個(gè)計(jì)算的屬性與最先計(jì)算的屬性關(guān)聯(lián)較弱,導(dǎo)致鏈?zhǔn)交貧w方法效果不明顯.

Fig.1 Top-100 ranking quality of all algorithms on three datasets圖1 3個(gè)數(shù)據(jù)集上所有方法的top-100排序質(zhì)量

· WineQulaity數(shù)據(jù)集

WineQuality數(shù)據(jù)集的12個(gè)屬性全部為實(shí)數(shù),即,WineQuality數(shù)據(jù)集其實(shí)是稀疏性很高的數(shù)據(jù)集.實(shí)驗(yàn)選取的未知屬性也為實(shí)數(shù)屬性.雖然只選取了兩個(gè)位置屬性,但從圖1(b)中可以看到,直接從原始數(shù)據(jù)進(jìn)行概率推理的方法在近5 000條具有實(shí)數(shù)的數(shù)據(jù)中,仍然由于數(shù)據(jù)域過(guò)大導(dǎo)致的稀疏性而毫無(wú)效果.即:top-100中,命中的解釋的個(gè)數(shù)為 0.當(dāng)我們將過(guò)大的實(shí)數(shù)數(shù)據(jù)域通過(guò)兩兩比較壓縮到{0,1}后再進(jìn)行簡(jiǎn)單的概率推理,得到的結(jié)果就比直接從原始數(shù)據(jù)進(jìn)行概率推理好一些,但由于WineQuality本身是一個(gè)稀疏性相對(duì)于Airfoil Self-Noise數(shù)據(jù)集較大的數(shù)據(jù)集,從圖1(b)中可以明顯地看到,此方法相對(duì)于直接從原始數(shù)據(jù)進(jìn)行概率推理的方法提升并不如圖1(a)中明顯.但當(dāng)與簡(jiǎn)單的統(tǒng)計(jì)機(jī)器學(xué)習(xí)方法結(jié)合后,除了與多分類方法結(jié)合的算法運(yùn)行過(guò)慢,與回歸結(jié)合的3種方法都在兩兩比較概率推理一半左右的時(shí)間內(nèi)生成了結(jié)果,并得到了非常顯著的準(zhǔn)確率的提升.其中,聯(lián)合回歸方法和鏈?zhǔn)交貧w方法在結(jié)果上稍優(yōu)于簡(jiǎn)單回歸方法,符合基礎(chǔ)統(tǒng)計(jì)學(xué)理論.

· SkillCraft1數(shù)據(jù)集

為了驗(yàn)證與機(jī)器學(xué)習(xí)結(jié)合的方法在尋找稀疏性較低的屬性時(shí)是否會(huì)由于求解最后結(jié)果的過(guò)程較為繁瑣而導(dǎo)致效果不如簡(jiǎn)單的概率推理,我們?cè)赟kill Craft1數(shù)據(jù)集上選取了3個(gè)屬性域較小的整數(shù)屬性作為未知屬性.從圖1(c)中可以看到,直接從原始數(shù)據(jù)進(jìn)行推理的方法仍然沒(méi)有效果;但通過(guò)兩兩比較壓縮到{0,1}后再進(jìn)行簡(jiǎn)單的概率推理后,得到的結(jié)果就比直接從原始數(shù)據(jù)進(jìn)行概率推理好一些.當(dāng)與簡(jiǎn)單的統(tǒng)計(jì)機(jī)器學(xué)習(xí)方法結(jié)合后,除了與多分類方法結(jié)合的算法運(yùn)行過(guò)慢,與回歸結(jié)合的3種方法都得到了不比簡(jiǎn)單概率推理差、甚至稍好一點(diǎn)的排序質(zhì)量.這說(shuō)明對(duì)于稀疏性較低的屬性,與回歸結(jié)合的 3種方法在幾乎相同的時(shí)間內(nèi),得到的質(zhì)量并不會(huì)比簡(jiǎn)單概率推理差.

· 效果總結(jié)

綜上,對(duì) 3個(gè)數(shù)據(jù)集上所有算法的排序質(zhì)量分析可以看到,對(duì)于屬性域較大、稀疏性較高的數(shù)據(jù)集,與機(jī)器學(xué)習(xí)結(jié)合方法的效果明顯優(yōu)于直接從原始數(shù)據(jù)進(jìn)行概率推理和從兩兩比較結(jié)果進(jìn)行概率推理的方法;而對(duì)于稀疏性較低的數(shù)據(jù)集,與機(jī)器學(xué)習(xí)結(jié)合的方法的效果也并不會(huì)弱于其他兩種簡(jiǎn)單概率推理方法.

6.3 運(yùn)行時(shí)間對(duì)比

在第6.2節(jié)排序質(zhì)量對(duì)比的實(shí)驗(yàn)基礎(chǔ)上,統(tǒng)計(jì)了每種方法在每個(gè)數(shù)據(jù)集上做100次實(shí)驗(yàn)后得到的平均運(yùn)行時(shí)間,如圖2所示.可以看到在實(shí)驗(yàn)過(guò)程中,數(shù)據(jù)集中的元組個(gè)數(shù)和屬性個(gè)數(shù)對(duì)運(yùn)行時(shí)間的影響都較大,所以在第6.4節(jié)中,基于WineQuality數(shù)據(jù)集進(jìn)行擴(kuò)展性實(shí)驗(yàn)的研究.

Fig.2 Runtime of all methods on three datasets圖2 所有方法在3個(gè)數(shù)據(jù)集上的運(yùn)行時(shí)間

6.4 擴(kuò)展性實(shí)驗(yàn)

6.4.1 數(shù)據(jù)集設(shè)置

我們基于WineQuality數(shù)據(jù)集,做關(guān)于行擴(kuò)展性和列擴(kuò)展性的實(shí)驗(yàn).

· 對(duì)于行擴(kuò)展性實(shí)驗(yàn),我們將提取 WineQuality數(shù)據(jù)集中 7個(gè)不同的子數(shù)據(jù)集,分別具有不同的元組數(shù),而未知屬性與第 6.2.3節(jié)全部相同,以衡量不同的元組數(shù)條件對(duì)不同方法求解 Why-not問(wèn)題解釋的排序質(zhì)量的影響和對(duì)不同方法的運(yùn)行時(shí)間的影響.具體信息見(jiàn)表9;

· 對(duì)于列擴(kuò)展性,設(shè)置 5種不同數(shù)量的未知屬性,以衡量在不同數(shù)量未知屬性的條件下,不同方法求解Why-not問(wèn)題解釋的排序質(zhì)量的變化趨勢(shì)以及不同方法運(yùn)行時(shí)間的變化趨勢(shì).具體信息見(jiàn)表10.

Table 9 Row scalability dataset setting表9 行擴(kuò)展性使用數(shù)據(jù)集設(shè)置

Table 10 Column scalability dataset setting表10 列擴(kuò)展性使用數(shù)據(jù)集設(shè)置

6.4.2 行擴(kuò)展性

· 排序質(zhì)量

為減少偶然性并全面觀察各個(gè)算法排序質(zhì)量隨著元組數(shù)量的變化,在此實(shí)驗(yàn)中分別測(cè)量了在不同元組數(shù)條件下的top-1排序質(zhì)量、top-10排序質(zhì)量、top-50排序質(zhì)量、top-100排序質(zhì)量和top-300排序質(zhì)量,具體結(jié)果如圖3所示.

Fig.3 Top-1, Top-10, Top-50, Top-100, Top-300 quality under different number of tuples圖3 不同元組數(shù)條件下的Top-1,Top-10,Top-50,Top-100,Top-300質(zhì)量

從圖3中可以看出:從原始數(shù)據(jù)進(jìn)行概率推理的方法一直沒(méi)有明顯效果.而從圖3(c)、圖3(d)兩張圖中可以看出:依據(jù)兩兩比較結(jié)果進(jìn)行概率推理的方法在top-50和top-100的排序質(zhì)量有輕微隨著元組數(shù)的增加而下降的趨勢(shì).但是圖3(e)中明顯可以得到下降的趨勢(shì).此實(shí)驗(yàn)結(jié)果與隨著數(shù)據(jù)量增多,稀疏性增加,簡(jiǎn)單概率推理的效果下降的理論相符.

而對(duì)于3種與回歸結(jié)合的概率推理方法,首先可以看到它們?cè)?張排序質(zhì)量圖顯示的結(jié)果上,因?yàn)?種與回歸結(jié)合的概率推理方法充分考慮了屬性之間的關(guān)系,所以得到的排序質(zhì)量都優(yōu)于兩種概率推理方法,并且得到的排序質(zhì)量一直很穩(wěn)定,幾乎不受數(shù)據(jù)量增加的影響.

· 運(yùn)行時(shí)間

所有方法在不同元組數(shù)條件下的運(yùn)行時(shí)間和內(nèi)存消耗如圖4所示,可以清楚地看到:從原始數(shù)據(jù)進(jìn)行概率推理的方法仍然是最快的,但也是效果最差的.而 3種與回歸結(jié)合的方法的圖像表明,3種算法是隨著數(shù)據(jù)集中元組數(shù)的增加呈線性增長(zhǎng)的.依據(jù)兩兩比較結(jié)果進(jìn)行概率推理的方法在元組數(shù)不斷增加的條件下,運(yùn)行時(shí)間呈非線性增長(zhǎng).若在相同的未知屬性條件下,3種與回歸結(jié)合的方法在時(shí)間和效果上都明顯優(yōu)于依據(jù)兩兩比較結(jié)果進(jìn)行概率推理的方法.而在運(yùn)行時(shí)的內(nèi)存消耗方面,可以清楚地看到:從原始數(shù)據(jù)進(jìn)行概率推理和根據(jù)兩兩比較進(jìn)行概率推理的方法所占內(nèi)存基本相同,而 3種與回歸結(jié)合的方法的運(yùn)行內(nèi)存消耗順序從小到大分別為簡(jiǎn)單回歸方法、聯(lián)合回歸方法和鏈?zhǔn)交貧w方法.這種順序是合理的,因?yàn)閺暮?jiǎn)單回歸方法到鏈?zhǔn)交貧w方法,屬性之間的關(guān)系被更加詳細(xì)地考慮,因此運(yùn)行時(shí)所占內(nèi)存聯(lián)合回歸方法和鏈?zhǔn)交貧w方法會(huì)大于簡(jiǎn)單回歸方法.在元組數(shù)不斷增加的條件下,5種方法的內(nèi)存消耗也呈近平方式增長(zhǎng),與本文所使用的兩兩比較方式內(nèi)存的增長(zhǎng)速度相符.

Fig.4 Runtime and memory of all methods圖4 所有方法在不同元組數(shù)條件下的運(yùn)行時(shí)間和內(nèi)存消耗

6.4.3 列擴(kuò)展性

· 排序質(zhì)量

為了減少偶然性并全面觀察各個(gè)算法排序質(zhì)量隨著未知屬性數(shù)量的變化,在此實(shí)驗(yàn)中分別測(cè)量了在不同元組數(shù)條件下的top-1排序質(zhì)量、top-10排序質(zhì)量、top-50排序質(zhì)量、top-100排序質(zhì)量和top-300排序質(zhì)量,具體結(jié)果如圖5所示.

從圖5中可以看出,從原始數(shù)據(jù)進(jìn)行概率推理的方法一直沒(méi)有明顯效果.而依據(jù)兩兩比較結(jié)果進(jìn)行概率推理的方法隨著未知屬性數(shù)的增加,下降的趨勢(shì)非常強(qiáng)烈;而在未知屬性數(shù)超過(guò)4之后,此方法在top-300的質(zhì)量也為0了.

而對(duì)于3種與回歸結(jié)合的概率推理方法,首先可以看到:隨著未知屬性的增加,排序質(zhì)量呈下降趨勢(shì).這是由于隨著未知屬性數(shù)量的增加,與回歸結(jié)合的概率推理方法可以學(xué)習(xí)到的信息變少的緣故.但是由于充分考慮屬性之間的關(guān)系,它們?cè)趖op-1,top-10,top-50,top-100,top-300的排序質(zhì)量上都優(yōu)于兩種概率推理方法.

Fig.5 Top-1, Top-10, Top-50, Top-100, Top-300 quality under different number of unknown attributes圖5 不同未知屬性數(shù)條件下的Top-1,Top-10,Top-50,Top-100,Top-300質(zhì)量

· 運(yùn)行時(shí)間

所有方法在不同元組數(shù)條件下的運(yùn)行時(shí)間如圖6所示,可以清楚地看到,從原始數(shù)據(jù)進(jìn)行概率推理的方法仍然是最快的,因?yàn)閺脑紨?shù)據(jù)進(jìn)行概率推理的方法在計(jì)算時(shí)不需要進(jìn)行兩兩比較等一系列步驟,但是也是效果最差的.而 3種與回歸結(jié)合的方法的圖像表明,3種算法是隨著測(cè)試數(shù)據(jù)集中未知屬性數(shù)的增加呈線性增長(zhǎng)的.依據(jù)兩兩比較結(jié)果進(jìn)行概率推理的方法,在未知屬性數(shù)不斷增加的條件下,運(yùn)行時(shí)間仍然穩(wěn)定,幾乎不受未知屬性數(shù)的影響.因?yàn)樵趦蓛杀容^時(shí),未知屬性數(shù)的數(shù)量相對(duì)于元組數(shù)量對(duì)運(yùn)行時(shí)間的影響較小.

Fig.6 Runtime of all methods under different number of unknown attributes圖6 所有方法在不同未知屬性數(shù)條件下的運(yùn)行時(shí)間

6.4.4 列擴(kuò)展性(含與分類結(jié)合方法)

為了比較與分類結(jié)合的方法和其他方法在不同未知屬性數(shù)條件下的效果,我們利用WineQuality數(shù)據(jù)集的子數(shù)據(jù)集WineQuality-300來(lái)對(duì)6種方法做不同的對(duì)比實(shí)驗(yàn).WineQuality-300中含有300條數(shù)據(jù),用如此少量數(shù)據(jù)的原因,是因?yàn)槎喾诸惙椒ǖ臅r(shí)間效率過(guò)慢,用太大的數(shù)據(jù)集無(wú)法在可觀時(shí)間內(nèi)得到結(jié)果.

在此列擴(kuò)展性實(shí)驗(yàn)中,仍然將排序質(zhì)量和運(yùn)行時(shí)間作為兩個(gè)重要的指標(biāo).為了更詳細(xì)地看到每個(gè)算法在top-50之前和top-100之前的變化趨勢(shì),此實(shí)驗(yàn)中還畫出了在不同未知屬性數(shù)條件下,top-50前和top-100前的趨勢(shì)圖.

· 排序質(zhì)量

所有方法在不同未知屬性數(shù)條件下,Top-1,Top-10,Top-50,Top-100,Top-300的排序質(zhì)量圖如圖7所示(含與分類結(jié)合的方法).在圖中可以清楚看到:當(dāng)在Top-1,未知屬性個(gè)數(shù)為1時(shí),如圖7(a)所示,與分類結(jié)合的方法比其他的方法得到的結(jié)果要好一些;但在其他情況下,如圖7(b)～圖7(e)所示,與分類結(jié)合的方法得到的排序質(zhì)量并沒(méi)有相對(duì)其他的方法有顯著的提升.這是由于在未知屬性個(gè)數(shù)為 1時(shí),分類時(shí)問(wèn)題為二分類;而當(dāng)未知屬性個(gè)數(shù)為2時(shí),分類問(wèn)題變?yōu)樗姆诸?以此類推.所以當(dāng)未知屬性個(gè)數(shù)增多時(shí),由于類別個(gè)數(shù)呈指數(shù)增長(zhǎng),與分類結(jié)合的方法效果并不會(huì)相對(duì)其他方法有顯著的提高.

Fig.7 Top-1, Top-10, Top-50, Top-100, Top-300 quality under different number of unknown attributes圖7 不同未知屬性數(shù)條件下的Top-1,Top-10,Top-50,Top-100,Top-300質(zhì)量

為了更加詳細(xì)地研究與分類結(jié)合的方法和其他算法的效果對(duì)比,在下文中給出每個(gè)算法在 top-50之前和top-100之前的變化趨勢(shì)圖.

· Top-50排序質(zhì)量趨勢(shì)

所有算法在 top-50之前在不同屬性數(shù)條件下的變化趨勢(shì)圖如圖8所示(含與分類結(jié)合的方法).圖8(a)～圖8(f)分別代表了未知屬性數(shù)為1～6時(shí),各個(gè)算法的top-50排序質(zhì)量趨勢(shì).從圖中可以看出,直接從源數(shù)據(jù)進(jìn)行概率推理的方法仍然是最差的.而依據(jù)兩兩比較比較結(jié)果進(jìn)行概率推理的方法在所有屬性數(shù)條件下都差于與機(jī)器學(xué)習(xí)結(jié)合的方法.與分類結(jié)合的方法在前top-10的表現(xiàn)比與回歸結(jié)合的方法好,而在top-10之后都差于或持平與回歸結(jié)合的方法.

Fig.8 Top-50 quality ranking trend under different number of unknown attributes圖8 不同未知屬性數(shù)條件下的Top-50排序質(zhì)量趨勢(shì)

· Top-100排序質(zhì)量趨勢(shì)

所有算法在top-100之前在不同屬性數(shù)條件下的變化趨勢(shì)圖如圖9所示(含與分類結(jié)合方法).圖9(a)～圖9(f)分別代表了未知屬性數(shù)為1～6時(shí),各個(gè)算法的top-100排序質(zhì)量趨勢(shì).Top-100排序質(zhì)量趨勢(shì)圖是對(duì)top-50趨勢(shì)圖做了擴(kuò)展,以防止因?yàn)槿〉膖op-k數(shù)量過(guò)小而導(dǎo)致趨勢(shì)不明.觀察圖9,得到的結(jié)論與top-50趨勢(shì)圖得到的結(jié)論一致.

Fig.9 Top-100 quality ranking trend under different number of unknown attributes圖9 不同未知屬性數(shù)條件下的Top-100排序質(zhì)量趨勢(shì)

· 運(yùn)行時(shí)間

所有方法在不同未知屬性條件數(shù)下的運(yùn)行時(shí)間如圖10所示(含與分類結(jié)合方法).可以明顯地看出:與分類結(jié)合的方法效率非常低,而其他方法的運(yùn)行時(shí)間都明顯優(yōu)于與分類結(jié)合的方法.

Fig.10 Runtime of all methods under different number of unknown attributes圖10 所有方法在不同未知屬性數(shù)條件下的運(yùn)行時(shí)間

6.5 討 論

在尋求 Why-not問(wèn)題解釋的應(yīng)用場(chǎng)景中,有的應(yīng)用場(chǎng)景對(duì)響應(yīng)時(shí)間要求較高,如對(duì) NBA球星信息的查詢;有的場(chǎng)景對(duì)解釋的準(zhǔn)確率要求較高,如用戶在查詢某個(gè)公司的員工信息時(shí),對(duì)缺失的年齡、社保號(hào)等信息的Why-not問(wèn)題解釋準(zhǔn)確率要求較高,甚至是絕對(duì)準(zhǔn)確.所以根據(jù)不同的應(yīng)用場(chǎng)景,基于兩兩比較模型的 Why-not問(wèn)題解釋及排序方法更適用于對(duì)解釋準(zhǔn)確率要求較高的場(chǎng)景.

7 結(jié)論與未來(lái)工作

7.1 結(jié) 論

本文受利用兩兩比較方法尋找函數(shù)依賴的算法啟發(fā),提出了將兩兩比較方法和統(tǒng)計(jì)學(xué)方法以及機(jī)器學(xué)習(xí)方法進(jìn)行結(jié)合的針對(duì) Why-not問(wèn)題尋找解釋并對(duì)解釋進(jìn)行排序的算法.在尋找解釋之前,對(duì)傳統(tǒng)解釋的形式進(jìn)行了重新定義.對(duì)于取值域非常大的屬性,提出利用兩兩比較方法將屬性的值域壓縮到{0,1},并首先利用統(tǒng)計(jì)學(xué)方法對(duì)得到的兩兩比較結(jié)果值進(jìn)行初始統(tǒng)計(jì),得到一種候選解釋和其概率,計(jì)算統(tǒng)計(jì)學(xué)特征后進(jìn)行排序.之后,和機(jī)器學(xué)習(xí)中的多分類和回歸方法進(jìn)行結(jié)合,經(jīng)過(guò)實(shí)驗(yàn)證明,與回歸方法結(jié)合較與多分類結(jié)合方法更為有效;與多分類結(jié)合的方法比直接進(jìn)行概率統(tǒng)計(jì)的方法更為有效.

與之前已有的成果相比,本文更多地考慮了在求解釋的過(guò)程中對(duì)解釋進(jìn)行詳細(xì)化和排序,是在以前的相關(guān)工作中并未被仔細(xì)考慮的方面.實(shí)驗(yàn)證明:詳細(xì)化和排序確實(shí)對(duì)用戶更好更快地尋找解釋起到了積極作用.

7.2 未來(lái)工作展望

在后續(xù)工作中,可以從兩個(gè)個(gè)方面對(duì)現(xiàn)有工作進(jìn)行擴(kuò)展.

· 首先,考慮更大規(guī)模的數(shù)據(jù).目前,我們利用兩兩比較方法尋找解釋并對(duì)解釋進(jìn)行排序的時(shí)候,考慮的是整個(gè)數(shù)據(jù)庫(kù)中的對(duì)比結(jié)果.而在后續(xù)工作中,可以考慮對(duì)原始數(shù)據(jù)集進(jìn)行適當(dāng)采樣,使得采樣結(jié)果可以大致描述整個(gè)數(shù)據(jù)集的樣子.然后,在采樣結(jié)果上進(jìn)行兩兩比較的操作與運(yùn)算;

· 其次,可以考慮頻繁更改的數(shù)據(jù)庫(kù).現(xiàn)有的工作只針對(duì)于確定的數(shù)據(jù)庫(kù),對(duì)于頻繁更改的數(shù)據(jù)庫(kù),可以考慮在數(shù)據(jù)庫(kù)的時(shí)間切片上進(jìn)行采樣,并利用某個(gè)時(shí)間窗內(nèi)找到的可能解釋,綜合解釋的時(shí)間戳,找到最合理的解釋.

綜上所述,上述兩方面將是日后研究的重點(diǎn).在將來(lái)的工作中,將爭(zhēng)取對(duì)現(xiàn)有工作進(jìn)行擴(kuò)展,得到能夠解決更加通用的實(shí)際問(wèn)題的方法.