趙志偉

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

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

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

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

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

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

1.1 矩陣分解算法

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

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

由貝葉斯后驗(yàn)概率可得：

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

式中：

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

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

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

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

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

1.2 相似度算法

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

式中：rUx，ik是用戶x 對(duì)物品k 的評(píng)分，是用戶歷史評(píng)價(jià)物品的平均分，用戶y 同理。

商品i 是兩用戶歷史記錄中共同評(píng)價(jià)商品。

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

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

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

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

（1）對(duì)用戶對(duì)物品的原始評(píng)價(jià)矩陣R 進(jìn)行矩陣分解，得到用戶矩陣U 和物品矩陣V，并再次逆向計(jì)算得到相似矩陣。

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

（3）根據(jù)向量c1和c2，判斷物品矩陣中的某物品是否是兩用戶均未評(píng)價(jià)過(guò)的物品。若是，則不改變?cè)u(píng)價(jià)向量的值，若否，則根據(jù)相似矩陣中的評(píng)分對(duì)c1和c2進(jìn)行填充，得到填充后的向量和和填充后的評(píng)價(jià)矩陣。

1.4 上下文感知算法

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

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

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

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

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

通過(guò)訪問(wèn)頻率只能初步判斷用戶對(duì)某屬性物品的興趣程度，真正反映用戶偏好特征的是用戶對(duì)該屬性物品的評(píng)分高低。

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

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

用戶對(duì)某特征類的偏好程度為

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

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

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

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

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

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

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

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

考慮到每個(gè)人的評(píng)分尺度差別，在計(jì)算預(yù)測(cè)評(píng)分時(shí)減去用戶的平均評(píng)分。

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

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

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

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

2 實(shí)驗(yàn)結(jié)果分析

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

2.1 實(shí)驗(yàn)數(shù)據(jù)來(lái)源

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

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

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

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

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

2.2 評(píng)價(jià)指標(biāo)

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

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

2.3 實(shí)驗(yàn)結(jié)果分析

2.3.1 矩陣稀疏度分析

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

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

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

從填充結(jié)果來(lái)看，填充后矩陣的稠密性有明顯的增加，填充后的矩陣的稀疏度遠(yuǎn)遠(yuǎn)小于原始矩陣的稀疏度。從稀疏度的變化趨勢(shì)來(lái)看，隨著用戶數(shù)的增加，原始矩陣的稀疏度變化不大，但是填充后的矩陣稀疏度有增加的趨勢(shì)。因?yàn)殡S著用戶和物品的增多，用戶評(píng)價(jià)過(guò)的物品占總物品比例降低，矩陣填充總數(shù)量降低。

2.3.2 準(zhǔn)確度分析

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

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

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

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

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

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

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

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

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

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

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

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

3 結(jié)語(yǔ)

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

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