面向數(shù)據(jù)集覆蓋問題的優(yōu)化算法研究

劉榮鑫

（哈爾濱工業(yè)大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院， 哈爾濱150001）

0 引 言

數(shù)據(jù)科學(xué)時代，基于某些數(shù)據(jù)集訓(xùn)練學(xué)習(xí)算法是非常常見的。 通過調(diào)查或科學(xué)實(shí)驗(yàn)，可以前瞻性地收集到數(shù)據(jù)集，最近已經(jīng)認(rèn)識到訓(xùn)練數(shù)據(jù)集只具有代表性是不夠的，如果受訓(xùn)練的系統(tǒng)要很好地處理一些不太流行的類別，則必須包括來自這些類別的足夠的例子。 “谷歌大猩猩”強(qiáng)調(diào)了這種包含問題的重要性，谷歌早期發(fā)布的圖像識別算法沒有對足夠多的深色皮膚圖像進(jìn)行訓(xùn)練，當(dāng)呈現(xiàn)黑皮膚的非洲裔美國人的圖像時，該算法將她識別為“大猩猩”［1］。 還有很多其他此類事件也說明了這個問題。 雖然谷歌對大猩猩事件的解決方案是“刪除大猩猩標(biāo)簽”，但更好的解決方案是事先確保訓(xùn)練數(shù)據(jù)在每個類別中都有足夠的條目。 無論分析任務(wù)的數(shù)據(jù)收集模式是什么，必須確保每個對象類別在數(shù)據(jù)集中有足夠的條目。 從數(shù)據(jù)多樣性相關(guān)的文獻(xiàn)中汲取靈感，將這個概念稱為“Coverage”，這樣的問題就是數(shù)據(jù)集覆蓋問題［2-3］。 上述示例不是數(shù)據(jù)科學(xué)家采樣的問題，他們以某種方式獲取了一個數(shù)據(jù)集，然而沒有意識到數(shù)據(jù)集覆蓋問題。 數(shù)據(jù)集覆蓋問題也為對抗性攻擊開辟了空間［4］。

數(shù)據(jù)集覆蓋問題和不平衡學(xué)習(xí)（imbalanced learning）問題類似， 不平衡學(xué)習(xí)即數(shù)據(jù)表示和信息提取的學(xué)習(xí)過程，其中存在嚴(yán)重的數(shù)據(jù)分布偏差，開發(fā)有效的決策邊界來支持決策過程，主要有隨機(jī)采樣的方法和代價敏感學(xué)習(xí)的方法。 使用采樣的方法來解決不平衡學(xué)習(xí)的問題，主要是通過一些機(jī)制來改變原始數(shù)據(jù)集的分布，使得處理后的數(shù)據(jù)集分布平衡。 在這方面比較有代表性的工作有隨機(jī)過采樣、隨機(jī)欠采樣、基于數(shù)據(jù)生成的合成采樣、基于聚類的采樣方法、integration of sampling and boosting。代價敏感學(xué)習(xí)是利用不同類別的樣本被誤分類而產(chǎn)生不同的代價，使用這種方法解決數(shù)據(jù)不平衡問題。很多研究表明，代價敏感學(xué)習(xí)和樣本不平衡問題有很強(qiáng)的聯(lián)系［5］。

不平衡學(xué)習(xí)問題主要是處理數(shù)據(jù)集中標(biāo)簽屬性的問題。 而數(shù)據(jù)集覆蓋問題，主要是數(shù)據(jù)集中的缺乏覆蓋的問題，即數(shù)據(jù)集中的某些條目缺乏覆蓋的情況。 例如：對于一個關(guān)系型數(shù)據(jù)集，主要考察數(shù)據(jù)集中的特征屬性，而不是標(biāo)簽屬性；考察各特征屬性組成的“模式”所覆蓋的數(shù)據(jù)元組個數(shù)是否滿足特定閾值，提出相應(yīng)的評價指標(biāo)，用于評價數(shù)據(jù)集的覆蓋情況，運(yùn)用相應(yīng)的算法處理數(shù)據(jù)集覆蓋問題。

