基于時間加權ALS 模型協同過濾推薦算法

徐雪東，劉曉東

（1.武漢郵電科學研究院，湖北武漢 430070；2.武漢虹旭信息技術有限責任公司，湖北 武漢 430070）

為解決信息過載問題，推薦系統的研究是近幾年的熱點，推薦系統中應用最廣泛的推薦算法就是協同過濾[1-4]。推薦算法的運行需要大量的計算，目前主流的大數據計算框架有Hadoop MapReduce 和Spark。然而Hadoop MapReduce 有如下缺點：①將計算出的中間結果會留存在磁盤中；②啟動時間久等。Spark 彌補了這些缺點。

基于模型的協同過濾算法有很多的分支，文中提到的ALS 算法屬于其中的一種。ALS 算法的核心是矩陣分解，其主要思想是將龐大且稀疏的評分矩陣進行降維，再通過用戶-物品矩陣的填充達到了預測的目的。矩陣分解的求解有隨機梯度下降法(SGD)和最小二乘法(ALS)兩種方法，相較之下，ALS能減少不必要的存儲開銷并且易于在Spark 平臺上實現并行化。所以選擇ALS 算法并在Spark 平臺進行并行化實現[5-9]。

在ALS 算法優化上，Ding Y、Li X 使用遺忘函數對評分矩陣進行加權，并對時間復雜度進行了優化[6]。遲玉良等人提出了項目相似度和ALS 結合的算法，引用余弦相似度緩解了數據稀疏的問題，但是該算法不適用于海量數據環境[8]。鄒小波、王佳斌等人將KNN 算法和ALS 算法融合，并加入了用戶偏置項，減少了預測的誤差，但是該算法復雜度高[5]。

以上學者的研究，都從不同角度優化了推薦算法，但是沒有考慮到上下文時間信息導致的用戶興趣變化的問題和用戶因某一特征而對整個物品高評價，從而難以獲取用戶真正的興趣的問題。該文將從時間維度和物品特征維度兩方面對推薦算法進行研究。

1 Spark

1.1 Spark簡介

Apache Spark 是一個通用的和Hadoop 集群兼容的計算平臺。Spark 完美解決了MapReduce 在中間結果處理方式上的不足，它在內存中進行運算從而削減了讀取磁盤造成的I/O 開銷。因其有速度快、易廣泛使用等優點，Spark 被各大互聯網企業（如阿里巴巴、騰訊等）廣泛應用。

1.2 Spark組件

Spark 組件如圖1 所示。其中，Spark Core 負責資源調度以及提供彈性分布式數據集(RDD)，Spark SQL 具備了在Dataset 和DataFrame 之上執行SQL的能力，Spark Streaming 提供了流式計算能力，Spark MLlib 提供了在Spark 運行機器學習算法的能力，Graphx 提供了圖計算能力。

圖1 Spark組件

1.3 Spark架構

Spark 架構如圖2 所示。由Driver 進程進行調用Spark 的Main 方 法,啟 動SparkContext(Spark 的 上 下文對象)，并細分任務，提交給Cluster Manager 進程。該進程負責申請或釋放集群資源。Worker 負責啟動和管理Executor，是一個守護進程，最后由Executor運行Spark Task。

圖2 Spark運行架構

2 矩陣分解ALS算法原理

由于用戶對物品的評分矩陣往往是大規模且稀疏的，矩陣分解的思路就是改變用戶對的評分矩陣的稀疏性，把它分解成兩個低階矩陣相乘的形式[10-17]。設m個用戶對n個物品評分矩陣R∈Rm×n，將R矩陣分解為P、Q矩陣。如下式：

為避免模型過于復雜而導致的過擬合問題，加入正則項來控制模型的方差。最后訓練P、Q矩陣時，可以使用均方誤差(RMSE)，它表示預測值和實際觀測的誤差大小，訓練的過程就是使RMSE 最小化的過程。至此，可以定義損失函數為:

