馬 騰，牛少彰，史成潔

(1.北京郵電大學(xué) 計(jì)算機(jī)學(xué)院，北京 100876；2.中科院信息工程研究所，北京 100093)

0 引言

隨著分布式計(jì)算和數(shù)據(jù)庫(kù)技術(shù)的發(fā)展，互聯(lián)網(wǎng)進(jìn)入了大數(shù)據(jù)時(shí)代。大數(shù)據(jù)時(shí)代為人們提供了豐富的信息，同時(shí)，也在各個(gè)領(lǐng)域帶來(lái)了巨大的機(jī)遇和挑戰(zhàn)。解決信息過(guò)載的問(wèn)題，從大量數(shù)據(jù)中提取有用的知識(shí)一直以來(lái)都廣受研究者們的關(guān)注。其中，推薦系統(tǒng)通過(guò)為用戶提供個(gè)性化服務(wù)，被認(rèn)為是當(dāng)前解決信息過(guò)載問(wèn)題最有效的工具之一，已被廣泛應(yīng)用在電商網(wǎng)站、影視資源服務(wù)商、社交網(wǎng)絡(luò)等各個(gè)領(lǐng)域。傳統(tǒng)推薦算法主要有基于內(nèi)容的推薦、協(xié)同過(guò)濾推薦、混合推薦等多種算法。交替最小二乘法（Alternating-Least-Squares，ALS）作為協(xié)同過(guò)濾推薦算法的一個(gè)分支，由于解決了協(xié)同過(guò)濾算法 中數(shù)據(jù)稀疏性的問(wèn)題，在推薦系統(tǒng)中被廣泛使用。

另一方面，現(xiàn)實(shí)中生成的大量數(shù)據(jù)普遍以流式無(wú)結(jié)構(gòu)化或半結(jié)構(gòu)化的形式存在，例如用戶點(diǎn)擊Web頁(yè)面產(chǎn)生的行為日志等。這些數(shù)據(jù)都具有變化迅速，數(shù)據(jù)量大的特點(diǎn)。例如用戶過(guò)了今天可能就不會(huì)對(duì)某件商品感興趣了。而傳統(tǒng)的推薦系統(tǒng)通常會(huì)在一個(gè)規(guī)定的時(shí)間間隔內(nèi)更新模型，如幾個(gè)小時(shí)或者數(shù)天，這就無(wú)法滿足對(duì)實(shí)時(shí)性的需求。并且由于用戶對(duì)某件商品的興趣會(huì)隨著時(shí)間減弱，因此傳統(tǒng)的推薦算法的預(yù)測(cè)質(zhì)量也會(huì)隨之下降。

本文針對(duì)以上問(wèn)題，設(shè)計(jì)了一種基于 Flink的電商實(shí)時(shí)推薦系統(tǒng)。該系統(tǒng)共分為4個(gè)模塊：數(shù)據(jù)加載模塊、商品特征向量計(jì)算模塊、日志采集模塊、實(shí)時(shí)推薦模塊。數(shù)據(jù)加載模塊將用戶對(duì)商品的歷史評(píng)分?jǐn)?shù)據(jù)導(dǎo)入數(shù)據(jù)庫(kù)中。商品特征向量計(jì)算模塊通過(guò)用戶對(duì)商品的歷史評(píng)分?jǐn)?shù)據(jù)得到每個(gè)商品的特征向量。日志采集模塊將實(shí)時(shí)采集到的用戶評(píng)分?jǐn)?shù)據(jù)同時(shí)進(jìn)行緩存和輸入到實(shí)時(shí)推薦模塊中。實(shí)時(shí)推薦模塊得到用戶實(shí)時(shí)的評(píng)分?jǐn)?shù)據(jù)，結(jié)合商品特征向量，通過(guò)實(shí)時(shí)推薦算法得到推薦商品列表，為用戶做出推薦。

1 相關(guān)工作

