?作者 |?YBH

學校 |?上海交通大學

研究方向 |?推薦系統

我花了半個多月將推薦系統傳統算法分別進行了總結歸納，應該時目前全網最全的版本了。希望對大家了解推薦系統傳統算法有所幫助。

推薦系統的傳統算法主要包括：

• 基于鄰域的算法

• 隱語義模型

• 決策樹模型

• 邏輯回歸

基于鄰域的算法

主要介紹了 user-based CF（協同過濾），item-based CF 的原理以及他們的對比，另外還有相關代碼和優化實驗結果。詳細內容：

1.1 基于鄰域的算法（協調過濾）

1.1.1 UserCF

算法步驟：

找到和目標用戶興趣相似的用戶集合；

將集合中用戶喜歡的未出現在目標用戶的興趣列表中的 item 以一定的權值排序后推薦給用戶

用戶相似度計算：

改進：

由于很多用戶兩兩之間并沒有對同樣的物品產生過行為，用用戶-物品表計算用戶相似度很多時候計算都是浪費的，可以利用物品-用戶倒排表簡化計算。

加入熱門商品懲罰，用戶對冷門物品采取相同行為更能說明兩者的相似性

1.1.2 ItemCF

算法步驟：

計算物品之間的相似性

根據物品的相似度和用戶的歷史行為給用戶生成推薦列表

物品相似度計算：

余弦相似度

改進：

加入熱門用戶懲罰，或者直接忽略過分活躍用戶

利用用戶-物品倒排表

同類物品相似度歸一化

哈利波特問題：物品太熱門

加大對熱門物品的懲罰

兩個不同領域的熱門商品有很高的相似度

解決方法：1.引入物品的內容數據

2.對不同領域的物品降權

1.1.3 UserCF與ItemCF比較

1.1.4 UserCF與ItemCF實驗分析（基于movielens數據集）

代碼鏈接：github.com/mercurialgh/

1.2 UserCF 實驗

K 代表最當前用戶最相似的 k 個用戶，nitems 代表推薦的商品數目
不加入熱門商品懲罰：
K=8

1.nitems=5

1.nitems=10

1.nitems=20

1.nitems=40

1.nitems=160

選擇與用戶相似度最高的 8 個用戶，隨著推薦數目 k 的升高，召回率升高，準確率下降，覆蓋率升高，流行度降低，符合直觀理解。
nitems=10

1.k=4

1.k=8

1.k=16

1.k=32

1.k=160

每次推薦的數目為 10，選取的相似用戶的數量 k 從 4 到 32，召回和準確率都提升了，但是 k 從 32 到 160，對于模型沒有性能提升，反而損失了一部分性能，k 的增大會使得覆蓋率降低，商品的流行度上升。

加入熱門商品懲罰：

1.k=8,n=10，不熱門商品懲罰：

1.k=8,n=10，熱門商品懲罰

與書中描述的不同的是，我加入了懲罰項反而使得召回和準確率稍微下降了，覆蓋率提升了一點。

1.3 ItemCF實驗

K 代表與當前用戶感興趣的物品最相似的 k 個物品，nitems 表示推薦的數量
不加入活躍用戶懲罰：
K=8

1.n=5

1.n=10

1.n=20

1.n=40

選擇最相似的 8 個物品，推薦數目遞增，跟 UserCF 第一個實驗的結果一樣，召回提高，準確率下降，覆蓋率提升，商品流行度下降。
nitems=10

1.k=4

1.k=8

1.k=16

1.k=100

推薦 10 個物品，選擇最相似商品的個數 k 從 4 到 16 的時候，召回和準備率都提升了，覆蓋率下降，流行度升高。但是 k 過大時，模型的性能反而會有損失。同時響應時間也會慢很多

加入活躍用戶懲罰：

1.k=8,n=10,不加入活躍用戶懲罰：

1.k=8,n=10,加入活躍用戶懲罰：

加入活躍用戶懲罰后，模型性能有了較小的提升。
同類物品相似度歸一化

1.k=8,n=10,不進行歸一化：

1.k=8,n=10,進行歸一化：

