基于Spark 的大規(guī)模單圖頻繁子圖算法

蔣來好 朱志祥 趙子晨

（1.西安郵電大學(xué)計算機學(xué)院 西安 710061）（2.陜西省信息化工程研究院 西安 710061）

1 引言

教育信息化、網(wǎng)絡(luò)化是高?，F(xiàn)代化的必經(jīng)之路。隨著校園卡存儲事物的繁瑣及工作量的增加，進而保存在服務(wù)器中的數(shù)據(jù)量正以驚人的速度增長，因此服務(wù)器的負(fù)擔(dān)也隨之加大，而作為管理者們期望從這些龐大的數(shù)據(jù)中獲取有用的信息。目前，校園一卡通的數(shù)據(jù)挖掘［1］越來越被重視，但對消費流水?dāng)?shù)據(jù)的深入研究則不多見，主要因為針對大規(guī)模的消費流水?dāng)?shù)據(jù)沒有合適的處理算法［2］，頻繁軌跡挖掘和頻繁子圖的研究也主要針對于社交網(wǎng)絡(luò)，但發(fā)現(xiàn)學(xué)生頻繁消費行為特征［3］、解決學(xué)生人際關(guān)系問題，以及預(yù)防惡劣事件的發(fā)生，不僅對構(gòu)建和諧校園環(huán)境有著十分重要的作用，也給一卡通建設(shè)提供了可參照的標(biāo)準(zhǔn)。

目前頻繁子圖的研究主要集中在圖集的研究，像社交網(wǎng)絡(luò)或萬維網(wǎng)鏈接圖等，應(yīng)用于校園卡消費數(shù)據(jù)的研究則不多見，而單圖數(shù)據(jù)并不適合被劃分為圖集再操作，主要因為大規(guī)模單圖的頂點數(shù)量經(jīng)常在百萬級別以上，遠超圖集中的單個圖，這樣最后得到的頻繁模式子［4～6］圖規(guī)模也遠比圖集上大。不僅在支持度計算比圖集要復(fù)雜，在子圖同構(gòu)中進行測試時也要消耗更多的時間。頻繁子圖挖掘問題的核心實質(zhì)是頂點的單圖挖掘，針對單圖頻繁子圖的挖掘已有文獻［7～9］，2014 年提出GRAMI 算法［9］模型將難點轉(zhuǎn)為限制約束問題，該算法在單機頻繁子圖挖掘中的效果最好。但是GRAMI算法是單機算法，面對大規(guī)模圖的運行效率較低，也無法在支持度較低的頻繁子圖中挖掘。現(xiàn)分布式環(huán)境［10～13］下的單圖頻繁子圖挖掘算法［14～16］，都針對于有向圖且需要指定子圖頂點個數(shù)k，不能支持子圖增長模式的挖掘，針對圖集的其他分布式頻繁子圖挖掘算法［17］大多是基于MapReduce 框架［18］，Spark框架非常適合迭代計算模型，對比MapReduce無需要多次讀寫磁盤，也不會造成大量的IO 及序列化和反序列化的開銷?；谏鲜鰡栴}，本文提出如下算法：

1）提出基于密度聚類的DP-DBSCAN 數(shù)據(jù)轉(zhuǎn)化算法，將我校一卡通數(shù)據(jù)轉(zhuǎn)化為頻繁子圖的準(zhǔn)備數(shù)據(jù)集。

2）基于次優(yōu)樹按照廣度優(yōu)方法搜索生成候選子圖的方法將大規(guī)模單圖并行化，提出了基于Spark［19～20］的頻繁子圖挖掘架構(gòu)。

3）提出分布式大規(guī)模單圖的頻繁子圖挖掘算法FSMBUS。

2 頻繁子圖的基本定義

定義1 子圖和子圖同構(gòu)：給定一個圖G=(V ，E，L )，其中V 和E 分別表示頂點和邊的集合，L 是關(guān)于頂點和邊的標(biāo)簽映射函數(shù)，現(xiàn)有一個圖S 其中S=(VS，ES，LS)，當(dāng)且僅當(dāng)VS?V，ES?E，LS(υ)=L(υ)，對于每一個v ∈VS∪ES都成立時，則稱S 是G 的一個子圖。 S 與G 的子圖同構(gòu)，即存在一個映射函數(shù)：f:VS→V ，函數(shù)滿足：

