基于用戶查詢與樣本間匹配度評估的分層抽樣策略

鄔志罡 荊一楠 何震瀛 王曉陽,3

1(復旦大學計算機科學技術學院 上海 201203)2(上海市數(shù)據(jù)科學重點實驗室(復旦大學) 上海 200433)3(上海智能電子與系統(tǒng)研究院 上海 200433)

0 引 言

在數(shù)據(jù)探索性分析場景下，用戶將發(fā)起一系列查詢來探索數(shù)據(jù)集中的海量數(shù)據(jù)。然而，對整個海量數(shù)據(jù)集進行完整掃描將導致用戶查詢緩慢且阻礙了系統(tǒng)交互性，嚴重影響了用戶的生產(chǎn)力甚至創(chuàng)造力[1]。因此，用戶通常借助抽樣系統(tǒng)來生成海量數(shù)據(jù)集上的一個樣本子集，并在樣本集上得到查詢的近似結(jié)果，以查詢結(jié)果精確度上的損失換取更快的查詢速度。

分組聚合查詢普遍存在于數(shù)據(jù)探索性分析場景中，例如當用戶在保存商品交易記錄的數(shù)據(jù)集上進行探索時，將會發(fā)起如下查詢：SELECT SUM(sales) FROM order GROUP BY type來分析各種種類的商品銷售情況。在這種情況下，如果在構造樣本時采用隨機均勻抽樣策略(Uniform Sampling)，那么生成的樣本集中每種商品種類的樣本量將正比于該商品種類的交易記錄數(shù)量。這種均勻抽樣策略將導致從小眾的商品類別分組中收集到的樣本量不足，甚至導致交易數(shù)量非常稀缺的商品類別分組完全消失在最終結(jié)果中，從而產(chǎn)生很大的誤差[2]。為了能在相同抽樣率的限制條件下使得查詢結(jié)果擁有更高的精確度，現(xiàn)有系統(tǒng)通常采用分層抽樣策略(Stratified Sampling)[3]，即首先按照分組屬性的取值對數(shù)據(jù)集進行劃分，進而在劃分出的每個分組中進行抽樣。例如在上述的示例中，首先按照商品種類type對數(shù)據(jù)集進行分類，然后對每一類商品種類type中的數(shù)據(jù)分別進行抽樣。設計一種有效的分層抽樣策略的關鍵在于：(1) 依據(jù)哪些屬性進行分層；(2) 如何將固定的總樣本量具體分配到每一層中。針對第一個問題，現(xiàn)有分層抽樣系統(tǒng)通常利用到了用戶的歷史查詢記錄。此類系統(tǒng)基于用戶的歷史查詢記錄能被用來較為精準地預測未來用戶查詢請求這一假設，針對用戶歷史查詢記錄中表現(xiàn)出的分組特征，篩選出頻率最高的幾組分組屬性列集合，然后在其上進行分層抽樣。然而，在現(xiàn)實場景中，當用戶查詢特征的穩(wěn)定性無法得到保證時，或是在用戶查詢歷史無法獲得的情況下，甚至是當抽樣系統(tǒng)冷啟動未運行任何查詢時，現(xiàn)有的用戶查詢歷史驅(qū)動的抽樣系統(tǒng)將無法達到預期的效果。另一方面，針對上述第二個問題，國會抽樣策略[4]一文中給出了當查詢中分組條件確定時，最優(yōu)的分層抽樣策略對應的總樣本量具體到每個分組的分配方案，即在各分組間完全均勻分配?；谶@一理論，該文作者進一步提出了國會抽樣策略，即一種總樣本量分配方案優(yōu)化后的分層抽樣策略。然而，該抽樣策略雖然生成了一個面對任何分組查詢時能夠取得較優(yōu)的平均效果的樣本集，但其僅給出了在數(shù)據(jù)集上生成唯一一份樣本集的抽樣策略。然而，在現(xiàn)實場景中，如果抽樣系統(tǒng)能夠為用戶生成多份離線樣本集并支持在運行時自動從其中為用戶選擇出最匹配當前查詢的樣本集，其效果顯然要好于用一份樣本集來應對所有可能的用戶查詢[5]。

