常用的推薦算法解析
轉(zhuǎn)載 2016年04月28日 15:40:24
標(biāo)簽：
算法 /
互聯(lián)網(wǎng) /
技術(shù)
**28858
前言隨著互聯(lián)網(wǎng)技術(shù)和社會化網(wǎng)絡(luò)的發(fā)展，每天有大量包括博客，圖片，視頻，微博等等的信息發(fā)布到網(wǎng)上。傳統(tǒng)的搜索技術(shù)已經(jīng)不能滿足用戶對信息發(fā)現(xiàn)的需求，原因有多種，可能是用戶很難用合適的關(guān)鍵詞來描述自己的需求，也可能用戶需要更加符合他們興趣和喜好的結(jié)果，又或是用戶無法對自己未知而又可能感興趣的信息做出描述。推薦引擎的出現(xiàn)，可以幫用戶獲取更豐富，更符合個人口味和更加有意義的信息。
個性化推薦根據(jù)用戶興趣和行為特點，向用戶推薦所需的信息或商品，幫助用戶在海量信息中快速發(fā)現(xiàn)真正所需的商品，提高用戶黏性，促進信息點擊和商品銷售。推薦系統(tǒng)是基于海量數(shù)據(jù)挖掘分析的商業(yè)智能平臺，推薦主要基于以下信息：
l熱點信息或商品
l用戶信息，如性別、年齡、職業(yè)、收入以及所在城市等等
l用戶歷史瀏覽或行為記錄
l社會化關(guān)系個性化推薦算法
2.1. 基于人口統(tǒng)計學(xué)的推薦基于人口統(tǒng)計學(xué)的推薦機制（Demographic-based Recommendation）是一種最易于實現(xiàn)的推薦方法，它只是簡單的根據(jù)系統(tǒng)用戶的基本信息發(fā)現(xiàn)用戶的相關(guān)程度，然后將相似用戶喜愛的其他物品推薦給當(dāng)前用戶。
首先，系統(tǒng)對每個用戶都有一個用戶 Profile 的建模，其中包括用戶的基本信息，例如用戶的年齡，性別等等；然后，系統(tǒng)會根據(jù)用戶的 Profile 計算用戶的相似度，可以看到用戶 A 的 Profile 和用戶 C 一樣，那么系統(tǒng)會認(rèn)為用戶 A 和 C 是相似用戶，在推薦引擎中，可以稱他們是“鄰居”；最后，基于“鄰居”用戶群的喜好推薦給當(dāng)前用戶一些物品。
這種基于人口統(tǒng)計學(xué)的推薦機制的好處在于：
l因為不使用當(dāng)前用戶對物品的喜好歷史數(shù)據(jù)，所以對于新用戶來講沒有“冷啟動（Cold Start）”的問題。
l這個方法不依賴于物品本身的數(shù)據(jù)，所以這個方法在不同物品的領(lǐng)域都可以使用，它是領(lǐng)域獨立的（domain-independent）。
然后，這個方法的缺點和問題就在于，這種基于用戶的基本信息對用戶進行分類的方法過于粗糙，尤其是對品味要求較高的領(lǐng)域，比如圖書，電影和音樂等領(lǐng)域，無法得到很好的推薦效果。另外一個局限是，這個方法可能涉及到一些與信息發(fā)現(xiàn)問題本身無關(guān)卻比較敏感的信息，比如用戶的年齡等，這些用戶信息不是很好獲取。
2.2. 基于內(nèi)容的推薦基于內(nèi)容的推薦是在推薦引擎出現(xiàn)之初應(yīng)用最為廣泛的推薦機制，它的核心思想是根據(jù)推薦物品或內(nèi)容的元數(shù)據(jù)，發(fā)現(xiàn)物品或者內(nèi)容的相關(guān)性，然后基于用戶以往的喜好記錄，推薦給用戶相似的物品。這種推薦系統(tǒng)多用于一些資訊類的應(yīng)用上，針對文章本身抽取一些tag作為該文章的關(guān)鍵詞，繼而可以通過這些tag來評價兩篇文章的相似度。
這種推薦系統(tǒng)的優(yōu)點在于：
l易于實現(xiàn)，不需要用戶數(shù)據(jù)因此不存在稀疏性和冷啟動問題。
l基于物品本身特征推薦，因此不存在過度推薦熱門的問題。
然而，缺點在于抽取的特征既要保證準(zhǔn)確性又要具有一定的實際意義，否則很難保證推薦結(jié)果的相關(guān)性。豆瓣網(wǎng)采用人工維護tag的策略，依靠用戶去維護內(nèi)容的tag的準(zhǔn)確性。
2.3. 基于關(guān)聯(lián)規(guī)則的推薦基于關(guān)聯(lián)規(guī)則的推薦更常見于電子商務(wù)系統(tǒng)中，并且也被證明行之有效。其實際的意義為購買了一些物品的用戶更傾向于購買另一些物品?；陉P(guān)聯(lián)規(guī)則的推薦系統(tǒng)的首要目標(biāo)是挖掘出關(guān)聯(lián)規(guī)則，也就是那些同時被很多用戶購買的物品集合，這些集合內(nèi)的物品可以相互進行推薦。目前關(guān)聯(lián)規(guī)則挖掘算法主要從Apriori和FP-Growth兩個算法發(fā)展演變而來。
基于關(guān)聯(lián)規(guī)則的推薦系統(tǒng)一般轉(zhuǎn)化率較高，因為當(dāng)用戶已經(jīng)購買了頻繁集合中的若干項目后，購買該頻繁集合中其他項目的可能性更高。該機制的缺點在于：
l計算量較大，但是可以離線計算，因此影響不大。
l由于采用用戶數(shù)據(jù)，不可避免的存在冷啟動和稀疏性問題。
l存在熱門項目容易被過度推薦的問題。
2.4. 基于協(xié)同過濾的推薦協(xié)同過濾是一種在推薦系統(tǒng)中廣泛采用的推薦方法。這種算法基于一個“物以類聚，人以群分”的假設(shè)，喜歡相同物品的用戶更有可能具有相同的興趣?；趨f(xié)同過濾的推薦系統(tǒng)一般應(yīng)用于有用戶評分的系統(tǒng)之中，通過分?jǐn)?shù)去刻畫用戶對于物品的喜好。協(xié)同過濾被視為利用集體智慧的典范，不需要對項目進行特殊處理，而是通過用戶建立物品與物品之間的聯(lián)系。
目前，協(xié)同過濾推薦系統(tǒng)被分化為兩種類型：基于用戶(User-based)的推薦和基于物品(Item-based)的推薦。
2.4.1. 基于用戶的推薦基于用戶的協(xié)同過濾推薦的基本原理是，根據(jù)所有用戶對物品或者信息的偏好（評分），發(fā)現(xiàn)與當(dāng)前用戶口味和偏好相似的“鄰居”用戶群，在一般的應(yīng)用中是采用計算“K-Nearest Neighboor”的算法；然后，基于這 K 個鄰居的歷史偏好信息，為當(dāng)前用戶進行推薦。
這種推薦系統(tǒng)的優(yōu)點在于推薦物品之間在內(nèi)容上可能完全不相關(guān)，因此可以發(fā)現(xiàn)用戶的潛在興趣，并且針對每個用戶生成其個性化的推薦結(jié)果。缺點在于一般的Web系統(tǒng)中，用戶的增長速度都遠遠大于物品的增長速度，因此其計算量的增長巨大，系統(tǒng)性能容易成為瓶頸。因此在業(yè)界中單純的使用基于用戶的協(xié)同過濾系統(tǒng)較少。
2.4.2. 基于物品的推薦基于物品的協(xié)同過濾和基于用戶的協(xié)同過濾相似，它使用所有用戶對物品或者信息的偏好（評分），發(fā)現(xiàn)物品和物品之間的相似度，然后根據(jù)用戶的歷史偏好信息，將類似的物品推薦給用戶?；谖锲返膮f(xié)同過濾可以看作是關(guān)聯(lián)規(guī)則推薦的一種退化，但由于協(xié)同過濾更多考慮了用戶的實際評分，并且只是計算相似度而非尋找頻繁集，因此可以認(rèn)為基于物品的協(xié)同過濾準(zhǔn)確率較高并且覆蓋率更高。
同基于用戶的推薦相比，基于物品的推薦應(yīng)用更為廣泛，擴展性和算法性能更好。由于項目的增長速度一般較為平緩，因此性能變化不大。缺點就是無法提供個性化的推薦結(jié)果。
兩種協(xié)同過濾，在基于用戶和基于物品兩個策略中應(yīng)該如何選擇呢？其實基于物品的協(xié)同過濾推薦機制是 Amazon 在基于用戶的機制上改良的一種策略，因為在大部分的 Web 站點中，物品的個數(shù)是遠遠小于用戶的數(shù)量的，而且物品的個數(shù)和相似度相對比較穩(wěn)定；同時基于物品的機制比基于用戶的實時性更好。但也不是所有的場景都是這樣的情況，在一些新聞推薦系統(tǒng)中，也許物品，也就是新聞的個數(shù)可能大于用戶的個數(shù)，而且新聞的更新程度也有很快，所以它的相似度依然不穩(wěn)定。所以，推薦策略的選擇其實也和具體的應(yīng)用場景有很大的關(guān)系。
基于協(xié)同過濾的推薦機制是現(xiàn)今應(yīng)用最為廣泛的推薦機制，它有以下幾個顯著的優(yōu)點：
l它不需要對物品或者用戶進行嚴(yán)格的建模，而且不要求物品的描述是機器可理解的，所以這種方法也是領(lǐng)域無關(guān)的。
l這種方法計算出來的推薦是開放的，可以共用他人的經(jīng)驗，很好的支持用戶發(fā)現(xiàn)潛在的興趣偏好。
然后而它也存在以下幾個問題：
l方法的核心是基于歷史數(shù)據(jù)，所以對新物品和新用戶都有“冷啟動”的問題。
l推薦的效果依賴于用戶歷史偏好數(shù)據(jù)的多少和準(zhǔn)確性。
l在大部分的實現(xiàn)中，用戶歷史偏好是用稀疏矩陣進行存儲的，而稀疏矩陣上的計算有些明顯的問題，包括可能少部分人的錯誤偏好會對推薦的準(zhǔn)確度有很大的影響等等。
l對于一些特殊品味的用戶不能給予很好的推薦。
l由于以歷史數(shù)據(jù)為基礎(chǔ)，抓取和建模用戶的偏好后，很難修改或者根據(jù)用戶的使用演變，從而導(dǎo)致這個方法不夠靈活。
3.推薦系統(tǒng)與廣告投放互聯(lián)網(wǎng)上的主題廣告推廣（例如，百度推廣，google adsense）的目標(biāo)在于實現(xiàn)一個面向用戶的個性化廣告投放系統(tǒng)。通過把個性化推薦算法在廣告投放中的應(yīng)用，就實現(xiàn)了我們個性化廣告投放的目標(biāo)。那么，這種演變是如何實現(xiàn)的呢？
在互聯(lián)網(wǎng)中，例如，百度，擁有大量的網(wǎng)頁信息，而主題廣告推廣的對象不是用戶而是某一類型的頁面。通過類比，每種網(wǎng)頁類型對應(yīng)于推薦系統(tǒng)中的一個用戶，而每一個廣告就對應(yīng)于推薦系統(tǒng)中的一個物品，網(wǎng)頁類型（用戶）對廣告（物品）的評分則可以用該網(wǎng)頁類型中投放廣告時的點擊情況來計算，這樣就構(gòu)成了一個user-item-rating的矩陣。也就是，通過協(xié)同過濾算法可以實現(xiàn)對不同類型的網(wǎng)頁進行廣告推薦。
此外，實際應(yīng)用協(xié)同過濾算法來進行廣告投放也存在一個些問題。例如，協(xié)同過濾中的“冷啟動”問題，也就是新增廣告條目的推薦需要額外考慮；同時，也需要考慮用戶對廣告的接受程度，廣告庫存率等問題。
- 業(yè)界個性化推薦系統(tǒng)
4.1. Yahoo！Resarch - Web-ScaleRecommendation Systems2011推薦系統(tǒng)論壇中，來自Yahoo！的Yehuda Koren分享了他對于互聯(lián)網(wǎng)中推薦系統(tǒng)的經(jīng)驗。在》中，簡單介紹了目前廣泛流行的協(xié)同過濾推薦機制；另外分析了一些推薦系統(tǒng)中值得注意的一些問題：
lBias Matters
在實際的應(yīng)用中，用戶并不是隨機地選擇物品去打分，而是只選擇那些和他們興趣相關(guān)的物品打分，絕大多數(shù)用戶往往忽略了去給那些沒有興趣的物品打分。Koren通過分析Netflix Prize數(shù)據(jù)，Koren發(fā)現(xiàn)用戶對視頻的評分變化中，Bias可以解釋其中的33%，而個性化只能解釋其中的10%，剩下的57%暫時還得不到解釋。
lEliciting user feedback
Koren的目標(biāo)是解決推薦系統(tǒng)的cold-start問題，例如，Yahoo！ Movie中，對于新用戶，很難預(yù)測他們的喜好（對視頻的評分）。那么，可以選一些視頻讓新用戶打分，從而獲取他們的興趣數(shù)據(jù)。在此過程中，使用了決策樹模型來引導(dǎo)用戶評分，可以用盡量少的視頻，最大程度地了解用戶興趣。
lEstimating confidence in recommendations
在推薦系統(tǒng)中，我們需要對被推薦物品的可信度進行估計，從而得出更為可信的物品來進行推薦。Koren在這里提出了基于概率的可信度計算方法，也就是根據(jù)對評分（用戶對物品）的概率預(yù)測，然后利用熵，標(biāo)準(zhǔn)方差，或是Gini不純度等概率分布來對物品可信度進行評估。
4.2. 淘寶推薦系統(tǒng)淘寶推薦系統(tǒng)的目標(biāo)就是要為各個產(chǎn)品提供商品，店鋪，人，類目屬性各種維度的推薦。它的核心就是以類目屬性和社會屬性為紐帶，將人，商品和店鋪建立起聯(lián)系。
淘寶的寶貝推薦原則：
l基于內(nèi)容的和關(guān)聯(lián)規(guī)則
l全網(wǎng)優(yōu)質(zhì)寶貝算分
l根據(jù)推薦屬性篩選TOP
l基于推薦屬性的關(guān)聯(lián)關(guān)系
l采用搜索引擎存儲和檢索優(yōu)質(zhì)寶貝
l加入個性化用戶信息
根據(jù)用戶的購買和收藏記錄產(chǎn)生可推薦的關(guān)聯(lián)規(guī)則。對優(yōu)質(zhì)寶貝的算分需要考慮商品的相關(guān)屬性，包括描述，評價，名稱，違規(guī)，收藏人氣，累計銷量，UV，以及PV等等。此外，推薦系統(tǒng)根據(jù)用戶的瀏覽，收藏，購買行為以及反饋信息，在Hadoop上來計算用戶帶權(quán)重的標(biāo)簽，用于進行個性化推薦。
那么，淘寶是如何利用個性化推薦的結(jié)果呢？下圖展示了淘寶基于個性化推薦的5W營銷系統(tǒng)：
在個性化推薦之上，淘寶還實現(xiàn)了基于內(nèi)容的廣告投放。由于個性化推薦出來的物品是用戶所感興趣的，可以想象，基于此之上的廣告投放也應(yīng)該會行之有效。
眾所周知，淘寶具有海量的數(shù)據(jù)和商品問題，這里列舉了淘寶數(shù)據(jù)的一些參數(shù)：超過8億種在線商品，100萬產(chǎn)品，4萬屬性，等等。在淘寶實現(xiàn)推薦系統(tǒng)可能遇到的各種各樣的難題，其中有：
l商品種類繁多，生命周期短，很難及時收集到足夠多的點擊或購買數(shù)據(jù)，這使得基于用戶行為的推薦方法，比如基于物品的推薦方法，發(fā)揮空間有限。
l因為商品是由賣家而非網(wǎng)站登記的，數(shù)據(jù)的規(guī)范性差，這又給基于內(nèi)容的推薦帶來了很大的困難。
l8億種商品中，重復(fù)的商品種類應(yīng)該非常多，需要盡量避免推薦重復(fù)種類的商品給用戶，但在數(shù)據(jù)規(guī)范性差、區(qū)分度差的情況下，如何歸并重復(fù)商品種類，這本身也是個很大的難題。
l大多數(shù)推薦系統(tǒng)只需要考慮如何滿足買家的需求，在淘寶，還要考慮賣家的需求。
4.3. 豆瓣的推薦引擎 - 豆瓣猜
豆瓣網(wǎng)在國內(nèi)互聯(lián)網(wǎng)行業(yè)美譽度很高，這是一家以幫助用戶發(fā)現(xiàn)未知事物為己任的公司。它的“豆瓣猜”是一種個性化的推薦，其背后采用了基于用戶的協(xié)同過濾技術(shù)。那么，豆瓣猜是如何向我們推薦產(chǎn)品的呢？
首先，確定什么樣的產(chǎn)品適合推薦？豆瓣猜提出選擇”具有媒體性的產(chǎn)品 (Media Product)“來進行推薦，即選擇多樣、口味很重要、單位成本不重要，同時能夠廣泛傳播 (InformationCascade)的產(chǎn)品；接著在對真實的數(shù)據(jù)集進行定量分析后，進一步得出，應(yīng)該是條目增長相對穩(wěn)定、能夠快速獲得用戶反饋，數(shù)據(jù)稀疏性與條目多樣性、時效性比較平衡的產(chǎn)品，才是適合推薦的產(chǎn)品。
其次，豆瓣網(wǎng)的推薦引擎面對高成長性的挑戰(zhàn)，通過降低存儲空間，近似算法與分布式計算的設(shè)計，來實現(xiàn)對基于用戶的協(xié)同過濾推薦系統(tǒng)的線性擴展。
最后，針對當(dāng)前推薦系統(tǒng)面臨的問題，包括傾向于給出平庸的推薦，有信息無結(jié)構(gòu)，以及缺乏對用戶的持續(xù)關(guān)注等黑盒推薦問題。豆瓣提出了分為 Prediction，F(xiàn)orecasting，Recommendation 三個階段的下一代推薦系統(tǒng)，并探討了一種下一代推薦引擎的構(gòu)想——基于用戶行為模型的、有記憶的、可進化的系統(tǒng)。
4.4. Hulu的個性化推薦Hulu是一家美國的視頻網(wǎng)站，它是由美國國家廣播環(huán)球公司（NBC Universal）和?？怂箯V播公司（Fox）在2007年3月共同投資建立的。在美國，Hulu已是最受歡迎的視頻網(wǎng)站之一。它擁有超過250個渠道合作伙伴，超過600個頂級廣告客戶，3千萬的用戶，3億的視頻，以及11億的視頻廣告。廣告是衡量視頻網(wǎng)站成功與否的一個重要標(biāo)準(zhǔn)。事實證明，Hulu的廣告效果非常好，若以每千人為單位對廣告計費，Hulu的所得比電視臺在黃金時段所得還高。那么，是什么讓Hulu取得了這樣的成功呢？
通過對視頻和用戶特點的分析，Hulu根據(jù)用戶的個人信息，行為模型和反饋，設(shè)計出一個混合的個性化推薦系統(tǒng)。它包含了基于物品的協(xié)同過濾機制，基于內(nèi)容的推薦，基于人口統(tǒng)計的推薦，從用戶行為中提煉出來的主題模型，以及根據(jù)用戶反饋信息對推薦系統(tǒng)的優(yōu)化，等等。此個性化推薦系統(tǒng)也進而成為了一個產(chǎn)品，用于給用戶推薦視頻。這個產(chǎn)品通過問答的形式，與用戶進行交互，獲取用戶的個人喜歡，進一步提高推薦的個性化。
Hulu把這種個性化推薦視頻的思想放到了廣告投放中，設(shè)計出了一套個性化廣告推薦系統(tǒng)。那么，這種廣告系統(tǒng)是如何實現(xiàn)個性化的呢？
lHulu的用戶對廣告擁有一定控制權(quán)，在某些視頻中你可以根據(jù)自己的喜好選擇相應(yīng)的廣告，或者選擇在開頭看一段電影預(yù)告片來抵消廣告。
lHulu收集用戶對廣告的反饋意見（評分），例如，某個廣告是否對收看用戶有用？
l根據(jù)人口統(tǒng)計的信息，來投放廣告。例如，分析Hulu用戶的年齡，性別特征來同方不同的視頻及廣告。
l根據(jù)用戶的行為模式，進一步增加廣告投放的準(zhǔn)確性。