1）?υ∈VS，LS(υ)=L(f(υ));

2）?(u，υ)∈ES；(f(u)，f(υ))∈E

并且LS(u，υ)=L(f(u)，f(v))，其中f 是一個單映射函數(shù)，稱S 在G 中的一個嵌入。

定義2 頻繁子圖：給定一個圖G 和一個最小支持度τ ，Sup(G，S)表示子圖S 在G 中屬于同構(gòu)圖的計數(shù)，當(dāng)Sup(G，S)≥τ 時S 為G 的一個頻S=(VS，ES，LS)繁子圖。

定義3 MNI 支持度：f 為子圖在G 中的同構(gòu)映射集合，f 集合的長度為m，同時為f 集合上每一個υ 去重之后的映射函數(shù)，其中υ ∈VS，則其MNI支持度計算方式表示為

定 義 4CSP 模 型 s=(VS，ES，LS) 為G=(V，E，L)的一個子圖，在G 中查找子圖S 的同構(gòu)用CSP( X，D，C )模型來表示：

1）X 所包含的變量xi表示VS中的各個頂點υ；

2）D 是各個xi∈X 數(shù)據(jù)域的集合，每個數(shù)據(jù)域都是V 的一個子集；

3）C 表示有如下約束條件：

（1）xi1≠xi2，表示在同一個同構(gòu)映射中頂點最多被分配一次，即要保證頂點的不重復(fù)性；

（2）L(xi)=LS(υ)，表示所分配的頂點標(biāo)簽一定要與子圖的標(biāo)簽一一對應(yīng)，即頂點一致性；

（3）L(xi1，xi2)=Ls(υ1，υ2)表示被分配的頂點之間邊的標(biāo)簽應(yīng)與子圖邊標(biāo)簽相互對應(yīng)，即為弧一致性；

定理1子圖S 中任意一個有效分配對應(yīng)G 的CSP模型，即S 是G 中的子圖同構(gòu)。

有效分配的意思是指在CSP 模型中滿足條件C 的約束，如圖1（b）在圖1（a）中的一個有效分配為(v1，v2，v3) ={u0，u1，u3} ，因為u0，u1，u3的頂點ID互不相同，頂點標(biāo)簽(IE，DB，IR)與邊標(biāo)簽（12，4）也剛好與圖1（b）一一對應(yīng)。而圖1（a）中這3 個頂點u0，u1，u3組成的的圖正好為圖1（b）的同構(gòu)。

根據(jù)定義4 和定理1 可推出，通過使用CSP 模型在候選子圖拓?fù)浣Y(jié)構(gòu)中，由約束條件尋找真實圖中的同構(gòu)映射。將圖1（b）在圖1（a）中進行的頻繁子圖查找轉(zhuǎn)變成CSP模型為

再根據(jù)約束條件在數(shù)據(jù)域中尋找其對應(yīng)的有效 分 配 為{u0，u1，u3}，{u7，u6，u5}，{u7，u6，u8}，即 同 構(gòu)映射，然后再由MNI支持度的計算值判斷該候選子圖是否為頻繁子圖。

圖1 合作網(wǎng)絡(luò)圖樣例

3 候選子圖的生長

次優(yōu)樹是FFSM 算法［20］提出的一種高效的候選子圖生長策略，鄰接矩陣M 存儲每個圖，其對角線存儲頂點標(biāo)簽，非對角線存儲頂點與頂點相連邊的標(biāo)簽。

定義5標(biāo)準(zhǔn)的鄰接矩陣CAM：給定一個n×n的鄰接矩陣M 表示有n 個頂點的圖G，定義M 的編碼為該矩陣中包括對角線的下三角，并按順序m1，1m2，1m2，2…mm，1，mm，2…mn，n-1mn，n構(gòu) 成 的 序 列，記為code(M) ，按字典序比較得到max(code(M))稱為標(biāo)準(zhǔn)編碼，對應(yīng)的矩陣稱為標(biāo)準(zhǔn)鄰接矩陣。

