徐細林，李毅

（四川大學計算機學院，成都 610065）

0 引言

筆者在某家互聯(lián)網(wǎng)公司承擔過視頻直播和電臺的推薦系統(tǒng)的設計和開發(fā)工作，矩陣分解算法是所用到的推薦策略中的一種。筆者將在這里詳細介紹矩陣分解算法如何運用在有大量用戶的手機App或者網(wǎng)站的推薦系統(tǒng)上。

一個活躍度較高的App每天會產(chǎn)生很多新的內(nèi)容，每天會有大量用戶去點擊觀看，如何找出用戶喜歡看的內(nèi)容推薦給用戶成為一個關鍵性的問題。

對于一個大型的直播app來說，每日的活躍用戶在幾千萬左右，活躍主播在數(shù)十萬左右。如何做個性化推薦，在數(shù)十萬個主播中找出每個用戶他喜歡的數(shù)十到數(shù)百個主播是推薦系統(tǒng)要解決的問題。

1 數(shù)據(jù)收集和數(shù)據(jù)預處理

每天用戶打開App后，用戶會對展示給用戶的主播或者電臺進行點擊、觀看、打賞。通過Nginx+kafka來收集這些用戶的日志數(shù)據(jù)。對收集的JSON數(shù)據(jù)做簡單解析后以天為分區(qū)存入到hive當中。

在不能直接獲取到用戶對item的評分時，充分利用最可能表達用戶對item的喜好程度的觀看時長和打賞這兩項數(shù)據(jù)來表示用戶對主播的評分。

依據(jù)存入到hive當中的數(shù)據(jù)，獲取每天單個用戶對每一個主播的打賞金額p和觀看時長t，以s=1000*p+t作為單個用戶對單個主播的評價基本依據(jù)。計算從當前往過去推15天的用戶-主播的累加的s值。

由此可以得到一張具有用戶id，主播id，評價值s這三個字段的二維表。對評價值s這一個字段的具體數(shù)值做一個min-max標準化：

為了防止作弊的情況以及頭部主播流量過于聚焦，smax不直接取最大的數(shù)，一般取前1%大的數(shù)。對于超出smax的數(shù)，直接設置為1，小于smax的數(shù)，直接用min-max公式計算即可。

數(shù)據(jù)標準化之后，用戶id，主播id，評價值s*這三個字段的二維表寫入到hive當中，這張二維表就可以直接作為數(shù)據(jù)源來直接使用。

2 矩陣分解和als算法

矩陣分解即把一個矩陣分解成多個小矩陣的乘積。在推薦系統(tǒng)中，一般是會把一個大的矩陣分解成兩個小矩陣的乘積。

如表1所示，在這里user指用戶，item指主播。矩陣中的值代表某用戶對某播主的評價（標準化后的觀看時長和打賞金額之間的轉(zhuǎn)化值）。為空的表示該用戶對該主播之前沒有交互，是需要求解預測的值。

表1

在大型應用中由于用戶數(shù)和item數(shù)都非常龐大，那么矩陣就會非常大，會遠遠超出單機所能計算的規(guī)模。由此需要用分布式系統(tǒng)來處理。

User和item之間有多個關聯(lián)維度（例如性別、年齡、各種風格等），我們只需要把評價矩陣R投射在這些維度上即可。設維度為k，那么可以表示為：

圖1 大矩陣R拆分成兩個小矩陣

一般情況下k的值會遠小于m和n的值，這樣達到降維的目的。k的值一般取20-100之間，不需要顯示定義這些關聯(lián)維度，假設他們存在即可。

分解后的兩個小矩陣相乘即可填充稀疏矩陣R中的空值。

那么問題轉(zhuǎn)化成找出合適的矩陣U和矩陣V，使得這兩個分解矩陣相乘所得的積與初始評分矩陣R之間的差的平方最小。為了防止過擬合，引入正則化項。那么損失函數(shù)為：

上面的公式直接優(yōu)化并不容易，可以u和v的二元導數(shù)并不容易計算。采用交替最小二乘法（ALS），即交替固定其中一個維度，而去優(yōu)化另一個維度來優(yōu)化損失函數(shù)。

首先對ui求導，可得：

令偏導數(shù)為0，即：

可得：

同理可得 vj=(UTU+λI)-1UTrj（2）

算法詳細步驟如下：

初始化U，V；

（2）開始迭代，直到損失函數(shù)J的值小于設定的數(shù)或者迭代次數(shù)大于設定的次數(shù)；

①固定v，使用公式1來更新ui；

②固定u，使用公式2來更新vj；

（3）達到（2）中設定的迭代終止條件，得到的U和V即為所要求的矩陣。

分解得到的U和V矩陣相乘，即可得到用戶對item的評分值。

3 在Spark中使用矩陣分解做推薦系統(tǒng)

對于大規(guī)模推薦系統(tǒng)，數(shù)據(jù)量會遠遠超出單機能處理的能力。一般會使用基于Spark計算引擎的分布式系統(tǒng)來處理推薦系統(tǒng)問題。

在數(shù)據(jù)預處理過程當中，已經(jīng)獲得一張每個用戶對每個主播評價的二維表。

Spark中的機器學習庫MLlib當中已經(jīng)集成了ALS，使用時直接調(diào)用就可以。在訓練過程當中需要設置以下四個參數(shù)：

