基于協(xié)同過濾算法的電影推薦系統(tǒng)

1、高級(jí)數(shù)據(jù)挖掘期末大作業(yè) 基于協(xié)同過濾算法的電影推薦系統(tǒng)本電影推薦系統(tǒng)中運(yùn)用的推薦算法是基于協(xié)同過濾算法（Collaborative Filtering Recommendation）。協(xié)同過濾是在信息過濾和信息系統(tǒng)中正迅速成為一項(xiàng)很受歡迎的技術(shù)。與傳統(tǒng)的基于內(nèi)容過濾直接分析內(nèi)容進(jìn)行推薦不同，協(xié)同過濾分析用戶興趣，在用戶群中找到指定用戶的相似（興趣）用戶，綜合這些相似用戶對(duì)某一信息的評(píng)價(jià)，形成系統(tǒng)對(duì)該指定用戶對(duì)此信息的喜好程度預(yù)測(cè)。電影推薦系統(tǒng)中引用了Apache Mahout提供的一個(gè)協(xié)同過濾算法的推薦引擎Taste，它實(shí)現(xiàn)了最基本的基于用戶和基于內(nèi)容的推薦算法，并提供了擴(kuò)展接口，使用戶方便的

2、定義和實(shí)現(xiàn)自己的推薦算法。電影推薦系統(tǒng)是基于用戶的推薦系統(tǒng)，即當(dāng)用戶對(duì)某些電影評(píng)分之后，系統(tǒng)根據(jù)用戶對(duì)電影評(píng)分的分值，判斷用戶的興趣，先運(yùn)用UserSimilarity計(jì)算用戶間的相似度.UserNeighborhood根據(jù)用戶相似度找到與該用戶口味相似的鄰居，最后由Recommender提供推薦個(gè)該用戶可能感興趣的電影詳細(xì)信息。將用戶評(píng)過分的電影信息和推薦給該用戶的電影信息顯示在網(wǎng)頁(yè)結(jié)果頁(yè)中，推薦完成。一、Taste 介紹Taste是 Apache Mahout 提供的一個(gè)個(gè)性化推薦引擎的高效實(shí)現(xiàn)，該引擎基于java實(shí)現(xiàn)，可擴(kuò)展性強(qiáng)，同時(shí)在mahout中對(duì)一些推薦算法進(jìn)行了MapReduce

3、編程模式轉(zhuǎn)化，從而可以利用hadoop的分布式架構(gòu)，提高推薦算法的性能。在Mahout0.5版本中的Taste， 實(shí)現(xiàn)了多種推薦算法，其中有最基本的基于用戶的和基于內(nèi)容的推薦算法，也有比較高效的SlopeOne算法，以及處于研究階段的基于SVD和線性插值的算法，同時(shí)Taste還提供了擴(kuò)展接口，用于定制化開發(fā)基于內(nèi)容或基于模型的個(gè)性化推薦算法。Taste 不僅僅適用于 Java 應(yīng)用程序，還可以作為內(nèi)部服務(wù)器的一個(gè)組件以 HTTP 和 Web Service 的形式向外界提供推薦的邏輯。Taste 的設(shè)計(jì)使它能滿足企業(yè)對(duì)推薦引擎在性能、靈活性和可擴(kuò)展性等方面的要求。下圖展示了構(gòu)成Taste的核心

4、組件：  從上圖可見，Taste由以下幾個(gè)主要組件組成：DataModel：DataModel是用戶喜好信息的抽象接口，它的具體實(shí)現(xiàn)支持從指定類型的數(shù)據(jù)源抽取用戶喜好信息。在Mahout0.5中，Taste 提供 JDBCDataModel 和 FileDataModel兩種類的實(shí)現(xiàn)，分別支持從數(shù)據(jù)庫(kù)和文件文件系統(tǒng)中讀取用戶的喜好信息。對(duì)于數(shù)據(jù)庫(kù)的讀取支持，在Mahout 0.5中只提供了對(duì)MySQL和PostgreSQL的支持，如果數(shù)據(jù)存儲(chǔ)在其他數(shù)據(jù)庫(kù)，或者是把數(shù)據(jù)導(dǎo)入到這兩個(gè)數(shù)據(jù)庫(kù)中，或者是自行編程實(shí)現(xiàn)相應(yīng)的類。UserSimilarit和ItemSimilarity：

