基于優(yōu)化歐氏距離的協(xié)同過濾推薦

陳小輝，高 燕

(榆林學(xué)院信息工程學(xué)院，陜西 榆林 719000)

0 引言

在過去的十余年中，網(wǎng)絡(luò)上的信息數(shù)量呈爆炸模式大幅增長，同時也伴隨著網(wǎng)上電子商務(wù)成交量的大幅提升，越來越多的人愿意通過互聯(lián)網(wǎng)獲取需要的商品和服務(wù)，可是由于網(wǎng)上巨大的信息量，用戶獲取有效信息的成本變得日益昂貴。推薦系統(tǒng)作為一種信息超載的有效解決方案逐漸在許多領(lǐng)域得到應(yīng)用，特別是在一些電子商務(wù)網(wǎng)絡(luò)中，如亞馬遜、淘寶、京東商城等，運(yùn)營商使用推薦系統(tǒng)幫助客戶從海量的商品中挑選自己喜愛的書籍、CD、衣服、家具，甚至，汽車、房產(chǎn)等，而在一些社交網(wǎng)絡(luò)和其他領(lǐng)域，也會用到推薦系統(tǒng)來幫助客戶找到其潛在的朋友、客戶等。

推薦系統(tǒng)所使用的算法主要有基于內(nèi)容的推薦算法、協(xié)同過濾推薦算法和結(jié)合內(nèi)容與協(xié)同過濾的推薦算法。協(xié)同過濾(Collaborative Filtering，CF)推薦是根據(jù)用戶自身數(shù)據(jù)和對項目的評價數(shù)據(jù)，按照一定的鄰居查找算法找出若干個相似性較高的鄰居，使用這些鄰居的評價數(shù)據(jù)預(yù)測當(dāng)前用戶對一些項目的評價并給出推薦［1-2］。協(xié)同過濾推薦算法又可進(jìn)一步分為基于內(nèi)存和基于模型2 類，前者常用于現(xiàn)在大多數(shù)的網(wǎng)上交易和服務(wù)系統(tǒng)，后者多用于相關(guān)的推薦算法研究?；趦?nèi)存的協(xié)同過濾推薦過程是先計算用戶或者item 之間的相似度，然后找相似度最高的若干鄰居，再根據(jù)鄰居的數(shù)據(jù)計算預(yù)測值并形成項目或者用戶推薦［4］。

在現(xiàn)實(shí)網(wǎng)絡(luò)推薦系統(tǒng)中，由于每個具體用戶往往只是購買了或者使用了網(wǎng)站中數(shù)以萬計商品或服務(wù)中的極少數(shù)一部分，因此用戶僅僅對極少一部分項目有有效評價數(shù)據(jù)，這會導(dǎo)致用戶項目評分?jǐn)?shù)據(jù)矩陣異常稀疏從而產(chǎn)生數(shù)據(jù)稀疏問題;再次是冷啟動問題，當(dāng)協(xié)同過濾推薦系統(tǒng)中加入新的用戶或者是新的評價項目時，新用戶或項目的相關(guān)評價結(jié)果缺失或者是極為稀少，這些問題對于最近鄰居的尋找以及有效推薦造成了一些困難［5-7］。

對于以上問題，許多研究人員都提出了一些改進(jìn)的策略，文獻(xiàn)［8］提出了一種分階段評分預(yù)測法，該方法先采用聚類方法對原始評分矩陣中的用戶和item 進(jìn)行聚類，然后使用加權(quán)非負(fù)矩陣分解方法在聚類結(jié)果上進(jìn)行預(yù)測推薦;文獻(xiàn)［9］將融合聚類(Cluster Ensemble)算法應(yīng)用到協(xié)同過濾推薦中;文獻(xiàn)［10］使用奇異值分解技術(shù)實(shí)現(xiàn)對評分矩陣進(jìn)行降維，從而尋找用戶之間的隱含關(guān)系;文獻(xiàn)［11］使用因子分析方法先對評價數(shù)據(jù)進(jìn)行降維操作，然后用回歸分析策略預(yù)測未知評價數(shù)據(jù)。以上解決方法在一些方面彌補(bǔ)了數(shù)據(jù)稀疏以及冷啟動造成的困難，但是在進(jìn)行用戶或者項目相似性度量時，往往忽視用戶向量之間(或項目向量之間)的長度差異，以及忽略共同評價項目的(或共同評價用戶)數(shù)量上的不同，這往往會導(dǎo)致對于最近鄰計算的失真。

