基于塊坐標(biāo)下降算法的優(yōu)化哈希數(shù)據(jù)流頻率估計(jì)

鐘章生, 袁智勇

(南昌理工學(xué)院 計(jì)算機(jī)信息工程學(xué)院, 江西 南昌 330013)

0 引言

流媒體模型在搜索查詢(xún)監(jiān)控、網(wǎng)絡(luò)流量監(jiān)控等應(yīng)用中發(fā)揮了極其重要的作用,在這些應(yīng)用中最基本的問(wèn)題之一是頻率估計(jì),即在輸入流中,估計(jì)每個(gè)元素的發(fā)生次數(shù)[1-2]。數(shù)據(jù)流通常具有大容量的特征,因此,如何實(shí)現(xiàn)大型流媒體數(shù)據(jù)的頻率估計(jì)成為了研究的熱點(diǎn)問(wèn)題。

Sketches是處理流媒體數(shù)據(jù)的最強(qiáng)大工具之一,它是一種數(shù)據(jù)結(jié)構(gòu),可以表示為輸入的線性變換。Lu等[3]提出一種基于Rhombus Sketch的可動(dòng)態(tài)調(diào)整的Sketch算法:DARS Sketch。該算法根據(jù)對(duì)流數(shù)據(jù)規(guī)模的估計(jì),調(diào)整多層Sketch層級(jí)結(jié)構(gòu)的內(nèi)存分配,保證數(shù)據(jù)的存儲(chǔ)位置在內(nèi)存調(diào)整前后是一致的。Guo等[4]基于二項(xiàng)式分布和中心極限定理,結(jié)合Count-min Sketch處理大數(shù)據(jù)流的事件頻率表。Yang等[5]提出了一種基于桶sketch的用于覆蓋聚類(lèi)和多樣性最大化問(wèn)題的空間高效滑動(dòng)窗口算法,有效實(shí)現(xiàn)了流計(jì)算中的頻率估計(jì)。雖然上述方法取得了一定效果,但是上述頻率估計(jì)任務(wù)的估計(jì)精度極大地依賴(lài)于隨機(jī)哈希,導(dǎo)致估計(jì)精度穩(wěn)定性較低,可行性較差。

為了進(jìn)一步提升估計(jì)精度,有大量文獻(xiàn)將深度學(xué)習(xí)算法引入到流媒體數(shù)據(jù)頻率估計(jì)中。Pinckaers等[6]提出了一種基于深度卷積神經(jīng)網(wǎng)絡(luò)的流媒體頻率估計(jì)算法,通過(guò)卷積神經(jīng)網(wǎng)絡(luò)(convolutional neural networks, CNN)處理元素的列集,從而提升算法的適用性。甘元藝[7]提出了一個(gè)面向流的大數(shù)據(jù)應(yīng)用的延遲和資源感知調(diào)度框架(Lr-Stream),旨在優(yōu)化延遲和吞吐量,并且利用深度Q網(wǎng)絡(luò)對(duì)系統(tǒng)指標(biāo)進(jìn)行了全面評(píng)估。Zhang等[8]提出了一種基于強(qiáng)化學(xué)習(xí)和神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)的調(diào)度算法流式數(shù)據(jù)排序,用于在單處理器上處理受有限存儲(chǔ)大小和排序順序正確性約束的流式數(shù)據(jù)。趙鵬等[9]使用可解釋的機(jī)器學(xué)習(xí)方法學(xué)習(xí)連續(xù)和混合整數(shù)凸優(yōu)化問(wèn)題最優(yōu)解背后的策略,作為其關(guān)鍵參數(shù)的函數(shù),對(duì)大型視頻流數(shù)據(jù)實(shí)現(xiàn)頻率估計(jì)。雖然上述方法利用深度學(xué)習(xí)的強(qiáng)非線性映射能力極大地提升了頻率估計(jì)的準(zhǔn)確性;但是由于流媒體數(shù)據(jù)規(guī)模較大,加上深度學(xué)習(xí)的訓(xùn)練要求較高,因此導(dǎo)致計(jì)算成本較高,很難實(shí)現(xiàn)實(shí)時(shí)估計(jì)功能。