綜上所述，本文的數(shù)據(jù)集覆蓋問題不同于不平衡問題，使用現(xiàn)有的不平衡學(xué)習(xí)的方法可能不能很好的處理缺乏覆蓋的數(shù)據(jù)集。 本文研究分析了已有獲取MUP 的三種算法的優(yōu)缺點(diǎn)以及適用場景；結(jié)合關(guān)聯(lián)規(guī)則挖掘相關(guān)研究以及搜索算法的思路，并提出了針對DeepDiver 算法的改進(jìn)算法FastDeepDiver算法，它能夠更快地識別到未覆蓋模式并更快地獲取MUP，從而過濾掉更多的節(jié)點(diǎn)；提出了計算coverage 算法面，對數(shù)據(jù)稀疏問題以及位圖過大、內(nèi)存不足問題的解決思路。

1 數(shù)據(jù)集覆蓋問題相關(guān)算法研究與優(yōu)化

1.1 數(shù)據(jù)集覆蓋問題相關(guān)定義

給定一個數(shù)據(jù)集D，以及d 個低維分類屬性A ＝｛A1，A2，…，Ad｝。 如果屬性值是連續(xù)的或者高基數(shù)的，考慮用桶化的方法將其轉(zhuǎn)換為離散屬性。 對于圖像，比如說膚色，可能需要先進(jìn)行圖像的膚色相關(guān)的標(biāo)注，想辦法轉(zhuǎn)換為離散屬性的形式。 每個元組t ∈D 是一個向量，對于所有i ＝1，…，d，Ai的值為t［i］。 此外，數(shù)據(jù)集還包括包含目標(biāo)值的“標(biāo)簽屬性”Y ＝｛Y1，Y2，…，Yd｝，覆蓋問題中不考慮標(biāo)簽屬性。 數(shù)據(jù)集覆蓋問題的相關(guān)定義如下：

（1）模式（Pattern）。模式P 是大小為d 的向量，其中P［i］ 是X（意味著其值未指定） 或者是屬性Ai的值。 將值為X 的元素命名為非確定性元素，將其他元素命名為確定性元素。 一個元組t 匹配模式P（寫為M（t，P）＝T），如果對于所有的i，若P［i］ 是確定性的，t［i］ 等于P［i］；否則M（t，P）＝F。

（2）Coverage。 給定具有基數(shù)c ＝｛c1，c2，…，cd｝的d 個屬性的數(shù)據(jù)集D，以及基于c 和d 的模式P，模式P 的coverage 是D 中與P 匹配的元組數(shù)。 形式上：cov (P，D) ＝

（3） 覆 蓋／未 覆 蓋 模 式（Covered／Uncovered Pattern）。 如果模式P 的覆蓋大于或等于指定的覆蓋閾值τ，則稱模式P 為覆蓋模式，即cov (P，D) ≥τ。 否則，模式P 被稱為未覆蓋模式。

（4）父／子模式（Parent／Child Pattern）。 如果可以通過用X 替換P2中的一個確定性元素（比如P2［i］） 來獲得P1，則模式P1是模式P2的父模式，可以等效地說P2是模式P1的子模式。

（5） 極 大 未 覆 蓋 模 式（Maximal Uncovered Pattern （MUP））。給定閾值τ，如果cov (P ) ＜τ（未覆蓋），且對于P 的任意父模式P｀，cov (P｀ ) ≥τ（覆蓋），則P 為極大未覆蓋模式。

（6） MUP 識 別 問 題（ MUP Identification Problem）。給定在具有基數(shù)c的d 個屬性上定義的數(shù)據(jù)集D，以及覆蓋閾值τ，找到所有最大未覆蓋模式M 集合。

1.2 對現(xiàn)有獲取MUP 算法的分析與研究

獲取MUP，即解決MUP 識別問題。 獲取MUP的算法是基于遍歷模式圖的方法。

