基于Spark的上下文感知推薦算法的研究

趙志偉

（星環眾志科技（北京）有限公司，北京100044）

大數據時代的到來，給現代社會帶來了巨大的影響。當用戶在海量數據中查找信息時，需要投入很大的精力。為了解決用戶篩選信息困難的問題，推薦系統逐漸進入我們的視野。推薦系統通過分析用戶興趣和項目屬性之間的關系，能夠幫助用戶從大量的可選數據中快速定位到滿足用戶需求的信息[1]。

推薦系統的上下文感知算法是目前應用領域應用最多，也是最成功的一種推薦算法。

首先對原始矩陣進行填充[2-3]，合理增加矩陣稠密性，然后結合物品的上下文信息，得到用戶偏好度矩陣，最后通過優化的皮爾遜相似度得到近鄰用戶，最終得到用戶對物品的預測評分。

本文提出的基于Spark 的上下文感知算法是在Spark 平臺進行計算的，主要通過緩解矩陣稀疏性、優化計算模型、提高算法可擴展性等方面對已投入應用的上下文感知推薦算法的優化，并在實際應用中對算法的可行性和準確性進行對比和分析。

1 相關算法設計

1.1 矩陣分解算法

矩陣分解算法是將高維矩陣分成兩個低維矩陣，根據用戶的評價矩陣對用戶進行興趣分析。假設用戶的特征矩陣為U，包含個數M，物品的特征矩陣為V，包含個數為N，用戶特征矩陣和物品特征矩陣的維度都是d。則所有用戶對所有物品的評分構成的評分矩陣R 可表示為R＝UTV。同樣地，如果計算出U 和V 的值，也可反向推出R 的值，通過反向計算得到的用戶物品評價矩陣與原矩陣近似。評分矩陣R 和近似矩陣之間的誤差稱為噪聲，噪聲值的分布屬于高斯分布。

根據貝葉斯公式，得出噪聲概率矩陣的概率密度函數為

由貝葉斯后驗概率可得：

進行對數變換后，再求最大化后驗概率，即求下式的最小值：

式中：

用梯度下降法多次迭代，直到求出最小值，最終將高維矩陣分解為維度較低的矩陣U 和矩陣V，同時根據低維矩陣也可得到原矩陣的相似矩陣。

在推薦系統中，為了緩解原始矩陣稀疏的問題會采用矩陣填充的方式。

一般情況下，采用將沒有數值的位置填入統一度量的方式，如平均數、眾數，或者根據實際應用場景人為設定一個較為合理的值，完善矩陣后再根據推薦算法得出推薦結果。這種方法對緩解稀疏性有一定的效果，但實際中大部分用戶對該產品的評價與填充結果正好相反，導致通過算法計算后預測出的興趣商品與用戶的真實興趣有很大誤差[4-5]。

如果采用凸矩陣填充方式，即求矩陣跡或者跡模的最小化。這種方式計算結果比較理想，但是推薦系統中存儲海量的用戶和物品數據，使用這種方式需要將整個矩陣加載到內存中，會超出計算機的承受能力。

為了解決這些問題，本文引入非凸矩陣的填充。通過對非凸矩陣進行矩陣分解，將原始稀疏矩陣分解成兩個維度較低的矩陣，在實際計算時只需存儲分解后的兩個低維矩陣，能夠明顯降低計算機的內存消耗。

1.2 相似度算法

在實際中，直接使用余弦相似度計算出的相似誤差較大。根據用戶的個性化評分尺度，同時統一評分標準，在計算時一般采用皮爾遜相似度。皮爾遜相似度公式為

式中：rUx，ik是用戶x 對物品k 的評分，是用戶歷史評價物品的平均分，用戶y 同理。

商品i 是兩用戶歷史記錄中共同評價商品。

當用戶訪問的項目集合較小時，得到的結果會偏高。在計算相似度時可引入共同評分權重因子，可得相似度公式為

式中：Gx∩Gy為用戶共同評價商品個數，Gx為目標用戶評價商品總個數。

1.3 矩陣填充優化算法

為了最大化保留用戶興趣特征，提高矩陣填充的合理性，本文采用基于矩陣分解的矩陣填充方式。

（1）對用戶對物品的原始評價矩陣R 進行矩陣分解，得到用戶矩陣U 和物品矩陣V，并再次逆向計算得到相似矩陣。

（2）根據用戶矩陣U 中任意兩用戶，得到用戶對所有物品的評分向量c1和c2。

（3）根據向量c1和c2，判斷物品矩陣中的某物品是否是兩用戶均未評價過的物品。若是，則不改變評價向量的值，若否，則根據相似矩陣中的評分對c1和c2進行填充，得到填充后的向量和和填充后的評價矩陣。

1.4 上下文感知算法