為了解決上述2個(gè)問(wèn)題,本文提出了一種基于塊坐標(biāo)下降算法的優(yōu)化哈希數(shù)據(jù)流頻率估計(jì)，并且通過(guò)實(shí)驗(yàn)結(jié)果證明了所提出方法的有效性。

1 相關(guān)理論

1.1 隨機(jī)Sketches方法

用索引u表示變量,索引i和k表示變量標(biāo)號(hào),索引j表示存儲(chǔ)桶。為便于標(biāo)記,根據(jù)上下文使用符號(hào)u或i表示元素;以此類(lèi)推,使用這2種方法中的任何一種對(duì)頻率進(jìn)行索引。

，

(1)

即該元素在S中出現(xiàn)的次數(shù);本文中,1A表示事件A的指示函數(shù)。假設(shè)S和U都是較大的,因此希望在比min{|S|,|U|}小得多的空間中實(shí)現(xiàn)準(zhǔn)確估計(jì)。在額外的假設(shè)下,即已經(jīng)觀察到的輸入流的前綴S0=(u1,u2,…,u|S0|),其中|S0|?|S|。

1.2 基于學(xué)習(xí)的方法

另外,分配給Heavy-hitter的每一個(gè)bheavy唯一桶都應(yīng)保持相關(guān)元素的頻率和元素名稱(chēng)ID。如上文所述,這可以通過(guò)使用具有開(kāi)放尋址的哈希來(lái)實(shí)現(xiàn),由此它足以將哈希的ID存儲(chǔ)為logbheavy+t位,以確保不會(huì)與概率1-2-t發(fā)生沖突。logbheavy+t與每個(gè)計(jì)數(shù)器的位數(shù)相當(dāng),唯一存儲(chǔ)桶的空間是普通存儲(chǔ)桶的2倍。從理論和經(jīng)驗(yàn)上看,學(xué)習(xí)增強(qiáng)算法都優(yōu)于傳統(tǒng)的完全隨機(jī)算法，然而,該方法仍然是啟發(fā)式的,不能保證獲得最佳性能。

2 基于塊坐標(biāo)下降算法的優(yōu)化哈希數(shù)據(jù)流頻率估計(jì)

本文兩階段方法的工作原理如下。在第一階段,流前綴中出現(xiàn)的元素根據(jù)其觀察到的頻率以最佳方式分配給桶,從而使頻率估計(jì)誤差最小化,同時(shí),將相似的元素映射到相同的桶。與基于CMS的方法相反,在所提出的方法中,元素頻率的估計(jì)是映射到同一桶的所有元素的頻率的平均值,因此,本文目標(biāo)是將“相似”元素分配給同一個(gè)桶。在第二階段,一旦對(duì)前綴中出現(xiàn)的元素進(jìn)行了優(yōu)化分配,將根據(jù)元素的特征訓(xùn)練一個(gè)分類(lèi)器,將元素映射到桶。通過(guò)這種方法,能夠提供前綴中未出現(xiàn)的不可見(jiàn)元素的估計(jì)值,因此不會(huì)記錄它們的頻率。

提出的哈希方案包括一個(gè)哈希表,將前綴中出現(xiàn)的元素ID映射到桶和學(xué)習(xí)的分類(lèi)器。此外,對(duì)于每個(gè)桶,需要保持其中映射的所有元素的頻率之和。在流處理期間,一旦估計(jì)器準(zhǔn)備就緒,每當(dāng)前綴中出現(xiàn)的元素重新出現(xiàn)時(shí),增加元素映射到的桶的計(jì)數(shù)器,即聚合頻率。最后,為了實(shí)現(xiàn)任何給定元素的計(jì)數(shù)查詢(xún),只需通過(guò)哈希表或分類(lèi)器輸出映射元素的桶的當(dāng)前平均頻率。

2.1 學(xué)習(xí)最佳哈希方案

(2)

