王永貴，徐山珊，肖成龍

遼寧工程技術(shù)大學(xué) 軟件學(xué)院，遼寧 葫蘆島 125105

1 引言

社交網(wǎng)絡(luò)的發(fā)展改變著人們的生活方式，興趣的共同點會導(dǎo)致社交網(wǎng)絡(luò)中的個體逐漸發(fā)展形成一系列的社團(tuán)[1]。推薦好友[2]通常轉(zhuǎn)化為社團(tuán)發(fā)現(xiàn)，用戶的行為習(xí)慣或興趣愛好越相似，越可能是同一個社團(tuán)中的成員[3]。無線城市社團(tuán)發(fā)現(xiàn)是通過智能移動終端連接無線網(wǎng)絡(luò)的方式，對用戶的地理位置進(jìn)行捕捉[4]，在MAC 地址接入記錄中挖掘隱藏的關(guān)鍵信息。社團(tuán)發(fā)現(xiàn)在諸多方面具備廣闊的發(fā)展前景和重要的應(yīng)用價值[5]，但在大數(shù)據(jù)時代[6]中準(zhǔn)確快速地解決社團(tuán)發(fā)現(xiàn)問題仍面臨著巨大的挑戰(zhàn)。

文獻(xiàn)[7-12]針對傳統(tǒng)社團(tuán)發(fā)現(xiàn)算法的缺點，提出了改進(jìn)方法，卻沒有考慮地理位置信息[13]。文獻(xiàn)[14-16]分析了將社區(qū)發(fā)現(xiàn)與關(guān)聯(lián)規(guī)則相結(jié)合的可行性，并提出了混合算法。文獻(xiàn)[17-19]針對傳統(tǒng)關(guān)聯(lián)規(guī)則算法挖掘效率低的缺點，提出了改進(jìn)算法。然而，上述大部分算法均是單機(jī)執(zhí)行，已無法處理大規(guī)模復(fù)雜數(shù)據(jù)集。

針對上述問題，本文深入研究了社團(tuán)發(fā)現(xiàn)問題，并提出了基于Spark 利用改進(jìn)關(guān)聯(lián)規(guī)則解決無線城市社團(tuán)發(fā)現(xiàn)問題的SIACD（Spark-based use of improved Apriori to achieve community detection）算法。實驗結(jié)果表明，SIACD 算法解決了Apriori 算法需大量迭代計算的問題，改善了團(tuán)搜索（clique search，CS）算法生成結(jié)果冗余的不足，充分發(fā)揮Spark并行計算的優(yōu)勢，避免了MP-T-CS（MapReduce tree clique search）算法多次磁盤I/O操作的缺點，有效提升了計算效率。

文章組織結(jié)構(gòu)如下：第1 章介紹研究背景與意義；第2章介紹基礎(chǔ)知識和Spark大數(shù)據(jù)平臺；第3章介紹相關(guān)算法并分析其不足；第4 章介紹新SIACD算法；第5 章為實驗驗證及結(jié)果分析；第6 章總結(jié)全文。

2 相關(guān)知識

2.1 社團(tuán)發(fā)現(xiàn)

社團(tuán)發(fā)現(xiàn)是指發(fā)現(xiàn)網(wǎng)絡(luò)中社團(tuán)個體行為之間的關(guān)聯(lián)關(guān)系。用戶之間的互動越頻繁就越可能蘊(yùn)含著潛在的興趣關(guān)聯(lián)或者較強(qiáng)的社交關(guān)系。

2.2 MAC地址

定義1[4]（MAC 地址）介質(zhì)訪問控制地址，又稱為物理地址，用來定義網(wǎng)絡(luò)硬件設(shè)備的位置。

定義2[4]（MAC地址原始數(shù)據(jù)）用戶使用設(shè)備的MAC地址、無線網(wǎng)絡(luò)的MAC地址、接入時間、接入地點以及其他相關(guān)信息組成的集合。

定義3[4]（MAC 地址事務(wù)數(shù)據(jù)）將MAC 地址原始數(shù)據(jù)中同時同地的數(shù)據(jù)壓縮后得到的集合。

例如，在同一地點3位用戶進(jìn)行無線網(wǎng)絡(luò)認(rèn)證行為，100 s以內(nèi)有效，如表1所示[20]。

Table 1 MAC transaction data表1 MAC事務(wù)數(shù)據(jù)

2.3 關(guān)聯(lián)規(guī)則

關(guān)聯(lián)規(guī)則是分析數(shù)據(jù)源并從中發(fā)現(xiàn)事物之間可能存在的關(guān)聯(lián)或者聯(lián)系。Apriori算法是經(jīng)典的關(guān)聯(lián)規(guī)則算法，已廣泛應(yīng)用到各個領(lǐng)域。

