推薦算法綜述_1

1、推薦算法綜述推薦算法綜述蘇芳芳 2014-10-14電子商務(wù)推薦電子商務(wù)推薦l將電子商務(wù)系統(tǒng)的瀏覽者轉(zhuǎn)變?yōu)橘?gòu)買者：瀏覽者經(jīng)常沒(méi)有購(gòu)買欲望，電子商務(wù)推薦他們感興趣的商品，從而完成購(gòu)買過(guò)程。l提高電子商務(wù)系統(tǒng)的交叉銷售：推薦用戶確實(shí)需要但是在購(gòu)買過(guò)程中沒(méi)有想到的商品列表。l保留用戶：提高推薦質(zhì)量，讓用戶對(duì)該系統(tǒng)產(chǎn)生依賴。研究?jī)?nèi)容和方向研究?jī)?nèi)容和方向l推薦技術(shù)研究l實(shí)時(shí)性研究l推薦質(zhì)量研究l多種數(shù)據(jù)多種技術(shù)的集成l數(shù)據(jù)挖掘技術(shù)的應(yīng)用（關(guān)聯(lián)規(guī)則挖掘、序列模式挖掘、聚類 分析、貝葉斯分類）l用戶隱私保護(hù)研究l推薦系統(tǒng)可視化研究（可視化研究和推薦結(jié)果解釋研究）推薦算法主要算法推薦算法主要算法l協(xié)同過(guò)濾推薦

2、算法l基于內(nèi)容的推薦算法l基于圖結(jié)構(gòu)推薦l基于關(guān)聯(lián)規(guī)則推薦l基于知識(shí)推薦l混合推薦協(xié)同過(guò)濾推薦協(xié)同過(guò)濾推薦l協(xié)同過(guò)濾推薦算法有： 基于用戶的協(xié)同過(guò)濾推薦算法 基于項(xiàng)目的協(xié)同過(guò)濾推薦算法 基于降維的協(xié)同過(guò)濾推薦算法 基于聚類的協(xié)同過(guò)濾推薦算法基于用戶的協(xié)同過(guò)濾推薦基于用戶的協(xié)同過(guò)濾推薦l基于用戶協(xié)同過(guò)濾推薦根據(jù)其他用戶的觀點(diǎn)產(chǎn)生對(duì)目標(biāo)用戶的推薦列表基于用戶的協(xié)同過(guò)濾推薦基于用戶的協(xié)同過(guò)濾推薦l算法步驟：1、數(shù)據(jù)表示：對(duì)用戶已經(jīng)購(gòu)買過(guò)的商品進(jìn)行建模2、最近鄰查詢：計(jì)算相似度，搜索當(dāng)前用戶的最近鄰居3、推薦產(chǎn)生：根據(jù)最近鄰對(duì)商品的評(píng)分預(yù)測(cè)當(dāng)前用戶對(duì)商品的評(píng)分，產(chǎn)生top-N商品基于用戶的協(xié)同過(guò)濾推薦

3、基于用戶的協(xié)同過(guò)濾推薦1、數(shù)據(jù)表示基于用戶的協(xié)同過(guò)濾推薦基于用戶的協(xié)同過(guò)濾推薦2、最近鄰查詢計(jì)算當(dāng)前用戶和其他用戶的相似度，選擇相似度高的若干用戶作為最近鄰。相似度計(jì)算： 余弦相似性 修正的余弦相似性 相關(guān)相似性（pearson correlation） 基于圖結(jié)構(gòu)的相似度基于用戶的協(xié)同過(guò)濾推薦基于用戶的協(xié)同過(guò)濾推薦l相似度計(jì)算方法余弦相似性：修正的余弦相似性：相關(guān)相似性：基于用戶的協(xié)同過(guò)濾推薦基于用戶的協(xié)同過(guò)濾推薦3、推薦產(chǎn)生計(jì)算用戶u對(duì)項(xiàng)i的預(yù)測(cè)評(píng)分Pu,i : 選擇評(píng)分高的的若干項(xiàng)目推薦給用戶u。基于項(xiàng)目的協(xié)同過(guò)濾推薦基于項(xiàng)目的協(xié)同過(guò)濾推薦l基于項(xiàng)目協(xié)同過(guò)濾推薦根據(jù)用戶對(duì)相似項(xiàng)最近鄰居的

