基于變分自編碼器的近似聚合查詢優化方法

黃龍森，房俊，周云亮，郭志城

(1.北方工業大學 信息學院，北京 100144；2.北方工業大學 大規模流數據集成與分析技術北京市重點實驗室，北京 100144)

近年來，大數據的快速增長和廣泛應用對查詢處理提出了巨大挑戰.在大規模數據集上執行聚合查詢是數據分析和決策制定的常見任務.近似查詢處理方法（approximate query processing,AQP）[1-2]通過使用抽樣、概率估計、統計技術等近似技術，可以快速地計算查詢的近似答案且提供一定的精度保證[3-4].

偏態數據分布是指在數據集中存在不平衡的數據分布情況，其中某些屬性的取值頻率遠高于其他屬性.該分布可能源于數據收集過程、自然數據特征或者是特定應用領域的限制等因素.采用近似查詢處理方法，往往無法有效處理這種偏態數據分布，導致查詢結果的準確度下降.分層抽樣方法被認為是解決偏態數據分布的有效方法.傳統做法通常是依據概率進行抽樣，但一次或幾次抽樣的隨機性無法保證所抽樣本的分布與原始偏態數據的分布相一致.采用多次迭代的抽樣方法可以減輕這一問題，但會帶來顯著的時間和空間成本.

機器學習驅動的AQP 算法主要關注于使用生成模型表達原數據集的概率密度分布，利用所得的概率密度函數，近似估計查詢結果.生成模型具有學習數據分布的潛在變量并快速生成符合該分布數據的特點[5-7]，在音頻、圖像和文字等領域中廣泛應用.近年來，生成模型也在近似查詢處理方法中用于生成符合原始數據分布的小樣本數據[8-9]，但如果直接將生成模型應用于偏態數據的學習生成，效果不理想.

本文提出結合分層分組抽樣和變分自編碼器生成模型的近似聚合查詢新方法（group variational auto-encoder,GVAE），通過數據預處理、分層分組、模型優化等手段，訓練優化的變分自編碼器模型.生成模型后設置采樣比例，輸入隨機噪聲到模型中，快速生成小批量樣本并執行聚合查詢.實驗表明，與基準方法相比，對偏態分布數據的近似聚合查詢有更小的查詢相對誤差.

1 相關工作

近似查詢處理這一領域的研究歷程總體上可以分為以下2 個階段.1）Olken 等[10]首次提出并實現了在關系型數據庫上使用采樣技術.此后，在隨機采樣的基礎上，分層抽樣和各種離線構建數據概要的方法被廣泛研究.在分布式系統被提出后，研究者們關注于如何在分布式場景下離線或在線采樣.2）在深度學習技術推動的 AI 浪潮下，研究者逐漸意識到機器學習模型對數據的強大擬合能力，基于生成模型的AQP 算法在這種背景下被提出.現行的AQP 算法主要包含在線算法、離線算法與機器學習算法3 種[11-12].在線 AQP 算法的主要目的是在查詢執行期間設計合理的采樣策略，基于在線采樣計算OLAP 的近似查詢結果，并為該近似查詢結果設計誤差估計算法[13-14].

基于離線算法的近似查詢處理方法主要通過分析歷史查詢日志和原數據集，對數據總體進行采樣或計算其關鍵統計信息，利用這些信息近似回答在線查詢[15-18].

基于機器學習的近似查詢處理算法分為以下2 類：1）使用神經網絡直接學習原始數據分布到生成數據分布的映射；2）利用生成模型學習原始數據分布的潛在特征，根據潛在特征對隨機變量的分布變換，生成與原始數據分布相似的數據樣本.變分自編碼器（variational auto-encoder,VAE）[19]和生成對抗網絡[20]（generative adversarial network,GAN）是生成模型中經典的2 類模型.VAE 模型學習數據的低維潛在特征（均值和方差），快速擬合數據分布并生成具有較高相似度的數據，提供用于聚合查詢的數據樣本.

Thirumuruganathan 等[21]提出使用變分自編碼器模型（VAE-AQP）對原始數據分布進行建模，生成高效、交互式的總體估計.VAE-AQP 存在處理偏態數據時相對誤差不夠精確的問題，難以擬合期望的數據分布，影響查詢準確率.

