于自強(qiáng),禹曉輝,董吉文,王 琳

1(濟(jì)南大學(xué) 信息科學(xué)與工程學(xué)院,山東 濟(jì)南 250022)

2(山東大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,山東 濟(jì)南 250101)

1 引 言

隨著移動(dòng)終端和無線網(wǎng)絡(luò)的廣泛應(yīng)用,現(xiàn)實(shí)中許多應(yīng)用面臨大規(guī)模數(shù)據(jù)流的處理.例如,社交網(wǎng)絡(luò)中的微博數(shù)據(jù),電子商務(wù)領(lǐng)域的顧客瀏覽、交易數(shù)據(jù),城市交通管控系統(tǒng)的過車數(shù)據(jù),環(huán)境監(jiān)測(cè)領(lǐng)域的傳感器數(shù)據(jù)等都包含了大規(guī)模數(shù)據(jù)流.在海量數(shù)據(jù)流中,通常隱藏著大量用戶感興趣的特定模式,發(fā)現(xiàn)這些特定模式對(duì)于改善應(yīng)用服務(wù)質(zhì)量,提升數(shù)據(jù)應(yīng)用價(jià)值具有重要意義.多數(shù)據(jù)流中的頻繁伴隨模式是由Yu等人[1]首次提出來的,現(xiàn)實(shí)中若干應(yīng)用都可以抽象為頻繁伴隨模式的發(fā)現(xiàn)問題.本文的研究目標(biāo)是設(shè)計(jì)分布式挖掘算法,實(shí)時(shí)發(fā)現(xiàn)海量數(shù)據(jù)流中的頻繁伴隨模式.為便于描述,下文將采用FCP來表達(dá)頻繁伴隨模式.

給定一個(gè)無界數(shù)據(jù)流的集合S={s1,s2,…,sn}和一個(gè)元素集合O={o1,o2,…,ok},如果集合O是一個(gè) FCP,那么它將滿足以下條件:(1) 該集合中的元素在小于τ的時(shí)間段內(nèi)出現(xiàn)在至少θ個(gè)數(shù)據(jù)流上；(2) 該集合的元素在每一個(gè)數(shù)據(jù)流上出現(xiàn)的時(shí)間間隔不大于ξ.這里,τ、θ、ξ都是用戶指定的參數(shù)[1].頻繁伴隨模式表達(dá)了一組對(duì)象在多個(gè)數(shù)據(jù)流中的緊密關(guān)系,許多應(yīng)用都可以歸結(jié)為數(shù)據(jù)流上的頻繁伴隨模式發(fā)現(xiàn)問題[1].

伴隨車輛發(fā)現(xiàn).當(dāng)前城市主要道路和路口安裝了監(jiān)控抓拍設(shè)備,車輛每次經(jīng)過時(shí),抓拍設(shè)備都會(huì)生成一條結(jié)構(gòu)化的過車記錄(vehicle passing record,簡(jiǎn)稱VPR).這樣,每個(gè)抓拍設(shè)備將產(chǎn)生一個(gè)由連續(xù)過車記錄組成的數(shù)據(jù)流,而一些伴隨行駛的車輛將會(huì)出現(xiàn)在由多個(gè)抓拍設(shè)備所產(chǎn)生的數(shù)據(jù)流中.因此,從過車記錄中發(fā)現(xiàn)伴隨車輛相當(dāng)于從這些數(shù)據(jù)流中發(fā)現(xiàn)FCP.現(xiàn)實(shí)中,及時(shí)發(fā)現(xiàn)伴隨車輛對(duì)于預(yù)防和打擊罪犯嫌疑人駕駛多部車輛協(xié)同作案、尾隨受害人作案等案件具有重要意義.

基于微博的熱點(diǎn)話題發(fā)現(xiàn).在新浪微博等社交平臺(tái),可以認(rèn)為每個(gè)用戶對(duì)應(yīng)著一個(gè)由自己發(fā)布的微博組成的數(shù)據(jù)流.較短時(shí)間內(nèi),在許多用戶微博中頻繁出現(xiàn)的詞匯組合通常預(yù)示著一個(gè)新的熱點(diǎn)話題的出現(xiàn).那么從海量用戶對(duì)應(yīng)的數(shù)據(jù)流中挖掘頻繁伴隨出現(xiàn)的熱點(diǎn)詞匯組合其本質(zhì)也是多數(shù)據(jù)流的FCP發(fā)現(xiàn)問題.

位置信息服務(wù).在一些簽到應(yīng)用中(如 Foursquare),用戶會(huì)在到達(dá)一個(gè)地點(diǎn)之后簽到,并向數(shù)據(jù)中心報(bào)告自己的位置.在這類應(yīng)用中,可以認(rèn)為每個(gè)簽到的地點(diǎn)對(duì)應(yīng)著一個(gè)數(shù)據(jù)流,而每個(gè)數(shù)據(jù)流是由用戶的簽到信息組成.在這些數(shù)據(jù)流中實(shí)時(shí)挖掘 FCP,能夠發(fā)現(xiàn)短時(shí)間內(nèi)共同到達(dá)某些簽到地點(diǎn)的用戶群,而發(fā)現(xiàn)這些用戶具有潛在的商業(yè)價(jià)值,例如可以作為某些廣告更好地推送對(duì)象.

以上事例所要解決的基本問題都是發(fā)現(xiàn)較短時(shí)間內(nèi)出現(xiàn)在多個(gè)數(shù)據(jù)流上的FCP(車輛、人、關(guān)鍵詞等).與多數(shù)據(jù)流頻繁伴隨模式發(fā)現(xiàn)較為相似的問題是數(shù)據(jù)流中的頻繁模式發(fā)現(xiàn)問題,但兩者有明顯區(qū)別.數(shù)據(jù)流中的頻繁模式是指某一個(gè)元素集合在一個(gè)數(shù)據(jù)流的多個(gè)“事務(wù)(transaction)”中出現(xiàn),且出現(xiàn)的頻率大于給定的閾值；本文所研究的頻繁伴隨模式則是指一個(gè)元素集合在多個(gè)數(shù)據(jù)流中出現(xiàn),并且所在數(shù)據(jù)流的數(shù)目和出現(xiàn)的間隔需要滿足指定的條件.由于問題本身不同,因此,已有數(shù)據(jù)流頻繁模式挖掘算法無法直接用來解決本文所研究的問題,原因?qū)⒃谙乱还?jié)進(jìn)行詳細(xì)闡述.

目前,對(duì)于多數(shù)據(jù)流FCP發(fā)現(xiàn)問題的研究還很少.文獻(xiàn)[1]提出該問題的同時(shí),給出了CooMine挖掘算法.該算法的目的是通過減少內(nèi)存消耗和索引維護(hù)代價(jià)快速發(fā)現(xiàn)多數(shù)據(jù)流中的 FCP.值得注意的是,CooMine算法是針對(duì)單個(gè)計(jì)算節(jié)點(diǎn)設(shè)計(jì)的集中式挖掘算法,而單個(gè)計(jì)算節(jié)點(diǎn)受到硬件資源的限制,很難應(yīng)對(duì)大規(guī)模數(shù)據(jù)流.為解決這一問題,最直接的辦法是采用多個(gè)計(jì)算節(jié)點(diǎn),令每個(gè)計(jì)算節(jié)點(diǎn)獨(dú)立運(yùn)行 CooMine算法,處理一部分?jǐn)?shù)據(jù)流.該策略雖然能夠處理大規(guī)模數(shù)據(jù)流,但缺點(diǎn)是形成某些 FCP的數(shù)據(jù)流可能被分在不同的計(jì)算節(jié)點(diǎn),導(dǎo)致部分結(jié)果丟失.另一策略是將CooMine算法在多個(gè)計(jì)算節(jié)點(diǎn)上并行化實(shí)現(xiàn),但是CooMine算法采用的Seg-tree樹型索引結(jié)構(gòu)很難有效地并行化部署到多個(gè)計(jì)算節(jié)點(diǎn)上.因此,當(dāng)在分布式計(jì)算環(huán)境下解決大規(guī)模數(shù)據(jù)流 FCP發(fā)現(xiàn)問題時(shí)無法直接采用CooMine算法,仍需設(shè)計(jì)高效的分布式挖掘算法.