4、評(píng)分產(chǎn)生對(duì)目標(biāo)用戶的推薦列表基于項(xiàng)目的協(xié)同過(guò)濾推薦基于項(xiàng)目的協(xié)同過(guò)濾推薦l算法步驟：1、最近鄰查詢：搜索目標(biāo)項(xiàng)的最近鄰居2、推薦產(chǎn)生：根據(jù)用戶對(duì)目標(biāo)項(xiàng)最近鄰居的評(píng)分預(yù)測(cè)用戶對(duì)目標(biāo)項(xiàng)的評(píng)分，產(chǎn)生top-N商品基于聚類的協(xié)同過(guò)濾推薦基于聚類的協(xié)同過(guò)濾推薦l將整個(gè)用戶空間根據(jù)用戶的購(gòu)買習(xí)慣和評(píng)分特點(diǎn)劃分為若干個(gè)不同的聚類；l根據(jù)每個(gè)聚類中用戶對(duì)商品的評(píng)分信息生成一個(gè)虛擬用戶，將所有虛擬用戶對(duì)商品的評(píng)分作為新的搜索空間；l查詢當(dāng)前用戶在虛擬用戶空間中的最近鄰居，產(chǎn)生對(duì)應(yīng)的推薦結(jié)果。l查詢效率高、實(shí)時(shí)響應(yīng)快基于聚類的協(xié)同過(guò)濾推薦基于聚類的協(xié)同過(guò)濾推薦- -劃分聚類劃分聚類lK-means聚類算法：1).

5、隨機(jī)選擇k個(gè)用戶作為種子節(jié)點(diǎn),將k個(gè)用戶對(duì)項(xiàng)的評(píng)分?jǐn)?shù)據(jù)作為初始的聚類中心。2)對(duì)剩余的用戶集合,計(jì)算每條用戶與k個(gè)聚類中心的相似性,將每個(gè)用戶分配到相似性最高的聚類中。3)對(duì)新生成的聚類,計(jì)算聚類中所有用戶對(duì)項(xiàng)的平均評(píng)分,生成新的聚類中心。4)重復(fù)以上2到3步,直到聚類不再發(fā)生改變?yōu)橹埂；诰垲惖膮f(xié)同過(guò)濾推薦基于聚類的協(xié)同過(guò)濾推薦l虛擬用戶集生成根據(jù)不同的聚類生成對(duì)應(yīng)的聚類中心,聚類中心與聚類中其他用戶的距離之和最小,代表該聚類中用戶對(duì)商品的典型評(píng)分。將所有的聚類中心作為虛擬的用戶集合?；诰垲惖膮f(xié)同過(guò)濾推薦基于聚類的協(xié)同過(guò)濾推薦l推薦產(chǎn)生在虛擬的用戶集合上使用各種相似性度量方法搜索當(dāng)前用戶的

