HSSM:一種流數(shù)據(jù)分層次模最大化方法

張奮翔　陳華輝　錢江波　董一鴻

(寧波大學(xué)信息科學(xué)與工程學(xué)院　浙江寧波　315211)

?

HSSM:一種流數(shù)據(jù)分層次模最大化方法

張奮翔陳華輝錢江波董一鴻

(寧波大學(xué)信息科學(xué)與工程學(xué)院浙江寧波315211)

(zhang_fenxiang@163.com)

從大規(guī)模數(shù)據(jù)中“摘要”出最能滿足效用函數(shù)收益的有限個(gè)數(shù)據(jù)對(duì)象，可以被歸納為次模函數(shù)最大化問題.并行過濾算法在滿足流數(shù)據(jù)訪問次數(shù)限制與實(shí)時(shí)響應(yīng)的條件下，通過分布式篩選的方式實(shí)現(xiàn)次規(guī)模最大化，但在提升摘要速率時(shí)效用函數(shù)收益損失較大.提出一種流數(shù)據(jù)分層次模最大化算法HSSM，在僅訪問一次數(shù)據(jù)集的條件下，采用流水并行的分布式處理框架得到接近于標(biāo)準(zhǔn)貪心算法的次模函數(shù)收益，同時(shí)改進(jìn)HSSM通過累積摘要的壓縮存儲(chǔ)、分層過濾低增益對(duì)象提升摘要速率.該方法在數(shù)據(jù)摘要問題的相關(guān)領(lǐng)域具有廣泛的應(yīng)用性，如文檔集中代表性文章的選取、數(shù)據(jù)集中心點(diǎn)選取等.實(shí)驗(yàn)結(jié)果顯示，分布式算法Spark-HSSM+對(duì)比于傳統(tǒng)的算法在運(yùn)行速率上達(dá)到與摘要規(guī)模k成k2正比例關(guān)系的提升.而相對(duì)于其他分布式算法，其實(shí)驗(yàn)效用收益與理論最差收益都更接近于貪心算法.

流次模最大化；分層模型；流水并行；數(shù)據(jù)摘要；Spark分布式平臺(tái)

在信息飛速增長(zhǎng)的時(shí)代，經(jīng)常需要從海量數(shù)據(jù)或僅能訪問一次的流數(shù)據(jù)中“摘要”出一個(gè)較小的且具有代表性的數(shù)據(jù)集[1-2]，例如，熱點(diǎn)文章及熱門微博推薦[3-4]、文檔中概要語句提取[5]、數(shù)據(jù)集中心點(diǎn)選取[6]、數(shù)據(jù)集中噪聲的查找[7]和社交網(wǎng)絡(luò)中最大影響力節(jié)點(diǎn)的選取[8]等.摘要方法通常使用某種效用函數(shù)或稱收益函數(shù)(utility function)來評(píng)價(jià)所選子集的“代表性”是否達(dá)到目的.數(shù)據(jù)對(duì)象在摘要過程中往往具有收益遞減的所謂次模特性[9].次模最大化即研究如何利用該次模特性摘要出一個(gè)小規(guī)模對(duì)象集合，實(shí)現(xiàn)對(duì)原始數(shù)據(jù)集的主要特征概括.

圍繞次模最大化問題已有不少的相關(guān)研究.最先由Nemhauser等人[9]提出使用標(biāo)準(zhǔn)貪心算法在有限次訪問數(shù)據(jù)集的條件下，得到具有最低收益保證的摘要結(jié)果；Mirzasoleiman等人[10]設(shè)計(jì)出適用于處理靜態(tài)大規(guī)模數(shù)據(jù)集的主從分布式摘要算法，在運(yùn)行效率上對(duì)標(biāo)準(zhǔn)貪心算法做出改進(jìn)；Gomes等人[11]針對(duì)無法二次訪問的動(dòng)態(tài)流數(shù)據(jù)，提出了通過有效維護(hù)一個(gè)指定大小的對(duì)象集合完成近似最大化收益摘要，但存在流數(shù)據(jù)實(shí)時(shí)響應(yīng)速率慢的不足；Badanidiyuru等人[12]使用離散化預(yù)估最優(yōu)收益的方法設(shè)計(jì)有限數(shù)量的過濾器，通過并行篩選的思想提升流數(shù)據(jù)實(shí)時(shí)摘要速率.

Badanidiyuru等人雖然在摘要的實(shí)時(shí)性方面提出改進(jìn)，但存在摘要結(jié)果收益降低的缺陷.針對(duì)該問題，本文提出一種流數(shù)據(jù)分層次模最大化摘要算法(hierarchical streaming submodular maximization, HSSM)，采用分層流水并行和逐層摘要的策略實(shí)現(xiàn)分布式運(yùn)算與次模收益最大化.該方法僅需要訪問一遍數(shù)據(jù)集，即可得到規(guī)模為k且效用收益至少滿足1(2-1k)倍最優(yōu)解的摘要結(jié)果.對(duì)每批數(shù)據(jù)量為v的流數(shù)據(jù)摘要，僅需要O(v+k)的時(shí)間開銷即可完成更新.該方法摘要的理論與實(shí)驗(yàn)收益優(yōu)于其他并行算法而略低于貪心算法，但在運(yùn)行效率上較貪心算法有很大的提高.實(shí)驗(yàn)證明：本文算法可以有效地解決流數(shù)據(jù)的次模函數(shù)最大化問題.

1　流次模最大化問題

1.1次模函數(shù)最大化

從規(guī)模為n的數(shù)據(jù)集合O中選取大小為k的對(duì)象集合S作為摘要.效用函數(shù)f(S)用于表示摘要結(jié)果S對(duì)數(shù)據(jù)集O的效用收益，不同應(yīng)用場(chǎng)合可有不同的效用函數(shù).如1.2節(jié)的例子分別使用基于覆蓋率與距離損失函數(shù)的效用函數(shù)，由以下定義得知，該效用函數(shù)均為次模函數(shù).

定義1. 次模函數(shù).有限集合O和定義在其冪集2O→上的單調(diào)實(shí)函數(shù)f，稱f為次模函數(shù)當(dāng)且僅當(dāng)O的任意2個(gè)子集A,B及元素e，A?B?O，e∈OB，滿足：

f(A∪{e})-f(A)≥f(B∪{e})-f(B).

(1)

用Δf(e|A)=f(A∪{e})-f(A)表示元素e對(duì)集合A的效用增益(marginal gain)，式(1)說明次模函數(shù)的收益遞減性質(zhì)：若其他元素被先于元素e添加至集合A，將導(dǎo)致元素e的效用增益降低，即Δf(e|B)≤Δf(e|A).

定義2. 次模函數(shù)收益最大化(簡(jiǎn)稱次模最大化).從數(shù)據(jù)集O中萃取出有限規(guī)模為k的代表性子集S，通過次模函數(shù)的收益遞減特性選取近似最優(yōu)解，使得S滿足效用收益f(S)最大化，該過程稱為次模最大化：

(2)

貪心算法是次模最大化的代表，其通過k輪迭代添加效用增益最大元素e∈OA至集合A，使得規(guī)模為k的集合A效用收益盡可能最大化，并通過次模最大化特性證明其在最差情況下的收益保證.

定義3. 摘要.基于效用評(píng)價(jià)函數(shù)從集合O中選取一個(gè)規(guī)模較小且具有高效用收益的子集S，則稱子集S為集合O的摘要.

1.2次模最大化的典型問題

本文主要關(guān)心持續(xù)不斷到來的流數(shù)據(jù)或僅能訪問一遍的大規(guī)模數(shù)據(jù)摘要問題，下面是2個(gè)典型例子.

1.2.1 基于覆蓋率的摘要問題

(3)

摘要集合應(yīng)盡可能覆蓋數(shù)據(jù)集的總信息收益f(O)，以覆蓋率(式(3))表示摘要S包含數(shù)據(jù)集O的信息收益比例[1,13].在逐個(gè)選取摘要對(duì)象的過程中，覆蓋率函數(shù)滿足ΔCov(e|Si-1)≥ΔCov(e|Si)的次模特性，故該問題是次模最大化問題.

