基于距離衰減和評(píng)分趨勢(shì)改進(jìn)的協(xié)同推薦算法

王 勇，易 庭

(廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院，廣東廣州510006)

隨著移動(dòng)互聯(lián)網(wǎng)的發(fā)展，越來(lái)越多的用戶都通過手機(jī)、平板等設(shè)備接入互聯(lián)網(wǎng)，如何從用戶的位置信息中挖掘出商業(yè)利益已經(jīng)成為推薦領(lǐng)域的研究熱點(diǎn).在商品推薦領(lǐng)域中常用的推薦算法有基于內(nèi)容推薦、協(xié)同過濾推薦、基于規(guī)則推薦、基于知識(shí)推薦等算法，其中協(xié)同過濾算法是在移動(dòng)推薦領(lǐng)域中運(yùn)用最為廣泛的算法［1］.但是協(xié)同過濾推薦算法在實(shí)際應(yīng)用中也存在不足，其中用戶評(píng)價(jià)標(biāo)準(zhǔn)不一導(dǎo)致評(píng)分矩陣誤差較大，SVD算法提出基于矩陣奇異值分解的方法解決該問題，但是該算法效率較低、運(yùn)算量大.越來(lái)越多的移動(dòng)軟件開始考慮用戶的位置信息，試圖通過用戶位置信息來(lái)提供更加精準(zhǔn)個(gè)性化的服務(wù).

移動(dòng)推薦系統(tǒng)可以利用地點(diǎn)、時(shí)間、天氣等信息來(lái)影響推薦結(jié)果，其中基于位置的移動(dòng)推薦系統(tǒng)是根據(jù)用戶的位置信息來(lái)提供準(zhǔn)確的個(gè)性化推薦［2］.移動(dòng)用戶的興趣偏好隨著地理位置的不同會(huì)發(fā)生變化，同時(shí)待推薦商品也隨著用戶位置的移動(dòng)而改變.然而當(dāng)前移動(dòng)推薦系統(tǒng)中考慮位置信息比較單一，只是簡(jiǎn)單根據(jù)用戶位置獲取用戶周邊的商品和服務(wù)，或者根據(jù)用戶與商品的距離對(duì)待推薦商品進(jìn)行排序，并沒有深入研究距離對(duì)推薦系統(tǒng)產(chǎn)生的影響.距離的遠(yuǎn)近反映了用戶到達(dá)目的地的成本，推薦商品的距離越遠(yuǎn)，用戶對(duì)該商品選擇的概率會(huì)隨之減少.對(duì)于推薦商品，用戶在其距離和喜好度上進(jìn)行綜合考慮，用戶可能會(huì)選擇一個(gè)喜好度較低但距離更近的商品.僅僅通過距離遠(yuǎn)近對(duì)推薦商品進(jìn)行排序往往導(dǎo)致推薦的結(jié)果不能滿足用戶需求.Abowd等［3］提出的移動(dòng)旅游推薦系統(tǒng)，通過位置獲取天氣、溫度等過濾推薦項(xiàng)目，并沒有考慮移動(dòng)用戶的個(gè)性化偏好和距離給用戶帶來(lái)的影響.Girardello等［4］提出的應(yīng)用程序推薦系統(tǒng)，該系統(tǒng)考慮了用戶位置信息對(duì)用戶選擇的影響，并沒有考慮移動(dòng)用戶個(gè)人偏好和距離對(duì)應(yīng)用程序選擇的影響.Yang［5］通過統(tǒng)計(jì)分析移動(dòng)用戶訪問過的商家網(wǎng)頁(yè)，但是其忽略了“鄰居”用戶的距離關(guān)系.同時(shí)由于用戶對(duì)商品的評(píng)價(jià)標(biāo)準(zhǔn)不同，部分用戶在給商品進(jìn)行評(píng)價(jià)時(shí)容易給出高分，而部分用戶對(duì)非喜愛的商品評(píng)分較低，導(dǎo)致評(píng)分矩陣的誤差較大，從而降低推薦列表準(zhǔn)確度.