定義4[21]（關(guān)聯(lián)規(guī)則）某事務(wù)包含項集X，很可能包含項集Y(X?Y=?)，關(guān)聯(lián)規(guī)則：X→Y。

定義5[21]（支持度計數(shù)）事務(wù)包含項集X的個數(shù)，表達(dá)式：σ(X)=|{ti|X?ti,ti?T}|。

定義6[21]（支持度）事務(wù)同時包含X和Y的百分比，表達(dá)式：s(X→Y)=σ(X?Y)/N。

定義7[21]（置信度）事務(wù)已包含X時，包含Y的百分比，表達(dá)式：c(X→Y)=σ(X?Y)/σ(X)。

定義8[21]（頻繁項集）支持度大于等于支持度閾值的項集。

性質(zhì)1[17]若一個項集是頻繁項集，則它的所有子集也都是頻繁項集。反之也成立。

2.4 Spark平臺

早期研究者較關(guān)注基于Hadoop的算法并行化計算，但Hadoop網(wǎng)絡(luò)和磁盤讀寫開銷很大，難以高效地實現(xiàn)大量的迭代計算[22-26]。Spark 是專為處理大數(shù)據(jù)而設(shè)計的快速且通用的計算引擎[27]。Spark不僅能基于內(nèi)存計算，還能在Hadoop 中并行計算，因此Spark能更好地適用于需大量迭代計算的算法，在實際的數(shù)據(jù)分析過程中具有重要的意義[28]。

3 相關(guān)算法研究

3.1 基于CS算法的社團(tuán)發(fā)現(xiàn)

3.1.1 經(jīng)典CS算法

團(tuán)搜索（CS）算法主要思想是將數(shù)據(jù)映射到無向有權(quán)圖中，節(jié)點代表用戶，邊代表不同用戶在某地同時出現(xiàn)的關(guān)系，邊上的權(quán)重代表同時出現(xiàn)的次數(shù)。通過挖掘由較大權(quán)重的邊組成的團(tuán)，從而發(fā)現(xiàn)潛在的社團(tuán)關(guān)系。但CS算法存在生成結(jié)果冗余、復(fù)雜度高、海量數(shù)據(jù)溢出等問題。

3.1.2 改進(jìn)MP-T-CS算法

MAC地址數(shù)據(jù)預(yù)處理主要偽代碼如下所示：

針對CS 算法的缺點，提出了解決無線城市數(shù)據(jù)中社團(tuán)發(fā)現(xiàn)問題的MP-T-CS算法。該算法利用特殊二叉樹結(jié)構(gòu)存儲數(shù)據(jù)，將CS 算法的主要思想結(jié)合MapReduce模型[4]，在Hadoop集群上實現(xiàn)了算法并行化計算，但該算法進(jìn)行了多次Map和Reduce操作，只有重新從磁盤中加載數(shù)據(jù)后才能再次處理數(shù)據(jù)，因此造成了不必要的時間消耗。

3.2 基于Apriori算法的社團(tuán)發(fā)現(xiàn)

3.2.1 核心思想

事務(wù)代表社團(tuán)活動，而事務(wù)的項集代表用戶組成的社團(tuán)數(shù)據(jù)集合，若不同的用戶同時在某些事務(wù)中頻繁出現(xiàn)，那么他們很可能屬于同一個社團(tuán)。利用Apriori算法尋找頻繁項集的過程就是挖掘不同用戶是某社團(tuán)成員的過程，即為社團(tuán)發(fā)現(xiàn)。

3.2.2 算法步驟

首先從數(shù)據(jù)集中生成候選1-項集C1，當(dāng)C1大于等于支持度閾值時生成頻繁1-項集L1。然后由L1兩兩結(jié)合生成C2，對C2進(jìn)行剪枝并生成L2，不斷迭代，直至最終獲取Lk。算法流程圖如圖1所示。

Fig.1 Community discovery flow chart based on Apriori algorithm圖1 基于Apriori算法的社團(tuán)發(fā)現(xiàn)流程圖

3.2.3 算法分析

Apriori算法需不斷遍歷數(shù)據(jù)集來計算候選項集的支持度計數(shù)，其計算復(fù)雜度主要受到項數(shù)和事務(wù)數(shù)的影響。設(shè)事務(wù)數(shù)為m，項數(shù)為n，該算法的時間復(fù)雜度為O(mn2)，空間復(fù)雜度為O(n2)。不難看出，Apriori 算法的復(fù)雜度較高，會造成極大的時間消耗與空間消耗，尤其是輸入大規(guī)模數(shù)據(jù)時，傳統(tǒng)Apriori算法挖掘效率很低，因此不適用于現(xiàn)階段大規(guī)模復(fù)雜網(wǎng)絡(luò)數(shù)據(jù)中的社團(tuán)發(fā)現(xiàn)。

