基于Spark的推薦系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)

李 星，李 濤

(南京郵電大學(xué) 通信與信息工程學(xué)院，江蘇 南京 210003)

0 引 言

在當(dāng)今大數(shù)據(jù)時(shí)代[1]背景下，處在互聯(lián)網(wǎng)浪潮之中的人們能夠以前所未有的方式獲得更多、更全、更豐富的信息。當(dāng)前逐步從信息匱乏的階段慢慢過渡到信息爆炸的階段，從而進(jìn)入到一個(gè)信息過載的時(shí)代，人們?cè)谙硎茇S富信息福利的同時(shí)，也經(jīng)常陷入到數(shù)據(jù)的海洋中無所適從。信息過濾是人們必須要面對(duì)的問題，而推薦系統(tǒng)一直發(fā)揮著至關(guān)重要的作用。推薦系統(tǒng)不僅可以使用戶更方便快捷地發(fā)現(xiàn)切合自身需求的有用信息，而且能夠保證信息更加準(zhǔn)確地推送給潛在用戶，達(dá)到企業(yè)與消費(fèi)者的共贏[2]。在推薦系統(tǒng)中影響其性能高低最重要的因素就是其推薦算法的效率，而推薦系統(tǒng)中最為經(jīng)典的算法就是協(xié)同過濾算法[3]，該算法是基于用戶-物品行為歷史數(shù)據(jù)集，利用其中的相似性計(jì)算或者用戶興趣模型訓(xùn)練的辦法進(jìn)行過濾推薦。

在信息泛濫的互聯(lián)網(wǎng)世界中，不僅需要過濾海量數(shù)據(jù)，而且要力求在最短時(shí)間內(nèi)響應(yīng)用戶的需求，推薦系統(tǒng)必然要具備大數(shù)據(jù)處理能力。目前這一領(lǐng)域的框架有很多，其中Spark作為主流的內(nèi)存計(jì)算框架，具有很強(qiáng)的大數(shù)據(jù)處理能力，運(yùn)行于Spark平臺(tái)[4]的推薦系統(tǒng)有望獲得極高的運(yùn)行效率和處理能力。文中即是基于Spark分布式計(jì)算框架進(jìn)行推薦系統(tǒng)的研究和實(shí)現(xiàn)。

1 Spark平臺(tái)

1.1 Spark簡介

Spark是一個(gè)通用的大規(guī)模數(shù)據(jù)快速處理引擎[5]，是美國加州大學(xué)伯克利分校AMPLab于2010年開發(fā)的大數(shù)據(jù)計(jì)算平臺(tái)。不同于Hadoop MapReduce[6]，Spark Job計(jì)算的中間輸出結(jié)果可以直接緩存在內(nèi)存當(dāng)中，不再像MapReduce那樣頻繁讀寫本地磁盤?；谝陨咸攸c(diǎn)，Spark在分布式迭代運(yùn)算方面的速度要遠(yuǎn)遠(yuǎn)優(yōu)于經(jīng)典的Hadoop MapReduce框架。

AMPLab還基于Spark Core開發(fā)了大數(shù)據(jù)處理一體化的技術(shù)生態(tài)系統(tǒng)BDAS(the Berkeley data analytics stack)，即伯克利數(shù)據(jù)分析軟件棧。除了基礎(chǔ)的Spark計(jì)算框架，它還具有更高層級(jí)的計(jì)算能力[7]，主要包括Spark Streaming流處理框架、SparkSQL結(jié)構(gòu)化數(shù)據(jù)的查詢及分析的查詢引擎、GraphX圖計(jì)算框架和MLlib機(jī)器學(xué)習(xí)庫等等。恰是因?yàn)樯鲜鲎禹?xiàng)目的存在，使得Spark能夠提供更全面靈活的計(jì)算能力。

1.2 Spark設(shè)計(jì)思想

Spark對(duì)數(shù)據(jù)的核心抽象是彈性分布式數(shù)據(jù)集(resilient distributed datasets，RDD[8])，其實(shí)就是分布式的元素集合。有別于普通的數(shù)據(jù)集，RDD中的數(shù)據(jù)是分區(qū)存儲(chǔ)的，以達(dá)到數(shù)據(jù)的并行處理。因此，Spark處理數(shù)據(jù)的過程即是通過需處理的數(shù)據(jù)創(chuàng)建RDD，然后對(duì)RDD進(jìn)行相應(yīng)的Transformation和Action操作并最終得到運(yùn)算結(jié)果。RDD通常緩存在內(nèi)存中，父RDD的輸出結(jié)果可以在內(nèi)存中直接作為子RDD的輸入，迭代計(jì)算的效率因此大大提高。使用Spark編程無需關(guān)注底層的數(shù)據(jù)切分和存儲(chǔ)過程以及計(jì)算過程的容錯(cuò)機(jī)制，只需集中于業(yè)務(wù)邏輯處理，提高了編程效率。

