基于birch聚類的可更新機器學習索引模型

曹衛東，金 超

(中國民航大學 計算機科學與技術學院，天津 300300)

0 引 言

索引作為如今數據庫系統中用于數據存儲的重要技術之一，直接影響到了數據庫系統的存取性能。幾十年來，研究人員致力于研究出輕量、高效的索引結構：部分學者通過優化B樹索引結構和嘗試索引壓縮算法[1]來更好地發揮包括CPU緩存等在內的硬件優勢，例如A-樹[2]在葉子節點中使用了線性模型。

傳統數據庫索引為了追求泛用性，通常只通過數據結構進行優化，欠缺對數據集模式和分布規律的考慮[3]。Google團隊Kraska等[4]將機器學習引入索引結構設計，并提出了learned index。這種索引結構可以學習數據集分布情況，生成適配度較高的專用索引結構，顯著提升大數據檢索效率[5]。

Michael Mitzenmacher將神經網絡運用在數據庫索引布隆過濾器上[6]，Harrie Oosterhuis等研究了機器學習索引在索引壓縮上的潛力[7]，HaiXin Wang等嘗試用機器學習化的索引結構檢索高維數據[8]，混合專家網絡[9]等技術也被引入相關研究。但是索引更新的問題沒有得到解決，針對這一缺陷，JiaLin Ding等[10]提出了ALEX，對葉節點進行了重新設計，使用就地插入策略解決了之前learned index只能在只讀場景下進行的問題。并發數據結構XIndex索引[11]采取的解決方案是設置緩沖區進行插入。FITling-tree[12]為每個段內部預留緩沖區實現更新。PGM-index[13]從索引壓縮等多個方面優化了FITing-Tree。但是大多數相關研究選擇采用learned index提出的遞歸模型Recursive Model Indexes(RMI)結構框架或類似RMI結構框架，并沒有解決RMI中數據固定劃分導致擬合效果不佳和訓練時間長的問題。

本文面向海量數據高檢索需求，提出了ULIB (upda-table learning index structure based on birch clustering)。該模型采用了類樹的結構設計，首先對數據集使用birch聚類算法來實現數據的初步劃分，引入Calinski-Harabasz(CH)函數作為評價指標判斷聚類有效性；然后在訓練階段，采用前饋神經網絡進行分段學習，同時將數據訪問模式引入損失函數設計提高預測精度。最后，在數據更新過程中使用基于日志結構合并(log-structured merge，LSM)樹的異地插入策略解決更新問題。

1 機器學習索引

1.1 機器學習索引模型及相關問題

機器學習索引模型使用索引列的所有鍵值作為訓練集進行訓練，待檢索數據鍵作為輸入，鍵值所在的位置作為輸出。訓練結束得到的模型會生成真實值的偏移量，并存儲整個數據集中最大的向下和向上偏移量(稱作誤差范圍)。如圖1所示，B樹等同于機器學習，同樣可以看成一個根據鍵值預測數據所在位置的模型。

圖1 B樹與機器學習索引結構

當機器學習索引模型中一個檢索請求生成后，模型根據輸入的鍵值輸出這個鍵對應數據項的預測位置，類似B樹中的頁面設置，數據檢索保證了在預測位置最大的上下誤差范圍內一定能搜索到待檢索的數據項。雖然在索引設計方案中使用一個全連接神經網絡就可以擬合數據的整體分布，但是由于索引對于預測精度的要求較高，訓練階段需要大量的時間和空間去降低極小的誤差，即在單個數據實例級別上進行精確定位十分困難[14]，這個問題被稱作是“最后一公里”問題。

可以說，機器學習索引設計的關鍵就是如何解決初始數據劃分問題、數據劃分后的“最后一公里”問題和索引更新問題。

1.2 learned index的解決方案

learned index提供的解決方案是RMI，其結構如圖2所示。

圖2 RMI模型結構

其中，RMI頂層使用神經網絡來實現數據分發，在第二層使用線性回歸算法來實現各數據段的擬合，除第一層外，每一層分布情況由上一層模型的輸出決定，遞歸執行直至最后一層，在誤差區間使用二分查找來找到待檢索鍵的最終位置。

learned index相比較B樹，在查詢時間復雜度方面，可以由B樹的O(logN)降低至O(1)，同時也可以顯著減少空間占用，空間復雜度從B樹O(N)降低至O(1)。

learned index存在的問題為：使用復雜的遞歸層次結構帶來的模型訓練時間長的問題；采取均等劃分策略進行數據劃分，葉子節點使用線性回歸模型進行擬合解決“最后一公里”問題，擬合效果很大程度上由數據劃分階段所劃分出的各個數據區域自身分布決定，性能存在優化空間；每次數據更新后需要完整重新訓練數據集，即沒有解決索引更新的問題。