定義6次優(yōu)樹：如果圖G矩陣M 的極大子矩陣是另一個圖的標(biāo)準(zhǔn)鄰接矩陣時，則稱該矩陣M是次優(yōu)鄰接矩陣，記作次優(yōu)CAM，其中每個CAM同時又是下一個次優(yōu)CAM，由次優(yōu)CAM 構(gòu)成的樹就叫作次優(yōu)樹。

給定2個次優(yōu)鄰接矩陣M 和N ，通過M 與N的連接操作生成新矩陣稱之為FFSM-JOIN［20］，M或N 擴展頻繁邊生成新矩陣稱FFSM-Extension［20］。現(xiàn)以空為根節(jié)點，頻繁邊為第1層葉子，第2層葉子節(jié)點是次優(yōu)鄰接矩陣由頻繁邊通過上述兩大算子生成，同理依次不斷迭代上述過程，就可以生成當(dāng)前層的下一層次優(yōu)樹，這樣就能枚舉出不會重復(fù)的候選子圖。圖1（d）在生長過程中形成的次優(yōu)樹為圖2，圖2 的樹根節(jié)點為空其他節(jié)點代表圖1（d）的一個子圖。其中白色背景的為CAM，灰色背景的為次優(yōu)CAM，通過當(dāng)前的父節(jié)點FFSM-JOIN或FFSM-Extension算子生成下一層節(jié)點。

4 頻繁子圖挖掘算法

FSMBUS 算法是在Spark 框架下，以迭代式RDD 設(shè)計的一種分布式算法。通過使用次優(yōu)樹作為候選子圖的生長策略，將候選子圖邊數(shù)作為第二次迭代的增量。在圖2 的次優(yōu)樹中我們可以發(fā)現(xiàn)：在計算支持度時直接影響孩子節(jié)點的是確定當(dāng)前候選子圖是否頻繁，樹每層邊的數(shù)量與支持的計算互不影響。如圖3 所示是FSMBUS 的流程框架，其中主要包含數(shù)據(jù)預(yù)處理和數(shù)據(jù)挖掘階段。數(shù)據(jù)挖掘是算法的核心部分，按廣度搜索進行次優(yōu)樹的生長，并行計算每一層中CAM 的候選子圖是否頻繁。如果是非頻繁，剪枝其候選子圖然后繼續(xù)生長次優(yōu)樹開始下一次的迭代。第i 次迭代生成邊數(shù)為i+2 的頻繁子圖并且作為第i+1次迭代的輸入，一直到候選子圖全部為非頻繁時迭代結(jié)束。算法主要解決了兩大難點，一個是候選搜索數(shù)據(jù)域的構(gòu)建另一個是支持度的計算。

圖2 次優(yōu)樹

4.1 數(shù)據(jù)預(yù)處理

一卡通流水?dāng)?shù)據(jù)的分布緊密情況和上下課時間直接相關(guān)，為得到學(xué)生一起消費的頻繁子圖，提出基于密度聚類的DP-DBSCAN數(shù)據(jù)轉(zhuǎn)化算法。

給定數(shù)據(jù)集D=D1+D2+…Dn，Dn表示第n天的數(shù)據(jù)集，所有對象標(biāo)記為“unvisited”，從D1開始選擇第一條消費軌跡點v0=x0( y0，t0)，標(biāo)記為“visited”，并按消費順序檢查v0的ε 鄰域中是否為空，如果不是，創(chuàng)建一棵以x0為根結(jié)點的B+樹，并對ε 鄰域中包含的所有對象xi( i =0…n )按樹的結(jié)構(gòu)存儲到集合N ，否則選擇下一個未訪問對象。N 中標(biāo)記為“unvisited”的對象改為“visited”，并檢查該ε 鄰域，如果是非空，則ε 鄰域中的所有對象都被插入到當(dāng)前葉結(jié)點的下一層，依次檢查當(dāng)前葉結(jié)點，迭代N 中所有未訪問對象，直到N 不再變化時提取B+樹的每個分支，生成FP 樹的時空軌跡序列。對剩下未訪問的對象，生成過程繼續(xù)，直到所有對象被訪問結(jié)束循環(huán)下一個數(shù)據(jù)集。算法偽代碼如下所示。