參數(shù)λ∈[0,1]控制哈希方案之間的權(quán)衡,這些哈希方案映射到相同的桶元素,桶元素在前綴(λ→1)中觀察到的頻率相似,以及對(duì)元素的特征相似性(λ→0)施加更大權(quán)重的哈希方案，因此,將目標(biāo)中的第一項(xiàng)稱(chēng)為估計(jì)誤差,將第二項(xiàng)稱(chēng)為相似性誤差。

式(1)是一個(gè)非線性二元優(yōu)化問(wèn)題,很難解決，因此,下一步將提出不同的方法,用于在不同制度下求解最優(yōu)解或接近最優(yōu)的解。

2.2 混合整數(shù)線性格式

式(2)等價(jià)于下面的混合整數(shù)線性?xún)?yōu)化問(wèn)題:

(3)

證明過(guò)程與文獻(xiàn)[11]中定理1證明過(guò)程類(lèi)似。

問(wèn)題(3)由O(n2b)個(gè)變量和約束項(xiàng)組成。在本文所考慮的應(yīng)用中,求解混合整數(shù)線性?xún)?yōu)化問(wèn)題的計(jì)算量仍然是巨大的。為了解決該問(wèn)題,本文提出了一種塊坐標(biāo)下降算法。

2.3 高效塊坐標(biāo)下降算法

通過(guò)利用問(wèn)題(1)結(jié)構(gòu),提出了高效塊坐標(biāo)下降算法,該算法既可以啟發(fā)式地解決問(wèn)題(2),也可以用于計(jì)算問(wèn)題(3)。

在每次迭代中,高效塊坐標(biāo)下降算法按順序和隨機(jī)順序檢查b個(gè)變量zi,i∈[n]的所有n個(gè)塊,每個(gè)塊包含特定元素到任何桶的所有可能的映射。對(duì)于每個(gè)元素i,選擇較多映射值,使總體估計(jì)誤差最小化。為此,將元素i從當(dāng)前存儲(chǔ)桶中移除,并計(jì)算與每個(gè)存儲(chǔ)桶j相關(guān)的估計(jì)誤差,將元素i分配到存儲(chǔ)桶j,然后將元素i從存儲(chǔ)桶j移除,將元素i分配到存儲(chǔ)桶j*,使所有誤差項(xiàng)的總和最小化。

當(dāng)改進(jìn)后的估計(jì)誤差可以忽略時(shí),算法終止;如果希望更快地獲得中間解決方案,可以將終止標(biāo)準(zhǔn)設(shè)置為用戶(hù)指定的最大迭代次數(shù)。經(jīng)驗(yàn)表明,高效塊坐標(biāo)下降算法經(jīng)過(guò)幾十次迭代后收斂到局部最優(yōu),并得到性能較優(yōu)的解。由于該算法不能保證收斂到全局最優(yōu)解,因此該過(guò)程可以設(shè)置多組初始值,重復(fù)多次實(shí)驗(yàn)。

可以有效地實(shí)現(xiàn)高效塊坐標(biāo)下降算法,使每次迭代的復(fù)雜度為O(n2b)。這是意料之中的,因?yàn)閷?duì)于每個(gè)桶,需要計(jì)算映射到其中的所有元素對(duì)之間的相似性錯(cuò)誤,該過(guò)程的計(jì)算復(fù)雜度為O(n2b)。

2.4 動(dòng)態(tài)規(guī)劃算法

當(dāng)λ=1的特殊情況下,即在計(jì)算最優(yōu)哈希方案時(shí),不考慮特征,可以得到以下公式:

(4)

式(4)是一個(gè)一維k中值聚類(lèi)問(wèn)題,根據(jù)文獻(xiàn)[12],提出了一個(gè)復(fù)雜度為O(n2b)的動(dòng)態(tài)規(guī)劃算法解決問(wèn)題(4)的最優(yōu)性。在最優(yōu)量化背景下,對(duì)問(wèn)題(4)提出了一種更有效的求解方法;使用動(dòng)態(tài)規(guī)劃結(jié)合矩陣搜索技術(shù),問(wèn)題(4)的最優(yōu)性的計(jì)算復(fù)雜度為O(nb)。