1.2.2基于距離損失函數(shù)的中心點(diǎn)選取問題

求解k-medoid(k-中心點(diǎn))問題是典型的數(shù)據(jù)挖掘應(yīng)用[14-15]，通過最小距離損失選取若干個(gè)對(duì)象為數(shù)據(jù)集中心點(diǎn)(如聚類中心等).其評(píng)價(jià)標(biāo)準(zhǔn)是最小化中心點(diǎn)與其他對(duì)象的距離之和，對(duì)于一個(gè)數(shù)據(jù)集O，使用距離函數(shù)(如歐氏距離公式：d(x,x′)=‖x-x′‖)表示集合O中對(duì)象間距離：O×O→.該問題的摘要損失函數(shù)L被定義如下[11]：

(4)

通過輔助對(duì)象e0=0，即可將L轉(zhuǎn)換為具有次模特性的距離損失函數(shù)：

f(S)=L({e0})-L(S∪{e0}).

(5)

1.3次模最大化問題的相關(guān)算法

1.3.1 標(biāo)準(zhǔn)次模最大化算法

Nemhauser等人[9]提出的Standard-Greedy算法(及與次模相關(guān)的標(biāo)準(zhǔn)貪心算法[16-17])在解決次模最大化問題中給出近似最優(yōu)解方案.該算法每次迭代訪問數(shù)據(jù)集時(shí)，將滿足最大化邊際收益的對(duì)象添加到摘要集合中：

Si=Si-1∪{arg max Δf(e|Si-1)}.

(6)

文獻(xiàn)[9]證明了在最壞情況下，該算法依然可以給出效用收益滿足大于(1-1e)倍的最優(yōu)解收益，并且沒有其他方法能在同樣訪問量級(jí)上保證更優(yōu)的最差解收益.

1.3.2流次模最大化算法

與靜態(tài)數(shù)據(jù)處理不同，流數(shù)據(jù)具有動(dòng)態(tài)增長(zhǎng)的特點(diǎn)(搜索引擎Bing每10 min就產(chǎn)生超過1 TB的數(shù)據(jù)[18]).流數(shù)據(jù)摘要算法的提出是為了解決靜態(tài)摘要方法在多次訪問數(shù)據(jù)集方面的不足.

流數(shù)據(jù)的摘要算法是在有限的時(shí)間及內(nèi)存空間開銷條件下得到近似最優(yōu)收益的解決方案，主要包含以下3個(gè)難點(diǎn)：

1) 摘要算法訪問數(shù)據(jù)集的總次數(shù)，即非特定條件下流數(shù)據(jù)不能被二次訪問.

2) 算法完成摘要的運(yùn)行時(shí)間.流數(shù)據(jù)處理要求極高的實(shí)時(shí)性，因此摘要完成的運(yùn)行時(shí)間是評(píng)價(jià)流算法符合需要的重要指標(biāo)之一.

3) 算法最差解的摘要收益.流算法通常由于條件限制而給出近似解，故必須保證算法在最差情況下解收益的可接受性.

Gomes等人提出的Stream-Greedy算法[11]通過對(duì)比替換的方式，維持摘要S的效用收益最大化：若存在新對(duì)象oi替換b∈Sk，使得摘要S的效用收益增加，則替換Sk=Sk∪{oi}.該方法在解決流次模摘要問題的同時(shí)仍存在2方面缺陷：1)在數(shù)據(jù)增益非均勻的情況下，該算法的摘要收益僅為1k最優(yōu)解；2)該算法對(duì)于分批規(guī)模為v的流數(shù)據(jù)更新時(shí)間復(fù)雜度為Ω(kv)，因此無法在短時(shí)間完成對(duì)大規(guī)模摘要(k很大)的更新.

1.3.3分布式次模最大化算法

為了解決流算法更新時(shí)間開銷大的難題，相應(yīng)的分布式解決方案被提出.Mirzasoleiman等人[10]與Kumar等人[19]分別提出解決次模函數(shù)最大化問題的分布式算法.其中，文獻(xiàn)[19]的Greedy-Scaling算法要求已知單對(duì)象最大增益值 (即摘要至少訪問2次數(shù)據(jù)集)且未給出具體實(shí)現(xiàn)，故本文未對(duì)其進(jìn)行對(duì)比.

Badanidiyuru等人[12]提出具有最差收益保證的快速分布式次模摘要方法(Sieve-Stream)，實(shí)現(xiàn)以當(dāng)前單個(gè)對(duì)象的最大收益值m及離散系數(shù)ε預(yù)估出最優(yōu)解集合T={(1+ε)i|m≤(1+ε)i≤k×m}.對(duì)于新數(shù)據(jù)e，通過i個(gè)以ti∈T作為目標(biāo)收益的過濾器并行篩選：當(dāng)摘要規(guī)模|S|

文獻(xiàn)[12]是具有最低收益保證且滿足分布式快速摘要的次模最大化算法，但該算法在流數(shù)據(jù)篩選過程中缺陷.一方面，若指定摘要規(guī)模為k，由于流數(shù)據(jù)具有增益不確定性(因此需要最差解保證)，使得大多數(shù)過濾器通常處于非飽和狀態(tài)，故摘要并沒有達(dá)到收益最大化；另一方面，對(duì)于因單對(duì)象最大收益增大而新產(chǎn)生的過濾器，由于該過濾器無法訪問已處理數(shù)據(jù)(流數(shù)據(jù)在非特定情況下只能訪問一次)，將導(dǎo)致許多高收益的對(duì)象被忽略處理.實(shí)驗(yàn)表明，該算法在實(shí)際摘要問題中的確存在效用收益明顯低于大部分次模摘要算法的現(xiàn)象.因此，本文旨在提出新的分布式次模最大化算法，同時(shí)滿足盡可能高的效用收益.

2　流數(shù)據(jù)分層次模最大化算法

由于傳統(tǒng)次模最大化問題的研究無法解決流數(shù)據(jù)摘要問題；同時(shí)，現(xiàn)存的流算法在提高摘要效率的同時(shí)存在降低摘要收益或最低收益保證過低的問題.因此，本文提出基于次模最大化的分層流摘要算法旨在解決3個(gè)難點(diǎn)：1)算法可以適用于解決流數(shù)據(jù)摘要問題；2)通過次模特性使得摘要獲得盡可能高的收益及滿足最低收益保證；3)設(shè)計(jì)分布式處理框架旨在提高摘要速率.

2.1分層次模最大化

本節(jié)設(shè)計(jì)一種新的并行處理框架用于解決流數(shù)據(jù)摘要在分布式處理方面的難題.由流水線并行(pipeline)[20]處理技術(shù)啟發(fā)，通過分割次模增益的方法提出分層次模最大化算法HSSM.

根據(jù)1.1節(jié)給出的定義，為使摘要獲得盡可能高的收益，次模最大化方法通過k輪迭代添加最大增益對(duì)象組成摘要集合S.由于分批到來的流數(shù)據(jù)不能夠一次性全部訪問，因此通過分層保留已訪問數(shù)據(jù)的逐輪次優(yōu)摘要對(duì)象hi來替代全局的最高增益對(duì)象.新數(shù)據(jù)對(duì)次優(yōu)累積摘要的效用增益為：Δf(ei|Sj)=f(Sj∪{ei})-f(Sj)，Sj={h1,h2,…,hj}.若數(shù)據(jù)ei的增益高于某輪最大增益對(duì)象hj時(shí)，替換hj與ei，進(jìn)而實(shí)現(xiàn)流數(shù)據(jù)的摘要過程滿足次模最大化.

由于同一時(shí)刻的數(shù)據(jù)增益篩選過程相互獨(dú)立(即數(shù)據(jù)對(duì)象ei對(duì)于不同的累積摘要Sj需被計(jì)算k次)，進(jìn)而通過如圖1所示的流水并行模式分層進(jìn)行數(shù)據(jù)增益對(duì)比.其中，時(shí)刻Ti的數(shù)據(jù)在頂層V(累積摘要為空時(shí))完成增益對(duì)比；與此同時(shí)，其余層也分別基于不同的累積摘要Sj對(duì)數(shù)據(jù)ei-j+1進(jìn)行的增益篩選.

