陳斌等

摘要：隨著Web技術(shù)的發(fā)展，互聯(lián)網(wǎng)用戶數(shù)量持續(xù)增長，快速為用戶生成精確推薦變得愈加困難。提出了項(xiàng)目協(xié)同過濾算法，采用余弦相似性計(jì)算項(xiàng)目間相似度并用加權(quán)平均值的方法為用戶生成推薦結(jié)果。在Apache Spark上構(gòu)建該系統(tǒng)，對(duì)抓取到的某電商商品數(shù)據(jù)進(jìn)行測(cè)試。實(shí)驗(yàn)結(jié)果表明，基于Spark的推薦系統(tǒng)可以顯著提高推薦生成的速度和有效性。

關(guān)鍵詞：Apache Spark；協(xié)同過濾；推薦系統(tǒng)

DOIDOI：10.11907/rjdk.143871

中圖分類號(hào)：TP319

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

0 引言

協(xié)同過濾推薦在信息過濾和信息系統(tǒng)中正迅速成為一項(xiàng)很受歡迎的技術(shù)。與傳統(tǒng)的基于內(nèi)容過濾進(jìn)行推薦不同，協(xié)同過濾分析用戶興趣，在用戶群中找到指定用戶的相似（興趣）用戶，綜合這些相似用戶對(duì)某一信息的評(píng)價(jià)，形成系統(tǒng)對(duì)該用戶的喜好程度預(yù)測(cè)。

Spark[1]是一個(gè)通用的并行計(jì)算框架，由UCBerkeley的AMP實(shí)驗(yàn)室開發(fā)，是MapReduce模型的實(shí)現(xiàn)之一，它提供的框架自動(dòng)執(zhí)行任務(wù)分解、發(fā)送、執(zhí)行、歸并、容錯(cuò)工作，免去了二次開發(fā)和定制專用的分布式調(diào)度系統(tǒng)。和Hadoop一樣，建立在HDFS基礎(chǔ)上，但它的Job中間輸出和結(jié)果可保存在內(nèi)存中，減少了硬盤I/O次數(shù)，因而可以有較高的速度，對(duì)迭代和多步驟運(yùn)算有更好的支持能力。鑒于此，很多機(jī)器學(xué)習(xí)相關(guān)工作者都在研究和使用它。本文在學(xué)習(xí)Spark基礎(chǔ)上，搭建了一個(gè)Spark平臺(tái)，并在其上設(shè)計(jì)實(shí)現(xiàn)了一個(gè)協(xié)同過濾系統(tǒng)。

1 協(xié)同過濾算法設(shè)計(jì)

協(xié)同過濾系統(tǒng)一般分為基于用戶的協(xié)同過濾、基于項(xiàng)目的協(xié)同過濾和基于模型的協(xié)同過濾[2]?；谟脩舻膮f(xié)同過濾假設(shè)：對(duì)同樣的項(xiàng)目，如果用戶間的評(píng)分結(jié)果較為相似，則他們對(duì)其它項(xiàng)目的評(píng)分也比較相似。此假設(shè)弊端是運(yùn)算量隨用戶量和項(xiàng)目數(shù)量的增長而急劇增長?；陧?xiàng)目的協(xié)同過濾系統(tǒng)則通過計(jì)算基本穩(wěn)定的項(xiàng)目間相似性作出推薦，意味著用戶的偏好由系統(tǒng)中的項(xiàng)目唯一確定，因而有更好的可擴(kuò)展性。

在一個(gè)典型的協(xié)同過濾場(chǎng)景中，有n個(gè)項(xiàng)目Ι={i1，i2，…，in}和k個(gè)用戶U={u1，u2，...，uk}，令Mk*n為基本用戶對(duì)各項(xiàng)目的偏好矩陣。其中，Mu，i表示用戶u對(duì)項(xiàng)目i的偏好，如評(píng)分，其值為實(shí)數(shù)或空，空表示當(dāng)前用戶尚未對(duì)項(xiàng)目作出評(píng)價(jià)。推薦系統(tǒng)的任務(wù)就是根據(jù)目標(biāo)用戶u∈U的評(píng)分歷史，預(yù)測(cè)出用戶最喜歡的項(xiàng)目。本文采用基于項(xiàng)目的協(xié)同過濾算法，使用余弦相似性計(jì)算項(xiàng)目間相似性，然后采用加權(quán)平均值的方法為用戶生成推薦結(jié)果。

1.1 相似性度量方法

