兩兩比較模型的Why-not問題解釋及排序?

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

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

2(大數據系統軟件國家工程實驗室,北京 100084)

3(北京信息科學與技術國家研究中心,北京 100084)

1 引 言

1.1 問題背景

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

數據起源,或者可以叫做一段數據的歷史信息,曾經被用于研究解釋數據從哪里來[1-3]和在原始數據變成結果集的過程中都發生了什么[4-7].對于這些信息的整合,可以幫助我們理解為什么某些元組并沒有出現在結果集中[4,7,8].數據起源在這些工作中可以幫助人們解釋一些結果集中非正常的結果.

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

例1:考慮表1中的關系和查詢Q1:

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

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

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

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

Table 1 Challenger USA space shuttle O-ring dataset表1 挑戰者號美國航天飛機O型圈數據集

Table 2 Query results表2 查詢結果

1.2 主要貢獻

本文在以前工作的基礎上,做出了如下主要貢獻.

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

· 在多屬性的情況下,可能的值域會很大,為了避免數據稀疏性問題,提出將數據表示為兩兩比較關系,以{0,1}表示兩個元組在某個屬性上是否相等,從而支持更有效的概率模型學習;

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

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

· 在不同數據集上的實驗結果證明:利用統計、分類和回歸方法計算兩兩關系概率分布的方法,可以為用戶尋找Why-not問題的解釋并返回較為高質量的解釋.

1.3 論文結構

本文第 2節對相關工作進行具體介紹.第 3節給出本文的一些通用基礎定義和問題的形式化定義.解釋的統計學特征定義將與利用統計學方法尋找候選解釋和它們的概率分布的算法一起在第4節中說明.第5節呈現結合機器學習分類方法的尋找候選解釋及其概率分布的算法和3種結合回歸方法尋找候選解釋及其概率分布的算法.在第6節中將給出不同算法在真實數據集上的實驗結果的比較.最后,在第7節中對本文的工作進行總結,并對未來的工作進行展望.

2 相關工作

2.1 Why-not問題

現今,數據量正在快速地增長.數據庫管理系統從不同的數據源中抽取數據,聚合數據并將它們添加到數據庫中.但是數據源常常不具有很好的質量.由于數據源的低質量和低一致性,用戶或者數據科學家們經常會面臨一種問題:當他們在一個數據庫上執行查詢的時候,一些他們期望的答案并沒有出現在返回的查詢結果中.繼而用戶可能會詢問為什么一個或者多個元組沒有在查詢結果集中出現,也就是 Why-not問題.顯然,為數據科學家或者用戶提供針對于缺失元組的解釋,可以幫助他們更好地理解或修復數據庫.這種問題其實是數據起源問題的一個擴展,最早在文獻[12]中被提出.

2.2 缺失答案解釋

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

缺失答案(MA)[10]在給出單個缺少的元組和單個選擇項目連接(SPJ)查詢后,計算基于實例的解釋.事實上,它重寫查詢,使得重寫查詢的結果對應于指定的缺失答案的所有可能的基于實例的解釋.基于實例的說明插入或更新源數據,并且可以通過信任表(屬性)來減少需要被進行插入(更新)的數據.

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

Meliou等人統一了查詢結果和缺失答案中存在數據的基于實例的解釋[18].不使用數據來源[14],解決方案利用了因果關系和責任關系.此文詳細研究了基于因果關系和責任的聯合查詢解釋的復雜性,Meliou等人在文獻[18]中還將現有數據的一種具體類型的解釋統一為缺少數據的一種特定類型的解釋.

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

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

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

最近已經提出了計算針對關系和SQL查詢之外的查詢基于修改的解釋算法.在考慮副作用的同時,計算基于修改的解釋的一種算法專門解答Why-not的Top-k查詢問題[21].這個算法重點在于改變k或偏好權重,使缺失答案出現在查詢結果中.Islam等人在文獻[22]中提出了解決方案,回答了Why-not的反向Skyline查詢問題.

2.3 條件函數依賴