與集中式算法相比,設(shè)計(jì)分布式挖掘算法面臨以下挑戰(zhàn).

(1) 由于每個(gè)計(jì)算節(jié)點(diǎn)只存儲(chǔ)部分?jǐn)?shù)據(jù),這給 FCP的生成和比對(duì)帶來很大困擾.例如,對(duì)于一個(gè)分布在計(jì)算節(jié)點(diǎn)n1上的長(zhǎng)度為k的FCP,計(jì)算節(jié)點(diǎn)n1無法得知該FCP應(yīng)和哪些計(jì)算節(jié)點(diǎn)的長(zhǎng)度為k的FCP合并,生成長(zhǎng)度為(k+1)的 FCP.

(2) 采用多個(gè)計(jì)算節(jié)點(diǎn)處理海量數(shù)據(jù)流時(shí),可能出現(xiàn)不同計(jì)算節(jié)點(diǎn)上數(shù)據(jù)負(fù)載不均的情況,從而影響整體的處理效率.這是因?yàn)?每個(gè) FCP的生成需要多個(gè)計(jì)算單元協(xié)同合作,負(fù)載失衡時(shí),負(fù)載較輕的計(jì)算單元往往需要等待負(fù)載較重的計(jì)算單元的計(jì)算結(jié)果,從而影響了整個(gè)系統(tǒng)的挖掘效率.

(3) 由于大規(guī)模數(shù)據(jù)流連續(xù)到達(dá),新到達(dá)的數(shù)據(jù)不斷地和已有數(shù)據(jù)共同構(gòu)成新的FCP,這就要求挖掘算法必須能夠隨著數(shù)據(jù)流的連續(xù)到達(dá)實(shí)時(shí)發(fā)現(xiàn)新生成的FCP,實(shí)現(xiàn)FCP的增量挖掘.

為應(yīng)對(duì)以上挑戰(zhàn),本文提出FCP分布式挖掘方法(FCP distributed mining approach,簡(jiǎn)稱FCP-DM).該方法的核心思想是采用基于服務(wù)器集群的分布式計(jì)算模式,從大規(guī)模數(shù)據(jù)流中實(shí)時(shí)連續(xù)發(fā)現(xiàn) FCP.FCP-DM 首先將每個(gè)連續(xù)到達(dá)的數(shù)據(jù)流劃分成若干 segment片段,將問題轉(zhuǎn)化為從不同數(shù)據(jù)流的 segment中發(fā)現(xiàn) FCP；然后基于Actor-Model計(jì)算模型構(gòu)建多級(jí)分布式挖掘框架,由多計(jì)算節(jié)點(diǎn)實(shí)現(xiàn)對(duì)不同數(shù)據(jù)流的 segment片段的逐級(jí)并行處理；最后根據(jù)Apriori算法的迭代思想,設(shè)計(jì)不同層級(jí)的數(shù)據(jù)分發(fā)策略,通過對(duì)segment的多層計(jì)算和比對(duì),最終得到FCP.

本文的主要貢獻(xiàn)如下:

· 提出 FCP-DM 分布式挖掘方法并給出相應(yīng)的分布式多級(jí)計(jì)算框架,能夠?qū)崿F(xiàn)對(duì)大規(guī)模數(shù)據(jù)流的并行處理,通過多層迭代計(jì)算和比對(duì)發(fā)現(xiàn)所有的 FCP.FCP-DM 方法具備良好的可擴(kuò)展性,僅通過增加硬件資源就可實(shí)現(xiàn)處理能力的線性增長(zhǎng).

· 解決了分布式環(huán)境下多數(shù)據(jù)流FCP挖掘所面臨的負(fù)載遷移、多計(jì)算節(jié)點(diǎn)之間FCP分發(fā)策略以及面向連續(xù)數(shù)據(jù)流的FCP增量挖掘等問題.

· 在開源流數(shù)據(jù)處理平臺(tái)S4上實(shí)現(xiàn)了FCP-DM方法,并且以山東省會(huì)城市濟(jì)南某天所有卡口的過車記錄為測(cè)試數(shù)據(jù)集進(jìn)行大量實(shí)驗(yàn),充分驗(yàn)證了該算法的各項(xiàng)性能.

2 相關(guān)工作

多數(shù)據(jù)流頻繁伴隨模式發(fā)現(xiàn)問題是由Yu等人首次提出來的[1],并給出兩種集中式挖掘算法:DIMine算法和CooMine算法.這兩種算法通過設(shè)計(jì)不同的索引結(jié)構(gòu)來提高挖掘效率并達(dá)到節(jié)省存儲(chǔ)空間的目的.然而,這兩種算法都是基于單機(jī)計(jì)算環(huán)境而設(shè)計(jì),難以直接應(yīng)用到分布式環(huán)境中,可擴(kuò)展性較差,無法應(yīng)對(duì)當(dāng)前規(guī)模急劇增長(zhǎng)的海量數(shù)據(jù)流.

已有工作中,與多數(shù)據(jù)流 FCP發(fā)現(xiàn)問題最為相似的是數(shù)據(jù)流上的頻繁模式挖掘問題.數(shù)據(jù)流上的頻繁模式(frequent pattern,簡(jiǎn)稱FP)[2]是指給定一個(gè)由連續(xù)的transaction組成的數(shù)據(jù)流(每個(gè) transaction包含多個(gè)元素),如果指定的某段時(shí)間內(nèi)該數(shù)據(jù)流共有n個(gè)transaction,而一個(gè)元素集合在其中的m(m≤n)個(gè)transaction中出現(xiàn)并且,那么該元素集合就是一個(gè)頻繁模式,sup是用戶指定的閾值.下文采用FP表示頻繁模式.

近年來,流數(shù)據(jù)FP挖掘問題受到國(guó)內(nèi)外學(xué)者的廣泛關(guān)注[2-12].Manku和Motwani提出了粘性抽樣和有損耗的計(jì)數(shù)算法來計(jì)算數(shù)據(jù)流元素集合的近似頻率[4].Yu等人提出了 FDPM算法[5],該算法能夠使用有界的內(nèi)存挖掘數(shù)據(jù)流中的頻繁元素集合.該算法是以假的消極結(jié)果為導(dǎo)向的,即某些特定的頻繁元素集合可能不會(huì)被發(fā)現(xiàn).這兩項(xiàng)工作都是基于landmark模型,它們的目標(biāo)都是挖掘數(shù)據(jù)流從開始到當(dāng)前時(shí)間所有的頻繁模式.此外,它們并不保證發(fā)現(xiàn)所有頻繁模式,而是保證獲得一個(gè)錯(cuò)誤率小于指定參數(shù)的近似結(jié)果集.

另外一些方法[2,5-12]是能夠從數(shù)據(jù)流中獲得當(dāng)前精確的頻繁模式集合.Chang等人[2]提出了一種挖掘算法,該算法通過自適應(yīng)地減小過期事務(wù)的影響從而從在線數(shù)據(jù)流中發(fā)現(xiàn)頻繁模式.Leung和 Khan等人[6]提出樹型索引結(jié)構(gòu)(DSTtree),該索引能夠從數(shù)據(jù)流中捕獲重要信息從而精確地挖掘頻繁模式.Mozafari等人則將數(shù)據(jù)流劃分成滑動(dòng)窗口,提出 versification這一新的計(jì)數(shù)概念,并基于此概念設(shè)計(jì)了 SWIM 算法.該算法是一種精確算法,其性能和擴(kuò)展性能夠根據(jù)窗口的大小進(jìn)行調(diào)整[8].KARP等人提出了一個(gè)簡(jiǎn)單、精確的數(shù)據(jù)流上的頻繁項(xiàng)集發(fā)現(xiàn)算法,并證明了該算法的時(shí)間復(fù)雜度為線性且空間復(fù)雜度為 1/θ,θ為用戶指定的支持度[9].Chi等人[10]主要研究?jī)?nèi)存受限情況下的數(shù)據(jù)流上閉合頻繁項(xiàng)集挖掘問題,并給出 Moment(maintaining closed frequent itemsets by incremental updates)算法對(duì)數(shù)據(jù)流的閉合頻繁項(xiàng)集進(jìn)行持續(xù)監(jiān)測(cè).Silva等人提出了Star FP Stream算法,用以解決從多維數(shù)據(jù)模型所產(chǎn)生的海量星型數(shù)據(jù)模式中發(fā)現(xiàn)頻繁模式[11].李海峰等人研究了數(shù)據(jù)流上頻繁項(xiàng)集挖掘時(shí)所采用的滑動(dòng)窗口模型,提出了基于事務(wù)的可變窗口滑動(dòng)模型,并在此基礎(chǔ)上提出了頻繁項(xiàng)集的挖掘算法FIMoTS[12].