模式圖（Pattern graph）：令P 為在基數(shù)為c 的d個屬性上定義的所有可能模式的集合。 P 的模式圖是圖G（V，E），其中V ＝P。 具有父子關(guān)系的每對節(jié)點(diǎn)P 和P｀之間都有一條邊。 每個邊緣位于相鄰級別的兩個節(jié)點(diǎn)之間，父節(jié)點(diǎn)比子節(jié)點(diǎn)小一級。

如圖1 所示，為3 個二元屬性的模式圖，二元屬性即每個屬性的屬性值可以取0 或1。 下面將通過該模式圖示例對已有的獲取MUP 算法進(jìn)行分析，并提出改進(jìn)算法。

圖1 3 個二元屬性的模式圖Fig. 1 The pattern graph of three binary attributes dataset

1.2.1 自頂向下算法（Pattern-Breaker）分析

自頂向下的算法類似極大頻繁項(xiàng)集挖掘中的MaxMiner 算法，采用了廣度優(yōu)先遍歷的搜索策略［6］。 它從最一般的模式開始，不斷地一層一層地生成更具體的子模式，并利用coverage 的“單調(diào)性”屬性來過濾掉模式圖中的部分節(jié)點(diǎn)。 圖1 的模式圖轉(zhuǎn)換為一個樹形圖，如圖2 所示。

自頂向下算法利用單調(diào)性過濾掉部分子模式圖，來減少獲取MUP 所消耗的時間，但是這個算法在它找到未覆蓋模式前，需要遍歷模式圖中的已覆蓋區(qū)域的節(jié)點(diǎn)，計算這些節(jié)點(diǎn)的coverage，它的運(yùn)行時間取決于模式圖中已覆蓋區(qū)域的大小。 因此，如果模式圖中一大片區(qū)域都是已覆蓋的，那么自頂向下的算法運(yùn)行時間就很長，性能較差。

圖2 自頂向下算法樹形圖Fig. 2 Thetree graph of Pattern-Breaker

1.2.2 自底向上算法（Pattern-Combiner）分析

自底向上算法參考頻繁項(xiàng)集挖掘中從特殊到一般的思路，它自底向上地遍歷模式圖，同樣用單調(diào)性來避免遍歷整個模式圖，一旦找到了一個已覆蓋模式，就可以過濾掉這個分支。 自底向上算法將模式圖轉(zhuǎn)化為一個森林，并通過相應(yīng)的規(guī)則，來保證每個候選節(jié)點(diǎn)只生成一次，如圖3 所示。

圖3 自底向上算法森林圖Fig. 3 The forest graph of Pattern-Combiner

自底向上算法先遍歷未覆蓋區(qū)域的節(jié)點(diǎn)，所以如果模式圖中大部分節(jié)點(diǎn)都是未覆蓋的，那么該算法的性能較差。 同時，由于它最開始需要通過倒排索引的方式計算第d 層的各個節(jié)點(diǎn)的coverage， 而對d - 1 層到第0 層的節(jié)點(diǎn)的coverage，只需要根據(jù)其子節(jié)點(diǎn)得到。 所以，自底向上算法適用于屬性基數(shù)較小，且閾值較?。ù蟛糠止?jié)點(diǎn)都是已覆蓋的）的情況。 自底向上的算法對于屬性基數(shù)較大的數(shù)據(jù)集，運(yùn)行性能差。 原因：①屬性基數(shù)大，第d 層的模式節(jié)點(diǎn)很多。 ②根據(jù)子節(jié)點(diǎn)計算自身的coverage，所以基數(shù)變大后每個節(jié)點(diǎn)的計算時間也會增加（可能造成嚴(yán)重哈希沖突）。 對于屬性個數(shù)多，屬性基數(shù)小的數(shù)據(jù)集，使用自底向上的算法比較好，當(dāng)然也得綜合考慮閾值。

1.2.3 DeepDiver 算法分析

當(dāng)處于模式圖的中間層數(shù)時，這兩個算法都表現(xiàn)不佳，因?yàn)樗鼈兌夹枰闅v大約一半的模式圖。