此節將介紹條件函數依賴的基礎定義[23]和它的一些有趣的統計學特征[24],即支持度和置信度.后文將基于條件函數依賴的統計學特征重新定義解釋的統計學特征.

2.3.1 基礎定義

一個在關系R上的條件函數依賴φ是一個元組R(X→Y,Tp),其中,

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

·R(X→Y)是一個標準函數依賴,又可以被叫做嵌在φ中的函數依賴;

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

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

2.3.2 統計學特征

(1) 支持度

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

其中,s是R中與φ相配的部分元組的數量,N是關系R中的元組數.

(2) 置信度

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

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

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

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

2.4 利用兩兩比較方法尋找函數依賴

受利用兩兩比較方法尋找函數依賴的算法啟發,我們簡化了解決問題的統計學方法,并為與機器學習算法結合提供了可能.本節簡略概述利用兩兩比較方法尋找函數依賴的3種算法.

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

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

3 基礎定義

為了方便對下文的理解,我們將闡述在整個論文中通用的一些基礎定義,并給出相應的示例作為解釋.

3.1 用戶的問題

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

3.2 基礎定義

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

定義1(待調試場景).一個待調試場景S可以被定義成為具有3個元素的元組〈query,D,E〉.D的具體含義是上文中提到的原始數據庫.query的具體含義是用戶在原始數據庫上執行的查詢.E的具體含義代表了一個沒有出現在query[D]但是出現在用戶的問題中的元組.

例2:如例1中所示,此處待調試場景S就可以被表示成〈Q1,挑戰者號美國航天飛機O型圈數據集,(6,78,12)〉.

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

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

定義3(解釋).若給定一個待調試場景S,一個解釋可被定義為一個帶符號的元組的集合,記為

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

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

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

從解釋式樣中可知,在Tk中的屬性可以被分為兩類:一類是已知屬性,另一類是未知屬性.假設Tk中的未知屬性共有l個,則對于關系Tk,它可以被表示成.其中,代表未知屬性,代表已知屬性.

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

定義5(解釋概率).一個解釋的概率,或者說一個解釋會被添加進原始數據庫的概率,記為P(e),可以被定義為一種聯合概率:

特別地,如果假設原始數據庫中所有的關系都是獨立的,即關系之間沒有外鍵等關系,那么可以得到如下的解釋概率表達式:

進一步地,如果假設原始數據庫中所有關系的所有屬性之間都是獨立的,即屬性之間沒有類 FD或者 CFD的函數依賴限制,那么可以得到如下的解釋概率表達式:

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

在整體列表Lall中,有一類比較特殊的解釋,它們的特點是沒有任何消極值.在整體列表中找到所有這樣的解釋并對他們進行排序,就可以得到解釋的正列表.同理,也可以得到解釋的負列表.

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

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

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

本節重點討論利用基礎的統計學方法尋找解釋的兩種算法:第 1種是未經任何變化從原始數據進行概率推理,第2種是在兩兩比較方法的基礎上對數據進行概率推理.對于這兩種算法,首先都會對算法整體進行概述,再詳細解釋算法并給出偽代碼.為了便于理解,還會給出相應運算實例.

4.1 從原始數據進行概率推理

4.1.1 算法概述

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

4.1.2 從原始數據進行概率推理算法

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

· 步驟1:統計所有屬性值的聯合概率.

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

· 步驟2:統計己知屬性值的聯合概率.

對于所有已知屬性值,按照步驟1中描述的方法統計聯合概率.首先,設所有已知屬性的值為,即:對于關系T中的任意元組ti,如果對于任意的已知屬性Ak,都有ti[Ak]=p[Ak],若以numknown代表已知屬性的值等于p中已知屬性值的元組個數,則其數量可以加1.則聯合概率為:

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

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

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

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

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

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

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

算法1.從原始數據進行概率推理.

輸入:原始數據庫中的關系T,查詢Q,缺失答案q;

輸出:整體列表Lall.

4.1.3 算法實例描述

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

首先在表1中尋找是否有與 3個屬性值完全相等的元組.尋找后發現沒有找到,則從源數據進行概率推理的方法并不能給出一個合理的解釋.即,尋找到的解釋的準確率為0.

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