以上這些方法雖然能夠從數(shù)據(jù)流中挖掘頻繁模式,但是無法被直接用來解決FCP挖掘問題.首先,FP和FCP的定義有著很大的不同.FP挖掘問題是關(guān)注一個(gè)元素集合在某個(gè)數(shù)據(jù)流上出現(xiàn)的頻率,而FCP挖掘問題則關(guān)注一個(gè)元素集合在數(shù)據(jù)流內(nèi)部和多個(gè)數(shù)據(jù)流之間的伴隨關(guān)系.此外,上述方法主要針對(duì)單個(gè)數(shù)據(jù)流的 FP挖掘問題,而本文要解決的是多數(shù)據(jù)流FCP發(fā)現(xiàn)問題,需要對(duì)多個(gè)數(shù)據(jù)流同時(shí)處理,兩者之間存在明顯區(qū)別.

值得注意的是,文獻(xiàn)[13]提出了H-stream算法,目標(biāo)是發(fā)現(xiàn)多個(gè)數(shù)據(jù)流上的頻繁模式.表面上看,H-stream算法要解決的問題似乎與本文的問題非常相似,但事實(shí)上有很大不同.雖然 H-stream算法的目標(biāo)是挖掘在多個(gè)數(shù)據(jù)流出現(xiàn)的FP,但本質(zhì)上還是先查找每個(gè)數(shù)據(jù)流的FP,然后篩選符合條件的FP.而本文中,FCP是由多個(gè)數(shù)據(jù)流共同生成,因此必須同時(shí)處理多個(gè)數(shù)據(jù)流才能發(fā)現(xiàn)FCP.此外,H-stream是一種近似算法,而本文的目標(biāo)是求解精確結(jié)果.因此,H-stream算法并不能解決本文研究的問題.此外,毛宇星等人雖然也提出一種多層關(guān)聯(lián)規(guī)則挖掘方法[14],但是分層的目的是對(duì)每層的數(shù)據(jù)進(jìn)行聚類,而本文所設(shè)計(jì)的多層挖掘模型的目的是充分發(fā)揮多計(jì)算節(jié)點(diǎn)在處理多數(shù)據(jù)流時(shí)的并行計(jì)算能力,研究的側(cè)重點(diǎn)有很大不同.

頻繁情節(jié)挖掘(frequent episode mining)是在頻繁模式挖掘基礎(chǔ)上衍生出來的又一問題,它是指從一些序列數(shù)據(jù)中發(fā)現(xiàn)有價(jià)值的或者用戶感興趣的模式序列[15,16].目前,已有若干工作研究多個(gè)行業(yè)(如通信、制造業(yè)、金融、生物信息)的頻繁情節(jié)挖掘問題,但是絕大部分工作都是采用離線方式挖掘頻繁情節(jié),這些方法也難以用于實(shí)時(shí)發(fā)現(xiàn)多數(shù)據(jù)流的頻繁伴隨模式.雖然Ao等人提出了基于episode trie的在線頻繁情節(jié)挖掘方法[15],然而該方法所關(guān)注的頻繁情節(jié)也是基于單個(gè)數(shù)據(jù)流定義的,與本文研究的問題有很大區(qū)別.此外,該方法是針對(duì)單機(jī)計(jì)算環(huán)境所設(shè)計(jì),episode trie索引結(jié)構(gòu)很難直接部署到分布式計(jì)算環(huán)境,也難以解決本文所研究的問題.

當(dāng)前,也有一些學(xué)者開始研究大數(shù)據(jù)環(huán)境下的模式發(fā)現(xiàn)[17-20],但是這類工作通常關(guān)注的是靜態(tài)數(shù)據(jù)集上的模式發(fā)現(xiàn)問題,而本文關(guān)注的是從海量動(dòng)態(tài)數(shù)據(jù)流上發(fā)現(xiàn)特定模式.

3 問題定義

為便于算法描述,本文引入并使用文獻(xiàn)[1]所給出的相關(guān)定義.

定義 1(數(shù)據(jù)流(data stream)).數(shù)據(jù)流是一組連續(xù)的按時(shí)間順序到達(dá)的元素序列.對(duì)于數(shù)據(jù)流中的任意元素oi(i為該元素在數(shù)據(jù)流中的序列號(hào)),它的標(biāo)識(shí)符和時(shí)間戳分別是idi和ti,其中,ti表示該元素出現(xiàn)的時(shí)間.

定義2(伴隨模式(co-occurrence pattern,簡(jiǎn)稱CP)).給定數(shù)據(jù)流si上的一個(gè)元素集合O={o1,o2,…,ok},如果,則認(rèn)為集合O是一個(gè)伴隨模式CP,這里,,ξ是用戶指定的閾值.CPk(k≥2)表示長(zhǎng)度為k的CP,即該CP包含k個(gè)元素.

定義3(頻繁伴隨模式(frequent co-occurrence pattern,簡(jiǎn)稱FCP)).如果一個(gè)伴隨模式CP在l個(gè)數(shù)據(jù)流中出現(xiàn),l個(gè)數(shù)據(jù)流可以表示為集合S={s1,s2,…,sl}.如果該CP滿足以下條件:

(1)l≥θ；

定義4(segment片段).給定一個(gè)數(shù)據(jù)流si,一個(gè)segment片段G(o1,o2,…,om)是數(shù)據(jù)流si的子序列,并且G滿足以下條件.

(1) |ti-tj|≤ξ,這里,oi,oj是G中任意兩個(gè)元素,ti,tj分別是oi,oj出現(xiàn)的時(shí)間；

(2) 數(shù)據(jù)流si中不存在子序列G?,使得G?是一個(gè)segment片段并且G是G?的一個(gè)嚴(yán)格的子序列.

圖1給出由多個(gè)元素構(gòu)成的一個(gè)數(shù)據(jù)流,假設(shè)每個(gè)元素出現(xiàn)的時(shí)間如下:ta=2,tc=5,td=13,tg=16,te=20,tb=26,并假設(shè)ξ=10,那么該圖中{a,c,d}和{d,g,e}為兩個(gè) segment.元素a是 segment片段G0的第 1個(gè)元素,因?yàn)閠d-ta＜ξ,tg-ta＞ξ,所以元素d是G0的最后一個(gè)元素.當(dāng)以元素c為第 1個(gè)元素構(gòu)建 segment時(shí),由于tg-tc＞ξ,{c,d,g}無法構(gòu)成segment.進(jìn)一步地,我們以元素d為第1個(gè)元素構(gòu)建segment時(shí),便可得{c,d,e}是一個(gè)segment.

Fig.1 Segment partition圖1 Segment片段

4 FCP-DM挖掘方法

引入 segment之后,每個(gè)數(shù)據(jù)流被劃分成多個(gè) segment片段,那么 FCP-DM 的目標(biāo)就是從海量數(shù)據(jù)流的segment中發(fā)現(xiàn)FCP.根據(jù)CP和FCP的定義,可以推斷出一個(gè)數(shù)據(jù)流的某個(gè)segment中的任意CP都可能與其他數(shù)據(jù)流的segment中的CP形成FCP.因此,為了得到精確結(jié)果,FCP-DM算法需要對(duì)所有數(shù)據(jù)流的segment所包含的CP進(jìn)行比對(duì).

4.1 FCP-DM算法

FCP-DM算法中,每一個(gè)數(shù)據(jù)流首先被劃分成多個(gè)segment.由于segment分布在不同的計(jì)算節(jié)點(diǎn)上,那么如何比對(duì)不同segment中的CP是一個(gè)首先要解決的問題.

