一種流數(shù)據(jù)立方體分析挖掘框架*

金蒼宏 ，劉澤民 ，吳明暉 ，應(yīng) 晶 ,

（1.浙江大學(xué)計算機科學(xué)與技術(shù)學(xué)院 杭州 310027；2.浙江大學(xué)城市學(xué)院 杭州 310015）

1 引言

聯(lián)機分析挖掘（online analytical mining，OLAM）是一種結(jié)合數(shù)據(jù)挖掘和聯(lián)機分析處理 （online analytical processing，OLAP）的知識發(fā)現(xiàn)方法。使用OLAM可在多維數(shù)據(jù)庫的不同數(shù)據(jù)子集和抽象層次上進行探索式挖掘，因此在決策定制、市場分析、可視化等領(lǐng)域都發(fā)揮著重要作用。隨著移動互聯(lián)網(wǎng)的迅速發(fā)展和廣泛應(yīng)用，各種類型的數(shù)據(jù)流規(guī)模急劇增大，如金融流數(shù)據(jù)、圖像流數(shù)據(jù)、社交流數(shù)據(jù)等。挖掘數(shù)據(jù)流中包含用戶刻面和行為動作的相關(guān)信息，成為當前研究的一個熱點[1]。如在移動應(yīng)用分析系統(tǒng)中，通過SDK（軟件開發(fā)工具包）可以采集應(yīng)用的名稱、使用時間、GPS信息、IP地址、手機型號、網(wǎng)絡(luò)類型等多個維度的信息。對此類信息進行OLAM分析，可提供靈活的多角度數(shù)據(jù)分析場景，提高商業(yè)競爭能力。例1給出一個流數(shù)據(jù)OLAM的分析場景。

例1：運營方希望能實時監(jiān)控某款應(yīng)用在不同人群中的活躍度，以便其能分析出核心用戶，實時調(diào)整留存和激活策略，增強其競爭力。

對于不同人群的劃分可以使用數(shù)據(jù)立方體分析，可以在多個子空間中統(tǒng)計相關(guān)活躍度。但是，流數(shù)據(jù)處理具有單次掃描、較低的時間和空間復(fù)雜度、適應(yīng)動態(tài)變化的流速等要求，且系統(tǒng)挖掘時效性強，需實時返回分析結(jié)果，而事先又無法指定所需要觀察的維度組合，需要對維度組合進行全量分析，因此實時計算量巨大。

基于上述的要求，使用現(xiàn)有的OLAM方法，把數(shù)據(jù)倉庫中的記錄通過OLAP投射到不同空間生成數(shù)據(jù)單元，再通過多角度綜合分析數(shù)據(jù)的方法[2]無法滿足上述要求，原因如下。

（1）數(shù)據(jù)量大

和傳統(tǒng)的數(shù)據(jù)倉庫相比，移動互聯(lián)網(wǎng)下的流式數(shù)據(jù)是海量的且增長迅速。傳統(tǒng)OLAP工具在存儲空間和計算效率上都無法滿足實時性能要求。

（2）數(shù)據(jù)動態(tài)性強

傳統(tǒng)OLAP方法，通過對數(shù)據(jù)立方體建立物化視圖（materialized view）可以預(yù)計算部分結(jié)果，從而提高實時查詢的效率，達到空間和效率上的平衡[3]，如QC-Tree、侏儒立方體等方法[4]。但流式數(shù)據(jù)是動態(tài)可變的，因此對于數(shù)據(jù)無法做靜態(tài)的預(yù)處理，必須要實時計算。

（3）數(shù)據(jù)時效性強

傳統(tǒng)OLAP框架處理的是歸檔數(shù)據(jù)，對數(shù)據(jù)的實效性要求不高。而數(shù)據(jù)流內(nèi)含的時態(tài)特征表明，數(shù)據(jù)是有生命周期的。用戶往往只對特定時間窗口內(nèi)的數(shù)據(jù)感興趣，而忽略窗口外的數(shù)據(jù)。如例1中，只需要統(tǒng)計分析促銷活動過程中的最近的數(shù)據(jù)，而忽略其他歷史歸檔數(shù)據(jù)。

由此可見，傳統(tǒng)的OLAM方法不能很好地處理數(shù)據(jù)流。而其他基于數(shù)據(jù)抽樣[5,6]和基于數(shù)據(jù)壓縮[4]兩種流式數(shù)據(jù)處理方法受限于計算能力和存儲空間的大小，只在整體空間或幾個分組中進行數(shù)據(jù)分析，如stream[7]、TelegraphCQ[8]、SMM[9]等。但它們沒有提供在任意子空間或任意層次中對數(shù)據(jù)進行分析的方案。

本文提出一種流數(shù)據(jù)立方體處理框架——sketch cube（概要立方體）。并在storm開源流處理平臺中實現(xiàn)。sketch cube在較小的空間中實時聚合有效數(shù)據(jù)單元信息，可滿足OLAM的分析需求，其貢獻在于以下幾點。

·提出一種可擴展的數(shù)據(jù)單元標識方法，對流數(shù)據(jù)的任意維度組合通過配對函數(shù) （pairing function）[10]映射生成唯一標識且保證維度擴展后數(shù)據(jù)仍不沖突。