2 可更新機器學習索引模型ULIB

針對大數據時代海量數據高檢索需求，提出基于birch聚類的高效可更新機器學習索引模型ULIB。

2.1 ULIB模型結構

ULIB模型結構如圖3所示，模型一共分為4個階段：

圖3 ULIB模型結構

(1)數據劃分，利用birch算法將數據集劃分為D1到Dk，由于在神經網絡中訓練時間并不隨數據集規模增長而線性增加，而是更高程度增長，所以劃分數據集的操作可以獲得更短的訓練時間；

(2)基于神經網絡的葉子結點訓練，針對數據劃分后的k個數據區域，分別構建同樣數量的神經網絡模型進行訓練，以解決“最后一公里”問題。

(3)數據檢索，當查詢數據時，模型選擇器首先檢查待查詢鍵是否存在于緩存中，若不在則確定出待查詢鍵所對應的模型和鍵所在位置的預測y，最后自預測位置y按照最大最小誤差利用二分查找展開搜索，直至找到最終的數據精確位置。

(4)數據更新，當數據插入時，模型會在內存中開辟一個緩存區域存儲待插入數據，當緩存溢出時，將緩存中所有數據插入到對應學習模型中，并重新訓練對應模型。

2.2 基于birch聚類的數據劃分

2.2.1 birch聚類及有效性判定

birch算法是一種自底向上的層次聚類算法，核心為聚類特征CF和聚類特征樹CFtree。

相比較k-means，birch聚類無需定義聚類特征數k，且能以很高的效率更新[15]。CFtree包含3個關鍵閾值數，每個內部節點的最大CF閾值數B、葉節點最大CF閾值數L和子簇最大半徑閾值T，這3個數值直接決定了CFtree的最終形態和聚類類別數。

一般來說，在沒有數據集類別的先驗知識時，需要確定出合適的B、L和T來使聚類效果盡可能好。研究者提出了“最優聚類質量判定原則”，即通過組內元素之間距離和組件元素距離兩個方面來判定聚類效果優劣。并依據此原則提出了多個判別函數：DB函數、DI函數和CH函數，本文選取公認判定效果最佳的CH函數

(1)

如式(1)，k代表聚類類別數，n代表數據集元素個數

(2)

如式(2)，traceB等于組和組之間離差矩陣的跡，nj等于第j個組中存在的元素的數目，u為數據集所有元素的均值，uj是第j個組中所有元素的均值

(3)

如式(3)，traceW表示組內元素之間的離差矩陣的跡，xi代表第i個組內元素。一般來說，聚類效果優秀代表的是組與組之間的距離大，而組內的元素距離小。也就是說，聚類質量越好，CH值越大。

2.2.2 數據劃分流程

在機器學習索引模型中使用birch聚類算法進行數據劃分可以根據數據集分布情況生成內部分布更加統一的不同數據區域，進而提升模型預測精度。

ULIB數據劃分流程如圖4所示，選擇數據開始訓練過程后，讀入數據樣本，使用默認B、L值進行birch聚類，進行閾值判定后更新CFtree，之后依次輸入不同的B、L值組合，CFtree在不斷地迭代中進行更新，直至算法收斂結束聚類并記錄對應CH值用于后續對比。

圖4 基于birch的數據劃分流程

2.3 葉子節點訓練

2.3.1 神經網絡結構

ULIB設計的子模型神經網絡結構如圖5所示。

圖5 神經網絡設置

具體訓練流程為：

每個模型接收數據對應類別列向量輸入X=[x1，x2，…，xd]T通過式(4)產生凈輸出a[1]，其中b為偏置，行向量W[1]為權重向量

a[1]=W[1]X+b

(4)

凈輸入a[1]通過Relu激活函數做實現非線性變換，如式(5)。得到輸入為X時該神經元的活性值a[2]

a[2]=ρ(a[1])=max(a[1]，0)

(5)

如式(6)所示，輸出預測值y

y=ρ(W[2]a[2]+b2)

(6)

2.3.2 子模型設置及損失函數優化

ULIB其中一個子模型k訓練過程如圖6所示，在訓練階段，ULIB會根據birch聚類階段產生的k個數據區域分別構造k個模型，其中各個模型為兩層神經網絡，輸入為待檢索數據的鍵，輸出為預測的位置，使用神經網絡進行葉子節點訓練可以適應各種場景下的非線性擬合需求，提升預測精度。

圖6 子模型結構

為了實現進一步提升模型性能，將數據訪問熱度融入到損失函數構造中，即針對熱點訪問的數據，模型訓練過程中會增加其權重，宏觀上彌補了緩沖區帶來的性能損耗。