1.3 Spark的運(yùn)行架構(gòu)

在Spark集群部署后，Master進(jìn)程和Worker進(jìn)程分別在主節(jié)點(diǎn)和從節(jié)點(diǎn)啟動(dòng)運(yùn)行。在Spark應(yīng)用程序的執(zhí)行過程中[9]，每個(gè)Spark應(yīng)用都由一個(gè)Driver程序來負(fù)責(zé)作業(yè)的調(diào)度，即分發(fā)Task任務(wù)，而Worker負(fù)責(zé)監(jiān)控本節(jié)點(diǎn)的資源狀況以及創(chuàng)建Executor進(jìn)程。在執(zhí)行階段，Driver程序會(huì)將Task和Task所依賴的數(shù)據(jù)文件和程序jar包等分發(fā)給對(duì)應(yīng)的Worker節(jié)點(diǎn)，同時(shí)Executor進(jìn)程對(duì)分區(qū)RDD進(jìn)行運(yùn)算處理。

Spark工作的流程如圖1所示。用戶首先向Spark集群提交應(yīng)用程序，Master進(jìn)程會(huì)在一個(gè)Worker節(jié)點(diǎn)上啟動(dòng)Driver程序來進(jìn)行任務(wù)管理，Driver根據(jù)任務(wù)情況向Master申請(qǐng)到資源(CPU、內(nèi)存等)，并初始化Executor。然后SparkContext中的DAGScheduler會(huì)將任務(wù)生成有向無環(huán)圖(DAG)并提交給TaskScheduler，TaskScheduler再根據(jù)DAG生成相應(yīng)的TaskSet并分配任務(wù)給Executor并發(fā)執(zhí)行。

圖1 Spark工作流程

1.4 環(huán)境說明

文中搭建的Spark集群[10]采用了實(shí)驗(yàn)室中的四臺(tái)普通計(jì)算機(jī)，組成了一個(gè)Master主節(jié)點(diǎn)和三個(gè)Slave節(jié)點(diǎn)的運(yùn)行環(huán)境，節(jié)點(diǎn)均采用Centos6.5 Linux系統(tǒng)，節(jié)點(diǎn)之間使用局域網(wǎng)進(jìn)行網(wǎng)絡(luò)連接，同時(shí)以上節(jié)點(diǎn)還運(yùn)行了分布式文件存儲(chǔ)系統(tǒng)HDFS的服務(wù)。具體情況如表1所示。

表1 節(jié)點(diǎn)具體說明

1.5 軟件安裝

本系統(tǒng)Java JDK的安裝包采用jdk-7u79-linux-x64.tar.gz，Scala的安裝包采用scala-sdk-2.10.4.tar.gz，Hadoop安裝包采用hadoop-2.5.0-cdh5.3.6.tar.gz，在系統(tǒng)軟件安裝過程中最重要的一點(diǎn)就是要配置安全外殼協(xié)議(SSH)以便實(shí)現(xiàn)遠(yuǎn)程無密碼登陸與管理。在完成Hadoop集群的配置安裝后，在此基礎(chǔ)上進(jìn)行Spark的安裝，Spark安裝包采用Spark 1.5.1.tar.gz，軟件開發(fā)環(huán)境采用IntelliJIDEA 2017.2.1。集群所有軟件在安裝并配置完畢后即可啟動(dòng)Spark分布式集群進(jìn)行測試。

2 推薦系統(tǒng)

2.1 推薦系統(tǒng)概述