可以看出加入歸一化后所有指標都提升了，尤其是覆蓋率提升了很多，說明同類物品歸一化是有效的。

隱語義模型

主要介紹了隱語義模型原理，矩陣分解，以及 Factorization Machine（FM）和 Field-aware Factorization Machine（FFM）的原理和推導。詳細內容：

在隱語義模型中，我們使用同樣的維度來表征（Embedding）item 和用戶。對于 item，這個表征就是 item 表現出的對應維度的特征強度；對于用戶，就是用戶表現出的對對應維度特征的偏好強度。用用戶的表征向量點乘 item 的表征向量，就可以得到用戶對該條目的偏好描述。

表示用戶 u 對 item i 的喜好程度，其中關于用戶和條目的描述維度有 k 個，這個參數是自定義的。

我們對模型的優化目標：

其中 為實際喜好值， 為 Frobenius 范數。為了抑制過擬合，需要加入正則化參數：

本質上看，隱語義模型是不含非線性過程的單層圖神經網絡。一般來講，我們觀測到的用戶對 item 的行為是很少的，用戶對大部分 item 沒有互動和喜好參數，特別是沒有顯式的負樣本。

負樣本構造應該遵循的原則：

對每個用戶，要保證正負樣本均衡

對每個用戶采樣負樣本時，要選取那些熱門，而用戶沒有行為的物品

由于有訓練過程，LFM 不能用于實時推薦，但可以作為 Hybrid System 中的一個選項。當然，也可以將 LFM 演變成 2 層神經網絡，增加其表征能力：

這種表征類似于矩陣分解（Matrix Factorization）。不過這種改進一般使 Recall 的提升在幾個百分點內，而計算量上大幅提升。為了避免計算導致的延遲，可以在模型確定之后對每個用戶計算一個推薦條目表，在部署時直接查表以免除計算過程。

2.1 Factorization Machine（FM）

針對的問題：

類別特征經過 one-hot 編碼后數據稀疏性

一些特征兩兩組合之后往往與 label 有更強的關聯性

多項式模型是比較直觀的包含特征組合的模型，二階形式如下：

特征 ， 的組合用 表示，只有當兩者都非零時才有意義，該模型的主要問題：

特征數量為 N，二次項系數為 N(N-1)/2，復雜度太高

one-hot 特征太稀疏，特征組合之后更加稀疏

FM 的模型方程：

利用了推薦系統中的矩陣分解思想，實際就是 LFM（latent factor model）隱因子模型。參數量由 N(N-1)/2 降到 k*n。

原來只有 都不為 0 時才能計算，樣本量很少，現在只要 不為 0 就可以計算，解決了樣本量的問題，并且參數量減少。

注意這里公式之所以能這么化簡，是因為我們做了假設：即每一個特征都可以用一個 k 維的隱向量來表示。但是這個假設不一定成立，例如行業（industry）特征做 one-hot 后，不同行業都用 k 維向量表示還行，但此時性別（gender）特征也用 k 維向量表示這顯然不太合理。若該假設有問題，則公式不成立。

2.2 Field-aware Factorization Machine（FFM）

FFM 將特征按不同的規則分到多個場（field），特征 屬于某個特定的場 f，每個特征 可以被映射為多個隱向量 ，每個隱向量對應一個場，當特征組合時，用特征對應的場的隱向量進行內積。

FFM 由于引入了場，使得每兩組特征交叉的隱向量都是獨立的，可以取得更好的組合效果，但是使得計算復雜度無法通過優化變成線性時間復雜度，每個樣本預測的時間復雜度為，不過 FFM 的 k 值通常遠小于 FM 的 k 值。FM 可以看做只有一個場的 FFM。

2.3 LFM和基于鄰域的方法的比較

LFM 具有比較好的理論基礎，它是一種學習方法，通過優化一個設定的指標建立最優的模型。基于鄰域的方法更多的是一種基于統計的方法，并沒有學習過程。

LFM 在生成一個用戶推薦列表時速度太慢，因此不能在線實時計算。

ItemCF 算法支持很好的推薦解釋，它可以利用用戶的歷史行為解釋推薦結果。但 LFM 無法提供這樣的解釋。