更新損失函數如式(7)，其中，x為輸入數據的主鍵，y為輸入數據項對應的位置，f1(x)到fk(x)代表第1個到第k個訓練模型，λx代表數據項x的訪問熱度信息，這個值由實際生活中對于x的訪問次數決定，針對不同的數據項i會有不同的λx值。優化目標是最小化損失函數

(7)

2.4 基于LSM的索引更新

模型訓練得出的數據區域設為D1到Dk，訓練模型fi(x)對應的數據區域是Di。當一個待檢索數據x輸入后，輸出的y就是模型計算出的x對應的數據區域Di中的預測的位置。計算x對應的存儲真實位置是D1到Di-1的所有數據區域的數據量的累計值加上預測位置y，也就是說，只需要記錄下各個數據區域的數據量，即可通過計算確定x對應的訓練模型，而且插入操作完成后，只對x對應的數據區域Di中的數據量和數據分布產生影響，訓練時也只需要重新訓練Di，其它數據區域不需要進行重訓練，依舊可以通過對應的f(x)計算出待檢索鍵的相對位置y，之后累加位于這個數據區域之前的所有數據區域數據累計量的大小得到待檢索鍵的真正的位置，模型間實現了互不干擾。

但是當插入條目較多時，每次插入都要對對應數據區域進行重訓練依然會給模型帶來不小的開銷，進而影響模型性能。基于日志結構的LSM樹，是一種寫優化的數據組織方式，其核心思想包括延遲更新，核心為延遲批處理索引變更請求，采用類似歸并排序的方式串聯所有的變更信息，最后統一將變更遷移至磁盤[16]。

為此，如圖7所示，模型借鑒了LSM樹的延遲更新思路。在插入過程開始后，首先在內存中劃分一塊新的緩存，并將其分為k個緩存塊，分別對應k個數據區域。當一條待插入數據請求生成后，模型首先根據待插入數據的輸入值x計算確定其對應存儲數據區域Di，然后將這條數據存儲到被劃分號的第i個緩存塊中以B樹形式存儲，只有當這個緩存塊達到閾值溢出以后，才將其中的數據歸并到實際的數據區域，并重新訓練。至此完成一次插入操作。使用這樣的異地插入不僅能夠分攤數據移位代價，還能分攤模型重訓練代價。

圖7 索引更新

2.5 數據檢索過程

當各個神經網絡模型訓練完成以后，都會相應生成一個適配各個模型的最大檢索誤差值。而且每一個模型對應的數據區域都存在一個存儲范圍，這個范圍決定了檢索時待檢索鍵對應哪個模型。

在檢索階段，模型首先根據輸入的待檢索鍵x的大小來確定其范圍，進而根據范圍確定x對應的索引模型fi(x)，首先在fi(x)對應的劃分緩沖區中第i個緩存塊中進行查找，檢查x是否作為臨時數據存放在內存中，若不在，則根據fi(x)計算出x在這個模型中存儲的預測位置y，并根據生成的error序列找到對應的最大誤差，最后通過二分查找算法在預測位置y的最大誤差區間內查找精確位置，完成檢索操作。

3 實驗結果與分析

3.1 實驗數據及設置

實驗使用數據集為亞馬遜書籍排名數據集和Weblogs數據集，以連續取樣的方式各采樣了約300萬條不重復的數據。其中：書籍排名數據集是來自亞馬遜發布的書籍各個時間段銷售排名情況；weblog數據集采集了服務器端訪問日志記錄。兩個數據集都選擇時間戳作為訓練用主鍵。

本文的實驗硬件環境為：CPU為2.7 GHz的6核，內存為60 G；硬盤容量為1 TB。訓練使用的為一塊8 G GTX 1080 GPU。軟件環境：使用操作系統為 Windows10 x64；Python版本為Python 3.6；基于版本號為1.13.2的 TensorFlow實現機器學習部分。

實驗對比模型設置：

ULIB：設置為兩層架構，模型輸入為待檢索數據的鍵，輸出為鍵所預測的位置，隱藏層神經元設置為32個，激活函數為Relu；

learned index：設置為兩層的遞歸回歸模型RMI，第一層使用神經網絡結構，隱藏層設置為16*16個神經元，激活函數為ReLu。輸出層設置為100個線性回歸模型；

B+樹：設置頁面大小為256，緩存為64 K；

ALEX：使用自適應RMI模型，并在各個葉子節點加入空隙數組，大小為4倍鍵值數目。

3.2 聚類有效性評估指標

本文使用了CH函數量化指標來確定分支因子B和最大樣本半徑閾值T，為此，實驗設計了不同分支因子B和不同最大樣本半徑閾值T來進行組合實驗，實驗結果見表1、表2。

表1 不同T、B對應CH指數(amon)