面對上文提到的這些挑戰(zhàn)，本文提出一種新的抽樣策略。本文主要貢獻包括：(1) 為任一具體分層抽樣策略，即其所生成的樣本集，與任意分組聚合查詢提供了一種匹配度評估的方法，并且提供了根據(jù)匹配度評估打分為用戶查詢選取最優(yōu)樣本集的方法。(2) 提出了一種基于用戶查詢與樣本間匹配度評估的分層抽樣策略，支持離線生成包含多份分層抽樣樣本集的抽樣組合。(3) 以限定相同樣本量評估近似結(jié)果精確度的方式，通過在模擬數(shù)據(jù)集和真實數(shù)據(jù)集上的大量實驗證明了本文提出的抽樣策略的有效性。

1 相關工作

BlinkDB[6]通過分析用戶的歷史查詢記錄，在篩選出的若干個熱點分組屬性集上進行分層抽樣。當用戶的歷史查詢記錄能很好地表征未來的查詢情況時，這種針對特定的查詢特征生成的特定抽樣策略顯然能夠獲得不錯的效果。然而，在某些數(shù)據(jù)探索性分析場景下，由于不同用戶的探索目的各不相同且其探索意圖隨時間不斷改變，這種用戶查詢特征不隨時間變化的穩(wěn)定性假設通常無法得到保證，因此此類抽樣系統(tǒng)的效果也會受到很大影響。另一方面，BlinkDB需要在運行時從多份預先準備的離線樣本中選取出一份最適合當前查詢的樣本，其選擇方法僅僅考慮了當前分組聚合查詢的分組條件屬性集與某一離線分層抽樣策略的分層屬性集之間的集合包含關系，沒有給出一個具體的可供量化的評估標準。

ICICLES[7]在進行抽樣時，對數(shù)據(jù)集中的每條記錄的抽取概率正比于該條記錄累計出現(xiàn)在用戶歷史查詢產(chǎn)生的結(jié)果集中的次數(shù)。該系統(tǒng)不斷更新維護一個根據(jù)用戶歷史查詢生成的多重集合，即一種允許相同元素重復出現(xiàn)的集合。每條用戶查詢結(jié)果中涉及到的數(shù)據(jù)記錄都會被存放在這個多重集合中。該系統(tǒng)將會在該多重集合上進行隨機均勻抽樣，以期望生成的樣本集能匹配將來的用戶查詢。然而，這樣的方式不僅使其生成的樣本強依賴于用戶歷史查詢記錄，并且會使得那些還沒有被用戶探索到的區(qū)域樣本量極其匱乏，這將嚴重阻礙用戶探索數(shù)據(jù)集中新的區(qū)域以獲取新的發(fā)現(xiàn)或結(jié)論。

國會抽樣策略[4]通過優(yōu)化分層抽樣策略的總樣本量分配方式來提高針對用戶分組聚合查詢返回的近似結(jié)果的精確度。相較于其僅僅生成唯一一份樣本集，本文提出的抽樣策略可以支持生成多份離線樣本集并在運行時自動從多份離線樣本集中選出最匹配的一份樣本集進行近似結(jié)果計算。由于準備了多份離線樣本，從中選出一份更能匹配當前用戶查詢特征的樣本的可能性將大大提升。

2 問題歸納

分層抽樣策略是一種先將整個數(shù)據(jù)集按照某些屬性上的取值分成若干層，然后再從每一層中隨機抽取樣本的抽樣方法。分層抽樣策略中，如何將總樣本量具體分配到每個分組中是影響最終生成的樣本集效果的最主要的問題。幸運的是，關于分層抽樣策略的諸多特性已經(jīng)有多位學者進行了研究總結(jié)。Acharya[4]證明了針對某一特定的用戶分組聚合查詢，即當用戶查詢中的分組條件確定時，最優(yōu)的分層抽樣總樣本量分配方案就是在該分組查詢將會產(chǎn)生的所有分組間均勻分配樣本空間。