5、前者用于定義兩個(gè)用戶間的相似度，后者用于定義兩個(gè)項(xiàng)目之間的相似度。Mahout支持大部分駐留的相似度或相關(guān)度計(jì)算方法，針對(duì)不同的數(shù)據(jù)源，需要合理選擇相似度計(jì)算方法。UserNeighborhood：在基于用戶的推薦方法中，推薦的內(nèi)容是基于找到與當(dāng)前用戶喜好相似的“鄰居用戶”的方式產(chǎn)生的，該組件就是用來定義與目標(biāo)用戶相鄰的“鄰居用戶”。所以，該組件只有在基于用戶的推薦算法中才會(huì)被使用。Recommender：Recommender是推薦引擎的抽象接口，Taste 中的核心組件。利用該組件就可以為指定用戶生成項(xiàng)目推薦列表。二、相似性度量本章節(jié)將系統(tǒng)中用到的幾個(gè)相似性度量函數(shù)作以介紹，taste中已

6、經(jīng)具體實(shí)現(xiàn)了各相似性度量類。User CF 和 Item CF 都依賴于相似度的計(jì)算，因?yàn)橹挥型ㄟ^衡量用戶之間或物品之間的相似度，才能找到用戶的“鄰居”，才能完成推薦。下面就對(duì)常用的相似度計(jì)算方法進(jìn)行詳細(xì)的介紹： 1. 基于皮爾森相關(guān)性的相似度 Pearson correlation-based similarity皮爾森相關(guān)系數(shù)反應(yīng)了兩個(gè)變量之間的線性相關(guān)程度，它的取值在-1, 1之間。當(dāng)兩個(gè)變量的線性關(guān)系增強(qiáng)時(shí)，相關(guān)系數(shù)趨于1或-1；當(dāng)一個(gè)變量增大，另一個(gè)變量也增大時(shí)，表明它們之間是正相關(guān)的，相關(guān)系數(shù)大于0；如果一個(gè)變量增大，另一個(gè)變量卻減小，表明它們之間是負(fù)相關(guān)的，相關(guān)系數(shù)小于0；如果相

7、關(guān)系數(shù)等于0，表明它們之間不存在線性相關(guān)關(guān)系。用數(shù)學(xué)公式表示，皮爾森相關(guān)系數(shù)等于兩個(gè)變量的協(xié)方差除于兩個(gè)變量的標(biāo)準(zhǔn)差。Pearson correlation-based similarity協(xié)方差（Covariance）：在概率論和統(tǒng)計(jì)學(xué)中用于衡量?jī)蓚€(gè)變量的總體誤差。如果兩個(gè)變量的變化趨于一致，也就是說如果其中一個(gè)大于自身的期望值，另一個(gè)也大于自身的期望值，那么兩個(gè)變量之間的協(xié)方差就是正值；如果兩個(gè)變量的變化趨勢(shì)相反，則協(xié)方差為負(fù)值。Covariance其中u表示X的期望E(X), v表示Y的期望E(Y)標(biāo)準(zhǔn)差（Standard Deviation）：標(biāo)準(zhǔn)差是方差的平方根Standard De

8、viation方差(Variance)：在概率論和統(tǒng)計(jì)學(xué)中，一個(gè)隨機(jī)變量的方差表述的是它的離散程度，也就是該變量與期望值的距離。Variance即方差等于誤差的平方和的期望基于皮爾森相關(guān)系數(shù)的相似度有兩個(gè)缺點(diǎn)：(1) 沒有考慮（take into account）用戶間重疊的評(píng)分項(xiàng)數(shù)量對(duì)相似度的影響；(2) 如果兩個(gè)用戶之間只有一個(gè)共同的評(píng)分項(xiàng)，相似度也不能被計(jì)算Table1上表中，行表示用戶（15）對(duì)項(xiàng)目（101103）的一些評(píng)分值。直觀來看，User1和User5用3個(gè)共同的評(píng)分項(xiàng)，并且給出的評(píng)分走差也不大，按理他們之間的相似度應(yīng)該比User1和User4之間的相似度要高，可是User1和

9、User4有一個(gè)更高的相似度1。同樣的場(chǎng)景在現(xiàn)實(shí)生活中也經(jīng)常發(fā)生，比如兩個(gè)用戶共同觀看了200部電影，雖然不一定給出相同或完全相近的評(píng)分，他們之間的相似度也應(yīng)該比另一位只觀看了2部相同電影的相似度高吧！但事實(shí)并不如此，如果對(duì)這兩部電影，兩個(gè)用戶給出的相似度相同或很相近，通過皮爾森相關(guān)性計(jì)算出的相似度會(huì)明顯大于觀看了相同的200部電影的用戶之間的相似度。Mahout對(duì)基于皮爾森相關(guān)系數(shù)的相似度給出了實(shí)現(xiàn)，它依賴一個(gè)DataModel作為輸入。PearsonCorrelationSimilarity同時(shí)，Mahout還針對(duì)缺點(diǎn)(1)進(jìn)行了優(yōu)化，只需要在構(gòu)造PearsonCorrelationSim