·提出一種改進概要統(tǒng)計模型——ACM（advanced count model），ACM根據(jù)數(shù)據(jù)分布特性和存儲模型的設(shè)計特征，可有效裁剪長尾的數(shù)據(jù)單元，以提高計算能力和存儲空間效率，同時可改進數(shù)據(jù)單元統(tǒng)計精確度。

·提出一種基于時間窗口的倒排檢索模型，可支持任意時間粒度的組合。在類線性存儲空間中存放所有有效數(shù)據(jù)單元的統(tǒng)計信息，最大限度地保證了信息的完整性。

·從理論上給出sketch cube的適用場景和準確率范圍。通過storm實現(xiàn)sketch cube功能，且在海量真實數(shù)據(jù)流下測試模型在不同參數(shù)和時間片長度下的吞吐量和準確率。理論分析和實驗證明sketch cube的查詢效率高且能支持流式數(shù)據(jù)下的立方體全量分析。

本文研究主要結(jié)合傳統(tǒng)的OLAP方法和流數(shù)據(jù)處理方法。

已有的對傳統(tǒng)OLAP的擴展研究如（參考文獻[11～13]）引入了文本屬性，提出文本立方體（text cube）概念。Lin C等[13]提出基于關(guān)鍵詞的數(shù)據(jù)立方體查詢，對數(shù)值和文本維度分別建立層次結(jié)構(gòu)，通過倒排索引檢索出相應(yīng)的數(shù)據(jù)單元。在此基礎(chǔ)上，Ding B等[12]提出基于關(guān)鍵詞的top-k數(shù)據(jù)單元查詢問題，通過對關(guān)鍵詞的信息檢索（information retrieval）度量，提取出與關(guān)鍵詞最相關(guān)的k個數(shù)據(jù)單元。與此相反，參考文獻[11]提出了數(shù)據(jù)單元主題判定問題，對給定層次的數(shù)據(jù)單元結(jié)合自然語言模型，判斷其所屬的主題和相關(guān)概率。

流數(shù)據(jù)結(jié)合OLAP操作產(chǎn)生了流立方體（stream cube）的概念。參考文獻[4]使用傾斜時間框架（tilted time framework）管理數(shù)據(jù)，使用線性回歸函數(shù)對流數(shù)據(jù)在不同維度上進行壓縮。但是該方法物化數(shù)據(jù)帶有主觀性，會丟失部分信息。同時在上下層節(jié)點合并時需要頻繁更新head表，更新速度較慢。文本流數(shù)據(jù)立方體（如Liu X等[14]）通過Twitterstream數(shù)據(jù)，建立熱點圖和情感圖等應(yīng)用。該方法雖然使用時間序列分析，但還是把信息看成靜態(tài)地存放在數(shù)據(jù)倉庫中而進行分析。其他的流數(shù)據(jù)分析方法，如抽樣方法[6,15]，通過建立不同的分布概率函數(shù) （probability distribution function,PDF）對異構(gòu)源數(shù)據(jù)進行抽樣和語義分析，獲得不同的權(quán)重，通過樣本值的上下限來估計實際的聚合值。方法依賴于樣本的采集和分布情況，因此對于錯誤率無法進行有效的控制。參考文獻[16]的方法則使用壓縮策略，通過對數(shù)據(jù)特征分析，只保留其主要元素，而過濾其他元素。但它們把數(shù)據(jù)看成整體，挖掘不同數(shù)據(jù)流和不同時間段之間的關(guān)聯(lián)關(guān)系，而不是有層次的可以進行OLAP操作的模型。

此外，計數(shù)型散列技術(shù)統(tǒng)計數(shù)據(jù)的方法有 na觙ve counting bloom filter （NCBF）、d-left counting bloom filter（dlCBF） 和 binary shrinking d-left counting bloom filter（BSdlCBF）等[17]。在此基礎(chǔ)上，概要技術(shù)[18,19]可在二階矩陣大小空間內(nèi)保存流數(shù)據(jù)，把N個輸入元素壓縮在lb N的存儲空間中。

2 問題描述

2.1 基本概念

定義1 （多維數(shù)據(jù)流模型 （multi-attribute stream data model，MSDM））定義某時間點上的數(shù)據(jù)流記錄。MSDM為一個二元組結(jié)構(gòu)（S,T），其中，S為多維度數(shù)據(jù)模型S=（A0,A1,…,Ai:M），Ai表示標準屬性，M為度量維度，T為某個時間點。

如 ((Wi-Fi,hz,Samsung∶1)，20140510081559) 中 ，S=(Wi-Fi,hz,Samsung∶1) 為 維 度 模 型 ，hz表 示 “杭 州 ”，20140510081559為時間點，1為度量值。

定義2 （流立方體）表示給定一個時間段內(nèi)的MSDM，按不同的維度構(gòu)建的一個數(shù)據(jù)立方體stream cube=(A1,A2,…,An,M,T)。對于stream cube中的每條數(shù)據(jù)r=(a1,a2,…,an,m,t)，其中 r[Ai]=ai∈Ai，ai為屬性 Ai的值 ，m 為度量值。對于時間維度T有ti-1

如例1中，給定時間間隔為5 min，在該時間段內(nèi)收集的所有數(shù)據(jù)產(chǎn)生的數(shù)據(jù)立方體，即該時間段內(nèi)的流立方體。

定義3 （祖先單元和后代單元）對于流立方體中的數(shù)據(jù)單元Cm和Cn，定義*表示該維度折疊且計算不考慮，則Cm是Cn的祖先（Cn是Cm的后代）可表示為：