3 頻率估計(jì)

3.1 前綴中元素的頻率估計(jì)

3.2 基于相似性的不可見(jiàn)元素頻率估計(jì)

3.3 自適應(yīng)計(jì)數(shù)擴(kuò)展

上文描述了一種靜態(tài)方法。學(xué)習(xí)流前綴中出現(xiàn)的元素的最佳哈希方案,然后只跟蹤它們的頻率,所有參數(shù)的估計(jì)頻率僅基于U0中元素的頻率。下文將描述一種動(dòng)態(tài)方法,它跟蹤U0中元素頻率以外的元素頻率。在較高的層次上,自適應(yīng)方法基于對(duì)每個(gè)桶中不同元素的近似計(jì)數(shù)。工作步驟如下:

① 學(xué)習(xí)基于觀察到的流前綴的最佳哈希方案,并訓(xùn)練將元素映射到桶的分類(lèi)器,如上所述。對(duì)于每個(gè)桶,只記錄其中映射的元素?cái)?shù)量,而不是存儲(chǔ)映射到此桶的元素的ID。使用分類(lèi)器來(lái)確定任何元素映射到哪個(gè)桶。

② 在給定元素U和集合U′?U的情況下,針對(duì)所有元素u∈U或者u∈U′,進(jìn)行概率測(cè)試,U′對(duì)應(yīng)于流數(shù)據(jù)中出現(xiàn)的元素。如果u∈U′,那么Bloom過(guò)濾器BF(u)=1；如果u?U′,那么就不需要BF(u)=0。

③ 根據(jù)元素u∈U0初始化Bloom過(guò)濾器。一方面,將所有元素u∈U0初始化為BF(u)=1；另一方面,可能將元素u?U0初始化為BF(u)=0或BF(u)=1。

④ 對(duì)于在處理流前綴S0之后出現(xiàn)在流中的每個(gè)后續(xù)元素u,將其映射到桶j∈[b]使用經(jīng)過(guò)訓(xùn)練的分類(lèi)器。然后,使用Bloom過(guò)濾器測(cè)試是否已經(jīng)找到u。如果BF(u)=0,則增加頻率φj和桶j中的元素?cái)?shù)cj,并令BF(u)=1；如果BF(u)=1,只增加頻率φj。

Bloom過(guò)濾器誤報(bào)的影響是,本文方法將標(biāo)記流中未出現(xiàn)的可見(jiàn)元素。當(dāng)該元素出現(xiàn)在流中時(shí),不會(huì)增加計(jì)數(shù)器cj,該計(jì)數(shù)器跟蹤該元素映射的桶j中的元素?cái)?shù)量，因此,j中元素cj的估計(jì)數(shù)量將小于實(shí)際數(shù)量，故而,自適應(yīng)計(jì)數(shù)擴(kuò)展通常會(huì)高估元素的頻率。

4 有關(guān)合成數(shù)據(jù)的實(shí)驗(yàn)

4.1 數(shù)據(jù)合成

在合成實(shí)驗(yàn)中使用的數(shù)據(jù)是根據(jù)以下方法生成的:

元素:用一個(gè)正整數(shù)G∈Z>0參數(shù)化元素U的集合,通過(guò)下述方式控制問(wèn)題大小。按指數(shù)遞增2G0+1,2G0+2,…,2G0+G生成G組元素G1,G2,…,GG。將每組關(guān)聯(lián)為Gg,g∈[G],具有p維正態(tài)分布,從[-10,10]p和等于恒等式的協(xié)方差矩陣中選擇μg均值。繪制與每個(gè)元素u∈Gg相關(guān)聯(lián)的特征,實(shí)現(xiàn)對(duì)應(yīng)于元素組的p維正態(tài)分布N(μg,I)。

通過(guò)設(shè)置G=10和g0=0.5,得到了8 192個(gè)元素,其中只允許4 096個(gè)元素出現(xiàn)在前綴中,而前綴的大小為10 240，因此,目標(biāo)是學(xué)習(xí)一種哈希方案。該方案最多將4 096個(gè)元素映射到10個(gè)桶，這種哈希方案的內(nèi)存要求是約等于20 000 B。