從20世紀(jì)90年代中期開(kāi)始，對(duì)推薦系統(tǒng)的研究吸引了越來(lái)越多的研究人員。經(jīng)典的推薦算法可以劃分為協(xié)同過(guò)濾推薦和基于內(nèi)容的推薦。協(xié)同過(guò)濾推薦根據(jù)用戶對(duì)項(xiàng)目的行為數(shù)據(jù)為用戶產(chǎn)生推薦；而基于內(nèi)容的推薦算法通過(guò)對(duì)項(xiàng)目?jī)?nèi)在語(yǔ)義的分析，為用戶推薦與感興趣項(xiàng)目相似的項(xiàng)目。然而，每種推薦算法都有各自的缺陷。兩種算法都需要面對(duì)冷啟動(dòng)的問(wèn)題，即如何對(duì)新用戶進(jìn)行推薦或如何推薦新產(chǎn)品給用戶。此外，協(xié)同過(guò)濾算法還有打分稀疏性的問(wèn)題和算法可擴(kuò)展性問(wèn)題，而基于內(nèi)容的推薦算法不可避免地受到信息獲取技術(shù)的約束。因此，很多研究人員為了解決推薦算法的局限性，將協(xié)同過(guò)濾和基于內(nèi)容的推薦兩種算法的優(yōu)點(diǎn)相結(jié)合，提出了各種混合推薦算法。其中包括將不同算法的推薦結(jié)果線性組合、在不同的場(chǎng)景中使用更可信的推薦結(jié)果以及在協(xié)同過(guò)濾算法中加入基于內(nèi)容的算法等。

最近，針對(duì)大數(shù)據(jù)和實(shí)時(shí)性的推薦系統(tǒng)受到了更多的關(guān)注。文獻(xiàn)[1]提出了一種關(guān)鍵字感知推薦系統(tǒng)，該系統(tǒng)旨在使用Apache Hadoop處理大型數(shù)據(jù)集。該系統(tǒng)背后的主要思想是利用從用戶和項(xiàng)目的文本數(shù)據(jù)中提取的關(guān)鍵字，以提高性能并緩解冷啟動(dòng)問(wèn)題。文獻(xiàn)[2]提出了一種稱(chēng)為APRA的大數(shù)據(jù)近似并行推薦算法，該算法是基于Apache Spark開(kāi)發(fā)的，可有效處理大規(guī)模數(shù)據(jù)。文獻(xiàn)[3]提出一種自適應(yīng)分布式數(shù)據(jù)流環(huán)境的SGD算法，通過(guò)點(diǎn)對(duì)點(diǎn)網(wǎng)絡(luò)控制模型訓(xùn)練過(guò)程，對(duì)矩陣分解模型實(shí)時(shí)增量更新，避免引入?yún)?shù)服務(wù)器帶來(lái)的性能瓶頸。文獻(xiàn)[4]提出了一種簡(jiǎn)單但高效的推薦算法，該算法利用用戶的個(gè)人資料屬性將其劃分為多個(gè)集群。對(duì)于每個(gè)群集，設(shè)想一個(gè)虛擬意見(jiàn)領(lǐng)袖代表整個(gè)群集，這樣可以顯著減小原始用戶項(xiàng)目矩陣的維數(shù)，然后設(shè)計(jì)加權(quán)斜率One-VU方法并將其應(yīng)用于虛擬意見(jiàn)領(lǐng)袖-項(xiàng)目矩陣以獲得推薦結(jié)果。文獻(xiàn)[5]提出了疾病診斷和治療推薦系統(tǒng)DDTRS，引入了密度峰值聚類(lèi)分析算法來(lái)進(jìn)行疾病癥狀聚類(lèi)，通過(guò)Apriori算法分別進(jìn)行疾病診斷規(guī)則和疾病治療規(guī)則的關(guān)聯(lián)分析，并在Spark云平臺(tái)實(shí)現(xiàn)了解決方案。文獻(xiàn)[6]提出了一種基于聯(lián)合訓(xùn)練方法的推薦算法，稱(chēng)為ECoRec，該算法可以驅(qū)動(dòng)兩個(gè)或更多推薦算法彼此同意自己的預(yù)測(cè)來(lái)產(chǎn)生最終的預(yù)測(cè)。文獻(xiàn)[7]提出了一種具有遺傳算法的最近鄰人工免疫系統(tǒng)NNAISGA，通過(guò)進(jìn)行快速數(shù)據(jù)插補(bǔ)以減少稀疏性。文獻(xiàn)[8]提出了用于預(yù)測(cè)大時(shí)間序列的不同可擴(kuò)展方法，還開(kāi)發(fā)了處理任意預(yù)測(cè)范圍的方法。文獻(xiàn)[9]提出了GRS用戶群推薦系統(tǒng)，可以幫助用戶群根據(jù)他們的喜好和需求找到合適的項(xiàng)目。文獻(xiàn)[10]提出了一種有效的并行算法 ConSimMR，用于使用 MapReduce構(gòu)造相似矩陣。文獻(xiàn)[11]提出了一種推薦算法，這種算法可建立獨(dú)立于個(gè)人用戶興趣的集體偏好模型，并且不需要復(fù)雜的評(píng)分系統(tǒng)。

