云計(jì)算環(huán)境下基于Apriori算法的智能推薦模型

摘要：介紹了Apriori算法和智能推薦的基本思想，針對(duì)當(dāng)前互聯(lián)網(wǎng)應(yīng)用中智能推薦復(fù)雜性問(wèn)題，提出了云計(jì)算環(huán)境下基于Apriori的聚類算法模型。該模型根據(jù)用戶訪問(wèn)網(wǎng)站的行為特征數(shù)據(jù)，分析和挖掘出用戶期望的瀏覽對(duì)象，動(dòng)態(tài)調(diào)整云計(jì)算系統(tǒng)的智能推薦內(nèi)容。實(shí)驗(yàn)結(jié)果表明，該算法模型有效提高了智能推薦的準(zhǔn)確性和效率。

關(guān)鍵詞：Aporiori；智能推薦；云計(jì)算；MapReduce；Hadoop

DOIDOI：10.11907/rjdk.151322

中圖分類號(hào)：TP3-0

文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：16727800（2015）006000803

基金項(xiàng)目基金項(xiàng)目：浙江省教育科學(xué)規(guī)劃項(xiàng)目（2014SCG430）

作者簡(jiǎn)介作者簡(jiǎn)介：金偉?。?982-），男，浙江義烏人，碩士，義烏工商職業(yè)技術(shù)學(xué)院機(jī)電信息分院講師，研究方向?yàn)橛?jì)算機(jī)網(wǎng)絡(luò)安全、云計(jì)算。

0 引言

在信息技術(shù)支持下，智能推薦系統(tǒng)能夠?yàn)橛脩籼峁﹤€(gè)性化的推薦結(jié)果，使每個(gè)用戶獲取自己真正需要的信息。隨著云計(jì)算時(shí)代的到來(lái)，網(wǎng)絡(luò)內(nèi)容提供商要想更好吸引用戶訪問(wèn)，增加受關(guān)注程度和客戶滿意度，必須在用戶體驗(yàn)和網(wǎng)站特點(diǎn)上進(jìn)行研究。智能推薦作為增加用戶體驗(yàn)、提升網(wǎng)站滿意度的有效途徑，近年來(lái)受到了業(yè)界研究人員的廣泛關(guān)注。搜索引擎輸入的是查詢關(guān)鍵字，推薦引擎輸入的則是用戶的行為特征數(shù)據(jù)。智能推薦就是針對(duì)這種行為建模，對(duì)用戶感興趣或者期望看到的內(nèi)容進(jìn)行推測(cè)的服務(wù)。

用戶行為分析和挖掘是基于用戶訪問(wèn)、點(diǎn)擊、操作等的“大數(shù)據(jù)”行為，根據(jù)熱門、興趣、地域、探索四大策略邏輯，按照一定算法推測(cè)出用戶感興趣的內(nèi)容。數(shù)據(jù)分析的目的是建立客戶行為模型，推理出目標(biāo)數(shù)據(jù)。這些模式可以是客戶細(xì)分或者客戶聚類，也可以是關(guān)聯(lián)規(guī)則集。根據(jù)這些行為特征建立的模型，能夠自動(dòng)計(jì)算出用戶感興趣的內(nèi)容，判斷出用戶的可能性需求等。數(shù)據(jù)挖掘、機(jī)器學(xué)習(xí)、模糊數(shù)學(xué)和其它信息處理手段被廣泛應(yīng)用于數(shù)據(jù)分析領(lǐng)域。

本文提出云計(jì)算環(huán)境下基于Apriori算法的智能推薦模型，該模型通過(guò)綜合考慮用戶瀏覽行為習(xí)慣與心理預(yù)期在不同網(wǎng)站的表現(xiàn)，預(yù)測(cè)出網(wǎng)站推薦訪問(wèn)的內(nèi)容，動(dòng)態(tài)調(diào)整云計(jì)算系統(tǒng)的智能推薦策略，在滿足用戶預(yù)期的前提下實(shí)現(xiàn)任務(wù)的及時(shí)性。基于用戶行為特征的智能推薦算法，通過(guò)對(duì)用戶行為特征進(jìn)行統(tǒng)計(jì)和數(shù)據(jù)挖掘得到這類用戶的瀏覽規(guī)律，從而增加用戶對(duì)網(wǎng)站的粘合度和體驗(yàn)。