在本文構(gòu)建的分布式計(jì)算環(huán)境中,一個(gè)物理節(jié)點(diǎn)可以運(yùn)行若干個(gè)邏輯計(jì)算單元(processing element,簡(jiǎn)稱PE).FCP-DM算法的思想是以CP本身為key構(gòu)建分布式哈希索引(DH-index),每個(gè)CP對(duì)應(yīng)DH-index的一個(gè)索引單元.DH-index中每個(gè)索引單元的value值包括對(duì)應(yīng)CP的出現(xiàn)時(shí)間以及它所在的segment和數(shù)據(jù)流的相關(guān)信息.這種情況下,不同segment中相同的CP被插入到DH-index時(shí),這些CP將被映射到同一個(gè)索引單元.當(dāng)FCP-DM被部署到分布式計(jì)算環(huán)境時(shí),令物理節(jié)點(diǎn)的一個(gè)PE負(fù)責(zé)一個(gè)索引單元,該索引單元每增加一條新的記錄(即來自某個(gè)segment的CP),PE都會(huì)判斷該索引單元對(duì)應(yīng)的CP是否為FCP.某個(gè)CP一旦滿足FCP定義的條件,FCP-DM會(huì)實(shí)時(shí)發(fā)現(xiàn)該FCP.

在圖 2中,給出分別屬于數(shù)據(jù)流(s1,s3,s2)的 3個(gè) segment(G0,G1,G2),根據(jù)給定的 segment,得到所有長(zhǎng)度為 2的CP集合.根據(jù)圖2的CP2集合建立DH-index索引,如圖3所示.FCP-DM算法對(duì)DH-index進(jìn)行掃描,可以得到全部長(zhǎng)度為 2的 FCP(FCP2).例如,設(shè)定θ=3,那么 FCP-DM 只需對(duì){o1,o2}進(jìn)行判斷.如果{o1,o2}出現(xiàn)在s1,s3,s2的時(shí)間間隔小于τ,那么{o1,o2}就是一個(gè)FCP.FCP-DM算法在獲得FCP2后,便利用Apriori啟發(fā)式思想[3],逐步地由FCPk(k≥2)的集合推導(dǎo)出FCPk+1(k≥2)的集合.

Fig.2 Segments and the correspondingCP2 collections圖2 生成segment的CP2集合

Fig.3 The structure of DH-index圖3 DH-index示意圖

實(shí)際應(yīng)用中,海量數(shù)據(jù)流將產(chǎn)生規(guī)模巨大的 CP,超出了單個(gè)計(jì)算節(jié)點(diǎn)的處理能力.為此,本文將 FCP-DM 算法部署到分布式計(jì)算環(huán)境,通過利用多計(jì)算節(jié)點(diǎn)的存儲(chǔ)和計(jì)算資源,采用并行計(jì)算和比對(duì)方式,實(shí)現(xiàn)海量數(shù)據(jù)流中FCP的實(shí)時(shí)發(fā)現(xiàn).下面介紹FCP-DM算法的分布式計(jì)算框架.

4.2 FCP-DM分布式計(jì)算框架

本文所提出的 FCP-DM 分布式計(jì)算框架(FCP-DM distributed framework,簡(jiǎn)稱 FCP-DMDF)采用 Actor-Model分布式計(jì)算模型,FCP-DMDF中基本邏輯處理單元是 PE(processing element),每個(gè)物理節(jié)點(diǎn)可以運(yùn)行任意多個(gè) PE.PE之間通過發(fā)送和接收事件(event)進(jìn)行數(shù)據(jù)傳輸.一個(gè) Event被表示為〈type,key,value〉,type表示Event的類型,key和 value分別表示 Event的鍵值和內(nèi)容.每個(gè) PE指定其所接收的 Event的 type和 key值.FCP-DMDF根據(jù)PE所指定的type和key值為其分發(fā)Event.任意一個(gè)PE可以接受其他PE發(fā)送的Event,也可以將本地計(jì)算結(jié)果以Event的形式發(fā)送給其他PE.對(duì)于一個(gè)新的Event,如果已有的PE無法對(duì)其進(jìn)行處理,那么FCP-DMDF將自動(dòng)構(gòu)建一個(gè)新的PE處理該Event.

FCP-DMDF是一個(gè)多級(jí)框架,主要包括數(shù)據(jù)接收層、數(shù)據(jù)分割層和算法實(shí)現(xiàn)層.圖4是FCP-DMDF框架示意圖.

Fig.4 The framework of FCP-DMDF圖4 FCP-DMDF示意圖

數(shù)據(jù)接收層的任務(wù)是接收持續(xù)到達(dá)的數(shù)據(jù)流.每個(gè)數(shù)據(jù)流由一個(gè)ReceivePE負(fù)責(zé),ReceivePE的任務(wù)是接收數(shù)據(jù)流并隨時(shí)間延續(xù)將每個(gè)數(shù)據(jù)流分割成若干segment,然后將segment以SegmentEvent的形式發(fā)送至數(shù)據(jù)分割層的PartitionPE.

數(shù)據(jù)分割層的任務(wù)是生成每個(gè)segment所有長(zhǎng)度為2的CP.該層中每個(gè)PartitionPE的任務(wù)是接收來自不同數(shù)據(jù)流的segment,并計(jì)算每個(gè)segment包含的所有長(zhǎng)度為2的CP.然后以CP本身為key值將每一個(gè)CP以CPEvent的形式分發(fā)至算法實(shí)現(xiàn)層的PE.在該層中,每個(gè)PartitionPE負(fù)責(zé)一個(gè)或多個(gè)segment,并能夠根據(jù)負(fù)載對(duì)segment進(jìn)行數(shù)據(jù)遷移,第4.3.1節(jié)將詳細(xì)討論該問題.

算法實(shí)現(xiàn)層是 FCP-DMDF的主體部分.該層包含多個(gè)Computing-Level,Computing-Level-i表示第i層Computing-Level,負(fù)責(zé)發(fā)現(xiàn)長(zhǎng)度為(i+1)的FCP.FCP-DM算法在產(chǎn)生長(zhǎng)度為i的FCP時(shí)包含兩步操作:CPi的聚合和FCPi的檢測(cè),因此,每層Computing-Level-i包含兩類PE:CPi-PE和FCPi-PE.當(dāng)i≥3時(shí),由FCPi-1集合得到FCPi集合的迭代計(jì)算步驟如下.

①CPi-PE將可能構(gòu)成CPi的一組FCPi-1進(jìn)行聚合,生成待檢測(cè)的CPi,并將符合條件的CPi以CPEvent的形式發(fā)送至FCPi-PE.分布式環(huán)境下,如何將可能構(gòu)成CPi的一組FCPi-1由不同的PE匯聚至同一個(gè)CPi-PE是一個(gè)不小的挑戰(zhàn),為此,本文設(shè)計(jì)了基于〈key,value〉的FCP分發(fā)策略(該策略將在第4.3.2節(jié)詳細(xì)加以討論)；

②FCPi-PE接收來自不同CPi-PE的CPi進(jìn)行檢測(cè)并判斷其是否為FCPi,然后將發(fā)現(xiàn)的FCPi以FCPEvent的形式發(fā)送至Computing-Level-(i+1)層的CPi+1-PE.

③ 重復(fù)步驟①和②,CPi+1-PE將接收的FCPi合并生成CPi+1,然后由FCPi+1-PE檢測(cè)CPi+1是否為FCPi+1.根據(jù)上述步驟,隨著i的增長(zhǎng),算法實(shí)現(xiàn)層能夠通過逐步迭代的方式發(fā)現(xiàn)所有的FCP.

需要說明的是,當(dāng)i=2時(shí),由于CP2由PartitionPE直接生成,因此,每個(gè)CP2-PE接收到的是一組來自不同數(shù)據(jù)流的CP2,CP2-PE將該組CP2進(jìn)行聚合后發(fā)送至FCP2-PE.由于現(xiàn)實(shí)應(yīng)用中 FCP的最大長(zhǎng)度無法預(yù)先確定,因此FCP-DM計(jì)算框架將根據(jù)FCP的長(zhǎng)度自適應(yīng)地增加或減少Computing-Level的層數(shù),從而發(fā)現(xiàn)給定數(shù)據(jù)流中所有FCP.

