基于Spark Streaming的增量協(xié)同過濾算法

曾志武 蔡明

摘 要：針對協(xié)同過濾算法處理大數(shù)據(jù)流時響應慢的缺陷，在改善推薦準確度的情況下，提出增量更新算法以加快響應速度，提高推薦系統(tǒng)性能。介紹了當前協(xié)同過濾算法以及KNN和Spark的相關知識，闡述了協(xié)同過濾算法的增量模型。采用Group Lens網站提供的Movie Lens數(shù)據(jù)集作為實驗數(shù)據(jù)，應用Socket模擬流和Spark并行計算技術實現(xiàn)增量模型。實驗結果顯示，在保證推薦準確度的前提下，響應時間明顯縮短，說明增量模型適合實時處理大數(shù)據(jù)流，可緩解數(shù)據(jù)處理不及時問題。

關鍵詞：協(xié)同過濾；推薦系統(tǒng)；增量計算；實時流計算；Spark Streaming

DOI：10.11907/rjdk.173047

中圖分類號：TP312

文獻標識碼：A 文章編號：1672-7800（2018）006-0088-04

Abstract：Because of the slow response of collaborative filtering algorithm in dealing with large data streams， this paper presents an incremental updating algorithm to speed up the response times and improve the recommendation system performance under the condition of guaranteeing the accuracy of recommendation. Firstly， this paper presents the background and purpose of the study， and then introduces the current collaborative filtering algorithm and its related knowledge of KNN and Spark. Secondly， the incremental model of collaborative filtering algorithm is proposed . Finally， we used Movie Lens dataset provided by Group Lens website was used as the experimental data source， with Spark Stream to receive stream data from Socket and Spark to parallel computing increment data . The experimental results showed that in the case of reliable recommendation accuracy， response times is significantly improved and it proves that the incremental model proposed in this paper is very suitable for real-time processing of large data stream to alleviate the problem of no timely processing data.

Key Words：collaborative filtering； recommender system； incremental computing； real-time stream computing； Spark streaming

0 引言

在大數(shù)據(jù)流環(huán)境下，各大電子商務網站都希望及時捕獲、分析處理用戶的偏好信息，及時響應用戶的興趣變化，給用戶推薦喜歡的商品。以前一般是進行批量或小批量的全量分析，這樣響應時間明顯滯后于用戶喜好的變化。目前推薦系統(tǒng)算法一般分為基于內容的推薦算法[1]、協(xié)同過濾推薦算法[2]以及混合推薦算法[3]3類，其中協(xié)同過濾推薦算法提出最早、應用范圍最廣。因此，本文針對該算法進行改進，在保證推薦準確度的前提下提出增量模型，解決推薦延遲或響應慢的問題。

1 協(xié)同過濾算法與實時流計算

1.1 協(xié)同過濾算法

協(xié)同過濾算法一般分為基于內存的協(xié)同過濾和基于模型的協(xié)同過濾?；趦却娴膮f(xié)同過濾比較簡單、高效，但遇到大規(guī)模數(shù)據(jù)時難以擴展、響應時間相對滯后?；谀Ｐ偷膮f(xié)同過濾運用機器學習算法離線訓練數(shù)據(jù)獲得適當?shù)哪Ｐ?，然后應用到實際場景中，這樣不能及時反映用戶喜好的變化?；趦却娴膮f(xié)同過濾分為基于用戶的協(xié)同過濾和基于項目的協(xié)同過濾，基于用戶的協(xié)同過濾一般應用在用戶偏好經常變化的場景，比如新聞視頻等網站，而基于項目的協(xié)同過濾一般應用在物品數(shù)量變化相對較少的情況，比如購物網站?；谀Ｐ偷膮f(xié)同過濾有基于矩陣分解的協(xié)同過濾[4]以及基于神經網絡的協(xié)同過濾[5]等，本文主要研究基于項目的協(xié)同過濾，以改善推薦精度和響應時間，提高系統(tǒng)可擴展性。

基于項目協(xié)同過濾算法流程如圖1所示。

首先形成用戶項目評分矩陣，然后計算相似度矩陣，接著從相似度矩陣獲取K個相似近鄰，然后基于K近鄰集預測用戶未評分項目的分數(shù)，最后對未評分項目進行排序，推薦前N個物品給用戶。

目前項目相似度計算方法有余弦相似度、修改的余弦相似度以及Pearson相似度，其中Pearson相似度比較常見，如式（1）所示。