上下文信息可以描述某一事物相關狀態的所有信息。在推薦系統中，算法的上下文感知信息可以有多種，大體可分為時間、地點、天氣等物理信息，身份、社交對象等社會信息，年齡、心情、經驗和認知能力等狀態信息，推薦物品類型和屬性等媒體信息。

根據推薦系統的數據集，可得到物品信息的上下文。設某個物品有k 個重要屬性，則該物品的上下文信息總集合可定義為

式中：Ci是離散值，還可細分為子信息。

例如電影數據集，C=｛C1，C2｝，C1為主題，C2為年代，而主題又可分為愛情片、動作片和科幻片，年代可分為古代、現代和未來。在推薦系統中，可以根據用戶信息以及所訪問物品的上下文信息，得出用戶對某類屬性的訪問次數以及訪問項目總數，通過兩者的比值，得出用戶對某個特征類的偏好。

式中：Ni，c表示用戶i 對屬性c 的興趣程度，Ci，c表示用戶對屬性c 的訪問次數，Ii表示用戶訪問所有項目集合。

通過訪問頻率只能初步判斷用戶對某屬性物品的興趣程度，真正反映用戶偏好特征的是用戶對該屬性物品的評分高低。

如果用戶對某兩個屬性類的訪問次數相同，但是對第一類屬性中的物品評分普遍高于第二類屬性，表示用戶對第一類屬性更有興趣。

式中：Pi，c表示用戶i 對屬性c 評分程度，ri，c表示屬性c 中評分高于用戶評價平均分的物品數。

用戶對某特征類的偏好程度為

1.5 基于Spark 的上下文感知推薦算法

根據上文提出的矩陣分解算法和上下文感知算法，本文提出了上下文感知優化算法。優化后的算法有效緩解了傳統推薦算法[6]面臨的原始矩陣稀疏問題，從優化相似度和轉變計算工具的角度提高了推薦算法的準確性和效率性。

優化后的算法計算流程如下：

（1）原始矩陣填充：對原始的用戶物品評價矩陣R 進行矩陣分解，計算出相似矩陣，并按照填充規則對原始矩陣進行填充。

（2）用戶偏好相似度計算：計算用戶對每個屬性類在訪問頻率上的興趣程度，形成用戶屬性興趣矩陣。同時根據用戶評價平均評分，形成用戶主觀評分矩陣。結合兩矩陣形成用戶偏好度矩陣Hi。

（3）將共同評價項目個數引入皮爾遜相似度，根據用戶偏好度矩陣Hi得出目標用戶與其他用戶的相似度。

（4）根據相似度，找到與目標用戶相似度最高的k 個用戶，得到近鄰用戶集合Topk。

（5）根據相似用戶集合中用戶v 對項目的評分，預測目標用戶的項目的評分。選取評分最高的項目推薦給用戶。評分公式為

考慮到每個人的評分尺度差別，在計算預測評分時減去用戶的平均評分。

在推薦算法中，優化各流程中的參數可以使推薦結果的準確度得到提高，但同時也增加了計算量。矩陣填充和相似度的計算增加了多個計算環節，這些額外的步驟會增加計算時長。面對大數據時代的海量數據，算法優化帶來的額外耗時是無法預判的。為了增加算法的拓展性，引入了大數據分布式計算平臺—Spark。

Spark 是大規模數據處理的通用計算引擎，隨著近幾年的發展已經形成了功能完善的分布式計算系統。它基于彈性分布式數據集RDD 的轉化實現對數據的計算，計算時Spark 將數據加載到內存，執行效率非常高。

根據推薦算法的拓展性和效率性要求，可以將算法部署在Spark 平臺，計算時多個算法并行執行。每個計算環節都通過多臺服務器分布式處理，從而極大地提高算法的執行效率。圖1 展示了系統對于關鍵用戶推薦的整體流程。

圖1 Spark 進行用戶推薦整體流程Fig.1 Process of user recommendation on Spark

2 實驗結果分析

針對傳統推薦算法本身的局限性，本文通過對矩陣填充、結合上下文感知信息和完善計算工具等方式完善推薦算法，最終使推薦算法更準確的反映用戶的實際需求。為了更好地驗證推薦結果的準確性，本文用音樂數據集中的數據檢驗優化后的算法在準確度和效率上的提高。

2.1 實驗數據來源

考慮到優化后的算法會涉及上下文信息、矩陣填充等因素，用Last.fm 提供的音樂數據集hetrec 2011-lastfm-2k 來進行算法的性能和結果準確度的驗證。

在Last.fm 音樂集中，包含每個用戶和最受用戶歡迎的藝術家列表以及播放次數。它還包括可用于構建內容向量的用戶應用標簽，是具有用戶社交網絡信息的數據集。在數據集中，用戶作為算法中的樣本用戶，藝術家作為算法中被推薦的項目，用戶收聽數作為樣本用戶的評分數據，標簽數和標簽記錄數作為考察項目關系的標準。音樂數據集總體信息見表1。

表1 音樂數據集總體信息Tab.1 General music dataset information