1 算法模型理論依據(jù)及設(shè)計(jì)思想

云計(jì)算環(huán)境下，用戶訪問(wèn)具有動(dòng)態(tài)性和模糊性。根據(jù)用戶行為數(shù)據(jù)生成規(guī)則集，為了提高推薦的準(zhǔn)確性，并減少噪音，只保留大于最小置信度的規(guī)則。為了生成所有頻集，使用遞歸方法。

1.1 Apriori算法概念

Agrawal[1]等提出了用于挖掘關(guān)聯(lián)規(guī)則的Apriori算法。Apriori算法使用一種逐層搜索的迭代算法，目標(biāo)是通過(guò)不斷迭代，縮小聚類范圍。

過(guò)程如下：

（1）連接。目標(biāo)是找出Lk，通過(guò)Lk-1 做自連接運(yùn)算產(chǎn)生候選k-項(xiàng)目集的集合。設(shè)置候選集合為Ck。

（2）剪枝。對(duì)于Ck包含的元素，使所有的頻繁k-項(xiàng)目集都包含在Ck中，對(duì)數(shù)據(jù)庫(kù)進(jìn)行掃描計(jì)算， 計(jì)算Ck候選集合元素?cái)?shù)量。確定Lk， 從而屬于Lk[2]。

1.2 智能推薦建模

智能推薦 模型集合多種技術(shù)，包括關(guān)聯(lián)規(guī)則、數(shù)據(jù)挖掘、模糊決策、機(jī)器學(xué)習(xí)等，既要將大數(shù)據(jù)的樣本預(yù)處理好，也要融合好多種技術(shù)，取長(zhǎng)補(bǔ)短。隨著系統(tǒng)吞吐數(shù)據(jù)規(guī)模的擴(kuò)大，大數(shù)據(jù)挖掘成為智能推薦模型成功的關(guān)鍵，因此必須選擇分布式策略處理大量用戶行為數(shù)據(jù)，并進(jìn)行深入挖掘。MapReduce簡(jiǎn)單易用，其迭代式的運(yùn)算框架能很好地滿足這種數(shù)據(jù)挖掘分析的需求。

1.3 基于MapReduce的客戶特征智能推薦模型

本文基于用戶訪問(wèn)站點(diǎn)的行為特征，建立一種基于用戶行為特征分析的云計(jì)算調(diào)度機(jī)制，其模型如圖1所示，用戶終端負(fù)責(zé)收集本地用戶行為信息再上傳給各類服務(wù)提供商的用戶行為數(shù)據(jù)分析模塊。用戶行為數(shù)據(jù)分析模塊通過(guò)對(duì)用戶提交任務(wù)和查看任務(wù)結(jié)果行為的歷史數(shù)據(jù)進(jìn)行統(tǒng)計(jì)與分析，采用相應(yīng)的分布模型對(duì)用戶各時(shí)間片段內(nèi)的工作狀態(tài)和心里預(yù)期任務(wù)完成時(shí)間進(jìn)行定性刻畫(huà)。用戶行為規(guī)律數(shù)據(jù)按服務(wù)類別化，采用唯一的服務(wù)類別編碼并統(tǒng)一存儲(chǔ)在云計(jì)算綜合控制中心的策略管理模塊。任務(wù)調(diào)度模塊收到任務(wù)管理模塊的請(qǐng)求后根據(jù)服務(wù)編碼查找當(dāng)前時(shí)間片段的資源分配策進(jìn)行資源動(dòng)態(tài)分配。

MapReduce是Google提出的一個(gè)軟件框架，它提供了一種在大規(guī)模計(jì)算機(jī)Cluster中對(duì)大數(shù)據(jù)進(jìn)行分布式處理的算法，通過(guò)將海量數(shù)據(jù)集切分成小數(shù)據(jù)集，提交給不同的計(jì)算機(jī)節(jié)點(diǎn)作并行處理。 MapReduce將客戶行為特征數(shù)據(jù)結(jié)構(gòu)化為集，將規(guī)則的剪枝和連接轉(zhuǎn)換成Map和Reduce兩個(gè)函數(shù)。在MapReduce平臺(tái)里，一個(gè)作業(yè)的輸入數(shù)據(jù)集合被切分成多個(gè)單獨(dú)的集合，交由映射過(guò)程并行處理，將一組對(duì)映射成一組新的對(duì)，作為Reduce的輸入，執(zhí)行計(jì)算?；贛apReduce的調(diào)度機(jī)制如圖2 所示，由輸入、Map、Reduce、輸出4部分構(gòu)成[46]。