本文通過研究距離和評(píng)分趨勢(shì)對(duì)推薦系統(tǒng)的影響，在協(xié)同推薦的基礎(chǔ)上，提出一種新的基于距離衰減和評(píng)分趨勢(shì)改進(jìn)的商品推薦方法.該方法中引入距離衰減函數(shù)和評(píng)分趨勢(shì)函數(shù)對(duì)協(xié)同推薦算法進(jìn)行改進(jìn)，并實(shí)現(xiàn)了一個(gè)基于該推薦方法的商品推薦系統(tǒng).

1 改進(jìn)的協(xié)同推薦系統(tǒng)

推薦系統(tǒng)主要是根據(jù)用戶的位置信息和購(gòu)買歷史等數(shù)據(jù)為用戶提供精準(zhǔn)推薦，本系統(tǒng)包括手機(jī)客戶端和服務(wù)器端，其系統(tǒng)架構(gòu)如圖1所示.用戶通過移動(dòng)設(shè)備向服務(wù)器發(fā)起請(qǐng)求，請(qǐng)求中攜帶位置等信息.其中位置信息通過位置管理模塊獲取，包括GPS或者基站定位方式獲取.服務(wù)器端包括用戶偏好管理、推薦商品管理和推薦處理3個(gè)模塊.用戶偏好管理模塊是通過獲取用戶的個(gè)人信息、購(gòu)買記錄、簽到記錄等數(shù)據(jù)，通過分類算法生成用戶偏好信息表;推薦商品管理模塊包括對(duì)商品進(jìn)行分類等進(jìn)行處理;推薦處理模塊采用協(xié)同推薦算法，首先通過評(píng)分趨勢(shì)函數(shù)對(duì)評(píng)分矩陣進(jìn)行處理并計(jì)算出目標(biāo)用戶的相似“鄰居”，然后通過相似“鄰居”對(duì)待推薦商品打分并根據(jù)位置信息對(duì)商品進(jìn)行處理，從推薦商品中找到TOP—N商品返回給目標(biāo)用戶.

圖1 系統(tǒng)架構(gòu)圖Fig.1 System architecture graph

1.1 數(shù)據(jù)處理

系統(tǒng)通過位置信息對(duì)商品和鄰居用戶集進(jìn)行過濾.服務(wù)器通過用戶的請(qǐng)求獲取用戶的位置信息，根據(jù)距離式(1)、(2)，從待推薦商品數(shù)據(jù)庫(kù)中獲取用戶周邊的待推薦商品集合I和用戶集R，通過用戶集合R查找用戶偏好數(shù)據(jù)庫(kù)形成用戶評(píng)分矩陣R(m，n).該矩陣表示不同用戶對(duì)項(xiàng)目的評(píng)分，其中rij是用戶i對(duì)項(xiàng)目j的打分.

距離公式采用球面坐標(biāo)，(xa，ya)、(xb，yb)分別代表A、B兩個(gè)點(diǎn)的經(jīng)緯度，S代表兩個(gè)點(diǎn)的距離，式(3)把兩點(diǎn)之間的距離轉(zhuǎn)換到［0，1］區(qū)間(距離閾值為10 km)，方便計(jì)算.

1.2 商品評(píng)分