記為Cn[t]奐Cm[t]，即兩個數(shù)據(jù)單元之間的時間相同，祖先單元至少在一個維度上包含子孫單元且在其他所有維度上和子孫單元的值相等。

對于給定的流數(shù)據(jù)單元D0=((Wi-Fi,hz,Samsung),20140510081559)的父節(jié)點有如下7個：

上述例子中沒有顯示數(shù)據(jù)單元的度量值M，祖先單元的度量值可以由其子孫單元的度量值通過聚合操作而計算得出。聚合操作可以分為分布型（distributive）、代數(shù)型（algebraic）和整體型（holistic）3 類[20]。

2.2 流數(shù)據(jù)立方體問題描述

在一組給定的持續(xù)的MSDM中，按時間窗口大小，劃分出不同的數(shù)據(jù)片段，按照其維度生成流數(shù)據(jù)立方體。流數(shù)據(jù)立方體實時提供了清潔、有組織和匯總的數(shù)據(jù)，因此可以在不同粒度父子數(shù)據(jù)單元中分析挖掘。通過和流數(shù)據(jù)框架的結(jié)合，大大增強探索式數(shù)據(jù)挖掘能力和靈活性。如例1所示，可以滿足實時的、全量的多層次數(shù)據(jù)挖掘的需求。

3 sketch cube框架結(jié)構(gòu)

本節(jié)給出構(gòu)造sketch cube框架所需的主要部件：數(shù)據(jù)單元標識算法及其改進模型、流數(shù)據(jù)立方體存儲結(jié)構(gòu)和裁剪模型、時間窗口索引等。

3.1 數(shù)據(jù)單元標識算法

流數(shù)據(jù)立方體產(chǎn)生了海量的維度組合，即數(shù)據(jù)單元，這些數(shù)據(jù)單元中的不同屬性值包含多種類型，有連續(xù)型、離散數(shù)值型、字符型等。需要對這些屬性值進行字典化處理，并給每個數(shù)據(jù)單元一個唯一的標識，用于后續(xù)計算。

數(shù)據(jù)單元標識（data cell identifier，DCI）算法的功能就是把不同的維度組合映射成唯一整數(shù)，且算法支持維度的擴展，即新增維度或修改維度值都不會與原有映射值沖突。在流數(shù)據(jù)R=(A1,A2,…,An,M)中，|Ai|表示第i維的基數(shù)。使用兩個步驟進行數(shù)據(jù)單元標識。

（1）由于維度值的多樣性，需要先把記錄R的維度Ai映射成連續(xù)的自然數(shù)，即：

（2）在步驟（1）中產(chǎn)生 n 個自然數(shù) Ni，形成集合 S，使用配對函數(shù)對S中的任意非空子集生成唯一的自然數(shù)。

配對函數(shù)的定義為把兩維度元組映射成一維度元組的函數(shù)N×N→N。它是一個雙射函數(shù)，其單調(diào)遞增的特性如式（3）所示，保證其不會重復(fù)。

對于高于兩維度的元組可以使用嵌套模式進行，文本使用康托爾配對函數(shù)（Cantor tuple function），如圖1和式（4）所示，按維度順序進行嵌套配對，把中間結(jié)果當成下一步操作的輸入。

圖1 有限元素算術(shù)圖

3.1.1 改進配對函數(shù)

康托爾配對函數(shù)用嵌套方式生成映射值，當元組維度較高或者某些維度基數(shù)較大時，會導(dǎo)致巨大的映射值。提出改進配對函數(shù)（advanced pairing function，APF）模型，其思想是在不改變計算模型的同時，產(chǎn)生較小的映射值。其理論依據(jù)如下：

·在數(shù)據(jù)立方體中，維度的順序與數(shù)據(jù)單元描述無

關(guān)，即數(shù)據(jù)單元(A1,A2)=(A2,A1)；

·在嵌套方法中，越早進入計算的數(shù)值參與循環(huán)的次數(shù)越多，對結(jié)果值大小的影響越大。

APF 模型定義如式（5）和式（6）所示。

對給定屬性Ai：

如圖1所示，嵌套計算從尾部開始，式（5）表示輸入配對函數(shù)的維度順序由維度基數(shù)大小決定，基數(shù)大的維度靠前。式（6）表示把維度值映射成連續(xù)自然數(shù)時，對出現(xiàn)頻率高（freq值大）的維度值賦給小自然數(shù)。維度基數(shù)的大小和維度值的頻率可以由統(tǒng)計或經(jīng)驗獲得。如本文實驗中，手機操作系統(tǒng)維度基數(shù)小于城市維度基數(shù)，Android機型多于蘋果機型。使用APF模型可以有效地減少大數(shù)值在遞歸中的計算次數(shù)，達到最終控制輸出映射值的目的。

3.1.2 算法步驟

結(jié)合APF模型，給出算法1數(shù)據(jù)單元標識（DCI）算法的步驟。DCI算法先把流數(shù)據(jù)中每條記錄的維度值映射成由小到大的自然數(shù)（行①），通過遞歸函數(shù)得到與之相關(guān)的所有維度組合（行②），并使用康托爾配對函數(shù)獲得所有組合唯一標識（行③～⑦）。

算法1 數(shù)據(jù)單元標識算法

輸入：流數(shù)據(jù)記錄r=(a1,a2,…,ai,m,t)

