阮得寶，李長云

（湖南工業(yè)大學(xué) 計算機與通信學(xué)院，湖南 株洲 412007）

一種改進的基于Spark 的用戶行為分析方法的研究

阮得寶，李長云

（湖南工業(yè)大學(xué) 計算機與通信學(xué)院，湖南 株洲 412007）

為解決大數(shù)據(jù)量情況下的網(wǎng)絡(luò)用戶行為分析的時效性、準(zhǔn)確性，針對Apriori算法對數(shù)據(jù)庫反復(fù)掃描和候選集過大的問題，提出了一種將壓縮矩陣和事務(wù)權(quán)值引入的改進型Apriori算法，并將改進后的算法運用于云計算平臺Spark。實驗證明，改進后的算法的性能和效率都更高，在網(wǎng)絡(luò)用戶行為分析中具有優(yōu)勢。

Spark；Apriori；互聯(lián)網(wǎng)；數(shù)據(jù)分析；網(wǎng)絡(luò)用戶行為分析

1　背景知識介紹

隨著互聯(lián)網(wǎng)的飛速發(fā)展，網(wǎng)絡(luò)逐漸成為人們獲取信息的最重要手段，網(wǎng)絡(luò)數(shù)據(jù)流量也產(chǎn)生了巨大的增長。用戶行為分析，是指在獲得網(wǎng)站訪問量基本數(shù)據(jù)的情況下，對有關(guān)數(shù)據(jù)進行統(tǒng)計、分析，從中發(fā)現(xiàn)用戶訪問網(wǎng)站的規(guī)律，并將這些規(guī)律與網(wǎng)絡(luò)營銷策略和推薦系統(tǒng)等相結(jié)合，從而發(fā)現(xiàn)目前網(wǎng)絡(luò)活動中可能存在的問題，并為進一步優(yōu)化用戶體驗和擴大服務(wù)提供商利益提供依據(jù)［1］。但是由于網(wǎng)絡(luò)的開放性、動態(tài)性以及多樣性等特點，用戶在網(wǎng)上產(chǎn)生的數(shù)據(jù)量越大，用戶行為分析的難度也越大。因此，在大數(shù)據(jù)量情況下對網(wǎng)絡(luò)用戶行為進行分析的需求越來越迫切。

用戶行為分析的目的，是掌握用戶的行為習(xí)慣和特點，進而根據(jù)用戶的行為特點進行有針對性的網(wǎng)絡(luò)信息推送；通過推送，用戶獲取需要信息的難度也大大降低。用戶行為分析方式主要有以下幾種方法：用戶特征分析，是指找出用戶的行為特征的方法；關(guān)聯(lián)分析，是指尋找用戶的兩種或者幾種行為習(xí)慣的聯(lián)系、相關(guān)性或者因果關(guān)系；分類與預(yù)測，利用分類技術(shù)將用戶歸屬于一個特定的類；異常分析，針對用戶的不正常網(wǎng)絡(luò)流量進行分析；TopN分析，在用戶行為分析中，往往按照某一指標(biāo)進行倒序或者正序排列，取前N項分析。

互聯(lián)網(wǎng)發(fā)展的同時，網(wǎng)絡(luò)用戶行為相關(guān)的數(shù)據(jù)也在激增，傳統(tǒng)的用戶行為分析方法不足以支持如此巨大的數(shù)據(jù)量。因此，用戶行為分析的方法必須運用海量數(shù)據(jù)運算［2］。在這樣的情況下，海量數(shù)據(jù)的挖掘技術(shù)就至關(guān)重要。當(dāng)前海量數(shù)據(jù)挖掘的辦法主要有以下幾種。

1）抽樣，對數(shù)據(jù)進行抽樣，在抽樣數(shù)據(jù)的基礎(chǔ)上建立數(shù)據(jù)挖掘模型；2）集成方法，劃分數(shù)據(jù)集，并行創(chuàng)建分類器，然后集成處理；3）Map/reduce框架，基于云計算平臺處理海量數(shù)據(jù)［3］。

針對云計算情形下的用戶行為分析的算法主要有以下幾種。

