萬字長文 | 10種傳統機器學習演算法，阿里工程師總結 | 下

知識 01-15

在這篇文章中我們將介紹10種常見的推薦演算法，並且列舉一些實際的例子，希望能對你的推薦演算法學習帶來些許幫助。

1基於CF的推薦演算法

1.1演算法簡介

CF（協同過濾）簡單來形容就是利用興趣相投的原理進行推薦，協同過濾主要分兩類，一類是基於物品的協同過濾演算法，另一種是基於用戶的協同過濾演算法，這裡主要介紹基於物品的協同過濾演算法。

給定一批用戶，及一批物品，記Vi表示不同用戶對物品的評分向量，那麼物品i與物品j的相關性為：

上述公式是利用餘弦公式計算相關係數，相關係數的計算還有：傑卡德相關係數、皮爾遜相關係數等。

計算用戶u對某一物品的偏好，記用戶u對物品i的評分為score(u,i)，用戶u對物品i的協同過濾得分為rec(u,j)。

1.2業務實踐

以購物籃子為例，業務問題：根據用戶的歷史購買商品記錄，給用戶推薦一批商品，協同過濾演算法實現方法如下。

記buyers表示用戶購買商品的向量，記為其中表示全庫用戶集合，表示用戶對商品的得分，定義如下：

Step1：計算物品之間的相關係數

記buyersi表示用戶購買商品的向量，記buyersi=(…,bu,i,…) u∈U為,其中U表示全庫用戶集合，bu,i表示用戶u對商品i的得分，定義如下：

那麼商品i與商品j的相關係數如下：

上述公式是是利用餘弦公式計算相關性，含義是商品的用戶購買向量夾角越小越相似。此外也可以運用皮爾遜、傑卡德、自定義公式計算相關性，這裡不一一列舉。

Step2：計算用戶對商品的協同過濾得分

給定一個用戶u，設該用戶歷史購買商品記錄的向量為historyu=(…,hu,i,…) ,i∈I其中I表示所有商品的集合：

計算給定一個物品j的協同過濾得分為:

Step3：給用戶推薦商品

通過Step2計算用戶對全庫商品的協同過濾得分，取得分top 10展示給用戶。

2基於關聯規則的推薦演算法

2.1演算法簡介

基於關聯規則的推薦是根據歷史數據統計不同規則出現的關係，形如：X->Y，表示X事件發生後，Y事件會有一定概率發生，這個概率是通過歷史數據統計而來。

對於一個規則X->Y，有兩個指標對該規則進行衡量。一個是支持度，表示在所有樣本數據中，同時包含X和Y樣本的佔比。另一個是置信度，表示在所有包含X的樣本中，包含Y的樣本佔比。

在關聯推薦演算法中，最主要的是如何找到最大頻繁項，業界主要的做法有兩種，分別為Apriori演算法和FP樹。但在互聯網海量的用戶特徵中，使用這些演算法挖掘頻繁集計算複雜度非常高，下面我們介紹一種在業務當中簡單實用的關聯規則演算法。

2.2業務實踐

同樣是以購物籃子為例，業務場景是：根據用戶歷史購物記錄，給用戶推薦商品。下面我們介紹如何構建簡單的關聯規則推薦演算法。

Step1：數據準備

首先收集用戶展示購買記錄，並且關聯用戶在展示時刻的特徵數據。設總樣本數量為n條，數據格式如下：

表1：初始數據

其中用戶特徵可以是用戶歷史購買的商品ID，也可以是用戶屬性特徵，例如：年齡、性別、居住地等等。

Step2：特徵交叉

在上表中，對於同一個樣本所有特徵兩兩交叉，生成長度為2的特徵規則，合併原來的長度為1的特徵規則，得到關聯規則數據輸入表如下：

表2：rule輸入數據

上述表中只用長度為1（原始特徵）和2（原始特徵兩兩交叉）的規則作為後面rule的候選集，不做長度為3的規則主要的考慮點是降低規則空間複雜度。

Step3：生成關聯規則

首先把上表的特徵展開，使得一個特徵一條記錄，如下表：

表3：展開數據

計算每個規則的支持度，置信度，提升度。首先作變數聲明：