DeepDiver 算法采用類似極大頻繁項(xiàng)集挖掘中MAFIA 算法的思路［6］，考慮使用深度優(yōu)先遍歷的搜索策略（擴(kuò)展節(jié)點(diǎn)方式同自頂向上算法），以更快地找到未覆蓋模式，通過建立已獲得的MUP 集合的倒排索引，來高效地過濾掉MUP 的祖先節(jié)點(diǎn)以及后代節(jié)點(diǎn)。 DeepDiver 算法對于屬性基數(shù)大的數(shù)據(jù)集大部分情況運(yùn)行時間比自底向上算法少，且更穩(wěn)定。

1.3 獲取MUP 的改進(jìn)算法——FastDeepDiver 算法

DeepDiver 算法利用了深度優(yōu)先搜索的方法盡快找到MUP，目的是更快地找到未覆蓋模式節(jié)點(diǎn)。深度優(yōu)先搜索擴(kuò)展的方向不一定是較優(yōu)的搜索方向，有爬山法最佳優(yōu)先搜索等方法用于優(yōu)化深度優(yōu)先搜索策略。

考慮這樣一個示例，一個有3 個二元屬性的數(shù)據(jù)集D，其只有一個數(shù)據(jù)元組100，設(shè)定閾值為1，可以得XX1 為MUP，考慮使用DeepDiver 算法來獲取MUP，如果它是通過XXX→1XX→10X→101 的路徑進(jìn)行深度優(yōu)先搜索，那么當(dāng)遍歷到101 時才發(fā)現(xiàn)其為未覆蓋模式，從101 開始向上找MUP，依次替換它的確定性元素為X，當(dāng)替換第一位為X 時，得到父節(jié)點(diǎn)X01，計算X01 的coverage，得到其為未覆蓋模式，繼續(xù)替換得到X01 的父節(jié)點(diǎn)XX1，計算XX1 的coverage，得到其為未覆蓋模式，繼續(xù)替換得到XX1的父節(jié)點(diǎn)XXX，計算XXX 的coverage，得到其為已覆蓋模式，因?yàn)閄X1 只有一個父節(jié)點(diǎn)，從而得到XX1 為MUP。 然而，如果它是按照XXX→XX1 的路徑進(jìn)行深度優(yōu)先搜索，那么在遍歷到XX1 時發(fā)現(xiàn)它是未覆蓋模式，從而發(fā)現(xiàn)它是MUP，那么當(dāng)后面遇到10X 以及它的后代節(jié)點(diǎn)直接被MUP 的倒排索引過濾了。 從上述例子推理可知，屬性個數(shù)越多，如果能在更淺的層找到未覆蓋模式，從而找到MUP，那么能夠過濾掉的節(jié)點(diǎn)就會更多，而且在往上找MUP 的過程，也能避免計算一些已覆蓋父節(jié)點(diǎn)的coverage。 也就是說，在更淺的層更早地發(fā)現(xiàn)MUP，就能更快地找到MUP，從而過濾掉更多的節(jié)點(diǎn)，可以減少在找到未覆蓋模式節(jié)點(diǎn)后，向上找遍歷的祖先節(jié)點(diǎn)個數(shù)。 因此，考慮結(jié)合爬山法和最佳優(yōu)先搜索策略對深度優(yōu)先搜索進(jìn)行優(yōu)化，提出對DeepDiver算法的改進(jìn)算法FastDeepDiver 算法。

先計算模式圖中第一層節(jié)點(diǎn)的coverage，如果第一層的各節(jié)點(diǎn)有一個未覆蓋模式節(jié)點(diǎn)，那么按照節(jié)點(diǎn)的coverage，由大到小的順序依次壓入棧中，再進(jìn)行深度優(yōu)先搜索；如果第一層各節(jié)點(diǎn)都是已覆蓋的，那么考慮從第一層的節(jié)點(diǎn)生成第二層的節(jié)點(diǎn)，計算第二層各節(jié)點(diǎn)的coverage，再按照第二層各節(jié)點(diǎn)的coverage 由大到小的順序依次壓入棧中。 這樣就保證了深度優(yōu)先搜索最初前進(jìn)的方向?yàn)樽顑?yōu)的方向。 FastDeepDiver 算法的偽代碼如下：