4.1.4 算法問題分析

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

4.2 依據兩兩比較結果進行概率推理

4.2.1 算法概述

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

4.2.2 依據兩兩比較結果進行概率推理算法

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

· 步驟1:計算兩兩比較結果表.

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

· 步驟2:根據兩兩比較結果表統計聯合概率.

在得到兩兩比較結果表S后,按照第4.1節中統計所有屬性聯合概率的方法,可以初步統計所有屬性的聯合概率.假設兩兩比較結果表被分成了多個組,其中一個組對應的所有屬性值為b1,b2,…,bm,包含的元組數為numb,則:

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

接著,計算兩兩比較結果表S中已知屬性的聯合概率,即計算Q中屬性的聯合概率,具體步驟類似于第 4.1節.在計算過Q中屬性的聯合概率后,對于任意的元組ti,有:

· 步驟3:對每個解釋計算支持度和置信度.

解釋的支持度和置信度是在對解釋排序時需要采用的非常重要的評價指標.首先,仿照條件函數依賴,定義解釋的支持度和置信度.

對于一個解釋e,它的支持度被定義為

置信度被定義為

其中,對所有j=1,…,l,當e包含否定符號?時,fe[Bj]=0;其余情況下,fe[Bj]=1.

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

從步驟3中得到所有解釋的支持度以及置信度值后,需要根據支持度和置信度值篩選候選解釋.在尋找候選解釋時,我們允許用戶提供一個閾值η,當解釋的支持度值大于η時,此解釋可作為一個候選解釋.

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

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

算法2.根據兩兩比較結果進行概率推理.

輸入:兩兩比較結果表S,Why-not問題比較表Q,缺失答案q,閾值η;

輸出:整體列表Lall.

4.2.3 算法實例描述

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

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

Table 3 Pair-wise table of Challenger USA space shuttle O-ring dataset表3 挑戰者號美國航天飛機O型圈數據集的兩兩比較結果表

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

Table 4 Why-not pair-wise table of Challenger USA space shuttle O-ring dataset表4 挑戰者號美國航天飛機O型圈數據集與Why-not問題的兩兩比較結果表

從表4中可以得到:

而從表3中可以得到:

繼而,對每個候選解釋,計算他們的支持度和置信度.在例 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),再結合4種0,1值的可能組合,如對于(6,0,78,50,12),可衍生出(6,-0,78,50,12),(6,0,78,-50,12),(6,-0,78,-50,12)另外 3種候選解釋,最終可以得到所有候選解釋.根據支持度和置信度的定義,可得到如表5所示的針對每個解釋的支持度和置信度值,篩選掉支持度小于等于 1的解釋后,對置信度進行排序,即可得到解釋的整體列表.

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

4.2.4 算法問題分析

上述算法的最大問題在于數據集很大時,不同的屬性對最后得到的條件概率的貢獻是不同的.若在中有一個屬性非常明顯地影響了其他屬性,另外一個屬性與其他屬性都獨立,顯然,對于這個屬性對結果沒有什么貢獻.而影響了其他屬性,對最后得到的概率影響是巨大的.

5 概率模型學習

本節重點討論將統計學方法的思想與機器學習的方法結合尋找解釋.基于此思路,我們提出了兩大類算法.

· 第1類算法是與分類結合的算法,用高級的多分類算法來預測聯合概率;

· 第 2類算法是與回歸結合的算法,在此類算法中,基于不同屬性關系間的假設,我們提出了 3種不同的算法:第1種是簡單地從已知屬性值與未知屬性值的回歸式中進行概率推理;第2種是選定一個未知屬性并將其余未知屬性也作為回歸的一部分,進行選定屬性的概率推理;第 3種鏈式推理方法使每一個已求解出的未知屬性值聯合已知屬性值作為即將要被求解的未知屬性值的前提條件.

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

5.1 分類

5.1.1 方法概述

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

算法3.與分類方法結合.

輸入:兩兩比較結果表S,Why-not問題對比表Q,Why-not問題q;