決策樹模型

主要介紹了 GBDT 的原理和推導，包括 GBDT 回歸算法，GBDT 分類算法（二分類，多分類）以及正則化。XGB 的原理和推導，正則化，節點分類準則（貪心準則，近似算法，稀疏感知等）以及工程優化原理。詳細內容：

3.1 GBDT

bdt 通過多輪迭代，每輪迭代產生一個弱分類器，每個分類器在上一輪分類器的殘差基礎上進行訓練。對弱分類器的要求一般是足夠簡單，并且是低方差和高偏差的。因為訓練的過程是通過降低偏差來不斷提高最終分類器的精度。

弱分類器一般會選擇為 CART（也就是分類回歸樹）。由于上述高偏差和簡單的要求每個分類回歸樹的深度不會很深。最終的總分類器是將每輪訓練得到的弱分類器加權求和得到的（加法模型）。

算法流程如下：

1. 初始化

2. 對 t=1，2，3，...T，

• 計算殘差?

• 擬合殘差學習得到弱分類器?

• 得到新的強學習器?

3. 樹的深度達到閾值或者殘差小于閾值，得到最終的強學習器

3.1.1 GBDT回歸算法

假設訓練集樣本 ，最大迭代次數 T，損失函數 L，輸出的強學習器 ，回歸算法的流程如下：

1. 初始化弱學習器，c 的值可以設為樣本 y 的均值?

2. 對迭代次數 t=1,...T；

• 對樣本 i=1,...m；計算梯度

• 利用 ，擬合一顆 CART 樹，得到第 t 棵回歸樹，其對應的葉子節點區域為 ，j=1,2,..J。其中 J 為回歸樹 t 的葉子節點個數。

• 對葉子區域 j=1,2,3,…,J，計算最佳擬合值：

• 更新強學習器

3. 得到最終的強學習器

3.1.2 GBDT分類算法

GBDT 分類算法在思想上和回歸算法沒有區別，但是由于樣本輸出不是連續的值，而是離散的類別，導致我們無法直接從輸出類別去擬合類別輸出的誤差。為解決此問題，我們嘗試用類似于邏輯回歸的對數似然損失函數的方法，也就是說我們用的是類別的預測概率值和真實概率值來擬合損失函數。對于對數似然損失函數，我們有二元分類和多元分類的區別。

1. 二分類

對于二元 GBDT，如果用類似于邏輯回歸的對數似然損失函數，則損失函數表示為 ，其中 ，此時的負梯度誤差為

由于上式比較難優化，我們一般使用近似值代替：

除了負梯度計算和葉子節點的最佳殘差擬合的線性搜索外，二元 GBDT 分類和 GBDT 回歸算法過程相同。

2. 多分類

多元 GBDT 要比二元 GBDT 復雜一些，對應的是多元邏輯回歸和二元邏輯回歸的復雜度差別。假如類別數為 K，則我們的對數似然函數為：

其中如果樣本輸出類別為 k，則 ，第 k 類的概率 的表達式為：

集合上兩式，我們可以計算出第 t 輪的第 i 個樣本對應類別 l 的負梯度誤差為：

其實這里的誤差就是樣本 i 對應類別l的真實概率和 t-1 輪預測概率的差值。對于生成的決策樹，我們各個葉子節點的最佳殘差擬合值為：

由于上式比較難優化，我們用近似值代替：

除了負梯度計算和葉子節點的最佳殘差擬合的線性搜索，多元 GBDT 分類和二元 GBDT 分類以及 GBDT 回歸算法過程相同。

3.1.3 正則化

和 Adaboost 一樣，我們也需要對 GBDT 進行正則化，防止過擬合。GBDT 的正則化主要有 3 種方式：learning_rate（學習率）；subsample（子采樣比例）；min_samples_split（葉子結點包含的最小樣本數）。?

針對 GBDT 正則化，我們通過子采樣比例方法和定義步長 v 方法來防止過擬合。

1. learning_rate。學習率是正則化的一部分，它可以降低模型更新的速度（需要更多的迭代）。通常我們用 learning_rate 和最大迭代次數一起來決定算法的擬合效果。