本文主要采用余弦相似性度量方法[2]計(jì)算用戶間、項(xiàng)目間的相似性，這里以計(jì)算用戶間相似性為例，其計(jì)算方法可表示為：

sim（ux，uy）=∑i∈Cux，uyrux，iruy，i∑i∈Cux，uyrux，i2∑i∈Cux，uyruy，i2（1）

其中，Cux，uy表示用戶ux和uy共同評(píng)價(jià)過的項(xiàng)目i∈Ι的集，rux，i表示用戶ux對(duì)項(xiàng)目i的評(píng)分，ruy，i表示用戶uy對(duì)項(xiàng)目i的評(píng)分。相似性即兩向量ux，uy的夾角余弦值，因?yàn)橛脩粼u(píng)分均為正數(shù)，故相似性取值范圍為[0，1]。

1.2 加權(quán)平均值

在協(xié)同過濾算法中，計(jì)算出所有用戶間的相似度后，就可以采用一種方法為給定的用戶u∈U，預(yù)測(cè)出用戶對(duì)所有尚未評(píng)價(jià)項(xiàng)目的評(píng)分。這里介紹一種最為簡單、常用并且效果良好的方法：加權(quán)求和，表示為：pux，i=ux+∑uy∈Nux（ruy，i-uy）*sim（ux，uy）∑uy∈Nuxsim（ux，uy）（2）

其中，Nux 表示用戶ux的鄰居，sim（ux，uy）表示用戶ux和uy的相似度。

2 推薦系統(tǒng)部署與設(shè)計(jì)

由于推薦系統(tǒng)的高度計(jì)算密集性，將推薦系統(tǒng)部署到單臺(tái)機(jī)器上會(huì)有很大的限制，例如，CPU運(yùn)算速度、內(nèi)存大小和硬盤I/O能力等，更為重要的是如果此計(jì)算機(jī)發(fā)生故障，將面臨數(shù)據(jù)丟失的風(fēng)險(xiǎn)。使用分布式計(jì)算環(huán)境可以大大緩解此類問題，如可在分布式運(yùn)算框架Hadoop/MapReduce下實(shí)現(xiàn)推薦系統(tǒng)[4-6]。Spark是一個(gè)開源的Hadoop/MapReduce并行計(jì)算框架，本文在Spark平臺(tái)上構(gòu)建一個(gè)協(xié)同過濾系統(tǒng)。

2.1 軟硬件配置

實(shí)驗(yàn)平臺(tái)硬件采用Intel Core i5雙核的普通PC，網(wǎng)絡(luò)帶寬為100Mbps，為提高虛擬機(jī)I/O速度，采用1條4G和1條8G DRR1333內(nèi)存條，并搭載128GSanDisk固態(tài)硬盤。主機(jī)采用Windows 8.1 x64位系統(tǒng)，虛擬機(jī)采用開源的Oracle VM VirtualBox 4.3，虛擬主機(jī)系統(tǒng)采用開源的Linux/CentOS6.5，具體如表1所示。

2.2 網(wǎng)絡(luò)規(guī)劃

在VirtualBox中建立HostOnly網(wǎng)絡(luò)，虛擬主機(jī)規(guī)劃如下：（master/worker，169.254.80.3）；（Worker1，169.254.80.4）；（Worker2，169.254.80.5）。

2.3 SSH通信配置

SSH通信協(xié)議（Secure Shell）[7]是集群中各個(gè)節(jié)點(diǎn)通信所采用的協(xié)議，主節(jié)點(diǎn)可以通過SSH啟動(dòng)或關(guān)閉集群中節(jié)點(diǎn)。在配置SSH之前，需要保證各節(jié)點(diǎn)能相互通信。在各節(jié)點(diǎn)的終端中通過sshkeygen命令生成公私鑰，將各節(jié)點(diǎn)的公鑰內(nèi)容寫入authorized_keys文件中，并發(fā)布到各節(jié)點(diǎn)的～${USER}/.ssh目錄下，權(quán)限為600。

2.4 Java環(huán)境安裝

從官網(wǎng)下載安裝包文件，使用rpmi jdk.rpm命令安裝，之后編輯～user/.bash_profile文件，添加JAVA_HOME環(huán)境變量為jdk安裝目錄，添加$JAVA_HOME/bin到Path變量。

2.5 Spark安裝配置