本文提出一種采用優(yōu)化歐氏距離的最近鄰居度量算法，該算法考慮了評分空間中用戶評分向量(或者項目評分向量)在數(shù)據(jù)維度上的差異，并且考慮了鄰居和當(dāng)前用戶共同評分項目數(shù)以及每個用戶的評分項目數(shù)。與通常采用的傳統(tǒng)相似性計算方法比較，該算法的相似度計算結(jié)果更加符合實(shí)際情況，使推薦系統(tǒng)的推薦效率和準(zhǔn)確率都有了明顯改善。

1 相關(guān)工作

基于內(nèi)存的推薦算法是目前商業(yè)推薦系統(tǒng)中應(yīng)用最多的推薦算法，本文以其中基于用戶(Userbased)的協(xié)同推薦系統(tǒng)為例來說明推薦系統(tǒng)的工作原理，該方法是在用戶項目評價二維矩陣上，通過一定的方法尋找一些相似度較高的鄰居，使用一定的算法按照鄰居對待預(yù)測項目評分來預(yù)測當(dāng)前用戶對該項目的評分［12-13］。協(xié)同過濾推薦系統(tǒng)實(shí)現(xiàn)包括數(shù)據(jù)定義、相似度計算和評分預(yù)測及推薦。

1.1 評價數(shù)據(jù)定義

采集網(wǎng)絡(luò)系統(tǒng)中所有用戶對項目的評價數(shù)據(jù)形成一個二維矩陣，如圖1 所示，該矩陣R 是一個n×m二維表，n 表示用戶數(shù)量，m 表示評價項目數(shù)量，表中值Rx，y代表第x 個用戶對于第y 個項目的評價結(jié)果。而評價結(jié)果，一般可分為顯式評價和隱式評價2 類，顯式評價是用戶對項目的直接評分，隱式評價則是依據(jù)用戶的一些行為如對相應(yīng)網(wǎng)頁的瀏覽頻次、停留時間、是否購買等來給出的量化表示。矩陣的每一個水平向量表示一個用戶對項目的評價，矩陣的每一個垂直向量表示某個項目從用戶處得到的評價。用戶評分矩陣如圖1 所示。

圖1 用戶-項目評價矩陣

1.2 相似度計算

協(xié)同過濾推薦算法的根本在于對最近鄰居的查找，查找中用以度量用戶相似性的傳統(tǒng)方法有向量空間相似性度量方法(VSS，Vector Space Similitude)以及皮爾森相似性度量方法(PCC，Pearson Correlation Coefficient)2 種。向量空間度量方法是把用戶對n 個項目的評價值作為一個n 維向量，2 個用戶之間的相似值使用2 個n 維向量之間的夾角余弦值來表示［14］。假設(shè)用戶u 和用戶v 對于產(chǎn)品i 的評分分別為rui和rvi，用戶u 和v 所共同評價過的產(chǎn)品集合為Iuv;則用戶u 和v 的相似度計算如式(1)所示。

PCC 相似性度量算法則是基于變量的線性關(guān)系，用戶u，v 的相似度計算Sim(u，v)如式(2)所示，分別表示u 和v 所有有效評價的平均值，Iuv表示被用戶u 與用戶v 共同評價過的項目集。

1.3 預(yù)測評分與項目推薦

在使用VSS 或者PCC 相似性度量算法計算得到兩兩用戶間的相似度后，得到K 個與當(dāng)前用戶具有最大相似度的鄰居，如果需要對當(dāng)前用戶的某項未評分項目進(jìn)行預(yù)測時，可以使用特定的計算方法基于鄰居在該項目的評價來得到預(yù)測值［15］。用戶u 對項目i 的預(yù)測評分值可以使用公式(3)計算，為提高算法的可靠性，式中考慮了用戶間評分習(xí)慣和評分尺度的不同，并且還使用了用戶所有評價的平均值，N(u)為找到的相似鄰居集合，集合規(guī)模為K。計算得到項目的預(yù)測評分后，可對未評價項目排序，并形成若干推薦項目。