Fig. 1　Data processing in pipeline mode.圖1　流水并行模式處理數(shù)據(jù)

總體來說，傳統(tǒng)的迭代算法使得規(guī)模為n的數(shù)據(jù)集被訪問k輪后完成摘要篩選工作，其時(shí)間復(fù)雜度為Ω(nk).而流水并行的方法通過在連續(xù)的個(gè)時(shí)間單位比較待處理數(shù)據(jù)，進(jìn)而實(shí)現(xiàn)基于不同累積摘要的多次增益篩選，使得總處理時(shí)間減少為Ω(n+k)，一般而言v?k，故摘要的總時(shí)間復(fù)雜度約為Ω(n).

結(jié)合流水并行模式的分層摘要算法HSSM如圖2所示，其對(duì)單個(gè)數(shù)據(jù)對(duì)象處理的主要步驟如下：

1) 算法從流數(shù)據(jù)中逐一獲取待處理數(shù)據(jù)ei，并將該數(shù)據(jù)作為輸入傳入首層.

2) 構(gòu)建分層(圖1中Layerl)數(shù)據(jù)結(jié)構(gòu)：el表示第l層的待處理對(duì)象；Sl-1表示第l層之上的累積摘要結(jié)果：初始化S0對(duì)象為空，逐層完成增益篩選后，更新Sl=Sl-1∪{hl}并傳遞給l+1層完成增益累積；摘要維持對(duì)象hl是自身與待處理對(duì)象el基于累積摘要Sl-1對(duì)比后的高收益者：

(7)

3) 通過自頂(第1層)向下的方式，逐層完成數(shù)據(jù)el與維持對(duì)象hl的篩選.根據(jù)增益比較結(jié)果輸出

4) 算法在處理完所有數(shù)據(jù)后，通過合并各Layerl中摘要維持對(duì)象組成規(guī)模為k的摘要結(jié)果S={h1,h2,…,hk}.

算法1完成了分層模型中Layerl的數(shù)據(jù)篩選工作，行①②為摘要維持對(duì)象與待處理數(shù)據(jù)的增益計(jì)算，其中f為任意的效用函數(shù)；行③～⑨首先將待處理數(shù)據(jù)與摘要維持對(duì)象進(jìn)行增益對(duì)比，對(duì)比的結(jié)果決定是否更新摘要維持對(duì)象，同時(shí)返回下層待處理數(shù)據(jù)與累積摘要.

Fig. 2　The processing of per object in HSSM.圖2　流數(shù)據(jù)對(duì)象在HSSM算法中的順序處理流程

算法1. 增益篩選算法Filter(ei,hl,Sl-1).

輸入：待處理數(shù)據(jù)ei、摘要維持對(duì)象hl、累積摘要Sl-1；

輸出：下層待處理對(duì)象ei+1、本層摘要維持對(duì)象hl、下層累積摘要Sl.

① 計(jì)算維持對(duì)象hl增益:g_h=Δf(hl|Sl-1)；

② 計(jì)算待處理對(duì)象ei增益:g_e=Δf(ei|Sl-1)；

③ ifg_e>g_h

⑤tmp=hll,hl=ei；

⑥ return [tmp,hl,Sl-1∪{hl}]；

⑦ else

⑨ return [ei,hl,Sl-1∪{hl}].

綜上所述，HSSM算法通過流水線并行的方式分層解決流數(shù)據(jù)次模最大化摘要問題，同時(shí)該算法通過指定分層數(shù)量k確定摘要結(jié)果規(guī)模.

2.2HSSM算法的收益分析

HSSM算法與其他次模最大化方法都無法保證摘要結(jié)果在所有情況下都達(dá)到最優(yōu)解收益.本節(jié)旨在分析該算法在最差情況下的摘要效用收益保證.

定理1. 在摘要維持對(duì)象(h1,h2,…,hk)未改變的情況下(即被過濾對(duì)象ek=ei=e1)，過濾對(duì)象ek滿足Δf(ek|Sk-1)≤f(Sk)k.

證明. 在HSSM算法中，設(shè)hi是第i層的摘要維持對(duì)象，i=1,2,…,k，滿足收益遞減特性：

Δf(h1|S0)≥Δf(h2|S1)≥…≥Δf(hk|Sk-1).

(8)

被第i層過濾的數(shù)據(jù)對(duì)象ei，其增益小等于該層摘要維持對(duì)象：Δf(ei|Si-1)≤Δf(hi|Si-1).特別地，當(dāng)該對(duì)象被所有層過濾時(shí)，其增益小于式(8)中最小增益維持對(duì)象:Δf(ei|Sk-1)≤Δf(hk|Sk-1).

由式(8)同時(shí)得出，第i層摘要維持對(duì)象hi的收益小于等于本層累積摘要的平均收益:Δf(hi|Si-1)≤f(Si)i，且平均累積收益同時(shí)滿足逐層遞減特性：f(S1)1≥f(S2)2≥…≥f(Sk)k.故推出被過濾對(duì)象ek在所有層被過濾時(shí)，滿足增益小等于累積摘要集合的最小平均收益:

Δf(ek|Sk-1)≤Δf(hk|Sk-1)≤f(Sk)k.

證畢.

證畢.

定理3. HSSM算法的摘要收益f(Sk)對(duì)比最優(yōu)解S*的收益f(S*)，滿足f(Sk)≥1(2-1k)×f(S*).

證明.

易得知：最優(yōu)解S*與摘要Sk的收益交集不大于Sk的效用收益；同時(shí)摘要Sk中所有不被包含的效用收益至多為定理1中被HSSM算法過濾的增益；進(jìn)而通過定理2中第k層過濾對(duì)象的增益損失上界，推導(dǎo)出摘要Sk的最低效用收益.

證畢.

定理1表明被過濾的對(duì)象其增益不大于所選摘要S的平均增益；定理2表明，即使摘要S改變，已被過濾的對(duì)象增益也不會(huì)超過新摘要S′的平均增益；定理3得知，基于分層思想的次模最大化方法，在最壞情況下仍可以得到大于1(2-1k)最優(yōu)解的收益.

2.3HSSM算法的改進(jìn)

進(jìn)一步分析HSSM算法，存在3點(diǎn)可改進(jìn)之處：

1) HSSM算法中的分層模型存在收益遞減特性，使得底層出現(xiàn)大量滿足Δf(ei|Si-1)<σ的低增益對(duì)象，存在重復(fù)計(jì)算效用收益的問題；

2) HSSM算法通過式(7)進(jìn)行數(shù)據(jù)增益對(duì)比的過程中，當(dāng)累積摘要集合規(guī)模 (即|Si-1|≤k)較大時(shí)，將導(dǎo)致效用收益計(jì)算f(Si-1)的時(shí)間開銷過大；

3) 摘要規(guī)模(k)較大時(shí)可能導(dǎo)致分層數(shù)量過多.

本節(jié)對(duì)這3方面不足提出進(jìn)一步改進(jìn)的做法.

2.3.1通過閾值過濾低增益對(duì)象

針對(duì)效用函數(shù)收益計(jì)算的時(shí)間開銷問題，HSSM算法提出基于次模函數(shù)最大化收益遞減特性的最低增益閾值過濾方法，使得各層不再將增益小于σ的待處理對(duì)象ei傳輸至下一層，進(jìn)而減少了低增益對(duì)象的增益計(jì)算開銷.

σ=min(μ,Δf(hk|Sk-1)).

2.3.2效用向量替代累積摘要

