Ⅰ 推薦系統召回演算法之——圖模型（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將多節點並行計算提高計算性能。
Ⅱ C++課程設計 矩形覆蓋小正方形
實際上,你可以利用圖論的概念來解決.
相鄰的實際上等於是有關系,那可以在圖中描述為鄰接點.不斷的添加相鄰的元素就能夠組成一張無向圖.如果考慮求一個最小覆蓋的問題,推薦的演算法(根據你的需求猜測)
1. 二部圖匹配(最大流最小流)
2.最小生成樹
Ⅲ ACM題目求解題思路
有N個石子,每個石子重量Qi；按順序將它們裝進K個筐中；求一種方案，使得最重的筐最輕。 分析：本題乍一看很容易想到動態規劃。事實上的確可以用動態規劃解決，稍加分析我們很快得到一個簡單的演算法。用狀態f(i,k)表示將前i個石子裝入k個筐最優方案，g(i,j)表示i-j中最重的石子，則可以寫出狀態轉移方程：g(i,j)=max {g(i,j-1),Qj}f(i,j)=min max {f(k , j-1), g(k+1 , i)} | 1<=j<=k邊界條件：g(i,i)=Qi,f(1,1)=g(1,1)很明顯，這個演算法的時間復雜度為O(N3),空間復雜度為O(N2)，並不十分理想。經過一些優化可以將復雜度降為O(N2)，不過這樣思維復雜度驟然加大，且演算法本身仍不夠高效。現在已經很難在原動態規劃模型上做文章了，我們必須換一個思路。按一般的想法，順序將石子裝入筐，即先把石子放入第一筐，放到一定時候再改放第二個筐，第三個筐……但由於筐的重量沒有上限，我們無法知道放到什麼時候可以停止，轉而將石子放入下一個筐。此時，問題的難點已經顯露出來，是不是有方法可以化解呢？我們不妨針對上面的難點，加入一個參數P，改求一個判定可行解問題：每個筐石子重量和不能超過P，是否可以用K個筐裝下所有石子。首先經過分析不難發現，如果當前筐的石子總重量為T1，即將處理的石子重量為T2，若T1+T2 ≤P，則我們仍將該石子放入當前框，這是顯而易見的。由此可以得出貪心演算法，按順序把石子放進筐，若將石子放入當前筐後，筐的總重量不超過P，則繼續處理下一個石子；若重量和超過P，則將該石子放入下一個筐，若此時筐的數目超過K，則問題無解，否則處理完所有石子後就找到了一個可行解。以上演算法時間復雜度O(N),空間復雜度O(N)，這都是理論的下界。現在我們已經解決了可行解問題，再回到原問題。是不是可以利用剛才的簡化過的問題呢？答案是肯定的。一個最簡單的想法是從小到大枚舉P，不斷嘗試找最優解為P的方案（這就是剛才的可行解問題），直到找到此方案。這就是題目的最優解。估算一下上面演算法的時間復雜度。令T=∑Qi，則最壞情況下需要枚舉T次才能找到解，而每次判斷的時間復雜度為O(N)，因此總的時間復雜度為O(TN)，故需要做進一步優化。下面考慮答案所在的區間。很明顯，若我們可以找到一個總重量不超過P』的解，則我們一定能找到一個總重量不超過P』+1的解，也就是說，可行答案必定可以位於區間[q,+∞]（其中q為本題最優解）。因此，我們自然而然的聯想到了二分，具體方法為：在區間[1,T]內取中值m，若可以找到不超過m的方案，則嘗試區間[1,m-1];若不能，嘗試區間[m+1,T]。不斷重復以上步驟即可找到問題的最優解。分析一下採用二分法後演算法總的時間復雜度：由於每次除去一半的區間，則一共只需判斷log2N次，而每次判斷的時間復雜度為O(N)，因此這個演算法總的時間復雜度為O(NlgT)。一般而言，這個復雜度可以令人滿意的，並且實際使用中效果非常好。但該復雜度同權值有關，不完全屬於多項式演算法，我們可以繼續求得一個多項式演算法（該演算法與本文核心內容無關，只作簡單探討）。首先，此問題的答案必定為某一段連續石子的和，而段數不超過n2，因此，我們最多隻要判斷log2N2=2log2N次即可。現在新的問題是如何找到第m大的段。首先，以每個石子開頭的所有段，例如：3 2 1 2，以2開頭的所有段：2；2 1； 2 1 2， 由於每個石子的重量都大於0，因此總和一定是遞增的。現在有n個遞增段，如何快速的找到第k大的數呢？設各段長度為L1,L2,…,LN,中點分別為M1,M2,…,MN，我們每次詢問各段中點的大小，若L1/2+L2/2+..+LN/2>k，則找到權值最大的中點，刪去其後的數（下圖中紅色部分），否則找到權值最小的中點，刪去其前面的部分（下圖中黑色部分），可以證明刪去的一定不是所求的數。 註：上圖中每個各格子代表一個數。 由以上可知每次可以去掉某一段的1/2，因為有n段，故總共需要去O(Nlog2N)次，每次找最小最大值可以用堆實現，復雜度僅為O(lgN)，因此總的時間復雜度為O(lg2N)，而由上文我們知道找中值的操作總共有log2N次，故這個演算法的時間復雜度為O(Nlg3N)。 至此我們終於得到了一個多項式級別的演算法，當然這個演算法實現起來比較麻煩，實際效果也不甚理想，不過具有一定的理論價值，在此不做過多討論。 回顧本題解題過程，首先我們得到了一個動態規劃演算法，由於很難再提高其效率，因此我們另闢蹊徑，尋求新的演算法。在分析過程中我們發現由於筐的重量沒有上限，因此很難確定將多少石子放入同一個筐內。為了解決此難點，我們加入了參數P，改求可行解問題。參數的加入實際上就是強行給筐定了一個上界。正是由於這無形之中多出的條件，使得問題立刻簡單化，於是我們很自然的得到了貪心演算法。而最終使用二分法降低了演算法的時間復雜度，成功地解決了問題。 由上面的例子我們得到了此類解法的一般步驟，通常分為兩步：Ⅰ.首先引入參數P，解決子問題：能否找到一個不優於P的方案Ⅱ.從小到大枚舉P，判斷是否有優於P的方案，直到找出原問題的最優解 一般地，參數搜索可以通過二分法或迭代降低時間復雜度，由於迭代法證明比較復雜，所以本文更多的討論二分法。 這個方法的應用比較廣泛，通常情況下和上例一樣求最大（小）值盡量小（大）的題目都可以採用此方法，比如下面的例子。神秘的山：有n個隊員攀登n個山峰，每個隊員需要選擇一個山峰，隊員們攀登的山峰各不相同，要求最後一個登頂的隊員用的時間盡量短。 分析：本問題分為兩個部分解決：1．求出每個隊員攀登到各個山峰所需的時間；2．找一個最優分配方案。 第一部分屬於幾何問題，我們可以枚舉每個隊員攀登山峰的位置再做簡單的判斷（題目規定攀登點必須為整點，這就為枚舉提供了條件），這樣就可求得隊員們攀登上各個山峰所需的時間。下面重點討論第二部分。首先將我們的數據構圖，很明顯，我們得到的是一個二部圖，假設有3個隊員3個山峰，每個隊員攀登的時間如下 山峰1山峰2山峰3隊員1132隊員2222隊員3133 則我們可以構圖，每條邊附上相應的權值： 現在的任務就是在圖中找一個匹配，匹配中權值最大的邊盡量小。這個問題是否可以直接套用一些常見的模型呢？比如最大匹配或是最佳匹配？經過分析不難發現在這個問題中它們都是不足以勝任的，因此我們不得不做新的嘗試。 上文提到過要求極大（小）值盡量小（大）的題目往往先定出上界比較容易下手，那麼這題也採用類似的思路。引入一個參數T，先求一個判定可行解的子問題：找一個方案，要求最後登山的隊員所用時間不超過T。 改變後的題目有什麼不同之處呢？如果隊員i攀登上山峰j所需的時間超過T，則可以認為他在規定時間內不能攀登上山峰j，我們就可以把這條邊從圖中刪去。例如在上例中找一個不超過2的方案，經過一次「篩選」，保留的圖如下。 經過這次過濾保留下來的邊都是「合法邊」，我們只需要在這個新的二部圖中找一個完備匹配即可，一個完備匹配唯一對應著一個可行方案。而找完備匹配可以借用最大匹配的演算法，因為如果一個二部圖的最大匹配數等於N，則找到了一個完備匹配，否則該圖中將不存在完備匹配。（上圖中的紅色表示一個完備匹配），那麼這一步的時間復雜度為O(NM)，而在本題中M=N2，因此我們可以在O(N3)的時間內判斷出是否存在一個方案滿足最後等上山頂的隊員時間不超過T。 最後，再用二分法枚舉參數T，找到最優解。由於答案必定為某個隊員攀登上其中一個山峰的時間，因此我們開始的時候可以將所有數據排序，這樣最終的時間復雜度為O(N3lgN)。引入參數後求可行解的子問題與原問題最大的區別在於定下上界以後，我們很自然的排除了一些不可取條件，從而留下了「合法」條件，使得問題變的簡單明了。. 上面的例子在增加了上界之後，排除了一些無效條件，其實它的作用絕不僅局限於此，有些時候，它能將不確定條件變為確定條件，比如下面的例子，最大比率問題：有N道題目,每道題目有不同的分值和難度,分別為Ai,Bi；要求從某一題開始, 至少連續選K道題目,滿足分值和與難度和的比最大。 分析：最樸素的想法是枚舉下標i』,j』，得到每一個長度不小於K的連續段，通過累加Ai』->Aj』，Bi』->Bj』求出比值，並找出比最大的一段。這樣做的時間復雜度很高，由於總共有N2段，每次計算比值的時間是O(N)，則總的時間復雜度到達O(N3)，不過計算比值時，可以採用部分和優化，這樣能把復雜度降至O(N2)，但仍然不夠理想。我們需要追求更出色的演算法，先考慮一個簡單的問題——不考慮難度（Bi），僅僅要求分值和最大（當然此時分值有正有負）。這個簡化後的問題可以直接掃描，開始時為一個長度為K的段，設為Q1,Q2,…Qk， 每次添加一個新數，若Q1+Q2+..+QL-K小於0，則把它們從數列中刪去，不斷更新最優解即可。這樣我們就能在O(N)的時間內找到長度不小於k且和最大的連續段。 之所以能成功解決簡化後的問題，是由於該問題中每個量對最終結果的影響是確定的，若其小於0，則對結果產生不好的影響，反之則是有益的影響。那麼原問題每個參數對最終結果的影響是不是確定的呢？很遺憾，並不是這樣，因為每個題目有兩個不同的參數，他們之間存在著某些的聯系，而這些聯系又具有不確定性，故我們很難知道它們對最終結果是否有幫助。想解決原問題，必須設法消除這個不確定因素！那麼有沒有辦法將這些不確定的因素轉化成確定的因素呢？此時，引入參數勢在必行！那麼我們引入參數P，求一個新的問題：找一個比值不小於P的方案。這個問題實際就是求兩個下標i』,j』，滿足下面兩個不等式j』-i』+1≥k ①(Ai』+Ai』+1....+Aj』)/(Bi』+Bi』+1…+Bj』) ≥ p ②由不等式②=>Ai』+Ai』+1....+Aj』 ≥p(Bi』+Bi』+1…+Bj』)整理得(Ai』-pBi』)+(Ai』+1-pBi』+1)…+(Aj』-pBj』) ≥0可以令Ci=Ai-pBi，則根據上面不等式可知問題實際求一個長度不小於k且和大於０的連續段。由之前的分析可以知道我們能在O(N)的時間內求出長度不小於k且和最大的連續段，那麼如果該段的和大於等於０，則我們找到了一個可行解，如果和小於０，則問題無解。也就是說，我們已經能在O(N)的時間內判斷出是否存在比值不小於P的方案，那麼接下來的步驟也就順理成章了。我們需要通過二分法調整參數P，不斷逼近最優解。計算一下以上演算法的時間復雜度，設答案為T，則該演算法的時間復雜度為O(NlgT)，雖然這並不是多項式級別的演算法，但在實際使用中的效果非常好。引入參數後，由於增加了一個條件，我們就可以將不確定的量變為確定的量，從而解決了問題。三． 總結 本文主要通過幾個例子說明了參數搜索法在信息學中的應用，從上文的例子可以看出加入參數一方面能大大降低思維復雜度，另一方面也能得到效率相當高的演算法，這使得我們解最解問題又多了一中有力的武器。當然，任何事物都是具有兩面性的。參數搜索在具有多種優點的同時也有著消極的一面。由於需要不斷調整參數逼近最優解，其時間復雜度往往略高於最優演算法，且通常依賴於某個權值的大小，使得我們得到的有時不是嚴格意義上的多項式演算法。文章中還總結了使用此方法解題的一般步驟，在實際應用中，我們不能拘泥於形式化的東西，必須靈活應用，大膽創新，這樣才能游刃有餘的解決問題。
Ⅳ h 1269 tarjan WA 了 求解釋
ACM 推薦題目：不過不一定是北大的。
一.動態規劃
參考資料：
劉汝佳《演算法藝術與信息學競賽》
《演算法導論》
推薦題目：
簡單
中等，經典TSP問題
中等，狀態壓縮DP
中等
中等，樹形DP。
可參考《演算法藝術與信息學競賽》動態規劃一節的樹狀模型
中等，《演算法藝術與信息學競賽》中的習題
中等，《演算法藝術與信息學競賽》中的習題
中等，《演算法藝術與信息學競賽》中的習題
中等，遞推
中等，需要減少冗餘計算
中等，四邊形不等式的簡單應用
較難，狀態壓縮DP，《演算法藝術與信息學競賽》中有解答
較難，《演算法藝術與信息學競賽》中有解答
較難，需要配合數據結構優化（我的題目^_^）
較難，寫起來比較麻煩
較難
難，樹形DP
難，狀態壓縮DP，題目很有意思
難
非常難
二.搜索
參考資料：
劉汝佳《演算法藝術與信息學競賽》
推薦題目：
簡單，深搜入門題
中等，廣搜
中等，廣搜
較難，廣搜
難，IDA*，迭代加深搜索，需要較好的啟發函數
難，可重復K最短路，A*。
可參考解題報告:
難，深搜剪枝，《演算法藝術與信息學競賽》中有解答
難，《演算法藝術與信息學競賽》習題
難，深搜
較難，《演算法藝術與信息學競賽》中有解答
很難
三. 常用數據結構
參考資料：
劉汝佳《演算法藝術與信息學競賽》
《演算法導論》
線段樹資料：
樹狀數組資料
關於線段樹和樹狀數組更多相關內容可在網上搜到
後綴數組資料
推薦題目
較難，線段樹應用，《演算法藝術與信息學競賽》中有解答
簡單，線段樹應用矩形面積並，《演算法藝術與信息學競賽》中有解答
較難，線段樹應用，可參考解題報告
難，二維樹狀數組。
中等，線段樹應用。
難，堆的應用，《演算法藝術與信息學競賽》中有解答
中等，左偏樹，二項式堆或其他可合並堆的應用。
左偏樹參考
二項式堆參見《演算法導論》相關章節
中等，並查集
中等，字典樹
較難，多串匹配樹
參考：
難，後綴數組
較難，最長公共子串，經典問題，後綴數組
很難，後綴數組
可參考解題報告
很難，數據結構綜合運用
四.圖論基礎
參考資料：
劉汝佳《演算法藝術與信息學競賽》
《演算法導論》
《網路演算法與復雜性理論》謝政
推薦題目:
簡單，歐拉路
中等，無向圖割邊
較難，無向圖雙連通分支
中等，最小度限制生成樹，《演算法藝術與信息學競賽》中有解答
中等，最小比率生成樹，《演算法藝術與信息學競賽》中有解答
簡單，最短路問題
中等，差分約束系統，Bellman-Ford求解，《演算法藝術與信息學競賽》中有解答
簡單，Bellman-Ford
中等，網路流
較難，網路流
中等，二部圖最大匹配
較難，二部圖最大匹配
中等，二部圖最大權匹配
KM演算法參考《網路演算法與復雜性理論》
較難，二部圖最大權匹配
中等，LCA（最近公共祖先）問題
參考Tarjan's LCA algorithm 《演算法導論》第21章習題
較難，2-SAT問題
參考：
較難，2-SAT問題
較難，最小樹形圖
參考《網路演算法與復雜性理論》中朱-劉演算法
Ⅳ C++ 實現輸入一個二部圖的臨接矩陣，找出二部圖中的最大匹配，輸出為
#include <iostream>
#include <fstream>
#include<string>
#define MAXN 10000
using namespace std;
int mk[MAXN]; //mk[i]=0表示未訪問過，為1表示訪問過
int nx=MAXN, ny=MAXN; //X，Y集合中頂點的個數
int g[MAXN][MAXN]; //鄰接矩陣，g[i][j]為1，表示Xi,Yj有邊相連
int cx[MAXN],cy[MAXN]; //cx[i]最終求得的最大匹配中與Xi匹配的Y頂點，cy[i]同理
int pred[MAXN]; //用來記錄交錯軌的，同時也用來記錄Y集合中的頂點是否被遍歷過
int queue[MAXN]; //實現BFS搜索時，用到的隊列（用數組模擬）
int read() //讀取數據，數組存儲
{
ifstream cin("ER_data.txt",ios::in);
/廳則/ifstream cin("test.txt",ios::in);
for(int i=0;i<MAXN;i++)
for(int j=0;j<MAXN;j++)
g[i][j]=0;
int x,y;
while(cin>>x>>y)
g[x][y]=1;
cin.close();
return 0;
}
int path (int u)
{
for (int v=0; v <ny; v++ ) //考慮所有Yi頂點v
{
if (g[u][v]&&!mk[v]) //v與u鄰接，且沒有訪問過
{
mk[v]=1; //訪問v
//如果v沒有匹配；或者扮亂棚v已經匹配了，但從cy[v]出發可以找到一條增廣路
//注意，前一個條件成立，則不會遞歸調用
if (cy[v]==-1||path ( cy[v]) )
{
cx[u]=v;
cy[v]=u;
return 1;
}
}
}
return 0; //如果不存在從u出發的增廣路
}
int DMaxMatch() //DFS演算法
{
int res=0; //所求得的最大匹配
memset (cx,0xff,sizeof(cx)); //從0匹配開始增廣，將cx和cy各元素初始化為-1
memset (cy,0xff,sizeof(cy));
for (int i=0;i<=nx;i++)
{
if (cx[i]==-1) //從每個未蓋點出發進行尋找增廣路徑
{
memset( mk,0,sizeof(mk));
res+=path(i); //每找到一條增廣路，匹配數加1
}
}
return res;
}
int BMaxMatch() //BFS演算法
{
int i,j,y;
int cur,tail; //表示隊列頭和尾位置的下標
int res = 0; //所求得的最大匹配
memset (cx,0xff,sizeof(cx)); //初始化所有點為未匹配的狀態
memset (cy,0xff,sizeof(cy));
for ( i=0;i<陪判 nx;i++ )
{
if ( cx[i]!= -1) //對X集合中的每個未蓋點i進行BFS找交錯軌
continue;
for (j=0;j< ny;j++)
pred[j]=-2; //-2表示初始值
cur=tail=0; //初始化隊列
for ( j=0;j<ny;j++ ) //把i的鄰接頂點都入隊列
{
if ( g[i][j] )
{
pred [j]=-1; queue[tail++]=j; //-1表示遍歷到，是鄰接頂點
}
}
while ( cur <tail ) //BFS
{
y=queue[cur];
if (cy[y]==-1) break; //找到一個未匹配的頂點，則找到了一條增廣軌
cur++; //y已經被匹配給cy[y]了，從cy[y]出發，將它的鄰接頂點入隊列
for ( j = 0; j<ny; j++)
{
if (pred [j]==-2&&g[cy[y]][j])
{
pred [j] =y;
queue [tail++]=j;
}
}
}
if ( cur==tail ) continue; //沒有找到交錯軌
while (pred[y]>-1) //更改交錯軌上的匹配狀態
{
cx[ cy[pred[y]]]=y;
cy[y]=cy[pred[y]];
y=pred[y];
}
cy[y]=i; cx[i]=y;
res++; //匹配數加1
}
return res;
}
int main(){
read(); //讀數據
int max1,max2;
max1 = DMaxMatch(); //DFS找的最大匹配
max2 = BMaxMatch(); //BFS找的最大匹配
cout<<max1<<endl<<max2<<endl;
cin.get();
return 0;
}
-----------------------------------------------------------------------
3）Hopcroft-Karp演算法
/*Hopcroft-Karp演算法代碼*/
#include <iostream>
#include <fstream>
#include <cstdio>
#include <memory.h>
#include <queue>
using namespace std;
const int MAXN = 100 ;
const int INF = 1 << 28;
bool flag;
int p=MAXN,n=MAXN;
int Mx[MAXN], My[MAXN], Nx=MAXN, Ny=MAXN;
int dx[MAXN], dy[MAXN], dis;
bool vst[MAXN];
int g[MAXN][MAXN];
int read()
{
ifstream cin("ER_data-1.txt",ios::in);
//ifstream cin("ER_data.txt",ios::in);
//ifstream cin("test.txt",ios::in);
for(int i=0;i<MAXN;i++)
for(int j=0;j<MAXN;j++)
g[i][j]=0;
int x,y;
while(cin>>x>>y)
g[x][y]=1;
cin.close();
return 0;
}
bool BFS(void) //BFS
{
queue <int> Q;
dis = INF;
memset(dx, -1, sizeof(dx));
memset(dy, -1, sizeof(dy));
for (int i = 0; i < Nx; i++)
if (Mx[i] == -1)
{
Q.push(i); dx[i] = 0;
}
while (!Q.empty())
{
int u = Q.front(); Q.pop();
if (dx[u] > dis) break; //該增廣路徑長度大於dis還沒有結束，等待下一次BFS再擴充
for (int v = 0; v < Ny; v++)
if (g[u][v] && dy[v] == -1) //v是未匹配點
{
dy[v] = dx[u]+1;
if (My[v] == -1) dis = dy[v]; //得到本次BFS的最大遍歷長度
else
{
dx[My[v]] = dy[v]+1; //v是匹配點，繼續延伸
Q.push(My[v]);
}
}
}
return dis != INF;
}
bool DFS(int u) //DFS
{
for (int v = 0; v < Ny; v++)
if (!vst[v] && g[u][v] && dy[v] == dx[u]+1)
{
vst[v] = 1;
if (My[v] != -1 && dy[v] == dis) continue; //增廣路徑的長度大於本次查找的dis，是BFS被break的情況，也就是還不確定是否是增廣路徑，只有等再次調用BFS再判斷
if (My[v] == -1 || DFS(My[v])) //是增廣路徑，更新匹配集
{
My[v] = u; Mx[u] = v;
return 1;
}
}
return 0;
}
int MaxMatch()
{
int res = 0;
memset(Mx, -1, sizeof(Mx));
memset(My, -1, sizeof(My));
while (BFS())
{
memset(vst, 0, sizeof(vst));
for (int i = 0; i < Nx; i++)
if (Mx[i] == -1 && DFS(i))
res++; //查找到一個增廣路徑，匹配數增加
}
return res;
}
int main()
{
read();
int max = MaxMatch();
cout<<max<<endl;
cin.get();
return 0;
}
Ⅵ 推薦系統中用到的熱傳導演算法和物質擴散是怎麼用的
常常用二部圖來表示用戶和物品之間的關系：
把用戶（Users）看成一類，把物品（Objects）看作另一類。當某個用戶購買過某個商品時，他們之間會存在一條連邊。
而同一類點之間不存在連邊，即用戶與用戶之間，商品與商品之間不存在連邊，類似於這樣組成的網路就稱為二部圖。電子商務中的商品推薦，可以看做是二部圖上的鏈路挖掘問題，而擴散過程可以用來尋找網路中兩個節點之間的關聯強度。
Ⅶ 推薦演算法簡介
寫在最前面：本文內容主要來自於書籍《推薦系統實踐》和《推薦系統與深度學習》。
推薦系統是目前互聯網世界最常見的智能產品形式。從電子商務、音樂視頻網站，到作為互聯網經濟支柱的在線廣告和新穎的在線應用推薦，到處都有推薦系統的身影。推薦演算法是推薦系統的核心，其本質是通過一定的方式將用戶和物品聯系起來，而不同的推薦系統利用了不同的方式。
推薦系統的主要功能是以個性化的方式幫助用戶從極大的搜索空間中快速找到感興趣的對象。因此，目前所用的推薦系統多為個性化推薦系統。個性化推薦的成功應用需要兩個條件：
在推薦系統的眾多演算法中，基於協同的推薦和基於內容的推薦在實踐中得到了最廣泛的應用。本文也將從這兩種演算法開始，結合時間、地點上下文環境以及社交環境，對常見的推薦演算法做一個簡單的介紹。
基於內容的演算法的本質是對物品內容進行分析，從中提取特徵，然後基於用戶對何種特徵感興趣來推薦含有用戶感興趣特徵的物品。因此，基於內容的推薦演算法有兩個最基本的要求：
下面我們以一個簡單的電影推薦來介紹基於內容的推薦演算法。
現在有兩個用戶A、B和他們看過的電影以及打分情況如下：
其中問好（?）表示用戶未看過。用戶A對《銀河護衛隊 》《變形金剛》《星際迷航》三部科幻電影都有評分，平均分為 4 .7 分 （ (5+4+5 ) / 3=4.7 ）；對《三生三世》《美人魚》《北京遇上西雅圖》三部愛情電影評分平均分為 2.3 分 （ ( 3十2+2 ) /3=2.3 ）。現在需要給A推薦電影，很明顯A更傾向於科幻電影，因此推薦系統會給A推薦獨立日。而對於用戶B，通過簡單的計算我們可以知道更喜歡愛情電影，因此給其推薦《三生三世》。當然，在實際推薦系統中，預測打分比這更加復雜些，但是其原理是一樣的。
現在，我們可以將基於內容的推薦歸納為以下四個步驟：
通過上面四步就能快速構建一個簡單的推薦系統。基於內容的推薦系統通常簡單有效，可解釋性好，沒有物品冷啟動問題。但他也有兩個明顯的缺點：
最後，順便提一下特徵提取方法：對於某些特徵較為明確的物品，一般可以直接對其打標簽，如電影類別。而對於文本類別的特徵，則主要是其主題情感等，則些可以通過tf-idf或LDA等方法得到。
基於協同的演算法在很多地方也叫基於鄰域的演算法，主要可分為兩種：基於用戶的協同演算法和基於物品的協同演算法。
啤酒和尿布的故事在數據挖掘領域十分有名，該故事講述了美國沃爾瑪超市統計發現啤酒和尿布一起被購買的次數非常多，因此將啤酒和尿布擺在了一起，最後啤酒和尿布的銷量雙雙增加了。這便是一個典型的物品協同過濾的例子。
基於物品的協同過濾指基於物品的行為相似度（如啤酒尿布被同時購買）來進行物品推薦。該演算法認為，物品A和物品B具有很大相似度是因為喜歡物品A的用戶大都也喜歡物品B。
基於物品的協同過濾演算法主要分為兩步：
基於物品的協同過濾演算法中計算物品相似度的方法有以下幾種：
（1）基於共同喜歡物品的用戶列表計算。
此外，John S. Breese再其論文中還提及了IUF（Inverse User Frequence，逆用戶活躍度）的參數，其認為活躍用戶對物品相似度的貢獻應該小於不活躍的用戶，應該增加IUF參數來修正物品相似度的公式：
上面的公式只是對活躍用戶做了一種軟性的懲罰， 但對於很多過於活躍的用戶， 比如某位買了當當網80%圖書的用戶， 為了避免相似度矩陣過於稠密， 我們在實際計算中一般直接忽略他的興趣列表， 而不將其納入到相似度計算的數據集中。
（2）基於餘弦相似度計算。
（3）熱門物品的懲罰。
從上面（1）的相似度計算公式中，我們可以發現當物品 i 被更多人購買時，分子中的 N(i) ∩ N(j) 和分母中的 N(i) 都會增長。對於熱門物品，分子 N(i) ∩ N(j) 的增長速度往往高於 N(i)，這就會使得物品 i 和很多其他的物品相似度都偏高，這就是 ItemCF 中的物品熱門問題。推薦結果過於熱門，會使得個性化感知下降。以歌曲相似度為例，大部分用戶都會收藏《小蘋果》這些熱門歌曲，從而導致《小蘋果》出現在很多的相似歌曲中。為了解決這個問題，我們對於物品 i 進行懲罰，例如下式， 當α∈(0, 0.5) 時，N(i) 越小，懲罰得越厲害，從而使熱門物品相關性分數下降（ 博主註：這部分未充分理解 ）：
此外，Kary pis在研究中發現如果將ItemCF的相似度矩陣按最大值歸一化， 可以提高推薦的准確率。 其研究表明， 如果已經得到了物品相似度矩陣w， 那麼可以用如下公式得到歸一化之後的相似度矩陣w'：
歸一化的好處不僅僅在於增加推薦的准確度，它還可以提高推薦的覆蓋率和多樣性。一般來說，物品總是屬於很多不同的類，每一類中的物品聯系比較緊密。假設物品分為兩類——A和B， A類物品之間的相似度為0.5， B類物品之間的相似度為0.6， 而A類物品和B類物品之間的相似度是0.2。 在這種情況下， 如果一個用戶喜歡了5個A類物品和5個B類物品， 用ItemCF給他進行推薦， 推薦的就都是B類物品， 因為B類物品之間的相似度大。 但如果歸一化之後， A類物品之間的相似度變成了1， B類物品之間的相似度也是1， 那麼這種情況下， 用戶如果喜歡5個A類物品和5個B類物品， 那麼他的推薦列表中A類物品和B類物品的數目也應該是大致相等的。 從這個例子可以看出， 相似度的歸一化可以提高推薦的多樣性。
那麼，對於兩個不同的類，什麼樣的類其類內物品之間的相似度高，什麼樣的類其類內物品相似度低呢？一般來說，熱門的類其類內物品相似度一般比較大。如果不進行歸一化，就會推薦比較熱門的類裡面的物品，而這些物品也是比較熱門的。因此，推薦的覆蓋率就比較低。相反，如果進行相似度的歸一化，則可以提高推薦系統的覆蓋率。
最後，利用物品相似度矩陣和用戶打過分的物品記錄就可以對一個用戶進行推薦評分：
基於用戶的協同演算法與基於物品的協同演算法原理類似，只不過基於物品的協同是用戶U購買了A物品，會計算經常有哪些物品與A一起購買（也即相似度），然後推薦給用戶U這些與A相似的物品。而基於用戶的協同則是先計算用戶的相似性（通過計算這些用戶購買過的相同的物品），然後將這些相似用戶購買過的物品推薦給用戶U。
基於用戶的協同過濾演算法主要包括兩個步驟：
步驟（1）的關鍵是計算用戶的興趣相似度，主要是利用用戶的行為相似度計算用戶相似度。給定用戶 u 和 v，N(u) 表示用戶u曾經有過正反饋（譬如購買）的物品集合，N(v) 表示用戶 v 曾經有過正反饋的物品集合。那麼我們可以通過如下的 Jaccard 公式簡單的計算 u 和 v 的相似度：
或通過餘弦相似度：
得到用戶之間的相似度之後，UserCF演算法會給用戶推薦和他興趣最相似的K個用戶喜歡的物品。如下的公式度量了UserCF演算法中用戶 u 對物品 i 的感興趣程度：
首先回顧一下UserCF演算法和ItemCF演算法的推薦原理：UserCF給用戶推薦那些和他有共同興趣愛好的用戶喜歡的物品， 而ItemCF給用戶推薦那些和他之前喜歡的物品具有類似行為的物品。
（1）從推薦場景考慮
首先從場景來看，如果用戶數量遠遠超過物品數量，如購物網站淘寶，那麼可以考慮ItemCF，因為維護一個非常大的用戶關系網是不容易的。其次，物品數據一般較為穩定，因此物品相似度矩陣不必頻繁更新，維護代價較小。
UserCF的推薦結果著重於反應和用戶興趣相似的小群體的熱點，而ItemCF的推薦結果著重於維系用戶的歷史興趣。換句話說，UserCF的推薦更社會化，反應了用戶所在小型興趣群體中物品的熱門程度，而ItemCF的推薦更加個性化，反應了用戶自己的個性傳承。因此UserCF更適合新聞、微博或微內容的推薦，而且新聞內容更新頻率非常高，想要維護這樣一個非常大而且更新頻繁的表無疑是非常難的。
在新聞類網站中，用戶的興趣愛好往往比較粗粒度，很少會有用戶說只看某個話題的新聞，而且往往某個話題也不是每天都會有新聞。 個性化新聞推薦更強調新聞熱點，熱門程度和時效性是個性化新聞推薦的重點，個性化是補充，所以 UserCF 給用戶推薦和他有相同興趣愛好的人關注的新聞，這樣在保證了熱點和時效性的同時，兼顧了個性化。
（2）從系統多樣性（也稱覆蓋率，指一個推薦系統能否給用戶提供多種選擇）方面來看，ItemCF的多樣性要遠遠好於UserCF，因為UserCF更傾向於推薦熱門物品。而ItemCF具有較好的新穎性，能夠發現長尾物品。所以大多數情況下，ItemCF在精度上較小於UserCF，但其在覆蓋率和新穎性上面卻比UserCF要好很多。
在介紹本節基於矩陣分解的隱語義模型之前，讓我們先來回顧一下傳統的矩陣分解方法SVD在推薦系統的應用吧。
基於SVD矩陣分解在推薦中的應用可分為如下幾步：
SVD在計算前會先把評分矩陣 A 缺失值補全，補全之後稀疏矩陣 A 表示成稠密矩陣，然後將分解成 A' = U∑V T 。但是這種方法有兩個缺點：（1）補成稠密矩陣後需要耗費巨大的儲存空間，對這樣巨大的稠密矩陣進行儲存是不現實的；（2）SVD的計算復雜度很高，對這樣大的稠密矩陣中進行計算式不現實的。因此，隱語義模型就被發明了出來。
更詳細的SVD在推薦系統的應用可參考 奇異值分解SVD簡介及其在推薦系統中的簡單應用 。
隱語義模型（Latent Factor Model）最早在文本挖掘領域被提出，用於找到文本的隱含語義。相關的演算法有LSI，pLSA，LDA和Topic Model。本節將對隱語義模型在Top-N推薦中的應用進行詳細介紹，並通過實際的數據評測該模型。
隱語義模型的核心思想是通過隱含特徵聯系用戶興趣和物品。讓我們通過一個例子來理解一下這個模型。
現有兩個用戶，用戶A的興趣涉及偵探小說、科普圖書以及一些計算機技術書，而用戶B的興趣比較集中在數學和機器學習方面。那麼如何給A和B推薦圖書呢？
我們可以對書和物品的興趣進行分類。對於某個用戶，首先得到他的興趣分類，然後從分類中挑選他可能喜歡的物品。簡言之，這個基於興趣分類的方法大概需要解決3個問題：
對於第一個問題的簡單解決方案是找相關專業人員給物品分類。以圖書為例，每本書出版時，編輯都會給出一個分類。但是，即使有很系統的分類體系，編輯給出的分類仍然具有以下缺點：（1）編輯的意見不能代表各種用戶的意見；（2）編輯很難控制分類的細粒度；（3）編輯很難給一個物品多個分類；（4）編輯很難給一個物品多個分類；（5）編輯很難給出多個維度的分類；（6）編輯很難決定一個物品在某一個類別中的權重。
為了解決上述問題，研究員提出可以從數據出發，自動找到那些分類，然後進行個性化推薦。隱語義模型由於採用基於用戶行為統計的自動聚類，較好地解決了上面提出的5個問題。
LFM將矩陣分解成2個而不是3個：
推薦系統中用戶和物品的交互數據分為顯性反饋和隱性反饋數據。隱式模型中多了一個置信參數，具體涉及到ALS（交替最小二乘法，Alternating Least Squares）中對於隱式反饋模型的處理方式——有的文章稱為「加權的正則化矩陣分解」：
一個小細節：在隱性反饋數據集中，只有正樣本（正反饋）沒有負反饋（負樣本），因此如何給用戶生成負樣本來進行訓練是一個重要的問題。Rong Pan在其文章中對此進行了探討，對比了如下幾種方法：
用戶行為很容易用二分圖表示，因此很多圖演算法都可以應用到推薦系統中。基於圖的模型（graph-based model）是推薦系統中的重要內容。很多研究人員把基於領域的模型也稱為基於圖的模型，因為可以把基於領域的模型看作基於圖的模型的簡單形式。
在研究基於圖的模型之前，需要將用戶行為數據表示成圖的形式。本節的數據是由一系列用戶物品二元組 (u, i) 組成的，其中 u 表示用戶對物品 i 產生過行為。
令 G(V, E) 表示用戶物品二分圖，其中 V=V U UV I 由用戶頂點 V U 和物品節點 V I 組成。對於數據集中每一個二元組 (u, i) ，圖中都有一套對應的邊 e(v u , v i )，其中 v u ∈V U 是用戶對應的頂點，v i ∈V I 是物品i對應的頂點。如下圖是一個簡單的物品二分圖，其中圓形節點代表用戶，方形節點代表物品，用戶物品的直接連線代表用戶對物品產生過行為。比如下圖中的用戶A對物品a、b、d產生過行為。
度量圖中兩個頂點之間相關性的方法很多，但一般來說圖中頂點的相關性主要取決於下面3個因素：
而相關性高的一對頂點一般具有如下特徵：
舉個例子，如下圖，用戶A和物品c、e沒有邊直連，但A可通過一條長度為3的路徑到達c，而Ae之間有兩條長度為3的路徑。那麼A和e的相關性要高於頂點A和c，因而物品e在用戶A的推薦列表中應該排在物品c之前，因為Ae之間有兩條路徑。其中，（A,b,C,e）路徑經過的頂點的出度為（3，2，2，2），而 (A,d,D,e) 路徑經過了一個出度比較大的頂點D，所以 (A,d,D,e) 對頂點A與e之間相關性的貢獻要小於（A,b,C,e）。
基於上面3個主要因素，研究人員設計了很多計算圖中頂點相關性的方法，本節將介紹一種基於隨機遊走的PersonalRank演算法。
假設要給用戶u進行個性化推薦，可以從用戶u對應的節點 v u 開始在用戶物品二分圖上進行隨機遊走。遊走到任一節點時，首先按照概率α決定是繼續遊走還是停止這次遊走並從 v u 節點重新開始遊走。若決定繼續遊走，則從當前節點指向的節點中按照均勻分布隨機選擇一個節點作為遊走下次經過的節點。這樣，經過很多次隨機遊走後，每個物品被訪問到的概率會收斂到一個數。最終的推薦列表中物品的權重就是物品節點的訪問概率。
上述演算法可以表示成下面的公式：
雖然通過隨機遊走可以很好地在理論上解釋PersonalRank演算法，但是該演算法在時間復雜度上有明顯的缺點。因為在為每個用戶進行推薦時，都需要在整個用戶物品二分圖上進行迭代，知道所有頂點的PR值都收斂。這一過程的時間復雜度非常高，不僅無法在線進行實時推薦，離線計算也是非常耗時的。
有兩種方法可以解決上面PersonalRank時間復雜度高的問題：
（1）減少迭代次數，在收斂之前停止迭代。但是這樣會影響最終的精度。
（2）從矩陣論出發，重新涉及演算法。另M為用戶物品二分圖的轉移概率矩陣，即：
網路社交是當今社會非常重要甚至可以說是必不可少的社交方式，用戶在互聯網上的時間有相當大的一部分都用在了社交網路上。
當前國外最著名的社交網站是Facebook和Twitter，國內的代表則是微信/QQ和微博。這些社交網站可以分為兩類：
需要指出的是，任何一個社交網站都不是單純的社交圖譜或興趣圖譜。如QQ上有些興趣愛好群可以認識不同的陌生人，而微博中的好友也可以是現實中認識的。
社交網路定義了用戶之間的聯系，因此可以用圖定義社交網路。我們用圖 G(V,E,w) 定義一個社交網路，其中V是頂點集合，每個頂點代表一個用戶，E是邊集合，如果用戶va和vb有社交網路關系，那麼就有一條邊 e(v a , v b ) 連接這兩個用戶，而 w(v a , v b )定義了邊的權重。一般來說，有三種不同的社交網路數據：
和一般購物網站中的用戶活躍度分布和物品流行度分布類似，社交網路中用戶的入度（in degree，表示有多少人關注）和出度（out degree，表示關注多少人）的分布也是滿足長尾分布的。即大部分人關注的人都很少，被關注很多的人也很少。
給定一個社交網路和一份用戶行為數據集。其中社交網路定義了用戶之間的好友關系，而用戶行為數據集定義了不同用戶的歷史行為和興趣數據。那麼最簡單的演算法就是給用戶推薦好友喜歡的物品集合。即用戶u對物品i的興趣 p ui 可以通過如下公式計算。
用戶u和用戶v的熟悉程度描述了用戶u和用戶在現實社會中的熟悉程度。一般來說，用戶更加相信自己熟悉的好友的推薦，因此我們需要考慮用戶之間的熟悉度。下面介紹3中衡量用戶熟悉程度的方法。
（1）對於用戶u和用戶v，可以使用共同好友比例來計算他們的相似度：
上式中 out(u) 可以理解為用戶u關注的用戶合集，因此 out(u) ∩ out(v) 定義了用戶u、v共同關注的用戶集合。
（2）使用被關注的用戶數量來計算用戶之間的相似度，只要將公式中的 out(u) 修改為 in(u)：
in(u) 是指關注用戶u的集合。在無向社交網路中，in(u)和out(u)是相同的，而在微博這種有向社交網路中，這兩個集合的含義就不痛了。一般來說，本方法適合用來計算微博大V之間的相似度，因為大v往往被關注的人數比較多；而方法（1）適用於計算普通用戶之間的相似度，因為普通用戶往往關注行為比較豐富。
（3）除此之外，還可以定義第三種有向的相似度：這個相似度的含義是用戶u關注的用戶中，有多大比例也關注了用戶v：
這個相似度有一個缺點，就是在該相似度下所有人都和大v有很大的相似度，這是因為公式中的分母並沒有考慮 in(v) 的大小，所以可以把 in(v) 加入到上面公式的分母，來降低大v與其他用戶的相似度：
上面介紹了3種計算用戶之間相似度（或稱熟悉度）的計算方法。除了熟悉程度，還需要考慮用戶之間的興趣相似度。我們和父母很熟悉，但很多時候我們和父母的興趣確不相似，因此也不會喜歡他們喜歡的物品。因此，在度量用戶相似度時，還需要考慮興趣相似度，而興趣相似度可以通過和UserCF類似的方法度量，即如果兩個用戶喜歡的物品集合重合度很高，兩個用戶的興趣相似度很高。
最後，我們可以通過加權的形式將兩種權重合並起來，便得到了各個好有用戶的權重了。
有了權重，我們便可以針對用戶u挑選k個最相似的用戶，把他們購買過的物品中，u未購買過的物品推薦給用戶u即可。打分公式如下：
其中 w' 是合並後的權重，score是用戶v對物品的打分。
node2vec的整體思路分為兩個步驟：第一個步驟是隨機遊走（random walk），即通過一定規則隨機抽取一些點的序列；第二個步驟是將點的序列輸入至word2vec模型從而得到每個點的embedding向量。
隨機遊走在前面基於圖的模型中已經介紹過，其主要分為兩步：（1）選擇起始節點；（2）選擇下一節點。起始節點選擇有兩種方法：按一定規則抽取一定量的節點或者以圖中所有節點作為起始節點。一般來說會選擇後一種方法以保證所有節點都會被選取到。
在選擇下一節點方法上，最簡單的是按邊的權重來選擇，但在實際應用中需要通過廣度優先還是深度優先的方法來控制遊走范圍。一般來說，深度優先發現能力更強，廣度優先更能使社區內（較相似）的節點出現在一個路徑里。
斯坦福大學Jure Leskovec教授給出了一種可以控制廣度優先或者深度優先的方法。
以上圖為例，假設第一步是從t隨機遊走到v，這時候我們要確定下一步的鄰接節點。本例中，作者定義了p和q兩個參數變數來調節遊走，首先計算其鄰居節點與上一節點t的距離d，根據下面的公式得到α：
一般從每個節點開始遊走5~10次，步長則根據點的數量N遊走根號N步。如此便可通過random walk生成點的序列樣本。
得到序列之後，便可以通過word2vec的方式訓練得到各個用戶的特徵向量，通過餘弦相似度便可以計算各個用戶的相似度了。有了相似度，便可以使用基於用戶的推薦演算法了。
推薦系統需要根據用戶的歷史行為和興趣預測用戶未來的行為和興趣，因此大量的用戶行為數據就成為推薦系統的重要組成部分和先決條件。如何在沒有大量用戶數據的情況下設計個性化推薦系統並且讓用戶對推薦結果滿意從而願意使用推薦系統，就是冷啟動問題。
冷啟動問題主要分為三類：
針對用戶冷啟動，下面給出一些簡要的方案：
（1）有效利用賬戶信息。利用用戶注冊時提供的年齡、性別等數據做粗粒度的個性化；
（2）利用用戶的社交網路賬號登錄（需要用戶授權），導入用戶在社交網站上的好友信息，然後給用戶推薦其好友喜歡的物品；
（3）要求用戶在登錄時對一些物品進行反饋，手機用戶對這些物品的興趣信息，然後給用推薦那些和這些物品相似的物品；
（4）提供非個性化推薦。非個性化推薦的最簡單例子就是熱門排行榜，我們可以給用戶推薦熱門排行榜，然後等到用戶數據收集到一定的時候，在切換為個性化推薦。
對於物品冷啟動，可以利用新加入物品的內容信息，將它們推薦給喜歡過和他們相似的物品的用戶。
對於系統冷啟動，可以引入專家知識，通過一定高效的方式快速建立起物品的相關度表。
在上面介紹了一些推薦系統的基礎演算法知識，這些演算法大都是比較經典且現在還在使用的。但是需要注意的是，在實踐中，任何一種推薦演算法都不是單獨使用的，而是將多種推薦演算法結合起來，也就是混合推薦系統，但是在這里並不準備介紹，感興趣的可以查閱《推薦系統》或《推薦系統與深度學習》等書籍。此外，在推薦中非常重要的點擊率模型以及基於矩陣的一些排序演算法在這里並沒有提及，感興趣的也可自行學習。
雖然現在用的很多演算法都是基於深度學習的，但是這些經典演算法能夠讓我們對推薦系統的發展有一個比較好的理解，同時，更重要的一點——「推陳出新」，只有掌握了這些經典的演算法，才能提出或理解現在的一些更好地演算法。
Ⅷ 推薦演算法簡介
在這個時代，無論是信息消費者還是信息生產者都遇到了很大的挑戰:作為信息消費者，如何從大量信息中找到自己感興趣的信息是一件非常困難的事情;作為信息生產者， 如何讓自己生產的信息脫穎而出，受到廣大用戶的關注，也是一件非常困難的事情。推薦系統就是解決這一矛盾的重要工具。推薦系統的任務就是聯系用戶和信息，一方面幫助用戶發現對自己有價值的信息，另一方面讓信息能夠展現在對它感興趣的用戶面前，從而實現信息消費者和信息 生產者的雙贏。和搜索引擎不同的是，推薦系統不需要用戶提供明確的需求，而是通過分析用戶的歷史行為給用 戶的興趣建模，從而主動給用戶推薦能夠滿足他們興趣和需求的信息 個性化推薦的成功需要兩個條件。第一是存在 信息過載 ，因為如果用戶可以很容易地從所有物品中找到喜歡的物品，就不需要個性化推薦。第二用 戶大部分時候沒有特別明確的需求 ，因為用戶沒有明確的需求，可以直接通過搜索引擎找到感興趣的物品。
一個完整的推薦系統一般存在3個參與方：用戶、物品提供者和提供推薦系統的網站。以圖書推薦為例， 首先，推薦系統需要滿足用戶的需求，給用戶推薦那些令他們感興趣的圖書。其次，推薦系統要讓各出版社的書都能夠被推薦給對其感興趣的用戶，而不是只推薦幾個大型出版社的書。最後， 好的推薦系統設計，能夠讓推薦系統本身收集到高質量的用戶反饋，不斷完善推薦的質量，增加 用戶和網站的交互，提高網站的收入。因此在評測一個推薦演算法時，需要同時考慮三方的利益， 一個好的推薦系統是能夠令三方共贏的系統。
推薦系統中，主要有3種評測推薦效果的實驗方法，即離線實驗(offline experiment)、用戶調查(user study)和在線實驗(online experiment)。
2.1 離線實驗
離線實驗的方法一般由如下幾個步驟構成: (1) 通過日誌系統獲得用戶行為數據，並按照一定格式生成一個標準的數據集; (2) 將數據集按照一定的規則分成訓練集和測試集; (3) 在訓練集上訓練用戶興趣模型，在測試集上進行預測; (4) 通過事先定義的離線指標評測演算法在測試集上的預測結果。
從上面的步驟可以看到，推薦系統的離線實驗都是在數據集上完成的，也就是說它不需要一個實際的系統來供它實驗，而只要有一個從實際系統日誌中提取的數據集即可。這種實驗方法的 好處是不需要真實用戶參與，可以直接快速地計算出來，從而方便、快速地測試大量不同的演算法。它的主要缺點是無法獲得很多商業上關注的指標，如點擊率、轉化率等，而找到和商業指標非常相關的離線指標也是很困難的事情
2.2 用戶調查
3.3 在線實驗
在完成離線實驗和必要的用戶調查後，可以將推薦系統上線做 AB測試 ，將它和舊的演算法進行比較。 AB測試 是一種很常用的在線評測演算法的實驗方法。它通過一定的規則將用戶隨機分成幾組，並對不同組用戶採取不同的演算法，然後通過統計不同組用戶的各種不同的評測指標比較不同演算法的好壞。 AB測試的優點是可以公平獲得不同演算法實際在線時的性能指標，包括商業上關注的指標。 AB測試的缺點主要是周期比較長，必須進行長期的實驗才能得到可靠的結果。因此一般不會用 AB測試測試所有的演算法，而只是用它測試那些在離線實驗和用戶調查中表現很好的演算法。其次， 一個大型網站的AB測試系統的設計也是一項復雜的工程。
一般來說，一個新的推薦演算法最終上線，需要完成上面所說的3個實驗。 1）首先，需要通過離線實驗證明它在很多離線指標上優於現有的演算法。 2）然後，需要通過用戶調查確定它的用戶滿意度不低於現有的演算法。 3）最後，通過在線的AB測試確定它在我們關心的指標上。
本節將介紹各種推薦系統的評測指標。這些評測指標可用於評價推薦系統各方面的性能。這 些指標有些可以定量計算，有些只能定性描述，有些可以通過離線實驗計算，有些需要通過用戶 調查獲得，還有些只能在線評測。
(1) 用戶滿意度
用戶作為推薦系統的重要參與者，其滿意度是評測推薦系統的最重要指標。但是，用戶滿意度沒有辦法離線計算，只能通過用戶調查或者在線實驗獲得。
在在線系統中，用戶滿意度主要通過一些 對用戶行為的統計得到 。比如在電子商務網站中，用戶如果購買了推薦的商品，就表示他們在一定程度上滿意。因此，我們可以 利用購買率度量用 戶的滿意度 。此外，有些網站會通過設計一些用戶 反饋界面收集用戶滿意度 。比如在視頻網站中，都有對推薦結果滿意或者不滿意的 反饋按鈕 ，通過統計兩種按鈕的單擊情況就可以度量系統的用戶滿意度。更一般的情況下，我們可以用 點擊率、用戶停留時間和轉化率等指標度量 用戶的滿意度。
(2) 預測准確度
預測准確度度量一個推薦系統或者推薦演算法預測用戶行為的能力。這個指標是最重要的推薦系統離線評測指標
在計算該指標時需要有一個離線的數據集，該數據集包含用戶的歷史行為記錄。然後，將該數據集通過時間分成訓練集和測試集。最後，通過在訓練集上建立用戶的行為和興趣模型預測用戶在測試集上的行為，並計算預測行為和測試集上實際行為的重合度作為預測准確度。 預測准確度指標有分為以下幾種：
評分預測：
預測用戶對物品評分的行為成為評分預測，在評分預測中，預測准確度一般通過均方根誤差RMSE和平均絕對誤差MAE計算，對於測試集中的一個用戶u和物品i,令[圖片上傳失敗...(image-62a797-1560412790460)] 是用戶u對物品i的實際評分，而[圖片上傳失敗...(image-28cfbc-1560412790460)] 是推薦演算法給出的預測評分，那麼RMSE定義為：
其中T為樣本個數
MAE採用絕對值計算預測誤差，它的定義為:
TopN推薦
網站在提供推薦服務時，一般是給用戶一個個性化的推薦列表，這種推薦叫做TopN推薦。TopN推薦的預測准確率一般通過准確率(precision)/召回率(recall)度量。 令R(u)是根據用戶在訓練集上的行為給用戶作出的推薦列表，而T(u)是用戶在測試集上的行為列表。那麼，推薦結果的召回率定義為:
推薦結果准確率定義：
(3) 覆蓋率
覆蓋率（coverage）描述一個推薦系統對物品長尾的發掘能力。覆蓋率有不同的定義方法，最簡單的定義為推薦系統能夠推薦出來的物品占總物品集合的比例。假設系統的用戶集合U，推薦系統給每個用戶推薦一個長度為N的物品集合R（u）。那麼推薦系統的覆蓋率可以通過下面的公式計算：
I為總物品數
此外，從上面的定義也可以看到，熱門排行榜的推薦覆蓋率是很低的，它只會 推薦那些熱門的物品，這些物品在總物品中占的比例很小。一個好的推薦系統不僅需要有比較高的用戶滿意度，也要有較高的覆蓋率。
但是上面的定義過於粗略。覆蓋率為100%的系統可以有無數的物品流行度分布。為了更細致地描述推薦系統發掘長尾的能力，需要統計推薦列表中不同物品出現次數的分布。如果所有的 物品都出現在推薦列表中，且出現的次數差不多，那麼推薦系統發掘長尾的能力就很好。因此， 可以通過研究物品在推薦列表中出現次數的分布描述推薦系統挖掘長尾的能力。如果這個分布比 較平，那麼說明推薦系統的覆蓋率較高，而如果這個分布較陡峭，說明推薦系統的覆蓋率較低。 在資訊理論和經濟學中有兩個著名的指標可以用來定義覆蓋率。第一個是信息熵:
其中：n代表推薦列表中物品類別個數，p(i)代表每個類別的所佔的比率
第二個指標是基尼系數：
(4) 多樣性
為了滿足用戶廣泛的興趣，推薦列表需要能夠覆蓋用戶不同的興趣領域，即推薦結果需要具有多樣性。多樣性推薦列表的好處用一句俗話表示就是（不在一棵樹上弔死）。盡管用戶的興趣在較長的時間跨度中是一樣的。但具體到用戶訪問推薦系統的某一時刻，其興趣往往是單一的，那麼如果推薦列表只能覆蓋用戶的一個興趣點，而這個興趣點不是用戶這個時刻的興趣點，推薦結果就不會讓用戶滿意。反之如果推薦列表表較多樣，覆蓋用戶絕大多數的興趣點，那麼久會增加用戶找到感興趣物品的概率。因此給用戶的推薦列表也需要滿足用戶廣泛的興趣，即具有多樣性。
多樣性描述了推薦列表中物品兩兩之間的不相似性，因此，多樣性和相似性是對應的。假設s(i, j) ∈Î[0,1] 定義了物品i和j之間的相似度，那麼用戶u的推薦列表R(u)的多樣性定義如下：
而推薦系統的整體多樣性可以定義為所有用戶推薦列表多樣性的平均值：
(5) 新穎性
新穎的推薦是指給用戶推薦那些他們以前沒有聽說過的物品。在一個網站中 實現新穎性 的最簡單辦法是，把那些用戶之前在網站中對其有過行為的物品從推薦列表中過濾掉。比如在一個視 頻網站中，新穎的推薦不應該給用戶推薦那些他們已經看過、打過分或者瀏覽過的視頻。 評測新穎度的最簡單方法是利用推薦結果的平均流行度，因為越不熱門的物品越 可能讓用戶覺得新穎。因此，如果推薦結果中物品的平均熱門程度較低，那麼推薦結果就可能有比較高的新穎性。
(6) 驚喜度
驚喜度(serendipity)是最近這幾年推薦系統領域最熱門的話題。如果推薦結果和用戶的歷史興趣不相似，但卻讓用戶覺得滿意，那麼就可以說推薦結果的驚喜度很高，而推薦的新穎性僅僅取決於用戶是否聽說過這個推薦結果。提高推薦驚喜度需要提高推薦結果的用戶滿意度，同時降低推薦結果和用戶歷史興趣的相似度。
(7) 信任度
度量推薦系統的信任度只能通過問卷調查的方式，詢問用戶是否信任推薦系統的推薦結果。 提高推薦系統的信任度主要有兩種方法。首先需要增加推薦系統的透明度(transparency)， 而增加推薦系統透明度的主要辦法是提供推薦解釋。只有讓用戶了解推薦系統的運行機制，讓用 戶認同推薦系統的運行機制，才會提高用戶對推薦系統的信任度。其次是考慮用戶的社交網路 信息，利用用戶的好友信息給用戶做推薦，並且用好友進行推薦解釋。這是因為用戶對他們的 好友一般都比較信任，因此如果推薦的商品是好友購買過的，那麼他們對推薦結果就會相對比較信任
(8) 實時性
在很多網站中，因為物品(新聞、微博等)具有很強的時效性，所以需要在物品還具有時效 性時就將它們推薦給用戶。 推薦系統的實時性包括兩個方面。首先，推薦系統需要實時地更新推薦列表來滿足用戶新的 行為變化。實時性的第二個方面是推薦系統需要能夠將新加入系統的物品推薦給用戶。這主要考驗了推 薦系統處理物品冷啟動的能力。
(9) 健壯性
健壯性(即robust,魯棒 性)指標衡量了一個推薦系統抗擊作弊的能力。演算法健壯性的評測主要利用模擬攻擊。首先，給定一個數據集和一個演算法，可以用這個演算法 給這個數據集中的用戶生成推薦列表。然後，用常用的攻擊方法向數據集中注入雜訊數據，然後 利用演算法在注入雜訊後的數據集上再次給用戶生成推薦列表。最後，通過比較攻擊前後推薦列表 的相似度評測演算法的健壯性。如果攻擊後的推薦列表相對於攻擊前沒有發生大的變化，就說明算 法比較健壯
(10) 商業目標
很多時候，網站評測推薦系統更加註重網站的商業目標是否達成，而商業目標和網站的盈利模式是息息相關的
(11) 總結
上一節介紹了很多評測指標，但是在評測系統中還需要考慮評測維度，比如一個推薦演算法， 雖然整體性能不好，但可能在某種情況下性能比較好，而增加評測維度的目的就是知道一個演算法 在什麼情況下性能最好。這樣可以為融合不同推薦演算法取得最好的整體性能帶來參考。
一般來說，評測維度分為如下3種。 1） 用戶維度 ：主要包括用戶的人口統計學信息、活躍度以及是不是新用戶等。 2） 物品維度 ：包括物品的屬性信息、流行度、平均分以及是不是新加入的物品等。 3） 時間維度 ：包括季節，是工作日還是周末，是白天還是晚上等。 如果能夠在推薦系統評測報告中包含不同維度下的系統評測指標，就能幫我們全面地了解推 薦系統性能，找到一個看上去比較弱的演算法的優勢，發現一個看上去比較強的演算法的缺點。