4 新SIACD算法

4.1 核心思想

SIACD算法的核心思想：首先，針對大多數(shù)社團(tuán)發(fā)現(xiàn)算法不考慮社團(tuán)成員所在地理位置信息的問題，引入了無線城市中MAC 地址事務(wù)數(shù)據(jù)，利用布爾矩陣將數(shù)據(jù)進(jìn)行壓縮，這樣可以有效減少數(shù)據(jù)的存儲空間[29]；其次，利用基于項數(shù)布爾矩陣中0-1向量的交運(yùn)算來改進(jìn)傳統(tǒng)Apriori算法循環(huán)掃描數(shù)據(jù)的缺點，并保留關(guān)聯(lián)規(guī)則的先驗性質(zhì)，將不符合條件的項集刪除，再次壓縮數(shù)據(jù)，從而減少計算次數(shù)；最后，在Spark 集群上實現(xiàn)算法的并行化計算，利用Spark 基于內(nèi)存計算的優(yōu)勢，提高算法的計算效率。

從目前來看，與其他的英語教學(xué)階段相比，高職英語教育在實踐教學(xué)的過程之中存在許多的不足，其中職校學(xué)生的綜合英語基礎(chǔ)相對較為薄弱，老師所采取的教學(xué)理念以及教學(xué)模式比較傳統(tǒng)以及單一，實際的教學(xué)內(nèi)容與慕課的教學(xué)要求之間還存在許多差距，這一點嚴(yán)重影響了教學(xué)質(zhì)量以及教學(xué)水平的提升。

湖州市南潯區(qū)人民政府副區(qū)長沈雪芬在大會致辭中肯定了南潯木地板產(chǎn)業(yè)的發(fā)展，并表揚(yáng)了包括世友地板、久盛地板、森林之星地板等優(yōu)秀地板品牌。她相信，中國地板產(chǎn)業(yè)必將形成新的格局，并擁有更廣闊的發(fā)展前景。

4.2 MAC地址數(shù)據(jù)預(yù)處理

針對大多數(shù)傳統(tǒng)社團(tuán)發(fā)現(xiàn)算法沒有考慮地址位置信息的缺點，SIACD 算法引入MAC 地址的概念。事務(wù)Tn[21]代表同時出現(xiàn)在某地的用戶們所擁有的MAC 地址的集合，且事務(wù)Tn中包含唯一的標(biāo)識號TID。若一組MAC 地址在不同的事務(wù)中頻繁出現(xiàn)，則表示這些用戶來自于同一個社團(tuán)[13]。而利用Apriori 算法尋找MAC 地址事務(wù)數(shù)據(jù)中頻繁項集的過程，即為社團(tuán)發(fā)現(xiàn)。

4.2.1 相關(guān)定義

定義9[19]（布爾矩陣）又稱0-1矩陣。

定義10[17]（項數(shù)）事務(wù)Tn包含項的個數(shù)叫作事務(wù)的項數(shù)，用TIn表示。

定義11[17]（項數(shù)布爾矩陣）在布爾矩陣的前面加上一列記錄事務(wù)的項數(shù)，即項數(shù)布爾矩陣。

性質(zhì)2[17]在數(shù)據(jù)集中若存在一個事務(wù)Tn，且該事務(wù)的項數(shù)小于k，當(dāng)生成頻繁k-項集時，沒有必要掃描該事務(wù)。

證明生成Lk時需計算Ck的事務(wù)數(shù)，若Tn的項數(shù)小于k，由定義10可知Tn不可能包含Ck，則不需要掃描Tn。因此如果直接挖掘Lk，則可以刪掉項數(shù)小于k的Tn，不用映射到布爾矩陣中[17]。 □

4.2.2 處理方法

將MAC 地址原始數(shù)據(jù)中同一時間和場所的數(shù)據(jù)進(jìn)行壓縮，刪除非關(guān)鍵數(shù)據(jù)，只保留用戶設(shè)備的MAC 地址和無線網(wǎng)絡(luò)的MAC 地址以及接入時間等數(shù)據(jù)，生成MAC 地址事務(wù)數(shù)據(jù)集。利用0-1 儲存特性將其轉(zhuǎn)化成布爾矩陣，這樣可以有效壓縮數(shù)據(jù)存儲空間，節(jié)約數(shù)據(jù)讀取掃描的時間。