通過數(shù)據(jù)處理后獲得的用戶－項(xiàng)目R(m，n)評(píng)分矩陣，但是用戶在評(píng)分的時(shí)候往往會(huì)出現(xiàn)3種情況:積極用戶喜歡對(duì)購(gòu)買的商品打高分，只有特別糟糕的情況下才會(huì)打低分;消極用戶則對(duì)產(chǎn)品極為嚴(yán)格，除非很滿意不然往往會(huì)給出低分;有的用戶不管好壞都會(huì)給一個(gè)中等分?jǐn)?shù).從而導(dǎo)致評(píng)分矩陣偏差.本文通過計(jì)算用戶之間和項(xiàng)目之間的評(píng)分差異以及用戶評(píng)分趨勢(shì)，對(duì)評(píng)分矩陣進(jìn)行處理.其中通過式(4)、(5)計(jì)算用戶和項(xiàng)目評(píng)分的趨勢(shì)，判斷用戶和項(xiàng)目是消極還是積極評(píng)分，其中為用戶的平均評(píng)分，而是項(xiàng)目的平均評(píng)分.

當(dāng)φu與φi同時(shí)大于0時(shí)表明用戶偏向于積極評(píng)分，同時(shí)項(xiàng)目偏向于被積極評(píng)分.此時(shí)它們之間的評(píng)分取兩者之間的最低值.則它們之間的評(píng)分為

當(dāng)φu與φi同時(shí)小于0時(shí)表明用戶偏向于消極評(píng)分，而項(xiàng)目偏向于被消極評(píng)分.此時(shí)它們之間的評(píng)分取兩者之間的最低值.則它們之間的評(píng)分為

當(dāng)φu大于0而φi小于0時(shí)表明用戶偏向于積極評(píng)分而項(xiàng)目偏向于被消極品分，則它們之間的評(píng)分為

其β中為評(píng)分趨勢(shì)因子.

當(dāng)φu小于0而φi大于0時(shí)表明用戶趨向于消極評(píng)分而項(xiàng)目趨向于被積極評(píng)分，此時(shí)它們的評(píng)分值為

通過商品評(píng)分趨勢(shì)函數(shù)對(duì)R′(m，n)進(jìn)行處理，得到修正后的評(píng)分矩陣R′(m，n)，同時(shí)該方法解決了評(píng)分矩陣的稀疏問題，通過預(yù)測(cè)用戶的評(píng)分趨勢(shì)使得用戶某些沒有評(píng)分的商品頁(yè)也能夠得到一個(gè)較準(zhǔn)確的評(píng)分值.

通過該矩陣計(jì)算位置相鄰用戶與目標(biāo)用戶的相似度，求出目標(biāo)用戶最近“鄰居”，其中通過皮爾森公式(見式(10))計(jì)算相似度.式中Iuv表示用戶u與目標(biāo)用戶v共同評(píng)分的項(xiàng)目，Ru，c表示用戶對(duì)項(xiàng)目c的評(píng)分，表示用戶對(duì)所有項(xiàng)目的平均評(píng)分，Rv，c表示目標(biāo)用戶對(duì)項(xiàng)目c的評(píng)分，表示目標(biāo)用戶對(duì)所有項(xiàng)目的平均評(píng)分.

通過目標(biāo)用戶的最近鄰居評(píng)分矩陣，使用評(píng)分公式(11)對(duì)待推薦商品集I進(jìn)行評(píng)分，獲得鄰居用戶對(duì)待推薦商品的評(píng)分表.

1.3 距離衰減

傳統(tǒng)的移動(dòng)推薦算法只是通過用戶的位置信息獲取其周邊的服務(wù)進(jìn)行推薦，但其并沒有考慮距離的遠(yuǎn)近對(duì)用戶選擇的影響.Song［6-7］等指出個(gè)體總是頻繁地出現(xiàn)在某些特定的地點(diǎn)，位置上更靠近的用戶更容易產(chǎn)生相同的選擇.用戶選擇不同目標(biāo)的概率與距離成負(fù)相關(guān)［8－9］，隨著距離的擴(kuò)大，人與人之間的影響會(huì)減弱，人與推薦產(chǎn)品之間的交互強(qiáng)度也會(huì)減弱，用戶選擇該產(chǎn)品的概率會(huì)隨之降低.距離衰減函數(shù)f(d)以距離d為參數(shù)，目前最常用的距離衰減函數(shù)包括指數(shù)函數(shù)、冪函數(shù)以及高斯函數(shù)，3種衰減函數(shù)衰減關(guān)系如圖2所示.隨著用戶之間距離的增大，用戶之間的相關(guān)度會(huì)減弱.其中指數(shù)函數(shù)和冪函數(shù)衰減速度過快，導(dǎo)致通過距離對(duì)推薦集的影響過大，影響了生成推薦商品集的正確性.