• 經驗表明：一個小的學習率（v<0.1）可以顯著提高模型的泛化能力（相比較于 v=1）。

• 如果學習率較大會導致預測性能出現較大波動。

2. subsample，子采樣比例。Freidman 從 bagging 策略受到啟發，采用隨機梯度提升來修改了原始的梯度提升樹算法。

每一輪迭代中，新的決策樹擬合的是原始訓練集的一個子集（而并不是原始訓練集）的殘差。這個子集是通過對原始訓練集的無放回隨機采樣而來。無放回抽樣的子采樣比例（subsample），取值為 (0,1]。如果取值為 1，則與原始的梯度提升樹算法相同，即使用全部樣本。

如果取值小于 1，則使用部分樣本去做決策樹擬合。較小的取值會引入隨機性，有助于改善過擬合，因此可以視作一定程度上的正則化；但是 會增加樣本擬合的偏差，因此取值不能太低。推薦在 [0.5, 0.8] 之間。這種方法除了改善過擬合之外，另一個好處是：未被采樣的另一部分子集可以用來計算包外估計誤差。因此可以避免額外給出一個獨立的驗證集。

3. min_samples_split，葉子結點包含的最小樣本數。梯度提升樹會限制每棵樹的葉子結點包含的樣本數量至少包含 m 個樣本，其中m為超參數。在訓練過程中，一旦劃分結點會導致子結點的樣本數少于 m，則終止劃分。

3.2 XGB

3.2.1 算法原理

和 GBDT 一樣，XGBoost 是一個加法模型，在每一步迭代中只優化當前步中的子模型。在第 m 步中：

目標函數為經驗風險+結構風險（正則項）：

由

可以得到上式二階泰勒展開：

前 m-1 個子模型已經確定了，故上式中除了關于 的部分都是常數，不影響對 的優化求解。目標函數可轉化為：

其中：

這里的L是損失函數，度量一次預測的好壞。在 確定了的情況下，對每個樣本點i都可以輕易計算出一個 和 。

3.2.2 xgb的正則化

為防止過擬合，XGBoost 設置了基于樹的復雜度作為正則項：

T 為樹 f 的葉節點個數，w 為所有葉節點輸出回歸值構成的向量，由（1），（2）可知：

接下來通過一個數學處理，可以使得正則項和經驗風險項合并到一起。經驗風險項是在樣本層面上求和，我們將其轉換為葉節點層面上的求和。

3.2.3 節點分裂準則

1. 貪心準則

XGBoost 的子模型樹和決策樹模型一樣，要依賴節點遞歸分裂的貪心準則來實現樹的生成。除此外，XGBoost 還支持近似算法，解決數據量過大超過內存、或有并行計算需求的情況。

基本思路和 CART 一樣，對特征值排序后遍歷劃分點，將其中最優的分裂收益作為該特征的分裂收益，選取具有最優分裂收益的特征作為當前節點的劃分特征，按其最優劃分點進行二叉劃分，得到左右子樹。

上圖是一次節點分裂過程，很自然地，分裂收益是樹 A 的評分減去樹 B 的評分。虛線框外的葉節點，即非分裂節點的評分均被抵消，只留下分裂后的 LR 節點和分裂前的 S 節點進行比較，因此分裂收益的表達式為：

2. 近似算法

XGBoost 還提供了上述貪心準則的近似版本，簡言之，將特征分位數作為劃分候選點。 這樣將劃分候選點集合由全樣本間的遍歷縮減到了幾個分位數之間的遍歷。

具體而言，特征分位數的選取有 global 和 local 兩種可選策略：global 在全體樣本上的特征值中選取，在根節點分裂之前進行一次即可；local 則是在待分裂節點包含的樣本特征值上選取，每個節點分裂前都要進行。通常，global 由于只能劃分一次，其劃分粒度需要更細。

在 XGB 原始論文中，作者在 Higgs Boson 數據集上比較了精確貪心準則、global 近似和 local 近似三類配置的測試集 AUC，用 eps 代表取分位點的粒度，如 eps=0.25 代表將數據集劃分為 1/0.25=4 個 buckets，發現 global（eps=0.05）和 local（eps=0.3）均能達到和精確貪心準則幾乎相同的性能。