1）分類。分類是指將數(shù)據(jù)庫中的數(shù)據(jù)按照種類和性質(zhì)分別歸類。2）回歸分析。回歸分析是指查找出幾種變量之間的依賴關(guān)系，并用來分析變量里所包含的數(shù)據(jù)之間的規(guī)律。3）聚類分析。聚類分析是指根據(jù)規(guī)定的聚類變量，將數(shù)據(jù)庫中的數(shù)據(jù)分成若干類。4）關(guān)聯(lián)規(guī)則。關(guān)聯(lián)規(guī)則是指數(shù)據(jù)對象之間的依賴關(guān)系，目的就是從發(fā)現(xiàn)支持度大于給定值的規(guī)則。5）神經(jīng)網(wǎng)絡(luò)方法。神經(jīng)網(wǎng)絡(luò)方法模擬人的直觀思維方式，將信息分布式存儲以及并行協(xié)同處理，特點是非線性映射能力及高度的并行性，神經(jīng)網(wǎng)絡(luò)方法在邏輯推理中寫成串行的指令，讓計算機運行。6）Web數(shù)據(jù)挖掘。Web數(shù)據(jù)挖掘應(yīng)用于Web環(huán)境，它從大量的Web文檔數(shù)據(jù)中發(fā)現(xiàn)隱藏在數(shù)據(jù)中的規(guī)律，通過對這些數(shù)據(jù)的挖掘，可以得到僅通過文字檢索無法獲得的信息。

基于云計算平臺的用戶行為分析中，較為重要、應(yīng)用較廣泛的算法是關(guān)聯(lián)規(guī)則算法，其流程圖如圖1所示。

圖1　關(guān)聯(lián)分析流程圖Fig.1　Flow chart of the correlation analysis

關(guān)聯(lián)分析中最典型的算法就是Apriori算法。Apriori算法的核心思想是基于兩階段頻集思想的挖掘算法，它的優(yōu)點是簡單、容易理解和數(shù)據(jù)要求低。但是，傳統(tǒng)的Apriori算法存在下面2個缺點：1）根據(jù)Apriori算法的定義，Apriori算法會產(chǎn)生大量的頻繁集；2）在數(shù)據(jù)庫規(guī)模巨大的情況下，算法會重復(fù)掃描事務(wù)數(shù)據(jù)庫，這種反復(fù)掃描會增加I/O的負載，并且隨著數(shù)據(jù)庫規(guī)模的增加，I/O負載會呈現(xiàn)指數(shù)式的增加。

近幾年，隨著Hadoop的使用不斷廣泛和完善，大量研究人員也都致力于將傳統(tǒng)的數(shù)據(jù)挖掘算法采用并行編程框架進行分布式并行化處理，以提高數(shù)據(jù)挖掘的效率［4］。許多學(xué)者也針對Apriori算法的不足，結(jié)合Hadoop在大集群中所展現(xiàn)的優(yōu)勢，提出了一些基于Hadoop的改進型Apriori算法。其不足之處大多是求解局部的頻繁項集時，沒有剪切操作，導(dǎo)致生成的候選項集過大。隨著Spark的異軍突起，Hadoop有逐漸被取代的趨勢?，F(xiàn)階段，針對Spark的運用，主要集中在數(shù)據(jù)挖掘方面，鮮有將Spark運用于用戶行為分析的研究。本文提出的基于Spark的改進型Apriori算法更能適用于大數(shù)據(jù)挖掘，從而對用戶行為進行可靠的分析。

2　基于Spark的Apriori算法設(shè)計

針對Apriori算法效率欠佳的問題，許多研究人員在Apriori原始算法的基礎(chǔ)上對Apriori算法進行了大量地改進。改進的Apriori算法所使用的主要技術(shù)有：哈希技術(shù)、事務(wù)壓縮技術(shù)、分區(qū)技術(shù)和采樣技術(shù)等等。而通過這些技術(shù)改進后的Apriori算法都存在著候選集過大或者犧牲了原算法計算結(jié)果準(zhǔn)確性的問題［5］。

在大數(shù)據(jù)情況下，影響Apriori算法效率最大的問題主要是對數(shù)據(jù)庫的反復(fù)掃描。為了解決這個問題，課題組在使用矩陣形式來存儲數(shù)據(jù)庫的基礎(chǔ)上，提出利用向量計算的方法計算支持度，并且對相同事務(wù)壓縮以減小矩陣的大小，優(yōu)化數(shù)據(jù)結(jié)構(gòu)，提高算法的效率。算法首先對交易事務(wù)的數(shù)據(jù)庫進行掃描，然后將數(shù)據(jù)庫轉(zhuǎn)化成一個布爾矩陣，轉(zhuǎn)化的同時對事務(wù)數(shù)據(jù)進行壓縮，在生成頻繁集時，得到項集的支持度計數(shù)，若大于最小支持度計數(shù)，保留項集，反之則舍棄。計算過程中對數(shù)據(jù)矩陣進行刪減，并反復(fù)迭代上述過程，避免了原算法在計算候選集的支持度時掃描全部數(shù)據(jù)庫的不足。

Spark是UC Berkeley AMP Lab所開源的類HadoopMap/reduce的通用并行框架，擁有Hadoop MapReduce所具有的優(yōu)點。Spark與Map/reduce的區(qū)別是，它的Job中間輸出和結(jié)果可以保存在內(nèi)存中，沒有讀寫HDFS的需求［6］。因此，Spark為迭代式數(shù)據(jù)處理提供了更好的支持。Spark的生態(tài)系統(tǒng)如圖2所示。Spark的核心和精華是它的彈性分布式數(shù)據(jù)集（resilient distributed dataset，RDD），RDD是只讀的紀(jì)錄分區(qū)的集合，能夠在內(nèi)存中加載，方便再次使用。RDD可以分布在多個節(jié)點上，可以進行并行處理［7］。