4.3 構(gòu)建FCP-DMDF面臨的挑戰(zhàn)與解決方案

本節(jié)主要研究分布式環(huán)境下多數(shù)據(jù)流FCP挖掘所面臨的負(fù)載遷移、FCP分發(fā)策略以及面向連續(xù)數(shù)據(jù)流的FCP增量挖掘等挑戰(zhàn).

4.3.1 數(shù)據(jù)分割層的負(fù)載均衡策略

數(shù)據(jù)分割層將生成每一個(gè)segment片段所有的長(zhǎng)度為2的CP,并將CP進(jìn)行分發(fā).實(shí)際應(yīng)用中,數(shù)據(jù)分割層的每個(gè)計(jì)算單元可能負(fù)責(zé)若干個(gè) segment,如果數(shù)據(jù)分布不均勻,將造成不同計(jì)算單元之間的負(fù)載失衡,降低整個(gè)計(jì)算框架的挖掘效率.

為解決這一問題,本文設(shè)計(jì)動(dòng)態(tài)遷移策略來保證計(jì)算單元之間的負(fù)載均衡.為便于描述,令PEr表示數(shù)據(jù)接收層的任意一個(gè) ReceivePE,令表示數(shù)據(jù)分割層任意兩個(gè)不同的 PartitionPE.此外,令[wh,wk]表示元素序列號(hào)的范圍,如果某個(gè)segment片段首個(gè)元素oi的idi∈[wh,wk],那么該segment位于范圍[wh,wk].

(1) 對(duì)PEip的 key值范圍[wh,wk]進(jìn)行拆分,生成[wh,wj]和[wj,wk](wh

(2)PEpi將[wj,wk]范圍內(nèi)未處理的segment以SegmentEvent的形式發(fā)送至數(shù)據(jù)分割層的新的邏輯計(jì)算單元將由FCP-DMDF在發(fā)出SegmentEvent后創(chuàng)建.可接收SegmentEvent的key值范圍為[wj,wk].

圖5是負(fù)載遷移執(zhí)行過程的示意圖.其中,圖5(a)表示初始狀態(tài)下數(shù)據(jù)輸入層的PEr根據(jù)的key值范圍向其發(fā)送相應(yīng)的segment.圖5(b)的①②③步則表示上述負(fù)載遷移3個(gè)步驟的執(zhí)行過程.其中,

③PEr將后續(xù)到達(dá)的位于[wj,wk]的segment發(fā)送至.

Fig.5 The procedure of workload transfer圖5 負(fù)載遷移示意圖

4.3.2 分布式環(huán)境下FCP分發(fā)策略

FCP-DM算法逐步地由FCPk的集合推導(dǎo)出FCPk+1的集合,這在單機(jī)環(huán)境下不難實(shí)現(xiàn).但在分布式環(huán)境下卻面臨新的問題.

(1) 由于數(shù)據(jù)分布在多個(gè)計(jì)算節(jié)點(diǎn)上,單個(gè)計(jì)算節(jié)點(diǎn)無法確定哪些FCPk能夠合并生成FCPk+1.

(2) 為解決第1個(gè)問題,需要將能夠合并生成FCPk+1的FCPk分發(fā)至同一個(gè)計(jì)算單元,但是如何將這些FCPk分發(fā)至同一個(gè)計(jì)算單元?jiǎng)t又是一個(gè)新的挑戰(zhàn).例如,{a,b,c}和{b,c,d}是兩個(gè)長(zhǎng)度為3的FCP,FCP-DM算法將會(huì)對(duì){a,b,c}和{b,c,d}進(jìn)行合并,生成長(zhǎng)度為4的CP{a,b,c,d},繼而判斷{a,b,c,d}是否為FCP4.分布式環(huán)境下,{a,b,c}和{b,c,d}可能分布在不同的計(jì)算節(jié)點(diǎn)n1和n2上,n1和n2無法直接獲取對(duì)方的數(shù)據(jù),這為生成伴隨模式{a,b,c,d}增加了很大難度.

為解決上述問題,本文設(shè)計(jì)基于〈key,value〉的 FCP分發(fā)策略.該策略首先令能夠合并生成CPk+1的FCPk具有相同的key值,然后令每個(gè)key值由FCP-DMDF中唯一的計(jì)算單元負(fù)責(zé).此時(shí),根據(jù)key值與計(jì)算單元的映射關(guān)系,可將具有相同key值的FCPk分發(fā)至同一個(gè)計(jì)算單元,繼而由該計(jì)算單元對(duì)這些FCPk進(jìn)行聚合,生成相應(yīng)的CPk+1,最后判斷CPk+1是否為FCPk+1.

假設(shè)FCPk和FCP?k分別表示兩個(gè)不同的長(zhǎng)度為k的FCP,FCPk+1表示一個(gè)長(zhǎng)度為(k+1)的FCP.如果,那么FCPk和FCP?k至少含有(k-1)個(gè)相同元素.將FCPk的任意一個(gè)由(k-1)個(gè)不同元素構(gòu)成的集合記作ek,那么FCPk將包含個(gè)不同的集合.對(duì)于任意集合,可能存在一個(gè)頻繁伴隨模式滿足,這種情況下,可能產(chǎn)生CPk+1.因此,對(duì)于任意一個(gè)FCPk,以每個(gè)為key,以FCPk自身為value生成k個(gè)形如 的元組,并將每個(gè)元組根據(jù)分發(fā)到不同的PE,這使得含有相同的不同元組將被發(fā)送至同一個(gè)PE.該類PE接收到這些元組之后,能夠?qū)⑦@些元組進(jìn)行聚合,構(gòu)成CPk+1,并將該CPk+1發(fā)送至下一層計(jì)算單元由其判斷該CPk+1是否為FCPk+1.

4.3.3 FCP連續(xù)增量挖掘方法

由于數(shù)據(jù)流持續(xù)到達(dá)且沒有邊界,新的數(shù)據(jù)流到達(dá)之后,可能與已有數(shù)據(jù)形成新的 FCP,因此需要對(duì)連續(xù)到達(dá)的數(shù)據(jù)流持續(xù)監(jiān)控,設(shè)計(jì)增量挖掘方法實(shí)時(shí)發(fā)現(xiàn)由新到達(dá)的數(shù)據(jù)流所形成的 FCP.在增量挖掘方法中,我們始終維護(hù)FCP-DMDF框架,并將已處理的有效數(shù)據(jù)始終在內(nèi)存中進(jìn)行維護(hù).新的數(shù)據(jù)流到達(dá)之后,只需將這些數(shù)據(jù)與已有的有效數(shù)據(jù)進(jìn)行比對(duì),即可發(fā)現(xiàn)新生成的FCP.

由于數(shù)據(jù)流的規(guī)模無限擴(kuò)大,導(dǎo)致無法在內(nèi)存存儲(chǔ)所有數(shù)據(jù),需要對(duì)過期數(shù)據(jù)進(jìn)行刪除.由于形成FCP的所有元素的時(shí)間間隔不大于τ,如果某個(gè)元素的產(chǎn)生時(shí)間與當(dāng)前時(shí)間的間隔大于τ,那么該元素可以被安全刪除,原因是它不可能和其他元素共同構(gòu)成新的FCP.從節(jié)省內(nèi)存角度考慮,則應(yīng)該實(shí)時(shí)刪除過期元素.然而,如果令每個(gè)計(jì)算節(jié)點(diǎn)持續(xù)監(jiān)視其維護(hù)的每條數(shù)據(jù)是否過期,那么該操作將產(chǎn)生很大的計(jì)算代價(jià).為使內(nèi)存使用效率和計(jì)算代價(jià)兩方面達(dá)到一個(gè)平衡,本文設(shè)計(jì)了延遲刪除策略.該策略中,每個(gè)計(jì)算節(jié)點(diǎn)每隔Δt時(shí)間令其所有的邏輯計(jì)算單元執(zhí)行一次對(duì)過期數(shù)據(jù)的刪除操作.實(shí)驗(yàn)部分,我們將Δt的默認(rèn)值設(shè)置為τ.Δt值越大,刪除操作的計(jì)算代價(jià)越小,但是內(nèi)存消耗增大；Δt值越小,內(nèi)存消耗越少,但刪除操作代價(jià)增大.因此,可以調(diào)整Δt的值來平衡內(nèi)存使用效率和刪除計(jì)算代價(jià).實(shí)驗(yàn)部分將對(duì)Δt對(duì)于算法內(nèi)存使用情況的影響進(jìn)行測(cè)試.