4.2 實(shí)驗(yàn)軟件配置

所有算法都采用Python 3編譯器,運(yùn)行所有實(shí)驗(yàn)的硬件配置為CentOS 7版的標(biāo)準(zhǔn)Intel(R)Xeon(R)CPU E5-2690@2.90 GHz。獨(dú)立重復(fù)每個(gè)實(shí)驗(yàn)10次,并計(jì)算平均誤差及其標(biāo)準(zhǔn)偏差。

優(yōu)化算法如下:

MILP:使用商業(yè)MIO解算器Gurobi解決混合整數(shù)線性?xún)?yōu)化問(wèn)題。

BCD:塊坐標(biāo)下降算法。

DP:通過(guò)動(dòng)態(tài)編程在線性時(shí)間內(nèi)解決問(wèn)題。

本文研究的機(jī)器學(xué)習(xí)算法包括線性分類(lèi)器,即多項(xiàng)式邏輯回歸(Logreg)[13],基于樹(shù)的分類(lèi)器(Cart)[14],以及集成分類(lèi)器,即隨機(jī)森林(Rf)[15]。所有方法均使用10倍交叉驗(yàn)證進(jìn)行調(diào)整;調(diào)整的超參數(shù)是Logreg正則化項(xiàng)的權(quán)重、Cart的最小雜質(zhì)減少量和最大深度、每個(gè)分割中的最大特征數(shù)和rf的最大深度。在實(shí)驗(yàn)中使用Cart作為底層分類(lèi)器,使用Scikit機(jī)器學(xué)習(xí)包實(shí)現(xiàn)上述所有算法。

將標(biāo)準(zhǔn)分鐘示意圖(CMS)稱(chēng)為計(jì)數(shù)分鐘,將學(xué)習(xí)分鐘示意圖(LCMS)稱(chēng)為Heavy-hitter,使用Python實(shí)現(xiàn)了上述估計(jì)器。

4.3 結(jié)果分析

實(shí)驗(yàn)1超參數(shù)λ的影響。在本實(shí)驗(yàn)中,研究了超參數(shù)λ對(duì)學(xué)習(xí)哈希方案的影響。通過(guò)令G=6,并根據(jù)不同的λ,運(yùn)行3個(gè)不同版本的哈希優(yōu)化算法。記錄前綴上的估計(jì)、相似性和總體誤差,以及每個(gè)算法的運(yùn)行時(shí)間。為了檢驗(yàn)BCD的次優(yōu)度,給出了構(gòu)成目標(biāo)函數(shù)誤差項(xiàng)的實(shí)際值,也就是說(shuō),不以每元素或者每對(duì)元素的尺度進(jìn)行轉(zhuǎn)換。結(jié)果如圖1所示。

(a) 估計(jì)誤差

(b) 相似性誤差

(c) 總體誤差

(d) 訓(xùn)練時(shí)間

圖1 超參數(shù)的影響Fig.1 Effect of super parameters

從實(shí)驗(yàn)1結(jié)果可知:

MILP以增加運(yùn)行時(shí)間為代價(jià)獲得最小的總體誤差。該方法相較于BCD方法更加優(yōu)越,因?yàn)樵摲椒ǖ玫降慕鈳缀蹩偙菳CD獲得的解更好。

BCD獲得的解的時(shí)間性能較高;對(duì)于小規(guī)模的問(wèn)題,BCD的運(yùn)行時(shí)間1 s。

正如預(yù)期的那樣,DP的估計(jì)誤差最小,因?yàn)樗鼉H針對(duì)與λ值無(wú)關(guān)的估計(jì)誤差進(jìn)行優(yōu)化。但是就相似性和總體而言,DP的性能明顯較差。

在λ=1的情況下,所有3種方法都能夠找到可比較的近似最優(yōu)解。