從上文提到的分層抽樣策略最優(yōu)總樣本量分配方案中，我們可以看出，包含不同分組條件組合的用戶查詢所對應的最優(yōu)樣本集都是不同的。因此，抽樣系統(tǒng)希望通過僅僅一份離線樣本去應對所有可能的用戶查詢并都能獲得較優(yōu)的效果的這一目標是不現(xiàn)實的。如果系統(tǒng)可以在離線時生成多份樣本集，并且能夠在運行時自動根據(jù)當前用戶分組聚合查詢?nèi)〕鲆环葑钇ヅ涞臉颖炯M行近似結(jié)果計算，那么系統(tǒng)將有更大機會得到更為精確的近似結(jié)果。然而，在應對實際場景時，我們顯然無法為用戶發(fā)起的每種可能的分組聚合查詢準備一份最優(yōu)樣本。試想，當用戶的查詢模式不具備時間上的穩(wěn)定性時，我們想要優(yōu)化的查詢集合將無法被縮小到一個預處理開銷可以承受的范圍內(nèi)。例如，當數(shù)據(jù)集上共有20個分組屬性時，總共會產(chǎn)生220種分組條件組合情況。如果我們希望能在運行時為任一可能的用戶查詢都匹配到最優(yōu)的離線樣本集，那么我們在預處理階段需要對每種可能的分組條件組合都預先保存一份分層抽樣樣本。即使每份樣本集的抽樣率僅為0.1%，那么總的預生成樣本集合的數(shù)據(jù)量大小也將會超過原始數(shù)據(jù)集的1 000倍。本文中，我們將考慮更為實際的應用場景，即用戶可提供的用于生成離線樣本集的存儲空間是有限的。因此，本文提出的抽樣系統(tǒng)的設計目標可具體定義為：針對某一特定的數(shù)據(jù)集，如何生成k份分層抽樣樣本集，使得在運行時能從k份樣本集中挑選出最合適的一份，從而期望能在所有可能的用戶分組查詢上的平均誤差達到最小值。

3 基于匹配度評估的分層抽樣策略

3.1 抽樣策略間的匹配度評估

上節(jié)中，我們已經(jīng)闡述了用戶發(fā)起的每一類分組聚合查詢都具有相對應且確定的最優(yōu)分層抽樣總樣本量分配方案這一理論基礎。并且，任意樣本集都能根據(jù)其在每個分層上保存的樣本點個數(shù)回溯到一個具體的分層抽樣總樣本量分配方案。那么，如果我們能夠為分層抽樣策略任意兩種總樣本量分配方案間提供一種匹配度評估的方法，我們就能將任意用戶查詢與樣本集之間的匹配度評估轉(zhuǎn)換為該用戶查詢對應的最優(yōu)抽樣策略與生成該樣本集的具體抽樣策略這兩種不同的分層抽樣總樣本量分配方案之間的匹配度評估。我們也就能將上節(jié)中提出的實際場景下的抽樣系統(tǒng)設計目標形式化地定義為一個優(yōu)化問題。該優(yōu)化問題的損失函數(shù)即為使用k份離線樣本集來應對所有可能的用戶分組查詢時將會產(chǎn)生的匹配度損失的總和。接下來，本節(jié)將先介紹任意分層抽樣總樣本量分配方案的形式化表示公式并進一步提出任意兩種抽樣策略間匹配度損失的形式化評估方法。

考慮某數(shù)據(jù)集D，可用作用戶查詢分組條件的類別分組屬性為A1,A2,…,Aα。其中，又有每個類別所對應的值域上取值的數(shù)量大小為N1,N2,…,Nα。那么用戶在該數(shù)據(jù)集上發(fā)起的分組聚合查詢所產(chǎn)生的最小分組單位g的總數(shù)量為N1×N2×…×Nα。例如，考慮包含某國人口調(diào)查數(shù)據(jù)的數(shù)據(jù)集，其中共有兩個分組屬性A1和A2，分組屬性A1為性別，分組屬性A2為學歷?？紤]每種分組屬性值域上取值的數(shù)量，分組屬性A1對應的取值可能為“男性”或“女性”，即N1為2，分組屬性A2對應的取值可能為“本科”、“碩士”或“博士”，即N2為3。那么，總共將產(chǎn)生6個最小分組單位gi(1≤i≤6)，分別為：g1:(“男性”，“本科”)、g2:(“男性”，“碩士”)、g3:(“男性”，“博士”)、g4:(“女性”，“本科”)、g5:(“女性”，“碩士”)、g6:(“女性”，“博士”)。