由于 FCP-DMDF始終在內(nèi)存中維護(hù)有效數(shù)據(jù),那么對(duì)于一個(gè)最新到達(dá)的 segment,如果它能夠和已有數(shù)據(jù)形成FCP,那么只需要在已有數(shù)據(jù)的基礎(chǔ)上處理該segment,便可發(fā)現(xiàn)由新到達(dá)的segment與已有segment所形成的所有FCP,從而實(shí)現(xiàn)多數(shù)據(jù)流FCP的連續(xù)增量挖掘.為解決這一問題,本文設(shè)計(jì)了Incremental-mining算法并給出算法的偽代碼.對(duì)于一個(gè)新生成的segment,Incremental-mining算法首先生成該segment的所有CP2,之后對(duì)應(yīng)的PE將CP2與已有數(shù)據(jù)進(jìn)行比對(duì),得到FCP2.然后,基于Apriori啟發(fā)式思想,由對(duì)應(yīng)的PE對(duì)FCP2所能構(gòu)成的 FCP進(jìn)行逐級(jí)并行檢測(cè),從而得到該 segment與已有數(shù)據(jù)形成的所有 FCP.在 Incremental-mining算法對(duì)segment的處理過程中,僅有少量PE參與計(jì)算,因此可節(jié)省計(jì)算資源.

Incremental-mining算法.

圖6給出在FCP-DMDF上利用Incremental-mining算法發(fā)現(xiàn)FCP3的一個(gè)例子.在該例子中,假設(shè)數(shù)據(jù)流S1至Si的segment已被處理,此時(shí)數(shù)據(jù)流Si+1產(chǎn)生一個(gè)新的segment(Gi+1),下面是利用Incremental-mining算法發(fā)現(xiàn)由新產(chǎn)生的 segment所形成的 FCP.首先由 ReceivePE將每個(gè)數(shù)據(jù)流劃分成不同的 segment；對(duì)于一個(gè)segment,PartitionPE生成其包含的所有CP2.CP2-PE將來自不同數(shù)據(jù)流的相同CP2發(fā)送至FCP2-PE,然后由FCP2-PE判斷某個(gè)CP2是否為FCP2.FCP2-PE根據(jù)第 4.3.2節(jié)介紹的分發(fā)策略,將得到的FCP2發(fā)送至對(duì)應(yīng)的CP3-PE,每個(gè)CP3-PE將收到的FCP2進(jìn)行聚合,生成CP3,最后由FCP3-PE檢測(cè)CP3是否為FCP3.

Fig.6 Procedure of miningFCP3 (θ=3)圖6FCP3挖掘示意圖(θ=3)

4.3.4 Incremental-mining算法時(shí)間復(fù)雜度分析

分布式環(huán)境下,Incremental-mining算法處理一個(gè)長(zhǎng)度為m的 segment片段G的時(shí)間復(fù)雜度的下界為,最壞情況下的時(shí)間復(fù)雜度為,z表示運(yùn)行Incremental-mining算法的一層CPi-PE或FCPi-PE的數(shù)量.

證明:Incremental-mining算法處理G時(shí),首先生成個(gè)CP2,并檢測(cè)每一個(gè)CP2是否為FCP2.如果每一個(gè)CP2均不是FCP2,則算法終止.為了便于描述,假設(shè)個(gè)CP2均勻分布到z個(gè)PE上進(jìn)行并行處理,那么每個(gè)PE負(fù)責(zé)CP2的數(shù)量約為,單個(gè)PE的計(jì)算時(shí)間為(td為單個(gè)CP2的檢測(cè)時(shí)間).此時(shí)的時(shí)間復(fù)雜度為.

下面討論Incremental-mining算法最壞情況下的時(shí)間復(fù)雜度.當(dāng)G能夠形成FCPm時(shí),Incremental-mining算法的計(jì)算時(shí)間最長(zhǎng).一般情況下,只有部分伴隨模式能夠構(gòu)成頻繁伴隨模式.不失一般性,假設(shè)G的長(zhǎng)度為i的子集是FCPi的概率為p(0

雖然Incremental-mining算法最壞情況下的時(shí)間復(fù)雜度為,但它的實(shí)際計(jì)算時(shí)間要小很多,原因如下.

(1) 真實(shí)情況下p值非常小,因此需要檢測(cè)的FCPi數(shù)量遠(yuǎn)小于,即；

(2) Incremental-mining算法運(yùn)行在多個(gè)物理計(jì)算節(jié)點(diǎn)之上,能夠利用大量的PE實(shí)現(xiàn)對(duì)FCPi的并行檢測(cè),將大大縮短計(jì)算時(shí)間.因此,物理節(jié)點(diǎn)越多,總的 PE的數(shù)量越多(即z值越大),計(jì)算時(shí)間越短,這與實(shí)驗(yàn)部分中圖10所示結(jié)果一致.

5 實(shí) 驗(yàn)

首先,本文基于Apache開源流數(shù)據(jù)處理平臺(tái)S4[21]實(shí)現(xiàn)了FCP-DMDF.S4中的邏輯處理單元稱為PE,每個(gè)物理節(jié)點(diǎn)可以運(yùn)行任意多個(gè)PE.基于S4平臺(tái)實(shí)現(xiàn)FCP-DMDF時(shí),FCP-DMDF中PE的功能可以由S4的PE來實(shí)現(xiàn).S4中PE之間通過發(fā)送和接收Event進(jìn)行數(shù)據(jù)傳輸.每個(gè)PE指定其所接收的Event的類型和key值.任意一個(gè)PE可以接受其他PE發(fā)送的Event,也可以將本地計(jì)算結(jié)果以Event的形式發(fā)送給其他PE.對(duì)一個(gè)新產(chǎn)生的Event,如果已有的PE根據(jù)Event的類型和key值都無法處理該Event,那么S4將自動(dòng)創(chuàng)建一個(gè)新的PE來處理該Event.由于S4的并行處理思想被當(dāng)前大多數(shù)流數(shù)據(jù)分布式計(jì)算平臺(tái)所采用,因此,本文所設(shè)計(jì)的FCP-DM分布式挖掘方法也易于部署到Storm、Spark Streaming等平臺(tái).

5.1 實(shí)驗(yàn)配置

實(shí)驗(yàn)采用8臺(tái)戴爾 R210的服務(wù)器,每臺(tái)服務(wù)器配置主頻2.4GHz的Intel處理器和8G內(nèi)存,服務(wù)器之間通過1Gbps帶寬的以太網(wǎng)相連.分布式平臺(tái)采用S4-0.6.0版本(http://incubator.apache.org/s4/download/).以山東省濟(jì)南市2015年5月1日7:00～12:00產(chǎn)生的320萬條過車記錄(vehicle passing records,簡(jiǎn)稱VPR)為測(cè)試數(shù)據(jù)集,從中挖掘頻繁伴隨車輛.該數(shù)據(jù)集中每條過車記錄可以看作是一個(gè)四元組〈ri,li,mi,tmi〉,ri表示該記錄的編號(hào),li表示該車的車牌號(hào),mi表示該記錄所對(duì)應(yīng)的監(jiān)控卡口編號(hào),tmi表示該記錄產(chǎn)生的時(shí)間.整個(gè)測(cè)試集中過車記錄是由不同卡口產(chǎn)生的,如果將同一個(gè)卡口連續(xù)產(chǎn)生的過車記錄看成一個(gè)數(shù)據(jù)流,那么若干卡口就對(duì)應(yīng)若干數(shù)據(jù)流.實(shí)驗(yàn)中要查找的伴隨車輛是指很短時(shí)間內(nèi)連續(xù)通過某卡口,并在一段時(shí)間內(nèi)以同樣方式通過多個(gè)卡口的一組車輛.因此,在測(cè)試數(shù)據(jù)集中發(fā)現(xiàn)伴隨車輛就相當(dāng)于從多個(gè)卡口產(chǎn)生的數(shù)據(jù)流中發(fā)現(xiàn) FCP.FCP定義中相關(guān)參數(shù)(ξ、τ和θ)將對(duì) FCP-DM 算法的效率和挖掘結(jié)果產(chǎn)生影響,因此,每組實(shí)驗(yàn)均標(biāo)明各個(gè)參數(shù)的取值.缺省情況下,ξ=60(s),θ=4,τ=2(h).每組實(shí)驗(yàn)均重復(fù)5次,取5次結(jié)果的平均值作為最終實(shí)驗(yàn)結(jié)果.

5.2 實(shí)驗(yàn)內(nèi)容

5.2.1 FCP-DM算法效率評(píng)估

圖7將測(cè)試數(shù)據(jù)集模擬為523個(gè)數(shù)據(jù)流,分別以20 000VPR/s、40 000VPR/s、60 000 VPR/s、80 000 VPR/s、100 000 VPR/s的速率發(fā)送至FCP-DMDF,以測(cè)試系統(tǒng)的抗壓性.實(shí)驗(yàn)結(jié)果表明,FCP-DM算法的最大處理能力約為60 000條/s.在該組實(shí)驗(yàn)中,我們?cè)趦?nèi)存中設(shè)置一個(gè)隊(duì)列Q用以緩存到達(dá)的VPR.FCP-DM(t)表示FCP-DM處理測(cè)試數(shù)據(jù)集所需總的時(shí)間,FCP-DM(Q)表示隊(duì)列Q緩存 VPR的最大數(shù)量.在圖 7中,當(dāng)數(shù)據(jù)到達(dá)速率小于60 000條/s時(shí),隨著數(shù)據(jù)速率的提高,FCP-DM(t)明顯下降.此時(shí),由于FCP-DM處理速率大于數(shù)據(jù)到達(dá)速率,所以FCP-DM(Q)趨近于 0.當(dāng)速率達(dá)到 60 000 VPR/s后,FCP-DM(t)趨于平穩(wěn),表明算法是以最大處理能力運(yùn)行的,FCP-DM(Q)開始明顯增加.