圍繞次模最大化方法中存在效用函數(shù)增益計(jì)算問題，大多數(shù)算法通過遍歷累積摘要集合Si與新增數(shù)據(jù)e的方法得到效用函數(shù)收益差值：Δf(e|Si)=f(Si∪{e})-f(Si).其中，計(jì)算效用收益f(Si)的集合遍歷開銷與摘要規(guī)模|Si|成正比例關(guān)系，為了進(jìn)一步減少該計(jì)算開銷，本文提出一種使用效用向量替換累積摘要Si的信息壓縮方法.

Fig. 3　k-medoid select problem with utility vector.圖3　效用向量在中心點(diǎn)選取問題中的應(yīng)用

以圖3的中心點(diǎn)選取問題為例，式(4)為該問題的次模效用函數(shù).從圖3(a)的12個(gè)數(shù)據(jù)點(diǎn)中選取3個(gè)中心點(diǎn)，使得各點(diǎn)到中心點(diǎn)的距離之和最??；初始化摘要集合為空；圖3(b)首先選取到各點(diǎn)距離損失最小的點(diǎn)E添加至摘要S；圖3(c)選取基于累積摘要S1的第2輪最大收益對(duì)象點(diǎn)L；第3輪中，累積摘要S2的效用收益為圖3(d)中點(diǎn)E與點(diǎn)L到其余各點(diǎn)的最近距離(同樣的，對(duì)規(guī)模為i的累積摘要Si，也需要遍歷i個(gè)數(shù)據(jù)獲取最優(yōu)值作為效用收益).

次模最大化問題通常滿足累積摘要在某一維度的收益單調(diào)增特性(如圖3(c)實(shí)際是優(yōu)化了摘要到點(diǎn)J，K的距離)，因此，該類問題中摘要添加最高增益對(duì)象hi與直接優(yōu)化摘要的某一維度的最優(yōu)效用值是等價(jià)的.本文提出對(duì)具有以下特性的效用函數(shù)進(jìn)行累積摘要集合Si的信息壓縮，引入效用向量(utility vector)概念.

Uk i=max{Uk i,gi({e})},

(9)

其中,Uk i表示第k層向量的第i維度效用值.效用向量Uk僅在新增摘要維持對(duì)象時(shí)完成更新，因此時(shí)間復(fù)雜度滿足Ω(f({Uk}))=1k×Ω(f(Sk))，而效用向量的收益f({Uk})則滿足f({Uk})=f(Sk).

綜上，對(duì)于未壓縮的累積摘要增益計(jì)算Δf(S)，其開銷為Ω(|S|×|f({hi})|×2).而通過效用向量的增益計(jì)算與更新開銷為Ω(|f({Ui})|+|f({Ui})|×2),其中|f({Ui})|=|f({hi})|，|S|=k.因此相對(duì)于原算法，效用向量在時(shí)間復(fù)雜度上到達(dá)23×k倍的提升.

2.3.3可變的分層摘要維持對(duì)象數(shù)量

HSSM算法中每層的增益篩選過程僅保留單個(gè)摘要維持對(duì)象hi，故具有最低收益保證的優(yōu)勢(shì).但考慮到某些場(chǎng)景中可能遇到需求摘要規(guī)模k過大，導(dǎo)致流水并行模式延遲過大(規(guī)模為v的數(shù)據(jù)摘要其時(shí)間開銷為Ω(v+k))及層數(shù)過多導(dǎo)致存儲(chǔ)空間增大等問題.本文提出分層模型中每層摘要維持?jǐn)?shù)量是可變的(即Layerl可以保留li個(gè)摘要維持對(duì)象{hi 1,hi 2,….,hi l}).該方法將摘要S不規(guī)則地分配在i層中，使得層數(shù)是可控的，但會(huì)導(dǎo)致并行度降低，從而減慢摘要時(shí)間.

2.3.4HSSM+算法

改進(jìn)的HSSM算法的實(shí)現(xiàn)如算法2所示.

算法2. HSSM+:改進(jìn)的流次模最大化分層算法.

輸入：數(shù)據(jù)集O、摘要規(guī)模k、過濾閾值σ；

輸出：摘要結(jié)果S.

h是摘要維持對(duì)象的集合；

② fori=1 tondo {

③e=Oi；*載入新數(shù)據(jù)*

④ forl=1 tokdo {*在每一層中篩選該數(shù)據(jù)*

⑤ if (Δf(e|Ul-1)<σ)

⑧ [e,hl,Ul]=Filter(e,hl,Ul-1)；}}

⑨S?；*初始化摘要結(jié)果*

⑩ forl=1 tokdo

3　分布式分層次模最大化算法及實(shí)現(xiàn)

根據(jù)第2.1節(jié)分析可知，HSSM+算法在不同層中數(shù)據(jù)增益對(duì)比具有可并行的特點(diǎn)，通過分布式處理框架實(shí)現(xiàn)不同分層的數(shù)據(jù)同時(shí)進(jìn)行篩選，可達(dá)到提高摘要速率的目標(biāo).本節(jié)主要介紹HSSM+算法的分布式實(shí)現(xiàn).

3.1分布式HSSM+算法

HSSM+算法構(gòu)建流水并行模式(圖1)使得某一時(shí)刻各層可同時(shí)進(jìn)行數(shù)據(jù)增益對(duì)比Δf操作，進(jìn)一步提出Spark-HSSM+算法.相對(duì)于單對(duì)象處理模式，分布式流數(shù)據(jù)框架需解決3個(gè)問題：

1) 對(duì)于實(shí)時(shí)到來的流數(shù)據(jù)，以單一對(duì)象作為分布式任務(wù)(Job)存在資源分配與任務(wù)調(diào)度(調(diào)度中心將任務(wù)分配給空閑的Worker并等待其返回運(yùn)行結(jié)果)的時(shí)間開銷問題.

2) 在建立分布式任務(wù)時(shí)，解決待處理數(shù)據(jù)與分層信息結(jié)合的問題.

3) 每輪摘要任務(wù)完成后，如何實(shí)現(xiàn)動(dòng)態(tài)更新分層信息.

針對(duì)分布式系統(tǒng)中以單個(gè)對(duì)象(或少量數(shù)據(jù))為數(shù)據(jù)處理單元(如Spark中的RDD)將導(dǎo)致頻繁的啟動(dòng)任務(wù)，整個(gè)摘要過程的調(diào)度總開銷甚至遠(yuǎn)大于摘要過程中效用收益的計(jì)算與對(duì)比的問題.分布式HSSM+算法將待處理數(shù)據(jù)按時(shí)間間隔t或數(shù)據(jù)量(最小數(shù)據(jù)規(guī)模閾值θ)進(jìn)行分批處理，該方法確保每一次任務(wù)處理的數(shù)據(jù)量盡可能滿足負(fù)載均衡與流數(shù)據(jù)處理的任務(wù)實(shí)時(shí)性.

為保證所有待處理數(shù)據(jù)O逐一被所有層過濾或保留.本文通過遞增的方式給每批新數(shù)據(jù)添加批次號(hào)(i)，同時(shí)建立一個(gè)有限大小的循環(huán)隊(duì)列用于存儲(chǔ)批數(shù)據(jù) (圖4步驟①)：首先，將新數(shù)據(jù)存儲(chǔ)于隊(duì)列的指定單元(i%k)；其次，Spark-HSSM+算法以時(shí)間片為單元，完成待處理批數(shù)據(jù)vi的摘要任務(wù)(即vi在對(duì)應(yīng)層Layerl的增益篩選操作)；最后，在下一時(shí)間片開始階段，讀入新數(shù)據(jù)vi+1并將(i+1)%k位置的原數(shù)據(jù)vi+1-k替代為該數(shù)據(jù).該方法實(shí)現(xiàn)批數(shù)據(jù)vi-k在k個(gè)時(shí)間單位內(nèi)被有規(guī)律的存儲(chǔ)，并通過算法3實(shí)現(xiàn)批次號(hào)i與各批次數(shù)據(jù)vi及分層信息的映射.

Fig. 4　Spark-HSSM+ algorithm in Spark.圖4　Spark框架實(shí)現(xiàn)Spark-HSSM+算法

算法3.BatchMap:基于批次號(hào)i獲取循環(huán)隊(duì)列數(shù)據(jù)與分層信息的映射關(guān)系.