其中，表示算法預測用戶u對物品i的評分結果，pu表示用戶u的隱含特征因子向量，qi為物品i的隱含特征因子向量。λ表示用于防止模型的過擬合的正則化項系數。

可使用最小二乘法對式（3）進行求解，下一步就是交替迭代的過程，固定其中一個矩陣，先固定Q，計算損失函數C(p,q)對pu的偏導數等于0，得到:

同理，固定P，繼續計算C(p,q)對qi的偏導數等于0，得到：

其中，E為f×f的單位矩陣。

初始化原始矩陣Q，再利用式（4）計算得到P，利用式（5）計算得到Q，反復迭代，到指定迭代次數或RMSE 最優時停止迭代。

ALS 模型思想的核心是將稀疏且龐大的評分矩陣降維，緩解了數據稀疏的問題，而且易并行化計算。但是，該算法沒有解決以下問題：①經過時間的推移，用戶興趣的變化；②用戶只喜好對物品的某一特征，而推薦算法會根據物品所有特征進行推薦，導致的推薦精度不高。針對以上問題，引入了上下文時間因子和物品特征因子對ALS算法進行融合加權，進一步優化ALS 算法以提高準確性，并在Spark 平臺進行并行化實驗。

3 ALS算法的優化

3.1 引入時間遺忘曲線

在時間衰減函數的選擇上，選擇艾賓浩斯遺忘曲線。曲線如圖3 所示。

圖3 遺忘曲線

遺忘曲線中，將信息從認知到遺忘一半的時間定義為信息半衰期T0，定義衰減因子λ=。則對于當前時刻tn的遺忘函數可表示為：

將遺忘函數應用在推薦算法中，則可作為時間權重T，當tn-t0越大，則T越小。即久遠的用戶對物品評分的價值越低。考慮到用戶短時間內的興趣不會改變，所以同時加入興趣保持期T1優化遺忘曲線。將T1融入到遺忘函數中，得到：

該式作為時間因子對評分數據進行時間加權，則更可以得到更符合實際的推薦結果。

3.2 引入物品特征

在實際中，物品往往有多個特征，如一部電影可以同時是科幻片和動作片，但傳統的推薦算法中只根據用戶對物品的評分去推薦物品，當用戶只喜好物品的某一特征而對物品評高分時，傳統推薦算法會將物品所有特征的類似物品進行推薦，從而導致推薦準確性不高。對于此問題，引入物品特征和時間特征融合對ALS 算法進行加權，從而提升推薦的準確性。

將式（7）中對遺忘函數的時間權重定義為:

則遺忘曲線表示為：

在用戶對物品的特征喜好的判斷上，該文選擇用戶喜好的物品中某特征出現的頻率作為用戶喜好的判斷。在用戶所有有評分數據的物品中，某一特征出現的頻率，可代表用戶更偏好于該特征，從而才偏好該物品。對于用戶u的喜好物品i的其中一個特征qij所出現的頻率可表示為：

其中，Tend表示用戶對包含qij特征的物品最后進行評分的時間，Tbegin表示用戶第一次選擇包含qi特征物品的時間，tn表示用戶得到推薦的時間。該式說明，當特征出現次數越多，用戶則更偏好與擁有該特征的物品。

3.3 時間特征和物品特征加權融合

定義γf=feq(qij)將物品特征頻率和時間特征加權融合，得到最終的時間曲線的加權如下式：

其中，α、β為權重平衡因子，用來平衡時間權重和物品特征權重在總權重中的占比，需要通過實驗獲取該參數的最佳值。

將式（11）代入式（9）得到的時間曲線作為最終對原始評分矩陣進行加權的時間權重，得到優化后的評分矩陣，如下式:

其中，θ為調節因子，表示對時間權重調節在合理區間。R為評分矩陣，為加權后的評分矩陣。

3.4 優化ALS算法的步驟