GAN 通過判別網絡和生成網絡相互對抗和學習的方法，降低生成樣本和原始數據之間的聚合查詢誤差.Zhang 等[22]介紹了基于條件生成模型的近似查詢處理方法，提出使用基于Wasserstein的條件生成對抗網絡（conditional -Wasserstein generative adversarial network,CWGAN）來有效地處理Group-by 查詢，在節省計算資源的同時保持較高的結果精度.GAN 在訓練過程中沒有明確的指標確定模型達到納什均衡，容易出現模型坍塌的問題.

2 基礎定義

2.1 聚合查詢

討論如下所示的查詢語句：

其中，T為數據集，T={X1,X2,···,Xn}.每個屬性 Xi都可以用作查詢中的條件和 COND中的屬性，也可以用作分組聚合的屬性.WHERE 和 G ROUP BY子句都是可選的，G是分組查詢中的指定分組列名.COND可以是多個條件同時判斷，每個條件都可以是 Xiop CONST形式的任何關系表達式，其中Xi是一個屬性，op∈{=,＜,＞,≤,≥}，CONST是指判斷條件的具體數值.AGGR是在AQP 相關研究中廣泛 研究的COUNT、AVG、SUM 聚合函數.

2.2 偏態系數

偏態(skewness)是指對數據分布對稱性的測度[23].偏態分布(skewness distribution)指頻數分布的高峰位于一側，尾部向另一側延伸的分布.它分為正偏態和負偏態，正偏態和負偏態由偏態系數來決定，若偏態系數大于0，則該分布為正偏態，反之為負偏態，如圖1 所示.

圖1 左偏分布、右偏分布與正態分布的比較Fig.1 Comparison of left-skewed and right-skewed distribution with normal distribution

一般可以用偏態系數（coefficient of skewness,SK）刻畫偏態程度，計算方法如下所示：

式中：Xi為第 i個數據點，X為樣本均值，S為樣本標準差，n為數據的樣本大小.|SK|∈(0,0.5)為輕度偏態分布，|SK|∈(0.5,1.0)為中度偏態分布，|SK|∈(1.0,+∞)為高度偏態分布.

2.3 聚合查詢誤差

聚合查詢誤差由相對誤差（relative error difference）來計算，記為 Rq.設聚合查詢語句 q 的查詢結果真值為 θ，AQP 查詢估計值為 θ?，則相對誤差的計算如下：

設通過分組聚合查詢語句 q給出一個組 G，G={g1,g2,···,gn}為分組結果的不同組別.其中，AQP 聚合查詢結果組別可能不包含在 G中.設真實數據的組別為 {g1,g2,···,gn},gi∈G，對應組的真實數據查詢結果集合為 θ={θ1,θ2,···,θn}，AQP查詢估計值當m＞r時有真實數據不存在的組別，不具有統計價值，因此不作考慮.缺失的分組項設置為100%.計算平均相對誤差如下所示：

2.4 不同偏態系數聚合查詢的相對誤差

以PM2.5 數據集①http://archive.ics.uci.edu/ml/datasets/Beijing+PM2.5+Data.為例，給出2010～2014 年的氣象環境數據，部分數據如表1 所示.表中，ρB為PM2.5 的質量濃度，CBWD 為風向，IWS 為累計風速.

表1 PM2.5 數據集的示例Tab.1 Example of PM2.5 dataset

利用CWGAN 和VAE-AQP 學習原數據分布生成的模型，對不同 Field 字段分組聚合查詢，相對誤差如表2 所示.

表2 不同模型下不同數據偏態系數的相對誤差Tab.2 Relative errors of bias coefficients for different data under different models

3 GVAE 方法

該GVAE 方法的處理過程如圖2 所示，主要包括數據預處理、模型訓練、數據生成、聚合查詢4 個步驟.

圖2 GVAE 方法的流程圖Fig.2 Flowchart of GVAE method

數據預處理是將數據集數據轉換為可以被神經網絡學習的數據，共分為數據編碼、數據標準化和數據分層分組3 部分.其中數據編碼將類別少的數據轉換為數值，便于GVAE 模型計算.數據標準化可以在保留數據分布特征的前提下消除不同數據之間的量綱差異，便于神經網絡梯度迅速下降，快速收斂.