輸入：當(dāng)前批次號(hào)i、數(shù)據(jù)總批數(shù)b、摘要大小k;

輸出：起始循環(huán)數(shù)據(jù)塊索引f_start、起始層次號(hào)l_start、對(duì)應(yīng)使用的數(shù)據(jù)塊及層次數(shù)目length.

① 初始化：f_start=0，l_start=0，length=0；

② ifi>(k-2) &&i

③f_start=i%k，l_start=0，length=k;

④ else ifi<(k-1)*循環(huán)隊(duì)列未滿*

⑤f_start=i，l_start=0，length=i+1;

⑦f_start=(b-1)%k，l_start=i-b+1，

length=k-i+b-1;

⑧ return [f_start,l_start,length].

為達(dá)到分層次模最大化算法的最差解收益保證，要求每輪摘要任務(wù)結(jié)束時(shí)，各層的累積摘要(或效用向量U)更新為上層累積摘要與本層篩選的最高增益對(duì)象hi.通過分布式任務(wù)可完成批數(shù)據(jù)vi的最優(yōu)增益對(duì)象hi的選取，然而該方法無法實(shí)現(xiàn)自頂向下的累積摘要(或效用向量)更新，本文通過對(duì)各分布式任務(wù)的結(jié)果進(jìn)行集中匯總更新的方式解決該難題.由于分布式摘要結(jié)果是無序的，故更新前還需對(duì)摘要結(jié)果進(jìn)行排序，以保證累積摘要是自頂向下添加實(shí)現(xiàn)分層次模最大化摘要.

3.2Spark平臺(tái)實(shí)現(xiàn)Spark-HSSM+算法

Spark[21]是基于Hadoop[22]文件存儲(chǔ)系統(tǒng)HDFS與MapReduce處理模式的分布式處理平臺(tái)，使用共享內(nèi)存的彈性分布式數(shù)據(jù)集(RDD)技術(shù)與DAG(有向無環(huán)圖)任務(wù)結(jié)構(gòu)改進(jìn)了Hadoop框架在迭代任務(wù)開始與結(jié)束階段因數(shù)據(jù)頻繁進(jìn)行磁盤讀寫操作產(chǎn)生開銷的缺陷.

Spark-HSSM+算法通過建立如圖4所示的分布式處理流程，利用Spark的Streaming流數(shù)據(jù)處理框架的fileStream()方法將流數(shù)據(jù)通過時(shí)間間隔(例如，1 s)分批讀入；并以循環(huán)隊(duì)列的形式實(shí)現(xiàn)3.1節(jié)中替換存儲(chǔ)數(shù)據(jù)至分布式內(nèi)存(RDD)中.

步驟②向分布式內(nèi)存申請(qǐng)k個(gè)單元存儲(chǔ)待處理數(shù)據(jù)塊(DataBlocki)，步驟③讀取圖4中Hierarchy Streaming Summarization的分層摘信息，通過map()方法完成摘要維持對(duì)象hi，上層待處理數(shù)據(jù)ti及效用向量Ui-1的數(shù)據(jù)映射操作，最終形成具有關(guān)聯(lián)批次號(hào)(batchid)的分布式待處理數(shù)據(jù)與分層信息.

圖4中步驟④通過按批次號(hào)連接(Spark中Join()方法)各分布式任務(wù)數(shù)據(jù)(包括DataBlocki，hi，ti及Ui-1)組成分布式任務(wù)(Job).

由于分層增益對(duì)比滿足數(shù)據(jù)間的獨(dú)立性，將所有任務(wù)(JobAB…)通過Spark的reduceByKey()方法分布在若干個(gè)節(jié)點(diǎn)上并行完成，使得所有數(shù)據(jù)分別執(zhí)行增益計(jì)算，并對(duì)batchid相同的數(shù)據(jù)(在同一節(jié)點(diǎn)上)進(jìn)行兩兩增益對(duì)比，最終僅返回最高增益對(duì)象為該層新摘要維持對(duì)象i (如圖4步驟⑤)，若發(fā)生摘要維持對(duì)象的替換時(shí)，需返回原摘要維持對(duì)象ei+1，使其在下層摘要篩選過程中被訪問.

步驟⑧通過實(shí)時(shí)訪問分層模型合并各層摘要維持對(duì)象(h1,h2,…,hk)，最終得到規(guī)模為k的摘要結(jié)果Sk.

算法4.Spark-HSSM+:Spark實(shí)現(xiàn)HSSM+算法.

輸入：分批數(shù)據(jù)集O、數(shù)據(jù)總批數(shù)b、摘要規(guī)模k；

輸出：摘要結(jié)果S.

