摘 要： 針對協(xié)同過濾（CF）推薦技術(shù)處理大數(shù)據(jù)時的計算效率問題，分析了CF算法的并行化。并行化CF算法采用Hadoop平臺的MapReduce并行編程模型，改善大數(shù)據(jù)環(huán)境下CF算法在單機運行時的計算性能。在實驗部分，設計不同集群環(huán)境下的加速比實驗，驗證該算法在大數(shù)據(jù)環(huán)境中具有的計算性能。

關(guān)鍵詞： 協(xié)同過濾； 計算效率； 加速比； Hadoop； 大數(shù)據(jù)

中圖分類號：TP391 文獻標志碼：A 文章編號：1006-8228（2016）05-30-04

Abstract： For the computational efficiency problem existing in big data processing with collaborative filtering （CF） recommendation， parallel computing of CF is analyzed. Parallelized CF algorithm uses MapReduce parallel programming model on Hadoop platform， which improves the computational efficiency of single PC to process big data. In the experiment section， the speedup experiments in different cluster environments are designed to verify the better computing performance of the algorithm in big data processing.

Key words： collaborative filtering； computational efficiency； speedup； Hadoop； Big data

0 引言

互聯(lián)網(wǎng)時代，網(wǎng)絡資源紛雜，信息過載，個性化推薦成為緩解用戶在網(wǎng)絡中的信息迷茫問題的重要途徑[1]。在多項目、多領域的推薦中，因不依賴用戶或項目內(nèi)容，具有較好通用性的協(xié)同過濾算法[2]成為較成功的推薦技術(shù)，因而其改進也受到廣泛關(guān)注。然而改進的算法通常是以犧牲計算效率換取計算準確度的提升。隨著大數(shù)據(jù)時代的來臨[3-7]，解決計算效率的問題也迫在眉睫。由于單機模式的計算能力有限，而分布式計算具有多資源、可擴展、高效計算等優(yōu)勢，用分布式計算實現(xiàn)高效的CF算法，既能提高推薦準確度，又能保證計算效率。目前主要使用云計算平臺Hadoop實現(xiàn)算法的并行化，如文獻[8-13]等是通過將算法移植至Hadoop得到高計算性能的算法。

本文將協(xié)同過濾推薦算法與開源分布式平臺Hadoop結(jié)合，研究協(xié)同過濾推薦算法的并行化，探索其MapReduce過程設計，比較單節(jié)點計算與多節(jié)點計算在計算效率上的差別，證明并行化后的算法在計算效率上的優(yōu)勢，其更能適應大數(shù)據(jù)環(huán)境。我們將并行化的CF算法簡稱為PCF（CF in Parallel）。

1 CF算法及Hadoop平臺概述

1.1 CF算法概述

協(xié)同過濾技術(shù)的思想簡單易懂，利用群體的觀點為個人進行推薦，比如，日常生活中我們經(jīng)常會參照身邊朋友的意見或行為，購買一些商品或作出某種選擇。在協(xié)同過濾技術(shù)中，用戶之間是有聯(lián)系的，他們可以是朋友、鄰居，根據(jù)趣味相投原則，鄰居用戶的喜好是一致或相近的，所以，對于當前用戶為其推薦鄰居的偏好項目。CF技術(shù)通過所有用戶的偏好、評分信息，經(jīng)過用戶相似度的度量，找到特定用戶的鄰居集合，根據(jù)最近鄰的興趣信息，為其作出項目推薦。

協(xié)同過濾推薦算法一般步驟為：構(gòu)建用戶-項目評分矩陣，據(jù)此計算用戶或項目相似度，進而計算預測評分、取前N個預測評分高的項目產(chǎn)生推薦集。以user-based算法為例，具體如下[14]。

⑴ 構(gòu)建評分矩陣。如表1所示。

⑵ 以用戶的相似度為計算目標，尋找鄰居用戶。余弦相似性、修正的余弦相似性、Pearson系數(shù)相關(guān)為三種常見的相似度計算方法。

其中Pearson系數(shù)相關(guān)計算兩用戶的相似度sim（i，j），用戶i與用戶j共同評分的項目集合為Iij，用戶i已作出評分的均值為。

⑴

⑶ 生成推薦。

① 計算預測值。

平均加權(quán)策略：用戶i對項目c的預測評分值：

⑵

② Top-N形式的推薦集。

計算鄰居集中的用戶i對各項目的加權(quán)評分平均值，Top-N推薦集取前N個且不屬于Ii（用戶i評分的項目集合）的項。

1.2 存在問題