10、ilarity時(shí)多傳入一個(gè)Weighting.WEIGHTED參數(shù)，就能使有更多相同評(píng)分項(xiàng)目的用戶之間的相似度更趨近于1或-1。UserSimilarity similarity1 = new PearsonCorrelationSimilarity(model);double value1 = similarity1.userSimilarity(1, 5);UserSimilarity similarity2 = new PearsonCorrelationSimilarity(model, Weighting.WEIGHTED); double value2 = similarity2.

11、userSimilarity(1, 5);結(jié)果：Similarity of User1 and User5 with weighting: 0.96556948907691752. 基于歐幾里德距離的相似度 Euclidean Distance-based Similarity歐幾里德距離計(jì)算相似度是所有相似度計(jì)算里面最簡(jiǎn)單、最易理解的方法。它以經(jīng)過人們一致評(píng)價(jià)的物品為坐標(biāo)軸，然后將參與評(píng)價(jià)的人繪制到坐標(biāo)系上，并計(jì)算他們彼此之間的直線距離。Euclidean Distance 2-CoordinateTable2圖中用戶A和用戶B分別對(duì)項(xiàng)目X、Y進(jìn)行了評(píng)分。用戶A對(duì)項(xiàng)目X的評(píng)分為2，對(duì)項(xiàng)目Y的

12、評(píng)分為4，表示到坐標(biāo)系中為坐標(biāo)點(diǎn)A(1.8, 4)；同樣用戶B對(duì)項(xiàng)目X、Y的評(píng)分表示為坐標(biāo)點(diǎn)B(4.5, 2.5)，因此他們之間的歐幾里德距離（直線距離）為：sqrt(B.x - A.x)2 + (A.y - B.y)2)Euclidean Distance計(jì)算出來的歐幾里德距離是一個(gè)大于0的數(shù)，為了使其更能體現(xiàn)用戶之間的相似度，可以把它規(guī)約到(0, 1之間，具體做法為：1 / (1 + d)。參見Table2Euclidean Distance-based Similarity只要至少有一個(gè)共同評(píng)分項(xiàng)，就能用歐幾里德距離計(jì)算相似度；如果沒有共同評(píng)分項(xiàng)，那么歐幾里德距離也就失去了作用。其實(shí)照常

13、理理解，如果沒有共同評(píng)分項(xiàng)，那么意味著這兩個(gè)用戶或物品根本不相似。3. 余弦相似度 Cosine Similarity余弦相似度用向量空間中兩個(gè)向量夾角的余弦值作為衡量?jī)蓚€(gè)個(gè)體間差異的大小。相比距離度量，余弦相似度更加注重兩個(gè)向量在方向上的差異，而非距離或長(zhǎng)度上。Cosine Similarity與歐幾里德距離類似，基于余弦相似度的計(jì)算方法也是把用戶的喜好作為n-維坐標(biāo)系中的一個(gè)點(diǎn)，通過連接這個(gè)點(diǎn)與坐標(biāo)系的原點(diǎn)構(gòu)成一條直線（向量），兩個(gè)用戶之間的相似度值就是兩條直線（向量）間夾角的余弦值。因?yàn)檫B接代表用戶評(píng)分的點(diǎn)與原點(diǎn)的直線都會(huì)相交于原點(diǎn)，夾角越小代表兩個(gè)用戶越相似，夾角越大代表兩個(gè)用戶的相似

14、度越小。同時(shí)在三角系數(shù)中，角的余弦值是在-1, 1之間的，0度角的余弦值是1，180角的余弦值是-1。借助三維坐標(biāo)系來看下歐氏距離和余弦相似度的區(qū)別：Distance and Cosine 3-Coordinates從圖上可以看出距離度量衡量的是空間各點(diǎn)間的絕對(duì)距離，跟各個(gè)點(diǎn)所在的位置坐標(biāo)（即個(gè)體特征維度的數(shù)值）直接相關(guān)；而余弦相似度衡量的是空間向量的夾角，更加的是體現(xiàn)在方向上的差異，而不是位置。如果保持A點(diǎn)的位置不變，B點(diǎn)朝原方向遠(yuǎn)離坐標(biāo)軸原點(diǎn)，那么這個(gè)時(shí)候余弦相似度cos是保持不變的，因?yàn)閵A角不變，而A、B兩點(diǎn)的距離顯然在發(fā)生改變，這就是歐氏距離和余弦相似度的不同之處。根據(jù)歐氏距離和余弦相