圖8表明,Yu等人提出的CooMine算法的最大處理能力約為8 000VPR/s(單個(gè)計(jì)算節(jié)點(diǎn))[1].通過圖7和圖8的比較可以發(fā)現(xiàn),FCP-DM在8個(gè)計(jì)算節(jié)點(diǎn)上的處理能力幾乎是CooMine算法的8倍.也就是說,FCP-DM在8個(gè)計(jì)算節(jié)點(diǎn)的處理效率幾乎相當(dāng)于在8個(gè)計(jì)算節(jié)點(diǎn)上分別運(yùn)行CooMine算法的效率總和.這是因?yàn)?CooMine算法是針對(duì)單機(jī)環(huán)境設(shè)計(jì)的多數(shù)據(jù)流頻繁伴隨模式發(fā)現(xiàn)算法,該算法為了節(jié)省內(nèi)存(壓縮 segment)和減少索引維護(hù)代價(jià),設(shè)計(jì)和采用Seg-tree樹型索引結(jié)構(gòu).本文設(shè)計(jì)的FCP-DM算法是針對(duì)分布式計(jì)算環(huán)境,擁有較充裕的內(nèi)存,因此采用了分布式哈希索引.雖然 CooMine算法對(duì)基于 Seg-tree的數(shù)據(jù)查找操作進(jìn)行了大量?jī)?yōu)化,但是FCP-DM算法中基于哈希索引的查詢操作(如查找元素、伴隨模式等)要比CooMine算法中基于Seg-tree的查詢操作具備更高的查詢效率,而哈希索引的內(nèi)存使用效率要低于 Seg-tree索引結(jié)構(gòu).因此,在 8臺(tái)機(jī)器上運(yùn)行FCP-DM算法的計(jì)算效率接近于在8個(gè)計(jì)算節(jié)點(diǎn)上單獨(dú)運(yùn)行的CooMine算法的計(jì)算效率之和.

Fig.7 Processing capability of FCP-DM圖7 FCP-DM方法處理能力

Fig.8 Processing capability of CooMine圖8 CooMine算法處理能力

為更加直觀地比較FCP-DM算法和CooMine算法的性能,分別令這兩種算法處理相同規(guī)模的過車記錄數(shù)據(jù)集,并調(diào)整過車記錄數(shù)據(jù)集的規(guī)模來比較兩者的處理時(shí)間.該組實(shí)驗(yàn)是將整個(gè)數(shù)據(jù)集一次性地加載到系統(tǒng)中,算法處理時(shí)間是指從處理第 1條數(shù)據(jù)開始至最后一條數(shù)據(jù)處理完成的時(shí)間跨度.圖 9所示的實(shí)驗(yàn)結(jié)果表明,FCP-DM算法(采用8個(gè)物理節(jié)點(diǎn))的處理時(shí)間要明顯小于CooMine算法的處理時(shí)間,并且隨著數(shù)據(jù)規(guī)模的擴(kuò)大,FCP-DM算法處理時(shí)間的增長(zhǎng)速率明顯小于CooMine算法的時(shí)間增長(zhǎng)速率.

圖10測(cè)試數(shù)據(jù)到達(dá)速率為40 000條/s時(shí)FCP-DM算法處理不同規(guī)模數(shù)據(jù)時(shí)的可擴(kuò)展性.該組實(shí)驗(yàn)中,分別采用2、4、6、8個(gè)計(jì)算節(jié)點(diǎn)處理不同規(guī)模的數(shù)據(jù)集.實(shí)驗(yàn)結(jié)果表明,隨著計(jì)算節(jié)點(diǎn)個(gè)數(shù)的增加,FCP-DM的處理時(shí)間明顯下降.VPR數(shù)量越多,處理時(shí)間的下降趨勢(shì)越明顯,表明FCP-DM方法在處理大規(guī)模數(shù)據(jù)流時(shí)具備良好的可擴(kuò)展性.

Fig.9 Comparison of FCP-DM and CooMine w.r.t. processing time圖9 FCP-DM與CooMine處理時(shí)間比較

Fig.10 The scalability of FCP-DM圖10 FCP-DM的可擴(kuò)展性

5.2.2 FCP-DM算法相關(guān)參數(shù)對(duì)算法性能影響的評(píng)價(jià)

圖11和圖12主要對(duì)本文所采取的負(fù)載遷移策略的性能進(jìn)行驗(yàn)證,主要測(cè)試單個(gè)PartitionPE所能承載的segment的最大數(shù)量β、數(shù)據(jù)到達(dá)速率以及數(shù)據(jù)集規(guī)模對(duì)于 PartitionPE數(shù)量的影響.該組實(shí)驗(yàn)共采用4個(gè)物理計(jì)算節(jié)點(diǎn).實(shí)驗(yàn)開始之前,我們對(duì)測(cè)試數(shù)據(jù)集中的所有元素的標(biāo)識(shí)進(jìn)行遍歷,得到一個(gè)能夠包含測(cè)試數(shù)據(jù)集中所有元素的標(biāo)識(shí)范圍[ws,we].實(shí)驗(yàn)開始時(shí),初始化一個(gè)PartitionPE,令其key值范圍為[ws,we],也就是說,所有初始的PartitionPE能夠接收所有的 segment.當(dāng)初始 PartitionPE接收但來不及處理的 segment數(shù)量達(dá)到閾值β時(shí),該P(yáng)artitionPE就會(huì)分裂,這樣就會(huì)產(chǎn)生多個(gè) PartitionPE.這里需要注意的是,PartitionPE一旦創(chuàng)建就不會(huì)被刪除,本組實(shí)驗(yàn)將記錄處理過程中所有的PartitionPE的數(shù)量.