定義一種離散概率分布，其在任意最小分組單位g上的概率取值為p(g)，代表從生成的離線樣本集中任意取出一條記錄，該記錄屬于最小分組單位g的概率。那么有：

式中：S為總抽樣數(shù)量大小，Sg為總抽樣數(shù)量S分配到最小分組單位g上的抽樣數(shù)量大小，且∑p(g)=1。由此，我們可以將任意分層抽樣策略總樣本量分配方案轉(zhuǎn)化為離散概率分布的形式。至此，我們得以通過衡量兩個離散概率分布間差異的距離函數(shù)，正式定量地評估任一總樣本量分配方案與用戶分組聚合查詢確定下的最優(yōu)樣本量分配方案間的匹配度損失程度。本文選取Jensen-Shannon散度[8]來衡量兩種抽樣策略間的匹配度損失程度。對于在同一值域Y上的概率分布P和Q，Jensen-Shannon散度定義如下：

式中：M定義如下：

公式中的KL是Kullback-Leibler散度[9]，是一種可用來測量兩組概率分布間差異性的非對稱性指標，定義如下：

當兩個概率分布相同時JS取值為0，兩個概率分布間的匹配度損失越大，則JS取值也將會增大。

3.2 抽樣策略的設計與實現(xiàn)

式中：U代表在該數(shù)據(jù)集上用戶發(fā)起的分組聚合查詢中，所有可能的分組條件組合的集合。PU代表的是，依據(jù)Acharya證明的分層抽樣總樣本量分配方案理論[4]所得到的最優(yōu)抽樣策略對應的概率分布。

為了解決上述優(yōu)化問題，我們設計了一種自適應的優(yōu)化算法，該算法基于優(yōu)化問題中的一種經(jīng)典隨機爬山算法(Stochastic Hill Climbing)[10]。該算法的主要流程如算法1所示。

算法1生成包含k組概率分布的最優(yōu)解集

輸入:迭代次數(shù)閾值tIteration，優(yōu)化目標損失值閾值tError

輸出:包含k組概率分布的最優(yōu)解集：solutionSet

1: solutionSet←insertkinitial probability distributions

2:t:iteration times←0

3:whileLOSS(solutionSet)>tErrorANDt

4: Generate solutionSetNew based on solutionSet

5:ifLOSS(solutionSetNew)

6: solutionSet←solutionSetNew

7:endif

8:t←t+1

9:endwhile

10:returnsolutionSet

在算法1中，主要包含了如下三個關鍵步驟:

(1) 第1行。在算法的初始化階段，我們?yōu)閗組抽樣策略，即為其分別對應的k個概率分布選擇k組合適的初始解集。

(2) 第4～7行。每輪迭代產(chǎn)生一組新的解集，并重新評估新的解集在優(yōu)化目標查詢集合上的損失值。若新的解集相比于當前解集能夠使得系統(tǒng)總優(yōu)化目標的損失值降低，則保留新的解集作為當前解集，反之則丟棄。

(3) 第3行。當系統(tǒng)總優(yōu)化目標損失值低于閾值tError時，或當?shù)螖?shù)大于閾值tIteration時，終止算法。否則，重復執(zhí)行步驟(2)。

其中，損失函數(shù)定義如下：

對于步驟(1)，一個合適的初始解集可以幫助優(yōu)化算法更快地終止。雖然隨機均勻抽樣策略在面對用戶分組聚合查詢時不是最優(yōu)解，但其得到的樣本保留了數(shù)據(jù)集原始的數(shù)據(jù)分布特征，并且是應對非分組查詢時的最優(yōu)抽樣策略。因此，在沒有任何額外信息的情況下，為了避免生成更糟糕的初始解集，我們就將隨機均勻抽樣策略選做初始解集。對于步驟(2)，由于我們已經(jīng)明確定義了系統(tǒng)的總體優(yōu)化目標，因此可以直接使用總體目標的衡量公式來對生成的中間解進行效果評估。在生成新的解集時，每個分組增大或減小樣本空間的概率將反比于該分組的大小。這是由于近似結(jié)果的誤差更多來源于樣本量更小的分組，調(diào)整此類分組使得我們的算法更有可能更快地向接近總體優(yōu)化目標的方向移動。