2 基于優(yōu)化歐氏距離鄰居相似性度量方法

2.1 傳統(tǒng)協(xié)同過濾推薦算法的缺陷

在傳統(tǒng)的協(xié)同過濾推薦系統(tǒng)中對于用戶之間相似度的計算方法，無論是VSS 算法還是PCC 算法都是在用戶對項目的原始評價值上計算相似性，而沒有考慮用戶的評價數(shù)值大小差異和評價項目數(shù)量的差異，這樣常常會得到與實(shí)際情況不相符合的推薦結(jié)果［16-17］。例如圖2 表示5 個用戶對5 個項目的評價矩陣，用戶的評價值在1 和6 之間，空白項目表示用戶未做評價。假設(shè)要預(yù)測用戶u2對于項目i5的評價，依次使用VSS 和PCC 鄰居相似性度量算法計算用戶相似度，可得u1和u2的相似值為0.9448 和0.6703，u2和u3的相似度為0.8451 和0.5273，從計算結(jié)果看u1與u2的相似性要比u2與u3的相似性強(qiáng)。但是用戶u1的評價值位于［1，6］區(qū)間，而用戶u2和u3的評價值位于［1，4］區(qū)間，從習(xí)慣性常識來看u2與u3的相似性應(yīng)該更強(qiáng)，在預(yù)測用戶u2對項目i5的評價時更應(yīng)當(dāng)考慮的鄰居是u3并不是u1。這是因為VSS 算法和PCC算法都不考慮不同用戶在對項目評分時評價值的范圍差異和有效評分項目數(shù)的差異。

圖2 用戶項目評分矩陣示例

2.2 距離鄰居相似性度量方法

針對傳統(tǒng)鄰居相似性度量方法的缺陷，本文設(shè)計了一種基于優(yōu)化歐氏距離的相似性度量方法(Optimization Euclidean Distance Similarity Measurement，簡記為OED)。傳統(tǒng)的歐氏距離方法也可以用來計算用戶向量之間的距離，但是推薦系統(tǒng)中用戶向量的歐氏距離一般是在不同維度的向量空間中計算，直接用它們的歐氏距離度量相似度和傳統(tǒng)的用戶相似性度量方法結(jié)果差異不大，而本文所提出的OED 方法在度量2 個向量的相似性時考慮了不同用戶向量所處的多維向量空間的維數(shù)差異。

假設(shè)在m 維向量空間中用戶u 和用戶v 的評價向量分別為，distmax表示m 維空間上的最大歐氏距離，dist()表示用戶向量之間的歐氏距離，則用戶u 和用戶v 之間的歸一化歐氏距離如式(4)所示。

用戶u 和用戶v 的相似程度可以用式(4)的倒數(shù)來表示，用Iuv代表用戶u 與用戶v 共同評分項目的集合，用戶評價向量的維度為m，且所有用戶的最大評價值為rmax，最小評價值為rmin，則用戶u，v 的相似度計算Sim(u，v)如式5 所示。

考慮不同用戶有效評價項目的數(shù)量差異以及共同評價項目的數(shù)量差異，為了使相似度值更符合實(shí)際情況，在公式(5)歸一化處理的基礎(chǔ)上引入杰卡德相似系數(shù)，則得到公式(6)，式中Iu和Iv分別表示用戶u和用戶v 的有效評價項目集合，|Iuv|、|Iu∪Iv|表示相應(yīng)集合中的項目個數(shù)。

公式(5)、(6)都假設(shè)不存在2 個用戶u，v 對所有項目的評分完全相同，此時用戶u 和v 的相似度越高，則Sim(u，v)值越大;如果存在u，v 對所有項目的評分完全相同，則默認(rèn)這2 個用戶的相似值取最大值。

3 實(shí) 驗

3.1 數(shù)據(jù)集