輸出：r所有維度組合標識

①根據(jù)APF模型中式（5）和式（6），將記錄r中的維度映射成(n1,n2,…,nn)

②set=(n1,n2,…,ni)的所有組合，size of=2i。

③set←{}；

④for all x∈{}do

⑤←pairing function(x)；

⑥end for

⑦return；

3.2 存儲結(jié)構(gòu)描述

提出一種通過sketch技術(shù)對流數(shù)據(jù)單元進行統(tǒng)計的方法，首先給出模型所需的獨立散列族定義。

3.2.1 獨立散列族定義

定義4 （均勻散列函數(shù)）對于給定的元素集合U通過散列函數(shù)h(x)投射到n個元素中，對每個j=1,…,n，給定x∈U，有 P[h(x)=j]=1/n，h(x)則為均勻散列函數(shù)。

定義5 （互相獨立散列函數(shù)族）在F散列族中任意選擇a、b兩個隨機函數(shù)，如果且則F為相互獨立的散列函數(shù)族。

3.2.2 計數(shù)最小概要模型

計數(shù)最小概要（count-min sketch,CM sketch）模型[10]是一個使用相互獨立散列函數(shù)族函數(shù)統(tǒng)計流數(shù)據(jù)元素出現(xiàn)頻率的模型。其結(jié)構(gòu)如圖2所示，是一個d×w的二維數(shù)組。

圖2 CM sketch存儲結(jié)構(gòu)

其中，d表示相互獨立散列族函數(shù)的個數(shù)，w表示每個散列函數(shù)的映射范圍，如式（7）所示：

顯然，n個元素可以表示2n個兩兩組合元素集合。因此，設(shè)計包含d個函數(shù)的相互獨立散列函數(shù)族，只需用個不同元素，如式（8）所示：

從SeedSet中隨機取不同的元素a和b，定義散列函數(shù)方法如式（9）所示：

由ha,b(z)產(chǎn)生的散列值是變長的，式（10）把值規(guī)約到w大小的數(shù)組中。

3.2.3 CM sketch效率

對于第t次到達的元素c，計數(shù)最小概要模型更新操作如式（11）所示：

即使用不同散列函數(shù)找到存儲結(jié)構(gòu)中的下標位置，并添加相應(yīng)值，其更新時間復(fù)雜度為

統(tǒng)計元素ai在CM sketch中的估計值a^i的操作如式（12）所示：

即通過散列函數(shù)族中的每個函數(shù)計算該元素在對應(yīng)數(shù)組中的下標值，獲得所有可能值中的最小值即該元素的估計值，其查詢時間復(fù)雜度為O(1)。

流數(shù)據(jù)有收款機模型（cash register model）和十字轉(zhuǎn)門模型（turnstile model）兩種模型。計數(shù)最小概要模型只支持收款機模型，即統(tǒng)計值只能遞增，因此基于此的sketch cube只支持分布型聚合操作。對于(A1,A2,…,An)數(shù)據(jù)立方體，所有數(shù)據(jù)單元個數(shù)則 sketch cube模型的壓縮率P為式（13）所示：

3.2.4 模型精度和前提條件

式（14）給出了預(yù)測元素ai統(tǒng)計值的偏差范圍，即預(yù)測統(tǒng)計值a^i小于實際值ai+綴||a||的概率為1-δ，可以根據(jù)元素多樣性和期望精確度調(diào)整綴和δ，進而調(diào)整存儲模型中的w和d值。

計數(shù)最小概要模型是一個數(shù)據(jù)敏感模型，對于偏斜數(shù)據(jù)（skew data）的支持較好（Zipfian參數(shù) 1

3.2.5 計數(shù)平均最小概要模型

對于分布較為均勻的數(shù)據(jù)集，不同元素之間的沖突影響較大，可使用計數(shù)平均最小概要（countmean min sketch，CMM sketch）統(tǒng)計個數(shù)。CMM sketch假設(shè)元素均勻分布在散列數(shù)組中，則對于元素ct的噪音因子定義如式（15）所示：

元素的預(yù)測值需要減去噪音因子，元素概要預(yù)測值返回結(jié)果取各散列數(shù)組中的值的中位數(shù)，如式（16）所示：

使用上述哪種模型進行統(tǒng)計，由流數(shù)據(jù)分布特征和業(yè)務(wù)需求而定。在本文實驗中，由于數(shù)據(jù)單元標識產(chǎn)生的維度組合值是偏斜的，因此采用計數(shù)最小概要模型。

3.3 裁剪模型

由數(shù)據(jù)單元標識模型產(chǎn)生的維度組合是冪級增長的，如給定n維記錄r=(a1,a2,…,an,m,t)可以產(chǎn)生2n種維度的組合。隨著維度數(shù)量增加，產(chǎn)生的數(shù)據(jù)單元數(shù)量是巨大的。海量的維度組合會導(dǎo)致計數(shù)最小概要模型的沖突率變大，影響精確度。因此，需要對維度組合進行裁剪。

在數(shù)據(jù)立方體不同聚合操作類型中，對分布類型的操作如sum和count，祖先單元（低維數(shù)據(jù)單元）聚合了其下的所有后代單元（高維數(shù)據(jù)單元）的值。由此可得后代數(shù)據(jù)單元的上限（up bound）和下限（low bound）,從而可以推理出祖先單元值的范圍（up bound-low bound），如式（17）所示：