圖2 距離衰減圖Fig.2 Distance decay graph

本文采用高斯型衰減函數(shù)，如式(12)所示，高斯衰減函數(shù)更能夠反映推薦系統(tǒng)中用戶對(duì)商品的選擇與距離之間的關(guān)系，其中α為衰減函數(shù)的衰減因子，衰減因子控制衰減函數(shù)的衰減速度.采用式(13)對(duì)待推薦商品的評(píng)分表進(jìn)行距離衰減，選擇評(píng)分超過預(yù)設(shè)閾值的TOP-N商品推薦給用戶.

2 應(yīng)用與分析

2.1 應(yīng)用數(shù)據(jù)的選取和算法度量標(biāo)準(zhǔn)

系統(tǒng)中的數(shù)據(jù)采集于Foursquare站點(diǎn)的簽到數(shù)據(jù)集，該數(shù)據(jù)集中包括大量的店鋪和商品以及位置信息、簽到記錄、用戶評(píng)論等大量信息.通過數(shù)據(jù)過濾提取出該站點(diǎn)2013年2月到2013年6月的簽到數(shù)據(jù)并刪除非活躍用戶的簽到信息(活躍用戶至少每個(gè)星期登錄一次)，得到908 675個(gè)用戶和41 037 532條簽到數(shù)據(jù).最后通過位置信息選取紐約、洛杉磯、芝加哥等城市提取出相應(yīng)的位置用戶的數(shù)據(jù).本文采用平均絕對(duì)誤差MAE、F1系數(shù)和排序分(rankscore)3個(gè)指標(biāo)來(lái)對(duì)算法進(jìn)行度量.

排序準(zhǔn)確度用于度量推薦算法產(chǎn)生的列表符合用戶對(duì)產(chǎn)品排序的程度［10-11］，考慮了推薦列表中的相對(duì)位置.Breese等提出排序分(rankscore)度量推薦系統(tǒng)的排序準(zhǔn)確度，排序分rankscore′u越小說(shuō)明用戶感興趣的在推薦列表中排在越靠前位置.定義如式(16)所示.

同時(shí)生成推薦集的平均時(shí)間是度量推薦算法復(fù)雜度的重要指標(biāo)，在商用推薦系統(tǒng)中如果產(chǎn)生推薦集所需的時(shí)間開銷大，不僅影響系統(tǒng)的性能，同時(shí)也降低了用戶體驗(yàn).通過時(shí)間度量標(biāo)準(zhǔn)更能體現(xiàn)推薦算法的效率.

2.2 商品推薦應(yīng)用

通過基于位置的商品推薦方法，本文建立了一個(gè)商品推薦系統(tǒng)應(yīng)用原型.系統(tǒng)采用Foursquare數(shù)據(jù)集，并采用N折交叉驗(yàn)證對(duì)數(shù)據(jù)集進(jìn)行劃分，其中3/4數(shù)據(jù)作為訓(xùn)練集，剩余1/4作為測(cè)試集.實(shí)驗(yàn)中采用多種推薦方法對(duì)不同城市的用戶進(jìn)行商品推薦并收集結(jié)果進(jìn)行分析，其中分別包括協(xié)同推薦、不修正矩陣協(xié)同推薦(基于距離衰減函數(shù)改進(jìn)的協(xié)同推薦)、SVD推薦、改進(jìn)SVD推薦和本文基于距離衰減和評(píng)分趨勢(shì)改進(jìn)的推薦算法.

