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

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

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

0 引 言

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

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

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

1 相關工作

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

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

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

2 問題歸納

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

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

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

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

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

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

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

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

式中：M定義如下：

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

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

3.2 抽樣策略的設計與實現

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

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

算法1生成包含k組概率分布的最優解集

輸入:迭代次數閾值tIteration，優化目標損失值閾值tError

輸出:包含k組概率分布的最優解集：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行。在算法的初始化階段，我們為k組抽樣策略，即為其分別對應的k個概率分布選擇k組合適的初始解集。

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

(3) 第3行。當系統總優化目標損失值低于閾值tError時，或當迭代次數大于閾值tIteration時，終止算法。否則，重復執行步驟(2)。

其中，損失函數定義如下：

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

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

3.3 系統運行時的樣本選擇與查詢重寫

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

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

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

4 實 驗

4.1 實驗設置

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

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

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

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

4.2 模擬數據集上精確度的表現

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

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

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

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

4.3 真實數據集上精確度的表現

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

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

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

4.4 離線樣本集個數k的影響

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

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

5 結 語

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