168
[推薦係統] 自己動手寫一個推薦係統
廢話：
最近朋友在學習推薦係統相關，說是實現完整的推薦係統，於是我們三不之一會有一些討論和推導，想想索性整理出來。
在文中主要以工程中做推薦係統的流程著手，穿插一些經驗之談，並對於推薦係統的算法的學術界最新的研究進展和流派作一些介紹。當然由於我做推薦係統之時還年幼，可能有很多偏頗甚至錯誤的見解，就當拋磚引玉，還請各位大大指點。
Reading lists
雖然很多人覺得作為AI的分支之一，推薦跟自然語言處理等問題的難度不可同日而語。但所謂磨刀不誤砍柴工，我覺得，至少在開工前先應該閱讀這樣基本書，起碼要看看目錄，以對於推薦係統有個初步的了解。
中文書籍：
1.《推薦係統實踐》項亮https://book.douban.com/subject/10769749/
這本書你說他好吧，不如recommend handbook；你說他不好吧，確實又把很多基礎而簡單的問題講的很詳細，而且還是中文的。薄薄的一本書，分分鍾可以翻完，總而言之，是一本入門的好書。
外文書籍：
1.《Recommender Systems Handbook》Paul B. Kantor https://book.douban.com/subject/3695850/
其實所有敢自稱handbook的書都是神書。這本書寫的非常細，而且非常全，如果你去看一些推薦係統的一些比較冷門的topic的paper，比如fighting spam的，甚至能發現很多paper就是直接引用這本書裏相關章節的內容。可以說這本書是做推薦同學必備的枕邊書，沒看過這本書出去吹牛逼時你都不好意思說自己是做推薦的，不過說實在，真正看完的沒幾個，一般是用到哪裏查哪裏，我剛才就去豆瓣驗證了，幾個做推薦的都是在讀，一群文藝青年都是想讀。此書唯一的缺點是沒有出新版，有些地方已經成為時代的眼淚了。
2.《Recommender Systems - An Introduction》 Dietmar Jannach
https://book.douban.com/subject/5410320/
跟上麵一本差不多，學院派的綜述型的書，厚厚一本，不看的時候當枕頭用。
3.《mahout in action》Sean Owen https://book.douban.com/subject/4893547/
上麵的一中一外的書都是理論基礎的書，這本書就和工程有些沾邊。如果你要用mahout框架來做推薦係統，那麼是必須要掃一遍的；如果你不用mahout，看看其中的流程和代碼組織也是有一定好處的。
Paper：
由於《Recommender Systems Handbook》很多地方已經成為了時代的眼淚，這裏推薦一些綜述，以便開闊眼界。
一篇是physics report上麵的recommend system這篇綜述，可以說是最新最全的綜述了，看完後學術界都在折騰啥分分鍾就清楚了。https://arxiv.org/pdf/1202.1112v1.pdf
比較經典的是recommend system的state of art這篇綜述，很多老一輩的同誌喜歡推薦的，說實在這篇因為年代久遠，也已經成為時代的眼淚了。
開工：
上麵給了一些reading lists，並不是說要讀完所有的才能開工，隻是說，先看完個目錄，哪裏不懂查哪裏。在下麵介紹的做推薦係統的流程中，我隻是想給大家介紹個普通的推薦係統該怎麼做，所以很多地方都有偷懶，還請大家見諒。而且由於我不是做的在線的推薦係統，而是屬於隔天推薦的那種離線的，所以敘述工程的時候就是隻敘述離線的推薦。
數據準備：
一般來說，做推薦係統的數據一般分兩種，一種從在線的讀取，比如用戶產生一個行為，推薦係統就反應下（傳說豆瓣fm就是這麼做的？），還有一種就是從數據庫裏讀。
我個人一般是這樣做的：跟做反作弊的人打個招唿，讓他們在記用戶行為數據的時候順便存到各個線上服務器上，再寫個php腳本，從各個服務器上把我需要的日誌抓過來，然後當日要的最新的數據就來了。
但是這種地方其實存儲的數據是加了一些判斷的，也就是說是分類記錄的（因為很多記錄是別人刷的，比如丟一個鏈接到qq群裏讓別人幫忙投票什麼的），這裏不細說，到後麵fighting spam的地方再討論。
數據過濾：
當我們得到了每天產生的數據後，說實在這些數據實在是太多了，我們當然用不到這麼多，就要寫個過濾模塊，把一些我們用不到的數據過濾掉。
我一般是這樣做的：寫個python的腳本，把過濾器放到一個單獨的模塊，要用的過濾器就到責任鏈裏麵注冊下。這樣別人和自己維護起來也方便點，順便一說，過濾的東西一般來說有這樣幾種：一種是一個item隻有一個user打過分的，而且以前沒有人打分的，這樣的數據放到推薦的模型裏去跑雖然mahout會自動無視它，但其實按照power law來說是有不少的，內存能省就省吧；還有一種是有些黑名單的，有item和user各自的黑名單，這些也是事先要去掉的。
數據存儲：
這個就是大家仁者見仁，智者見智的時候了，因為一般來說，是你選用的算法和算法具體的實現方式以及基礎架構決定了你的存儲方式，就不多說了。
我一般是這樣做的：一般做成增量處理的方式，然後每天一計算，一周一回滾。由於算法實現的特殊性，每40個item user對存儲在一起，有點類似於bitmap吧。
推薦係統算法部分：
這部分以前寫過類似的小記錄和心得筆記之類的東西，就直接貼了_(:з」∠)_
這裏的推薦係統的核心算法主要用mahout實現。
各種算法對於推薦都有著自己的特定的假設，對於什麼時候什麼樣的算法會有比較好的performance應該對於假設反複驗證。說白了就是做實驗。
然後我們一般用什麼算法呢，看看mahout給的算法吧，花樣繁多，什麼item based，user based，slop-one，SVD等等，常用的都有了，那我們要用什麼算法呢。
先簡單說下user based的算法在mahout中的一些實現：
第一步應該先算出所有人的相似度矩陣W，再去對於item進行遍曆，事實上mahout也是這樣做的。
相似度矩陣也許可以保留下來，這樣可以用來做譜聚類來驗證。
UserSimilarity 封裝了用戶之間的相似性
UserSimilarity similarity = new PearsonCorrelationSimilarity (model);
UserNeighborhood封裝了最相似的用戶組
UserNeighborhood neighborhood = new NearestNUserNeighborhood (2, similarity, model);
總而言之，用DataModel來生成data model，用UserSimilarity生成User-user之間的相似度矩陣，用戶的鄰居的定義用UserNeighborhood定義，推薦引擎使用Recommender實現。
對於推薦的評判是使用evaluator來進行評判
double score = evaluator.evaluate(recommenderBuilder, null, model, 0.95, 0.05);
用95%的數據構建模型，用5%的數據進行test
Fixed-size neighborhoods
對於到底用多少人作為用戶周圍的一圈，我們事實上沒有一個確定的值，就像做生物實驗一樣需要不斷在特定的數據集裏跑出來。
Threshold-based neighborhood
當然，我們也可以定義個threshold去找出最相似的用戶群。
Threshold定義為-1到1（相似度矩陣返回的相似度就是在這個範圍）
new ThresholdUserNeighborhood(0.7, similarity, model)
我們對於各個算法做個簡單的比（吐）較（槽）：
（假設我們是要像亞馬遜一樣對商品做推薦，然後我們最終是要做top k的推薦）
Item based
一般來說item-based要跑得快一些，因為item比user少
Slop one
說實在話我覺得在對於一些個人品味比較看重的東西上這個算法不是很靠譜
但是它在GroupLens 10 million數據的結果是0.65
當然，對於股票係統這種還是可取的
這個算法的假設是對於不同item的preference有種線性關係
不過slope-one有個好處是它的online算的很快，並且它的性能不由用戶的數量決定
在mahout中的調用方法是new SlopeOneRecommender(model)
這個方法提供了兩種weight：weighting based on count and on standard deviation
count 是越多的user的給越多的權重，對出的是一個加權的平均數
standard deviation則是越低的deviation給予越高的權重
這兩個weight是默認采用的，當然disable它們隻會讓結果變得稍微壞一點0.67
不過這個算法有個很明顯的缺點是比較占內存
但是幸運的是我們可以把它存在數據庫裏：MySQLJDBCDataModel
Singular value decomposition–based recommenders
事實上，盡管SVD失去了一些信息，但是有時候它可以改善推薦的結果。
這個過程在有用的方式平滑了輸入
new SVDRecommender(model, new ALSWRFactorizer(model, 10, 0.05, 10))
第一個參數10是我們的目標屬性個數
第二個屬性是lambda->regularization
最後一個參數是training step跑的次數
KnnItemBasedRecommender
囧，事實上這個是用的knn的方式來做的算法，和前麵的選擇一個threshold然後圈畫用戶的算法是比較像的
但是用knn代價是非常高的，因為它要去比較所有的items的對
ItemSimilarity similarity = new LogLikelihoodSimilarity(model);
Optimizer optimizer = new NonNegativeQuadraticOptimizer();
return new KnnItemBasedRecommender(model, similarity, optimizer, 10);
結果也還不算差，是0.76
Cluster-based recommendation
基於聚類的推薦可以說是基於用戶的推薦的算法的變體中最好的一種思路
對於每一個聚類裏麵的用戶進行推薦
這個算法在推薦裏麵是非常快的，因為什麼都事先算好了。
這個算法對於冷啟動還是挺不錯的
感覺mahout裏麵用的聚類算法應該類似於Kmeans？
TreeClusteringRecommender
UserSimilarity similarity = new LogLikelihoodSimilarity(model);
ClusterSimilarity clusterSimilarity =
new FarthestNeighborClusterSimilarity(similarity);
return new TreeClusteringRecommender(model, clusterSimilarity, 10);
注意的是兩個cluster之間的相似度是用ClusterSimilarity來定義的
其中cluster之間的相似度還有NearestNeighborClusterSimilarity可選
吐槽：
對於算法的選擇，其實我們是要和我們要推薦的目標掛鉤的。為什麼最近學術界搞SVD那一係的算法這麼火，什麼LDA，plsa各種算法層出不窮，事實上因為netflix的要求是要優化RMSE，在機器學習的角度來看，類似於回歸問題，而工業界的角度來說，我們一般的需求是做top k的推薦，更加類似於分類問題。所以為什麼相比用SVD係列的算法，用item based這種更加ad hoc的算法要表現的更好一些。當然2012年的KDD cup第一名的組用的是item based+SVD的算法，這是後話。
那麼我就假設解我們這個top k的商品推薦的問題就用item based好了（速度快，結果又不算差），接下來就是確定相似度了。
相似度確定：
我們對於各個相似度做一些比（吐）較（槽）：
PearsonCorrelationSimilarity
Pearson correlation：
coeff = corr(X , Y);
function coeff = myPearson(X , Y)
% 本函數實現了皮爾遜相關係數的計算操作
%
% 輸入：
% X：輸入的數值序列
% Y：輸入的數值序列
%
% 輸出：
% coeff：兩個輸入數值序列X，Y的相關係數
%
if length(X) ~= length(Y)
error('兩個數值數列的維數不相等');
return;
end
fenzi = sum(X .* Y) - (sum(X) * sum(Y)) / length(X);
fenmu = sqrt((sum(X .^2) - sum(X)^2 / length(X)) * (sum(Y .^2) - sum(Y)^2 / length(X)));
coeff = fenzi / fenmu;
end %函數myPearson結束
當兩個變量的標準差都不為零時，相關係數才有定義，皮爾遜相關係數適用於：
(1)、兩個變量之間是線性關係，都是連續數據。
(2)、兩個變量的總體是正態分布，或接近正態的單峰分布。
(3)、兩個變量的觀測值是成對的，每對觀測值之間相互獨立。
1.沒有考慮到用戶偏好重合的items的數量
2,隻有一個item是相交錯的話是不能得到correlation的，對於比較稀疏或者小的數據集這是個要注意的問題。不過一般來說兩個用戶之間隻有一個item重疊從直覺上來說也不那麼相似
Pearson correlation一般出現在早期的推薦的論文和推薦的書裏，不過並不總是好的。
在mahout中使用了一個增加的參數Weighting.WEIGHTED，適當使用可以改善推薦結果
EuclideanDistanceSimilarity
Return 1 / (1 + d)
CosineMeasureSimilarity
當two series of input values each have a mean of 0(centered)時和PearsonCorrelation是有相同結果的
所以在mahout中我們隻要簡單的使用PearsonCorrelationSimilarity就好
Spearman correlation
這個方法用rank的方式，雖然失去了具體的打分信息，不過卻保留了item的order
Return的結果是-1和1兩個值，不過和pearson一樣，對於隻有一個item重疊的也算不出。
而且這個算法比較慢，因為它要算和存儲rank的信息。所以paper多而實際用的少，對於小數據集才值得考慮
CachingUserSimilarity
UserSimilarity similarity = new CachingUserSimilarity(
new SpearmanCorrelationSimilarity(model), model);
Ignoring preference values in similarity with the Tanimoto coefficient
TanimotoCoefficientSimilarity
如果一開始就有preference value，當數據中signal比noise多的時候可以用這個方法。
不過一般來說有preference信息的結果要好。
log-likelihood
Log-likelihood try to access how unlikely 這些重疊的部分是巧合
結果的值可以解釋為他們的重合部分並不是巧合的概念
算法的結果可能比tanimoto要好，是一個更加聰明的metric
Inferring preferences
對於數據量比較小的數據，pearson很難handle，比如一個user隻express一個preference
於是要估計相似度麼.........
AveragingPreferenceInferrer
setPreferenceInferrer().
不過這種辦法在實際中並不是有用的，隻是在很早的paper中mention到
通過現在的信息來估計並不能增加什麼東西，並且很大的降低了計算速度
最終我們要通過實驗來比較上麵的相似度，一般來說是用準確率，召回率，覆蓋率評測。
這裏有一篇Building Industrial-scale Real-world Recommender Systems
https://vdisk.weibo.com/s/rMSj-
寫netflex的，非常好，我就不獻醜多說了，所以上麵隻是吐槽下常見的算法和相似度。
其實算法按流派分是分為下麵這些類別的，大家有興趣也可以了解下，我這裏就不多做介紹：
Similarity-based methods
Dimensionality Reduction Techniques
Dimensionality-based methods
Diffusion-based methods
Social fltering
Meta approaches
我上麵所說的相似度和推薦算法，隻能算是Similarity-based methods和Dimensionality Reduction Techniques裏的非常小的一小部分，隻當拋磚引玉了。
Ps：剛在豆瓣上問了下，他們說就用前兩種，事實上我也是覺得協同過濾+SVD 偶爾做做topic model就夠了 如果沒事幹再上點social trusted的東西
增加規則：
記得hulu在做presentation的時候說過“不能做規則定製的推薦係統不是一個好的推薦係統”（好像是這樣吧......）事實上我們做出來的推薦的結果是需要做很多處理再展現給用戶的，這時候就是需要增加規則的時候了。
1.改善推薦效果：有些協同過濾的算法，做出來的結果不可避免的產生一些讓人啼笑皆非的結果，比如用戶什麼都買，導致你有可能跟姑娘們推薦的時候在佛祖下麵推薦泳裝什麼的（真實的故事）。這時候就有兩種辦法，一種就是調整模型，一種就是增加規則做一定的限製。再舉個常見的例子就是有時候會在推薦冬裝的時候出現夏裝什麼的，這時候一般我的處理方式是給這種季節性商品做一個隨時間的衰退。
2.增加廣告和導向：插入廣告，我們的最愛，這個就不多說了，靠規則。而所謂用戶喜歡的，其實不一定就是最好的，比如用戶一般來說就喜歡便宜的，還有什麼韓流爆款之流，如果你推出來的東西都是這樣的，整個係統就變成洗剪吹大集合了，非常影響定位，這時候也要上規則。
3.做一些數據挖掘和fighting spam的工作：這個在fighting spam的地方細說
可視化參數調整：
做完上麵的工作，一般來說推薦係統的基礎架構就差不多了，但是往往各個算法以及你自己上的規則都有多如牛毛的參數要調整，這時候一般要自己寫個測試腳本，將調整的結果可視化下一下，我個人推薦的是highchart，看參數以及比較各個指標非常清爽， 還可以自己做一些比如是取log之類的定製，很是方便。https://www.highcharts.com/
調整參數以及上線：
上線前有兩個事要做，一般來說就是離線測試和AB test。
離線測試就是把數據抽樣一部分，分為train data和test data，然後評估一些準確率，召回率以及coverage之類的指標，用上麵的可視化工具觀測比較下，感覺差不多了把pm叫過來讓她給小編們看看，看看審美和效果之類的。這是比較粗糙的，有的地方做的比較過細，還有用戶調研和請一些人來實際使用，這是後話。
AB test也是大家最喜歡的地方了。因為說實在，評估推薦係統學術界是看準確率那一些東西，但是工業界還是看pv uv轉化率這種實打實帶來效益的東西，而AB test就是評估這些的。我個人是比較推薦這種方法，說不上好，隻是拋磚引玉，就是按一般的做法先空跑一個星期，然後再把係統上線實際做算法pk，然後選取的實驗用戶一半的幾率進入原來的算法的推薦，一半的幾率進入你的算法的推薦，每天看看轉化率之間的比較，順便還可以調下參數做做實驗。如果算法穩定表現較好，就差不多了。
Fighting spam：
俗話說，有人的地方就有江湖，有推薦的地方就有人刷。刷子一般分三種類型的：average random和nuke。一般來說，average和random比較好對付，隻要你的係統魯棒性好點，基本影響不大。但是nuke的就非常煩，一般來說有兩種思路解決，一種是提高係統魯棒性，另外就是上規則。我們從這張圖看看兩種思路分布對應的解決效果：
其實魯棒性的係統做的就是把efficient attack的曲線降低，其實效果不算太好。
規則就是做到提前檢測，將危險扼殺在搖籃之中，就是做的藍色的那塊detectable的部分。
Fighting spam是個博大精深的問題，俗話說，與人鬥，其樂無窮，就是說的這個意思。
我們從規則說來，一般來說規則可以放到最前麵的數據收集和過濾的階段，比如在收集數據的時候看看這個人是否是多個賬號但是是一個ip，或者有些人用戶名或者注冊郵箱有群體相似性質，或者有沒有出現pv等不正常的情況。有時候我們也可以從推薦的結果裏上規則來查，比如有些人刷的過火了，導致推薦結果出現一些問題，我們就可以用迭代的方式按照先驗的刷子的比例來排出刷子排行榜之類的東西。這些都是經驗之談，上不了台麵，大家也可以自己摸索。
結束：
上麵囉嗦了半天，大體上做一個完整的簡單推薦係統就是涉及到上麵這些步驟。一些地方說的不夠詳細，有些是因為我懶，有些是不方便說。大家覺得我說的不對或者不妥的地方，可以直接在下麵跟帖噴，或者有大大指導我也是很歡迎的，大家多交流經驗。我的郵箱是flclain@gmail.com 豆瓣是https://www.douban.com/people/45119625/ 有什麼問題也可以豆瓣或者郵件交流。
其實我是覺得，要是有個大大說“你個傻缺，寫的狗屁不通，讓我來教你我是怎麼做推薦的”就更好了。
最後更新：2017-04-03 08:26:22