推薦系統介紹
自從1992年施樂的科學家為了解決信息負載的問題，第一次提出協同過濾算法，個性化推薦已經經過了二十幾年的發展。1998年，林登和他的同事申請了“item-to-item”協同過濾技術的專利，經過多年的實踐，亞馬遜宣稱銷售的推薦占比可以占到整個銷售GMV（Gross Merchandise Volume，即年度成交總額）的30%以上。隨后Netflix舉辦的推薦算法優化競賽，吸引了數萬個團隊參與角逐，期間有上百種的算法進行融合嘗試，加快了推薦系統的發展，其中SVD（Sigular Value Decomposition，即奇異值分解，一種正交矩陣分解法）和Gavin Potter跨界的引入心理學的方法進行建模，在諸多算法中脫穎而出。其中，矩陣分解的核心是將一個非常稀疏的用戶評分矩陣R分解為兩個矩陣：User特性的矩陣P和Item特性的矩陣Q，用P和Q相乘的結果R'來擬合原來的評分矩陣R，使得矩陣R'在R的非零元素那些位置上的值盡量接近R中的元素，通過定義R和R'之間的距離，把矩陣分解轉化成梯度下降等求解的局部最優解問題。Netflix最新的實時推薦系統如圖9-5所示。
圖9-5 NetFlix的實時推薦系統系統架構圖（來源：http://techblog.netflix.com/2013/03/system-architectures-for.html）
與此同時，Pandora、LinkedIn、Hulu、Last.fm等一些網站在個性化推薦領域都展開了不同程度的嘗試，使得推薦系統在垂直領域有了不少突破性進展，但是在全品類的電商、綜合的廣告營銷上，進展還是緩慢，仍然有很多的工作需要探索。特別是在全品類的電商中，單個模型在母嬰品類的效果還比較好，但在其他品類就可能很差，很多時候需要根據品類、推薦欄位、場景等不同，設計不同的模型。同時由于用戶、SKU不停地增加，需要定期對數據進行重新分析，對模型進行更新，但是定期對模型進行更新，無法保證推薦的實時性，一段時間后，由于模型訓練也要相當時間，可能傳統的批處理的Hadoop的方法，無法再縮短更新頻率，最終推薦效果會因為實時性問題達到一個瓶頸。
推薦算法主要有基于人口統計學的推薦、基于內容的推薦、基于協同過濾的推薦等，而協同過濾算法又有基于鄰域的方法（又稱基于記憶的方法）、隱語義模型、基于圖的隨機游走算法等。基于內容的推薦解決了商品的冷啟動問題，但是解決不了用戶的冷啟動問題，并且存在過擬合問題（往往在訓練集上有比較好的表現，但在實際預測中效果大打折扣），對領域知識要求也比較高，通用性和移植性比較差，換一個產品形態，往往需要重新構建一套，對于多媒體文件信息特征提取難度又比較大，往往只能通過人工標準信息。基于鄰域的協同過濾算法，雖然也有冷啟動問題和數據稀疏性等問題，但是沒有領域知識要求，算法通用性好，增加推薦的新穎性，并且對行為豐富的商品，推薦準確度較高。基于模型的協同過濾算法在一定程度上解決了基于鄰域的推薦算法面臨的一些問題，在RMSE（Root Mean Squared Error，即均方根誤差）等推薦評價指標上更優，但是通常算法復雜，計算開銷大，所以目前基于鄰域的協同過濾算法仍然是最為流行的推薦算法。
基于鄰域的協同過濾主要分為User CF和Item CF，根據以下條件不同，各自又有不同的使用場景。
計算量大小不同。基于鄰域的協同過濾的時間復雜度為
, 其中n為用戶數，m為產品數，應用SVD等降維方法可以降低算法復雜度，但是分解矩陣又會花費一定的時間。
數據稀疏性傾斜度不同。例如，User CF主要基于用戶對共同項目的評分，如果用戶遠遠多于物品，沒有足夠評分將導致兩個用戶很少有共同評分的項目，找最近鄰用戶非常的不準確，雖然通過基于BP神經網絡、樸素貝葉斯分類、基于內容的預測等方法可以填充矩陣，但是都會不同程度地帶來的計算時間。
對于用戶數量遠遠大于產品，并且產品相對穩定的電商系統，計算產品相似度計算量小，適用Item CF，否則用戶量大，并且如果用戶購買頻繁，計算用戶相似度計算量很大，極端情況下，100個用戶對應2個產品，一個要計算C1002次相似度，一個只要計算C22，即一次相似度；反之，對于更新頻繁，物品數量海量的新聞、博客、微博等系統，User CF效果更好。
當然，雖然SVD在分解矩陣上花費了一定時間，同時降維也會導致用戶-項目矩陣中的信息丟失，但是用戶-項目矩陣降維后, 運算復雜度大大降低，同時矩陣稀疏性問題得到了較好地解決，作為Netflix比賽中最終提升效果較好的兩個方法之一，被眾多網站采用。用戶-項目矩陣中的信息丟失問題可以通過選取合適的保留維數k在一定程度上得到緩解。
在一個電商系統中，有商品、類目、品牌、團購、閃購、搜索、店鋪、廣告、促銷活動、抵用券等諸多實體；有首頁的大輪播、猜你喜歡欄位，詳情頁的看了還看、看了還買、推薦品牌等欄位，購物車頁面的買了還買、湊單免郵等欄位。如何在不同的欄位融入不同的推薦算法給用戶推薦相應的實體，構建出屬于電商自己的場景引擎，實現全站精準化，讓網站的GMV或者利潤達到最高，是每一個電商需要思考的問題。在實際中，很多推薦算法不一定要求實時，實時推薦在哪些場景下能帶給欄位更高的GMV轉化率，也是需要一定時間摸索和試錯的。
目前基于用戶畫像的推薦，主要用在基于內容的推薦，從最近的RecSys大會（ACM Recommender Systems）上來看，不少公司和研究者也在嘗試基于用戶畫像做Context-Aware的推薦（情境感知，又稱上下文感知）。利用用戶的畫像，結合時間、天氣等上下文信息，給用戶做一些更加精準化的推薦是一個不錯的方向。
實時推薦系統的方法
目前的商用推薦系統，當用戶數和商品數達到一定數目時，推薦算法都面臨嚴重的可擴展性問題，推薦的實效性變得非常差，如何在算法和架構上提高推薦速度是很多公司不得不思考的問題。目前，在算法上主要通過引入聚類技術和改進實時協同過濾算法提高推薦速度；在架構上，目前實時推薦主要有基于Spark、Kiji框架和Storm的流式計算3種方法。
1．聚類技術和實時協同過濾算法
在算法上，一般采用EM（Expectation-Maximization）、K-means、吉布斯（Gibbs Sampling）、模糊聚類等聚類技術提高推薦速度。因為使用聚類技術可以大大縮小用戶或項目的最近鄰居搜索范圍，從而提高推薦的實時性，如表9-1所示。
除此之外，實時協同過濾算法本身一直是人們研究的熱點，早在2003年，Edward F. Harrington就第一次提出了基于感知器的實時協同過濾算法，但是這種方法需要所有用戶的偏好，實用性較差；2010年，楊強等提出了實時進化的協同過濾算法，給予新得分更高的權重來增量更新User和Item的相似度；2011年，UC Berkeley的Jacob Abernethy等人提出了OCF-SGD算法，我們知道傳統的矩陣分解把用戶評分矩陣R分解成多個矩陣，比如R≈P*Q，該方法提出當新來一個User到Item的得分，把更新R矩陣的問題轉換成更新P和Q矩陣，從而達到實時協同過濾；近幾年的RecSys大會上，實時協同過濾也是討論的熱點，OCF-SGD算法每次只考慮一個用戶，忽略了用戶之間的關系，Jialei Wang等人提出了基于多任務學習的實時協同過濾算法，把每一個用戶當做一個任務，定義一個表示各個任務間相似性和交互程度的矩陣A，當新來一個User到Item的得分，通過矩陣A來更新其他用戶的得分。
2．基于Spark的方式
在架構上，第一種是使用Spark把模型計算放在內存中，加快模型計算速度，Hadoop中作業的中間輸出結果是放到硬盤的HDFS中，而Spark是直接保存在內存中，因此Spark能更好地適用于數據挖掘與機器學習等需要迭代的模型計算，如表9-2所示。
（來源：http://www.csdn.net/article/2014-05-19/2819831-TDW-Shuffle/2）
3．基于Kiji框架的方式
第二種是使用Kiji，它是一個用來構建大數據應用和實時推薦系統的開源框架，本質上是對HBase上層的一個封裝，用Avro來承載對象化的數據，使得用戶能更容易地用HBase管理結構化的數據，使得用戶姓名、地址等基礎信息和點擊、購買等動態信息都能存儲到一行，在傳統數據庫中，往往需要建立多張表，在計算的時候要關聯多張表，影響實時性。Kiji與HBase的映射關系如表9-3所示。
Kiji提供了一個KijiScoring模塊，它可以定義數據的過期策略，如綜合產品點擊次數和上次的點擊時間，設置數據的過期策略把數據刷新到KijiScoring服務器中，并且根據自己定義的規則，決定是否需要重新計算得分。如用戶有上千萬瀏覽記錄，一次的行為不會影響多少總體得分，不需要重新計算，但如果用戶僅有幾次瀏覽記錄，一次的行為，可能就要重新訓練模型。Kiji也提供了一個Kiji模型庫，使得改進的模型部署到生產環境時不用停掉應用程序，讓開發者可以輕松更新其底層的模型。
4．基于Storm的方式
最后一種基于 Storm 的實時推薦系統。在實時推薦上，算法本身不能設計的太復雜，并且很多網站的數據庫是TB、PB級別，實時讀寫大表比較耗時。可以把算法分成離線部分和實時部分，利用Hadoop離線任務盡量把查詢數據庫比較多的、可以預先計算的模型先訓練好，或者把計算的中間數據先計算好，比如，線性分類器的參數、聚類算法的群集位置或者協同過濾中條目的相似性矩陣，然后把少量更新的計算留給Storm實時計算，一般是具體的評分階段。
基于Storm的實時推薦系統
基于本章前面的學習，我們可以設計圖9-6所示的實時推薦系統。
圖9-6 實時推薦系統（圖片來源PRANAB GHOSH，Big Data Cloud meetup。版權歸原書作者所有）
用HBase或HDFS存儲歷史的瀏覽、購買行為信息，用Hadoop基于User CF的協同過濾，先把用戶的相似度離線生成好，用戶到商品的矩陣往往比較大，運算比較耗時，把耗時的運行先離線計算好，實時調用離線的結果進行輕量級的計算有助于提高產品的實時性。
我們來簡單回顧一下協同過濾算法（如圖9-7所示）：首先程序獲取用戶和產品的歷史偏好，得到用戶到產品的偏好矩陣，利用Jaccard相似系數（Jaccard coefficient）、向量空間余弦相似度（Cosine similarity）、皮爾遜相關系數（Pearson correlation coefficient）等相似度計算方法，得到相鄰的用戶（User CF）或相似商品（Item CF）。在User CF中，基于用戶歷史偏好的相似度得到鄰居用戶，將鄰居用戶偏好的產品推薦給該用戶；在Item CF中，基于用戶對物品的偏好向量得到相似產品，然后把這款產品推薦給喜歡相似產品的其他用戶。
圖9-7 協同過濾算法過程
然后通過Kafka或者redis隊列，保存前端的最新瀏覽等事件流，在Storm的Topology中實時讀取里面的信息，同時獲取緩存中用戶topN個鄰居用戶，把鄰居用戶喜歡的商品存到緩存中，前端從緩存中取出商品，根據一定的策略，組裝成推薦商品列表。
當然除了相似性矩陣，其他模型大體實現也相似，比如實際的全品類電商中不同的品類和欄位，往往要求不同的推薦算法，如母嬰產品，如圖9-8所示，如果結合商品之間的序列模式和母嬰年齡段的序列模式，效果會比較好，可以把模型通過Hadoop預先生成好，然后通過Storm實時計算來預測用戶會買哪些產品。
圖9-8 序列模式在母嬰類目推薦中的應用
本文摘自《Storm技術內幕與大數據實踐》
本書先介紹實時大數據平臺架構上的一些知識和難點，然后引入Storm來解決其中的問題。開始介紹Storm開發，再分享Storm集群中性能調優、資源隔離的一些知識和經驗，然后加入Storm監控和日志的內容。后面介紹如何通過Storm構建公司的基礎數據層；如何通過良好的架構設計實時更新基礎數據層的用戶畫像、分布式索引等，最后依托實時更新的基礎數據層，介紹如何構建各類個性化應用。