表2 不同T、B對應CH指數(weblogs)

從結果可以看出，關鍵參數T/B分別為0.5/100和2/25時，CH函數值取最大，即此時聚類效果最好，后續實驗均采用對應參數。也就是說，針對不同的數據集，存在不同的最優關鍵參數對來使模型分類效果獲得最優。

3.3 模型性能對比分析

3.3.1 檢索性能對比

為了驗證模型檢索性能優勢，實驗對比了ULIB、lear-ned index、B+樹和ALEX的檢索性能，如圖8、圖9所示。

圖8 檢索性能對比(amon)

其中橫軸代表生成的檢索負載，縱軸代表所需要的時間，其值越小，代表模型檢索吞吐量越大，即檢索性能越好。

結果表明，隨著檢索負載提高，檢索時間會正比增加，原因在于，神經網絡中的矩陣運算決定了檢索所需要的時間，而該過程與檢索負載成正比關系。

且ULIB在兩個數據集上檢索性能相比較B+樹、lear-ned index和ALEX也具有一定優勢。原因在于ULIB模型在數據劃分階段使用birch聚類算法進行劃分，各個數據區域內分布更加趨于一致，從而使神經網絡訓練擬合度更高。另外，learned index使用的是多層遞歸RMI，而ULIB使用了兩層的非RMI設計，并且只在第二層輸出層使用神經網絡進行訓練預測，因此在各個階段體現得更加輕量有效。

3.3.2 訓練時間對比

為了測試ULIB訓練時間，即模型建立所需時間，實驗比較了ALEX、learned index和ULIB在相同數據集下模型建立完成所用時間，在兩個數據集上進行實驗，結果如圖10所示。

圖10 訓練時間對比

結果表明，經過birch聚類后的ULIB模型相比較learned index在兩個數據集的訓練時間上存在明顯優勢，主要原因是：在經過聚類將數據集分類k類后，訓練數據集變成了k個規模更小的數據區域，而機器學習訓練時間隨數據規模增長可能是指數級增長的，所以相比較learned index直接訓練所有數據而言，ULIB模型訓練上會存在優勢。

3.3.3 插入性能對比

為了驗證ULIB在插入性能上的優勢，實驗比較了ULIB、B+樹和ALEX的插入性能對比。

實驗結果如圖11、圖12所示，圖示分別代表在亞馬遜數據排名數據集和weblogs上實驗結果，橫軸是待插入數據的數目，縱軸為完成插入操作所使用的時間。實驗分別測試了2萬～10萬條插入請求時結果。

圖11 插入性能對比(amon)

圖12 插入性能對比(weblogs)

結果表明，ULIB在數據插入性能上，保持了對B+樹和ALEX的優勢。原因在于，ULIB借鑒LSM樹中延遲更新思路在內存中設置了緩存區，當插入請求生成后，模型先將其插入至緩存塊中，只有內存的緩存區占用達到閾值并溢出后，才轉移至對應的數據區域，此時才對相對應的數據區域進行重訓練，也正是因為這種機制，不會每次插入數據都需要對神經網絡模型進行重訓練，實現了插入性能的優化。

3.3.4 內存占用對比

本節對比了3個模型在亞馬遜數據排名數據集上的內存占用，結果見表3，其中15.7 M、213 M代表learned index和B+樹存儲實驗數據所占用的空間，而60 K、180 K和890 K代表了各個機器學習索引中所設置的神經網絡占用的空間。

表3 3種模型內存占用對比

結果表明，B+樹在相同數據集下內存占用最多。原因是B+樹中消耗了大量空間來存儲數據鍵和指針信息等額外數據，所以說，存儲的數據集越大，B+樹所需要的內存就越大。而機器學習索引結構只需要存儲神經網絡模型參數和數據鍵，并不需要其它額外的空間，因此內存占用情況相比較B+樹具有明顯優勢。

另外，ULIB模型相比較而言更為輕量簡單，因此比learned index在內存占用方面更具有優勢。不過在參數B和T減小時，聚類類別數增加，神經網絡內存占用也會增加。

4 結束語

本文確立了學習化索引結構實現的關鍵要素，提出可更新機器學習索引檢索模型ULIB，最后在亞馬遜書籍排名和weblogs數據集上分別進行測試實驗。經實驗驗證，結論如下：①采用birch聚類進行數據劃分時，CH函數作為參考依據來可以找到關鍵參數B和T的局部最優解；②相比較learned index、ALEX和B+樹索引結構，ULIB在相同數量級上檢索性能、訓練時間、插入性能和內存占用均有更好的表現。

下一步研究工作在于，目前B和T的取值是通過在實驗中進行調整，從而實現局部最優，可以嘗試從數學角度計算推導全局最優解。