15、似度各自的計(jì)算方式和衡量特征，分別適用于不同的數(shù)據(jù)分析模型：歐氏距離能夠體現(xiàn)個(gè)體數(shù)值特征的絕對(duì)差異，所以更多的用于需要從維度的數(shù)值大小中體現(xiàn)差異的分析，如使用用戶行為指標(biāo)分析用戶價(jià)值的相似度或差異；而余弦相似度更多的是從方向上區(qū)分差異，而對(duì)絕對(duì)的數(shù)值不敏感，更多的用于使用用戶對(duì)內(nèi)容評(píng)分來區(qū)分用戶興趣的相似度和差異，同時(shí)修正了用戶間可能存在的度量標(biāo)準(zhǔn)不統(tǒng)一的問題（因?yàn)橛嘞蚁嗨贫葘?duì)絕對(duì)數(shù)值不敏感）。Mahout沒有專門給出基于余弦相似度的實(shí)現(xiàn)。 4. 調(diào)整余弦相似度 Adjusted Cosine Similarity在余弦相似度的介紹中說到：余弦相似度更多的是從方向上區(qū)分差異，而對(duì)絕對(duì)的數(shù)值不敏

16、感。因此沒法衡量每個(gè)維數(shù)值的差異，會(huì)導(dǎo)致這樣一個(gè)情況：比如用戶對(duì)內(nèi)容評(píng)分，5分制，X和Y兩個(gè)用戶對(duì)兩個(gè)內(nèi)容的評(píng)分分別為(1,2)和(4,5)，使用余弦相似度得出的結(jié)果是0.98，兩者極為相似，但從評(píng)分上看X似乎不喜歡這2個(gè)內(nèi)容，而Y比較喜歡，余弦相似度對(duì)數(shù)值的不敏感導(dǎo)致了結(jié)果的誤差，需要修正這種不合理性，就出現(xiàn)了調(diào)整余弦相似度，即所有維度上的數(shù)值都減去一個(gè)均值，比如X和Y的評(píng)分均值都是3，那么調(diào)整后為(-2,-1)和(1,2)，再用余弦相似度計(jì)算，得到-0.8，相似度為負(fù)值并且差異不小，但顯然更加符合現(xiàn)實(shí)。5. 斯皮爾曼相關(guān) Spearman Correlation斯皮爾曼相關(guān)性可以理解為是排

17、列后（Rank）用戶喜好值之間的Pearson相關(guān)度。Mahout in Action中有這樣的解釋：假設(shè)對(duì)于每個(gè)用戶，我們找到他最不喜歡的物品，重寫他的評(píng)分值為“1”；然后找到下一個(gè)最不喜歡的物品，重寫評(píng)分值為“2”，以此類推。然后我們對(duì)這些轉(zhuǎn)換后的值求Pearson相關(guān)系數(shù)，這就是Spearman相關(guān)系數(shù)。斯皮爾曼相關(guān)度的計(jì)算舍棄了一些重要信息，即真實(shí)的評(píng)分值。但它保留了用戶喜好值的本質(zhì)特性排序（ordering），它是建立在排序（或等級(jí)，Rank）的基礎(chǔ)上計(jì)算的。回顧前面表中User15對(duì)Item101103的喜好（評(píng)分）值，通過斯皮爾曼相關(guān)系數(shù)計(jì)算出的相似度為：Table3我們發(fā)現(xiàn)，計(jì)

18、算出來的相似度值要么是1，要么是-1，因?yàn)檫@依賴于用戶的喜好值和User1的喜好值是否趨于“一致變化”還是呈“相反趨勢(shì)變化"。Mahout對(duì)斯皮爾曼相關(guān)系數(shù)給出了實(shí)現(xiàn)，具體可參考SpearmanCorrelationSimilarity，它的執(zhí)行效率不是非常高，因?yàn)樗蛊柭嚓P(guān)性的計(jì)算需要花時(shí)間計(jì)算并存儲(chǔ)喜好值的一個(gè)排序（Ranks），具體時(shí)間取決于數(shù)據(jù)的數(shù)量級(jí)大小。正因?yàn)檫@樣，斯皮爾曼相關(guān)系數(shù)一般用于學(xué)術(shù)研究或者是小規(guī)模的計(jì)算。UserSimilarity similarity1 = new SpearmanCorrelationSimilarity(model); / const