Algorithm 2FastDeepDiver

Input：DatasetDwithdattributes having cardinalities c and thresholdτ

Ouput：Maximal uncovered patternsM

1： LetS ＝an empty stack

2： compute the coverage of each node in level 1 and store them in a hash tableT

3：isLevelOneHasUncovered ＝a flag indicating if there is a uncovered

node in level 1

4：if isLevelOneHasUncovered ＝＝true then

5： push the nodes in level 1 toSin descending order of coverage

6：initialLevel ＝1

7：else

8： clear hash tableT

9： compute thecoverage of each node in level 2 and

store them in a hash tableT

10： push the nodes in level 2 toSin descending order of coverage

11：initialLevel ＝2

12：end if

13：level ＝initialLevel

14： whileSis not empty do

15：P ＝pop a node fromS

16： uncoveredFlag ＝a flag indicating ifPis uncovered

17：iflevel ＝＝initialLevelthen

18：cnt ＝T.get（P）

19：uncoveredFlag ＝cnt ＜τ

20： else ifPis dominated byMthen

21： continue

22： else ifPdominatesMthen

23：uncoveredFlag ＝false

24： else

25：cnt ＝cov（P，D）

26：uncoveredFlag ＝cnt ＜τ

27： end if

28： ifuncoveredFlag is truethen

29： LetS′ ＝an empty stack

30： pushPtoS′

31： whileS′is not empty do

32：P′ ＝pop a node fromS′

33：K ＝generates parent nodes ofP’ by replacing one deterministic cell withX

34：flag ＝0

35： forP″∈Kdo

36：cnt′ ＝cov（P″，D）

37： ifcnt′ ＜τthen

38： pushP″toS′

39：flag ＝1 ； break

40： end if

41： end for

42： ifflag ＝＝0 then

43： addP′toM

44： end if

45： end while

46： else

47：Q ＝generates nodes onPand c based on Rule 1

48：ifQ.size＝＝0 then

49：level - -

50： else

51：level ＝level + Q.size

52： end if

53： pushQtoS

54： end if

55： end while

56： returnM

第13 行中的level變量是判斷當(dāng)前棧中彈出的節(jié)點(diǎn)是否是處于一開始計算過的層中，如果是，可以通過哈希表直接得到節(jié)點(diǎn)的coverage。

有研究證明沒有多項(xiàng)式時間復(fù)雜度的算法可以完成MUP 的枚舉，考慮一個有n個數(shù)據(jù)元組和n個二元屬性的數(shù)據(jù)集D，這些屬性的屬性值只有對角線上的值為1，其他取值都為0，即?i∈［1，n］，有ti［i］＝1 且?j≠i，有ti［j］＝1，如表1 所示。

表1 示例數(shù)據(jù)集Tab. 1 The constructed dataset

可以做一個估算，考慮上述數(shù)據(jù)集，因?yàn)檎麄€模式圖中所有節(jié)點(diǎn)的個數(shù)為：

當(dāng)n ≥7 時，2n＞2 n2，即MUP 的個數(shù)大于前兩層的節(jié)點(diǎn)的總個數(shù)，找到一個MUP 后，可以過濾掉的節(jié)點(diǎn)個數(shù)顯然不止一個，而且當(dāng)n 越來越大時，前兩層的節(jié)點(diǎn)個數(shù)num ?total，計算的前兩層節(jié)點(diǎn)coverage 的個數(shù)也遠(yuǎn)小于能夠通過MUP 過濾掉的節(jié)點(diǎn)個數(shù)。

DeepDiver 算法相對于自頂向下算法以及自底向上算法來說，其優(yōu)點(diǎn)在于當(dāng)閾值不是特別大或者閾值不是特別小時，它能過濾的節(jié)點(diǎn)個數(shù)更多，性能更好， 相對來說更加穩(wěn)定。 本文提出的FastDeepDiver 算法，能夠更快地找到未覆蓋模式，從而更快地找到MUP，過濾掉更多的節(jié)點(diǎn)，它在大多數(shù)情況下，性能比DeepDiver 算法更好、更穩(wěn)定。