數據分層分組是為了學習不同列的偏態分布并生成小樣本數據，其中分組是為了使變分自編碼器學習和生成小批量數據，而分層的目的是使每一組的數據分布都與原偏態數據的分布相似.

GVAE 模型訓練是將已經預處理好的數據輸入到神經網絡中學習，得到模型庫后，根據不同的聚合查詢語句從模型庫中選取模型，根據一定的樣本比例生成數據，對樣本執行聚合查詢.3.2～3.4 節將進一步描述上述內容.

3.1 數據預處理

對數據進行預處理，包括數據的編碼、標準化和分層分組3 部分，如圖2 的數據預處理部分所示.

3.1.1 數據編碼 機器學習中常用的編碼為二進制編碼和獨熱編碼（one-hot encoding），例如將數值 [1,2,3,4]編碼為 [0001,0010,0100,1000]，可以看出編碼位數和數值種類數成正比.機器學習過程中每一批的數據維度需要增加，加大了學習訓練時間的開銷.

本文使用的是標簽編碼（label encoder）[24].標簽編碼是根據字符串形式的特征值在特征序列中的位置，為其指定一個數字標簽.針對有不同數據類型的數據，需要對其格式進行轉換.對每一列數據統計分類和類型個數.分別對每一類標號，將真實值替換為標號值.

需要轉換為編碼的數據類型為類別和數值2 類.如表1 所示，字段 CBWD的數據類型為類別類型，為了適應神經網絡學習，必須對數據進行編碼.其中字段CBWD共有4種取值：[SE,NE,SW,CV]，編碼后為 [1,2,3,4]；字段 Year共5 種取值：2010～2014，因其數值大且類別少，3.1.2 節中的標準化過程計算更復雜，需要將其編碼，減小計算難度.

3.1.2 數據標準化 在機器學習算法中，數據標準化和歸一化是2 種常見的特征縮放（feature scaling）方法.其中歸一化指的是將數據的每一列的值縮放至0～1.0.對于偏態分布數據，在縮放過程中會導致分布特征消失，因此不選擇使用歸一化.

通過數據標準化，可以縮小數據的取值范圍，不會丟失原始數據分布的特征，也可以將數據轉換為近似的標準高斯分布，便于GVAE 模型學習數據分布.標準化過程如下所示：

式中：X為多維的數據向量，Xij為X 中第i 行第j 列數據；μj為數據第j 列的均值，σj為數據第j 列的標準差.通過將數據向量減去均值向量，再除以標準差向量，可以實現多維數據的標準化處理.計算每一列數據的均值和方差，將數據標準化，理論上數據是多少維，均值和方差也是相同的維度.將均值和方差向量保存，用于生成數據后的逆標準化.

3.1.3 分層分組 分層分組算法如算法1 所示，為了便于GVAE 一次性擬合每一組的分布，參考經典VAE 學習圖片數據的方法，將數據展開為一維向量，加速GVAE 學習的速度，擬合更準確.

根據算法1，對表1 所示的數據集進行訓練.設置每一組樣本的數據規模為1 000，記為基數.將4 000 條數據對應分為4 組，聚合查詢語句如式（1）所示，保持GVAE 模型網絡結構和采樣比例不變，統計平均訓練時間和查詢準確率，如表3所示.表中，Ng為每一組的數量，Tavg為訓練時間，Acc為近似查詢準確率.當數據規模為10 000～100 000 時，以1 000 為基數分組，兼顧了訓練時間和查詢準確率，若數據規模更大，則可以考慮根據數據量設置更大的基數.

表3 分組基數的比較Tab.3 Comparison of subgroup bases

不同分組方法對學習效率的影響，比較區間分組和分層分組方法，數據集分為樣本大小相同的若干組.任意重復選取2 組數據，計算總體數據和單列數據（CBWD）的均值（mean）、方差（Std）和KL 散度（KL）平均值，2 種分組方法的比較結果如表4 所示.

表4 區間分組樣本分布的比較Tab.4 Comparison of sample distribution for interval grouping