f->i 表示具備特徵f的用戶購買商品i的事件

sf,i 表示規則f->i的支持度

cf,i 表示規則f->i的置信度

sf,i 計算方法為：統計表3中中同時滿足特徵=f，商品=i，用戶是否購買=0的記錄條數記為notbuyersf,i

規則選擇，規則可以通過以下條件進行過濾。

條件1：大於等於某個值，參考值取20-100。

條件2：對所有規則的支持度做降序，取75位數為參考值，sf,i大於等於這個值。

條件3：對所有規則的置信度做降序，取75位數為參考值，cf,i大於等於這個值。

Step4：給用戶推薦商品

給定一個用戶u和一個商品i，通過上述方法生成用戶u的特徵集合記為F. 我們用該用戶特徵集合下，所有對i有效特徵的均值衡量用戶u對該物品的購買可能性p(u,i)：

通過上述公式對全庫商品求top 10得分的商品推薦給用戶。在實際計算當中，並非會進行全庫計算，而是採用特徵索引技術進行減少大量冗餘計算。

3基於bayes的推薦演算法

3.1原理介紹

Bayes(貝葉斯)定理是關於隨機事件A和B的條件概率相互轉化的一則定理，貝葉斯公式如下：

上述公式中，P(Bi|u)表示的含義是在發生了事件u的情況下，發生事件Bi的概率，P(Bi)表示事件Bi的發生概率，P(u)表示事件u的發生概率。

如何利用上述定理進行個性化推薦，下面我們舉個業務實踐的例子。

3.2業務實踐

以應用商店中應用推薦為例，業務場景：當用戶進入應用商店，根據用戶已安裝應用列表給用戶推薦應用。

Step1：問題分解

給定一個用戶u，給該用戶推薦應用B，根據貝葉斯公式用戶安裝概率為：

設用戶的安裝列表為{A1 ,…, An}，把用戶u看作是事件{A1 ,…, An}，為了簡化問題，假設Ak相互獨立，那麼：

上述式子可以化為：

在推薦場景中，是對一個用戶計算不同應用的得分，然後作降序進行推薦。而對於同一個用戶P(u)是不變的，所以我們可以用以下公式作為排序依據：

全庫的應用集合記為，所以在貝葉斯推薦模型中主要參數有兩個集合，分別為：

Step2：數據準備

首先收集歷史的用戶在應用商店中應用展示記錄，並且關聯用戶在展示時刻的安裝列表，數據格式如下：

表1：初始數據

Step3：模型參數計算

參數集合{P(B)|B∈I}的計算：給定一個應用B. 根據表1，首先中「展示應用=B」的樣本數，記為showNumsB然後計算「展示應用=B」且「用戶是否安裝=1」的樣本數記為installNumsB 那麼：

參數集合{P(Ai|B)|B∈I,Ai∈I}給定一個應用B及Ai 根據表1，首先計算「Ai∈已安裝列表」且「展示應用=B」的樣本數，記為showNumsAi,B . 然後計算「Ai∈已安裝列表」且「展示應用=B」且「用戶是否安裝=1」的樣本數，記為installNumsAi,B 那麼：

在計算P(Ai|B)可能會遇到樣本不足的情況，導致計算出異常值，為了避免這類情況，需要根據經驗加個最少安裝數限制，這裡我們定義為最少安裝次數為100，那麼：

其中P(Ai)是表示在所有用戶中，安裝了應用Ai用戶的佔比。

Step4：給用戶推薦應用

給定一個用戶u，及一批候選推薦應用池，我們通過上述方法計算用戶u對候選池中每個應用的得分sortScore(u,B)，根據這個值做降序，取top 10的應用推薦給用戶。

4基於KNN的推薦演算法

4.1演算法簡介

KNN（K最近鄰分類演算法）是一種在機器學習中比較簡單的演算法，它的原理如下：對於一個需要分類的物品A，定義某一種刻畫物品之間距離方法，找出該物品最鄰近k個有已知類別的物品，這k物品中出現最多的類別即為物品A的類別。如下圖：

在KNN算中，最核心的一點是怎麼定義物品之間的距離，這裡我們簡單列舉幾種計算物品距離的方法：歐式距離、曼哈頓距離、切比雪夫距離、傑卡德係數、夾角餘弦、皮爾遜係數。