將式（12）對原始評分矩陣進行優化，再代入式（3）得到了優化后的ALS 算法。該算法步驟如下：

第一步：讀取數據集，初始化用戶-物品評分矩陣R。

第二步：通過實驗得到的最優平衡因子(α,β)代入式（12）對R進行加權更新，得到新的評分矩陣。

第三步：訓練ALS 模型，將最優參數實驗得到的最佳迭代次數和隱因子數代入訓練，更新用戶矩陣和物品矩陣。

第四步：當得到最小的RMSE 或到達最大迭代次數時停止迭代，得到ALS 模型。

算法優化流程如圖4 所示。

圖4 算法優化流程圖

4 實驗以及結果分析

4.1 實驗環境搭建

基于阿里云環境創建Spark 集群，實現一主二從架構。實驗搭建的物理環境如表1 所示。

表1 實驗物理環境參數

首先配置主機之間的SSH 免密登錄。在此基礎上，搭建CDH6.2.1 大數據環境，并安裝HDFS、Spark、Yarn 等組件。

4.2 實驗數據準備

實驗選用國際公用數據集MovieLens 100K 數據集，其中包括電影評分數據u.data，電影信息數據u.item 和用戶信息數據u.user。

4.3 實驗設計

實驗結果評測標準將采用均方根誤差(Root Mean Squared Error,RMSE)。推薦算法得到的評分預測數據與實際觀測值之間的RMSE 來測試推薦算法預測的準確性。RMSE 的定義式如下：

其中，T為評分總數,rui是實際觀測值，是得到的預測值。

實驗過程中將數據集進行拆分，70%的數據為訓練集，30%的數據為測試集，并基于Spark 分布式環境設計了兩類實驗：①以不同迭代數和隱因子數進行實驗，得到最優參數。②對比算法優化前后RMSE值的變化，驗證優化后在準確性上的提升。

在最優參數的實驗中，測試ALS 模型在分布式Spark 環境下的不同迭代次數下RSME 值的變化情況，RSME 值低表示預測更為準確。測試的迭代次數為[5，10，15，20]，隱含特征因子數為[4，8，12，16]，結果如表2 和圖5 所示。

表2 不同迭代數和隱因子數下RMSE對比

圖5 不同迭代數和隱因子數下RMSE對比

由圖5 可知，對于當前數據集，平均RMSE 最低的是當隱因子個數為8 的情況，且此時，迭代數對RMSE 的影響較小，其最大和最小的差值不超過0.02，而迭代數的增長對推薦結果實時性有影響，增加了整體計算的時間。綜合以上結果，選擇隱因子個數為8，迭代次數為10 作為ALS 算法的參數。

在ALS 算法優化對比實驗中，選用實驗①得到的參數，即隱因子個數為8，迭代次數為10，在此參數下進行實驗②，選取信息半衰期T0為60 天，信息保持期T1為3 天，平衡因子α為[0.2，0.3，0.4]，β為[0.6，0.7，0.8]，衰減因子θ為0.3。進行優化后ALS 算法實驗，不同參數下的RMSE 如表3 所示。

表3 優化后ALS不同參數下的RMSE

觀察表3 可以發現，當平衡因子(α,β)取(0.3,0.7)時，優化后的ALS 算法可以得到最優的RSME。因此，選用(0.3,0.7)作為平衡因子參數。對比算法優化前后，結果如圖6 所示。

圖6 傳統ALS與優化后ALS對比

5 結束語

該文針對傳統矩陣分解ALS 算法所存在的時效性和推薦準確性的問題展開研究。選擇基于大數據分布式計算框架Spark 對傳統的ALS 算法進行了優化，同時通過實驗對比了改進前后的ALS 算法。由圖6 可知，優化后算法的RMSE 值降低了6.2%，結果表明，算法優化后有更優的推薦精度。但該優化算法尚未考慮用戶和物品相似度對推薦結果的影響，后續的工作將對時間加權函數和用戶以及物品相似度的融合加權進行研究。