1.4 計算coverage 算法的改進(jìn)方法

coverage 的計算方法，將數(shù)據(jù)集轉(zhuǎn)換成屬性值的倒排索引。 該方法類似頻繁項(xiàng)集挖掘中的BitTableFI 算法，將數(shù)據(jù)庫轉(zhuǎn)換成高度壓縮的Bitmap的形式，通過基于Bitmap 上的位與運(yùn)算，快速計算出候選集的支持度，從而大大減少了挖掘過程中掃描數(shù)據(jù)庫的時間開銷。 計算coverage 的方法利用了倒排索引，從而也建立了一個Bitmap。

考慮一個示例數(shù)據(jù)集，其有3 個二元屬性，其中有5 個數(shù)據(jù)元組，t1為010，t2為000，t3為001，t4為101，t5為010，可以得到倒排索引如表2 所示。

得到了這樣的倒排索引后，根據(jù)與運(yùn)算和點(diǎn)積運(yùn)算的方法來獲得一個模式的coverage。 其中， 位向量的總個數(shù)為cd，c 即屬性的基數(shù)，d 為屬性個數(shù)，每個位向量的長度為O（n），因此存儲所有位向量需要O（cdn）。

表2 示例數(shù)據(jù)集倒排索引Tab. 2 The inverted indices of constructed dataset

上述方法存在兩個問題：①如果這個倒排索引比較稀疏，即Bitmap 中大部分值都為0 的情況，將會帶來很多無效的與操作。 ②雖然Bitmap 極快地提高了coverage 的計算效率，但是同樣也帶來了一個問題，即極大的內(nèi)存需要，如果數(shù)據(jù)元組類型太多，可能無法全部讀入內(nèi)存。 對于以上兩個問題，本文提出了以下3 個改進(jìn)方法。

（1）提高與運(yùn)算效率的方法。 考慮引入一個輔助內(nèi)存，比如要計算模式001 的coverage，先計算v1，0AND v2，0的結(jié)果，再用這個結(jié)果去和v3，1做與運(yùn)算，想要在這個過程中過濾掉很多0 的位，就可以考慮只存儲v1，0AND v2，0結(jié)果中為1 的位的下標(biāo)集合N，表2 的例子中N ＝｛0，1｝，0 表示000 的位置下標(biāo)，1 表示001 的位置下標(biāo)，只需要考察v3，1中處于N 中的下標(biāo)處是否為1 即可。 如果是0 則從N 中刪除這個下標(biāo)，即此時只需考察v3，1中下標(biāo)為0 和1位置的值，得到N ＝｛1｝，最后做與運(yùn)算得到結(jié)果為向量｛0，1，0，0｝， 再與cnt 做點(diǎn)積運(yùn)算， 即可得到001 的coverage 為1。

（2）壓縮Bitmap 的方法。 若Bitmap 中0 特別多，不妨考慮在倒排索引中只保存位置為1 的下標(biāo)，即每個vi，j中只存儲下標(biāo)值，為下標(biāo)的集合，比如表2 的例子中，v1，0為｛0，1，2｝。 Bitmap 中的與運(yùn)算轉(zhuǎn)換成求交集運(yùn)算，即下標(biāo)求交集運(yùn)算，得到的結(jié)果再轉(zhuǎn)換為位向量的形式，再與cnt 做點(diǎn)積即可。 這樣的方法壓縮了Bitmap 的存儲空間，但是增加了運(yùn)行時間。

（3）劃分Bitmap 的方法。 若Bitmap 中數(shù)據(jù)元組類型特別多，這樣的倒排索引無法全部存入內(nèi)存，可以考慮把Bitmap 按元組（即列索引）進(jìn)行劃分，比如表2 中的Bitmap，如果考慮把它劃分為兩個部分，則v1，0從｛1，1，1，0｝劃分為｛1，1｝和｛1，0｝ ，相應(yīng)的cnt 劃分從｛1，1，2，1｝ 劃分為｛1，1｝ 和｛2，1｝，各個部分讀入內(nèi)存后，各自做與運(yùn)算得到的結(jié)果與cnt 的該部分做點(diǎn)積運(yùn)算得到covi，再把這些cov 加起來就得到了coverage。