②fori=1to(b+k-1)do{*處理所有數(shù)據(jù)獲取該批次號(hào)映射的層次信息*

③ [f_start,l_start,length]=BatchMap(i,

b,k)；

④ifi

⑤ 將oi存入DataBlockf_start數(shù)據(jù)塊；

⑦forc=0tolengthdo{*所有數(shù)據(jù)合并同層待處理數(shù)據(jù)與維持對(duì)象*

⑧ tmpBlcokj=DataBlockj∪{hl}∪{tl}；

⑨ 基于映射關(guān)系連接DataBlockj與Ul-1；

4　次模最大化相關(guān)算法的性能對(duì)比

將本文算法與常見的次模最大化算法進(jìn)行分析，分別通過訪問數(shù)據(jù)集次數(shù)、最低(最差解)收益保證、時(shí)間復(fù)雜度及流數(shù)據(jù)更新的時(shí)間與空間開銷方面作出對(duì)比，各算法主要性能如表1所示:

Table 1　Comparison Between the Existing Submodular Maximization Methods表1　常見次模最大化算法性能對(duì)比

首先對(duì)比各算法的數(shù)據(jù)集訪問次數(shù).除標(biāo)準(zhǔn)貪心算法(Standard-Greedy)需進(jìn)行k輪迭代訪問外，其余算法均可滿足流數(shù)據(jù)僅一次訪問數(shù)據(jù)集的限制.

在最差解收益保證方面，Standard-Greedy擁有最高的收益保證；Stream-Greedy算法需多次訪問數(shù)據(jù)集以維持其最差解下界，即僅訪問一次數(shù)據(jù)集時(shí)，其最差解收益的下界為1k×f(S*)，而在多次訪問數(shù)據(jù)集的條件下，其上界也不大于12*最優(yōu)解收益；Sieve-Streaming算法的最差解保證則與其離散度參數(shù)ε相關(guān)；本文提出的HSSM+算法在2.2小節(jié)中證明摘要至少達(dá)到1(2-1k)的最優(yōu)解收益.

對(duì)比各算法處理規(guī)模為n的數(shù)據(jù)集，其時(shí)間復(fù)雜度量級(jí)都不低于Ω(n×k2×Δf).但本文通過2.3.2節(jié)中提出效用向量壓縮方法使得計(jì)算每個(gè)數(shù)據(jù)對(duì)象增益的時(shí)間開銷由Ω(k2×Δf)降為32×k×Δf.

證明.

證畢.

對(duì)于流數(shù)據(jù)(僅通過訪問增量數(shù)據(jù)v更新摘要S)的摘要問題，GreeDi算法在處理已知數(shù)據(jù)規(guī)模的情況下(不符合一般流數(shù)據(jù)使用條件)，可基于不同的數(shù)據(jù)規(guī)模劃分提高摘要速率；分布式Sieve-Stream與Spark-HSSM+算法適用解決所有流數(shù)據(jù)摘要問題，且較其余非分布式算法具有約k倍的提高.其中，Spark-HSSM+算法因流水并行結(jié)構(gòu)對(duì)實(shí)時(shí)的摘要結(jié)果產(chǎn)生k個(gè)時(shí)間單位的延遲，但摘要過程的處理時(shí)間仍為Ω(v).

在空間開銷方面，GreeDi算法與Stream-Greedy算法僅保存規(guī)模為k的摘要結(jié)果與當(dāng)前處理的批數(shù)據(jù)v即可；Sieve-Stream算法根據(jù)其離散參數(shù)ε的不同，共保存logkε個(gè)過濾器，并分別為這些過濾器保存待處理數(shù)據(jù)v；Spark-HSSM+算法將批數(shù)據(jù)v需保存k個(gè)時(shí)間單位故產(chǎn)生k倍于批數(shù)據(jù)大小的額外內(nèi)存開銷.

從上述理論分析中得出，本文提出的流數(shù)據(jù)分層次模最大化摘要算法Spark-HSSM+，應(yīng)用流水并行結(jié)構(gòu)完成其在Spark分布式平臺(tái)的實(shí)現(xiàn)，通過效用向量U使得次模效用函數(shù)的計(jì)算開銷減少為原本的3(2k)，并以分布式任務(wù)的方式使得摘要速率比串行算法上具有k倍的提升，最終實(shí)現(xiàn)較貪心算法具有23×k2倍的速率優(yōu)化.

5　實(shí)驗(yàn)結(jié)果與分析

本節(jié)分別在單機(jī)環(huán)境及分布式集群上完成基于覆蓋率的摘要問題與基于距離損失函數(shù)的中心點(diǎn)選取問題的次模最大化算法對(duì)比實(shí)驗(yàn)：

隨機(jī)采樣(Random)：對(duì)數(shù)據(jù)集O隨機(jī)選取k個(gè)對(duì)象作為摘要.

Standard-Greedy(Greedy)：通過標(biāo)準(zhǔn)貪心算法[9]遍歷k次數(shù)據(jù)集選取k個(gè)對(duì)象作為摘要結(jié)果.

Stream-Greedy(SG)：基于1.3.2節(jié)中描述的流貪心算法[11]，維護(hù)規(guī)模為k個(gè)對(duì)象的結(jié)果作為摘要.

GreeDi：通過1.3.3節(jié)中描述的算法[10]，將數(shù)據(jù)集用分布式標(biāo)準(zhǔn)貪心算法進(jìn)行m次分割進(jìn)行摘要.

Sieve-Streaming(SS)：通過流數(shù)據(jù)過濾算法[12]選取指定的離散參數(shù)ε實(shí)現(xiàn)分布式過濾數(shù)據(jù)集并選取最優(yōu)解作為輸出.

Spark-HSSM+算法通過Scala2.11.6開發(fā)完成.所有單機(jī)對(duì)比實(shí)驗(yàn)運(yùn)行于具有8GB內(nèi)存、雙核2.4GHz處理器的PC機(jī)上，Java環(huán)境為JRE1.8.集群為基于Hadoopyarn2.2.0資源調(diào)度管理的Spark1.2.0分布式框架，包括15個(gè)擁有8GB內(nèi)存及4核2.4GHz處理器的普通PC節(jié)點(diǎn).而所有分布式算法的集群運(yùn)行參數(shù)統(tǒng)一設(shè)置：driver-memory為6GB，executor-memory為6GB，num-executors為10個(gè)，executor-cores為4個(gè).在本文的實(shí)驗(yàn)中，為保證所有摘要結(jié)果都能夠達(dá)到1(2-1k)的最優(yōu)解收益下限，因此每層的摘要維持對(duì)象數(shù)目均為1.

Spark框架通過DAG的任務(wù)結(jié)構(gòu)，使得所有數(shù)據(jù)在未執(zhí)行前，不進(jìn)行實(shí)際的數(shù)據(jù)分配，進(jìn)而使得所有被訪問的數(shù)據(jù)盡可能的存儲(chǔ)在同一臺(tái)機(jī)器上，減少不同機(jī)器間的任務(wù)開銷.

摘要集合的效用收益隨著摘要規(guī)模k的擴(kuò)大而提高，本文通過增量k值的方法對(duì)數(shù)據(jù)集進(jìn)行摘要收益對(duì)比，當(dāng)效用函數(shù)值增長(zhǎng)率低于γ(本文選取γ=10-5)時(shí)停止擴(kuò)展摘要規(guī)模.算法的性能對(duì)比主要基于2個(gè)指標(biāo)：1)指定規(guī)模的條件下，各算法的摘要效用收益；2)指定規(guī)模的條件下，各算法完成摘要的總時(shí)間.相較于其他流摘要算法，隨機(jī)選取策略僅訪問一遍數(shù)據(jù)集且無需計(jì)算效用收益，故其時(shí)間開銷是忽略不計(jì)的.對(duì)于無法在流數(shù)據(jù)或大規(guī)模數(shù)據(jù)集上完成摘要的Standard-Greedy算法，本文通過一個(gè)較小的數(shù)據(jù)集實(shí)現(xiàn)所有算法與該算法的對(duì)比.

5.1非分布式環(huán)境下的性能對(duì)比

本文首先對(duì)包含50 000個(gè)涉及1 000維特征(即每個(gè)對(duì)象包含一個(gè)或多個(gè)特征)的合成數(shù)據(jù)集進(jìn)行基于最大覆蓋率(式(3))的摘要實(shí)驗(yàn).該數(shù)據(jù)集規(guī)模較小，能夠進(jìn)行包括靜態(tài)算法(Standard-Greedy)及非分布式算法在覆蓋率與運(yùn)行時(shí)間的對(duì)比.實(shí)驗(yàn)中Sieve-Streaming算法選取ε=0.1對(duì)最優(yōu)解進(jìn)行離散.圖5、圖6分別為各算法對(duì)該數(shù)據(jù)集在不同摘要規(guī)模k的效用收益(覆蓋率)及運(yùn)行時(shí)間對(duì)比.

Fig. 5　The coverage of algorithms in different k.圖5　不同規(guī)模下各算法覆蓋率對(duì)比

Fig. 6　The running time of algorithms in different k.圖6　不同規(guī)模下各算法完整摘要時(shí)間對(duì)比

從圖5中可以看出，在規(guī)模不斷增加的過程中，Stream-Greedy(SG),Standard-Greedy(Greedy),Sieve-Stream(SS)及HSSM算法的收益都有次模特性，摘要的收益基本保持單調(diào)增長(zhǎng)特性，但Sieve-Stream由于規(guī)模改變導(dǎo)致每次選取的摘要可能不同，有可能出現(xiàn)規(guī)模增大摘要收益反而降低的現(xiàn)象.總體來說，Stream-Greedy算法與HSSM算法在覆蓋率收益方面都更接近于標(biāo)準(zhǔn)貪心算法Standard-Greedy的收益，而Sieve-Stream算法雖優(yōu)于隨機(jī)采樣方法(Random)，但相比于其他算法仍有10個(gè)百分比左右的差距.

圖6表明，對(duì)于同一數(shù)據(jù)集，摘要時(shí)間隨規(guī)模k呈指數(shù)型增長(zhǎng).而Stream-Greedy(SG)算法在僅訪問一遍數(shù)據(jù)集的情況下需依次計(jì)算新數(shù)據(jù)e的增益Δf(e|Sk{hi})與原摘要維持對(duì)象hi的增益Δf(hi|Sk{hi})，即二次訪問累積摘要集合，故比標(biāo)準(zhǔn)貪心算法多近一倍的開銷時(shí)間.同時(shí)，未優(yōu)化的HSSM算法與標(biāo)準(zhǔn)貪心算法時(shí)間開銷接近；而Sieve-Stream運(yùn)行時(shí)間則主要受限于過濾器數(shù)目及過濾器中摘要數(shù)量，本實(shí)驗(yàn)中k=50時(shí)過濾器數(shù)目為27個(gè)，其時(shí)間開銷約為標(biāo)準(zhǔn)貪心算法的16.