5.1.2 算法實例描述

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

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

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

5.2 聯合回歸

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

5.2.1 回歸方法簡介

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

5.2.2 邏輯回歸簡介

在統計學中,邏輯回歸是一個因變量有類別的回歸模型,且因變量應為二元因變量,即只能取0值或者1值.二元邏輯回歸模型通常被用來估計在一個或多個預測變量的條件下,二元因變量屬于每一種分類的概率.邏輯回歸中所用到的邏輯函數如下:

5.2.3 簡單回歸方法

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

· 步驟1:對兩兩比較結果表S進行回歸.

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

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

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

具體算法的偽代碼見算法4.

算法4.簡單回歸方法.

輸入:兩兩比較結果表S,Why-not問題對比表Q,Why-not問題q;

· 算法實例描述

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

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

則:

同理,可以得到:

5.2.4 聯合回歸方法

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

· 步驟1:選取一個未知屬性,對兩兩比較結果表S進行回歸.

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

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

具體算法的偽代碼見算法5.

算法5.聯合回歸方法.

輸入:兩兩比較結果表S,Why-not問題對比表Q,Why-not問題q;

· 算法實例描述

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

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

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

則:

同理,可以得到:

5.2.5 鏈式回歸方法

鏈式回歸方法的思想是,按順序考慮未知屬性的分類在已知屬性條件值和已求出分類概率的未知屬性值的條件下的概率值.此方法考慮未知屬性之間的關系,即:假設未知屬性和已知屬性之間存在相關關系,且未知數屬性和未知屬性之間也存在相關關系.所以,鏈式回歸方法分為如下步驟.

· 步驟1:選取一個未知屬性,對兩兩比較結果表S進行回歸.

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

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

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

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

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

具體算法的偽代碼如下.

算法6.鏈式回歸方法.

輸入:兩兩比較結果表S,Why-not問題對比表Q,Why-not問題q;

· 算法實例描述

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

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

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

同理,可以得到:

6 實驗結果與分析

6.1 實驗設置

6.1.1 使用數據集

本文的實驗中,利用了UCI Machine Learning Repository中的Airfoil Self-Noise,SkillCraft1和WineQuality這3個數據集.具體信息參見表6.

Table 6 Used datasets表6 使用數據集

值得注意的是:在本文的實驗中,由于涉及到算法的中文名都較長,所以實驗圖例中采用不同算法名稱的英文翻譯的縮寫,具體算法對應信息見表7.

Table 7 Algorithm names表7 算法對應名稱

6.1.2 實驗環境

本實驗在以下環境中進行:處理器:2.5GHz Intel Core i7;內存:16GB 1600MHz DDR3;操作系統:MacOS 10.11.6;數據庫系統:MySQL.

6.2 排序質量對比

6.2.1 數據集設置

在進行排序質量對比的實驗時,首先在 3個不同的數據集上運行了本文中提到的兩種不同的算法.而對于此實驗,需要知道 3種不同數據集中的未知屬性數和其數據類型,作為衡量數據集實驗難度的標準.具體信息見表8.

Table 8 Dataset setting of experiment of ranking quality表8 排序質量實驗數據集設置

6.2.2 質量衡量方法

本實驗中,將最原始的數據集表格作為正確的參考值.不失一般性,對實驗在每一個數據集上的查詢都要進行100次實驗,即:在每一次實驗中,隨機選取原始查詢結果中出現的元組作為Why-not問題,并在源數據庫中刪除掉相應元組.然后,利用刪除掉上述相應元組的數據庫對Why-not問題進行解釋,得到解釋結果的正列表.對于每一種算法得到的解釋結果的正列表,標記與被刪除掉的源數據相同的元組出現的位置.在重復 100次實驗后,選取top-1～top-100的位置,將這些位置中出現的正確元組數量相對于100次實驗取均值,即可得到6種不同算法在不同數據集上的質量.

6.2.3 實驗結果