圖2　Spark的生態(tài)系統(tǒng)圖Fig.2　Spark ecosystem diagram

基于Spark的改進型Apriori算法使用Map/reduce思想實現(xiàn)頻繁的計算。基于Spark的改進Apriori算法流程圖如圖3所示。

圖3　基于Spark的改進Apriori算法流程圖Fig.3　Flow chart of the improved Spark-based Apriori algorithm

在設(shè)計方面，由于Spark運行在Mesos平臺，所以采用分布式管理系統(tǒng)作為原始數(shù)據(jù)存放的存放系統(tǒng)。在Spark實現(xiàn)算法時，首先將原始的交易數(shù)據(jù)存放在HDFS中，隨后讀取HDFS上的交易事務(wù)數(shù)據(jù)，并將其轉(zhuǎn)化為壓縮矩陣，根據(jù)轉(zhuǎn)化后的矩陣數(shù)創(chuàng)建RDD。其次，通過Map操作計算候選集的局部支持度計數(shù)，通過Reduce計算候選集的全局支持度計數(shù)。因為轉(zhuǎn)化后的數(shù)據(jù)是緩存到本地隨機存取存儲器RAM中，所以每一個Map操作的過程中，都是直接讀取候選項集中項的行向量數(shù)據(jù)，不需要到分布式文件系統(tǒng)上重寫。數(shù)據(jù)集的劃分和任務(wù)分配都在Spark中由系統(tǒng)自動完成的［8］。為了驗證改進算法的性能提升程度，課題組進行了2組實驗，分別檢驗兩種算法在常規(guī)和云計算平臺下的表現(xiàn)。

3　實驗結(jié)果分析

Apriori算法性能提升，是指算法在分析處理大數(shù)據(jù)環(huán)境下的用戶行為數(shù)據(jù)時，其運算速度得到了提升。課題組設(shè)計2組實驗來驗證改進算法的性能。實驗一在不同規(guī)模的數(shù)據(jù)環(huán)境下，檢驗2種算法的性能。實驗二則是檢測在云計算平臺下，針對不同節(jié)點時，算法性能。實驗環(huán)境配置如下表1所示。

表1　實驗環(huán)境配置表Table 1　Configuration table of the experimental environment

實驗采用的數(shù)據(jù)是從數(shù)據(jù)堂獲得，數(shù)據(jù)內(nèi)容為社交資源共享站點用戶行為數(shù)據(jù)集［9］，數(shù)據(jù)大小總計652.36 MB。實驗一采用3種數(shù)據(jù)規(guī)模，對原算法和改進算法的性能進行對比，如表2所示。圖4用折線圖方式對比2種算法的運行時間。

表2　實驗1算法測試結(jié)果Table 2　Algorithm test results of experiment 1 ms

圖4　不同數(shù)據(jù)規(guī)模下2種算法性能的比較Fig.4　Comparison between the performance of two algorithms with different data scales

通過表2和圖4可知，改進Apriori算法效率在執(zhí)行時間上得到了很大的提升。但當(dāng)數(shù)據(jù)量增大時，提升的效率有所降低。

實驗二使用不同的節(jié)點的集群，測試處理相同大小數(shù)據(jù)時，原算法和運行于云計算平臺Spark的改進算法的性能。原算法無法運用在多節(jié)點，因此僅有1組數(shù)據(jù)。實驗結(jié)果如表3所示。圖5用折線圖的方式直觀地反映在不同節(jié)點數(shù)量情況下，改進算法的性能。

表3　實驗2算法測試結(jié)果Table 3　Algorithm test results of experiment 2 ms

圖5　不同節(jié)點下算法的性能Fig.5　Improved performance of algorithms with different nodes

通過表3和圖5可知，隨著節(jié)點數(shù)量的上升，在云計算平臺上使用的改進Apriori算法的效率越來越高?？偟膩碚f，效率的提升和節(jié)點數(shù)成正比。

綜合以上的實驗結(jié)果可以得出結(jié)論，在云計算平臺上使用的改進Apriori算法在性能和效率方面提升顯著，符合預(yù)期。

4　結(jié)語