2 算法結(jié)果及分析

2.1 數(shù)據(jù)集與實(shí)驗(yàn)運(yùn)行環(huán)境

（1）數(shù)據(jù)集：①AirBnB 數(shù)據(jù)集，收集了785 331條數(shù)據(jù)元組以及15 個屬性，其中一個屬性為三元屬性，其他屬性都是二元屬性。 ②BlueNile 數(shù)據(jù)集，BlueNile 是全球最大的線上鉆石零售商，收集了116 300條數(shù)據(jù)元組，數(shù)據(jù)集包括7 個分類屬性，分別是形狀、切割、顏色、透明度、拋光度、對稱性和熒光，各自的屬性基數(shù)為10、4、7、8、3、3、5。

（2）實(shí)驗(yàn)運(yùn)行環(huán)境：①硬件環(huán)境，2.80GHz i5 CPU 以及12GB 內(nèi)存。 ②軟件環(huán)境，Windows 10 操作系統(tǒng)，通過Java 實(shí)現(xiàn)算法在IntelliJ IDEA 集成環(huán)境中運(yùn)行。

AirBnB 數(shù)據(jù)集由于其屬性個數(shù)較多，模式圖大，用于對比獲取MUP 的算法的性能；BlueNile 數(shù)據(jù)集由于其屬性基數(shù)較大，主要用于驗(yàn)證自底向上算法對于屬性基數(shù)較大的數(shù)據(jù)集性能較差的推理。

2.2 獲取MUP 算法性能對比實(shí)驗(yàn)

本文主要從閾值τ 變化以及數(shù)據(jù)元組個數(shù)n 的變化來進(jìn)行獲取MUP 算法的性能。

2.2.1 只改變閾值性能對比實(shí)驗(yàn)

只改變閾值，而不改變屬性個數(shù)以及數(shù)據(jù)元組個數(shù)。

（1）采用AirBnB 數(shù)據(jù)集，取前10 個屬性進(jìn)行實(shí)驗(yàn)，其中有一個屬性為三元屬性，其他屬性都為二元屬性，數(shù)據(jù)元組個數(shù)為785 331 個，約80 萬條數(shù)據(jù)元組，閾值從8 ～80 000，實(shí)驗(yàn)得到如圖4 的實(shí)驗(yàn)結(jié)果，隨著閾值從小變大，模式圖中由大部分模式都是已覆蓋的到大部分都是未覆蓋的，所以自頂向下算法運(yùn)行時間由長變短，自底向上算法運(yùn)行時間由短變長，DeepDiver 算法和FastDeepDiver 算法運(yùn)行時間都是先變長后變短，從圖中可以看到，自底向上算法大部分情況運(yùn)行時間都較短。

（2）采用屬性基數(shù)較大的BlueNile 數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)。 BlueNile 數(shù)據(jù)集一共有116 300 條數(shù)據(jù)元組，且有7 個屬性，閾值從1 ～1 000。 實(shí)驗(yàn)得到如圖5所示的結(jié)果。 可以看到，由于BlueNile 中屬性基數(shù)較大，自底向上的算法大部分情況運(yùn)行時間都較長。

