召回演算法

㈠ 推薦系統召回演算法之——圖模型（Personal Rank）

目錄

1、Personal Rank 演算法背景

2、二分圖的概念

3、文件解析原理及其物理意義

4、PR公式推導

5、python實現

6、總結

Personal Rank演算法背景：

用戶行為很容易表示為圖

圖推薦在個性化推薦領域效果顯著，UI矩陣就是典型的二分圖。

二分圖： 又稱為二部圖，是圖論中的一種特殊模型。設G=(V,E)是一個無向圖，如果頂點V可分割為兩個互不相交的子集（A,B），並且圖中的每條邊（i,j）所關聯的兩個頂點i和j分別屬於這兩個不同的頂點集（i in A，i in B），則稱圖G為一個二分圖。

下面舉例並從物理意義角度解析，二分圖演算法是如何將UI矩陣表示為二分圖，計算出Item集合對固定user的重要程度排序?

1、兩個頂點之間連通的路徑數？

A到c：A->a->B->c；A->d->D->c兩條連通路徑；

A到e：A->b->C->e一條連通路徑

故，A對物品c的偏好程度大於對物品e的偏好。

2、兩個頂點之間的連通路徑長度？

A->c兩條路徑4個頂點，連通路徑長度都是3；A->e也為3

3、兩個頂點之間連通路徑經過頂點的初度？

A到c：A->a->B->c：3+2+2+2；A->d->D->c：3+2+2+2

A到e：A->b->C->e：3+2+2+1

演算法文字描述 ：對用戶A進行個性化推薦，從用戶A結點開始在用戶物品二分圖random walk ，以alpha的概率從A的出邊中等概率選擇一條遊走過去，到達頂點後（例如a），有alpha的概率繼續從頂點a的出邊中等概率選擇一條繼續遊走到下一個結點，或者（1-alpha）的概率回到起點A，多次迭代。直到所有的頂點對於用戶A的重要度收斂。（二分圖有且只有一個頂點）

演算法公式推導 ：

按照上面UI矩陣的二分圖表示法結合演算法文字描述，以節點A和a來舉例解釋公式。

：表示不同節點重要度。

以a為例，公式上部分表示節點a與之相連的節點A和B，分別從各自出邊等概率貢獻了1/3和1/2的重要度加和後乘以 ， 取經值為0-1之間（經驗值0.6）。

以A為例，公式下部分表示與A相連的節點a,b,d，分別從各自的出邊等概率貢獻了1/2的重要度，同時它們又是直接與A相連的節點，從PR演算法文字描述可知，都可以以1- 的概率回到A節點。

公式（1）的矩陣表達方式為： (2)

其中 是n維向量，每一個元素代表一個節點的PR重要度； 也是n維向量，第i個位置為1，其餘位置為0，我們就是要為第i個節點進行推薦。其中 是n階轉移矩陣：

 

由（2）進行恆等變形可得

(3)

(4) ，其中 就是所有節點的推薦結果，乘以 就是取出矩陣的第i列。

Python實現： https://github.com/SolodanceMagicq/RecommendSys/tree/master/PersonalRank

總結：

1、personalrank二分圖演算法，是一種無向圖，有且只有一個root頂點。

2、演算法核心思想是將UI矩陣以二分圖存儲，通過頂點按等概率隨機遊走，迭代計算關聯節點pr值的過程。首次迭代只計算推薦用戶（root頂點）與其直接關聯的節點pr值，然後每次基於上次節點進一步迭代計算關聯節點，直至收斂。

3、PersonalRank演算法迭代的時間復雜度過高，須進一步優化，工業界一般會藉助spark離線計算或maprece將多節點並行計算提高計算性能。

㈡ 如何提高機器學習演算法的召回率

最近在做文本分類，遇到了一些問題，想問問大家有沒有好的方法。為了節省時間，我只採取了部分數據來跑演算法（全部數據跑了之後的結果和這個差不多）
訓練集：4837 documents
測試集：2074 documents
樣本比例：正樣本：負樣本 = 1：3
預測結果中，有的演算法在正樣本中預測的精確率還行（0.95-1.00之間），但是召回率非常差，通常只有0.01和0.02左右，KNeighbors和DecisionTree的精確率和召回率都是0，只有NaiveBayes和BernoulliNB的PR和Recall比較平均，但是也沒有到0.8。
問題：我查了一下那些召回率較低（0.01）的演算法，475個樣本中（正樣本），實際上只有5個被預測正確了的，但是具體原因沒有查出來。
我想請問一下：1.召回率低是因為樣本極度不平衡造成的嗎？（雖然我認為1：3的比例不算極度不平衡。）2.在這種樣本不平衡的問題上，有沒有什麼好的方法可以提高召回率？我試過SMOTE方法（過采樣和欠采樣都有試過），但對於我的數據集並沒有什麼好的效果，不止到有沒有有什麼好的方法可以解決這個問題？謝謝！
添加評論
分享

查看全部 11 個回答

0贊同反對，不會顯示你的姓名
Elvin 全是細枝末節，做一個樂於分享的人
兩個問題一並回答一下，根據你的描述，我覺得問題應該不是出在正負樣本比上，1比3這個比例不但不是非常不均衡，相反在我看來已經是非常均衡了。以前做比賽有處理過正負比1比10000的數據，我覺得這才叫不平衡，才需要使用類似上采樣，下采樣，以及SMOTE演算法（都用過），而且這樣的情況下recall，F1等指標的提升是顯著的。我覺得正負比例在1：1至1：100間差別都不會太大，需要根據具體問題做離線交叉驗證去找到最好的比例。

所以我建議你不用再糾結正負樣本比的問題，可以再回頭看一看你的數據集，一方面看一看代碼是否有誤？數據集是否太小？（總覺得你的數據集太小，而且測試集相對於訓練集太大）另外訓練集，測試集的劃分是否正確？或者重新劃分一下訓練測試集做一下交叉驗證看一看各項指標再具體研究。