李 星，李 濤

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

0 引 言

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

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

1 Spark平臺

1.1 Spark簡介

Spark是一個通用的大規(guī)模數(shù)據(jù)快速處理引擎[5]，是美國加州大學(xué)伯克利分校AMPLab于2010年開發(fā)的大數(shù)據(jù)計算平臺。不同于Hadoop MapReduce[6]，Spark Job計算的中間輸出結(jié)果可以直接緩存在內(nèi)存當(dāng)中，不再像MapReduce那樣頻繁讀寫本地磁盤?；谝陨咸攸c，Spark在分布式迭代運算方面的速度要遠遠優(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計算框架，它還具有更高層級的計算能力[7]，主要包括Spark Streaming流處理框架、SparkSQL結(jié)構(gòu)化數(shù)據(jù)的查詢及分析的查詢引擎、GraphX圖計算框架和MLlib機器學(xué)習(xí)庫等等。恰是因為上述子項目的存在，使得Spark能夠提供更全面靈活的計算能力。

1.2 Spark設(shè)計思想

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

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

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

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

圖1 Spark工作流程

1.4 環(huán)境說明

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

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

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)軟件安裝過程中最重要的一點就是要配置安全外殼協(xié)議(SSH)以便實現(xiàn)遠程無密碼登陸與管理。在完成Hadoop集群的配置安裝后，在此基礎(chǔ)上進行Spark的安裝，Spark安裝包采用Spark 1.5.1.tar.gz，軟件開發(fā)環(huán)境采用IntelliJIDEA 2017.2.1。集群所有軟件在安裝并配置完畢后即可啟動Spark分布式集群進行測試。

2 推薦系統(tǒng)

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

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

2.2 協(xié)同過濾算法

協(xié)同過濾(collaborative filtering，CF)算法的核心思想就是利用群體的智慧來進行事物推薦。協(xié)同過濾按照參照物的不同主要分為基于用戶的協(xié)同過濾(user-based CF)和基于物品的協(xié)同過濾(item-based CF)[11]。user-based CF在推薦時首先根據(jù)行為記錄找到相似用戶(即人以群分)，然后根據(jù)相似用戶進行推薦。item-based CF最初由Amazon提出并應(yīng)用，基于物品協(xié)同過濾算法不是計算用戶間的相似度，而是計算物品間的相似度(即物以類聚)，將與目的用戶偏好過的商品的相似商品作為候選推薦列表推薦給目的用戶。對于大型電子商務(wù)平臺而言，商品更新速率較慢并且商品的數(shù)目遠小于用戶數(shù)目，計算物品相似度開銷遠遠比計算用戶相似度開銷小，因而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ù)，進行初步的減噪和歸一化處理。統(tǒng)計得出物品-用戶評分矩陣，用以表示具體每件物品被哪些用戶評分過，該表其實是由用戶-物品評分表(如表2所示)轉(zhuǎn)置得到，而用戶-物品評分矩陣則是每位用戶對物品的歷史評分記錄。

表2 用戶-物品評分表

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

(1)

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

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

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

(2)

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

(3)

(4)

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

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

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

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

(5)

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

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

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

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

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

(6)

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

(2)召回率(recall)。

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

(7)

(3)覆蓋率(recover)。

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

(8)

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

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

(9)

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

3 Spark平臺推薦算法并行化實現(xiàn)

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

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

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

輸入：userid、itemid、rating

輸出：用戶最感興趣的N個物品項

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

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

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

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

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

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

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

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

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

4 結(jié)束語

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