算法：數(shù)據(jù)轉(zhuǎn)換算法DP-DBSCAN輸入：

·D：一個包含n個對象的數(shù)據(jù)集

·Di：按天劃分的小數(shù)據(jù)集

·ε：度量方法—歐氏距離

輸出：軌跡樹表集

方法：

① 標(biāo)記所有對象為unvisited；

② do

③ for D 中每個Di

④ 按順序選擇一個unvisited對象vi=xi(yi，ti) ；

⑤ 標(biāo)記vi為visited

⑥ if vi的ε 鄰域內(nèi)非空

⑦ 以xi為根結(jié)點創(chuàng)建一顆B+樹；

⑧ 令N 為vi的ε 鄰域中的對象集合；

⑨ for N 中每個葉結(jié)點vi

⑩if vi為unvisited

? 標(biāo)記vi為visited；

? if vi的ε 鄰域非空，鄰域內(nèi)所有對象對應(yīng)的xi插入到當(dāng)前葉結(jié)點的下一層；

? end for

? 提取B+樹的每條分支，生成FP 樹的時空軌跡序列：

? else按順序訪問下一個未訪問對象

? end for

? 輸出Di的所有時空軌跡序列集；

? until 沒有標(biāo)記為unvisited的對象；

DBSCAN 的核心是利用滿足設(shè)定條件時不斷迭代的原理發(fā)現(xiàn)任意簇，而DP-DBSCAN 則是借其思想設(shè)計出在相鄰時間地點一起消費的軌跡序列。當(dāng)滿足在ε 值范圍內(nèi)（即相鄰的消費時間和地點），則生成一次一起消費的記錄。該算法按天分塊、流水順序查詢，依據(jù)歐氏距離劃分，B+樹存儲，通過提取每條分支得到在相鄰時間、地點一起消費的n條學(xué)生id軌跡序列：

S 表示一條時空屬性關(guān)系標(biāo)簽的軌跡序列，Xn表示經(jīng)過累計卡次降序排序后帶有關(guān)系標(biāo)簽的id-學(xué)生證號，dn是按順序從1…n 依次添加的關(guān)系標(biāo)簽值，用來描述具體消費關(guān)系的親密指數(shù)，當(dāng)dn＜4時稱兩節(jié)點間屬閨蜜關(guān)系，4 ≤dn＜8 為飯友，8 ≤dn≤12 為同學(xué)，其他情況不做標(biāo)記表示陌生。

按起始標(biāo)簽為srcLabel，邊標(biāo)簽為attr，目標(biāo)標(biāo)簽為dstLabel 的三元組格式進行存儲，由MNI 支持度策略過濾掉非頻繁邊，次優(yōu)樹中的第一層頻繁子圖是頻繁邊，頻繁邊兩端對應(yīng)的頂點映射存儲在頻繁邊RDD，而這些頂點映射就是CSP模型中的有效分配。圖3 是挖掘階段，因此需要先初始化一個當(dāng)前頻繁子圖RDD 作為挖掘階段的初始輸入，然后每次迭代當(dāng)前父級頻繁子圖的RDD。在準(zhǔn)備階段中，頻繁邊RDD 轉(zhuǎn)換成當(dāng)前的頻繁子圖數(shù)據(jù)集，即頻繁邊，Di存儲對應(yīng)變量中有效分配頂點，同時Di的各個頂點也會存儲候選子圖上相鄰頂點的索引位置及其ID。

圖3 FSMBUS算法的流程框架圖

Domain 的結(jié)構(gòu)如圖4（a）所示，表示一個候選子圖的結(jié)構(gòu)，每個候選子圖中含有k 個頂點，Vx表示D1中的有效分配頂點，{k-2 →{υy}}表示D1的υx與Dk-2的υy相連，在Dk-2上會對稱的存在與D1相連的信息，所以該算法可以應(yīng)用在無向圖的挖掘中。將Domain 的結(jié)構(gòu)對應(yīng)圖4（b），可以得到u1和u3，u6和u5，u6和u8分別都有邊相連，與傳統(tǒng)的存儲結(jié)構(gòu)相比，該結(jié)構(gòu)可以直接計算候選子圖的支持度。

