基于Hadoop的協同過濾推薦并行化研究

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

關鍵詞： 協同過濾； 計算效率； 加速比； Hadoop； 大數據

中圖分類號：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 引言

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

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

1 CF算法及Hadoop平臺概述

1.1 CF算法概述

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

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

⑴ 構建評分矩陣。如表1所示。

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

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

⑴

⑶ 生成推薦。

① 計算預測值。

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

⑵

② Top-N形式的推薦集。

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

1.2 存在問題

1.2.1 矩陣稀疏問題

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

1.2.2 冷啟動問題

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

1.2.3 可擴展問題

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

1.3 Hadoop簡介

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

2 基于MapReduce的CF算法分析

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

2.1 用戶相似度的計算

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

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

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

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

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

3 PCF算法的實現及實驗分析

3.1 實驗設計

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

3.2 實驗結果與分析

根據實驗結果，繪制加速比曲線圖，如圖3所示。

隨著節點數量的增加，加速比呈總體增長趨勢，體現了良好的可擴展性。但當節點數增加到一定數量時，加速比趨于穩定。

4 結束語

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

參考文獻（References）：

[1] 李樹青.個性化信息檢索技術綜述[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環境下的分布式協同過濾算法設計與實現[J].現代圖書情報技術，2013.1：83-89

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

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

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

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

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

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

[15] 黃正.面向數據稀疏的協同過濾推薦算法研究與優化[D].華南理工大學，2012：25-29

[16] 陸嘉恒.Hadoop實戰[M].機械工業出版社，2011.

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

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