為了比對測試OED 相似性度量方法的效果，采用來自于Group Lens 研究小組提供的Movielens 電影評價數(shù)據(jù)集。該數(shù)據(jù)集包含有943 個用戶對于1682部電影的評價，所有用戶都有20 個以上的評價值，數(shù)據(jù)集的稀疏度為93.7%。由于實(shí)際評價數(shù)據(jù)往往較為稀疏，實(shí)驗中對原始數(shù)據(jù)進(jìn)行隨機(jī)刪減，形成了稀疏度分別為2%、4%、6%、8%、10%、12%、14%、16%、18%和20%的10 個稀疏評價矩陣。

3.2 評價標(biāo)準(zhǔn)

實(shí)驗中使用常用的評價推薦是用準(zhǔn)確度的平均絕對誤差(Mean Absolute Error，MAE)值來評價OED算法的效果，MAE 值是預(yù)測值和實(shí)際值之間的方差均值，如式(8)所示。用戶u 對項目i 的真實(shí)評價用rui表示，通過算法預(yù)測的用戶u 對項目i 的評分值用表示，N 為全部預(yù)測評價值數(shù)量，MAE 值和預(yù)測的準(zhǔn)確度成反比，值越小則預(yù)測得越準(zhǔn)確。

3.3 實(shí)驗方案

為了檢驗OED 相似性度量方法的有效性，實(shí)驗中采用了基本歐氏距離相似性度量算法(ED，Euclidean Distance)、向量空間相似性度量算法VSS、優(yōu)化的向量空間夾角余弦算法AdjCOS 和皮爾森相似性度量算法PCC。傳統(tǒng)歐氏距離相似度計算公式見公式(7)，VSS 和PCC 相似度計算公式見公式(1)、公式(2)，ED 和AdjCOS 度量方法見公式(7)、公式(8)，式中rmid為用戶評分空間中最大評價值與最小評價值的平均數(shù)。依次將5 種相似度計算算法用到基于用戶的協(xié)同過濾推薦中去，采用公式(3)來計算預(yù)測值。

采用五折交叉驗證(5-Fold Cross Validation)來實(shí)驗，分別從10 個稀疏評價矩陣中隨機(jī)抽取10%的數(shù)據(jù)作為測試數(shù)據(jù)集，剩余部分為訓(xùn)練數(shù)據(jù)集。共進(jìn)行5 次劃分，在每一折實(shí)驗中，基于訓(xùn)練集數(shù)據(jù)預(yù)測測試集數(shù)據(jù)，并通過比較預(yù)測評分和真實(shí)評分得出每一折的MAE 值，最后計算得到平均MAE 值。實(shí)驗中最近鄰居數(shù)k 分別取10、20、30、40 和50，圖2 和圖3 分別給出了鄰居數(shù)k 等于10 和50 時相似度度量方法的性能比對。

圖2 k=10 時性能比對圖

圖3 k=50 時性能比對圖

從圖2 和圖3 可以看出，采用OED 方法推薦系統(tǒng)的MAE 值要明顯小于采用原始?xì)W氏距離相似性度量方法的推薦系統(tǒng)，而且也小于應(yīng)用其他3 種傳統(tǒng)的相似性度量算法的推薦系統(tǒng)，說明使用OED 算法其推薦結(jié)果更加接近于實(shí)際情況。并且從圖(2)和圖(3)中可以看出當(dāng)評分矩陣的數(shù)據(jù)密度逐漸增大時OED 推薦算法的MAE 值變化不大，但是當(dāng)用戶評分矩陣數(shù)據(jù)較為稀疏時候，OED 的表現(xiàn)更優(yōu)秀，說明當(dāng)數(shù)據(jù)稀疏，用戶向量的維度趨于多樣，這時OED 算法有更優(yōu)秀表現(xiàn)。

圖4 鄰居數(shù)對MAE 值的影響

圖4 為評分矩陣數(shù)據(jù)密度取10%時，鄰居數(shù)從10 變化到50 對應(yīng)的OED 算法推薦MAE 值的變化，說明OED 算法推薦性能會隨著鄰居數(shù)的增長而提高，當(dāng)鄰居數(shù)增長至40 以后，MAE 值變化趨于平緩。實(shí)驗表明相對于其它傳統(tǒng)推薦算法，使用OED 鄰居相似性度量算法能夠有效提高過濾推薦系統(tǒng)的性能，而且該方法能夠應(yīng)用于數(shù)據(jù)稀疏度較高的評價矩陣。