本文為解決大數(shù)據(jù)量情況下的網(wǎng)絡(luò)用戶行為分析的時效性、準(zhǔn)確性，針對Apriori算法對數(shù)據(jù)庫反復(fù)掃描和候選集過大的問題，在使用矩陣形式來存儲數(shù)據(jù)庫的基礎(chǔ)上，提出了利用向量計算的方法計算支持度，并且對相同事務(wù)壓縮以減小矩陣的大小，優(yōu)化數(shù)據(jù)結(jié)構(gòu)，提高算法的效率，并將改進后的算法運用于云計算平臺Spark。實驗結(jié)果表明，課題組提出的改進Apriori算法的性能有明顯的提升。并且改進后的算法運用于云計算平臺Spark時，性能也有進一步顯著的提升。

［1］呂桃霞，劉培玉.一種基于矩陣的強關(guān)聯(lián)規(guī)則生成算法［J］.計算機應(yīng)用研究，2011，28（4）：1301-1303.LTaoxia，LIU Peiyu.Algorithm for Generaring Strong Association Rules Based on Matrix［J］.Application Research of Computers，2011，28（4）：1301-1303.

［2］劉宗成，張忠林，田苗鳳.基于關(guān)聯(lián)規(guī)則的網(wǎng)絡(luò)行為分析［J］.電子科技，2015，28（9）：16-18.LIU Zhongcheng，ZHANG Zhonglin，TIAN Miaofeng.Analysis of Network Behaviors Based on Association Rules［J］.Electronic Science and Technology，2015，28（9）：16-18.

［3］Apache Spark.The Apache Software Foundation［EB/OL］.［2015-09-21］.http://spark.apache.org.

［4］吳岳忠，周訓(xùn)志.面向Hadoop的云計算核心技術(shù)分析［J］.湖南工業(yè)大學(xué)學(xué)報，2013，27（1）：77-80.Wu Yuezhong，Zhou Xunzhi.The Core Technology of Hadoop-Oriented Cloud Computing［J］.Journal of Hunan University of Technology，2013，27（1）：77-80.

［5］陶彩霞，謝曉軍，陳康，等.基于云計算的移動互聯(lián)網(wǎng)大數(shù)據(jù)用戶行為分析引擎設(shè)計［J］.電信科學(xué)，2013，29（3）：27-31.TAO Caixia，XIE Xiaojun，CHEN Kang，et al.Design of Mobile Internet Big Data User Behavior Analysis Engine Based on Cloud Computing［J］.Telecommunications Science，2013，29（3）：27-31.

［6］鄭鳳飛，黃文培，賈明正.基于Spark的矩陣分解推薦算法［J］.計算機應(yīng)用，2015，35（10）：21-23.ZHENG Fengfei，HUANG Wenpei，JIA Mingzheng.Matrix Factorization Recommendation Algorithm Based on Spark［J］.Journal of Computer Applications，2015，35（10）：21-23.

［7］宋文惠，高建瓴.基于矩陣的Apriori算法改進［J］.計算機技術(shù)與發(fā)展，2016，26（6）：80-83.SONG Wenhui，GAO Jianling.The Inproved Apriori Algorithm Based on Matrix［J］.Computer Technology and Development，2016，26（6）：80-83.

［8］李仕瓊.數(shù)據(jù)挖掘中關(guān)聯(lián)規(guī)則挖掘算法的分析研究［J］.電子技術(shù)與軟件工程，2015（4）：200.LI Shiqiong.Analysis of Algorithms Data Mining Association Rules Mining［J］.Electronic Technology & Software Engineering，2015（4）：200.

［9］YAO Junjie，CUI Bin，HAN Qiaosha，et al.Modeling User Expertise in Folksonomies by Fusing Multi-Type Features［C］//15th International Conference on Database Systems for Advanced Applications（DASFAA 2011）.HongKong：Springer，2011：53-67.

（責(zé)任編輯：申劍）

On an Improved Spark-Based Method for the Analysis of User Behaviors

RUAN Debao，LI Changyun
（School of Computer and Communication，Hunan University of Technology，Zhuzhou Hunan 412007，China）

In view of the repeated scanning of the database and the potential massive candidate sets involved in the Apriori algorithm， an improved method， with the compressed matrix and the transaction value introduced in the process， is proposed to solve such problems as the timeliness and accuracy of the analysis of network user behaviors， with a further application of the improved algorithm to Spark， a cloud computing platform.The experimental results verify the better performance and higher efficiency of the proposed method， with evident advantages in the user behavior analysis.

Spark；Apriori；Internet-work；data analysis；user behavior analysis

TP301.6

A

1673-9833（2016）04-0032-04

10.3969/j.issn.1673-9833.2016.04.007

2016-06-17

國家自然科學(xué)基金資助項目（61350011，61379058，41362015），湖南省自然科學(xué)基金資助項目（14JJ2115，12JJ2036），湖南工業(yè)大學(xué)自然科學(xué)基金資助項目（2014HX16）

阮得寶（1991-），男，安徽六安人，湖南工業(yè)大學(xué)碩士生，主要研究方向為大數(shù)據(jù)，E-mail：1040668038@qq.com