這三類配置在 XGBoost 包均有支持。

3. 加權分位數

查看（1）式表示的目標函數，令偏導為 0 易得

此目標函數可理解為以 為權重， 為標簽的二次損失函數：

因此，在近似算法取分位數時，實際上 XGBoost 會取以二階導 為權重的分位數。

4. 列采樣和學習率

XGBoost 還引入了兩項特性：列采樣和學習率。

列采樣，即隨機森林中的做法，每次節點分裂的待選特征集合不是剩下的全部特征，而是剩下特征的一個子集。是為了更好地對抗過擬合（我不是很清楚 GBDT 中列采樣降低過擬合的理論依據。原文這里提到的動機是某 GBDT 的軟件用戶反饋列采樣比行采樣更能對抗過擬合），還能減少計算開銷。

學習率，或者叫步長、shrinkage，是在每個子模型前（即在每個葉節點的回歸值上）乘上該系數，削弱每顆樹的影響，使得迭代更穩定。可以類比梯度下降中的學習率。XGBoost 默認設定為 0.3。

5. 稀疏感知

缺失值應對策略是算法需要考慮的。特征稀疏問題也同樣需要考慮，如部分特征中出現大量的 0 或干脆是 one-hot encoding 這種情況。XGBoost 用稀疏感知策略來同時處理這兩個問題：概括地說，將缺失值和稀疏 0 值等同視作缺失值，再將這些缺失值“綁定”在一起，分裂節點的遍歷會跳過缺失值的整體。這樣大大提高了運算效率。

分裂節點依然通過遍歷得到，NA 的方向有兩種情況，在此基礎上對非缺失值進行切分遍歷。或者可以理解 NA 被分到一個固定方向，非缺失值在升序和降序兩種情況下進行切分遍歷。

如上圖所示，若某個特征值取值為 1,2,5 和大量的 NA，XGBoost 會遍歷以上 6 種情況（3 個非缺失值的切分點 × 缺失值的兩個方向），最大的分裂收益就是本特征上的分裂收益，同時，NA 將被分到右節點。

3.2.4 工程優化

1. 并行列塊設計

XGBoost 將每一列特征提前進行排序，以塊（Block）的形式儲存在緩存中，并以索引將特征值和梯度統計量 對應起來，每次節點分裂時會重復調用排好序的塊。而且不同特征會分布在獨立的塊中，因此可以進行分布式或多線程的計算。

2. 緩存訪問

特征值排序后通過索引來取梯度 會導致訪問的內存空間不一致，進而降低緩存的命中率，影響算法效率。為解決這個問題，XGBoost 為每個線程分配一個單獨的連續緩存區，用來存放梯度信息。

3. 核外塊計算

數據量過大時，不能同時全部載入內存。XGBoost 將數據分為多個 blocks 并儲存在硬盤中，使用一個獨立的線程專門從磁盤中讀取數據到內存中，實現計算和讀取數據的同時進行。為了進一步提高磁盤讀取數據性能，XGBoost 還使用了兩種方法：一是通過壓縮 block，用解壓縮的開銷換取磁盤讀取的開銷；二是將 block 分散儲存在多個磁盤中，有助于提高磁盤吞吐量。

3.2.5 與GBDT比較

• 性質：GBDT 是機器學習算法，XGBoost 除了算法內容還包括一些工程實現方面的優化。

• 基于二階導：GBDT 使用的是損失函數一階導數，相當于函數空間中的梯度下降；而 XGBoost 還使用了損失函數二階導數，相當于函數空間中的牛頓法。

• 正則化：XGBoost 顯式地加入了正則項來控制模型的復雜度，能有效防止過擬合。

• 列采樣：XGBoost 采用了隨機森林中的做法，每次節點分裂前進行列隨機采樣。

• 缺失值處理：XGBoost 運用稀疏感知策略處理缺失值，而 GBDT 沒有設計缺失策略。

• 并行高效：XGBoost 的列塊設計能有效支持并行運算，提高效率。

邏輯回歸