1.2.1 矩陣稀疏問題

協(xié)同過濾是目前個性化推薦應用中的主流技術(shù)，然而隨著大數(shù)據(jù)時代的到來，系統(tǒng)內(nèi)的項目不斷增多，用戶規(guī)模日漸壯大，用戶不可能對每個或大多數(shù)項目都做出評價。當用戶或項目數(shù)量增大速度遠遠大于用戶對項目的評分速度時，就導致數(shù)據(jù)量雖然增大，CF技術(shù)所依賴的評分矩陣卻越來越稀疏，激化了該技術(shù)中一直存在的數(shù)據(jù)稀疏性問題，導致鄰居用戶或項目的計算準確性降低，對評分的預測出現(xiàn)偏差，影響推薦效果。針對稀疏性問題，目前主要的改進方向是矩陣填充或降維技術(shù)。

1.2.2 冷啟動問題

處于信息化時代，人們與互聯(lián)網(wǎng)的接觸越來越頻繁，越來越多的新用戶或新項目加入進來：新用戶無歷史行為信息，無法尋找到鄰居以獲得個性化服務；新項目評分信息較少甚至沒有，故無法尋找到鄰居以得到推薦。這是CF技術(shù)中的冷啟動問題，前者是用戶冷啟動，后者是項目冷啟動。冷啟動問題也可以理解成數(shù)據(jù)稀疏性的極端情況。針對該問題，目前主要是借鑒CBF的思想，結(jié)合用戶或項目本身的屬性信息完成推薦，緩解冷啟動[1]。

1.2.3 可擴展問題

一個好的推薦系統(tǒng)不僅僅預測的準確度要高，同樣重要的還有實時性。系統(tǒng)運算速度與評分矩陣的大小緊密關(guān)聯(lián)，而用戶規(guī)模和項目規(guī)模決定了矩陣的規(guī)模。面對急速增長的用戶量和項目量，協(xié)同過濾技術(shù)中可擴展問題的重要性日漸突出。針對該問題，目前的研究一方面是利用聚類技術(shù)，通過概率計算或設定閾值，在確保能夠盡量多地找到目標用戶或項目的鄰居前提下，將搜索空間縮至最小，以提高計算速度，緩解CF中的可擴展問題[15]；另一方面，跳出單機的局限，采用多核計算或云計算并行化方法，相對多核方式的核數(shù)有限、高實現(xiàn)成本，云計算的優(yōu)勢凸顯，越來越多的研究與應用采用該方法解決推薦領域的高準確度和低計算效率的矛盾。

1.3 Hadoop簡介

Hadoop起源于Apache公司的Lucene和Nutch項目[16]，是谷歌云計算理論的Java語言實現(xiàn)。其中并行計算模型MapReduce是Hadoop中最核心的部分，它是一種可靠、高效的并行編程模型和計算框架，借助于HDFS等分布式技術(shù)，能夠處理各類PB數(shù)量級的大數(shù)據(jù)[17]，其構(gòu)成部分主要有一個主控服務JobTracker，若干個從服務TaskTracker，分布式文件系統(tǒng)HDFS，以及客戶端Client[18]。MapReduce通過分解任務、合并結(jié)果的分而治之思想，實現(xiàn)可分解、可并行處理大數(shù)據(jù)集上的并行計算。MapReduce的任務執(zhí)行過程由Map和Reduce兩階段構(gòu)成，每次Map和Reduce的輸入和輸出均是鍵值對的形式，通過對相同key鍵值對的若干次歸類整理，調(diào)用用戶自定義的Map和Reduce函數(shù)，得到最終輸出結(jié)果。

2 基于MapReduce的CF算法分析

利用MapReduce并行計算模型實現(xiàn)CF算法的并行化，從原始的用戶-評分矩陣計算出推薦結(jié)果，需要多個MapReduce過程，本章節(jié)具體分析。

2.1 用戶相似度的計算

根據(jù)公式⑴，分析得用戶相似度計算的MapReduce過程如圖1，共包含三個MapReduce過程，每個過程都可并行運行。

輸入：評分矩陣，當前用戶id。

輸出：當前用戶與其他用戶的相似度值。

最后，當目標用戶需要推薦時，根據(jù)預測分值排序，返回TOP-N推薦集。至此，推薦完成。

在所有階段的MapReduce過程設計沒有改變算法的數(shù)學計算關(guān)系，所以對算法的計算結(jié)果沒有影響，在Hadoop平臺上運行與非并行模式下運行的推薦結(jié)果是一樣的，但是，并行模式Hadoop下的算法，有高效的大數(shù)據(jù)集計算能力，可擴展性較高。