19、ruct a Spearman Correlation-based SimilarityUser1 to User1 : 1.0User2 to User1 : -1.0User3 to User1 : NaNUser4 to User1 : 1.0User4 to User1 : 1.0考慮到Spearman Correlation的效率，可以把SpearmanCorrelationSimilarity包裝一層Cache，具體做法為： UserSimilarity similarity2 = new CachingUserSimilarity(new SpearmanCorrelationS

20、imilarity(model), model);這樣，每次計(jì)算的結(jié)果會(huì)直接放入Cache，下一次計(jì)算的時(shí)候可以立即得到結(jié)果，而不是重新再計(jì)算一次。6. 基于谷本系數(shù)的相似性度量 Tanimoto Coefficient-based SimilarityTanimoto Coefficient和前面的5中相關(guān)度計(jì)算方式有很大的不同，它不關(guān)心用戶對(duì)物品的具體評(píng)分值是多少，它在關(guān)心用戶與物品之間是否存在關(guān)聯(lián)關(guān)系。Tanimoto Coefficient依賴于用戶和物品之間的這種Boolean關(guān)系作為輸入。更準(zhǔn)確的說法為：Tanimoto Coefficient主要用于計(jì)算符號(hào)度量或布爾值度量的個(gè)體

21、間的相似度，因?yàn)閭€(gè)體的特征屬性都是由符號(hào)度量或者布爾值標(biāo)識(shí)，因此無法衡量差異具體值的大小，只能獲得“是否相同”這個(gè)結(jié)果，所以Tanimoto Coefficient只關(guān)心個(gè)體間共同具有的特征是否一致這個(gè)問題。Tanimoto Coefficient又被叫做Jaccard Coefficient，其值等于兩個(gè)用戶共同關(guān)聯(lián)（不管喜歡還是不喜歡）的物品數(shù)量除于兩個(gè)用戶分別關(guān)聯(lián)的所有物品數(shù)量。Intersection/Union也就是關(guān)聯(lián)的交集除于關(guān)聯(lián)的并集，用公式表示為：Tanimoto/Jaccard Coefficient其值介于0, 1之間，如果兩個(gè)用戶關(guān)聯(lián)的物品完全相同，交集等于并集，值為1

22、；如果沒有任何關(guān)聯(lián)，交集為空，值為0。三、電影推薦系統(tǒng)的實(shí)現(xiàn)1. 數(shù)據(jù)下載：到grouplens網(wǎng)站（）上下載Data Sets，在該電影系統(tǒng)中我們使用了將近900多用戶為1683的電影評(píng)了近100000行的數(shù)據(jù)集。將下載的ml-data_0.zip里的評(píng)分?jǐn)?shù)據(jù)和電影信息數(shù)據(jù)取出。將評(píng)分文件轉(zhuǎn)換成類似于csv文件格式的文本文件，CSV是逗號(hào)分隔值文件(Comma Separated value)，是一種用來存儲(chǔ)數(shù)據(jù)的純文本文件格式,文件名為rating.TXT?？梢杂脤懽职宕蜷_，如圖4.1：圖4.1 rating.txt示意圖然后將數(shù)據(jù)導(dǎo)入到mysql數(shù)據(jù)庫(kù)中，將電影數(shù)據(jù)文件也轉(zhuǎn)換成CSV格式文件，然后也導(dǎo)入數(shù)據(jù)庫(kù)中，Mysql中數(shù)據(jù)庫(kù)為movierecommendation，上述兩個(gè)文件對(duì)應(yīng)的表分別為movies和rating。由于taste引擎需要頻繁進(jìn)行數(shù)據(jù)庫(kù)操作，所以可以對(duì)mysql數(shù)據(jù)庫(kù)進(jìn)行一般的調(diào)優(yōu)，在mysql安裝目錄的my.ini文件中設(shè)置一些參數(shù)，從而加快數(shù)據(jù)庫(kù)操作運(yùn)行的時(shí)間。2. 系統(tǒng)結(jié)構(gòu)：本電影推薦系統(tǒng)前臺(tái)導(dǎo)航欄有三個(gè)菜單，分別為首頁(yè)，推薦電影，參數(shù)設(shè)置。首頁(yè)：首頁(yè)上顯示綜合評(píng)分最高的前20部電影，綜合評(píng)分是指對(duì)于一部電影，所有觀看改電影的用戶的評(píng)分的期望值。實(shí)現(xiàn)為在index.jsp頁(yè)面中調(diào)用數(shù)據(jù)庫(kù)接口，查詢數(shù)據(jù)庫(kù)，然后將結(jié)果顯示出來：參數(shù)設(shè)置頁(yè)