主要介紹了邏輯回歸的原理和如何在推薦上應用。詳細內容：

在推薦系統中，可以將是否點擊一個商品看成一個概率事件，被推薦的商品無非兩種可能性：1.被點擊；2.不被點擊。那么就可以將這個推薦問題轉換成一個分類問題。邏輯回歸是監督學習中的分類算法，所以可以使用邏輯回歸來進行一個分類預測。

邏輯回歸模型能夠綜合利用用戶，物品，上下文等多種不同的特征生成較全面的推薦結果。

算法步驟

（1）將用戶年齡、性別、物品屬性、物品描述、當前時間、當前地點等特征轉換成數值型特征向量；

（2）確定邏輯回歸模型的優化目標（以優化點擊率為例），利用已有樣本數據對邏輯回歸模型進行訓練，確定邏輯回歸模型的內部參數

（3）在模型服務階段，將特征向量輸入邏輯回歸模型，經過邏輯回歸模型的推斷，得到用戶“點擊”物品的概率

（4）利用“點擊概率”對所有候選物品進行排序，得到推薦列表

LR的數學形式如下：

其中 ，假設 ，，則 。

所以邏輯回歸實際上就是在線性回歸的基礎上加了 ，而這個就是所謂的 sigmoid 函數。可以看這篇詳細的解答：

https://www.zhihu.com/question/23666587/answer/462453898

LR的缺陷：

LR 假設各特征間是相互獨立的，忽略了特征間的交互關系，因此需要做大量的特征工程。同時 LR 對非線性的擬合能力較差，限制了模型的性能上限。通常LR可以作為 Baseline 版本。

這里有用邏輯回歸做電影推薦的 github 項目，有興趣的小伙伴可以實操一下：

https://github.com/LawsonAbs/MovieRecommend

這些傳統算法的思想后續在深度學習應用到推薦系統中都有很多相關的模型，比如 facebook 將協同過濾和深度學習結合的 DLRM，以及后面的 DeepFM，Wide&Deep，Deep&Cross，以及將 Facebook 將 GBDT+LR 結合的方法一度成為業內都使用的模型。所以了解這些算法對于提升自己時很有幫助的。

最后如果有錯誤希望大家指出，希望和大家一起交流，一起進步！

特別鳴謝

感謝 TCCI 天橋腦科學研究院對于 PaperWeekly 的支持。TCCI 關注大腦探知、大腦功能和大腦健康。

更多閱讀

#投 稿?通 道#

?讓你的文字被更多人看到?

如何才能讓更多的優質內容以更短路徑到達讀者群體，縮短讀者尋找優質內容的成本呢？答案就是：你不認識的人。

總有一些你不認識的人，知道你想知道的東西。PaperWeekly 或許可以成為一座橋梁，促使不同背景、不同方向的學者和學術靈感相互碰撞，迸發出更多的可能性。?

PaperWeekly 鼓勵高校實驗室或個人，在我們的平臺上分享各類優質內容，可以是最新論文解讀，也可以是學術熱點剖析、科研心得或競賽經驗講解等。我們的目的只有一個，讓知識真正流動起來。

📝?稿件基本要求：

? 文章確系個人原創作品，未曾在公開渠道發表，如為其他平臺已發表或待發表的文章，請明確標注?

? 稿件建議以?markdown?格式撰寫，文中配圖以附件形式發送，要求圖片清晰，無版權問題

? PaperWeekly 尊重原作者署名權，并將為每篇被采納的原創首發稿件，提供業內具有競爭力稿酬，具體依據文章閱讀量和文章質量階梯制結算

📬?投稿通道：

? 投稿郵箱：hr@paperweekly.site?

? 來稿請備注即時聯系方式（微信），以便我們在稿件選用的第一時間聯系作者

? 您也可以直接添加小編微信（pwbot02）快速投稿，備注：姓名-投稿

△長按添加PaperWeekly小編

🔍

現在，在「知乎」也能找到我們了

進入知乎首頁搜索「PaperWeekly」

點擊「關注」訂閱我們的專欄吧

·

總結

以上是生活随笔為你收集整理的史上最全推荐系统传统算法合集的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。