通過2.3節(jié)中引入最優(yōu)效用向量及最低增益過濾(σ=5)改進(jìn)后的HSSM+算法在覆蓋率收益與時(shí)間開銷如表2、表3所示.通過對(duì)比結(jié)果發(fā)現(xiàn)，僅當(dāng)k較大(k=45與k=50)的情況下，HSSM+算法的收益較原算法略有降低，但仍與Stream-Greedy算法收益接近.而在算法的運(yùn)行時(shí)間開銷方面，對(duì)比k=50的摘要規(guī)模，HSSM+比未改進(jìn)的HSSM算法提升了約39倍，比Stream-Greedy算法要高約60倍，對(duì)比不同的摘要規(guī)模，HSSM+算法也能較原算法達(dá)到接近于理論(23×k倍)的速率提升.

Table2ComparisonofHSSM,HSSM+ &Stream-Greedy(SG)inCoverage

表2改進(jìn)的HSSM算法(HSSM+)與樸素算法(HSSM)及流貪心算法(SG)的覆蓋率對(duì)比%

Algorithmk5101520253035404550SG61.2073.3777.0770.9881.0981.7482.3983.3783.8084.13HSSM59.8972.2876.3079.1380.6581.8582.5083.0483.5984.13HSSM+59.8972.2876.3079.1380.6581.8582.5083.0483.3783.59

Table 3　Comparison of HSSM, HSSM+ & Stream-Greedy(SG) in Running Time表3　改進(jìn)的HSSM算法(HSSM+)與樸素算法(HSSM)及流貪心算法(SG)的運(yùn)行時(shí)間對(duì)比　s

5.2基于距離損失函數(shù)的分布式中心點(diǎn)選取

通過對(duì)CensS1990數(shù)據(jù)集[23]采用基于距離損失式(5)的效用函數(shù)進(jìn)行中心點(diǎn)選取實(shí)驗(yàn)，該數(shù)據(jù)集生成包含2 458 285個(gè)68維特征的|O|×|O|距離矩陣數(shù)據(jù)，非流算法對(duì)于該數(shù)據(jù)集的多次訪問需數(shù)天時(shí)間才能得到選取結(jié)果，已不符合一般問題的解決時(shí)效條件.文獻(xiàn)[10]中證明該問題的摘要方法是增量可分的(additivelydecomposable)，故實(shí)驗(yàn)使用從原數(shù)據(jù)集中采樣|W|=1100|O|進(jìn)行流算法的對(duì)比實(shí)驗(yàn).由于文件大小的限制，本實(shí)驗(yàn)將該數(shù)據(jù)集以500個(gè)對(duì)象為一批次進(jìn)行分割，而該數(shù)據(jù)量過小使得Spark-HSSM+算法不能夠達(dá)到分布式最高運(yùn)行效率(分布式任務(wù)調(diào)度開銷過大)，但我們?nèi)赃M(jìn)行對(duì)比以證明優(yōu)化后的Spark-HSSM+算法在分布式環(huán)境下運(yùn)行效率得到提升.本實(shí)驗(yàn)設(shè)置過濾閾值μ=20，Sieve-Stream算法選取ε=0.1離散化最優(yōu)解，分布式中共包含72個(gè)過濾器.GreeDi不適合處理流數(shù)據(jù)，故僅用其作增量式(每批數(shù)據(jù)保存貪心摘要結(jié)果用于下一批次比較)貪心算法對(duì)比.

Fig. 7　The utility of different algorithms in k=50.圖7　k=50時(shí)效用函數(shù)值對(duì)比

圖7顯示在規(guī)模k=50的情況下，GreeDi,Stream-Greedy與Spark-HSSM+算法的效用收益相差不大，而Sieve-Stream算法則遇到過濾器最優(yōu)解估計(jì)不適的情況，其效用收益值甚至低于隨機(jī)采樣.

圖8表明Sieve-Stream算法與Spark-HSSM+算法的運(yùn)行速率要明顯優(yōu)于Stream-Greedy與GreeDi算法，因此更適合處理需要更高效響應(yīng)的流數(shù)據(jù)，其中，Spark-HSSM+算法較Stream-Greedy算法僅提高了29倍，未達(dá)到理論值提升的主要原因是數(shù)據(jù)規(guī)模過小不適合分布式任務(wù)且包含任務(wù)調(diào)度與資源分配同時(shí)產(chǎn)生額外開銷，故該算法在處理小批量數(shù)據(jù)時(shí)，優(yōu)化效果不明顯.

Fig. 8　The running time of different algorithms in k=50.圖8　k=50時(shí)各算法完整摘要時(shí)間對(duì)比

5.3分布式環(huán)境下基于覆蓋率的數(shù)據(jù)摘要

由于5.2節(jié)中實(shí)驗(yàn)未體現(xiàn)大規(guī)模流數(shù)據(jù)摘要的特點(diǎn)(每批次數(shù)據(jù)量過少)，因此，本節(jié)選取Yahoo！提供的28 041 015條用戶首頁訪問日志數(shù)據(jù)集[24]以280 000條數(shù)據(jù)進(jìn)行分批，同樣以基于最大覆蓋率的效用函數(shù)進(jìn)行實(shí)驗(yàn).

Fig. 9　Comparison of utility & running time on Yahoo! dataset.圖9　Yahoo!數(shù)據(jù)集的效用收益與運(yùn)行時(shí)間對(duì)比

該數(shù)據(jù)集包含126維用于描述用戶訪問時(shí)的行為特征，根據(jù)文獻(xiàn)[1]中提出的關(guān)聯(lián)規(guī)則對(duì)其中最頻繁的50維特征的頻繁二項(xiàng)集進(jìn)行最大覆蓋率摘要實(shí)驗(yàn).實(shí)驗(yàn)選取k=30，Spark-HSSM+算法選取過濾閾值上界μ=20，Sieve-Stream算法設(shè)置離散系數(shù)ε=0.01(該離散值使其效用收益更加接近于Spark-HSSM+算法).圖9為隨機(jī)采樣、SS算法及Spark-HSSM+算法的摘要時(shí)間及其效用收益對(duì)比.

圖9表明Spark-HSSM+算法在可接受響應(yīng)時(shí)間內(nèi)，較Sieve-Stream算法與隨機(jī)選取得到更優(yōu)的效用收益.同時(shí)其在運(yùn)行速率方面也較Sieve-Stream算法有10倍左右的提升.除上述3個(gè)算法外，其余算法均無法在24h內(nèi)給出響應(yīng)結(jié)果，對(duì)于流摘要的代表算法Stream-Greedy，本文通過其完成1%的數(shù)據(jù)處理量耗時(shí)預(yù)估出其時(shí)間開銷約為本文算法的500倍(理論值為23×k2=600倍，但應(yīng)除去分布式任務(wù)的啟動(dòng)與資源調(diào)度的時(shí)間開銷).故大規(guī)模流數(shù)據(jù)摘要算法Spark-HSSM+，在具有高效用收益的同時(shí)，其速率提升也是顯著的.

6　結(jié)　　論

本文提出了基于次模最大化的流數(shù)據(jù)分層摘要算法.該算法在分布式環(huán)境下僅一次訪問數(shù)據(jù)集即可完成選取大小為k的摘要集合，其摘要的效用函數(shù)收益至少能達(dá)到1(2-1k)的最優(yōu)解.實(shí)驗(yàn)表明Spark-HSSM+算法在處理大規(guī)模數(shù)據(jù)集時(shí)能夠在達(dá)到近似于標(biāo)準(zhǔn)貪心算法收益(次模最大化問題中最好的解決方案)的同時(shí)，相比于其他算法在實(shí)時(shí)性上具有優(yōu)勢(shì)，其速率在理論較標(biāo)準(zhǔn)貪心算法提升約為23×k2倍.本文的貢獻(xiàn)旨在對(duì)大規(guī)模數(shù)據(jù)及流數(shù)據(jù)集在次模最大化收益問題及運(yùn)行效率方面得到改進(jìn).

[1]XuJ,KalashnikovDV,MehrotraS.Efficientsummarizationframeworkformulti-attributeuncertaindata[C] //Procofthe33rdACMSIGMODIntConfonManagementofData.NewYork:ACM, 2014: 421-432

[2]WangZhenhua,ShouLidan,ChenKe,etal.Onsummarizationandtimelinegenerationforevolutionarytweetstreams[J].IEEETransonKnowledgeandDataEngineering, 2014, 27(5): 1301-1315