本文所述系統(tǒng)將在離線狀態(tài)下，按照上文所描述的優(yōu)化算法，生成一組各自代表不同分層抽樣策略總樣本量分配方案的概率分布。在分布式數(shù)據(jù)倉庫Hive[11]上，本系統(tǒng)將按照概率分布中所指示的各最小分組單位g上的抽樣率在各個分組上進行隨機均勻抽樣，并將生成的樣本集保存在數(shù)據(jù)倉庫Hive中。與此同時，系統(tǒng)將會記錄下與當前系統(tǒng)中保存的每份離線樣本集一一對應的概率分布描述。這些概率分布所代表的各最小分組單位上的抽樣率信息將會在系統(tǒng)在線運行時被用來進行與當前用戶查詢進行匹配度評估，并且用來縮放在樣本集上得到的用戶查詢結(jié)果，以生成最終需要返回的近似用戶查詢結(jié)果。

3.3 系統(tǒng)運行時的樣本選擇與查詢重寫

至此，本系統(tǒng)在運行時仍有兩個問題需要解決：

(1) 當某個具體的用戶分組聚合查詢請求到來時，系統(tǒng)將如何從離線生成的多份樣本集中選取出最優(yōu)的一份樣本，進行近似結(jié)果計算。正如3.1節(jié)中所述，任意的分層抽樣總樣本量分配方案可以被轉(zhuǎn)化成一個概率分布。同時，對于每個到來的用戶查詢，我們都可以相應地通過考慮查詢中的分組條件來計算出最匹配該查詢的概率分布。由于我們在離線時保存了每份樣本集對應的概率分布信息，因此我們有理由從中選出一份與當前用戶查詢所對應的最優(yōu)概率分布匹配度最高的樣本集進行近似結(jié)果計算。唯一需要注意的是，系統(tǒng)在運行時使用的匹配度評估函數(shù)應當與系統(tǒng)在離線生成樣本集時，運行的優(yōu)化算法中所使用的匹配度評估函數(shù)保持一致。

(2) 由于本系統(tǒng)使用的是分層抽樣策略，并且對每個分組的抽樣率不同，是一種有偏的抽樣方法，因此，系統(tǒng)需要重寫用戶查詢以生成無偏的近似結(jié)果。在離線生成樣本時，當系統(tǒng)從不同分組中按照抽樣率隨機均勻抽取不同數(shù)量的樣本時，系統(tǒng)同時已經(jīng)為每條樣本記錄保存了一個縮放因子。由于同一分組中的所有樣本記錄對應著相同的抽樣率，因此同一分組中生成的樣本記錄將共享相同的縮放因子，即為該樣本記錄所歸屬的分組上的抽樣率的倒數(shù)。在運行時，本系統(tǒng)將利用這些縮放因子來對每條樣本記錄進行加權處理，以得到無偏近似結(jié)果。具體來說，對于求和操作(SUM)，近似結(jié)果將會是所有相關的樣本記錄與相應的縮放因子的乘積的和。對于計數(shù)操作(COUNT)，近似結(jié)果為所有相關的樣本記錄對應的縮放因子的和。相應地，求平均值操作(AVG)通過將SUM與COUNT的結(jié)果相除計算得出。

4 實 驗

4.1 實驗設置

本文的實驗環(huán)境為包含1個master節(jié)點和9個slave節(jié)點的Spark集群。每一臺機器分別搭載主頻為2.1 GHz的Intel Xeon E5-2600處理器和64 GB內(nèi)存，運行在64位Ubuntu 14.04 Server系統(tǒng)上。集群上運行Spark 2.0.0和Hive 1.2.1。