其中，祖先單元X可以由最小單元Xi集合組成MSP（most specific partition）[13]。對于數(shù)據(jù)單元X下的任意子空間g的上下限為式（18）所示：

因計數(shù)最小概要模型適合于數(shù)據(jù)濃度大的元素（如大于閾值τ）。如圖3所示，結(jié)合式（18），數(shù)據(jù)單元間的包含關(guān)系在count操作中體現(xiàn)出單調(diào)性，即Cac[count]>τ→Ca[count]>τ,Cc[count]>τ。其他較復(fù)雜代數(shù)聚合操作如avg的上下限不等式在參考文獻[13]中有所定義。

裁剪規(guī)則：對于分布型聚合操作，如祖先單元的測量值小于閾值，則所有它的后代單元的測量值必定小于閾值，因此對于計數(shù)最小概要模型可以裁剪掉所有后代單元。

3.4 改進統(tǒng)計模型

由于sketch cube使用計數(shù)最小概要模型，針對分布型聚合操作，結(jié)合裁剪規(guī)則，提出改進統(tǒng)計模型（ACM）。模型通過預(yù)測單維數(shù)據(jù)單元的測量值，達到減少維度組合的目的。如果測量值小于閾值，可以刪除所有包含該維度值的子孫單元。如在記錄r=(a,b,c)中，若 Ca[count]<τ，則[count]<τ。對于n維度的流數(shù)據(jù)中，先進行n次單維度統(tǒng)計，假設(shè)有k個單維數(shù)據(jù)單元測量值小于閾值，則可以裁剪的維度為2k，在對于每條流數(shù)據(jù)中可減少統(tǒng)計操作2k-n次。因為流數(shù)據(jù)中的維度值往往是稀疏的，因此裁剪模型可以排除大多數(shù)的維度組合。如果一維裁剪模型的裁剪效果不佳，可以使用二維或高維裁剪模型，方法類似。算法2結(jié)合裁剪方法的維度生成規(guī)則。維度裁剪規(guī)則如圖3所示。

圖3 維度裁剪規(guī)則

算法2 改進統(tǒng)計模型

輸入：流數(shù)據(jù)記錄 r=(a1,a2,…,ai,m,t)，τ

輸出：r所有維度組合標識。

①set<1-DCounter>←{}；

②<1-DCounter>←Cak[Count]>τ,1≤k≤i；

③(a1,a2,…,aj)←(a1,a2,…,ai)<1-DCounter>；

④(a1,a2,…,aj)→(n1,n2,…,nj)

⑤set=(n1,n2,…,nj)的所有組合；

⑥set←{}；

⑦for all x∈{}do

⑧←Pairing Function(x)；

⑨end for

⑩return；

本文使用ACM(m)表示模型取每個維度上頻率最高的m個維度值進行組合，可以減少計算模型的復(fù)雜度和存儲的空間，且能保證最后的高頻數(shù)據(jù)單元不會被裁剪掉。實驗給出了使用ACM模型在不同m參數(shù)值下的優(yōu)化效率。

3.5 時間序列索引描述

流數(shù)據(jù)具體有內(nèi)在時序性，對流數(shù)據(jù)挖掘用傾斜時間窗口（tilted-time window，TTW）[23]在不同時間粒度（multiple time granularities）上進行分析。如圖4所示，sketch cube按時間片段對元素組合進行統(tǒng)計把結(jié)果放入計數(shù)最小概要模型。sketch cube設(shè)計的存儲結(jié)構(gòu)可支持任意時間粒度的組合，其合并計算式如式（19）所示：

對于給定散列函數(shù)族，相同維度組合在不同時間中的映射地址相等，可單次掃描小顆粒時間累加得到大顆粒時間度量值。

圖4 時間窗口聚合操作

4 實驗結(jié)果與分析

目前已有流處理框架都是先存儲數(shù)據(jù)片段再進行實時的OLAP操作，和文本所提實時計算和預(yù)存儲模型的sketch cube不同。因此本文主要通過如下3個方面驗證方法的有效性和正確性。

·通過真實移動應(yīng)用日志記錄分析場景進行實驗。分析sketch cube框架在不同時間窗口、不同裁剪模型參數(shù)和不同存儲模型大小下的正確率、剪枝能力、框架吞吐效率；驗證參數(shù)之間的影響和整體框架的有效性。

·理論分析和比較sketch cube在存儲空間上和其他存儲模型的差異。

·描述使用storm開源流框架搭建sketch cube的實現(xiàn)方式，并給出一個應(yīng)用場景。

4.1 實驗環(huán)境和數(shù)據(jù)描述

實驗機器選擇4臺Dell服務(wù)器，16核IntelXeon 2.27 GHz，內(nèi)存為32 GB，硬盤為4 TB，操作系統(tǒng)為Cenos 6.3，Java版本為JDK7。因為系統(tǒng)每秒接收流數(shù)據(jù)在1萬條左右，采用Kafka和storm框架對數(shù)據(jù)進行處理，存儲模型保存在MongoDB中。

數(shù)據(jù)集合：測試數(shù)據(jù)集來源于真實的移動嵌入式SDK中采集的應(yīng)用記錄，每條記錄包含56個維度數(shù)值。本實驗選擇其中8個有代表性的維度進行OLAP統(tǒng)計，使用5%的均勻抽樣（uniform sampling）方法運行 1 h，其含義和維度值的基數(shù)見表1。