如今推薦系統(tǒng)已經(jīng)普遍應(yīng)用于電商、新聞、地理位置等諸多領(lǐng)域。比如在電商領(lǐng)域，推薦系統(tǒng)實(shí)現(xiàn)的功能就是根據(jù)已有信息，如物品信息、用戶信息、用戶行為信息等，將相應(yīng)的物品推薦給用戶。常見的推薦任務(wù)主要有兩種；評(píng)分預(yù)測和Top-N推薦。對(duì)于用戶U，評(píng)分預(yù)測的任務(wù)是預(yù)測U對(duì)某物品可能的打分，而Top-N推薦則是為用戶U推薦N個(gè)他可能感興趣的物品。這兩種推薦都是依據(jù)用戶、物品自身的信息及用戶過去的行為記錄做出的預(yù)測。

2.2 協(xié)同過濾算法

協(xié)同過濾(collaborative filtering，CF)算法的核心思想就是利用群體的智慧來進(jìn)行事物推薦。協(xié)同過濾按照參照物的不同主要分為基于用戶的協(xié)同過濾(user-based CF)和基于物品的協(xié)同過濾(item-based CF)[11]。user-based CF在推薦時(shí)首先根據(jù)行為記錄找到相似用戶(即人以群分)，然后根據(jù)相似用戶進(jìn)行推薦。item-based CF最初由Amazon提出并應(yīng)用，基于物品協(xié)同過濾算法不是計(jì)算用戶間的相似度，而是計(jì)算物品間的相似度(即物以類聚)，將與目的用戶偏好過的商品的相似商品作為候選推薦列表推薦給目的用戶。對(duì)于大型電子商務(wù)平臺(tái)而言，商品更新速率較慢并且商品的數(shù)目遠(yuǎn)小于用戶數(shù)目，計(jì)算物品相似度開銷遠(yuǎn)遠(yuǎn)比計(jì)算用戶相似度開銷小，因而item-based CF的穩(wěn)定性比user-based CF的穩(wěn)定性更高[12]。故該系統(tǒng)采用基于物品協(xié)同過濾的Top-N推薦。

2.3 基于物品協(xié)同過濾算法的基本思路

item-based CF的基本思路和流程如下：

(1)收集用戶的歷史行為數(shù)據(jù)，進(jìn)行初步的減噪和歸一化處理。統(tǒng)計(jì)得出物品-用戶評(píng)分矩陣，用以表示具體每件物品被哪些用戶評(píng)分過，該表其實(shí)是由用戶-物品評(píng)分表(如表2所示)轉(zhuǎn)置得到，而用戶-物品評(píng)分矩陣則是每位用戶對(duì)物品的歷史評(píng)分記錄。

表2 用戶-物品評(píng)分表

推薦系統(tǒng)中主要有顯式評(píng)分與隱式評(píng)分兩種評(píng)分方式。其中顯示評(píng)分指的是用戶對(duì)物品的評(píng)價(jià)直接用具體分?jǐn)?shù)來表示，比如平時(shí)比較常見的用戶對(duì)某種物品的喜好程度，可以由1至5分來量化；而隱式評(píng)分則只是依照用戶對(duì)于某種物品有沒有購買、是否瀏覽過、評(píng)論過等行為，如果有相關(guān)行為則評(píng)分為1，無則評(píng)分為0。于是，可以得到一個(gè)N×M矩陣R：

(1)

其中，N表示用戶數(shù)量；M表示物品數(shù)量；rij表示用戶ui對(duì)物品mj的評(píng)分。若用戶ui對(duì)物品mj進(jìn)行了評(píng)分，則rij≠0，否則rij=0。由于文中采用隱反饋方式，所以rij的取值只能是1或0。

(2)計(jì)算物品之間的相似度。

找到與物品最相似的N個(gè)物品集合，物品m和n的相似度可使用以下余弦相似度公式計(jì)算：

(2)

其中，N(m)表示所有擁有物品m的用戶集合；N(n)表示所有擁有物品n的用戶集合。使用相似度計(jì)算公式可計(jì)算出示例表2中物品m1、m2以及m1、m3的相似度：

(3)

(4)

由結(jié)果可知m1、m2間有更大的相似度，因此在一位新用戶購買m1時(shí)，可優(yōu)先將m2商品推薦給他。

在示例計(jì)算過程中可發(fā)現(xiàn)此方法實(shí)際上會(huì)對(duì)比物品空間中的所有物品，致使其時(shí)間復(fù)雜度較高，為O(n2)。然而一個(gè)大型數(shù)據(jù)集中，會(huì)出現(xiàn)很多物品并沒有共同用戶交集的情況，因此在實(shí)際操作中，建立用戶-物品倒排表可以優(yōu)化計(jì)算，如圖2所示。其中矩陣W'中的值為式2中分子的值。