分層分組算法是在對數據分組之前先對數據分層，根據不同的聚合查詢語句 Aggr的數據類別數量，計算每個類別占總數據的比例，根據每層的比例對數據分組.若 G有多個字段，則執行多次分層抽樣，使得分組后的數據分布與多個字段的原數據分布相似.根據離散數據和連續數據的分組方式不同，離線數據可以以直接分層的方法實現；連續數據考慮先聚類為幾個層級，再進行分層抽樣.對于連續數據，會產生更多誤差，若不考慮時間開銷，則可以考慮將數據排序后等距分組，以高時間復雜度的代價換取低誤差.

分層分組算法帶來了更多的時間和空間開銷.假設總體大小為 N，分為 n 個層級，每個層級的大小分別為 N1,N2,···,Nn.指定每組樣本大小為M，假設每個層級的抽樣比例為 p1,p2,···,pn，滿足 M=N1p1+N2p2+...+Nnpn.將一列數據分為 n個層級的時間復雜度為 O(N)，空間復雜度為 O(n)，存儲層級信息.從數據中反復抽樣 m組，m=N/M，每一層抽樣時間的復雜度為 O(Nipi)，因此抽樣需要 O(m(N1p1+N2p2+...+Nnpn))=O(mM)=O(N)的時間復雜度，存儲分組數據也需要 O(N)的存儲開銷.時間復雜度為 O(2N)=O(N)，空間復雜度為O(N)+O(n)=O(N).

每一組數據是從原始數據依據聚合查詢語句的字段分層隨機抽樣得到，字段不同，分組分層抽樣的方式不同，分組數據也不同.不同的查詢字段對應不同的模型.有相同G 的查詢字段可以使用對應查詢字段的查詢語句訓練得到的模型.

3.2 GVAE 模型訓練

針對本文關注的問題，GVAE 與經典VAE 模型相比，主要在神經網絡結構和損失函數2 個方面進行了改進.

3.2.1 神經網絡模型 變分自編碼器是一類生成模型，它可以學習復雜的數據分布并生成樣本.VAE 的訓練效率高，具有可解釋的潛在空間.

生層模型中的潛在變量是捕獲用于生成建模的數據特征的中間數據表示.設 X是希望建模的數據，z是潛在變量，P(X)為由屬性 A1,···,Am組成的潛在關系的概率分布，P(z)為潛在變量的概率分布，則 P(X|z)是 給定潛在變量的生成數據的分布.

將式（5）代入式（6），式（6）也被稱為變分目標(variational objective)，此時可以將 P(X|z)和 Q(z|X)相關聯，即用 Q(z|X)來替代 P(z|X)，推斷出 P(X|z).式（6）的第1 項為重構損失，第2 項為KL 散度.

神經網絡結構如圖3 所示，編碼器將輸入數據 X映射到潛在空間，解碼器將潛在向量 z 映射回原始數據空間，通過學習數據的潛在特征 μ 和 σ并生成新數據樣本 X′.GVAE 模型的編碼器和解碼器分別為3 個全連接層，深度為3 時可以兼顧學習效率和查詢準確率.

圖3 變分自編碼器的神經網絡結構Fig.3 Neural network structure of variational auto-encoder

經典VAE 模型中，圖片像素歸一化后為(0,1.0)，因此需要在解碼器部分加上Sigmoid 函數，將生成值的取值范圍限制為 (0,1.0).對于一般數據，取值范圍不定，根據3.1.2 節所示的方法將數據標準化后，取值范圍不限定在 (0,1.0)，因此需要去掉Sigmoid 函數.

神經網絡的其他部分設置如下：學習率為1×10-5，模型優化器為AdamOptimizer，激活函數為Relu，神經元數設置為40 和2，重構損失函數為均方誤差.神經元數對生成的數據和查詢準確率無明顯影響，但神經元數過多會增加不必要的訓練時間開銷，神經元數過少則不利于梯度下降和損失函數收斂.

3.2.2 損失函數 經典VAE 的損失函數由重構損失和KL 損失2 部分構成，如式（7）所示.在模型訓練的過程中，由于不同批數據分布相似但不完全相同，容易導致VAE 后驗崩塌（posterior collapse）的問題，即散度消失，重構部分過早達到ELBO 上界.