(1) 模擬數(shù)據(jù)集 我們在TPC-H數(shù)據(jù)庫基準測試數(shù)據(jù)集[12]上生成模擬數(shù)據(jù)集及測試查詢模板。在原始的TPC-H數(shù)據(jù)集中，分組的數(shù)量及各分組的大小分布都相對較為均勻。為了能更好地模擬出真實情況下的數(shù)據(jù)集，并且為了能夠更好地對比不同抽樣策略在應對更具挑戰(zhàn)的傾斜數(shù)據(jù)集時性能上的差異性，我們利用了一個經(jīng)過版本修改的dbgen工具[13]生成非均勻分布的數(shù)據(jù)集。該工具將根據(jù)Zipf分布生成傾斜數(shù)據(jù)。在本實驗中，Zipf分布的特征指數(shù)z被設置為1.5。我們選取了TPC-H數(shù)據(jù)集中的lineitem表，并將擴展因子設置為100，最終得到了總大小為74.7 GB的模擬數(shù)據(jù)集。在構造用于實驗測試用的模擬用戶分組聚合查詢時，我們通過隨機生成若干分組屬性并進行隨機組合的方式來生成模擬用戶分組聚合查詢，以達到模擬測試現(xiàn)實場景中抽樣系統(tǒng)應對Ad-Hoc查詢時表現(xiàn)出的性能效果。

(2) 真實數(shù)據(jù)集 我們從公開的斯隆數(shù)字巡天數(shù)據(jù)集SDSS網(wǎng)站[14]上下載了真實數(shù)據(jù)集和真實的用戶查詢記錄。我們從SDSS數(shù)據(jù)集的BestDr8版本中選用了PhotoPrimary視圖，獲取了總共101.45 GB的數(shù)據(jù)。下載到的用戶查詢記錄被進行了一定修改以使其符合Spark SQL的語法定義。

在整個實驗過程中，我們對比了隨機均勻抽樣策略、國會抽樣策略和本文提出的匹配度分層抽樣策略。每種策略都在離線時都生成了抽樣率為1%的樣本。對于匹配度分層抽樣策略，默認用戶設置的離線樣本集個數(shù)k為5。

4.2 模擬數(shù)據(jù)集上精確度的表現(xiàn)

實驗一中，我們在模擬數(shù)據(jù)集TPC-H上總共生成了30條隨機用戶查詢，并且對每條用戶查詢運行在三種不同的抽樣策略生成的樣本集上得到的近似結(jié)果的相對誤差做了統(tǒng)計。我們根據(jù)用戶查詢中分組條件屬性的個數(shù)將用戶查詢分為了五類，以便能夠更為細致地考察不同抽樣策略在分組條件數(shù)量不同的情況下的表現(xiàn)。在TPC-H模擬數(shù)據(jù)集上的實驗統(tǒng)計結(jié)果如圖1所示。

圖1 TPC-H數(shù)據(jù)集上三種抽樣策略的平均相對誤差

由圖1可知，當分組屬性個數(shù)為0時，代表當前測試用戶分組聚合查詢?yōu)椴话纸M條件的非分組查詢。由于隨機均勻抽樣策略完全保留了整個數(shù)據(jù)集上底層的數(shù)據(jù)分布特征，因此其在非分組用戶查詢下的表現(xiàn)自然會優(yōu)于分層抽樣策略。在國會抽樣策略中，由于抽樣策略更傾向于補償小的分組因此會破壞整個生成的樣本的均勻性，導致其在應對非分組查詢時效果不佳，相較均勻抽樣策略誤差率提高了39.4%。而在本文提出的匹配度抽樣策略中，由于非分組用戶查詢相較于其他分組用戶查詢的特殊性，其在系統(tǒng)的總優(yōu)化目標中往往會產(chǎn)生很大影響。因此，在最后生成的多份離線樣本集中將會有一份樣本傾向于對非分組用戶查詢更加友好，使得本系統(tǒng)在面對非分組用戶查詢時也能獲得較好的效果。相較于國會抽樣策略，針對非分組用戶查詢，本文提出的匹配度分層抽樣策略在平均相對誤差上降低了16.6%。