3 PCF算法的實現(xiàn)及實驗分析

3.1 實驗設計

實驗的Hadoop平臺使用6臺PC機，搭建完全分布式環(huán)境。其中1臺部署namenode和jobtracker，另5臺部署datanode和tasktracker。集群配置如表4所示。

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

根據(jù)實驗結(jié)果，繪制加速比曲線圖，如圖3所示。

隨著節(jié)點數(shù)量的增加，加速比呈總體增長趨勢，體現(xiàn)了良好的可擴展性。但當節(jié)點數(shù)增加到一定數(shù)量時，加速比趨于穩(wěn)定。

4 結(jié)束語

本文介紹了CF算法，Hadoop云平臺概況，為了實現(xiàn)高效的推薦算法，以user-based CF為例，分析了其在MapReduce并行編程上的過程設計，即PCF算法，并在開源云計算平臺Hadoop上實現(xiàn)。通過變化集群節(jié)點數(shù)目和數(shù)據(jù)集規(guī)模大小，對加速比進行評估，實現(xiàn)較高計算效率的推薦。然而，一方面由于實驗條件的限制，搭建的集群規(guī)模有限；另一方面，是對Hadoop平臺的直接應用。下一步可以結(jié)合Hadoop中任務調(diào)度等方面的性能優(yōu)化，進一步提高計算能力，以適應不斷壯大的大數(shù)據(jù)。

參考文獻（References）：

[1] 李樹青.個性化信息檢索技術(shù)綜述[J].情報理論與實踐，2009.32（5）：107-113

[2] Liu Z B，Qu W Y，Li H T，et al. A Hybrid CollaborativeFiltering Recommendation Mechanism for P2P Networks[J]. Future Genera-tion Computer Systems，2010，26（8）：1409-1417

[3] Nature.Big Data[EB/OL].[2012-10-02].http：//www.nature.com/news/specials/bigdata/index.html

[4] Bryant R E，Katz R H，Lazowska E D.Big-Data computing：Creating revolutionary breakthroughs in commerce，science， and society[R]. [2012-10-02].http：//www.cra.org/ccc/docs/init/Big_Data.pdf

[5] Science.Special online collection：Dealing with data[EB/

OL]. [2012-10-02]. http：//www.Sciencemag.org/sites/special/data/，2011.

[6] Manyika J，Chui M，Brown B，et al.Big data：The next frontier for innovation，competition，and productivity[R/OL].[2012-10-22].http：//www.mckinsey.com/Insights/MGI/Research/Technology_and_Innovation/Big_data_

The_next_frontier_for_innovation

[7] Big Data Across the Federal Government[EB/OL].[2012-102].http：//www.whitehouse.gov/sites/default/files/microsites/ostp/big_data_fact_sheet_final_1.pdf.

[8] 肖強，朱慶華，鄭華，吳克文.Hadoop環(huán)境下的分布式協(xié)同過濾算法設計與實現(xiàn)[J].現(xiàn)代圖書情報技術(shù)，2013.1：83-89

[9] 程苗，陳華平.基于Hadoop的Web日志挖掘[J]計算機工程，2011.37（11）：37-39

[10] 張明輝.基于Hadoop的數(shù)據(jù)挖掘算法的分析與研究[D].昆明理工大學，2012.

[11] 李改，潘嶸，李章鳳，李磊.基于大數(shù)據(jù)集的協(xié)同過濾算法的并行化研究[J].計算機工程與設計，2012.33（6）：2437-2441

[12] 周源.基于云計算的推薦算法研究[D].電子科技大學，2012.

[13] 金龑.協(xié)同過濾算法及其并行化研究[D].南京大學，2012.

[14] 葉錫君，曹萍.ASUCF：基于平均相似度的協(xié)同過濾推薦算法[J].計算機工程與設計，2014.35（12）：4217-4222

[15] 黃正.面向數(shù)據(jù)稀疏的協(xié)同過濾推薦算法研究與優(yōu)化[D].華南理工大學，2012：25-29

[16] 陸嘉恒.Hadoop實戰(zhàn)[M].機械工業(yè)出版社，2011.

[17] 陳全，鄧倩妮.云計算及其關(guān)鍵技術(shù)[J].計算機應用，2009.29（9）：2562-2567

[18] Tom.White著.周敏奇，王曉玲，金澈清，錢衛(wèi)寧譯.Hadoop：權(quán)威指南[M].清華大學出版社，2011.