下面介紹KNN在實際業務中的運用。

4.2業務實踐

業務場景1：以應用商店為例，在用戶下載完一個應用時，觸發一個「大家還下載」的推薦，下面介紹如何運用knn演算法實現這個場景的推薦：

首先定義應用的維度向量，一種簡單的方法是離散化所有特徵，然後進行one-hot編碼，得到所有維度取值0/1的向量V，例如：可以把每個用戶當做一個維度，如果第n個用戶安裝了應用A，那麼應用A在第n個維度取值為1，否則為0，運用歐式距離可以得到應用A與應用B的距離公式：

。

給定一個應用A，通過上述公式取距離最小的4個應用出來，在用戶下載完應用A以後給該用戶推薦這4個應用。

業務場景2：網路購物中，在「猜你喜歡」場景推薦一批物品給用戶，

通過用戶的歷史購物清單，運用傑卡德公式計算用戶與用戶的相關係數：

表示購買了物品x的用戶集合，

那麼用戶u與用戶v的距離定義為：

給定一個用戶u，首先找出這個用戶最鄰近的k個用戶，然後在這k個用戶中按照購買的用戶數對物品進行降序，去除用戶u已經購買的物品，取top 10個物品推薦給用戶。

5決策樹演算法

5.1演算法簡介

決策樹一種經典的機器學習分類演算法，主要的代表演算法有ID3、C4.5、CARD，原理可以簡單理解為通過對數據總結、歸納得到一系列分類規則，舉個簡單的例子：

在決策樹中，一個葉子節點表示一條決策規則（通常葉子節點的類目等於該節點樣本最多的類目），決策樹演算法的目標是得到準確率高的規則，而決策規則的準確率可以用葉子節點的複雜度來衡量。

5.2複雜度計算

下面列舉2種常用複雜度的計算方法, 假設有樣本集X，總共的類目有n個，pi表示第i個類目的佔比。

（1）信息熵：

上式中，信息熵的值越高，複雜度越高，樣本的不確定性越大。

（2）基尼指數：

上式中，基尼指數越大，複雜度越高，樣本的不確定性也就越大。

5.3裂分指標

在決策樹的生成過程中，每一個節點的裂分都需要考慮選擇哪個屬性裂分使得系統的複雜度降低越多。不同演算法選用的裂分方法有所不同。

（1）ID3：信息增益

其中H(x)表示裂分前系統的複雜度，

表示裂分後系統的複雜度。該值越大表示裂分方式使得系統更為有序。

（2）C4.5：信息增益率

表示A屬性的第i個取值佔比，其中

表示的意思是屬性A的複雜度，該公式除了考慮系統純度的增量的同時，也考慮了屬性A的複雜度。該值越大表示裂分方式使得系統更為有序。（在ID3演算法中，由於選擇的是信息增益計算系統純度增量，往往會選擇複雜度高的屬性進行裂分，複雜度高的屬性取值分段會有很多，導致裂分後某些節點只有少量樣本而不具備用於預測的統計意義，C4.5基於這個問題加以改進）。

（3）CARD：基尼係數

CARD演算法生成的決策樹是一個二叉樹，每次裂分只裂分兩個節點，Gini(X|A)表示裂分後的複雜度，該值越高樣本無序性越大，X1,X2是X的裂分後的兩個樣本集（裂分方法為遍歷所有裂分可能，找出Gini(X|A)最小的那個點）。該值越小表示裂分方式使得系統更為有序。

5.4決策樹生成

輸入：

裂分指標：選擇一種裂分指標（信息增益、信息增益率、Gini係數）。

節點裂分終止條件：選擇節點最小樣本數及最大深度。

Step1：選擇一個可裂分的節點Di，循環計算所有屬性的裂分指標，選取最優的指標使得系統最為有序那個屬性作為裂分點，得到數據集Di+1,Di+2,…

Step2：所有葉子節點是否都達到了裂分的終止條件，是則執行Step3，否則執行step1。

Step3：減枝

Step4：返回決策樹T

5.5業務實踐

業務場景：以應用商店中應用個性化推薦為例。