（3）由上述實(shí)驗(yàn)可以看出，DeepDiver 算法和FastDeepDiver 算法有更好的魯棒性，更加穩(wěn)定。 接下來利用AirBnB 數(shù)據(jù)集驗(yàn)證FastDeepDiver 算法和DeepDiver 算法，本文采用AirBnB 數(shù)據(jù)集中的前13個屬性，其中12 個屬性為二元屬性，1 個屬性為三元屬性，數(shù)據(jù)元組個數(shù)n 為785331，閾值從8 ～80 000，實(shí)驗(yàn)得到如圖6 所示的結(jié)果，可以看出FastDeepDiver 算法大部分情況都比DeepDiver 算法性能更佳，因?yàn)镕astDeepDiver 算法能夠更快地尋找到未覆蓋模式（在更淺的層），從而找到MUP，從而過濾更多的節(jié)點(diǎn)。 當(dāng)閾值設(shè)定特別小時，DeepDiver算法運(yùn)行時間比FastDeepDiver 算法稍短，原因是閾值特別小時，模式圖中大部分區(qū)域都是已覆蓋的，相對DeepDiver 算法，F(xiàn)astDeepDiver 算法比較難在更淺的層找到未覆蓋模式，因?yàn)镕astDeepDiver 算法一開始需要先計算前兩層（可能不用計算第二層）的節(jié)點(diǎn)的coverage，且對這些節(jié)點(diǎn)按coverage 排序，所以當(dāng)閾值特別小時， FastDeepDiver 算法相對DeepDiver 算法沒有提升。 從實(shí)驗(yàn)可以得出，大部分情況下FastDeepDiver 算法是優(yōu)于DeepDiver 算法的，其魯棒性更佳。

圖4 AirBnB 數(shù)據(jù)集-只改變閾值（n＝785 331，d ＝10）Fig. 4 AirBnB：varying threshold（n＝785 331， d ＝10）

圖5 BlueNile 數(shù)據(jù)集-只改變閾值（n＝116 300，d ＝7）Fig. 5 BlueNile：varying threshold（n＝116 300，d ＝7）

2.2.2 只改變數(shù)據(jù)元組個數(shù)性能對比實(shí)驗(yàn)

本部分考察當(dāng)數(shù)據(jù)元組個數(shù)變化時，各個獲取MUP 算法運(yùn)行時間變化情況。 使用AirBnB 數(shù)據(jù)集，取前10 個屬性進(jìn)行實(shí)驗(yàn)，其中有一個屬性為三元屬性，其他屬性都為二元屬性，閾值取5 000，數(shù)據(jù)元組個數(shù)從8 000～785 331，得到如圖7 所示的實(shí)驗(yàn)結(jié)果。

圖6 AirBnB 數(shù)據(jù)集-只改變閾值（n＝785331，d＝13）Fig. 6 AirBnB：varying threshold（n＝785331，d ＝13）

圖7 AirBnB 數(shù)據(jù)集-只改變數(shù)據(jù)元組個數(shù)（threshold＝5000，d＝10）Fig. 7 AirBnB：varying data size（threshold＝5000，d ＝10）

從圖7 可以看出，各個算法運(yùn)行時間幾乎不變化，因?yàn)閿?shù)據(jù)元組個數(shù)大小只會影響計算coverage的倒排索引的大小，但當(dāng)數(shù)據(jù)元組個數(shù)為8 000 時，數(shù)據(jù)集幾乎所有元組類型都已經(jīng)包含到了，所以對倒排索引占內(nèi)存大小幾乎沒有影響，只影響cnt 向量中各位的值。 自底向上的算法只有在計算最底層的節(jié)點(diǎn)的coverage 時需要從倒排索引中計算，其受數(shù)據(jù)元組個數(shù)影響更小。

3 結(jié)束語

本文針對數(shù)據(jù)集覆蓋問題，在已有定義的基礎(chǔ)上，分析并提出了一系列的改進(jìn)優(yōu)化算法。 首先，分析了已有的獲取MUP 算法的優(yōu)缺點(diǎn)及適用場景；其次，結(jié)合關(guān)聯(lián)規(guī)則挖掘相關(guān)研究以及搜索算法的思路，研究并提出了針對DeepDiver 算法的改進(jìn)算法FastDeepDiver 算法，提出了計算coverage 算法對數(shù)據(jù)稀疏問題以及位圖過大內(nèi)存不足問題的解決思路。

通過實(shí)驗(yàn)分析了各個獲取MUP 的算法的性能，并驗(yàn)證了FastDeepDiver 算法相對于DeepDiver 算法的改進(jìn)效果。

未來考慮結(jié)合不平衡學(xué)習(xí)中的一些方法，用于處理數(shù)據(jù)集覆蓋問題。