本文首先基于“最近一段時(shí)間用戶的興趣是相似的”設(shè)計(jì)了一種實(shí)時(shí)推薦算法，可以滿足瞬時(shí)的推薦需求，并在準(zhǔn)確性方面具有優(yōu)越性。然后在Flink上對(duì)該算法進(jìn)行實(shí)現(xiàn)，并設(shè)計(jì)了電商推薦系統(tǒng)。

2 背景知識(shí)

ALS算法：當(dāng)數(shù)據(jù)中沒(méi)有顯性特征時(shí)，就需要根據(jù)已有的偏好數(shù)據(jù)，去發(fā)掘出隱藏的特征，即隱語(yǔ)義模型（LFM）。協(xié)同過(guò)濾算法非常依賴(lài)歷史數(shù)據(jù)，而一般的推薦系統(tǒng)中，偏好數(shù)據(jù)又往往是稀疏的，這就需要對(duì)原始數(shù)據(jù)做降維處理。假設(shè)用戶物品評(píng)分矩陣為 R，現(xiàn)在有 m個(gè)用戶，n個(gè)物品，目標(biāo)是找到兩個(gè)矩陣P和Q，使這兩個(gè)矩陣的乘積近似等于R，即將用戶物品評(píng)分矩陣R分解成兩個(gè)低維矩陣相乘：

分解之后的矩陣就代表了用戶和項(xiàng)目的k個(gè)隱藏特征。矩陣分解得到的預(yù)測(cè)評(píng)分矩陣?R，與原評(píng)分矩陣R在已知的評(píng)分項(xiàng)上可能會(huì)有誤差，這個(gè)誤差用平方損失函數(shù)來(lái)衡量，并且加入正則化項(xiàng)，以防過(guò)擬合：

Flink：Apache Flink是一個(gè)分布式處理框架，用于對(duì)無(wú)界和有界數(shù)據(jù)流進(jìn)行有狀態(tài)的計(jì)算。Flink作為新一代的流處理引擎，可以處理毫秒級(jí)的實(shí)時(shí)請(qǐng)求，并且支持流批一體的數(shù)據(jù)處理。在實(shí)際生產(chǎn)中的人工智能使用場(chǎng)景中，F(xiàn)link在包括特征工程，在線學(xué)習(xí)，在線預(yù)測(cè)等方面都有一些獨(dú)特優(yōu)勢(shì)。

3 實(shí)時(shí)推薦算法

實(shí)時(shí)計(jì)算與離線計(jì)算應(yīng)用于推薦系統(tǒng)上最大的不同在于實(shí)時(shí)計(jì)算推薦結(jié)果應(yīng)該反映最近一段時(shí)間用戶的偏好，而離線計(jì)算推薦結(jié)果則是根據(jù)用戶從第一次評(píng)分起的所有評(píng)分記錄來(lái)計(jì)算用戶總體的偏好。

用戶對(duì)物品的偏好隨著時(shí)間的推移總是會(huì)改變的。比如一個(gè)用戶u在某時(shí)刻對(duì)商品p給予了極高的評(píng)分，那么在近期一段時(shí)間，u極有可能很喜歡與商品p類(lèi)似的其他商品；而如果用戶u在某時(shí)刻對(duì)商品 q給予了極低的評(píng)分，那么在近期一段時(shí)間，u極有可能不喜歡與商品 q類(lèi)似的其他商品。所以對(duì)于實(shí)時(shí)推薦，當(dāng)用戶對(duì)一個(gè)商品進(jìn)行了評(píng)價(jià)后，用戶會(huì)希望推薦結(jié)果基于最近幾次評(píng)分進(jìn)行一定的更新，使得推薦結(jié)果匹配用戶近期的偏好，滿足用戶近期的口味。

如果實(shí)時(shí)推薦系統(tǒng)采用離線推薦算法，由于算法運(yùn)行時(shí)間巨大，不具有實(shí)時(shí)得到新的推薦結(jié)果的能力；并且由于用戶做出實(shí)時(shí)評(píng)分之后對(duì)整個(gè)評(píng)分表的影響只是增加一條記錄，使得算法運(yùn)行后的推薦結(jié)果與用戶做出本次評(píng)分前后沒(méi)有多少差別，從而給用戶推薦結(jié)果總是不變的感覺(jué)，影響用戶體驗(yàn)。所以本文的實(shí)時(shí)推薦算法主要實(shí)現(xiàn)兩個(gè)目標(biāo)：1.用戶實(shí)時(shí)評(píng)分之后，系統(tǒng)可以明顯的更新推薦結(jié)果；2.減少推薦過(guò)程中的計(jì)算量，滿足響應(yīng)時(shí)間上的實(shí)時(shí)要求。