針對該問題，參考文獻[25]，給KL 項乘上權重系數 kl_coef，從0 到1.0 逐漸增大，并乘上放大倍數 m，此處設置 m=10.如此可以使得梯度下降速度放緩，留出部分下降空間給重構損失.經過實驗測試，改進后的訓練擬合效果更好，查詢準確率更優.

3.3 數據生成

GVAE 通過多個全連接層層學習數據的隱含變量得到模型，讀取模型網絡的變量.將標準高斯分布變量 z輸入到模型中，擬合原數據分布數據，生成數據的樣例如下所示：

這是符合標準高斯分布的2×4 的隨機數字矩陣 z.根據3.1.3 節的數據分組所示，矩陣行數為2 表示2 組，即生成2 ×1 000 條數據，列數為4 表示生成數 據的維度.

3.4 聚合查詢

根據不同查詢字段訓練模型后，通過聚合查詢語句的查詢字段，從模型庫中選取對應查詢類的模型.根據適當的采樣比例，生成小批量數據，對數據進行逆變換，并保存到數據庫中，最后查詢數據，計算查詢相對誤差.聚合查詢過程如算法 2 所示.

4 實驗與分析

4.1 實驗設置

實驗環境為Intel(R)Core(TM)i7-7700HQ CPU；16 GB 內存；500 GB 硬盤；操作系統為Windows 10；采用Visual Studio Code 2019 編輯器和Python 3.10 語言版本，使用Pytorch 實現生成模型的搭建.

1)實驗數據集.選用2 個數據集進行實驗，分別為 Beijing PM2.5 真實數據集和TPC-H 合成數據集.

a)Beijing PM2.5 數據集.該數據集包含了美國駐北京大使館的PM2.5 數據的信息和北京首都國際機場的氣象數據.數據集包括年月日、PM2.5、氣溫、壓強和風向等字段，字段類型多樣.共43 824 條數據.控制不同列的偏態系數為0～1.0，間距為0.2，總共5 份數據集.

b)TPC-H 數據集.獲取TPC-H 數據生成工具，通過調整參數和比例，設置偏態系數為0～1.0，間距為0.2，生成5 份合成數據集.每份數據集包括多個表，如訂單（orders）和供應商（supplier）.每個表包含特定字段，模擬真實世界的企業數據倉庫.每一份合成數據集都是500 萬條，支持多種分組聚合查詢.

2)查詢語句.針對不同數據集的不同字段，執行分組聚合查詢和條件查詢語句，如下所示.

a)Beijing PM2.5 數據集

其中，CONST為判斷條件的具體數值.

3)評估指標.對實驗數據集進行測試，主要考慮訓練時間和查詢準確率.查詢準確率使用如式（3）所示的相對誤差進行計算.

4)實驗過程.

a)數據分布擬合效果的實驗.

通過計算真實數據和生成數據的累積分布函數（CDF），觀察模型擬合數據分布的效果.

b)不同模型方法的比較.

為了更好地體現GVAE 對偏態數近似聚合查詢的優越性，選擇VAE-AQP 和CWGAN 模型方法與GVAE 進行比較，對比不同模型方法在同偏態系數下的查詢相對誤差.

c)消融實驗.

以GVAE 模型方法為基礎，將選擇編碼方式為標簽編碼還是獨熱編碼、標準化或者歸一化對聚合查詢準確率的影響，分別記為GVAE(E)和GVAE(O)、GVAE(S)和GVAE(N).

將是否增加GVAE 模型中改進的兩部分，Sigmoid 層和KL 損失改進，分別記為GVAE(M)和GVAE(KL)，開展消融實驗，能夠更好地體現該算法對偏態數據近似聚合查詢的優越性.

d)其他實驗.

測試其他變量，如不同維度或不同采樣比例對聚合查詢相對誤差的影響.

4.2 實驗結果與分析

4.2.1 數據分布擬合效果實驗 為了度量原始數據分布和生成數據分布之間的相似性，選用連續列的kolmogorov-smirnov（KS）統計量[26]來評估，如下所示：