Step1：構造用戶畫像，收集用戶歷史下載應用記錄、已安裝應用記錄、用戶社會屬性（年齡、性別、學歷、所在城市）。

Step2：構造應用畫像，應用畫像包括應用ID，應用類型、應用標籤、應用安裝量排名、應用CTR等。

Step3：樣本收集，收集用戶歷史曝光下載應用記錄（欄位：用戶ID、應用ID、是否下載），並通關用戶ID、應用ID與用戶畫像、應用畫像關聯起來得到樣本數據，得到樣本數據（用戶ID，應用ID，用戶畫像，應用畫像，是否下載）。

Step4：構造模型訓練樣本，定義用戶畫像與應用畫像不同類型特徵的交叉規則生成模型特徵，運用定義好的交叉規則對所有樣本生成模型特徵，得到模型訓練樣本（模型特徵，是否下載）。

Step5：模型訓練，模型訓練樣本訓練CARD演算法，得到預測模型。

Step6：模型使用，給定一個用戶和應用，根據上述方法生成用戶的用戶畫像及應用的應用畫像，然後運用定義好的交叉特徵規則生成模型特徵，把模型特徵代入模型得到預測值。

6隨機森林演算法

6.1演算法簡介

隨機森林（RF）是決策樹與bagging結合一種分類回歸演算法，它由多顆決策樹構成的一個bagging決策系統。當運用RF進行預測時，首先把需要把樣本數據輸入到每一棵決策樹，每個樹得到一個葉子節點，預測的時候，如果是回歸問題則統計所有樹葉子節點的均值，如果是分類問題則求所有樹葉子節點類目出現最多的那個類。

RF每棵決策樹的構建方式如下：

Step1：用M表示數據總特徵維度，N表示樣本數量，m表示特徵抽樣維度。

Step2：有放回隨機抽取N個樣本作為這個樹的訓練樣本。

Step3：對訓練樣本構建決策樹，每次裂分前隨機抽取m個特徵出來，裂分特徵在這m個特徵中選擇一個最優的裂分特徵。

Step4：不作減枝直到不能裂分為止。

6.2業務實踐

在實際的業務運用中與決策樹類似，在前面介紹的決策樹業務實踐中可以直接用RF演算法替代決策樹，構造的方法如上所述，重複地隨機抽樣樣本及抽樣特徵構造多顆決策樹，決策樹的棵數需要結合分類精度及模型複雜程度判斷。

7基於矩陣分解的推薦演算法

7.1演算法介紹

在推薦演算法中，主要解決的問題是找到用戶對物品的偏好得分。矩陣分解演算法它的基本思想是認為用戶對物品的偏好是外在表現，內在是用戶對主題的偏好，而主題對不同物品又有不同的權重，通過用戶->主題->物品這條鏈路才形成用戶對物品的偏好。

矩陣分解的公式：

U=PQ

其中U表示用戶對不同物品的偏好矩陣， P表示用戶對不同主題的偏好矩陣， Q表示不同主題對應用的權重。

7.2模型求解

在實際的業務實踐中，往往是已知用戶對物品的部分偏好得分，求解用戶對未知物品的偏好得分。

以應用商店廣告場景為例：已知用戶在端內的物品曝光點擊記錄，求解用戶對不同廣告偏好得分。

Step1：根據樣本數據構造矩陣U

根據樣本數據，用戶對曝光物品有點擊記為1，沒有點擊記為0，沒有曝光過的物品不賦值（記為-），示例如下：

Step2：求解矩陣P和矩陣Q

設矩陣U的大小為N×M，主題數定義為K，那麼矩陣的大小是N×K，Q矩陣的大小是K×M，

構造損失函數，如下：

其中ui,j表示矩陣U的第i行第j列元素，pi表示矩陣P的第i行，qj表示矩陣Q的第j列，

通過梯度下降法可以求解矩陣P和矩陣Q。

Step3：預測用戶對沒有曝光過物品的偏好得分

給定一個用戶i，需要預測該用戶對物品j的偏好得分，公式為：

。

Step4：如何給用戶推薦物品

給定一個用戶，通過Step3的公式計算該用戶對所有物品的偏好得分，取該用戶沒有曝光過得分排名前10的物品進行推薦。