當(dāng)用戶u對(duì)商品p進(jìn)行一次評(píng)分，將觸發(fā)一次對(duì)用戶u的推薦結(jié)果的更新。對(duì)于用戶u來(lái)說(shuō)，他與商品p最相似的n個(gè)商品之間的推薦優(yōu)先級(jí)將發(fā)生變化，最終選取與商品p最相似的K個(gè)商品作為候選商品。這些商品將根據(jù)用戶u最近的若干次評(píng)分計(jì)算出對(duì)用戶u的推薦優(yōu)先級(jí)，然后與上次對(duì)用戶u的實(shí)時(shí)推薦結(jié)果進(jìn)行基于推薦優(yōu)先級(jí)的合并、替換得到更新后的推薦結(jié)果。

首先，獲取用戶u按時(shí)間順序最近的K個(gè)評(píng)分，記為RK；獲取商品 p的最相似的K個(gè)商品集合，記為S；然后，對(duì)于每個(gè)商品q?S，計(jì)算其推薦優(yōu)先級(jí)Euq，計(jì)算公式為：

其中：Rr表示用戶 u對(duì)商品 r的評(píng)分；sim(q,r)表示計(jì)算得到的商品q與商品r特征向量之間的相似度，設(shè)定最小相似度為0.6，當(dāng)商品q和商品 r相似度低于 0.6的閾值，則視為兩者不相關(guān)并忽略；表示q與RK中商品相似度大于最小閾值的個(gè)數(shù)；表示RK中與商品 q相似的、且本身評(píng)分較高（大于等于6）的商品個(gè)數(shù)；recount表示RK中與商品q相似的、且本身評(píng)分較低（小于6）的商品個(gè)數(shù)。

上一次為用戶u的實(shí)時(shí)推薦結(jié)果列表Rec也是一個(gè)大小為K的<商品m的ID，m的推薦優(yōu)先級(jí)>列表：

將 updatedList與上一次實(shí)時(shí)推薦結(jié)果 Rec進(jìn)行合并、替換形成新的推薦結(jié)果NewRec：

其中，i表示updatedList與Rec的商品集合中的每個(gè)商品，topK是一個(gè)函數(shù)，表示從中選出推薦優(yōu)先級(jí)最大的 K個(gè)商品。最終，NewRec即為經(jīng)過(guò)用戶u對(duì)商品p評(píng)分后觸發(fā)的實(shí)時(shí)推薦得到的最新推薦結(jié)果。

4 推薦系統(tǒng)架構(gòu)

本文基于 Flink實(shí)現(xiàn)的推薦系統(tǒng)分為 4個(gè)模塊：數(shù)據(jù)加載模塊、商品特征向量計(jì)算模塊、日志采集模塊、實(shí)時(shí)推薦模塊。系統(tǒng)架構(gòu)如圖1所示。

圖1 基于Flink的推薦系統(tǒng)Fig.1 recommender system based on Flink

數(shù)據(jù)加載模塊負(fù)責(zé)將歷史數(shù)據(jù)和日志采集模塊采集到的實(shí)時(shí)評(píng)分流數(shù)據(jù)加載到推薦系統(tǒng)用到的mysql數(shù)據(jù)庫(kù)中的Rating數(shù)據(jù)表中。Rating數(shù)據(jù)表有4個(gè)字段：用戶id，商品id，評(píng)分，時(shí)間戳。

商品特征向量計(jì)算模塊使用 ALS算法對(duì)數(shù)據(jù)庫(kù)中的Rating數(shù)據(jù)表進(jìn)行矩陣分解得到每個(gè)商品的特征向量，然后計(jì)算得到每件商品的相似商品列表，存入mysql中。由于此模塊涉及到對(duì)整個(gè)數(shù)據(jù)集使用ALS算法，耗時(shí)較長(zhǎng)，且用戶的一次評(píng)分對(duì)整個(gè)數(shù)據(jù)集的影響較小，所以不必實(shí)時(shí)更新相似列表，只需每隔一段時(shí)間進(jìn)行一次計(jì)算。

日志采集模塊負(fù)責(zé)用flume拉取客戶端埋點(diǎn)生成的日志信息，并通過(guò)kafka streaming程序?qū)θ罩拘畔⑦M(jìn)行清洗，通過(guò)日志前綴過(guò)濾出評(píng)分信息，并挑選出推薦系統(tǒng)用到的4個(gè)字段，以數(shù)據(jù)流的形式輸入到 kafka中，供數(shù)據(jù)加載模塊和實(shí)時(shí)推薦模塊使用。

