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

趙志偉

（星環(huán)眾志科技（北京）有限公司，北京100044）

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

推薦系統(tǒng)的上下文感知算法是目前應(yīng)用領(lǐng)域應(yīng)用最多，也是最成功的一種推薦算法。

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

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

1 相關(guān)算法設(shè)計

1.1 矩陣分解算法

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

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

由貝葉斯后驗概率可得：

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

式中：

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

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

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

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

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

1.2 相似度算法

在實際中，直接使用余弦相似度計算出的相似誤差較大。根據(jù)用戶的個性化評分尺度，同時統(tǒng)一評分標(biāo)準(zhǔn)，在計算時一般采用皮爾遜相似度。皮爾遜相似度公式為

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

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

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

式中：Gx∩Gy為用戶共同評價商品個數(shù)，Gx為目標(biāo)用戶評價商品總個數(shù)。

1.3 矩陣填充優(yōu)化算法

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

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

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

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

1.4 上下文感知算法

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

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

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

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

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

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

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

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

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

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

根據(jù)上文提出的矩陣分解算法和上下文感知算法，本文提出了上下文感知優(yōu)化算法。優(yōu)化后的算法有效緩解了傳統(tǒng)推薦算法[6]面臨的原始矩陣稀疏問題，從優(yōu)化相似度和轉(zhuǎn)變計算工具的角度提高了推薦算法的準(zhǔn)確性和效率性。

優(yōu)化后的算法計算流程如下：

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

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

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

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

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

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

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

Spark 是大規(guī)模數(shù)據(jù)處理的通用計算引擎，隨著近幾年的發(fā)展已經(jīng)形成了功能完善的分布式計算系統(tǒng)。它基于彈性分布式數(shù)據(jù)集RDD 的轉(zhuǎn)化實現(xiàn)對數(shù)據(jù)的計算，計算時Spark 將數(shù)據(jù)加載到內(nèi)存，執(zhí)行效率非常高。

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

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

2 實驗結(jié)果分析

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

2.1 實驗數(shù)據(jù)來源

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

在Last.fm 音樂集中，包含每個用戶和最受用戶歡迎的藝術(shù)家列表以及播放次數(shù)。它還包括可用于構(gòu)建內(nèi)容向量的用戶應(yīng)用標(biāo)簽，是具有用戶社交網(wǎng)絡(luò)信息的數(shù)據(jù)集。在數(shù)據(jù)集中，用戶作為算法中的樣本用戶，藝術(shù)家作為算法中被推薦的項目，用戶收聽數(shù)作為樣本用戶的評分數(shù)據(jù)，標(biāo)簽數(shù)和標(biāo)簽記錄數(shù)作為考察項目關(guān)系的標(biāo)準(zhǔn)。音樂數(shù)據(jù)集總體信息見表1。

表1 音樂數(shù)據(jù)集總體信息Tab.1 General music dataset information

Last.fm 數(shù)據(jù)集的稀疏度為

在結(jié)果測試時，選取最新12 個月的數(shù)據(jù)，訓(xùn)練集和測試集各自占比為80%和20%。

2.2 評價指標(biāo)

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

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

2.3 實驗結(jié)果分析

2.3.1 矩陣稀疏度分析

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

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

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

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

2.3.2 準(zhǔn)確度分析

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

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

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

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

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

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

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

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

2.3.3 算法執(zhí)行效率分析

固定近鄰用戶為50 時，設(shè)置定時任務(wù)記錄算法的執(zhí)行時間如表2。

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

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

3 結(jié)語

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

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