基于Spark Streaming的增量協同過濾算法

曾志武 蔡明

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

關鍵詞：協同過濾；推薦系統；增量計算；實時流計算；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 引言

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

1 協同過濾算法與實時流計算

1.1 協同過濾算法

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

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

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

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

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

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

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

1.2 實時流計算

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

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

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

2 增量模型與并行化實現

2.1 增量模型

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

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

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

2.2 并行化實現

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

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

3 實驗結果分析

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

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

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

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

在不同數據量情況下發現，增量運行時間和全量運行時間明顯不同，如圖5所示。

實驗采用Speedup[13]衡量同一數據集下增量算法和全量算法表現。

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

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

4 結語

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

參考文獻：

[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] 何佳知.基于內容和協同過濾的混合算法在推薦系統中的應用研究[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.

（責任編輯：杜能鋼）