天天看點

中國人工智能學會通訊——一種基于衆包的互動式資料修複方法 3 給定品質限制下的互動式算法

為了生成一個有效的互動式方案,我們提出了自己的算法,其中的關鍵問題是在衆包修複過程中如何選擇被衆包修複的值。

首先,我們傾向于選擇引起資料沖突最多的值進行衆包修複,這樣就會有更多的值在下一步的基于規則的修複過程中可以被推導。為了找出引起資料間沖突最多的值,先評估每個值的不和諧度disharmonious degree(簡稱為dScore),表示這個值和資料集中其他所有值之間的不和諧度。将在3.1節中介紹如何計算每個值的dScore。

中國人工智能學會通訊——一種基于衆包的互動式資料修複方法 3 給定品質限制下的互動式算法

雖然是在一個動态情況下安排沖突的修複順序,仍可以根據沖突之間的依賴關系,決定修複哪些值。在這一過程中,面臨的挑戰就是如何解決沖突間的依賴循環問題,我們将在3.2節中讨論這個問題。

一個值的不和諧度可以粗略地由它所引起的沖突的個數來表示。首先用一個簡單的例子介紹一下如何計算每個值的dScore。首先,假設除了某個位置上的值,整個資料集都是一緻的,即資料集上的其他所有值都是和諧的。然後,當該位置上的值出現後,可能會引起兩種沖突:①該值本身和一些值發生了沖突;②該值使得某個沖突裡的其他值發生了沖突。通常一個值帶來的沖突越多,這個值越有可能是一個錯誤的值。換句話說,在這種簡單的假設下,一個值的dScore就是它所引起的沖突的個數。

現在開始考慮實際情況,即資料集中已經存在錯誤的值和沖突。當一個新值出現時,不管它是否錯誤,都會帶來一些改變,如産生新的沖突或者加劇已有的沖突。在這種情況下,一個值的dScore由以下兩部分組成:

中國人工智能學會通訊——一種基于衆包的互動式資料修複方法 3 給定品質限制下的互動式算法
中國人工智能學會通訊——一種基于衆包的互動式資料修複方法 3 給定品質限制下的互動式算法

在安排沖突的修複順序時,我們會考慮沖突間的依賴關系。首先要獲得所有沖突之間的依賴關系,然後根據這些關系建立一個沖突依賴關系圖。

中國人工智能學會通訊——一種基于衆包的互動式資料修複方法 3 給定品質限制下的互動式算法
中國人工智能學會通訊——一種基于衆包的互動式資料修複方法 3 給定品質限制下的互動式算法
中國人工智能學會通訊——一種基于衆包的互動式資料修複方法 3 給定品質限制下的互動式算法
中國人工智能學會通訊——一種基于衆包的互動式資料修複方法 3 給定品質限制下的互動式算法

正如之前介紹的,一個沖突隻有在它所依賴的所有沖突都被解決之後,這個沖突才可以被解決。但是對于那些在同一個節點裡面互相重疊的沖突,需要考慮沖突裡的值被檢測的優先順序。同樣,我們根據這些值的dScore來确定檢測的順序。一個值的dScore越高,這個值越先被檢測。每次當有一個值被修改了,整個關系圖就需要随之更新。

中國人工智能學會通訊——一種基于衆包的互動式資料修複方法 3 給定品質限制下的互動式算法
中國人工智能學會通訊——一種基于衆包的互動式資料修複方法 3 給定品質限制下的互動式算法
中國人工智能學會通訊——一種基于衆包的互動式資料修複方法 3 給定品質限制下的互動式算法
中國人工智能學會通訊——一種基于衆包的互動式資料修複方法 3 給定品質限制下的互動式算法
中國人工智能學會通訊——一種基于衆包的互動式資料修複方法 3 給定品質限制下的互動式算法

互動式算法如算法1所示。首先要為資料集建立一個沖突依賴關系圖。不考慮其他因素,隻選擇每個節點中dScore最高的值進行衆包修複,直至節點中的所有沖突都被解決。當沒有這樣的節點隻有環時,計算這些環中所有節點的gbScore,選擇gbScore最高的節點進行處理進而分裂環。每次隻要有一個值被修改,關系圖、所有節點的bScore和gbScore都需要及時更新。當整個依賴關系圖中沒有一個節點時,算法就會結束。算法1的時間複雜度是O(mlogm+n),m是依賴關系圖中所有環中的節點個數,n指圖中不在環内的節點個數。

中國人工智能學會通訊——一種基于衆包的互動式資料修複方法 3 給定品質限制下的互動式算法
中國人工智能學會通訊——一種基于衆包的互動式資料修複方法 3 給定品質限制下的互動式算法
中國人工智能學會通訊——一種基于衆包的互動式資料修複方法 3 給定品質限制下的互動式算法
中國人工智能學會通訊——一種基于衆包的互動式資料修複方法 3 給定品質限制下的互動式算法
中國人工智能學會通訊——一種基于衆包的互動式資料修複方法 3 給定品質限制下的互動式算法

繼續閱讀