6、若干最近鄰居,然后根據(jù)最近鄰居對(duì)商品的評(píng)分信息產(chǎn)生對(duì)應(yīng)的推薦結(jié)果。最近鄰搜索和推薦產(chǎn)生的方法跟協(xié)同過(guò)濾推薦算法類似,在此不再贅述。協(xié)同過(guò)濾優(yōu)缺點(diǎn)及改進(jìn)協(xié)同過(guò)濾優(yōu)缺點(diǎn)及改進(jìn)l協(xié)同過(guò)濾優(yōu)點(diǎn)：交叉推薦l協(xié)同過(guò)濾缺點(diǎn)：冷啟動(dòng)基于內(nèi)容的過(guò)濾基于內(nèi)容的過(guò)濾l協(xié)同過(guò)濾方法只考慮了用戶評(píng)分?jǐn)?shù)據(jù),忽略了項(xiàng)目和用戶本身的諸多特征,如電影的導(dǎo)演、演員和發(fā)布時(shí)間等,用戶的地理位置、性別、年齡等.如何充分、合理的利用這些特征,獲得更好的推薦效果,是基于內(nèi)容推薦策略所要解決的主要問(wèn)題。l主要算法：l文本推薦方法l基于潛在語(yǔ)義分析的推薦l自適應(yīng)推薦文本推薦方法文本推薦方法l基于內(nèi)容的推薦方法根據(jù)歷史信息(如評(píng)價(jià)、分享、收藏

7、過(guò)的文檔)構(gòu)造用戶偏好文檔，計(jì)算推薦項(xiàng)目與用戶偏好文檔的相似度,將最相似的項(xiàng)目推薦給用戶。l相比于多媒體信息(視頻、音頻、圖片等)，文本類項(xiàng)目(新聞、網(wǎng)頁(yè)、博客)的特征提取相對(duì)容易,因而基于內(nèi)容的推薦方法在文本類推薦領(lǐng)域得到了廣泛應(yīng)用。基于潛在語(yǔ)義分析的推薦基于潛在語(yǔ)義分析的推薦l關(guān)鍵詞的同義和多義現(xiàn)象往往導(dǎo)致文檔相似度計(jì)算不準(zhǔn)確。l基本思想：采用文檔-詞矩陣奇異值分解的方法將文檔和詞語(yǔ)映射到同一個(gè)低維的潛在語(yǔ)義空間中計(jì)算各文檔與用戶查詢之間的相似度,據(jù)此返回最相關(guān)的文檔l缺點(diǎn)：采用奇異值分解得到的潛在語(yǔ)義空間物理意義不明確，矩陣的奇異值分解計(jì)算量大。自適應(yīng)推薦自適應(yīng)推薦l基于內(nèi)容推薦的關(guān)鍵是

8、 構(gòu)建和更新用戶偏好文檔。l用戶的興趣會(huì)隨時(shí)間動(dòng)態(tài)變化。l解決方法：采用貝葉斯分類、決策樹(shù)、聚類、人工神經(jīng)網(wǎng)絡(luò)等機(jī)器學(xué)習(xí)方法?；趦?nèi)容的推薦算法基于內(nèi)容的推薦算法l缺點(diǎn)：新用戶問(wèn)題、過(guò)擬合問(wèn)題、多媒體信息特征難提取等?；陉P(guān)聯(lián)規(guī)則推薦算法基于關(guān)聯(lián)規(guī)則推薦算法l關(guān)聯(lián)規(guī)則就是在一個(gè)交易數(shù)據(jù)庫(kù)中統(tǒng)計(jì)購(gòu)買了商品集X的交易中有多大比例的交易同事購(gòu)買了商品集Y。l基于關(guān)聯(lián)規(guī)則的推薦算法根據(jù)生成的關(guān)聯(lián)規(guī)則推薦模型和用戶的購(gòu)買行為向用戶產(chǎn)生推薦。l關(guān)聯(lián)規(guī)則推薦模型的建立離線進(jìn)行，可以保證有效推薦算法的實(shí)時(shí)性要求?；趫D結(jié)構(gòu)的推薦算法基于圖結(jié)構(gòu)的推薦算法1、用戶-項(xiàng)目矩陣可建模為一個(gè)二部圖(bipartite

9、graph),其中節(jié)點(diǎn)分別表示用戶和項(xiàng)目,邊表示用戶對(duì)項(xiàng)目的評(píng)價(jià)。基于圖結(jié)構(gòu)的推薦算法基于圖結(jié)構(gòu)的推薦算法2、計(jì)算資源分配矩陣W。項(xiàng)目j到項(xiàng)目i的資源分配權(quán)重wij計(jì)算如下:l其中Dj表示節(jié)點(diǎn)j的度?；趫D結(jié)構(gòu)的推薦算法基于圖結(jié)構(gòu)的推薦算法3 、 針 對(duì) 指 定 用 戶 計(jì) 算 各 項(xiàng) 目 的 資 源 分 配 。 令fi=(ai1,ai2,aim)表示用戶i的對(duì)m個(gè)項(xiàng)目的初始資源分配，fi表示用戶i的對(duì)m個(gè)項(xiàng)目的最終資源分配,則有fi=Wfi 。4、根據(jù)fi產(chǎn)生推薦列表。按fi中從大到小的順序排列生成一個(gè)推薦項(xiàng)目列表(用戶已經(jīng)偏好的項(xiàng)目除外)?；谥R(shí)的推薦算法基于知識(shí)的推薦算法l協(xié)同過(guò)濾和基