由于在 3種數據集上,與多分類(SVM)結合的方法運行時間過長,不能得到可觀的結果,故3種數據集上的質量曲線圖中,只有除了與多分類(SVM)結合的方法之外的5種方法.

· Airfoil Self-Noise數據集

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

Fig.1 Top-100 ranking quality of all algorithms on three datasets圖1 3個數據集上所有方法的top-100排序質量

· WineQulaity數據集

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

· SkillCraft1數據集

為了驗證與機器學習結合的方法在尋找稀疏性較低的屬性時是否會由于求解最后結果的過程較為繁瑣而導致效果不如簡單的概率推理,我們在Skill Craft1數據集上選取了3個屬性域較小的整數屬性作為未知屬性.從圖1(c)中可以看到,直接從原始數據進行推理的方法仍然沒有效果;但通過兩兩比較壓縮到{0,1}后再進行簡單的概率推理后,得到的結果就比直接從原始數據進行概率推理好一些.當與簡單的統計機器學習方法結合后,除了與多分類方法結合的算法運行過慢,與回歸結合的3種方法都得到了不比簡單概率推理差、甚至稍好一點的排序質量.這說明對于稀疏性較低的屬性,與回歸結合的 3種方法在幾乎相同的時間內,得到的質量并不會比簡單概率推理差.

· 效果總結

綜上,對 3個數據集上所有算法的排序質量分析可以看到,對于屬性域較大、稀疏性較高的數據集,與機器學習結合方法的效果明顯優于直接從原始數據進行概率推理和從兩兩比較結果進行概率推理的方法;而對于稀疏性較低的數據集,與機器學習結合的方法的效果也并不會弱于其他兩種簡單概率推理方法.

6.3 運行時間對比

在第6.2節排序質量對比的實驗基礎上,統計了每種方法在每個數據集上做100次實驗后得到的平均運行時間,如圖2所示.可以看到在實驗過程中,數據集中的元組個數和屬性個數對運行時間的影響都較大,所以在第6.4節中,基于WineQuality數據集進行擴展性實驗的研究.

Fig.2 Runtime of all methods on three datasets圖2 所有方法在3個數據集上的運行時間

6.4 擴展性實驗

6.4.1 數據集設置

我們基于WineQuality數據集,做關于行擴展性和列擴展性的實驗.

· 對于行擴展性實驗,我們將提取 WineQuality數據集中 7個不同的子數據集,分別具有不同的元組數,而未知屬性與第 6.2.3節全部相同,以衡量不同的元組數條件對不同方法求解 Why-not問題解釋的排序質量的影響和對不同方法的運行時間的影響.具體信息見表9;

· 對于列擴展性,設置 5種不同數量的未知屬性,以衡量在不同數量未知屬性的條件下,不同方法求解Why-not問題解釋的排序質量的變化趨勢以及不同方法運行時間的變化趨勢.具體信息見表10.

Table 9 Row scalability dataset setting表9 行擴展性使用數據集設置

Table 10 Column scalability dataset setting表10 列擴展性使用數據集設置

6.4.2 行擴展性

· 排序質量

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

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

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

而對于3種與回歸結合的概率推理方法,首先可以看到它們在5張排序質量圖顯示的結果上,因為3種與回歸結合的概率推理方法充分考慮了屬性之間的關系,所以得到的排序質量都優于兩種概率推理方法,并且得到的排序質量一直很穩定,幾乎不受數據量增加的影響.

· 運行時間

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

Fig.4 Runtime and memory of all methods圖4 所有方法在不同元組數條件下的運行時間和內存消耗

6.4.3 列擴展性

· 排序質量

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

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

而對于3種與回歸結合的概率推理方法,首先可以看到:隨著未知屬性的增加,排序質量呈下降趨勢.這是由于隨著未知屬性數量的增加,與回歸結合的概率推理方法可以學習到的信息變少的緣故.但是由于充分考慮屬性之間的關系,它們在top-1,top-10,top-50,top-100,top-300的排序質量上都優于兩種概率推理方法.

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

· 運行時間