圖4 Domain存儲結(jié)構(gòu)

4.2 數(shù)據(jù)挖掘階段

數(shù)據(jù)挖掘階段是通過迭代的方式實現(xiàn)候選子圖的生成、候選搜索數(shù)據(jù)域的構(gòu)建以及支持度的計算，即該過程是計算出所有頻繁子圖。

定義7 外/內(nèi)邊：在子圖生長的過程中，如果擴展邊需要引入新頂點，則稱該擴展邊E 為外邊，否則為內(nèi)邊。

步驟1 候選子圖的生成：第i 次迭代由第i-1次迭代產(chǎn)生的頻繁子圖進行FFSM-Join 和FFSM-Extend 后產(chǎn)生候選子圖，而FFSM-Join 和FFSM-Extend 算子生成的新候選子圖，其實質(zhì)都是在父級子圖上添加一條邊，因此都稱之為擴展邊。對于產(chǎn)生的新候選子圖的數(shù)據(jù)結(jié)構(gòu)，除了自身的拓?fù)浣Y(jié)構(gòu)外還包含其父級子圖的ID 號和對應(yīng)該子圖的擴展邊，而候選搜索數(shù)據(jù)域就基于以上2 個數(shù)據(jù)構(gòu)建。

步驟2 構(gòu)建候選搜索數(shù)據(jù)域：在計算支持度之前應(yīng)先取得當(dāng)前候選子圖所對應(yīng)的頂點數(shù)據(jù)，稱為候選搜索數(shù)據(jù)域，使用Domain 結(jié)構(gòu)存儲。FSMBUS 是通過使用增量的方式得到對應(yīng)的CD，每一個候選子圖都包含父級子圖IDK 信息和它的擴展邊信息，連接擴展邊對應(yīng)的父級子圖的有效分配數(shù)據(jù)，即當(dāng)前后選子圖的CD。

步驟3 支持度計算：頻繁子圖挖掘的核心是支持度的計算，該過程需要進行子圖NP 完全問題的同構(gòu)測試，F(xiàn)SMBUS 通過啟發(fā)式方法對候選搜索數(shù)據(jù)域進行支持度的搜索計算，其偽代碼如下：

算法1 支持度計算IsFrequent(D，τ)

輸入：D 表示當(dāng)前候選子圖的數(shù)據(jù)域，τ 表示最小支持度；

輸出：當(dāng)候選子圖的支持度大于τ 時返回true，否則false.

①val solDomain，nonCandidateMap；/分別存儲有效和無效的分配項/

②val search IndexOrder=getOrder（D）；/獲取搜索順序/

③for each i in seachIndexOrder

④ if CheckFrequnet（solDomain）return true；

⑤ for each υ in D（i）；/使用回朔的方法進行有效分配搜索/

⑥ If υ 包含在solDomain（i）中

⑦Go to next υ；

⑧Instance=SearchBackTraking（υ）；/回溯法的有效分配搜索/

⑨ If instance=empty

⑩nonCandidateMap（i），add（υ）；

? If D（i），size-nonCandidateMap（i），

? Size ＜τ return false；

? else

? solDomain（i），add（instance）

? If solDomain（i），size ≥τ go to next i；

? If solDomain（i），size ≤τ return false

? If checkFrequen（tsolDomain）return true；

?return true.

在計算支持度時依次遍歷變量X 的數(shù)據(jù)域，通過構(gòu)建深度優(yōu)先的搜索路徑，進行有效分配的搜索，直至MNI支持度大于τ 或者當(dāng)前變量的有效分配，與剩余候選項個數(shù)之和小于τ 時停止。在算法1 中，行③～⑤是遍歷數(shù)據(jù)域，行⑦是有效分配的搜索，行⑧～?是剪枝過程中頻繁條件的判斷。最后的計算結(jié)果如果是頻繁子圖，將會根據(jù)non-CandidateMap 搜索整個數(shù)據(jù)域進行剪枝，其目的是為了減少候選子圖的搜索空間及RDD的存儲空間。