8基於BP的推薦演算法

8.1演算法介紹

BP演算法是神經網路的一種演算法，BP演算法網路是有多層網路構成，信號的傳播是由第一層網路開始正向傳播到下一層網路。以3層神經網路為例，網路結構示例如下：

以3層神經網路關係如下：

向量X是模型輸入變數向量，wi是Li-1層與Li的連接權重矩陣，bi是Li的偏置向量。函數f是一個激活函數，目前業界常用的激活函數有relu、sigmod、tanh，傳統BP神經網路函數一般採用sigmod函數，如果採用該函數，那麼：

8.2模型求解

以個性化推薦場景中點擊率預估為例，上述模型參數有w1, w2, w3, b1, b2, b3，我們通過梯度下降法求解這些參數，首先收集樣本，取歷史用戶推薦的數據及用戶對推薦反饋的數據作為樣本。變數定義如下：

nums 表示收集樣本的數量。

(Xi,yi)表示用戶第個樣本的數據，Xi表示樣本的特徵，yi表示點擊情況(0表示沒有點擊，1表示點擊)。

Yi 表示上述模型構造中的輸出值，是關於w1, w2, w3, b1, b2, b3的變數。

損失函數：常用的的定義有兩種，一種是交叉熵，另一種均方差，以均方差為例：

通過上述損失函數，運用梯度下降法求解模型參數w1, w2, w3, b1, b2, b3。

9基於W2V的推薦演算法

9.1演算法簡介

W2V是在2013年由Google開源了一款用於詞向量計算的工具，該演算法提出的場景主要是解決NLP中詞向量化的問題，傳統對詞向量的方法是one-hot編碼，one-hot編碼存在主要有兩點，第一點維度極高無法直接作為模型的輸入變數，第二點是詞與詞之間沒有相關性。W2V的誕生解決了這兩個問題，W2V是通過神經網路對詞進行低緯度的向量化。

W2V有兩種模型，一個是CBOW模型，另一個是Skip-gram模型。兩個模型都是對詞進行向量化，區別在於：CBOW是以一個詞為輸出目標，以該詞鄰近的詞為輸入；Skip-gram是以一個詞為輸入，以該詞鄰近的詞為輸出目標。示例如下：

以CBOW模型為例，該模型的結構圖如下：

各層關係為：

Input層：以一個詞為輸出目標，以該詞鄰近的詞向量為輸入。

Projection層：把Input層的所有向量疊加求和。

Output層：首先對語料庫中的所有詞建立哈夫曼樹編碼（不使用one-hot編碼，one-hot編碼太稀疏）。然後為每在每個哈夫曼樹節點建立一個邏輯斯蒂分類模型，模型的輸入都是Projection的輸出。

9.1模型訓練

模型的參數，模型的參數包括所有詞的詞向量和哈夫曼樹中每個節點的邏輯斯蒂回歸參數

。

哈夫曼樹中的每個節點都是一個邏輯斯蒂回歸函數，以輸出的詞作為葉子節點路徑中的每個節點的分類（路徑走左分支為1，右分支非0）作為訓練目標。例如：上圖中輸出詞假設為「足球」，那麼路徑如下：

損失函數的構造，通過交叉熵的構造，以一個樣本例，樣本的輸入詞向量求和為XW，輸入詞為M，該詞對應的哈夫曼樹路徑為T(M)，那麼該樣本的損失函數如下：

把所有樣本的按照上述公式計算損失函數，求和後得到模型的損失函數：

通過梯度下降法可以求解所有詞的詞向量vi。

9.2業務實踐

場景：網路購物場景中，運用W2V+BP進行個性化推薦。

Step1：對物品進行向量化

把每個用戶看作一篇文章，用戶購買物品按照時間序列排序，物品看作詞，帶入W2V模型得到物品的向量。

Step2：樣本收集

收集客戶端中，對用戶的物品曝光及購買記錄，以用戶歷史購買的物品列表作為用戶畫像，以給用戶曝光物品後用戶是否購買為目標變數。

Step3：構造W2V + BP的模型

模型的輸入有兩個，第一個為用戶歷史購買物品的向量均值，第二個為曝光物品的向量。模型的輸出為用戶是否購買曝光的物品，中間用BP網路進行連接。