圖11的實(shí)驗(yàn)結(jié)果表明,當(dāng)β值一定時(shí),隨著數(shù)據(jù)到達(dá)速率的增加,PartitionPE的個(gè)數(shù)明顯增多,這是因?yàn)閿?shù)據(jù)到達(dá)越快,PartitionPE所積壓的未處理的 segment越多,這樣發(fā)生負(fù)載遷移的次數(shù)越多,導(dǎo)致更多的 PartitionPE產(chǎn)生.當(dāng)數(shù)據(jù)到達(dá)速率一定時(shí)(例如30 000VPR/s時(shí)),隨著β值的增大,PartitionPE的數(shù)量逐漸減少.這是因?yàn)殡S著β值的增大,PartitionPE能夠緩存的segment增多,使得PartitionPE的數(shù)量減少.圖12中,令FCP-DM處理不同規(guī)模的數(shù)據(jù)集并觀察PartitionPE的數(shù)量.當(dāng)數(shù)據(jù)到達(dá)速率和β值固定時(shí),我們發(fā)現(xiàn)數(shù)據(jù)集的規(guī)模對(duì)PartitionPE的數(shù)量沒有顯著影響,這表明PartitionPE的數(shù)量只與數(shù)據(jù)到達(dá)速率和β值有關(guān),與待處理的數(shù)據(jù)集規(guī)模無關(guān).

Fig.11 Number of PartitionPE w.r.t.β圖11 參數(shù)β對(duì)PartitionPE個(gè)數(shù)的影響

Fig.12 Number of PartitionPE w.r.t. scale of data圖12 數(shù)據(jù)集規(guī)模對(duì)PartitionPE個(gè)數(shù)的影響

在延遲刪除策略中,調(diào)整參數(shù)Δt的值可以改變對(duì)過期數(shù)據(jù)的刪除周期.圖13測(cè)試了參數(shù)Δt對(duì)于算法運(yùn)行時(shí)內(nèi)存使用狀況的影響.實(shí)驗(yàn)策略是隨機(jī)抽取100萬條VPR作為測(cè)試數(shù)據(jù)集,令數(shù)據(jù)發(fā)送速率為10 000VPR/s,然后觀察不同時(shí)刻的所有計(jì)算節(jié)點(diǎn)的內(nèi)存使用狀態(tài).圖13的縱坐標(biāo)表示所有計(jì)算節(jié)點(diǎn)運(yùn)行FCP-DM算法時(shí)消耗的內(nèi)存之和,橫坐標(biāo)表示算法的運(yùn)行時(shí)間.實(shí)驗(yàn)結(jié)果表明,算法運(yùn)行初期 Δt取不同值時(shí),內(nèi)存使用量均增大,這是因?yàn)榇藭r(shí)內(nèi)存中沒有過期數(shù)據(jù),致使內(nèi)存累積的數(shù)據(jù)增加.當(dāng)算法運(yùn)行50s之后,內(nèi)存使用量出現(xiàn)明顯波動(dòng),這是因?yàn)樗惴扛?Δt時(shí)間都會(huì)對(duì)過期數(shù)據(jù)進(jìn)行刪除.總的來說,Δt取值越小,平均的內(nèi)存使用量也越少,但是刪除次數(shù)也相對(duì)增加.圖14測(cè)試了參數(shù)ξ對(duì)FCP-DM處理時(shí)間的影響.圖14所示實(shí)驗(yàn)結(jié)果表明,算法處理時(shí)間隨著ξ值的增大而增加.這是因?yàn)?ξ越大,segment長(zhǎng)度越大,此時(shí)所產(chǎn)生的CP數(shù)量也越大.由于FCP-DM需要對(duì)所有的CP進(jìn)行處理,因此,FCP-DM算法的處理時(shí)間隨著CP數(shù)量的增大而明顯增加.

FCP-DM算法的目標(biāo)是準(zhǔn)確發(fā)現(xiàn)給定數(shù)據(jù)集中所有的FCP,即查全率和查準(zhǔn)率應(yīng)為100%.由于CooMine算法的目標(biāo)也是準(zhǔn)確發(fā)現(xiàn)給定數(shù)據(jù)流中所有的FCP[1],其查全率和查準(zhǔn)率均為100%.表1比較了FCP-DM算法和CooMine算法在同一數(shù)據(jù)集上所發(fā)現(xiàn)的FCP數(shù)量.當(dāng)參數(shù)θ和k取值一定時(shí),兩種算法在該實(shí)驗(yàn)數(shù)據(jù)集上發(fā)現(xiàn)的FCP數(shù)量相同,從而驗(yàn)證了FCP-DM算法的查全率和查準(zhǔn)率均為100%.

Fig.13 Memory consumption w.r.t. Δt圖13 參數(shù)Δt對(duì)于內(nèi)存使用的影響

Fig.14 Processing time w.r.t.ξ圖14ξ對(duì)處理時(shí)間的影響

Table 1 Comparison of FCP-DM and CooMine w.r.t. the number of discovered FCP表1 FCP-DM和CooMine挖掘結(jié)果數(shù)量比較

5.2.3 FCP-DM挖掘結(jié)果評(píng)價(jià)

圖15和圖16主要測(cè)試數(shù)據(jù)規(guī)模和參數(shù)θ對(duì)FCP-DM算法挖掘結(jié)果的影響,其中,k表示FCP的長(zhǎng)度,ξ、τ和θ的含義見定義2和定義3.該組實(shí)驗(yàn)中,一個(gè)FCP代表一組頻繁伴隨車輛.圖15所示實(shí)驗(yàn)結(jié)果表明,當(dāng)FCP定義中相關(guān)參數(shù)(ξ、τ、θ)的值固定時(shí),隨著數(shù)據(jù)規(guī)模的擴(kuò)大,FCP-DM發(fā)現(xiàn)的FCP數(shù)量逐漸增多；當(dāng)數(shù)據(jù)規(guī)模一定時(shí),FCP的長(zhǎng)度(k值)越大,FCP的數(shù)量越少,也就是說,用戶指定一組頻繁伴隨車輛中的車輛數(shù)目越大,現(xiàn)實(shí)中這樣的車輛組合越少,越符合我們的直觀認(rèn)識(shí).FCP定義中參數(shù)θ將對(duì)FCP的數(shù)量產(chǎn)生較大影響,圖16所示實(shí)驗(yàn)結(jié)果表明,隨著θ值的增大,FCP數(shù)量變小,也就是說,如果用戶要求一組 FCP伴隨出現(xiàn)的數(shù)據(jù)流越多,那么這樣的FCP數(shù)量越少,實(shí)驗(yàn)結(jié)果同樣符合預(yù)期.目前,FCP-DM算法已被應(yīng)用至山東省某地市智能交通綜合管控平臺(tái),用于快速發(fā)現(xiàn)頻繁伴隨車輛.圖17和圖18給出了FCP-DM算法在該交通管控平臺(tái)發(fā)現(xiàn)頻繁伴隨車輛的部分結(jié)果展示.其中,地圖中的紅色箭頭是車輛伴隨行駛方向,圖片右側(cè)是發(fā)現(xiàn)的頻繁伴隨車輛組合.

Fig.15 Number of FCP w.r.t. scale of data圖15 數(shù)據(jù)規(guī)模對(duì)FCP數(shù)量的影響

Fig.16 Number of FCP w.r.t. θ圖16 參數(shù)θ對(duì)FCP數(shù)量的影響

Fig.17 Demonstration of applying FCP-DM (1)圖17 FCP-DM實(shí)際應(yīng)用展示(1)

Fig.18 Demonstration of applying FCP-DM (2)圖18 FCP-DM實(shí)際應(yīng)用展示(2)

6 總 結(jié)

本文研究了海量多數(shù)據(jù)流 FCP挖掘問題,提出了 FCP-DM——一個(gè)可部署在分布式流數(shù)據(jù)處理平臺(tái)的分布式挖掘方法.在該方法中,本文重點(diǎn)研究分布式環(huán)境下多計(jì)算節(jié)點(diǎn)協(xié)同挖掘大規(guī)模數(shù)據(jù)流所形成的 FCP時(shí)面臨的負(fù)載均衡問題、數(shù)據(jù)分布式存儲(chǔ)背景下的FCP生成問題以及連續(xù)數(shù)據(jù)流的FCP增量挖掘問題,最后通過大量實(shí)驗(yàn)對(duì) FCP-DM 方法的各項(xiàng)性能和挖掘結(jié)果進(jìn)行充分驗(yàn)證,并給出了算法在實(shí)際應(yīng)用中的效果展示.后續(xù)工作將繼續(xù)研究如何對(duì)發(fā)現(xiàn)的大量FCP進(jìn)行排序優(yōu)化,從而將更符合用戶偏好的FCP排在挖掘結(jié)果的前面.