相似度計算在整個推薦流程中至關重要，本文選用文獻[6]提出的規(guī)范化Dice系數(shù)（Generalized Dice Coefficient）計算項目間的GDC相似度，該方法是Pearson相似度計算公式的改進，如式（2）所示。

利用KNN最近鄰模型[7-8]（k-NearestNeighbor）獲取與用戶最相似的K個用戶。為保證推薦精度，將K的取值與項目評分個數(shù)相關，如式（3）所示。

最后，依次計算用戶未評分項，并排序選擇前N個未評分項作為該用戶的推薦項。

1.2 實時流計算

Spark Streaming是基于Spark內核的一個分布式流計算應用框架，基于時空對數(shù)據(jù)流進行分割形成DStream，然后批量輸送給Spark引擎進行分布式內存計算。它是一個高效的分布式流計算引擎，在機器學習、數(shù)據(jù)挖掘等場合為用戶提供實時響應。

Spark是UC Berkeley AMP lab開源的通用分布式并行計算框架。該框架基于內存迭代計算，減少了I/O輸入輸出操作，從而提高了數(shù)據(jù)處理效率。Spark創(chuàng)新性地提出了彈性分布式數(shù)據(jù)集（Resilient Distributed Dataset，RDD）[9]。RDD作為Spark的核心具有如下特性：①只讀性數(shù)據(jù)集，易于多線程并發(fā)執(zhí)行；②一種分區(qū)的分布式存儲數(shù)據(jù)結構，易于分布式并行計算；③提供豐富的算子，同時每一個分區(qū)均有一個算子，方便用戶進行數(shù)據(jù)處理；④記錄了數(shù)據(jù)操作依賴關系，解決了數(shù)據(jù)容錯問題，且根據(jù)依賴關系實現(xiàn)了延遲調度機制，有效提高了執(zhí)行效率。其工作原理如圖2所示。

Spark Streaming工作流程是對流數(shù)據(jù)按照DStream Graph模板生成Job，然后通過JobScheduler線程池方式提交給Spark Cluster，如圖3所示。

2 增量模型與并行化實現(xiàn)

2.1 增量模型

采用基于項目的相似度，其中相似度計算采用GDC相似度增量[10]，如式（2）所示。將該公式首先分解為7個因子，如表1所示。當有新的評分記錄時更新緩存因子，增量更新如式（5）所示。

計算過程中有多個新增評分項時，每個評分項都可能對Sim（i，j）進行修改，一個Sim（i，j）值會受到新增項目i和項目j的同時修改，也就是說新增項目i和項目j必須在一個線程內執(zhí)行。所以，要在并行化執(zhí)行之前隔離這些沖突項，讓非沖突項盡可能地并行計算。

微批量形式的增量更新預測項目評分步驟如下：①根據(jù)初始數(shù)據(jù)初始化緩存因子并讀入內存，為后續(xù)增量計算作準備；②當微批量形式的增量數(shù)據(jù)到來時，從增量數(shù)據(jù)中提取出沖突項評分，對沖突項評分單線程進行并發(fā)計算，對非沖突項進行并行計算，并將增量評分加入評分集合；③并行化獲取用戶的未評分項，應用第②步計算結果預測用戶未評分項目的評分。先通過B/E得到相似度，然后通過式（3）得到未評分項的最近鄰，根據(jù)預測評分式（4）計算用戶未評分項目，整個過程都利用Spark基于內存的并行化計算；④不斷接受新數(shù)據(jù)，執(zhí)行步驟②、步驟③。

2.2 并行化實現(xiàn)

輸入評分數(shù)據(jù)Ratings，輸出項目相似度集合，代碼如下：

上述代碼中：第①～②步為初始化參數(shù)和SparkStreamContext；第③步并行初始化7個緩存因子；步驟⑤和步驟⑥聚合更新緩存因子所需要的數(shù)據(jù)；步驟⑦更新7個緩存因子，步驟⑨直接計算相似度矩陣。

3 實驗結果分析

實驗采用Intel 4Core主頻為2×2.2GHz、內存為8GB、硬盤160GB的計算機硬件配置，Spark版本2.2.0，基于Spark本地運行模式。采用Group Lens[11]網站的Movie Lens作為數(shù)據(jù)源，使用ML-2M的數(shù)據(jù)包，其中包括671個用戶對9 066部電影的100 004條評分記錄，評分值為1-5。從數(shù)據(jù)包中按時間排序分別選取1萬、2萬、3萬、…、8萬、9萬、10萬個評分記錄作為實驗數(shù)據(jù)，其中80%作為訓練數(shù)據(jù)集，20%作為測試數(shù)據(jù)集。