實(shí)驗(yàn)2λ=1時(shí),BCD和DP之間的比較。在本實(shí)驗(yàn)中,將重點(diǎn)研究λ=1的情況,并比較G、BCD和DP的增加值。在這種情況下,后者可以保證找到最優(yōu)的哈希方案。再次記錄前綴上的估計(jì)、相似性和總體誤差,以及每個(gè)算法的運(yùn)行時(shí)間。在本實(shí)驗(yàn)和隨后的實(shí)驗(yàn)中,以每元素與每對(duì)元素的比例轉(zhuǎn)換誤差,結(jié)果如圖2所示。從圖中可以觀察到,對(duì)于G≤10的問(wèn)題,BCD可以快速計(jì)算近似最優(yōu)解;然而,隨著G值的進(jìn)一步增加,BCD的性能惡化。

(a) 估計(jì)誤差

(b) 相似性誤差

(c) 總體誤差

(d) 訓(xùn)練時(shí)間

圖2 元素組數(shù)的影響Fig.2 Influence of element group number

實(shí)驗(yàn)3前綴中元素分?jǐn)?shù)的影響如圖3所示。在這個(gè)實(shí)驗(yàn)中,設(shè)G=10并改變g0的值,g0控制前綴中出現(xiàn)的元素的分?jǐn)?shù)。探索了2種學(xué)習(xí)哈希方案的方法:首先,設(shè)置λ=0.5并運(yùn)行BCD;然后,運(yùn)行DP(λ=1)。記錄前綴S0、元素上的估計(jì)和相似性錯(cuò)誤,這些元素沒(méi)有出現(xiàn)在S0中,但出現(xiàn)在S0之后的|S|=10|S0|。圖3表明,在前綴中觀察更多的元素會(huì)減少可見(jiàn)和不可見(jiàn)元素的估計(jì)誤差,但會(huì)增加相似性誤差。

(a) S0估計(jì)誤差

(b) S0相似性誤差

(c) |S|=10|S0|估計(jì)誤差

(d) |S|=10|S0|相似性誤差

圖3 可見(jiàn)元素的影響Fig.3 Influence of visible elements

實(shí)驗(yàn)4不同分類(lèi)器的對(duì)比結(jié)果如圖4所示。在這個(gè)實(shí)驗(yàn)中,設(shè)g0=0.33和λ=0.5,改變G的值,并探索使用不同類(lèi)型的分類(lèi)器(Logreg,Cart,Rf)作為哈希優(yōu)化的一部分的影響。記錄了S0中未出現(xiàn)但在S0后|S|=10|S0|到達(dá)范圍內(nèi)出現(xiàn)的元素的估計(jì)、相似性和總體誤差,統(tǒng)計(jì)了每種方法的訓(xùn)練時(shí)間。在圖中,可以看到使用非線性分類(lèi)器的優(yōu)點(diǎn)，然而,實(shí)驗(yàn)結(jié)果很大程度上取決于數(shù)據(jù)生成過(guò)程。

(a) 估計(jì)誤差

(b) 相似性誤差

(c) 總體誤差

(d) 訓(xùn)練時(shí)間

圖4 不同分類(lèi)器的對(duì)比結(jié)果Fig.4 Comparison results of different classifiers

5 搜索查詢(xún)估計(jì)

5.1 數(shù)據(jù)集

使用AOL查詢(xún)?nèi)罩緮?shù)據(jù)集,該數(shù)據(jù)集包含2006年90 d內(nèi)從65萬(wàn)匿名用戶(hù)收集的2 100萬(wàn)個(gè)搜索查詢(xún),其中有380萬(wàn)個(gè)唯一查詢(xún)。每個(gè)查詢(xún)都是自由文本中的搜索短語(yǔ),例如,第一個(gè)最常見(jiàn)的查詢(xún)是“google”,在整個(gè)90 d內(nèi)出現(xiàn)251 463次,第10個(gè)是“www.yahoo.com”,出現(xiàn)頻率為37 436次,第100個(gè)是“mys”,出現(xiàn)頻率為5 237次,第1 000個(gè)是“sharon stone”,出現(xiàn)頻率為926次,第10 000個(gè)是“online casino”,出現(xiàn)頻率為146次等。搜索查詢(xún)頻率的分布遵循Zipfian定律,因此該設(shè)置非常適合提出的算法(LCMS)。