FSMBUS算法偽代碼：

算法2 FSMBUS（v_path，e_path）

輸入：v_path 表示輸入圖頂點，e_path 表示邊的文件存儲路徑，τ 表示最小支持度；

輸出：S 為返回的頻繁子圖的集合。

①val G=Graph（v_path，e_path）；

②val FE=G，groupby.filter.map.filter.filter.collect；/檢測頻繁邊/

③val FERDD=（G，F(xiàn)E），fliter.flatMap.groupby.collect；/獲取頻繁邊的信息/

④val CFGRDD=FERDD.map.cache；/初始化頻繁邊/

⑤val matrixMap=Cam_Init（ConnectSplit（FE））； /將頻繁邊分割并轉(zhuǎn)為矩陣/

⑥while matrixMap.size＞0

⑦S，union（matrixMap.matrix）；/添加頻繁子圖/

⑧matrixMap=Cam_Gener（matrixMap）；

/使用CamCode進行連接和擴展/

⑨val candidateSubGQueue=matrixMap

.enqueue；/形成候選子圖隊列/

⑩val PFSGRDD=CFSGRDD；

? while candidateSubGQueue.size＞0

? val batchFreqSubGRDD=sc，Parallelize（candidateSubGQueue.dequeue（batch-Size））

? .join（FERDD）.map.join（PFSGRDD）.map｛

? D=Domain_Construct（）； /候選子圖候選數(shù)據(jù)域構(gòu)建/

? InFrequent_detect（）；/非頻繁檢測/

? IsFrequent（D，τ）；｝/支持度計算（算法1）/

? if batchFreqSubGRDD.count＞0

? matrixMap.add（batchFreqSub-GRDD，matrix）；

? CFSGRDD.union（batchFreqSub-GRDD）；

? return S

行①～⑤是數(shù)據(jù)準(zhǔn)備階段，行⑥～?是最核心的數(shù)據(jù)挖掘部分，行?是非頻繁檢測優(yōu)化，行②是在算法1 中的搜索順序選擇。行⑨～?可以看出FSMBUS 是先將候選子圖壓入隊列，然后再批量取出計算，主要因為存儲候選子圖的Domain 數(shù)據(jù)需要消耗很大空間，很容易造成集群內(nèi)存溢出，所以不會一次性將所有候選子圖同時并行計算，而是采用隊列的形式批處理。通過控制參數(shù)BatchSize 可以有效地解決內(nèi)存溢出問題，這說明FSMBUS具有良好的魯棒性。

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

實驗用的是普通PC 機，F(xiàn)SMBUS 使用Scala2.10.4 進行開發(fā)，集群環(huán)境為Spark1.2.0，運行的模式為Spark On Yarn，其中Yarn 對應(yīng)的Hadoop 版本為2.2.0，所有節(jié)點均使用普通PC機，運行時的通用參數(shù)driver-memory 為6GB，executor-memory 為6GB。

YikaTong：我校最近幾年的一卡通數(shù)據(jù)經(jīng)DP-DBSCAN 算法轉(zhuǎn)換后的學(xué)生一起消費軌跡集。頂點的標(biāo)簽為我校一卡通學(xué)生id，邊表示2 個學(xué)生之間存在一起消費關(guān)系，邊的標(biāo)簽為2 個學(xué)生之間消費親密程度是閨蜜、飯友，還是同學(xué)。為了對比海量數(shù)據(jù)處理在分布式平臺上的顯著性，以及頻繁子圖挖掘算法FSMBUS 的優(yōu)越性，增加兩個數(shù)據(jù)集Twitter 和PldWeb 進行更全面的實驗對比分析。實驗數(shù)據(jù)集描述如表1所示。

表1 實驗數(shù)據(jù)集描述

為了評估FSMBUS 的性能，實驗部分選擇與下列算法進行對比：

1）GRAMI：文獻［7］提出的算法，它為單機環(huán)境下的算法。

2）FSMBUS-H：本文提出的FSMBUS 算法在Hadoop2.2.0環(huán)境下實現(xiàn)，F(xiàn)SMBUS-H算法使用迭代式的MapReduce進行挖掘，利用HDFS進行數(shù)據(jù)共享。