rating：由用戶-物品矩陣構(gòu)成的訓練集；

rank：即k，表示矩陣分解的維度，一般設置在20到100之間；

numIterations:迭代次數(shù)；

lambda：正則項的懲罰系數(shù)。

訓練好的U和V兩個矩陣相乘，即可得到最終的評分矩陣T。獲取每個user中的評分最高的500個item，就是所推薦的結(jié)果。

接下來需要調(diào)參，最大化矩陣分解算法的推薦效果。在離線測試中，對比某一天的推薦內(nèi)容和該天用戶實際點擊、觀看、付費的節(jié)目來判斷推薦效果。但是由于過去沒有使用矩陣分解算法，這樣不能較好地反應實際情況，只能做一個參考。

初步調(diào)完參之后，選擇上線。給予10%的流量，觀測推薦效果。在上線的兩周內(nèi)，每天調(diào)整參數(shù)，使得該算法的推薦效果接近于最優(yōu)。

4 使用堆排序解決als中的笛卡兒積帶來的問題

在使用Spark中的MLlib庫中的ALS時，在對訓練好的模型進行預測時，如果直接調(diào)用recommend-ProductsForUsers（n），給每個用戶推薦最值得推薦的n個item時，不僅會極大的占用內(nèi)存資源，計算時長往往會超過1個小時，遠遠達不到系統(tǒng)推薦的需求，為此我們對spark在als這一塊做了優(yōu)化。

讀一下recommendProductsForUsers這個函數(shù)的源碼，我們發(fā)現(xiàn)函數(shù)對user和item做了一次crossjoin（笛卡爾乘積），而在實際業(yè)務中對1000萬的活躍用戶數(shù)和30萬的活躍主播數(shù)做一次笛卡爾乘積，會產(chǎn)生一張3萬億的用戶對主播的評分表，這極大占用了內(nèi)存，消耗了過多的計算資源。

而在實際業(yè)務中我們只需要獲得的是每個用戶最高評分的500個主播，并不需要保留單個用戶對所有主播的評分。我們自己構(gòu)造了一個函數(shù)，是用堆排序來做的。算法如下。

單個用戶的userfeatures和單個itemfeatures相乘，得到單個用戶對單個item的評分

如果評分數(shù)量小于500，對item加1，重復（1）的計算過程，直到滿500個為止。

對這500個評分構(gòu)建一個最小堆，堆頂為最小數(shù)s。

重復（1）的計算過程，繼續(xù)對item做迭代（直到所有item迭代完為止），如果新的評分大于最小堆堆頂?shù)臄?shù)s，那么替換s，并對最小堆做調(diào)整，使得其滿足最小堆的條件。

通過（4），最終獲得單個用戶在矩陣分解中評分最高的500個item，這也是最終給用戶所推薦的

對每一個用戶重復（1）到（5），最終獲得每個用戶最值得推薦的500個item。

通過上述算法，我們把內(nèi)存消耗降低了90%，預測時間由原來的1個多小時減少到9分鐘。

5 效果評測（與原有的算法效果比）

上線兩周后,和原有的方法做一些比較。主要評價指標有 CTR（Click-Through-Rate），ATU（Average Time Per User），ARPU（Average Revenue Per User）這三項。

CTR即點擊通過率，表示item的實際點擊次數(shù)除以該item獲得的曝光量。ATU即用戶平均觀看時長，指的是在一個周期內(nèi)用戶點擊進入各個直播間觀看的總時長除以進入的直播間數(shù)量。ARPU指的是在一個周期內(nèi)總收入除以活躍用戶數(shù)量。

下表表示基于item的協(xié)同過濾，基于user的協(xié)同過濾，熱門篩選和矩陣分解這四種策略在一周內(nèi)平均每天在評價指標上的表現(xiàn)。

表2 幾種算法在各個評價維度的分值

觀察可知，矩陣分解在CTR和ARPU兩個指標上表現(xiàn)最好，尤其是在ARPU上的表現(xiàn)出人意料?？梢蕴岣咂浞峙淞髁勘壤?，把矩陣分解作為個性化推薦系統(tǒng)的主要策略之一。

6 結(jié)語

本文從數(shù)據(jù)采集、數(shù)據(jù)預處理到矩陣分解算法運用以及預測階段算法改進，完整地實現(xiàn)了一套如何在大規(guī)模系統(tǒng)上通過矩陣分解算法做推薦系統(tǒng)，從而優(yōu)化了CTR指標，提升了ARPU值，具有極大的實用價值。

參考文獻：

[1]Zhou R,Khemmarat S,Gao L.The Impact of YouTube Recommendation System on Video Views[C].ACM SIGCOMM Conference on Internet Measurement 2010,Melbourne,Australia-November.DBLP,2010:404-410.

[2]Felfernig A,Jeran M,Ninaus G,et al.Toward the Next Generation of Recommender Systems:Applications and Research Challenges[M].Multimedia Services in Intelligent Environments.Springer International Publishing,2013:734-749.

[3]Lü L,Medo M,Chi H Y,et al.Recommender Systems[J].Physics Reports,2012,519（1）:1-49.

[4]李改,李磊.基于矩陣分解的協(xié)同過濾算法[J].計算機工程與應用,2011,47（30）:4-7.