4 結(jié)束語

系統(tǒng)過濾推薦系統(tǒng)中所采用的傳統(tǒng)相似性度量方法往往存在一定的不足，本文所提出的基于歸一化歐氏距離鄰居相似性度量方法，可用于解決各協(xié)同過濾推薦系統(tǒng)中的對評價項目的評分預(yù)測和推薦問題，特別是對于實(shí)際應(yīng)用推薦系統(tǒng)中高度稀疏的評價數(shù)據(jù)，該算法能夠更加準(zhǔn)確地查找鄰居，從而提高推薦的性能。

［1］鄧曉懿，金淳，韓慶平，等.基于情境聚類和用戶評級的協(xié)同過濾推薦模型［J］.系統(tǒng)工程理論與實(shí)踐，2013，33(11):2945-2953.

［2］Shi Y，Larson M，Hanjalic A.Exploiting user similarity based on rated-item pools for improved user-based collaborative filtering［C］// Proceedings of the 2009 ACM Conference on Recommender Systems.2009:125-132.

［3］Robert B，Yehuda K，Chris V.Modeling relationships at multiple scales to improve accuracy of large recommender systems［C］// Proceeding of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.California，USA，2007:95-104.

［4］代金龍.協(xié)同過濾算法中數(shù)據(jù)稀疏性問題研究［D］.重慶:重慶大學(xué)，2013.

［5］王道平，李秀雅，楊岑.基于內(nèi)容相似度的知識協(xié)同過濾推送算法研究［J］.情報理論與實(shí)踐，2013，36(10):86-90.

［6］王玉斌，孟祥武，胡勛.一種基于信息老化的協(xié)同過濾推薦算法［J］.電子與信息學(xué)報，2013，35(10):2391-2396.

［7］吳湖，王永吉，王哲，等.兩階段聯(lián)合聚類協(xié)同過濾算法［J］.軟件學(xué)報，2011，21(5):1042-1054.

［8］Tsai C F，Hung C.Cluster ensembles in collaborative filtering recommendation［J］.Applied Soft Computing，2012，12(4):1417-1425.

［9］Sarwar B，Karypis G，Konstan J.Item-based collaborative filtering recommendation algorithms［C］// Proceedings of the 10th International World Wide Web Conference.New York，2001:285-295.

［10］趙宏霞，王新海，楊皎平.基于用戶和項目因子分析的混合協(xié)同推薦算法［J］.計算機(jī)應(yīng)用，2011，31(5):1382-1386.

［11］李忠俊，周啟海，帥青紅.一種基于內(nèi)容和協(xié)同過濾同構(gòu)化整合的推薦系統(tǒng)模型［J］.計算機(jī)科學(xué)，2009，36(12):142-145.

［12］李濤，王建東，葉飛躍，等.一種基于用戶聚類的協(xié)同過濾推薦算法［J］.系統(tǒng)工程與電子技術(shù)，2007，29(7):1178-1182.

［13］劉慶鵬，陳明銳.優(yōu)化稀疏數(shù)據(jù)集提高協(xié)同過濾推薦系統(tǒng)質(zhì)量的方法［J］.計算機(jī)應(yīng)用，2012，32(4):1082-1085.

［14］李改，潘嶸，李章鳳，等.基于大數(shù)據(jù)集的協(xié)同過濾算法的并行化研究［J］.計算機(jī)工程與設(shè)計，2012，33(6):2437-2441.

［15］李華，張宇，孫俊華.基于用戶模糊聚類的協(xié)同過濾推薦研究［J］.計算機(jī)科學(xué)，2012，39(12):83-86.

［16］于洪，李轉(zhuǎn)運(yùn).基于遺忘曲線的協(xié)同過濾推薦算法［J］.南京大學(xué)學(xué)報(自然科學(xué)版)，2010，46(5):520-527.

［17］王海艷，張大印.一種可信的基于協(xié)同過濾的服務(wù)選擇模型［J］.電子與信息學(xué)報，2013，35(2):349-354.