Step4：模型訓練與使用

模型訓練：目前業界一般使用TF進行實現，BP網路的節點數及層數需要根據訓練情況確定。

模型使用：給定一個用戶u及一個物品i，把用戶u購買物品向量均值及物品i的向量作為模型輸入，計算物品i的模型得分。重複該操作，計算出用戶u所有候選物品的模型得分，根據物品的模型得分降序推薦給用戶。

10基於LR的推薦演算法

10.1原理介紹

LR（邏輯斯蒂回歸）演算法的本質是一個線性回歸函數，該演算法主要用作二分類的場景，例如點擊率預估，演算法公式如下：

其中x是模型的輸入

xi表示每個維度的輸入。

w是表示模型輸入x的係數向量，w=( w1, w2, …), wi表示維度xi的權重。

10.2模型求解

我們通過梯度下降法求解我們的模型。以點擊率預估為例，首先收集樣本。變數定義如下：

nums 表示收集樣本的數量
。

(Xi,yi)表示用戶第個樣本的數據，Xi表示樣本的特徵，yi表示點擊情況(0表示沒有點擊，1表示點擊)。

Yi 表示模型的預測值，是關於w,b的變數。

定義交叉熵損失函數：

通過梯度下降法求解los(w,b)最小時對應的w,b即為所求模型參數。

10.3業務實踐

LR演算法在目前推薦系統業界中，流行的做法是大規模離散化特徵（one-hot編碼），然後帶入LR模型，以廣告點擊率模型為例，步驟如下：

Step1：構造用戶畫像

按照特徵類別構造用戶畫像，對類別下面的所有特徵進行離散化處理，例如：用戶歷史瀏覽物品記錄，用戶社會屬性，通過模型給用戶打的標籤等等。

表：用戶畫像

Step2：構造物品畫像

構造物品畫像，同樣也是需要劃分物品特徵類別，類別下面特徵離散化處理，例如：物品ID，物品標籤，物品熱度等等。

表：用戶畫像

Step3：構造場景畫像

在實際的業務實踐中，往往是一個模型需要用到多個場景，不同場景物品的平均點擊率差別很大，為了更好地解決不同場景平均點擊率不同的問題，往往需要加上場景特徵。場景畫像一般只有場景ID，在某些特殊場景（例如：搜索列表）可以加上位置信息。

表：場景畫像

Step4：收集樣本數據

收集歷史曝光點擊數據，收集的數據維度包括:用戶ID，物品ID，場景ID，是否點擊。然後關聯用戶畫像和物品畫像得到模型的訓練樣本數據。

表：樣本數據

Step5：構造模型特徵

通過對樣本數據構造模型特徵得到模型的輸入，模型特徵分兩類，一類是交叉特徵，另一類是原始特徵。

交叉特徵：選擇用戶的類別特徵、選擇物品的類別特徵、場景ID做三個維度的交叉，例如：用戶歷史點擊記錄為item1,item2 ，物品的ID特徵為I1，場景特徵為scene1，那麼生成的交叉特徵為item1&I1&scene1,item2&I1&scene1。

原始特徵：原始特徵是指直接把畫像特徵作為模型的輸入特徵，一般是把物品的泛化特徵作為原始特徵，用於物品冷啟動特徵或場景冷啟動特徵，例如：物品的CTR、物品的熱度、物品的標籤等等。

表：模型輸入

Step6：模型訓練

把模型中的所有特徵進行one-hot編碼，假設模型特徵數為N，首先給每個模型特徵一個唯一1-N的編碼，那麼每個樣本的模型輸入向量是維度為N取值0/1的向量，0表示該樣本具備對應編號的特徵，1表示沒有，例如：樣本1的具有有編號為1和編號為3的特徵，那麼樣本1的模型輸入向量為(1,0,1,0,0,…)，

然後通過通用的LR訓練器訓練模型，即可把模型的參數訓練出來。

Step7：模型使用

給定一個用戶u，及一批候選物品，對用戶u如何推薦物品。通過上述方法計算用戶u對候選集中每個物品的模型得分，按照模型得分降序推薦給用戶。