式中：F1和 F2分別為原數據和生成數據的概率分布函數（CDF），sup為上確界.基于KS 統計量，比較生成數據與真實數據的CDF.如圖4 所示為真實數據集G 和合成數據集R 的GVAE 方法生成數據分布與原始數據分布的CDF 曲線.圖中，X 為數據標準化后的取值，Y 為對應取值的概率累積值.

圖4 不同數據集的CDFFig.4 CDF for different datasets

圖4(a)、(b)的 KS統計量分別為0.04 和0.03，這表示真實數據和生成數據CDF 之間的最大差異小，說明2 個分布之間的相似程度很高.

4.2.2 不同模型方法的比較 根據4.1 節的查詢語句，多次查詢真實數據和生成數據，計算不同的評估指標.

如圖5(a)、(b)所示為PM2.5 數據集和TPCH 數據集，分別統計在不同偏態系數的不同規模的數據集，近似聚合查詢的相對誤差平均值.對比GVAE、VAE-AQP 和CGWAN 模型方法，針對不同偏態系數的數據，近似聚合查詢有更小的查詢相對誤差，且隨著偏態系數的提高，相對誤差增大的幅度不超過2%，上升趨勢更平緩，查詢結果的相對誤差偏移更小.

圖5 不同偏態系數查詢的相對誤差Fig.5 Relative errors for queries with different bias coefficients

4.2.3 消融實驗 如圖6(a)、(b)所示，分別測試PM2.5 數據集和TPC-H 數據集對不同條件下的GVAE 模型計算不同偏態系數下的數據聚合查詢誤差，如4.1 節的消融實驗所示設置變量，可以看出不同變量對聚合查詢相對誤差的影響.

圖6 不同數據集和偏態系數的消融實驗Fig.6 Ablation experiment with different dataset and skewed coefficient

在相同消融條件下，GVAE(N)的查詢相對誤差比GVAE(S)高3%～5%，影響明顯.

4.2.4 其他實驗 如圖7(a)所示，在數據維度T ＞6的情況下，GVAE 模型方法能夠保持較小的相對誤差，CWGAN 和VAE-AQP 的相對誤差比GVAE 高.GVAE 與這2 種模型方法相比，隨著數據維度的增加，查詢時間和查詢準確率都有明顯優勢.GVAE 有確定的學習下界ELBO，便于衡量是否停止訓練.CWGAN 無法衡量何時達到納什均衡并停止訓練.VAE-AQP 相對于CWGAN 有更小的相對誤差，但如圖7(b)所示，在相對誤差相近的前提下，CWGAN 和VAE-AQP 的訓練時間比GVAE 長.這是因為在預處理階段已經將偏態數據處理為更適合模型學習的數據，每一組數據的分布相似，學習時的誤差下降更快，訓練時間更短.

圖7 不同維度下的模型比較Fig.7 Model comparison in different dimensions

如圖8 所示，對于不同規模的數據集PM2.5和TPC-H，Q1、Q2、Q3分別為4.1 節查詢語句b)中的第4、5、6 條查詢語句.在GVAE 方法中其他參數不變的情況下，Rq與采樣比例（sampling rate,SR）沒有明顯關系.查詢的誤差會小幅度波動，波動幅度小于0.5%.

圖8 不同采樣比例的相對誤差Fig.8 Relative error of different sampling rate

當模型生成數據時，只能生成分組基數的整數倍，提高抽樣比例只會增加生成數據的組數，生成數據分布幾乎不變，所以相對誤差不會大幅波動.

5 結 語

本文提出基于變分自編碼器的數據近似查詢處理優化方法，在數據預處理階段通過數據編碼和數據標準化，根據不同字段將偏態數據分層分組，便于GVAE 方法更好地訓練擬合的數據分布.加入了對損失函數的優化，避免過擬合.實驗結果表明，與對比算法相比，該方法對偏態分布數據的聚合查詢有更低的查詢誤差.

利用GVAE 方法學習偏態數據分布迅速，損失函數很快就收斂到一個定值，難以衡量是否訓練完成.下一步將深入研究為何導致其快速收斂，尋找新的衡量指標判斷訓練是否結束.