手機(jī)用戶在進(jìn)行手機(jī)攝影過程中，需要具有一定的道德觀念和法律意識，但有一部分手機(jī)用戶往往會為了迎合受眾獵奇心理，利用一些較高的隱蔽性功能進(jìn)行拍攝，并將一些隱私圖像上傳至網(wǎng)絡(luò)，嚴(yán)重侵害公民隱私權(quán)。

MAC地址數(shù)據(jù)預(yù)處理主要思想如圖2所示。

Fig.2 Data preprocessing main idea diagram圖2 數(shù)據(jù)預(yù)處理主要思想圖解

從HDFS（Hadoop distributed file system）中讀取MAC地址事務(wù)數(shù)據(jù)，以事務(wù)TID為行和項集items為列構(gòu)造事務(wù)矩陣M。若事務(wù)Tn中存在項集I，則其對應(yīng)的矩陣位置上賦值為“1”，若不存在則賦值為“0”。以此類推，從而將MAC 地址事務(wù)數(shù)據(jù)轉(zhuǎn)化為布爾矩陣MT。為了方便計算，在矩陣前面加上一列項數(shù)TIn，得到基于項數(shù)的全局布爾矩陣MTI。

4.2.3 處理流程

6.{Tn=Ti∩Ti-1}//生成新事務(wù)

一詞多譯,在本文指一個術(shù)語有多個譯文版本的現(xiàn)象,既包含語義無實質(zhì)偏差的譯文,也包含存在語義偏差的譯文。

4.3 基于改進(jìn)Apriori算法的社團(tuán)發(fā)現(xiàn)

傳統(tǒng)Apriori算法計算效率低的本質(zhì)原因是頻繁的迭代過程已無法滿足大數(shù)據(jù)時代對社團(tuán)發(fā)現(xiàn)問題的處理能力要求，對此本文結(jié)合Spark集群對Apriori算法進(jìn)行如下改進(jìn)。

Fig.3 Data preprocessing flow chart圖3 數(shù)據(jù)預(yù)處理流程圖

4.3.1 基于Apriori的改進(jìn)

針對Apriori算法存在重復(fù)掃描數(shù)據(jù)集及生成結(jié)果冗余等問題，SIACD 算法引入基于項數(shù)的布爾向量[30]交運(yùn)算的概念，能避免無效運(yùn)算，進(jìn)而提升算法效率。

定義12[17]（布爾向量交運(yùn)算）布爾向量X=(x1,x2,…,xn)和Y=(y1,y2,…,yn)的交運(yùn)算定義為X?Y=(x1·y1,x2·y2,…,xn·yn)。布爾向量交運(yùn)算相當(dāng)于邏輯與運(yùn)算，0 ?0=0,0 ?1=0,1 ?0=0,1 ?1=1。

Output:Lk.

“支架”是教師和學(xué)習(xí)者共同活動的過程，教師和學(xué)習(xí)者都為主體。只有教師和學(xué)習(xí)者都積極參與互動，才能促進(jìn)學(xué)習(xí)者從在教師的指導(dǎo)下完成任務(wù)轉(zhuǎn)變?yōu)楠毩⑼瓿扇蝿?wù)，提高自己的自主學(xué)習(xí)能力。教師“支架”是否能起到預(yù)期的作用受到教師和學(xué)習(xí)者相關(guān)因素的影響。

全局Moran's I取值范圍為[-1,1]，I＞0表明各樣本點互為正相關(guān)，且值越大，正相關(guān)程度越大；I＜0表明各樣本點互為負(fù)相關(guān)；I=0表明沒有相關(guān)性。

