協(xié)同過濾是推薦算法中最基本的算法，主要分為基于用戶的協(xié)同過濾算法和基于物品的協(xié)同過濾算法。

這篇文章主要介紹基于用戶的協(xié)同過濾算法，簡單來說，要給用戶u作推薦，那么只要找出那些和u之前的行為類似的用戶，即和u比較像的用戶，把他們的行為推薦給用戶u即可。所以基于用戶的系統(tǒng)過濾算法包括兩個步驟：1)找到和目標(biāo)用戶興趣相似的用戶集合 2)找到這個集合中的用戶喜歡的，且目標(biāo)用戶沒有聽說過的物品推薦給目標(biāo)用戶。

第一步的關(guān)鍵點(diǎn)在于計算用戶之間的相似度，相似度一般通過Jaccard公式或者余弦相似度即可求得，及計算共有行為所占的比重(具體式子google就行，csdn插入公式不方便。。。)，所以目前而言，計算用戶相似度的復(fù)雜度是O(N*N), N為用戶數(shù)量，在用戶數(shù)比較大的網(wǎng)站中不實(shí)用，比如亞馬遜用戶數(shù)量肯定N>100000，那么這樣的復(fù)雜度是不可接受的。

第一步時間復(fù)雜度的改進(jìn)方法：因?yàn)楹芏嘤脩糸g其實(shí)相似度是為0的，如果看成是一個N*N的矩陣的話，肯定是個稀疏矩陣，那么我們其實(shí)沒有必要浪費(fèi)計算量在這些0上。我們可以建立物品到用戶的倒查表，及可以根據(jù)物品找到所有對該物品有過行為的用戶，然后遍歷各物品，對一個物品然后找到對該物品有過行為的用戶，然后計算這些用戶間的行為相似度(共有行為+1，同時計算這些用戶的行為數(shù))，最后計算兩用戶間的公有行為占各自行為的比重。

第一步計算相似度的改進(jìn)方法：舉個例子：如果兩人都買過《新華辭典》，并不能說明這兩人想像，因?yàn)檫@本書基本上人人都會買，而如果這兩人都買過《機(jī)器學(xué)習(xí)》，那么我們可以肯定，這兩人在這方面有相同的興趣愛好，也就是說，越是對冷門物品有同樣的行為，就越說明用戶的相似性，即在計算用戶相似性的時候，需要降低熱門物品的影響(通過計算流行度來實(shí)現(xiàn)，然后用1/N(i)來計算公共行為比重，N(i)表示流行度，這樣，流行度高的物品所占比重就比較低)

第二步則比較簡單，選出K個和用戶u最相似的用戶，把他們喜歡過的物品并且用戶u沒有喜歡過的物品推薦給u即可。這里面K的選擇非常重要。K越大，推薦的結(jié)果就越熱門，流行度就越高，同時覆蓋率越低，因?yàn)榛就扑]的都是流行的物品

本文作者 wangyuquanliuli