3）NAVFSM：因為目前還沒有在分布式下的單圖處理方法，所以本文通過用暴力的枚舉方式，提出基于Spark平臺的樸素單圖上的分布式頻繁子圖算法。

FSMBUS 算法與GRAMI、FSMBUS-H、NAVFSM 算法的對比實驗結(jié)果如圖5～7所示。在相同最小支持度下FSMBUS算法的運行時間最少，最快是GRAMI 算 法 的20 倍；FSMBUS 算 法 的 性 能 最 高，F(xiàn)SMBUS-H 性能次之，主要是因為在運行時需要多次從HDFS 讀寫數(shù)據(jù)，但是在PldWeb 數(shù)據(jù)集上支持度在110000 時FSMBUS-H 性能超過了FSMBUS，這是由于Spark 內(nèi)存不足時要進行磁盤的溢寫和垃圾回收；在超大規(guī)模的PldWeb 數(shù)據(jù)集上會出現(xiàn)OOM 異常，基本無法正常運行。

圖5 YiKaTong數(shù)據(jù)集

圖6 Twitter數(shù)據(jù)集

圖7 PldWeb數(shù)據(jù)集

根據(jù)上述實驗結(jié)果分析可以得出以下結(jié)論：

1）FSMBUS 算法與GRAMI 相比，可以支承更低的支持度和更大的數(shù)據(jù)集，在相同的數(shù)據(jù)集下運算速度是GRAMI 3～20倍，主要因為FSMBUS是運行在Spark 的分布式算法，可以并行運算最耗時的支持度，每次迭代結(jié)果存儲在內(nèi)存中，只有當(dāng)內(nèi)存不足時才將數(shù)據(jù)溢寫到本地磁盤。同時FSMBUS在計算支持度前會先優(yōu)化候選子圖的非頻繁檢測來減少非頻繁子圖的搜索；通過本文提出的數(shù)據(jù)結(jié)構(gòu)，在搜索時減少了CSP 約束的判斷次數(shù)，支持更低支持度閾值的計算。

2）對比Hadoop 環(huán)境，Spark 基于內(nèi)存運算，在內(nèi)存足夠的情況下除了輸入輸出外不會頻繁讀寫HDFS 而產(chǎn)生額外的開銷，通過DAG 的作業(yè)執(zhí)行和RDD間的相互依賴，可高效地處理FSMBUS的迭代式算法任務(wù)。

3）根據(jù)本文提出的FSMBUS 算法，選定關(guān)系度范圍值是同學(xué)、飯友、閨蜜的三種類別，如圖8 是該算法部分放大后的結(jié)果圖。通過改變支持度分析圖形的邊緣點進而發(fā)現(xiàn)孤立消費人群，圖節(jié)點邊數(shù)較多的同學(xué)可作為評選班級干部時考慮其交際能力的一個依據(jù)，同時也可以通過輸入關(guān)系度范圍幫助用戶發(fā)現(xiàn)未來可能會認(rèn)識的消費人群。

圖8 學(xué)生頻繁消費關(guān)系子圖

6 結(jié)語

本文提出了一種基于Spark的分布式并行單圖上的頻繁子圖挖掘算法FSMBUS，候選子圖的生長是根據(jù)次優(yōu)樹按廣度優(yōu)先的方式增長，并行計算候選子圖的支持度，通過迭代的RDD 挖掘大規(guī)模單圖頻繁子圖。實驗表明FSMBUS 算法不僅能支持更低的支持度和更大規(guī)模的數(shù)據(jù)集，還比在Hadoop平臺上的運行效率高2～4 倍。將該算法應(yīng)用與我校一卡通消費數(shù)據(jù)，分析學(xué)生頻繁消費關(guān)系軌跡圖，通過調(diào)整支持度進一步研究孤立消費人群。同時該算法也可以擴展應(yīng)用在社交網(wǎng)絡(luò)上的頻繁子圖挖掘，跟據(jù)挖掘結(jié)果幫助企業(yè)決策提出可靠的依據(jù)。