圖2 用戶-物品倒排表生成過程

(3)計(jì)算出物品之間的相似度后，根據(jù)用戶的歷史物品表再計(jì)算出用戶-物品興趣度，以此進(jìn)行物品推薦。用戶u對(duì)物品m的興趣度為：

(5)

其中，interest(u,m)表示用戶u對(duì)物品m的興趣度；N(m,k)表示與物品n最相似的K件物品集合；N(u)表示用戶u現(xiàn)已擁有的物品集合；simmn表示物品m和物品n之間的相似度；run表示用戶u對(duì)物品n的興趣值(若只考慮隱式反饋數(shù)據(jù)，run為1)。

2.4 推薦系統(tǒng)評(píng)價(jià)指標(biāo)

一個(gè)推薦系統(tǒng)的性能好壞可以用以下評(píng)測指標(biāo)[13]來評(píng)定：

(1)準(zhǔn)確率(precision)。

準(zhǔn)確率是一個(gè)非常重要的性能指標(biāo)，直接關(guān)系到推薦系統(tǒng)服務(wù)質(zhì)量的好壞。若推薦系統(tǒng)向用戶u推薦了N件物品，推薦集合可記為R(u)，而用戶在測試集T上的喜好物品項(xiàng)集合記為T(u)，則準(zhǔn)確率計(jì)算公式如下：

(6)

準(zhǔn)確率指的是向用戶推薦的集合項(xiàng)R(u)中，有多少件物品屬于正確推薦，即推薦正確項(xiàng)占推薦列表的比例。

(2)召回率(recall)。

召回率指的是用戶喜好的集合項(xiàng)T(u)中，含有多少推薦系統(tǒng)正確推薦的物品，即推薦正確項(xiàng)占真實(shí)喜好列表的比例。召回率反映了推薦系統(tǒng)推薦項(xiàng)的覆蓋率，具體公式為：

(7)

(3)覆蓋率(recover)。

覆蓋率指的是推薦集合項(xiàng)R(u)在供應(yīng)商提供的物品總量中所占的比例[11]，具體公式為：

(8)

其中，U表示所有被推薦用戶；I表示供應(yīng)商提供的所有物品項(xiàng)。覆蓋率描述了推薦系統(tǒng)對(duì)物品長尾的發(fā)掘能力。

(4)均方根誤差(RMSE)。

(9)

依據(jù)準(zhǔn)確率和召回率公式定義可知，準(zhǔn)確率和召回率往往是兩個(gè)相互矛盾的指標(biāo)參數(shù)[14]。系統(tǒng)推薦并且用戶真實(shí)喜好的物品項(xiàng)集與系統(tǒng)推薦的物品項(xiàng)之間的比值越大，準(zhǔn)確率越大；系統(tǒng)推薦的物品項(xiàng)集中用戶真實(shí)喜歡的物品越多，召回率也越大。如果推薦系統(tǒng)推薦的物品很多，雖然召回率可能提高，準(zhǔn)確率也會(huì)有所下降；因此如果希望推薦系統(tǒng)更加準(zhǔn)確，推薦物品數(shù)量一定要適當(dāng)。

3 Spark平臺(tái)推薦算法并行化實(shí)現(xiàn)

3.1 基于物品的協(xié)同過濾推薦算法的Spark并行化實(shí)現(xiàn)流程

item-based CF算法的核心思想是對(duì)用戶推薦與其已喜歡物品相似的不同物品。其中比較關(guān)鍵的幾個(gè)參數(shù)及公式為用戶-歷史評(píng)分矩陣Rm，物品之間的相似度計(jì)算公式simmn及用戶對(duì)物品興趣度計(jì)算公式interest(u,m)。本系統(tǒng)以電影推薦為背景，測試數(shù)據(jù)集選取經(jīng)典的MovieLens[15]，該數(shù)據(jù)集記錄了用戶評(píng)分記錄。文中采用100萬條記錄作為實(shí)驗(yàn)數(shù)據(jù)集，將數(shù)據(jù)集文件下載并解壓后，其中的users.dat文件記錄所有用戶相關(guān)信息；movies.dat文件存儲(chǔ)的是電影自身信息，包括電影名、類型、年份等。ratings.dat文件記錄用戶-電影的評(píng)分信息及時(shí)間戳；每條評(píng)分記錄的格式為userid::itemid::rating::timestamp，前三項(xiàng)是需要的數(shù)據(jù)資源?；谖锲返膮f(xié)同過濾推薦算法具體流程如圖3所示。

