被“推薦系統”虐的日子，太慘了...
做廣告業務 1 年多時間了，但是平時的工作主要和廣告工程有關，核心的廣告算法由 AI 部門支持，對我們而言可以說是「黑盒般」的存在，只需要對訓練好的模型進行調用即可。
圖片來自 Pexels
近期，我打算系統性地學習下廣告中的搜索和推薦算法，當然更多是從工程的視角去弄清楚：算法的基本原理、以及面對線上海量數據時算法是如何解決性能問題的?整個過程，我會將有價值的技術點輸出成系列文章。
這篇文章屬于推薦系統的入門篇，本文暫不考慮線上環境的海量數據，目的是先了解清楚推薦系統的基本構成。
我會通過圖解推薦算法以及程序 demo 的形式展開，內容包括：
走進推薦系統的世界
“啤酒與尿布” 的故事相信很多人都聽過，年輕爸爸去超市購買尿布時，經常會買點啤酒犒勞自己。
因此，沃爾瑪將這兩種商品進行了捆綁銷售，最終獲得了更好的銷量。
“啤酒與尿布”的故事
這個故事背后的理論依據就是 “推薦算法”，因為尿布和啤酒經常出現在同一個購物車中，那么向購買尿布的年輕爸爸推薦啤酒確實有一定道理。
推薦系統到底解決的是什么問題?
推薦系統從 20 世紀 90 年代就被提出來了，但是真正進入大眾視野以及在各大互聯網公司中流行起來，還是最近幾年的事情。
隨著移動互聯網的發展，越來越多的信息開始在互聯網上傳播，產生了嚴重的信息過載。
因此，如何從眾多信息中找到用戶感興趣的信息，這個便是推薦系統的價值。精準推薦解決了用戶痛點，提升了用戶體驗，最終便能留住用戶。
推薦系統本質上就是一個信息過濾系統，通常分為：召回、排序、重排序這 3 個環節，每個環節逐層過濾，最終從海量的物料庫中篩選出幾十個用戶可能感興趣的物品推薦給用戶。
推薦系統的分階段過濾流程
推薦系統的應用場景
頭條、京東、網易云音樂中的推薦功能
哪里有海量信息，哪里就有推薦系統，我們每天最常用的 APP 都涉及到推薦功能：
- 資訊類：今日頭條、騰訊新聞等。
- 電商類：淘寶、京東、拼多多、亞馬遜等。
- 娛樂類：抖音、快手、愛奇藝等。
- 生活服務類：美團、大眾點評、攜程等。
- 社交類：微信、陌陌、脈脈等。
推薦系統的應用場景通常分為以下兩類：
- 基于用戶維度的推薦：根據用戶的歷史行為和興趣進行推薦，比如淘寶首頁的猜你喜歡、抖音的首頁推薦等。
- 基于物品維度的推薦：根據用戶當前瀏覽的標的物進行推薦，比如打開京東 APP 的商品詳情頁，會推薦和主商品相關的商品給你。
搜索、推薦、廣告三者的異同
搜索和推薦是 AI 算法最常見的兩個應用場景，在技術上有相通的地方。
這里提到廣告，主要考慮很多沒做過廣告業務的同學不清楚為什么廣告和搜索、推薦會有關系，所以做下解釋：
- 搜索：有明確的搜索意圖，搜索出來的結果和用戶的搜索詞相關。
- 推薦：不具有目的性，依賴用戶的歷史行為和畫像數據進行個性化推薦。
- 廣告：借助搜索和推薦技術實現廣告的精準投放，可以將廣告理解成搜索推薦的一種應用場景，技術方案更復雜，涉及到智能預算控制、廣告競價等。
推薦系統的整體架構
推薦系統的整體架構
上面是推薦系統的整體架構圖，自下而上分成了多層，各層的主要作用如下：
- 數據源：推薦算法所依賴的各種數據源，包括物品數據、用戶數據、行為日志、其他可利用的業務數據、甚至公司外部的數據。
- 計算平臺：負責對底層的各種異構數據進行清洗、加工，離線計算和實時計算。
- 數據存儲層：存儲計算平臺處理后的數據，根據需要可落地到不同的存儲系統中，比如 Redis 中可以存儲用戶特征和用戶畫像數據，ES 中可以用來索引物品數據，Faiss 中可以存儲用戶或者物品的 embedding 向量等。
- 召回層：包括各種推薦策略或者算法，比如經典的協同過濾，基于內容的召回，基于向量的召回，用于托底的熱門推薦等。為了應對線上高并發的流量，召回結果通常會預計算好，建立好倒排索引后存入緩存中。
- 融合過濾層：觸發多路召回，由于召回層的每個召回源都會返回一個候選集，因此這一層需要進行融合和過濾。
- 排序層：利用機器學習或者深度學習模型，以及更豐富的特征進行重排序，篩選出更小、更精準的推薦集合返回給上層業務。
從數據存儲層到召回層、再到融合過濾層和排序層，候選集逐層減少，但是精準性要求越來越高，因此也帶來了計算復雜度的逐層增加，這個便是推薦系統的最大挑戰。
其實對于推薦引擎來說，最核心的部分主要是兩塊：特征和算法。
推薦引擎的核心功能和技術方案
特征計算由于數據量大，通常采用大數據的離線和實時處理技術，像 Spark、Flink 等，然后將計算結果保存在 Redis 或者其他存儲系統中(比如 HBase、MongoDB 或者 ES)，供召回和排序模塊使用。
召回算法的作用是：從海量數據中快速獲取一批候選數據，要求是快和盡可能的準。
這一層通常有豐富的策略和算法，用來確保多樣性，為了更好的推薦效果，某些算法也會做成近實時的。
排序算法的作用是：對多路召回的候選集進行精細化排序。它會利用物品、用戶以及它們之間的交叉特征，然后通過復雜的機器學習或者深度學習模型進行打分排序，這一層的特點是計算復雜但是結果更精準。
圖解經典的協同過濾算法
了解了推薦系統的整體架構和技術方案后，下面帶大家深入一下算法細節。這里選擇圖解的是推薦系統中的明星算法：協同過濾(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。
從 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：
構造物品的相似度矩陣
基于第 2 步的 dataset，可以進一步統計出每部電影的評分次數以及電影的共生矩陣，然后再生成相似度矩陣。
基于相似度矩陣推薦物品
最后，可以基于相似度矩陣進行推薦了，輸入一個用戶 id，先針對該用戶評分過的電影，依次選出 top 10 最相似的電影，然后加權求和后計算出每個候選電影的最終評分，最后再選擇得分前 5 的電影進行推薦。
調用推薦系統
下面選擇 UserId=1 這個用戶，看下程序的執行結果。由于推薦程序輸出的是 movieId 列表，為了更直觀的了解推薦結果，這里轉換成電影的標題進行輸出。
最終推薦的前 5 個電影為：
線上推薦系統的挑戰
通過上面的介紹，大家對推薦系統的基本構成應該有了一個初步認識，但是真正運用到線上真實環境時，還會遇到很多算法和工程上的挑戰，絕對不是幾十行 Python 代碼可以搞定的。
主要總結如下幾點：
- 上面的示例使用了標準化的數據集，而線上環境的數據是非標準化的，因此涉及到海量數據的收集、清洗和加工，最終構造出模型可使用的數據集。
- 復雜且繁瑣的特征工程，都說算法模型的上限由數據和特征決定。對于線上環境，需要從業務角度選擇出可用的特征，然后對數據進行清洗、標準化、歸一化、離散化，并通過實驗效果進一步驗證特征的有效性。
- 算法復雜度如何降低?比如上面介紹的 Item-CF 算法，時間和空間復雜度都是 O(N×N)，而線上環境的數據都是千萬甚至上億級別的，如果不做算法優化，可能幾天都跑不出數據，或者內存中根本放不下如此大的矩陣數據。
- 實時性如何滿足?因為用戶的興趣隨著他們最新的行為在實時變化的，如果模型只是基于歷史數據進行推薦，可能結果不夠精準。
- 因此，如何滿足實時性要求，以及對于新加入的物品或者用戶該如何推薦，都是要解決的問題。
- 算法效果和性能的權衡。從算法角度追求多樣性和準確性，從工程角度追求性能，這兩者之間必須找到一個平衡點。
- 推薦系統的穩定性和效果追蹤。需要有一套完善的數據監控和應用監控體系，同時有 ABTest 平臺進行灰度實驗，進行效果對比。
寫在最后
這篇文章是推薦系統的入門篇，目的是讓大家對推薦系統先有一個整體的認識，后續我會再連載出一些文章，詳細地介紹面對具體業務和線上海量數據時，推薦系統應該如何設計?
作者：駱俊武
編輯：陶家龍
出處：轉載自公眾號 IT 人的職場進階