2.3 推薦分析

距離衰減因子對(duì)本文推薦算法的影響分析.圖3表示距離衰減函數(shù)中衰減因子對(duì)排序分和MAE的影響.文獻(xiàn)指出對(duì)于個(gè)體在城市尺度的移動(dòng)，距離衰減系數(shù)在1.0～2.0之間［12-14］，系統(tǒng)中通過調(diào)整衰減因子的值產(chǎn)生不同商品推薦集推薦給用戶，當(dāng)衰減因子為1.5時(shí)本文算法排序分和MAE趨向于最小，推薦精準(zhǔn)度更高.

圖3 衰減因子與排序分、MAE關(guān)系圖Fig.3 The relationship between attenuation factor、ranking score and MAE standard diagram

在衰減因子取值為1.5后，系統(tǒng)分別采用了協(xié)同推薦(S0)、未修正矩陣推薦算法(S1)、SVD算法(S2)、改進(jìn)SVD算法(S3)和本文推薦算法(S4)對(duì)不同城市的用戶進(jìn)行商品推薦，并統(tǒng)計(jì)各算法的MAE、排序分、F1系數(shù)等數(shù)據(jù)如表1所示.從表中對(duì)比S1和S0可知通過距離衰減提高了協(xié)同推薦的準(zhǔn)確率;對(duì)比S4與S1可知本文修正矩陣進(jìn)一步提高了算法準(zhǔn)確度;對(duì)比S2、S3、S4可知本文算法與SVD、改進(jìn)SVD算法在MAE和F1指標(biāo)基本相同，但是通過距離衰減使得本文算法排序分高于SVD和改進(jìn)SVD算法.

表1 多個(gè)城市推薦算法評(píng)價(jià)Tab.1 Each city recommended algorithms evaluation

生成推薦集的平均時(shí)間是度量推薦算法復(fù)雜度的重要指標(biāo).實(shí)驗(yàn)中統(tǒng)計(jì)各個(gè)算法產(chǎn)生推薦集的時(shí)間，并分析產(chǎn)生推薦集時(shí)間和用戶數(shù)量的關(guān)系，如圖4所示.隨著系統(tǒng)中用戶的增加，其中SVD算法的時(shí)間增長(zhǎng)是最快的，因?yàn)镾VD要對(duì)用戶矩陣進(jìn)行奇異值分解，用戶越多評(píng)分矩陣越大，其矩陣處理耗時(shí)越高;協(xié)同推薦算法隨著用戶的增加其評(píng)分矩陣也會(huì)增大，效率越來(lái)越低，當(dāng)用戶數(shù)量超過600時(shí)協(xié)同推薦算法的效率會(huì)低于本文推薦算法.本文推薦算法通過用戶評(píng)分趨勢(shì)對(duì)評(píng)分矩陣進(jìn)行修正，其效率高于通過矩陣奇異值分解的SVD算法，同時(shí)通過距離衰減使得評(píng)分矩陣減小而提高效率;而不修正矩陣推薦算法沒有對(duì)用戶矩陣進(jìn)行處理，但是其通過距離衰減使得其評(píng)分矩陣減小，其推薦效率是最高的.

圖4 各推薦算法效率圖Fig.4 Efficiency diagram of cornmend algortthms

3 結(jié)語(yǔ)

本文提出一種基于位置的商品推薦方法，并在此基礎(chǔ)上構(gòu)建了一個(gè)商品推薦應(yīng)用系統(tǒng).該推薦方法研究了位置對(duì)商品推薦的影響和用戶評(píng)分標(biāo)準(zhǔn)不同給推薦帶來(lái)的影響，引入基于距離衰減和評(píng)分趨勢(shì)改進(jìn)的協(xié)同推薦算法，提高了推薦商品的推薦準(zhǔn)確度和排序.同時(shí)根據(jù)到目的用戶的距離對(duì)“鄰居”用戶和商品進(jìn)行過濾，縮短了推薦商品集的產(chǎn)生時(shí)間，提高了系統(tǒng)的效率.

