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

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

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

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

1 CF算法及Hadoop平臺(tái)概述

1.1 CF算法概述

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

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

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

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

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

⑴

⑶ 生成推薦。

① 計(jì)算預(yù)測(cè)值。

平均加權(quán)策略：用戶i對(duì)項(xiàng)目c的預(yù)測(cè)評(píng)分值：

⑵

② Top-N形式的推薦集。

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

1.2 存在問(wèn)題

1.2.1 矩陣稀疏問(wèn)題

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

1.2.2 冷啟動(dòng)問(wèn)題

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

1.2.3 可擴(kuò)展問(wèn)題

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

1.3 Hadoop簡(jiǎn)介

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

2 基于MapReduce的CF算法分析

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

2.1 用戶相似度的計(jì)算

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

輸入：評(píng)分矩陣，當(dāng)前用戶id。

輸出：當(dāng)前用戶與其他用戶的相似度值。

最后，當(dāng)目標(biāo)用戶需要推薦時(shí)，根據(jù)預(yù)測(cè)分值排序，返回TOP-N推薦集。至此，推薦完成。

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

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

3.1 實(shí)驗(yàn)設(shè)計(jì)

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

3.2 實(shí)驗(yàn)結(jié)果與分析

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

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

4 結(jié)束語(yǔ)

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

參考文獻(xiàn)（References）：

[1] 李樹(shù)青.個(gè)性化信息檢索技術(shù)綜述[J].情報(bào)理論與實(shí)踐，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] 肖強(qiáng)，朱慶華，鄭華，吳克文.Hadoop環(huán)境下的分布式協(xié)同過(guò)濾算法設(shè)計(jì)與實(shí)現(xiàn)[J].現(xiàn)代圖書(shū)情報(bào)技術(shù)，2013.1：83-89

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

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

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

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

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

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

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

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

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

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