Last.fm 數據集的稀疏度為

在結果測試時，選取最新12 個月的數據，訓練集和測試集各自占比為80%和20%。

2.2 評價指標

衡量算法性能有多種評價指標： 如準確度、覆蓋率、擴展性等。其中，算法準確度包括分類準確度和誤差度。誤差度包括平均絕對誤差MAE 和均方根誤差RMSE。計算MAE 的過程非常直觀，直接計算最終的推薦結果和用戶記錄的真實值的差別。MAE 值越小，意味著推薦算法預測的值更接近用戶的真實興趣，推薦準確度就越高。計算公式為

式中：n 為樣本個數；pij為用戶的真實評分；為預測評分。

2.3 實驗結果分析

2.3.1 矩陣稀疏度分析

為了解決初始矩陣稀疏影響推薦算法計算準確率的問題，優化后的算法對原始用戶物品評價矩陣進行了填充。在實驗中，隨機抽取數據集中的數據作為初始用戶評價矩陣，記為matrix-init，然后根據上述填充算法對初始矩陣進行填充，新生成的矩陣記為matrix-fill。將填充前后的2 個矩陣進行稀疏度的對比，稀疏度用矩陣中空缺值的個數與矩陣中總元素的比值表示。

在數據集中隨機選取不同數量的用戶進行矩陣填充，填充前后的稀疏度對比結果如圖2 所示。

圖2 矩陣填充前后稀疏度對比Fig.2 Comparison of sparsity before and after matrix filling

從填充結果來看，填充后矩陣的稠密性有明顯的增加，填充后的矩陣的稀疏度遠遠小于原始矩陣的稀疏度。從稀疏度的變化趨勢來看，隨著用戶數的增加，原始矩陣的稀疏度變化不大，但是填充后的矩陣稀疏度有增加的趨勢。因為隨著用戶和物品的增多，用戶評價過的物品占總物品比例降低，矩陣填充總數量降低。

2.3.2 準確度分析

對于推薦算法而言，評價算法是否得到優化的一個重要標準就是準確度。在對比推薦算法的準確度實驗中，通過對近鄰用戶數的控制來觀察不同推薦算法下平均絕對誤差MAE 值的變化。MAE 值越低，則推薦算法的結果準確度越高，表明改進后的算法有更高的應用價值。

在實驗中，測試樣本集數據隨機抽取總用戶個數為1000，音樂家個數為3000，將近鄰函數個數作為自變量。為了驗證改進后的模糊聚類算法對上下文感知算法準確度的有所提高，實驗將基于基礎上下文感知和優化后的算法的MAE 值和執行時長進行了對比。

實驗時，將基于用戶的基礎上下文感知算法記為CF-base，將進行過初始矩陣填充步驟然后使用基礎上下文感知計算的算法記為CF-fill，將本文提出的上下文感知算法記為CF-context。計算相似度時采用結合用戶共同評價物品的皮爾遜相似度計算目標用戶的近鄰用戶。

三種算法下，根據近鄰用戶數的不同，得出的MAE 值的變化結果如圖3 所示。

圖3 三種算法下近鄰用戶數對MAE 值的影響Fig.3 Influence of the number of neighbor users on the MAE value under the three algorithms

從圖3 可以看出，三種算法下的平均絕對誤差隨著近鄰用戶的增加逐漸降低直至平穩收斂到某值而不再改變。

從總體上來看，CF-fill 算法和CF-context 算法推薦結果的準確率比CF-base 算法更高。在相同條件下，CF-fill 算法比CF-base 算法的MAE 值更小，說明對初始矩陣進行填充對推薦結果準確性的提高是有效果的。

在近鄰用戶個數在50 時，各算法的MAE 值趨于最佳狀態。隨著近鄰用戶個數的持續增加，誤差不再持續降低，反而有上升趨勢，由此看出近鄰用戶過多也會對最終推薦結果的準確性造成干擾。

2.3.3 算法執行效率分析

固定近鄰用戶為50 時，設置定時任務記錄算法的執行時間如表2。

表2 算法執行時間對比表Tab.2 Algorithm execution time comparison

從計算時間上看，執行三種算法所需的時間差距不大，CF-context 算法需要時間相對較長。對算法進行優化后，會增加額外的計算環節，需要更長的時間得出推薦結果。雖然計算時長有所增加，但是增加的幅度不大，而且推薦結果的準確度有明顯的提高，因此CF-context 算法有更高的使用價值。

3 結語

傳統的推薦算法由于原始矩陣稀疏和實際場景等約束條件的存在，得出的推薦結果可能與用戶真實的興趣項目差距較大。

本文在傳統算法的基礎上，提出了基于Spark的上下文感知推薦算法，在矩陣稀疏性、用戶和物品屬性、計算平臺等方面進行了優化，在計算時長增加幅度可接受范圍內，提高了推薦算法的準確度，進一步提高了推薦算法在實際場景下的適用性。