表1 移動數(shù)據(jù)信息結(jié)構(gòu)

對上述8個維度進行全立方體組合可得超過1017個數(shù)據(jù)單元。但通過分析可得，數(shù)據(jù)單元的分布是稀疏且偏斜的。在不同大小的時間窗口中，對維度組合的分布進行Zipfian的計算結(jié)果見表2。可得維度組合結(jié)果是偏斜的，因此，本實驗數(shù)據(jù)符合使用sketch cube框架的條件。

表2 抽樣移動數(shù)據(jù)分布

表2還表明數(shù)據(jù)是線性增加的，維度組合數(shù)量（DCIsize）隨時間增加而趨于穩(wěn)定，而偏斜因子和時間窗口長短無關(guān)。

表3給出了實驗涉及參數(shù)的取值范圍和缺省值。對于sketch cube所涉及的散列函數(shù)使用MurmurHash V3產(chǎn)生d個相互獨立的散列族，時間窗口以20 min為基本單位，ACM選擇m大小的裁剪模型，且在多組產(chǎn)生結(jié)果中進行分析和比較。

表3 實驗參數(shù)

表4給出了ACM模型在3個不同參數(shù)下和全量計算模型（full count model,FCM）在包括吞吐量、裁剪能力和模型準確率方面的比較結(jié)果。

4.2 sketch cube計算性能

本節(jié)討論ACM(m)裁剪方法在不同參數(shù)m下對sketch cube模型的剪枝能力。FCM表示統(tǒng)計全部維度組合，取m=(10,20,30,40,50)5個值，在3個不同時間長度中觀察ACM的輸出變化。如圖5所示，ACM模型在不同參數(shù)下都具有10倍左右的裁剪能力且很顯然參數(shù)值越小，保留的數(shù)據(jù)單元越少，裁剪能力越強。

表4 部分實驗結(jié)果

圖5 ACM剪枝實驗

接著，需要測試剪枝模型的有效性和可用性，即裁剪后的模型是否仍然可以滿足需求，而不會丟失很多有效數(shù)據(jù)。實驗取20 min數(shù)據(jù)，分別統(tǒng)計ACM不同參數(shù)下提取DCI數(shù)量和裁剪后維度組合數(shù)量。如圖6所示，ACM模型參數(shù)從10增加到50過程中，雖然DCI的數(shù)量有所提高，即計算得到的數(shù)據(jù)單元數(shù)量有明顯的增加，但是裁剪后維度組合出現(xiàn)次數(shù)卻基本相等。這說明數(shù)據(jù)是偏斜的，大量的高頻數(shù)據(jù)反復(fù)出現(xiàn)，而長尾的數(shù)據(jù)只有少量出現(xiàn)。因此，ACM（10）基本包含了所有高頻率的組合，在后續(xù)的框架構(gòu)建和查詢中，筆者使用ACM（10）作為裁剪模型。

圖6 ACM裁剪模型效率

4.3 存儲空間和誤差

使用計數(shù)最小概要模型的sketch cube中保存的元素統(tǒng)計數(shù)據(jù)值要大于元素實際值，本實驗使用平均百分比誤差（mean percentage error，MPE）統(tǒng)計計數(shù)的準確率。計算式如下：

其中，at是實際值，ft是預(yù)測值，n是測試數(shù)據(jù)數(shù)量。

圖7展示sketch cube中的存儲空間大小和ACM參數(shù)對MPE的影響。取10 min數(shù)據(jù)，在不同存儲寬度中比較4類模型的MPE值。ACM（m）中m越小，裁剪能力越強，模型準確率越高。隨著存儲空間的增大(即w參數(shù)的變大)，所有模型的準確率都有所提高，這是因為存儲空間的增加可以減少散列的碰撞概率，從而提高模型的準確率，但ACM整體準確率在任意存儲模型下都較FCM有明顯提高。

圖7 w和ACM(n)對MPE的影響

圖8 顯示存儲空間、結(jié)果集大小和MPE之間的關(guān)系。top-N從大到小排序，從橫軸看，頻率越高的數(shù)據(jù)單元，其MPE值越小，準確率越高。如在1 021寬度的存儲模型中，ACM （10）模型對前20的高頻數(shù)據(jù)單元的統(tǒng)計錯誤率為1%左右，而FCM的錯誤率超過20%。隨著top-N的變大，MPE值也上升，說明sketch cube產(chǎn)生的數(shù)據(jù)單元是偏斜的。在不同的系統(tǒng)應(yīng)用中，可以選擇合適的存儲空間大小和計算結(jié)果大小，如需要計算的top-N較大，則需要使用較小的ACM和較大的存儲空間w。

4.4 吞吐能力和計算時間比較

接著計算模型的吞吐計算能力，因為運行時間受分布式框架節(jié)點數(shù)據(jù)和數(shù)據(jù)傳輸影響較大，因此吞吐能力測試在單節(jié)點上進行。取170 880條數(shù)據(jù)，在單節(jié)點中測量DCI計算時間和sketch cube計算時間。DCI時間表示計算數(shù)據(jù)單元標識集合的時間，sketch時間表示計算存入二維數(shù)組的偏移值的時長。測試取w=1 021。如圖9所示，折線表示DCI集合的大小變化。從DCI運行時間和DCI集合變化曲線看，兩者之間成正比關(guān)系，即模型的裁剪能力越強，DCI集合越小，DCI運行時間越短。對于任意模型，DCI運行時間遠大于sketch計算時間。這些結(jié)論將被用于sketch cube模型的實現(xiàn)中。