所有方法在不同元組數條件下的運行時間如圖6所示,可以清楚地看到,從原始數據進行概率推理的方法仍然是最快的,因為從原始數據進行概率推理的方法在計算時不需要進行兩兩比較等一系列步驟,但是也是效果最差的.而 3種與回歸結合的方法的圖像表明,3種算法是隨著測試數據集中未知屬性數的增加呈線性增長的.依據兩兩比較結果進行概率推理的方法,在未知屬性數不斷增加的條件下,運行時間仍然穩定,幾乎不受未知屬性數的影響.因為在兩兩比較時,未知屬性數的數量相對于元組數量對運行時間的影響較小.

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

6.4.4 列擴展性(含與分類結合方法)

為了比較與分類結合的方法和其他方法在不同未知屬性數條件下的效果,我們利用WineQuality數據集的子數據集WineQuality-300來對6種方法做不同的對比實驗.WineQuality-300中含有300條數據,用如此少量數據的原因,是因為多分類方法的時間效率過慢,用太大的數據集無法在可觀時間內得到結果.

在此列擴展性實驗中,仍然將排序質量和運行時間作為兩個重要的指標.為了更詳細地看到每個算法在top-50之前和top-100之前的變化趨勢,此實驗中還畫出了在不同未知屬性數條件下,top-50前和top-100前的趨勢圖.

· 排序質量

所有方法在不同未知屬性數條件下,Top-1,Top-10,Top-50,Top-100,Top-300的排序質量圖如圖7所示(含與分類結合的方法).在圖中可以清楚看到:當在Top-1,未知屬性個數為1時,如圖7(a)所示,與分類結合的方法比其他的方法得到的結果要好一些;但在其他情況下,如圖7(b)～圖7(e)所示,與分類結合的方法得到的排序質量并沒有相對其他的方法有顯著的提升.這是由于在未知屬性個數為 1時,分類時問題為二分類;而當未知屬性個數為2時,分類問題變為四分類,以此類推.所以當未知屬性個數增多時,由于類別個數呈指數增長,與分類結合的方法效果并不會相對其他方法有顯著的提高.

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

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

· Top-50排序質量趨勢

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

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

· Top-100排序質量趨勢

所有算法在top-100之前在不同屬性數條件下的變化趨勢圖如圖9所示(含與分類結合方法).圖9(a)～圖9(f)分別代表了未知屬性數為1～6時,各個算法的top-100排序質量趨勢.Top-100排序質量趨勢圖是對top-50趨勢圖做了擴展,以防止因為取的top-k數量過小而導致趨勢不明.觀察圖9,得到的結論與top-50趨勢圖得到的結論一致.

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

· 運行時間

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

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

6.5 討 論

在尋求 Why-not問題解釋的應用場景中,有的應用場景對響應時間要求較高,如對 NBA球星信息的查詢;有的場景對解釋的準確率要求較高,如用戶在查詢某個公司的員工信息時,對缺失的年齡、社保號等信息的Why-not問題解釋準確率要求較高,甚至是絕對準確.所以根據不同的應用場景,基于兩兩比較模型的 Why-not問題解釋及排序方法更適用于對解釋準確率要求較高的場景.

7 結論與未來工作

7.1 結 論

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

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

7.2 未來工作展望

在后續工作中,可以從兩個個方面對現有工作進行擴展.

· 首先,考慮更大規模的數據.目前,我們利用兩兩比較方法尋找解釋并對解釋進行排序的時候,考慮的是整個數據庫中的對比結果.而在后續工作中,可以考慮對原始數據集進行適當采樣,使得采樣結果可以大致描述整個數據集的樣子.然后,在采樣結果上進行兩兩比較的操作與運算;

· 其次,可以考慮頻繁更改的數據庫.現有的工作只針對于確定的數據庫,對于頻繁更改的數據庫,可以考慮在數據庫的時間切片上進行采樣,并利用某個時間窗內找到的可能解釋,綜合解釋的時間戳,找到最合理的解釋.

綜上所述,上述兩方面將是日后研究的重點.在將來的工作中,將爭取對現有工作進行擴展,得到能夠解決更加通用的實際問題的方法.