10、于內(nèi)容的推薦算法各有優(yōu)勢(shì)。但在很多情況下這些方法并不是最好的選擇。比較典型的是，我們并不會(huì)非常頻繁的購(gòu)買房屋、汽車或計(jì)算機(jī)。 這樣我們可能無(wú)法依賴購(gòu)買記錄。l基于知識(shí)的推薦不需要評(píng)分?jǐn)?shù)據(jù)，沒(méi)有冷啟動(dòng)問(wèn)題。l基于知識(shí)的算法根據(jù)顯示知識(shí)領(lǐng)域 模型進(jìn)行推理?；谥R(shí)的推薦算法基于知識(shí)的推薦算法l用戶必須指定需求，然后系統(tǒng)設(shè)法給出解決方案。如果找不到解決方案，用戶必須修改需求。此外系統(tǒng)還要給出推薦物品的解釋。l“汽車的最高價(jià)是X，顏色應(yīng)該是黑的”混合推薦算法混合推薦算法l混合推薦是為解決協(xié)同過(guò)濾、基于內(nèi)容和基于圖結(jié)構(gòu)推薦算法各自問(wèn)題而提出的，達(dá)到“相互取長(zhǎng)補(bǔ)短”的推薦效果。例如，基于內(nèi)容方法可以解決協(xié)

11、同過(guò)濾中“新項(xiàng)目”問(wèn)題,而協(xié)同過(guò)濾可降低基于內(nèi)容算法面臨的“過(guò)擬合”問(wèn)題。l混合推薦可以獨(dú)立運(yùn)用協(xié)同過(guò)濾、基于內(nèi)容和基于圖結(jié)構(gòu)的推薦算法，將兩者或多者產(chǎn)生的推薦結(jié)果進(jìn)行融合，再將融合后的結(jié)果推薦給用戶。問(wèn)題和分析問(wèn)題和分析l推薦算法缺點(diǎn)和挑戰(zhàn) 數(shù)據(jù)的稀疏性 冷啟動(dòng) 可擴(kuò)展性 實(shí)時(shí)性 特征提取 推薦結(jié)果解釋 過(guò)擬合 托攻擊問(wèn)題 隱私問(wèn)題 多種數(shù)據(jù)和多種推薦技術(shù)的有效集成 自動(dòng)化推薦（根據(jù)用戶行為，不一定要 顯示評(píng)分）數(shù)據(jù)的稀疏性數(shù)據(jù)的稀疏性l數(shù)據(jù)稀疏性的解決辦法：降維技術(shù)-壓縮矩陣（采用奇異值分解方法刪除不重要的或噪音用戶和項(xiàng)目）采用潛在語(yǔ)義索引技術(shù)將 用戶-項(xiàng)目 矩陣轉(zhuǎn)換成 用戶-類別 矩陣矩

12、陣填充技術(shù)（BP神經(jīng)網(wǎng)絡(luò)、Nave Bayesian分類方法、基于內(nèi)容的預(yù)測(cè)、基于項(xiàng)評(píng)分預(yù)測(cè)的IRPRec）冷啟動(dòng)冷啟動(dòng)l 協(xié)同過(guò)濾的缺點(diǎn)：冷啟動(dòng)l冷啟動(dòng)問(wèn)題的解決方法：基于內(nèi)容的最近鄰居查找技術(shù)可擴(kuò)展性可擴(kuò)展性l可擴(kuò)展性解決方法： 降維 聚類 分類SVD等降維技術(shù)、基于最近鄰的KNN算法、新的最近鄰度量相似度支持度、基于模型的CF算法（如聚類協(xié)同過(guò)濾算法）數(shù)據(jù)集數(shù)據(jù)集l常用的數(shù)據(jù)集：MovieLensEachMovieBookCrossingJester JokeNetflixUsenet NewsgroupsUCI知識(shí)庫(kù)評(píng)價(jià)準(zhǔn)則評(píng)價(jià)準(zhǔn)則l統(tǒng)計(jì)精度度量：平均絕對(duì)誤差MAE、均方根誤差RMSE -為用戶估計(jì)特定項(xiàng)目的評(píng)分l決策支持精度度量：