圖8 w和ACM(m)對MPE的增長趨勢

圖9 不同模型的運行時間

4.5 實時挖掘效率

上述實驗過程把每條記錄可能的維度組合保存在類線性空間中。本實驗將統(tǒng)計數(shù)據(jù)存儲于MongoDB中，使用應(yīng)用ID和時間窗口對數(shù)據(jù)檢索。通過時間序列索引模型可知sketch cube支持任意時間窗口的組合。實驗取3個不同的應(yīng)用做實時查詢，其效率分析見表5。

表5 查詢效率分析

每個應(yīng)用分別以10、20、30 min為長度，隨機選擇高維度值產(chǎn)生數(shù)據(jù)單元，進行OLAP查詢。數(shù)據(jù)大小表示查詢所涉及應(yīng)用的日志數(shù)據(jù)大小。運行時間包括用時間序列索引找到相關(guān)的存儲單元，通過數(shù)據(jù)單元標識模型產(chǎn)生唯一自然數(shù)標識，使用最小計數(shù)模型找到該數(shù)據(jù)單元的估計值所需的時間總和。從運行時間看，因為數(shù)據(jù)已經(jīng)做了索引和統(tǒng)計，時間片長短和數(shù)據(jù)量大小對查詢時間變化較小。同時查詢時間都在毫秒級，因此可以滿足實時查詢的需求。

4.6 空間效率

由于目前已有的對流數(shù)據(jù)的OLAP框架都是基于先存儲數(shù)據(jù)，再進行分析的過程，和本文所述的實時統(tǒng)計框架有所不同。因此，本節(jié)主要理論分析數(shù)據(jù)在HashMap和sketch cube中的存儲空間對比。假設(shè)，所有數(shù)據(jù)存儲的基本單元都是整型，則HashMap的結(jié)構(gòu)可以表示為HashMap，key為維度計數(shù)器產(chǎn)生的數(shù)據(jù)單位標識，value為數(shù)據(jù)單元的統(tǒng)計個數(shù)。因此，對于每個數(shù)據(jù)單元需要2個Integer大小空間存儲，整體所需存儲空間為2×DCI個Integer。而使用sketch cube的存儲大小固定為w×d個Integer。例如，在表4中可得，ACM(10)在 20 min產(chǎn)生的 DCI為 15 896，則 HashMap的空間為 15 896×2=31 792個Integer，本實驗中 sketch cube大小為 1 021×5=5 105個Integer。因此，壓縮率為5 105/31 792=0.16。同理，可得ACM（30）和 ACM（50）壓縮率分別為 0.028和 0.022。由此可得，隨著ACM裁剪效率的下降，需要保存的數(shù)據(jù)單元數(shù)量增加，壓縮率會明顯降低，空間使用效率提高。

5 sketch cube平臺構(gòu)建過程

5.1 系統(tǒng)結(jié)構(gòu)

本節(jié)主要介紹使用storm開源流框架搭建sketch cube的過程。storm框架使用拓撲來描述不同計算節(jié)點之間的關(guān)系，根據(jù)前文的模塊定義，把sketch cube的不同模塊功能映射到storm的bolt中，且需要根據(jù)計算節(jié)點之間的I/O吞吐率和CPU計算量，調(diào)整節(jié)點的并發(fā)度，以達到系統(tǒng)整體的平衡。系統(tǒng)部署在第4.1節(jié)描述的4臺服務(wù)器中，其結(jié)構(gòu)如圖10所示。

圖10 storm實現(xiàn)sketch cube框架

系統(tǒng)分為3個部分，數(shù)據(jù)源負責(zé)收集相關(guān)多維度流數(shù)據(jù)信息，并保存在Kafka框架中；storm框架使用5個不同的計算節(jié)點，分別為輸入數(shù)據(jù)接收、字典化處理、DCI計算，存儲節(jié)點計算和存儲節(jié)點。處理后的數(shù)據(jù)被保存在MongoDB數(shù)據(jù)庫中。實時挖掘?qū)樱╩ining layer）從MongoDB中獲得壓縮后的數(shù)據(jù)單元統(tǒng)計值，并且進行相關(guān)在線分析模塊（OLAM）操作得到結(jié)果返回給用戶。

5.2 相關(guān)示例

對例1中的場景，給定應(yīng)用名稱和時間片段，實時統(tǒng)計不同的數(shù)據(jù)單元下的度量值，本實驗使用count計算數(shù)據(jù)單元的大小，最后選擇和該時段這個應(yīng)用最相關(guān)的top-50個數(shù)據(jù)單元。輸出所在數(shù)據(jù)單元的維度值。對于給定應(yīng)用appi，對于數(shù)據(jù)單元c的相關(guān)度(correlation)可以用式（21）所示：

其中，m表示數(shù)據(jù)單元度量值。

如對于流數(shù)據(jù)立方體c=((Wi-Fi,hz,Samsung),20140510081559)，包含應(yīng)用A的條數(shù)為200條，應(yīng)用B為300條，則