實驗采用平均絕對誤差MAE[12]作為評價標準，MAE通過計算用戶實際評分與預測評分之間的絕對偏差衡量推薦準確度，如式（6）所示。

其中：T為項目數(shù)量，r-ui為用戶u對項目i的實際評分，r′-ui為用戶u對項目i的預測評分。MAE越小，代表算法的推薦精度越高。本文對增量協(xié)同過濾算法與全量協(xié)同過濾算法的MAE進行比較，如圖4所示。

從圖4可以看出，在用戶評分數(shù)據(jù)集相對較小、數(shù)據(jù)稀疏的條件下，本文增量算法的推薦精度低于全量算法。隨著用戶評分數(shù)據(jù)集逐漸擴大，算法推薦精度逐漸提高，趨向于全量協(xié)同過濾算法推薦精度，這說明本文提出的基于Spark Streaming的增量協(xié)同過濾算法可以適應海量數(shù)據(jù)背景下的推薦。

在不同數(shù)據(jù)量情況下發(fā)現(xiàn)，增量運行時間和全量運行時間明顯不同，如圖5所示。

實驗采用Speedup[13]衡量同一數(shù)據(jù)集下增量算法和全量算法表現(xiàn)。

其中：F-p為p個數(shù)據(jù)集全量計算時間；I-p為p個數(shù)據(jù)集增量計算時間。增量計算與全量計算的加速比如圖6所示。

從圖6可以看出，本實驗Speedup值由較大幅度增長到趨于平緩。隨著數(shù)據(jù)量增加，系統(tǒng)資源逐漸成為性能提升的瓶頸。在對更大規(guī)模數(shù)據(jù)處理時，增加系統(tǒng)資源使Speedup進一步提升，表明該增量算法在大規(guī)模數(shù)據(jù)下的執(zhí)行效率高于全量更新算法，并且數(shù)據(jù)規(guī)模越大，精度越趨向于全量更新。

4 結語

基于Sprak Streaming計算的增量協(xié)同過濾算法緩解了大數(shù)據(jù)流處理的響應時間，在大數(shù)據(jù)環(huán)境下得到了較好應用。但如何從大規(guī)模數(shù)據(jù)中利用數(shù)據(jù)的多樣性獲取精準用戶偏好模型以提高推薦準確度，是今后的研究方向。

參考文獻：

[1] PAZZANI M J， BILLSUS D. Content-based recommendation systems[M]. The adaptive web. Springer Berlin Heidelberg，2007：325-341.

[2] LINDEN G，SMITH B， YORK J. Amazon.com recommendations： item-to-item collaborative filtering[J]. Internet Computing， IEEE，2003，7（1）：76-80.

[3] 俞騁超.基于深度神經網絡的用戶會話推薦算法研究[D].杭州：浙江大學，2016.

[4] KOREN Y， BELL R， VOLINSKY C. Matrix factorization techniques for recommender systems[J].Computer，2009，42（8）：30-37.

[5] 何佳知.基于內容和協(xié)同過濾的混合算法在推薦系統(tǒng)中的應用研究[D].上海：東華大學，2016.

[6] LUO X， XIA Y N， ZHU Q S. Applying the learning rate adaptation to the matrix factorization based collaborative filtering， knowledge-based systems[EB/OL]. https：//doi.org/10.1016/j.knosys.2012.07.016.

[7] LUO X， XIA Y N， ZHU Q S. Boosting the K-Nearest-Neighborhood based incremental collaborative filtering[J]. Knowledge-Based Systems，2013（53）：90-99.

[8] HERLOCKER， KONSTAN J A， RIEDL J. An empirical analysis of design choices in neighborhood-based collaborative filtering algorithms[J]. Information Retrieval，2002，5（4）：287-310.

[9] Apache Spark[EB/OL].http：//spark.apache.org/

[10] LUO X， XIA Y N， ZHU Q S. Incremental collaborative filtering recommender based on regularized matrix factorization， knowledge-based systems[EB/OL]. https：//grouplens.org/datasets/movielens/.

[11] BREESE J S， HECKERMAN D， KADIE C. Empirical analysis of predictive algorithms for collaborative filtering[C]. Proceedings of the Fourteenth conference on Uncertainty in artificial intelligence. Morgan Kaufmann Publishers Inc.，1998：43-52.

[12] ZHANG J， LI T， DAR， et al. A parallel method for computing rough set approximations[J]. Information Sciences，2012，194（5）：209-223.

（責任編輯：杜能鋼）