23 張圖,帶你入門推薦系統
做廣告業務 1 年多時間了,但是平時的工作主要和廣告工程有關,核心的廣告算法由 AI 部門支持,對我們而言可以說是「黑盒般」的存在,只需要對訓練好的模型進行調用即可。
近期,我打算系統性地學習下廣告中的搜索和推薦算法,當然更多是從工程的視角去弄清楚:算法的基本原理、以及面對線上海量數據時算法是如何解決性能問題的?整個過程,我會將有價值的技術點輸出成系列文章。
這篇文章屬於推薦系統的入門篇,本文暫不考慮線上環境的海量數據,目的是先了解清楚推薦系統的基本構成,我會通過圖解推薦算法以及程序 demo 的形式展開,內容包括:
01 走進推薦系統的世界
“啤酒與尿布” 的故事相信很多人都聽過,年輕爸爸去超市購買尿布時,經常會買點啤酒犒勞自己。因此,沃爾瑪將這兩種商品進行了捆綁銷售,最終獲得了更好的銷量。
“啤酒與尿布” 的故事
這個故事背後的理論依據就是 “推薦算法”,因爲尿布和啤酒經常出現在同一個購物車中,那麼向購買尿布的年輕爸爸推薦啤酒確實有一定道理。
- 推薦系統到底解決的是什麼問題?
推薦系統從 20 世紀 90 年代就被提出來了,但是真正進入大衆視野以及在各大互聯網公司中流行起來,還是最近幾年的事情。
隨着移動互聯網的發展,越來越多的信息開始在互聯網上傳播,產生了嚴重的信息過載。因此,如何從衆多信息中找到用戶感興趣的信息,這個便是推薦系統的價值。精準推薦解決了用戶痛點,提升了用戶體驗,最終便能留住用戶。
推薦系統本質上就是一個信息過濾系統,通常分爲:召回、排序、重排序這 3 個環節,每個環節逐層過濾,最終從海量的物料庫中篩選出幾十個用戶可能感興趣的物品推薦給用戶。
推薦系統的分階段過濾流程
- 推薦系統的應用場景
哪裏有海量信息,哪裏就有推薦系統,我們每天最常用的 APP 都涉及到推薦功能:
-
資訊類:今日頭條、騰訊新聞等
-
電商類:淘寶、京東、拼多多、亞馬遜等
-
娛樂類:抖音、快手、愛奇藝等
-
生活服務類:美團、大衆點評、攜程等
-
社交類:微信、陌陌、脈脈等
頭條、京東、網易雲音樂中的推薦功能
推薦系統的應用場景通常分爲以下兩類:
-
基於用戶維度的推薦: 根據用戶的歷史行爲和興趣進行推薦,比如淘寶首頁的猜你喜歡、抖音的首頁推薦等。
-
基於物品維度的推薦: 根據用戶當前瀏覽的標的物進行推薦,比如打開京東 APP 的商品詳情頁,會推薦和主商品相關的商品給你。
- 搜索、推薦、廣告三者的異同
搜索和推薦是 AI 算法最常見的兩個應用場景,在技術上有相通的地方。這裏提到廣告,主要考慮很多沒做過廣告業務的同學不清楚爲什麼廣告和搜索、推薦會有關係,所以做下解釋。
-
搜索: 有明確的搜索意圖,搜索出來的結果和用戶的搜索詞相關。
-
推薦: 不具有目的性,依賴用戶的歷史行爲和畫像數據進行個性化推薦。
-
廣告: 藉助搜索和推薦技術實現廣告的精準投放,可以將廣告理解成搜索推薦的一種應用場景,技術方案更復雜,涉及到智能預算控制、廣告競價等。
02 推薦系統的整體架構
推薦系統的整體架構
上面是推薦系統的整體架構圖,自下而上分成了多層,各層的主要作用如下:
-
數據源: 推薦算法所依賴的各種數據源,包括物品數據、用戶數據、行爲日誌、其他可利用的業務數據、甚至公司外部的數據。
-
計算平臺: 負責對底層的各種異構數據進行清洗、加工,離線計算和實時計算。
-
數據存儲層: 存儲計算平臺處理後的數據,根據需要可落地到不同的存儲系統中,比如 Redis 中可以存儲用戶特徵和用戶畫像數據,ES 中可以用來索引物品數據,Faiss 中可以存儲用戶或者物品的 embedding 向量等。
-
召回層: 包括各種推薦策略或者算法,比如經典的協同過濾,基於內容的召回,基於向量的召回,用於託底的熱門推薦等。爲了應對線上高併發的流量,召回結果通常會預計算好,建立好倒排索引後存入緩存中。
-
融合過濾層: 觸發多路召回,由於召回層的每個召回源都會返回一個候選集,因此這一層需要進行融合和過濾。
-
排序層: 利用機器學習或者深度學習模型,以及更豐富的特徵進行重排序,篩選出更小、更精準的推薦集合返回給上層業務。
從數據存儲層到召回層、再到融合過濾層和排序層,候選集逐層減少,但是精準性要求越來越高,因此也帶來了計算複雜度的逐層增加,這個便是推薦系統的最大挑戰。
其實對於推薦引擎來說,最核心的部分主要是兩塊:特徵和算法。
推薦引擎的核心功能和技術方案
特徵計算由於數據量大,通常採用大數據的離線和實時處理技術,像 Spark、Flink 等,然後將計算結果保存在 Redis 或者其他存儲系統中(比如 HBase、MongoDB 或者 ES),供召回和排序模塊使用。
召回算法的作用是:從海量數據中快速獲取一批候選數據,要求是快和儘可能的準。這一層通常有豐富的策略和算法,用來確保多樣性,爲了更好的推薦效果,某些算法也會做成近實時的。
排序算法的作用是:對多路召回的候選集進行精細化排序。它會利用物品、用戶以及它們之間的交叉特徵,然後通過複雜的機器學習或者深度學習模型進行打分排序,這一層的特點是計算複雜但是結果更精準。
03 圖解經典的協同過濾算法
瞭解了推薦系統的整體架構和技術方案後,下面帶大家深入一下算法細節。這裏選擇圖解的是推薦系統中的明星算法:協同過濾(Collaborative Filtering,CF)。
對於工程同學來說,可能覺得 AI 算法晦澀難懂,門檻太高,確實很多深度學習算法的確是這樣,但是協同過濾卻是一個簡單同時效果很好的算法,只要你有初中數學的基礎就能看懂。
- 協同過濾是什麼?
協同過濾算法的核心就是「找相似」,它基於用戶的歷史行爲(瀏覽、收藏、評論等),去發現用戶對物品的喜好,並對喜好進行度量和打分,最終篩選出推薦集合。它又包括兩個分支:
- 基於用戶的協同過濾: User-CF,核心是找相似的人。比如下圖中,用戶 A 和用戶 C 都購買過物品 a 和物品 b,那麼可以認爲 A 和 C 是相似的,因爲他們共同喜歡的物品多。這樣,就可以將用戶 A 購買過的物品 d 推薦給用戶 C。
基於用戶的協同過濾示例
- 基於物品的協同過濾: Item-CF,核心是找相似的物品。比如下圖中,物品 a 和物品 b 同時被用戶 A,B,C 購買了,那麼物品 a 和 物品 b 被認爲是相似的,因爲它們的共現次數很高。這樣,如果用戶 D 購買了物品 a,則可以將和物品 a 最相似的物品 b 推薦給用戶 D。
基於物品的協同過濾示例
- 如何找相似?
前面講到,協同過濾的核心就是找相似,User-CF 是找用戶之間的相似,Item-CF 是找物品之間的相似,那到底如何衡量兩個用戶或者物品之間的相似性呢?
我們都知道,對於座標中的兩個點,如果它們之間的夾角越小,這兩個點越相似,這就是初中學過的餘弦距離,它的計算公式如下:
舉個例子,A 座標是(0,3,1),B 座標是(4,3,0),那麼這兩個點的餘弦距離是 0.569,餘弦距離越接近 1,表示它們越相似。
除了餘弦距離,衡量相似性的方法還有很多種,比如:歐式距離、皮爾遜相關係數、Jaccard 相似係數等等,這裏不做展開,只是計算公式上的差異而已。
- Item-CF 的算法流程
清楚了相似性的定義後,下面以 Item-CF 爲例,詳細說下這個算法到底是如何選出推薦物品的?
第一步:整理物品的共現矩陣
假設有 A、B、C、D、E 5 個用戶,其中用戶 A 喜歡物品 a、b、c,用戶 B 喜歡物品 a、b 等等。
所謂共現,即:兩個物品被同一個用戶喜歡了。比如物品 a 和 b,由於他們同時被用戶 A、B、C 喜歡,所以 a 和 b 的共現次數是 3,採用這種統計方法就可以快速構建出共現矩陣。
第二步:計算物品的相似度矩陣
對於 Item-CF 算法來說,一般不採用前面提到的餘弦距離來衡量物品的相似度,而是採用下面的公式:
其中,N(u) 表示喜歡物品 u 的用戶數,N(v) 表示喜歡物品 v 的用戶數,兩者的交集表示同時喜歡物品 u 和物品 v 的用戶數。很顯然,如果兩個物品同時被很多人喜歡,那麼這兩個物品越相似。
基於第 1 步計算出來的共現矩陣以及每個物品的喜歡人數,便可以構造出物品的相似度矩陣:
第三步:推薦物品
最後一步,便可以基於相似度矩陣推薦物品了,公式如下:
其中,Puj 表示用戶 u 對物品 j 的感興趣程度,值越大,越值得被推薦。N(u) 表示用戶 u 感興趣的物品集合,S(j,N) 表示和物品 j 最相似的前 N 個物品,Wij 表示物品 i 和物品 j 的相似度,Rui 表示用戶 u 對物品 i 的興趣度。
上面的公式有點抽象,直接看例子更容易理解,假設我要給用戶 E 推薦物品,前面我們已經知道用戶 E 喜歡物品 b 和物品 c,喜歡程度假設分別爲 0.6 和 0.4。那麼,利用上面的公式計算出來的推薦結果如下:
因爲物品 b 和物品 c 已經被用戶 E 喜歡過了,所以不再重複推薦。最終對比用戶 E 對物品 a 和物品 d 的感興趣程度,因爲 0.682 > 0.3,因此選擇推薦物品 a。
04 從 0 到 1 搭建一個推薦系統
有了上面的理論基礎後,我們就可以用 Python 快速實現出一個推薦系統。
- 選擇數據集
這裏採用的是推薦領域非常經典的 MovieLens 數據集,它是一個關於電影評分的數據集,官網上提供了多個不同大小的版本,下面以 ml-1m 數據集(大約 100 萬條用戶評分記錄)爲例。
下載解壓後,文件夾中包含:ratings.dat、movies.dat、users.dat 3 個文件,共 6040 個用戶,3900 部電影,1000209 條評分記錄。各個文件的格式都是一樣的,每行表示一條記錄,字段之間採用 :: 進行分割。
以 ratings.dat 爲例,每一行包括 4 個屬性:UserID, MovieID, Rating, Timestamp。通過腳本可以統計出不同評分的人數分佈:
- 讀取原始數據
程序主要使用數據集中的 ratings.dat 這個文件,通過解析該文件,抽取出 user_id、movie_id、rating 3 個字段,最終構造出算法依賴的數據,並保存在變量 dataset 中,它的格式爲:dict[user_id][movie_id] = rate
3. 構造物品的相似度矩陣
基於第 2 步的 dataset,可以進一步統計出每部電影的評分次數以及電影的共生矩陣,然後再生成相似度矩陣。
4. 基於相似度矩陣推薦物品
最後,可以基於相似度矩陣進行推薦了,輸入一個用戶 id,先針對該用戶評分過的電影,依次選出 top 10 最相似的電影,然後加權求和後計算出每個候選電影的最終評分,最後再選擇得分前 5 的電影進行推薦。
5. 調用推薦系統
下面選擇 UserId=1 這個用戶,看下程序的執行結果。由於推薦程序輸出的是 movieId 列表,爲了更直觀的瞭解推薦結果,這裏轉換成電影的標題進行輸出。
最終推薦的前 5 個電影爲:
05 線上推薦系統的挑戰
通過上面的介紹,大家對推薦系統的基本構成應該有了一個初步認識,但是真正運用到線上真實環境時,還會遇到很多算法和工程上的挑戰,絕對不是幾十行 Python 代碼可以搞定的。
1、上面的示例使用了標準化的數據集,而線上環境的數據是非標準化的,因此涉及到海量數據的收集、清洗和加工,最終構造出模型可使用的數據集。
2、複雜且繁瑣的特徵工程,都說算法模型的上限由數據和特徵決定。對於線上環境,需要從業務角度選擇出可用的特徵,然後對數據進行清洗、標準化、歸一化、離散化,並通過實驗效果進一步驗證特徵的有效性。
3、算法複雜度如何降低?比如上面介紹的 Item-CF 算法,時間和空間複雜度都是 O(N×N),而線上環境的數據都是千萬甚至上億級別的,如果不做算法優化,可能幾天都跑不出數據,或者內存中根本放不下如此大的矩陣數據。
4、實時性如何滿足?因爲用戶的興趣隨着他們最新的行爲在實時變化的,如果模型只是基於歷史數據進行推薦,可能結果不夠精準。因此,如何滿足實時性要求,以及對於新加入的物品或者用戶該如何推薦,都是要解決的問題。
5、算法效果和性能的權衡。從算法角度追求多樣性和準確性,從工程角度追求性能,這兩者之間必須找到一個平衡點。
6、推薦系統的穩定性和效果追蹤。需要有一套完善的數據監控和應用監控體系,同時有 ABTest 平臺進行灰度實驗,進行效果對比。
寫在最後
這篇文章是推薦系統的入門篇,目的是讓大家對推薦系統先有一個整體的認識,後續我會再連載出一些文章,詳細地介紹面對具體業務和線上海量數據時,推薦系統應該如何設計?
歡迎關注微信公衆號:互聯網全棧架構,收取更多有價值的信息。
本文由 Readfog 進行 AMP 轉碼,版權歸原作者所有。
來源:https://mp.weixin.qq.com/s/PTncJJ8Q0UkIdPUxhGakjw