對上述top-50的數(shù)據(jù)單元相關(guān)屬性值進行統(tǒng)計，按每個屬性值出現(xiàn)次數(shù)多少排序，并產(chǎn)生如圖11所示的標簽云圖像。從圖11可得，不同時間窗口下的標簽云發(fā)生變化，這表明不同時間段的應(yīng)用受眾群體在發(fā)生變化。該類圖像報表可以更好地幫助用戶實時定位目標客戶。

圖11 標簽云推薦

6 總結(jié)和展望

本文研究一種對海量流數(shù)據(jù)進行OLAM操作的框架sketch cube：

·提出數(shù)據(jù)單元標識模型及其改進算法；

·引入計數(shù)最小概要模型保存統(tǒng)計結(jié)果，并給出其適用場景；

·提出基于上下限的數(shù)據(jù)單元裁剪方法，提高存儲效率和準確率；

·基于傾斜時間窗口的索引模型可快速計算任意時間片中的統(tǒng)計結(jié)果；

·真實數(shù)據(jù)集實驗中，比較了相關(guān)參數(shù)對模型的影響，體現(xiàn)模型的優(yōu)越性和可用性。

sketch cube只支持流數(shù)據(jù)分布型的聚合操作，在下一步工作中，將研究較為復(fù)雜的代數(shù)型和整體型聚合操作在流數(shù)據(jù)sketch cube模型中的應(yīng)用。同時把計算過程中的性能瓶頸通過合理設(shè)計拓撲結(jié)構(gòu)分散到不同機器節(jié)點中，以提高流數(shù)據(jù)的處理能力和穩(wěn)定性。

1 Aggarwal C C.An Introduction to Data Streams.Data Streams.Springer US,2007

2 Hellerstein J M,Haas P J,Wang H J.Online aggregation.ACM SIGMOD Record,1997,26(2):171～182

3 Zhang X,Chou P L,Dong G.Efficient computation of iceberg cubes by bounding aggregate functions.IEEE Transactions on Knowledge and Data Engineering,2007,19(7)

4 Chen Y,Do ng G,Han J,et al.Multi-dimensional regression analysis of time-series data streams.Proceedings of the 28th International Conference on Very Large Data Bases,VLDB Endowment,Hong Kong,China,2002:323～334

5 胡文瑜，孫志揮，吳英杰.數(shù)據(jù)挖掘取樣方法研究.計算機研究與發(fā)展,2009,48(1)：45～54

6 De Rougemont M,Cao P T.Approximate answers to OLAP queries on streaming data warehouses.Proceedings of the Fifteenth International Workshop on Data Warehousing and OLAP,Maui,Hi,USA,2012:121～128

7 Babcock B,Shinath B,Mayur D,et al.Models and issues in data stream systems.Proceedings of the 21st ACM Symposium on PrinciplesofDatabase Systems,Madison,Wiscomsin,USA,2002:1～16

8 Chandrasekaran S,Cooper O,Deshpande A.TelegraphCQ:continuous dataflow processing for an uncertain world.Proceedings of the Conf on Innovative Data Systems Research,Asilomar,CA,USA,2003

9 Hetal T,Nikolay L,Hamid M,et al.SMM:a data stream management system for knowledge discovery.Proceedings of International Conference on Data Engineering, Hannover,Germany,2011:757～768

10 Rosenberg A L.Efficient pairing functions-and why you should care.International Journal of Foundations of Computer Science,2003,14(1):3～17

11 Zhang D,Zhai C,Han J,et al.Topic modeling for OLAP on multidimensional text database:topic cube and its applications.Stat Anal Data Min,2009,2(56):378～395

12 Ding B,Zhao B,Lin C,et al.Topcells:keyword-based search of top-k aggregated documents in text cube.Proceedings of International Conference on Data Engineering (ICDE),Long Beach,USA,2010:381～384

13 Lin C,Ding B,Han J,et al.TextCube:computingirmeansures for multidimensional text database analysis.Proceedings of the 8th IEEE International Conference on Data Mining(ICDM),2008:905～910

14 Liu X,Tang K Z,Hancock J,et al.A text cube approach to human,social and cultural behavior in the Twitter stream.LNCS 7812,2013:321～330

15 Cuzzocrea A.Retrieving accurate estimates to OLAP queries over uncertain and imprecise multidimensional data streams.Proceedings of the 23rd International Conference on SSDBM,Portland,OR,USA,2011

16 Aggarwal C C.Managing and Mining Sensor Data.New York:Springer US,2013

17 張進，鄔江興，劉勤讓.4種技術(shù)型Bloom Filter的性能分析與比較.軟件學(xué)報，2010，21(5):1098～1114

18 Cormode G,Hadjieleftheriou M.Finding frequent items in data streams.Proceedings of the VLDB Endowment,2008,1(2):1530～1541

19 Considine J,Hadjieleftheriou M,Li F,et al.Robust approximate aggregation in sensor data management systems. ACM Transactions on Database Systems(TODS),2009,34(1)

20 Han J,Kamber M,Pei J.Data Mining Concepts and Techniques.Elsevier Ltd,2012

21 Cormode G,Muthukrishnan S.An improved data stream summary: the count-min sketch and its applications. J Algorithms,2005,55(1):58～75

22 Cormode G,Muthukrishnan S.Summarizing and mining skewed data streams.Proceedings of SDM,Trondheim,Normay,2005

23 Giannella C,Han J,Pei J,et al.Mining frequent patterns in data streams at multiple time granularities.Next Generation Data Mining,2003(212):191～212