5.2 基線方法

本文使用Count-min和Heavy-hitter作為基線方法。對(duì)于固定參數(shù)尺寸,即桶的總數(shù)b,統(tǒng)計(jì)了深度取d∈{1, 2, 4, 6}時(shí)的Count-min最佳性能,桶數(shù)量取bheavy∈{10,102,103,104}時(shí)的Heavy-hitter的最佳性能。此外,假設(shè)測(cè)試集中Heavy-hitter的ID是已知的，因此,將提出的方法與文獻(xiàn)[10]中提出方法進(jìn)行了比較。

5.3 提出方法

第一天包括超過(guò)20萬(wàn)個(gè)唯一的查詢(xún),僅存儲(chǔ)它們的ID就需要20萬(wàn)個(gè)存儲(chǔ)桶，因此,隨機(jī)抽樣觀察到的查詢(xún)子集,概率與觀察到的頻率成正比。使用查詢(xún)的抽樣子集作為本算法的輸入。

對(duì)于固定數(shù)量的桶總數(shù)btotal,需要確定學(xué)習(xí)的哈希方案包含的桶數(shù)量b與將存儲(chǔ)其ID的查詢(xún)數(shù)量n之間的比率c，因此,對(duì)于用戶(hù)指定的btotal和c,根據(jù)n=btotal/(1+c)和b=btotal-n選擇b和n。在本文實(shí)驗(yàn)中,檢驗(yàn)了c∈{0.03,0.3}時(shí)的模型性能。

為了為分類(lèi)器g創(chuàng)建輸入特征,在訓(xùn)練查詢(xún)中只保留500個(gè)最常見(jiàn)的詞。還包括查詢(xún)文本中ASCII字符的數(shù)量、標(biāo)點(diǎn)符號(hào)的數(shù)量、點(diǎn)的數(shù)量和空格的數(shù)量。

5.4 結(jié)果分析

(a) 第30天平均絕對(duì)誤差

(b) 第30天預(yù)測(cè)絕對(duì)誤差

(c) 第70天平均絕對(duì)誤差

(d) 第70天預(yù)測(cè)絕對(duì)誤差

實(shí)驗(yàn)中觀察到,在第30、70天之后,估計(jì)誤差的趨勢(shì)非常相似。變化的是估計(jì)誤差的絕對(duì)值,正如預(yù)期的那樣,估計(jì)誤差隨時(shí)間而惡化,對(duì)所有方法都是一致的。所提出的方法在這2個(gè)指標(biāo)上都優(yōu)于其他比較方法,隨著所有估計(jì)量的增加,它們的誤差也會(huì)下降。

在平均誤差方面提出方法性能表現(xiàn)最佳，原因是提出方法較適合估計(jì)很少出現(xiàn)的查詢(xún)的頻率。特別是,出現(xiàn)次數(shù)很少的查詢(xún)被放在同一個(gè)桶中,因此它們的估計(jì)誤差很小。相比之下,Heavy-hitter和Count-min通常將此類(lèi)查詢(xún)與中等或甚至高頻率的查詢(xún)放在同一個(gè)桶中,這會(huì)產(chǎn)生較大的估計(jì)誤差。

當(dāng)估計(jì)器的大小變得足夠大時(shí),Heavy-hitter和Count-min的估計(jì)誤差的預(yù)期值似乎緩慢地收斂到提出方法估計(jì)誤差，表明提出方法特別適合于低空間區(qū)域,并且可以實(shí)現(xiàn)更有效的頻率向量壓縮。

就Heavy-hitter和Count-min而言,前者確實(shí)產(chǎn)生了更好的估計(jì),與文獻(xiàn)[10]中的結(jié)果一致。就估計(jì)誤差的預(yù)期值而言,改進(jìn)更為顯著。鑒于Heavy-hitter在出現(xiàn)頻率最高的元素上沒(méi)有錯(cuò)誤,該觀察結(jié)果也是可以預(yù)期的,這些元素在該度量中權(quán)重很大。