2 云計(jì)算環(huán)境下智能推薦實(shí)現(xiàn)策略

目前有很多改進(jìn)的關(guān)聯(lián)規(guī)則算法，但是大部分未考慮算法的執(zhí)行效率。為了提高算法效率，本文提出了一種基于MapReduce的任務(wù)調(diào)度算法來(lái)進(jìn)行Apriori數(shù)據(jù)挖掘。

2.1 Map階段

通過(guò)對(duì)用戶特征行為進(jìn)行建模，將Apriori連接和剪枝的過(guò)程抽象成Map和Reduce的過(guò)程，從而實(shí)現(xiàn)推理運(yùn)算的并行化處理。Hadoop[78]平臺(tái)下的MapReduce任務(wù)調(diào)度是等待響應(yīng)機(jī)制，即等待每個(gè)節(jié)點(diǎn)的請(qǐng)求，先是主節(jié)點(diǎn)應(yīng)對(duì)響應(yīng)，計(jì)算出哪個(gè)從節(jié)點(diǎn)是空閑的，如果空閑就分配任務(wù)給它，依次類推地響應(yīng)計(jì)算請(qǐng)求。

2.3 實(shí)驗(yàn)及結(jié)果分析

系統(tǒng)基于Hadoop0.20.0[912]開(kāi)發(fā)， 硬件配置是：Core 2 E7500 Dual-core Processor 4GB RAM。軟件配置是：Ubuntu Linux 11.10，Hadoop-0.20.0，JDK 1.6。

按照Hadoop部署手冊(cè)將Apriori算法Jar包部署到實(shí)驗(yàn)平臺(tái)，配置文件中替換Hadoop中自帶的FIFO的配置節(jié)點(diǎn)。實(shí)驗(yàn)總共部署9臺(tái)PC作為Cluster，其中一臺(tái)主機(jī)作為主節(jié)點(diǎn)Map主機(jī)，剩下的8臺(tái)PC作為子節(jié)點(diǎn)機(jī)。試驗(yàn)中分別采用FIFO傳統(tǒng)調(diào)度算法和本文所提出的基于MapReduce的Apriori算法，在HDS這個(gè)基準(zhǔn)測(cè)試程序中進(jìn)行Apriori變化實(shí)驗(yàn)，以及用戶特征行為獲取，輸出初始規(guī)則集。為了比較并行算法和傳統(tǒng)串行算法對(duì)JOB的影響，設(shè)置JOB精度為8個(gè)組，再根據(jù)Cluster的當(dāng)前作業(yè)負(fù)載，確定每組中JOB的數(shù)量。

從表1可以看出，在求解精度較低時(shí)，兩種算法的求解時(shí)間相當(dāng)，但隨著求解精度的增加，基于MapReduce的Apriori連接和剪枝過(guò)程要明顯優(yōu)于傳統(tǒng)的串行搜索。這是因?yàn)?，由于函?shù)的求解精度小，算法的并行迭代次數(shù)少，因此MapReduce框架的優(yōu)勢(shì)顯示不出來(lái)。在最極端的情況下，例如兩個(gè)表的關(guān)聯(lián)規(guī)則生成，任務(wù)經(jīng)過(guò)一次MapRedece過(guò)程即可求解，因此兩種算法所花時(shí)間差異不大。隨著候選集合的擴(kuò)展、精度的提高，加上迭代次數(shù)的增加，基于MapReduce的Apriori要明顯優(yōu)于線性的關(guān)聯(lián)規(guī)則算法。

從圖3可以看出，經(jīng)過(guò)對(duì)比，在客戶滿意度VOC調(diào)查中，經(jīng)過(guò)MapReduce框架處理的Apriori算法明顯優(yōu)于其它數(shù)據(jù)挖掘算法?；诳蚣芙Y(jié)構(gòu)可以有效提升變換的穩(wěn)定性，使小波變換的時(shí)間和精度穩(wěn)定在一個(gè)水平線上，而線性變換算法由于是串行執(zhí)行，完全依賴于處理器全部的處理時(shí)間，因此在穩(wěn)定性上，基于MapReduce的Apriori算法更具優(yōu)勢(shì)。