[3]SiposR,SwaminathanA,ShivaswamyP,etal.Temporalcorpussummarizationusingsubmodularwordcoverage[C] //Procofthe21stACMIntConfonInformationandKnowledgeManagement.NewYork:ACM, 2012: 754-763

[4]ShouL,WangZ,ChenK,etal.Sumblr:Continuoussummarizationofevolvingtweetstreams[C] //Procofthe36thIntACMSIGIRConfonResearchandDevelopmentinInformationRetrieval.NewYork:ACM, 2013: 533-542

[5]BarzilayR,MckeownKR.Sentencefusionformultidocumentnewssummarization[J].ComputationalLinguistics, 2005, 31(3): 297-328

[6]ShiL,OlaS.Approximatingk-medianviapseudo-approximation[C] //Procofthe45thAnnualACMSymponTheoryofComputing.NewYork:ACM, 2013: 901-910

[7]El-AriniK,VedaG,ShahafD,etal.Turningdownthenoiseintheblogosphere[C] //Procofthe15thACMSIGKDDIntConfonKnowledgeDiscoveryandDataMining.NewYork:ACM, 2009: 289-298

[8]ChenHao,WangYitong.Threshold-basedheuristicalgorithmforinfluencemaximization[J].JournalofComputerResearchandDevelopment, 2012, 49(10): 2181-2188 (inChinese)

(陳浩, 王軼彤. 基于閾值的社交網(wǎng)絡(luò)影響力最大化算法[J]. 計(jì)算機(jī)研究與發(fā)展, 2012, 49(10): 2181-2188)

[9]NemhauserGLWolseyLA,FisherML.Ananalysisofapproximationsformaximizingsubmodularsetfunctions—I[J].MathematicalProgramming, 1978, 14(1): 265-294

[10]MirzasoleimanB,KarbasiA,SarkarR,etal.Distributedsubmodularmaximization:Identifyingrepresentativeelementsinmassivedata[J].AdvancesInNeuralInformationProcessingSystems, 2013, 87(1): 382-384

[11]GomesR,KrauseA.Budgetednonparametriclearningfromdatastreams[C] //ProcoftheIntConfonMachineLearning.Haifa:ICML, 2010: 391-398

[12]BadanidiyuruA,MirzasoleimanB,KarbasiA,etal.Streamingsubmodularmaximization:Massivedatasummarizationonthefly[C] //Procofthe20thACMSIGKDDIntConfonKnowledgeDiscoveryandDataMining.NewYork:ACM, 2014: 671-680

[13]VeeE,SrivastavaU,ShanmugasundaramJ,etal.Efficientcomputationofdiversequeryresults[C]//Procofthe24thIEEEIntConfonDataEngineering.Piscataway,NJ:IEEE, 2008: 228-236

[14]MishraD,HiranwalS.Analysis&implementationofitembasedcollaborationfilteringusingK-Medoid[C] //Procof2014IntConfonAdvancesinEngineeringandTechnologyResearch(ICAETR).Piscataway,NJ:IEEE, 2014: 1-5

[15]CarvalhoF,MeloF,LechevallierY.Amulti-viewrelationalfuzzyc-medoidvectorsclusteringalgorithm[J].Neurocomputing, 2015, 163(c): 115-123

[16]MinouxM.Acceleratedgreedyalgorithmsformaximizingsubmodularsetfunctions[J].LectureNotesinControlandInformationSciences, 1978, (7): 234-243

[17]LiuYong,GaoHong,LiJianzhong.Top-Kgraphpatternsminingbasedonsomejointsignificancemeasure[J]. //ChineseJournalofComputers, 2010, 33(2): 215-230 (inChinese)

(劉勇, 高宏, 李建中. 基于聯(lián)合意義度量的Top-K圖模式挖掘[J]. 計(jì)算機(jī)學(xué)報(bào), 2010, 33(2): 215-230)

[18]YanY,ZhangJ,HuangB,etal.Distributedoutlierdetectionusingcompressivesensing[C] //Procofthe2015ACMSIGMODIntConfonManagementofData.NewYork:ACM, 2015: 3-16

[19]KumarR,MoseleyB,VassilvitskiiS,etal.FastgreedyalgorithmsinMapReduceandstreaming[J].ACMTransonParallelComputing, 2015, 2(3): 14:1-14:22

[20]BeltrameG,BrandoleseC,FornaciariW,etal.Anassembly-levelexecution-timemodelforpipelinedarchitectures[C] //Procofthe2001IEEE//ACMIntConfonComputer-AidedDesign.Piscataway,NJ:IEEE, 2001: 195-200

[21]ZahariaM,ChowdhuryM,DasT,etal.Resilientdistributeddatasets:Afault-tolerantabstractionforin-memoryclustercomputing[C] //Procofthe9thUSENIXConfonNetworkedSystemsDesignandImplementation.Berkeley,CA:USENIXAssociation, 2012: 141-146

[22]Apache.Hadoop[OL]. [2009-03-06].http://hadoop.apache.org

[23]ChristopherM,BoT,DavidH.Thelearning-curvesamplingmethodappliedtomodel-basedclustering[J].TheJournalofMachineLearningResearch, 2002, 2(3): 397-418

[24]LiLihong,ChuWei,LangfordJ,etal.Unbiasedofflineevaluationofcontextual-bandit-basednewsarticlerecommendationalgorithms[C] //Procofthe4thACMIntConfonWebSearchandDataMining(WSDM’11).NewYork:ACM, 2011: 297-306

ZhangFenxiang,bornin1989.MastercandidateintheFacultyofElectricalEngineeringandComputerScience,NingboUniversity.Hismainresearchinterestsincludestreamdataprocessingandcloudcomputing.

ChenHuahui,bornin1964.PhD,professor.MemberofChinaComputerFederation.Hismainresearchinterestsareintheareasofdatastreamsandmassivedataprocessing(chenhuahui@nbu.edu.cn).

QianJiangbo,bornin1974.PhD,professor.MemberofChinaComputerFederation.Hismainresearchinterestsincludedatabasemanagement,streamingdataprocessing,multidimensionalindexing,andqueryoptimization(qianjb@163.com).

DongYihong,bornin1969.PhD,professorandmasterinstructorintheFacultyofElectricalEngineeringandComputerScience,NingboUniversity.Hismainresearchinterestsincludebigdata,dataminingandartificialintelligence(dongyihong@nbu.edu.cn).

HSSM: A Hierarchical Method for Streaming Submodular Maximization

Zhang Fenxiang, Chen Huahui, Qian Jiangbo, and Dong Yihong

(FacultyofElectricalEngineeringandComputerScience,NingboUniversity,Ningbo,Zhejiang315211)

How to extractkelements from a large data stream according to some utility functions can be reduced to maximizing a submodular set function. The traditional algorithms had already given some good solutions of summarizing a static data set by submodular method, well-known as standard greedy algorithm. Lastly researches also presented some new algorithms with corresponding distributed solutions to meet the streaming data access and the real-time response limits, but those algorithms are not good enough in maximizing the utility gain. In this paper, we propose a new algorithm called HSSM which runs as a pipelining distributed framework and requires only a single-pass access the data set. Finally, the utility gain of our solution is close to the option standard greedy solution. We also propose using utility vector to compress the set of summarization and filtering out the low gain objects to improve the original HSSM algorithm. Fortunately, this approach can get applications in many related fields such as representative articles selection,k-medoid select problem and so on. Experimental results show that the improved Spark-HSSM+ method can increase the summarization speed in direct proportion tok2in contrast to the traditional method. Compared with other distributed algorithms, the result of the Spark-HSSM+ method is the most close to the standard greedy solution.

streaming submodular maximization; hierarchy model; pipelining parallelism; data summarization; Spark distribution platform

2016-03-11；

2016-05-31

國家自然科學(xué)基金項(xiàng)目(61572266,61472194)

TP391

This work was supported by the National Natural Science Foundation of China (61572266,61472194).