三百萬級用戶數據做基於用戶協同過濾演算法，相似度如何計算？

01-23

用戶量有300萬，物品量有100種，興趣度無法度量，考慮通過用戶的其他屬性計算300萬用戶之間的相似度，然後按照相似度統計topN，再進行推薦，可是計算300萬用戶之間的相似度需要九萬億次計算，超過公司Hadoop集群處理能力，請問有何辦法？

1 先對用戶做個過濾，只訪問一種，或訪問太多種的都沒有意義，尤其訪問太多的（一兩百種都放問了），會嚴重影響計算效率

2 只計算訪問有交集的，需要先找出每個物品的所有訪問者

3 交集的計算可以通過劃時間窗口來進一步剪枝

另，高階的做法是，用SGD做矩陣分解，對用戶向量做做最近鄰搜索（可選Faiss、annoy之類）

我覺得如果要選擇協同過濾演算法，就要首先搞清楚自己的演算法應用場景，然後基於場景選擇協同的規則。

其實，usercf和itemcf都有其適用的場合。一般在選取的時候，我們會考慮以下幾個方面。

1.user和item的數量比。如果item的量遠小於user的數量，那麼我們優先選擇itemcf，因為這樣可以大大減小similarity的計算成本。

2.推薦場景。一般來說，像新聞、資訊、社交網站這種，信息變化頻繁，item時效性強且不穩定，就更適合做usercf。而像電商、圖書、電影網站，用戶的興趣想對固定，短時間變化不大，更傾向於找到與自己近段時間所喜歡的物品相似的物品，那麼itemcf會更合適。

3.物品覆蓋度。usercf是從人這個群體出發，推薦你朋友喜歡的東西，而itemcf是從物品出發，推薦跟你以前喜歡的東西類似的東西。那麼作為一個推薦系統來看，itemcf的多樣性會比usercf差一些，因為usercf會推熱門的居多；但是在個體的推薦列表中，itemcf的新穎性會略好。

你這個數據規模並不大，不過我想不通為什麼一定要user cf。

硬算也是可以的，一般這種300w X 100的矩陣都非常稀疏，預掃描一遍，可以把那些全空的去掉，如果再能配合一些位操作（將100個item存為2個long），估計計算量能降到kw級別。

如果可以損失一些精度，可以先對300w用戶聚類，然後對每個類別用戶進行計算，計算量會大大降低

三百萬里找出5萬高質量/高活躍用戶，三百萬用戶這5萬取相似度就可以了。中間過程再優化下（從5萬中根據物品再次篩選），這個計算量應該是可以的。

300W用戶量並不大，計算usercf時有幾個trick：

1是有交集的用戶才可能進行相似度計算，這樣一來就可以避免掉大部分計算了，不可能N^2種組合都要計算啦~

2是在統計item的銷量用戶時要適當截斷，如果item太火，它對於用戶相似的貢獻是比較小的，如果item的平均銷量是1K，那其實演算法複雜度是M * 1k * 1k (M是item數量)

上面兩種trick幾乎對效果的影響較小，但對實現的幫助杠杠的。當然了，更正統的做法是做矩陣乘法時進行合理的矩陣分塊，演算法參考A MapReduce Algorithm for Matrix Multiplication