3 結(jié)語(yǔ)

本文針對(duì)移動(dòng)互聯(lián)網(wǎng)用戶連接問(wèn)題，將Apriori算法引入到智能推薦系統(tǒng)設(shè)計(jì)中，提出了一種云環(huán)境下的智能推薦模型。為提高用戶行為特征分析及關(guān)聯(lián)預(yù)測(cè)速度， 并實(shí)時(shí)應(yīng)用到網(wǎng)站推薦中， 設(shè)計(jì)了在MapReduce上運(yùn)行的具有高效率的Apriori并行算法模型。為減少算法中邊際效應(yīng)對(duì)預(yù)測(cè)的影響，可將Apriori應(yīng)用到云計(jì)算中，所設(shè)計(jì)的并行算法可以實(shí)現(xiàn)負(fù)載平衡且干擾少， 因而具有較高的加速比且具有適于Apriori算法的特性。但該模型尚有許多待改進(jìn)之處，如：智能推薦系統(tǒng)的模糊性、容錯(cuò)性等。如何準(zhǔn)確劃分推薦層次，以及在用戶行為數(shù)據(jù)不可信的情況下，如何對(duì)智能推薦模型進(jìn)行識(shí)別和優(yōu)化則有待進(jìn)一步研究。

參考文獻(xiàn)參考文獻(xiàn)：

[1]AGRAWAL R，SRIKANT R.Fast algorithms for mining association rules[C].In Proceeding of the 20th International Conference on Very Large Databases，1994：487499.

[2]趙衛(wèi)中.基于云計(jì)算平臺(tái)Hadoop 的并行Kmeans聚類算法設(shè)計(jì)研究[J].計(jì)算機(jī)科學(xué)，2011， 38（10）：166168.

[3]周景才.云計(jì)算環(huán)境下基于用戶行為特征的資源分配策略[J].計(jì)算機(jī)研究與發(fā)展，2014，51（5）：11081109.

[4]張凱.云計(jì)算下基于用戶行為信任的訪問(wèn)控制模型[J].計(jì)算機(jī)應(yīng)用，2014，34（4）：10511054.

[5]M BURROWS.The chubby lock service for looselycoupled distributed systems[J].Proceedings of the 7th symposium on Operating systems design and implementation，2006，6（2）：335350.

[6]J BERLINSKA，M DROZDOWSKI.Scheduling divisible MapReduce computations[J].Journal of Parallel and Distributed Computing，2011，3（71）：450459.

[7]T SANDHOLM，K LAI.Dynamic proportional share scheduling in hadoop job scheduling strategies for parallel processing[J].Dynamic proportional share scheduling in hadoop Job scheduling strategies for parallel processing，2010，2（62）：110131.

[8]K KAMBATLA.Towards optimizing hadoop provisioning in the cloud[J].First Workshop on Hot Topics in Cloud Computing，2009，3（2）：118.

[9]WU RONG.Cyclic workflow execution mechanism on top of MapReduce framework[C].Washington：Seventh International Conference on Semantics，Knowledge and Grids，2011：2835.

[10]NIELSEN O M，HEGLAND M.Parallel performance of fast wavelet transform[J].International Journal of High Speed Computing，2000，11（1）：5573.

[11]WANG C，WANG Q，REN K.Privacypreserving public auditing for data storage security in cloud computing[J].In Proceedings of IEEE INFOCOM，2010，3（2）：5960.

[12]WHITE R，WHITE T.Hadoop：the definitive guide[M].Sebastopol：OReilly Media，2012.

責(zé)任編輯（責(zé)任編輯：孫 娟）

英文摘要Abstract：The basis mechanism of Intelligent Recommendation is introduced. Aimed at solving the complicated issue， a new Apriori Algorithm model based on Cloud Computing is proposed. Recoding to the users behaviors of visiting website， the adaptive viewing objects are calculated by analyzing and data mining. And the contents of Recommendation are adjusted dynamically for computing. By analyzing the experiment result on Hadoop platform， it shows that the new model based on Apriori for Cloud Computing is more efficient and more exact.

英文關(guān)鍵詞Key Words： Apriori； Intelligent Recommendation； Cloud Computing； MapReduce； Hadoop