從圖中的統(tǒng)計結(jié)果可以看出，隨著分組屬性個數(shù)的增長，各系統(tǒng)產(chǎn)生的近似結(jié)果的誤差也在隨之增長。這是由于當分組屬性個數(shù)增加時，用戶查詢產(chǎn)生的結(jié)果中將包含更多的分組數(shù)量并且各分組中包含的記錄數(shù)量的大小分布也將變得更加不平衡。分層抽樣策略在應對這種條件下的用戶查詢時，效果要顯著好于隨機均勻抽樣策略。而由于本系統(tǒng)通過衡量不同分組查詢對應的最優(yōu)分層抽樣總樣本量分配方案，將匹配度較高的總樣本量分配方案進行聚合，因此可以通過離線保存為數(shù)不多的多份樣本集的方式，優(yōu)化絕大部分的分組查詢。實驗結(jié)果也表明，當用戶查詢中分組屬性個數(shù)增加時，本系統(tǒng)生成的近似查詢結(jié)果的誤差的增加呈現(xiàn)出放緩的趨勢。相比于國會抽樣，本文提出的匹配度分層抽樣策略在模擬數(shù)據(jù)集TPC-H上的平均相對誤差降低了25.4%。

4.3 真實數(shù)據(jù)集上精確度的表現(xiàn)

實驗二中，我們選取了SDSS真實數(shù)據(jù)集并下載了真實的用戶查詢。我們同樣對這些真實用戶查詢按照分組屬性個數(shù)進行了分類，實驗獲得的統(tǒng)計結(jié)果如圖2所示。

圖2 SDSS數(shù)據(jù)集上三種抽樣策略的平均相對誤差

在真實數(shù)據(jù)集上，三種抽樣策略的表現(xiàn)與我們在模擬數(shù)據(jù)集上得出的結(jié)果非常相似。對于非分組用戶查詢，相較于國會抽樣，本文提出的匹配度分層抽樣將近似結(jié)果的精確度提高了12.4%。相比于國會抽樣，本文提出的匹配度抽樣策略在真實數(shù)據(jù)集SDSS上的平均相對誤差降低了26.3%。

4.4 離線樣本集個數(shù)k的影響

實驗三在TPC-H模擬數(shù)據(jù)集上進一步考察了本文提出的匹配度分層抽樣系統(tǒng)中，用戶允許存儲的離線樣本集個數(shù)k對于近似結(jié)果精確度的影響。圖3展示了在不同的k值情況下，用戶查詢的平均相對誤差隨分組屬性個數(shù)的變化情況。從圖中可以看出，當k為1時，即系統(tǒng)僅能保存一份離線樣本時，本文系統(tǒng)產(chǎn)生的離線樣本集將接近于國會抽樣策略所生成的樣本集，誤差較大。而當k不為1時，即用戶允許系統(tǒng)保存多份離線樣本時，由于系統(tǒng)可以通過數(shù)據(jù)特征預存多份離線樣本并且在運行時選擇出一份最優(yōu)樣本進行近似結(jié)果計算，其產(chǎn)生的近似結(jié)果的精確度相較于僅保存一份離線樣本時有著明顯提升。另外，可以看到當k值為5時，系統(tǒng)已經(jīng)能夠達到一個較好的性能，說明本文提出的優(yōu)化算法能夠很好地將具有相似數(shù)據(jù)分布特征的多種用戶分組查詢經(jīng)優(yōu)化后聚合到一份離線樣本集中。因此僅僅用少量的離線樣本集就能在大量的用戶查詢上達到較為出色的抽樣效果。

圖3 離線樣本集個數(shù)k對用戶查詢平均誤差的影響

5 結(jié) 語

本文提出了一種基于用戶查詢與各分層間總樣本量分配方案匹配度評估的分層抽樣策略，系統(tǒng)在運行時可以從多份離線樣本中選出一份最匹配當前查詢的樣本進行近似結(jié)果計算。同時，本文還為任一分層抽樣策略與任意用戶分組聚合查詢的匹配度提供了一種基于概率分布和數(shù)據(jù)特征的形式化定量評估方法。通過在模擬數(shù)據(jù)集和真實數(shù)據(jù)集上的廣泛實驗，本文驗證了數(shù)據(jù)驅(qū)動的基于匹配度評估的分層抽樣策略相較于傳統(tǒng)抽樣策略在用戶查詢近似結(jié)果的精確度上有了明顯提升。