2種不同內(nèi)存配置的估計(jì)誤差隨時(shí)間的變化如圖6所示。從這2個(gè)指標(biāo)來(lái)看,提出方法的優(yōu)勢(shì)隨著時(shí)間的推移而保持。此外,觀察到提出方法的估計(jì)誤差達(dá)到最小的標(biāo)準(zhǔn)差，原因是元素到桶的映射比Heavy-hitter和Count-min的映射更穩(wěn)定,因?yàn)樗鼈兪峭ㄟ^(guò)優(yōu)化得到的,而不是通過(guò)隨機(jī)化獲得的,提出方法隨機(jī)性的主要來(lái)源是分類(lèi)器。

(a) 4 kB平均絕對(duì)誤差

(b) 4 kB預(yù)測(cè)絕對(duì)誤差

(c) 120 kB平均絕對(duì)誤差

(d) 120 kB預(yù)測(cè)絕對(duì)誤差

然后對(duì)1.2～120 kB的內(nèi)存配置進(jìn)行實(shí)驗(yàn),并將提出方法與Count-min和Heavy-hitter進(jìn)行比較。對(duì)于120 kB的內(nèi)存,提出方法估計(jì)每個(gè)查詢(xún)的頻率的平均絕對(duì)估計(jì)誤差大約為29,而Heavy-hitter的誤差大約是479,如圖6(a)所示。內(nèi)存為4 kB時(shí),提出方法和Heavy-hitter的誤差大約分別為167和14 661,如圖6(c)所示。表1統(tǒng)計(jì)了90 d內(nèi),1、10、100、1 000、10 000個(gè)最常見(jiàn)查詢(xún)的平均誤差占每個(gè)查詢(xún)頻率的比例。

提出方法的另一個(gè)特性是在機(jī)器學(xué)習(xí)元素中的可解釋性,它可以深入了解潛在的頻率估計(jì)問(wèn)題。始終被標(biāo)記為最重要的特征是4個(gè)變量,即查詢(xún)文本中ASCII字符的數(shù)量、標(biāo)點(diǎn)符號(hào)的數(shù)量、點(diǎn)的數(shù)量和空格的數(shù)量,以及單詞“com”、“www”、“google”和“yahoo”,這一結(jié)果是合理的。

表1 平均誤差百分比

6 結(jié)語(yǔ)

為了不依賴(lài)于隨機(jī)哈希,并且降低計(jì)算復(fù)雜度,本文提出了一種基于塊坐標(biāo)下降算法的優(yōu)化哈希數(shù)據(jù)流頻率估計(jì)方法。所提出的算法使用混合整數(shù)線性?xún)?yōu)化動(dòng)態(tài)規(guī)劃方法,計(jì)算具有數(shù)千個(gè)元素的問(wèn)題的最優(yōu)哈希方案,以及使用塊坐標(biāo)描述算法計(jì)算具有數(shù)萬(wàn)個(gè)元素的頻率估計(jì)問(wèn)題。在合成數(shù)據(jù)集和搜索查詢(xún)數(shù)據(jù)集上對(duì)所提出的方法進(jìn)行了實(shí)驗(yàn)評(píng)估,實(shí)驗(yàn)結(jié)果證明:

① 提出方法能夠不依賴(lài)于隨機(jī)哈希實(shí)現(xiàn)頻率向量的更新壓縮,并跟蹤所有元素的頻率,與現(xiàn)有的流頻估計(jì)算法相比,所提出的基于學(xué)習(xí)的流頻估計(jì)算法具有更好的性能。

② 提出方法特別適合于低空間區(qū)域,并且可以實(shí)現(xiàn)更有效的頻率向量壓縮,另外提出方法較適合估計(jì)很少出現(xiàn)的查詢(xún)的頻率,其估計(jì)優(yōu)勢(shì)也會(huì)隨著時(shí)間的推移而保持。

③ 提出方法在機(jī)器學(xué)習(xí)元素中具有較強(qiáng)的可解釋性,它可以深入了解潛在的頻率估計(jì)問(wèn)題。