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

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

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

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

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

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

本文作者 wangyuquanliuli