矩陣分解在大規模個性化推薦系統中的實際應用

徐細林，李毅

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

0 引言

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

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

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

1 數據收集和數據預處理

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

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

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

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

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

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

2 矩陣分解和als算法

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

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

表1

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

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

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

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

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

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

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

首先對ui求導，可得：

令偏導數為0，即：

可得：

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

算法詳細步驟如下：

初始化U，V；

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

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

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

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

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

3 在Spark中使用矩陣分解做推薦系統

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

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

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

rating：由用戶-物品矩陣構成的訓練集；

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

numIterations:迭代次數；

lambda：正則項的懲罰系數。

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

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

初步調完參之后，選擇上線。給予10%的流量，觀測推薦效果。在上線的兩周內，每天調整參數，使得該算法的推薦效果接近于最優。

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

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

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

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

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

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

對這500個評分構建一個最小堆，堆頂為最小數s。

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

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

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

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

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

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

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

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

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

觀察可知，矩陣分解在CTR和ARPU兩個指標上表現最好，尤其是在ARPU上的表現出人意料。可以提高其分配流量比例，把矩陣分解作為個性化推薦系統的主要策略之一。

6 結語

本文從數據采集、數據預處理到矩陣分解算法運用以及預測階段算法改進，完整地實現了一套如何在大規模系統上通過矩陣分解算法做推薦系統，從而優化了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]李改,李磊.基于矩陣分解的協同過濾算法[J].計算機工程與應用,2011,47（30）:4-7.