首先需要配置Hadoop。從官網(wǎng)下載合適版本的Hadoop，安裝后修改配置文件：conf/coresite.xml， conf/hdfssite.xml， conf/yarnsite.xml和conf/mapredsite.xml，并添加對(duì)應(yīng)的環(huán)境變量，具體參考官網(wǎng)對(duì)應(yīng)版本配置介紹。然后從官網(wǎng)下載Hadoop版本編譯過的Spark程序并安裝。配置Spark最為簡單的方式就是以獨(dú)立方式部署。成功部署并啟動(dòng)后，Spark會(huì)運(yùn)行master服務(wù)器和worker服務(wù)器，注意：所有節(jié)點(diǎn)必須從master節(jié)點(diǎn)啟動(dòng)。然后將worker節(jié)點(diǎn)信息添加到master節(jié)點(diǎn)中的conf/slaves文件中，具體請(qǐng)參考官網(wǎng)文檔。本文中配置如下：

SPARK_MEM=2g #指定單個(gè)worker節(jié)點(diǎn)所使用的內(nèi)存值

SPARK_JAVA_OPTS=”Dspark.storage.memoryFraction=0.4 Xmx3g” #第1個(gè)參數(shù)：可用來作為cache的內(nèi)存比例，剩余內(nèi)存用來滿足任務(wù)運(yùn)行內(nèi)存空間的需要；第2個(gè)參數(shù)：設(shè)定jvm最大可用內(nèi)存為3G。

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

3.1 性能評(píng)估

為了驗(yàn)證基于Spark分布式平臺(tái)對(duì)協(xié)同過濾推薦引擎的執(zhí)行性能，我們從單節(jié)點(diǎn)到多節(jié)點(diǎn)進(jìn)行實(shí)驗(yàn)。實(shí)驗(yàn)數(shù)據(jù)由10W用戶和3900個(gè)商品構(gòu)成的69W條記錄構(gòu)成，使用隨機(jī)抽樣將數(shù)據(jù)分為測(cè)試數(shù)據(jù)和訓(xùn)練數(shù)據(jù)兩部分，比例為1∶9。采用Top20方法實(shí)驗(yàn)，最近鄰居個(gè)數(shù)為50個(gè)。

圖1 不同節(jié)點(diǎn)數(shù)推薦計(jì)算時(shí)間

圖1顯示執(zhí)行時(shí)間開始隨節(jié)點(diǎn)增加而減少，但是當(dāng)節(jié)點(diǎn)增加為3個(gè)時(shí)，加速效果則不明顯。我們認(rèn)為是CPU瓶頸，因所采用CPU為雙核酷睿i5型號(hào)；另外，根據(jù)Amdahl定律，并行化的程序所獲得的加速比，與程序中可并行執(zhí)行代碼所占比例有直接關(guān)系，所以加速效果并不是線性增長的。

3.2 推薦質(zhì)量評(píng)估

推薦質(zhì)量評(píng)估一般采用平均絕對(duì)誤差MAE（mean absolute error）方法，MAE越小則推薦質(zhì)量越高[8]，MAE計(jì)算公式可表示為：

MAE=∑a∈URa，i-Pa，iN（3）

其中，N表示總推薦個(gè)數(shù)，Ra，i表示用戶a對(duì)項(xiàng)目i的實(shí)際評(píng)分，Pa，i表示系統(tǒng)預(yù)測(cè)用戶a對(duì)項(xiàng)目i的評(píng)分。

采用余弦相似度方法，通過修改不同個(gè)數(shù)的最近鄰居，得出相應(yīng)的MAE，結(jié)果如圖2所示。

從圖2可以看出，MAE整體隨鄰居個(gè)數(shù)增加而降低，但其下降速度逐漸降低，即過多增加最近鄰居個(gè)數(shù)對(duì)推薦質(zhì)量的提高貢獻(xiàn)有限，反而消耗了更多的計(jì)算資源，因而需要在計(jì)算資源和推薦質(zhì)量之間取一個(gè)折衷值。

圖2 不同鄰居個(gè)數(shù)的MAE值

4 結(jié)語

本文首先給出一種協(xié)同過濾推薦算法的設(shè)計(jì)和實(shí)現(xiàn)方法，然后介紹了Apache Spark框架以及本文實(shí)驗(yàn)環(huán)境搭建過程，并進(jìn)行了算法實(shí)驗(yàn)。由于本文所采用設(shè)備性能的限制，未能進(jìn)行較大數(shù)據(jù)集的實(shí)驗(yàn)測(cè)試。在接下來的工作中，應(yīng)繼續(xù)研究如何對(duì)Spark進(jìn)行優(yōu)化，并研究較為適合的應(yīng)用場(chǎng)景。