［1］余文喆，張蓉，王立.電子商務(wù)中的商品推薦系統(tǒng)［J］.華東師范大學(xué)學(xué)報(bào):自然科學(xué)版，2013(3):46-53.Yu W Z，Zhang R，Wang L.Recommendation in E-commerce［J］.Journal of East China Normal University:Nature Science Editiion，2013(3):46-53.

［2］孟祥武，胡勛，王立才，等.移動(dòng)推薦系統(tǒng)及其應(yīng)用［J］.軟件學(xué)報(bào)，2013，24(1):91-108.Meng X W，Hu X，Wang L C，et al.Mobile recommender systems and their applications［J］.Journal of Software，2013，24(1):91-108.

［3］Abowd G D，Atkeson C G，Hong J，et al.A mobile context-aware tour guide［J］.Wireless Networks，1997，3(5):421-433.

［4］Girardello A，Michahelles F.AppAware:which mobile applications are hot?［C］∥Proc of the Human Computer Interaction with Mobile Devices and Services(Mobile HCI 2010).Lisbon:ACM，2010:431-434.

［5］Yang W S，Cheng H C，Dia J B.A location-aware recommender system for mobile shopping environments［J］.Expert Systems with Applications，2008，34(1):437-455.

［6］Song C，Qu Z，Blum M N，et al.Limits of predict ability in human mobility［J］.Science，2010，327(5968):1018-1021.

［7］Song C，Koren T，Wang P，et al.Modeling the scaling properties of human mobility［J］.Nature Physics，2010，6(10):818-823.

［8］劉瑜，龔俐，童慶禧.空間交互作用中的距離影響及定量分析［J］.北京大學(xué)學(xué)報(bào):自然科學(xué)版，2014，50(3):526-534.Liu Y，Gong L，Tong Q X.Quantifying the distance effect in spatial interactions［J］.Acta Scientiarum Naturalium Universitaties PeKinensis，2014，50(3):526-534.

［9］袁書寒，陳維斌，傅順開.位置服務(wù)社交網(wǎng)絡(luò)用戶行為相似性分析［J］.計(jì)算機(jī)應(yīng)用，2012，32(2):322-325.Yuan S H，Chen W B，F(xiàn)u S K.User behavior similarity analysis of location based social network［J］.Journal of Computer Applications，2012，32(2):322-325.

［10］朱郁筱，呂琳媛.推薦系統(tǒng)評(píng)價(jià)指標(biāo)綜述［J］.電子科技大學(xué)學(xué)報(bào)，2012，41(2):163-175.Zhu Y X，Lü L Y.Evaluation metrics for recommender system［J］.Journal of University of Electronic Scienceand Technology of China，2012，41(2):163-175.

［11］劉建國(guó)，周濤，郭強(qiáng).個(gè)性化推薦系統(tǒng)評(píng)價(jià)方法綜述［J］.復(fù)雜系統(tǒng)與復(fù)雜性科學(xué)，2009，6(3):1-10.liu J G，Zhou T，Guo Q.Overview of the evaluated algorithms for the personal reconmendation systems［J］.Complex Systems and Complexity Science，2009，6(3):1-10.

［12］Liu Y，Kang C，Gao S，et al.Understanding intra-urban trip patterns from taxi trajectory data［J］.Journal of Geographical Systems，2012，14(4):463-483.

［13］Kang C，Ma X，Tong D，et al.Intra-urban human mobility patterns:An urban morphology perspective［J］.Physica A:Statistical Mechanics and its Applications，2012，391(4):1702-1717.

［14］Gao S，Wang Y，Gao Y，et al.Understanding urban traffic flow characteristics:a rethinking of between-ness centrality［J］.Environment and Planning B:Planning and Design，2013，40(1):135-153.