實(shí)時(shí)推薦模塊在從kafka中收到用戶的一條實(shí)時(shí)評(píng)分時(shí)，按照前文第3章提出的實(shí)時(shí)推薦算法為用戶生成實(shí)時(shí)的推薦列表，返回到客戶端做出推薦。

主要的計(jì)算流程為：Flink程序加載商品相似度列表作為一條廣播流，與訂閱 kafka實(shí)時(shí)評(píng)分topic生成的評(píng)分流連接，當(dāng)一條實(shí)時(shí)評(píng)分?jǐn)?shù)據(jù)到來(lái)時(shí)，先從redis中獲取該用戶最近的n次評(píng)分，保存為一個(gè)數(shù)組recentlyRating[(productid,score)]；然后從廣播流中取出該用戶此次評(píng)分商品最相似的m個(gè)商品列表作為備選商品，保存為一個(gè)數(shù)組candidate[(productid,distance)]；對(duì)于每一個(gè)備選商品，計(jì)算與每一個(gè)最近n此評(píng)分商品的權(quán)重平均評(píng)分，然后與影響因子相加，得到每個(gè)備選商品的推薦得分；最后與上一次為該用戶的實(shí)時(shí)推薦列表進(jìn)行合并，得到最終的推薦列表。

5 實(shí)驗(yàn)及結(jié)果

本文在renttherunway數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn)。renttherunway包含了105508位用戶對(duì)5850個(gè)服裝類(lèi)商品的192544次評(píng)分。為了方便實(shí)時(shí)推薦系統(tǒng)的評(píng)價(jià)，本文挑選了100位擁有11次評(píng)分及以上的用戶，并將他們的評(píng)分按照時(shí)間順序排序，把每個(gè)人的最晚5次評(píng)分作為歷史評(píng)分?jǐn)?shù)據(jù)，保存在redis中，第6次評(píng)分作為每個(gè)用戶觸發(fā)實(shí)時(shí)推薦的評(píng)分，后5此評(píng)分作為測(cè)試集，來(lái)評(píng)價(jià)本文實(shí)時(shí)推薦系統(tǒng)。

在不同的參數(shù)下，實(shí)時(shí)推薦模型中基礎(chǔ)評(píng)分與ALS算法的RMSE對(duì)比如圖2。

通過(guò)圖2可以看出實(shí)時(shí)推薦模型中基礎(chǔ)評(píng)分的RMSE與ALS相似，在隱特征個(gè)數(shù)為20，正則化系數(shù)是1.0時(shí)，使RMSE最小約為 1.82，可以保持一個(gè)較高的準(zhǔn)確度。

圖2 不同參數(shù)下的RMSEFig.2 RMSE under different parameters

實(shí)驗(yàn)2 對(duì)于實(shí)時(shí)推薦算法來(lái)說(shuō)，一個(gè)很關(guān)鍵的評(píng)價(jià)標(biāo)準(zhǔn)就是用戶在每一次評(píng)分之后，推薦列表是否有明顯的變化，如果每次用戶得到的推薦列表都大同小異，則會(huì)大大影響用戶體驗(yàn)。針對(duì)這個(gè)標(biāo)準(zhǔn)，本文比較了100位用戶進(jìn)行兩次實(shí)時(shí)評(píng)分之后得到的推薦列表，100位用戶平均兩次列表中不一樣商品的占比達(dá)到了98%。用戶可以很明顯的感受到實(shí)時(shí)推薦結(jié)果在隨著他們的評(píng)分在不斷變化。

圖3 ALS 算法耗時(shí)與加速比Fig.3 ALS time-consuming and speedup

圖4 相似度計(jì)算耗時(shí)與加速比Fig.4 similarity calculation time-consuming and speedup

6 結(jié)論

由于現(xiàn)實(shí)中生成的大量數(shù)據(jù)普遍以流式無(wú)結(jié)構(gòu)化或半結(jié)構(gòu)化的形式存在，這些數(shù)據(jù)都具有變化迅速，數(shù)據(jù)量大的特點(diǎn)，并且用戶對(duì)推薦列表的實(shí)時(shí)變化有較高的需求，本文設(shè)計(jì)了一種實(shí)時(shí)推薦算法，可以滿足推薦系統(tǒng)的實(shí)時(shí)推薦需求，并基于Flink設(shè)計(jì)了一個(gè)電商實(shí)時(shí)推薦系統(tǒng)。最終實(shí)驗(yàn)證明在準(zhǔn)確度、推薦列表的變化率、可擴(kuò)展度上都具有一定的優(yōu)勢(shì)。但在離線相似度計(jì)算這部分在數(shù)據(jù)量較大時(shí)耗時(shí)較久，是未來(lái)可以優(yōu)化的部分。