圖3 基于Spark的商品協(xié)同過濾算法流程

輸入：userid、itemid、rating

輸出：用戶最感興趣的N個(gè)物品項(xiàng)

(1)計(jì)算用戶對(duì)物品的喜好：采用隱反饋數(shù)據(jù)原則對(duì)每個(gè)用戶給物品的評(píng)分進(jìn)行預(yù)處理操作。數(shù)據(jù)處理如下：用戶評(píng)分的物品記為1，反之記為0；

(2)統(tǒng)計(jì)每個(gè)物品數(shù)好評(píng)總數(shù)；可設(shè)置閾值，低于指定數(shù)的物品不參與后續(xù)計(jì)算；

(3)統(tǒng)計(jì)物品-好評(píng)鍵值對(duì)，對(duì)兩個(gè)相關(guān)聯(lián)的物品之間的共同用戶數(shù)進(jìn)行統(tǒng)計(jì)(也可設(shè)置閾值)；

(4)計(jì)算任意兩個(gè)有關(guān)聯(lián)物品的相似度；

(5)根據(jù)興趣度向用戶推薦N個(gè)最感興趣的物品。

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

系統(tǒng)基于Spark平臺(tái)推薦算法并行化實(shí)現(xiàn)，并測試計(jì)算推薦系統(tǒng)的相關(guān)評(píng)測指標(biāo)：準(zhǔn)確率、召回率、覆蓋率等。實(shí)驗(yàn)中訓(xùn)練集占數(shù)據(jù)量75%，測試集占25%。根據(jù)不同的參數(shù)設(shè)置，每個(gè)實(shí)驗(yàn)均進(jìn)行4次，并求得4次結(jié)果的平均值作為最終的測試結(jié)果[16]，如表3所示。

表3 基于物品協(xié)同過濾推薦算法在不同推薦列表長度(L值)時(shí)的性能 %

從表3可以看出，基于物品協(xié)同過濾推薦算法中的準(zhǔn)確率與召回率并不是和推薦列表長度呈線性關(guān)系，并且當(dāng)推薦列表長度為20時(shí)，系統(tǒng)的準(zhǔn)確率與召回率會(huì)比較高，由此可以看出，推薦列表長度的選擇是基于物品協(xié)同過濾推薦系統(tǒng)性能的重要影響因素。而對(duì)比覆蓋率可發(fā)現(xiàn)覆蓋率隨著L值的增長越來越低，是因?yàn)楫?dāng)推薦列表長度不斷增加時(shí)，推薦算法越來越傾向于推薦比較熱門的電影所致。

4 結(jié)束語

大數(shù)據(jù)時(shí)代互聯(lián)網(wǎng)中蘊(yùn)藏著海量富有價(jià)值的信息資源，如何更加快速有效地從中挖掘有用信息正是大數(shù)據(jù)應(yīng)用平臺(tái)需要考慮解決的問題。而用戶推薦這一應(yīng)用場景，正是從海量數(shù)據(jù)中挖掘有用信息的典型案例。研究表明，Spark計(jì)算框架相比傳統(tǒng)的MapReduce框架具有更強(qiáng)的并行計(jì)算能力。并且推薦算法中需要進(jìn)行連續(xù)迭代計(jì)算，這一需求也恰好使之非常適合運(yùn)行在Spark平臺(tái)之上。文中以設(shè)計(jì)并實(shí)現(xiàn)一個(gè)大數(shù)據(jù)環(huán)境下的推薦系統(tǒng)為主線，介紹了大數(shù)據(jù)相關(guān)技術(shù)和推薦系統(tǒng)的相關(guān)概念，實(shí)現(xiàn)了基于Spark的Item-CF推薦系統(tǒng)，并在數(shù)據(jù)集MovieLens下進(jìn)行了相關(guān)指標(biāo)的測評(píng)。結(jié)果顯示，該系統(tǒng)能夠較好地完成推薦任務(wù)，達(dá)到了設(shè)計(jì)前的預(yù)期。下一步的工作將針對(duì)電商平臺(tái)中日益多樣化的用戶行為，設(shè)計(jì)多種的數(shù)據(jù)處理方式，優(yōu)化推薦算法引擎，提升系統(tǒng)的通用性和可靠性。