2.if(TIi

3.{deleteTi}//刪除項數(shù)小于k的事務(wù)

4.else

5.for(i=last,i>1,i--)//從最后一行向上做交運(yùn)算

MAC地址數(shù)據(jù)預(yù)處理流程圖如圖3所示。

（2）加強(qiáng)施工工藝改造技術(shù)的研究。噴混植生是工程與生物措施緊密結(jié)合的施工技術(shù)，工藝過程復(fù)雜并影響著工程質(zhì)量。主要研究不同母巖、不同坡度巖石坡面的最佳施工工藝，錨桿與掛網(wǎng)工藝的改進(jìn)、建植層噴混工藝的優(yōu)化等，達(dá)到既降低生產(chǎn)成本，又能快速生態(tài)治理、長期護(hù)坡的目的。

7.Ck=T1?T2?…?Tn//生成局部候選項集Ck

8.if(Sup(Ck)

9.{deleteCk}//局部候選項集的支持度小于局部支持度閾值或不滿足先驗性質(zhì)，則刪除

10.else

14.else

11.C=C1?C2?…?Cn//合并所有局部候選項集

12.if(Sup(C)

這么壯觀的場面，該發(fā)個朋友圈了！近日，湖南高速警察民警巡邏中發(fā)現(xiàn)一小車撞護(hù)欄，所幸無人受傷，后對駕駛員進(jìn)行酒精測試，結(jié)果顯示醉駕，此時他竟提出要拍個照發(fā)“朋友圈”。

13.{deleteC}//刪除小于支持度閾值的候選項集

MATLAB仿真過程中每組發(fā)送的原始數(shù)據(jù)幀的個數(shù)K設(shè)為100，共發(fā)送25組數(shù)據(jù)幀.在40MHz帶寬下對單流和雙流分別取MCS4和MCS11的情況進(jìn)行評估和分析.

15.L=allC//生成全局頻繁項集L

4.3.2 提取社團(tuán)

由于MAC 地址具有唯一性，因此用戶MAC 地址等價于項I，即MACn=In。項In代表擁有MACn的社團(tuán)成員，事務(wù)Tn代表社團(tuán)活動，而事務(wù)的頻繁項集代表成員組成的社團(tuán)集合。若MAC 地址頻繁地同時出現(xiàn)在某些事務(wù)中，那么其對應(yīng)的用戶即為同一個社團(tuán)成員。利用改進(jìn)Apriori 算法尋找MAC 地址事務(wù)中頻繁項集的過程即為社團(tuán)發(fā)現(xiàn)，而頻繁項集中包含的MAC地址擁有者即為該社團(tuán)成員。

例如，通過4.3.1 小節(jié)生成全局頻繁項集L={I1,I2,I3}，將L中I轉(zhuǎn)換成對應(yīng)的MAC地址，即L={MAC1,MAC2,MAC3}。由MAC地址的唯一性可知，其對應(yīng)的用戶就是該社團(tuán)成員，即用戶1、用戶2、用戶3 這三位為該社團(tuán)成員。

4.4 基于Spark的并行化處理

4.4.1 處理過程

首先，Spark 通過flatmap()讀取數(shù)據(jù)并轉(zhuǎn)換成由事務(wù)標(biāo)識及對應(yīng)項組成的鍵值對。其中TID 對應(yīng)key，而item 對應(yīng)value。Reducebykey()將事務(wù)Tn所包含的項整合并計算其個數(shù)，獲取每個事務(wù)的項數(shù)TIn，添加到事務(wù)布爾矩陣首列前面。利用filter()刪除項數(shù)小于支持度閾值的事務(wù)，這樣可以有效減少無效數(shù)據(jù)，節(jié)省掃描數(shù)據(jù)的時間。其次，將剩余事務(wù)中的項整合成項集items 作為value，生成鍵值對。TID 兩兩相交并計算事務(wù)的項數(shù)，即items 中的布爾向量逐一兩兩做交運(yùn)算并將相交結(jié)果存儲于中。若事務(wù)的項數(shù)大于等于支持度閾值，則生成局部頻繁項集。Reducebykey()合并全部的局部頻繁項集，生成全局候選項集，利用filter()將不滿足Apriori原則及支持度小于全局支持度閾值的刪除，生成全局頻繁項集。最后，將全局頻繁項集子集中的項依次轉(zhuǎn)換成MAC地址，獲得其對應(yīng)的社團(tuán)成員集合。

電力變電站運(yùn)行的過程中，一定要重視設(shè)備的質(zhì)量檢查，因為設(shè)備的安全性取決于其質(zhì)量的好壞。電力企業(yè)需成立專業(yè)的設(shè)備評估小組，對各電力運(yùn)行設(shè)備等進(jìn)行定期維護(hù)和評估，保證設(shè)備能夠滿足國家規(guī)定的要求。對于一些磨損或老舊設(shè)備要進(jìn)行維護(hù)和更換，從而實現(xiàn)電力系統(tǒng)電力變電站的高效安全運(yùn)行，在這個基礎(chǔ)上提高電力行業(yè)的發(fā)展實力。

4.4.2 RDD分區(qū)

目前聚類方式有三類：一是系統(tǒng)聚類，用于對小樣本的對象間聚類以及對變量聚類。二是有序樣品聚類，對有排序次序的樣本的對象間聚類，要求是次序相鄰的對象才能聚為一類。三是動態(tài)聚類，適用于樣本量大時對象間的聚類，一般用k-means法處理。由于內(nèi)部審計一般依靠歷史數(shù)據(jù)，提出有價值的工作建議，所以由于涉及內(nèi)部審計的業(yè)務(wù)數(shù)據(jù)量較大，所以本文采用第三種聚類分析方式。

一般情況下，RDD（resilient distributed datasets）會自動進(jìn)行分區(qū)，但由于分區(qū)的數(shù)量影響著運(yùn)行時間的變化，尤其是通信代價在分布式程序中占比很大，Spark 程序可以自定義分區(qū)數(shù)量，因此通過控制RDD 分區(qū)對數(shù)據(jù)進(jìn)行并行化處理來減少通信開銷。最終目的是盡量減少網(wǎng)絡(luò)傳輸代價，從而極大地提升整體性能。

比如，明確鰱鳙魚的投放、捕撈經(jīng)營權(quán)歸千島湖發(fā)展集團(tuán)，鰱鳙魚年投放量必須在60萬kg以上，鰱鳙魚捕撈生產(chǎn)采取限額捕撈制度。

在spark-shell中執(zhí)行分區(qū)代碼部分如下所示：

實時跟蹤系統(tǒng)就是跟蹤、記錄學(xué)生的學(xué)習(xí)過程和教師的教學(xué)過程，得到大量的學(xué)習(xí)數(shù)據(jù)和教學(xué)數(shù)據(jù)，并智能化分析這些數(shù)據(jù)，得出有建設(shè)性的結(jié)論和建議，為改進(jìn)教學(xué)和學(xué)習(xí)提供強(qiáng)有力的指導(dǎo)。這一功能模塊與銅職院的質(zhì)量管理辦公室所做的工作切合，質(zhì)量管理辦公室的主要任務(wù)就是對學(xué)校教學(xué)質(zhì)量進(jìn)行診斷改進(jìn)分析研判。實時跟蹤系統(tǒng)不僅對單個教師的教學(xué)提供幫助，更是對整個學(xué)校的教學(xué)改革和教學(xué)研究提供大數(shù)據(jù)支持。因此這是學(xué)校應(yīng)該重點建設(shè)的第二個模塊，此方面可能涉及到人臉識別、智能跟蹤定位、數(shù)據(jù)存儲等相關(guān)的技術(shù)。

1.textFile(path,partition)//從HDFS讀取數(shù)據(jù)

2.def getPartitions:Array[Partition]//通過該方法獲取RDD的分區(qū)數(shù)量（）

3.parallelize(1 to 100,任務(wù)數(shù))

4.getNumPartitions:Int=分區(qū)數(shù)//RDD的分區(qū)

5.saveAsTextFile("/路徑")}//保存路徑

4.5 算法流程與舉例說明

4.5.1 算法流程

SIACD算法流程圖如圖4所示。

4.5.2 算法舉例

為了更加清晰地論述SIACD 算法的主要思想，舉例如圖5所示。

設(shè)min_sup=30%，則挖掘頻繁k-項集的事務(wù)數(shù)為當(dāng)設(shè)分區(qū)數(shù)為2時，局部頻繁k-項集的事務(wù)數(shù)為count(Ck)≥假設(shè)求L3(k=3)，則將局部布爾矩陣按項數(shù)大小降序重新排列，然后把項數(shù)小于3 的事務(wù)T1和T6刪除，產(chǎn)生新的局部布爾矩陣

Fig.4 SIACD algorithm flow chart圖4 SIACD算法流程圖

綜上分析，只有項集{I1,I2,I3}滿足要求，因此得到頻繁3-項集L3={I1,I2,I3}。將I轉(zhuǎn)換成MAC 地址，得到L3={MAC1,MAC2,MAC3}。即MAC 地址用戶頻繁地同時出現(xiàn)在事務(wù)T5～T7中，因此對應(yīng)的用戶1、用戶2、用戶3為同一社團(tuán)成員。

Fig.5 Parallel processing diagram based on improved Apriori圖5 基于改進(jìn)Apriori的并行處理圖解

4.6 算法分析

4.6.1 時間復(fù)雜性分析

SIACD算法通過預(yù)處理過程將數(shù)據(jù)集轉(zhuǎn)化為布爾矩陣，只掃描一次全部的事務(wù)數(shù)據(jù)集。布爾向量兩兩自連接可直接獲取頻繁項集，無需迭代運(yùn)算，有效減少了計算量，并結(jié)合Spark 實現(xiàn)了并行化處理，降低了運(yùn)行時間。設(shè)事務(wù)數(shù)為m、項數(shù)為n、分區(qū)數(shù)為p，該算法的時間復(fù)雜度為O(mn/p)，小于Apriori算法的時間復(fù)雜度為O(mn2)。另外，Spark 將數(shù)據(jù)緩存在內(nèi)存中計算，避免了大量的磁盤I/O 操作，降低了運(yùn)行時間，提高了計算效率。

4.6.2 空間復(fù)雜性分析

SIACD算法利用0-1形式轉(zhuǎn)化數(shù)據(jù)，有效減少了數(shù)據(jù)的存儲空間。通過布爾向量兩兩自連接完成交運(yùn)算，有效減少了候選項集的規(guī)模，避免了大量的迭代計算，同時減少了中間結(jié)果的存儲空間。因此當(dāng)事務(wù)數(shù)為m及項數(shù)為n時，該算法的空間復(fù)雜度為O(n)，小于Apriori算法的空間復(fù)雜度為O(n2)。

5 實驗驗證與分析

5.1 實驗環(huán)境

搭建Spark分布式計算集群，其中包含1個master主節(jié)點和7 個slave 計算節(jié)點。計算機(jī)配置：CPU 型號為Intel core i7-6500U，內(nèi)存為16 GB，硬盤為1 TB，操作系統(tǒng)為Linux系統(tǒng)，Ubuntu 14.04，JDK 1.8，Hadoop 2.6.0，Spark 1.6。

5.2 實驗對比

本文均采用多次平均值的方式統(tǒng)計運(yùn)行時間以消除單次實驗帶來誤差的影響。通過對MAC 地址數(shù)據(jù)集進(jìn)行隨機(jī)采樣來控制輸入MAC 地址事務(wù)數(shù)據(jù)規(guī)模。采用UCI 數(shù)據(jù)集中MAC 地址樣本數(shù)據(jù)集概況如表2所示。

Table 2 Survey of sample data sets表2 樣本數(shù)據(jù)集概況

5.2.1 結(jié)果準(zhǔn)確性實驗

實驗條件：集群節(jié)點數(shù)為8，MAC 地址事務(wù)數(shù)據(jù)為樣本1和樣本2，預(yù)設(shè)min_sup=20%及δ=0.05[13]，將兩樣本中固有社團(tuán)作為社團(tuán)發(fā)現(xiàn)結(jié)果準(zhǔn)確性的評價標(biāo)準(zhǔn)，對比SIACD 算法、Apriori 算法、MP-T-CS 算法、CS 算法、NMF 算法[12]、并行譜聚類算法[29]的挖掘結(jié)果。N()表示該算法挖掘的社團(tuán)個數(shù)，實驗結(jié)果如表3所示。

Table 3 Comparison of mining result表3 挖掘結(jié)果對比 個

實驗分析：如表3 所示，六種算法的社團(tuán)挖掘結(jié)果大致相同，且并行SIACD 算法和單機(jī)Apriori 算法挖掘的社團(tuán)質(zhì)量和數(shù)量相同。實驗說明：SIACD 算法的并行化處理是可靠的，能準(zhǔn)確挖掘出滿足支持度閾值的頻繁項集以及所需提取的社團(tuán)及社團(tuán)成員集合。

5.2.2 計算效率實驗

實驗條件：集群節(jié)點數(shù)為8，預(yù)設(shè)min_sup=20%，MAC 地址事務(wù)數(shù)據(jù)為樣本1 至樣本5，對比SIACD算法、Apriori 算法、MP-T-CS 算法、CS 算法的運(yùn)行時間的變化情況，實驗結(jié)果如圖6所示。

Fig.6 Comparison of running time of 4 algorithms in different amount of data圖6 四種算法在不同數(shù)據(jù)量下運(yùn)行時間的比較

實驗分析：如圖6所示，當(dāng)數(shù)據(jù)量較少時，SIACD算法、MP-T-CS算法、CS算法三種算法的運(yùn)行時間大致相同，原因是SIACD 算法是建立在Spark 偽集群上，節(jié)點之間傳輸數(shù)據(jù)浪費了時間，因此此時并沒有體現(xiàn)集群并行計算的優(yōu)勢。當(dāng)數(shù)據(jù)量逐漸增大時，SIACD算法的運(yùn)行時間要明顯低于其他算法的運(yùn)行時間，這是由于SIACD 算法利用布爾矩陣將數(shù)據(jù)進(jìn)行了壓縮，以及優(yōu)化了頻繁項集迭代的過程。當(dāng)數(shù)據(jù)量較大時，通信開銷占比微小可忽略不計，Spark基于內(nèi)存快速計算的特性顯現(xiàn)優(yōu)勢。實驗說明：SIACD 算法對海量數(shù)據(jù)的處理能力和計算效率比Apriori算法、MP-T-CS算法、CS算法更好。

5.2.3 支持度實驗

實驗條件：集群節(jié)點數(shù)為8，MAC 地址事務(wù)數(shù)據(jù)為樣本3，min_sup從10%至50%依次遞增，對比SIACD 算法、Apriori 算法、MP-T-CS 算法、CS 算法的運(yùn)行時間的變化情況，實驗結(jié)果如圖7所示。

Fig.7 Comparison of running time of 4 algorithms under different min_sup圖7 四種算法在不同支持度閾值下運(yùn)行時間的比較

實驗分析：如圖7 所示，四種算法的運(yùn)行時間會隨著支持度閾值的增大而減少，原因是算法利用支持度刪除不滿足要求的數(shù)據(jù)，支持度閾值越高，挖掘頻繁項集的數(shù)量就越少，時間消耗越少。隨著支持度閾值逐漸減少時，SIACD 算法的運(yùn)行時間明顯少于其他三種算法，這是由于SIACD算法利用0-1代替原始數(shù)據(jù)，減少數(shù)據(jù)存儲和掃描的時間，并優(yōu)化了計算過程，從而減少了運(yùn)行時間。實驗說明：支持度閾值過大挖據(jù)的有效信息減少，而支持度閾值過小挖掘的信息復(fù)雜且冗余，這說明預(yù)先設(shè)定不同的支持度閾值會影響產(chǎn)生頻繁項集的時間，進(jìn)而影響算法的計算效率。在同等條件下，SIACD 算法的計算效率高于其他的算法。

5.2.4 可擴(kuò)展性實驗

加速比是同一任務(wù)在單節(jié)點和多節(jié)點并行處理中消耗時間的比率，用來衡量算法程序并行化的性能及效果。加速比公式:

實驗1MAC 地址事務(wù)數(shù)據(jù)為樣本3，集群節(jié)點為1 至8，預(yù)設(shè)min_sup=20%，分別測試SIACD 算法、MP-T-CS算法的加速比，實驗結(jié)果如圖8所示。

Fig.8 Change of speedup ratio of algorithms圖8 算法加速比的變化情況

實驗分析：如圖8 所示，兩個算法的加速比均隨著節(jié)點數(shù)的增加呈上升趨勢，這表明計算速度在逐步提高。當(dāng)節(jié)點數(shù)也相同時，SIACD 算法的加速比總是要高于MP-T-CS 算法，原因是SIACD 算法將數(shù)據(jù)壓縮，有效減少了數(shù)據(jù)處理時間，并省去了生成頻繁項集的迭代過程，大大降低了運(yùn)行時間。實驗說明：雖然SIACD 算法和MP-T-CS 算法都具備可擴(kuò)展性，但SIACD算法的并行化性能及效果更好，對海量數(shù)據(jù)的計算效率更高。

實驗2集群節(jié)點為1 至8，預(yù)設(shè)min_sup=20%，分別測試SIACD算法計算MAC地址事務(wù)數(shù)據(jù)樣本1至樣本5的加速比，實驗結(jié)果如圖9所示。

Fig.9 Change of speedup ratio of SIACD algorithm under different amount of data圖9 SIACD算法在不同數(shù)據(jù)量下加速比的變化

實驗分析：如圖9所示，當(dāng)節(jié)點數(shù)不變，數(shù)據(jù)量較小時，線段接近水平，這說明加速效果并不明顯，原因是此時計算時間較短，通信開銷占比略大，并行計算優(yōu)勢也不突出。但當(dāng)數(shù)據(jù)量較大時，通信開銷占比可忽略不計，由于SIACD算法是基于Spark內(nèi)存快速計算的，加速優(yōu)勢明顯。實驗說明：在處理海量數(shù)據(jù)時，SIACD算法可以有效減少時間消耗，具有較好的處理能力和計算效率。

6 結(jié)束語

針對社團(tuán)發(fā)現(xiàn)算法計算效率低及復(fù)雜度高等問題，本文提出了基于Spark利用改進(jìn)關(guān)聯(lián)規(guī)則解決無線城市社團(tuán)發(fā)現(xiàn)問題的SIACD算法。該算法充分利用Spark基于內(nèi)存計算的特性，避免了MapReduce多次磁盤讀寫操作，改善了Apriori 算法迭代計算的不足，提高了社團(tuán)發(fā)現(xiàn)的效率。實驗結(jié)果表明，傳統(tǒng)的社團(tuán)發(fā)現(xiàn)算法和關(guān)聯(lián)規(guī)則算法均不滿足大數(shù)據(jù)時代對計算速度的要求，SIACD算法性能優(yōu)勢明顯，降低了計算時間，有效提升了對海量數(shù)據(jù)的處理能力。下一步，希望結(jié)合FP-tree 算法對無線城市社團(tuán)發(fā)現(xiàn)問題進(jìn)行更深入的研究。