基于社會(huì)化網(wǎng)絡(luò)的長(zhǎng)期搭乘共享個(gè)性化推薦方法

仲秋雁 李岳陽(yáng) 初 翔

(大連理工大學(xué)管理與經(jīng)濟(jì)學(xué)部信息管理與信息技術(shù)研究所 遼寧 大連 116024)

基于社會(huì)化網(wǎng)絡(luò)的長(zhǎng)期搭乘共享個(gè)性化推薦方法

仲秋雁 李岳陽(yáng) 初 翔

(大連理工大學(xué)管理與經(jīng)濟(jì)學(xué)部信息管理與信息技術(shù)研究所 遼寧 大連 116024)

在汽車、住宿等服務(wù)行業(yè)中，與共享服務(wù)配套的個(gè)性化推薦方法的研究不足，降低了用戶體檢。以搭乘共享問題為例，考慮位置、社交、費(fèi)用三方面因素，提出URLP(Users Recommendation Based on LBSNs and Payment)方法為用戶推薦長(zhǎng)期合作對(duì)象。該方法首先基于用戶行為矩陣計(jì)算車主與乘客的位置相似度，其次通過歷史交易數(shù)據(jù)學(xué)習(xí)建立基于位置的社交信任網(wǎng)絡(luò)，然后根據(jù)近期交易記錄擬合用戶的車費(fèi)偏好函數(shù)，最后綜合三類因素的影響自適應(yīng)地產(chǎn)生推薦列表。實(shí)驗(yàn)結(jié)果表明URLP方法具有良好的準(zhǔn)確率。雖然URLP方法以汽車共享為例提出，但方法同樣可被應(yīng)用于眾包快遞和配送等領(lǐng)域。

搭乘共享 個(gè)性化推薦 基于位置的社會(huì)化網(wǎng)絡(luò) TF-IDF

0 引 言

Uber和Airbnb兩家公司的崛起，讓其共性商業(yè)模式——共享經(jīng)濟(jì)成為全球最熱商業(yè)模式。共享經(jīng)濟(jì)指民眾公平、有償?shù)墓蚕硪磺猩鐣?huì)資源，彼此以不同的方式付出和受益，共同享受經(jīng)濟(jì)紅利[1]。拼車是目前一種典型的空車資源有償共享模式，指私家小汽車駕駛?cè)伺c其他人共乘出行，通過減少小汽車空座率達(dá)到減少小汽車出行量和道路需求等目的的集體行為[2]。類似的商業(yè)模式還有眾包快遞，被稱為“快遞版”Uber。搭乘共享平臺(tái)迅速發(fā)展，但是與平臺(tái)配合的推薦系統(tǒng)卻剛剛起步，相關(guān)研究也較少。本文以上班族通勤拼車為例，以基于位置的社會(huì)化網(wǎng)絡(luò)LBSNs(Location-based Social Networks )為推薦框架，提出一種適合長(zhǎng)期搭乘共享問題的個(gè)性化推薦方法——URLP方法。

對(duì)于拼車問題，很多學(xué)者采用數(shù)學(xué)分析的方式研究用戶最佳拼車策略。Friginal等認(rèn)為在個(gè)人與個(gè)人的拼車過程中會(huì)應(yīng)用到以下三中技術(shù)：談判機(jī)制、談判平臺(tái)和社交網(wǎng)絡(luò)[3]。Boukhater和Huang把拼車路線選擇作為一種組合優(yōu)化問題，根據(jù)自定義的適應(yīng)度函數(shù)，用遺傳算法為用戶尋找拼車路線最短的最優(yōu)拼車方案[4-5]。Knapen和Hartman研究長(zhǎng)期需求的拼車問題，建立拼車用戶選擇的圖論模型，其中Hartman用真實(shí)數(shù)據(jù)驗(yàn)證了其模型的有效性[6-7]。采用數(shù)學(xué)方法建模對(duì)以后的研究有很大借鑒作用，但大部分模型都只考慮位置遠(yuǎn)近對(duì)于用戶選擇的影響，模型過于理想，離實(shí)際應(yīng)用有一定距離。拼車用戶選擇問題的另一種研究方式是仿真方法。在圖論模型基礎(chǔ)上，Hussain和Knapen選擇不同“談判機(jī)制”，計(jì)算機(jī)仿真觀察不同機(jī)制下用戶行為[8-9]。Galland建立基于Agent的交流模型，用Agent檔案文件和社交網(wǎng)絡(luò)開始交流模型進(jìn)行仿真，最后用Flanders 的真實(shí)數(shù)據(jù)驗(yàn)證模型的有效性[10]。仿真研究可以在無法大規(guī)模實(shí)體演示的情況下，模擬現(xiàn)實(shí)情景，得出科學(xué)結(jié)論，但往往忽視了個(gè)體的差異性，現(xiàn)實(shí)生活中每個(gè)用戶對(duì)于拼車對(duì)象的選擇會(huì)因?yàn)閭€(gè)人社會(huì)背景、習(xí)慣等而大相徑庭。因此，有必要根據(jù)不同用戶特點(diǎn)，為其推薦不同對(duì)象進(jìn)行搭乘。

目前，LBSNs推薦框架流行于各種基于位置服務(wù)的研究。LBSNs是一種把地理位置信息作為一種新動(dòng)態(tài)的社交網(wǎng)絡(luò)[11]，它不僅意味著把地理位置信息附加到已經(jīng)存在的社交網(wǎng)絡(luò)中，也可能是由地理位置較近的人群組成的社交圈構(gòu)成的新的網(wǎng)絡(luò)結(jié)構(gòu)[12]。LBSNs中群體行為的研究已經(jīng)獲得例如智能交通系統(tǒng)、推薦系統(tǒng)等領(lǐng)域的關(guān)注[13]?；贚BSNs推薦的一個(gè)特點(diǎn)是推薦對(duì)象的“位置關(guān)聯(lián)性”[14]。Zheng和Liao把用戶到過某位置的次數(shù)作為該用戶對(duì)該位置的隱性評(píng)分，尋找近鄰用戶，從而為用戶推薦位置相近的朋友[15-16]，Griesner等通過矩陣分塊算法考慮上下文為用戶做出個(gè)性化的地點(diǎn)推薦[17]。對(duì)于LBSNs推薦中的冷啟動(dòng)問題，Gao等根據(jù)距離和社交關(guān)系把用戶分為四類改進(jìn)樸素貝葉斯方法來預(yù)測(cè)用戶出現(xiàn)在某位置的“可能性”，緩解了一般位置推薦中初始數(shù)據(jù)稀疏的問題[18]。已有的基于LBSNs推薦框架的研究在計(jì)算位置相似度時(shí)并不直接考慮兩個(gè)位置的經(jīng)緯度，大都采用改進(jìn)協(xié)同過濾算法、樸素貝葉斯方法等間接方式處理。在搭乘共享問題中，位置作為用戶偏好而不是被推薦項(xiàng)目，因此對(duì)多樣性要求低對(duì)準(zhǔn)確度要求高，需要直接處理位置數(shù)據(jù)，上述方法并不適用?；谝陨戏治觯疚倪x擇改進(jìn)基于內(nèi)容的推薦算法計(jì)算用戶位置相似度。

1 問題界定

通勤拼車用戶有兩個(gè)特點(diǎn)：有長(zhǎng)期拼車需求，拼車時(shí)間地點(diǎn)相對(duì)固定。因此，通過用戶歷史拼車記錄學(xué)習(xí)其偏好并做出推薦是可行的。拼車過程中，很多軟件是由需要拼車的乘客發(fā)布拼車需求，車主搶單，所以本文站在車主的角度，為車主推薦合適的拼車乘客。當(dāng)然，稍作調(diào)整后該方法也可以為乘客推薦合適的車主。本文選取位置、社交、車費(fèi)補(bǔ)貼進(jìn)行用戶偏好學(xué)習(xí)理由如下：

(1) 拼車過程中不論是車主或者乘客最關(guān)心的都是在自己計(jì)劃出行的時(shí)間內(nèi)，路線的匹配程度，越是“順路”,則車主和乘客拼車的可能性越大。故選取帶有時(shí)間參數(shù)的位置作為用戶偏好進(jìn)行學(xué)習(xí)。

(2) 由于上班族拼車為長(zhǎng)期需求，故在拼車過程中，車主和乘客會(huì)建立一種基于地理位置的“朋友”關(guān)系，甚至可能其中就有原來本就認(rèn)識(shí)的鄰居或同事。一位車主可能和與他上下班順路的多位乘客拼車，一位乘客也可能和多位車主拼車，則在某一地區(qū)會(huì)建立起一種隱性社交圈，本文認(rèn)為這是一種基于地理位置的社交網(wǎng)絡(luò)。社交會(huì)建立一種信任關(guān)系，從而影響用戶的行為。故選擇社交作為用戶偏好進(jìn)行學(xué)習(xí)。

(3) 現(xiàn)行拼車車費(fèi)由兩部分組成，油費(fèi)和車費(fèi)補(bǔ)貼。其中油費(fèi)paykm根據(jù)里程數(shù)決定，每次拼車油費(fèi)自動(dòng)計(jì)算，而車費(fèi)補(bǔ)貼Δsubsidy相對(duì)靈活，即pay=paykm+Δsubsidy。乘客不同，相同的里程，車主可能得到不同的車費(fèi)補(bǔ)貼?，F(xiàn)實(shí)拼車中，有的車主只愿意搭載同路的乘客，有的車主卻愿意為了更多的補(bǔ)貼而繞路，這會(huì)很大程度影響推薦結(jié)果。故本文只考慮會(huì)因?yàn)榻灰讉€(gè)人不同而不同的補(bǔ)貼部分，選擇其作為用戶偏好進(jìn)行學(xué)習(xí)。

2 URLP方法提出

2.1URLP基本框架

如圖1所示，首先由用戶信息和交易記錄抽取用戶-費(fèi)用、用戶-位置、用戶-用戶矩陣。根據(jù)用戶-費(fèi)用、用戶-位置矩陣，可以建立車主(car)、位置與時(shí)間(p,t)、乘客(pas)關(guān)系，其中車主和乘客統(tǒng)稱為用戶。每個(gè)用戶有一個(gè)費(fèi)用記錄(pay)，即乘客付出過的車費(fèi)或車主得到的車費(fèi)。根據(jù)用戶-用戶矩陣及上述用戶與位置、時(shí)間關(guān)系，可以建立一個(gè)基于位置的社會(huì)化網(wǎng)絡(luò)。最后根據(jù)用戶-位置-時(shí)間-費(fèi)用關(guān)系及基于位置的社會(huì)化網(wǎng)絡(luò)，計(jì)算用戶間位置相似度、信任值、費(fèi)用偏好度，應(yīng)用自適應(yīng)方法調(diào)節(jié)三部分比重，產(chǎn)生推薦列表。

圖1 研究框架

2.2 符號(hào)描述

由于拼車的車主和乘客的數(shù)據(jù)集的組成相同，故把車主和乘客統(tǒng)稱為用戶。對(duì)車主出行路線的描述采用化線為點(diǎn)的方式，由起點(diǎn)每隔x(x根據(jù)具體實(shí)例及推薦精度要求選取)米選取一點(diǎn)，直至終點(diǎn)，則車主的路線化為位置點(diǎn)集。對(duì)于乘客的路線，由于乘客較為關(guān)注的是在什么地點(diǎn)上車和在什么地點(diǎn)下車，故只選取起點(diǎn)和終點(diǎn)作為其位置點(diǎn)集。對(duì)時(shí)間的處理，每隔y(y根據(jù)具體實(shí)例及推薦精度要求選取)分鐘化為一組，則每個(gè)位置點(diǎn)對(duì)應(yīng)一個(gè)時(shí)間分組。

例如，已知車主路線和乘客路線，假設(shè)x取500，y取30。對(duì)于車主路線，由起始點(diǎn)p0、出發(fā)時(shí)間t0開始，每隔500米記錄一點(diǎn)(pi,ti)，pi用經(jīng)緯度表示，ti為經(jīng)過pi的時(shí)間點(diǎn)，對(duì)應(yīng)屬于某一時(shí)間分組。例如：一點(diǎn)((121.540 143,38.873 345),0725)，其中前一項(xiàng)表示一點(diǎn)東經(jīng)121.540 143度，北緯38.873 345度，0725表示7:25。假設(shè)0725對(duì)應(yīng)時(shí)間分組2 (7:00-7:30)，則該點(diǎn)數(shù)據(jù)可被表示為((121.540 143,38.873 345),2)。

同理處理乘客路線，不同之處是乘客位置只記錄起始點(diǎn)和終點(diǎn)。用上述方法處理路線數(shù)據(jù)，然后就可以根據(jù)位置點(diǎn)集進(jìn)行位置相似度計(jì)算，具體計(jì)算步驟見2.3.1節(jié)。

2.2.1 符號(hào)表示

URLP方法中使用的符號(hào)含義如表1所示。

表1 符號(hào)及含義

2.2.2 集合定義

定義1 對(duì)于用戶k的每次出行，其路線Rk都可以用位置和時(shí)間表示：

Rk=(Pk,Tk)

(1)

其中，Pk表示用戶k有近期出行記錄的位置點(diǎn)的集合，Tk表示Pk中各位置點(diǎn)對(duì)應(yīng)的各時(shí)間段。

定義2 用戶位置與時(shí)間屬性用集合U表示，用戶分為車主和乘客，Uo為車主屬性集合，Up為乘客屬性集合。則用戶k的屬性可以表示為：

Uk=(IDk,Rk)

(2)

定義3 根據(jù)用戶k最近拼車記錄，為曾與用戶有過拼車出行的其他用戶集合Fk表示為：

Fk=(ID,times)

(3)

其中，ID為與用戶k有過拼車記錄的其他用戶編號(hào)集合，times為該集合中用戶與用戶k對(duì)應(yīng)的拼車次數(shù)。

定義4 根據(jù)用戶k最近拼車記錄，為用戶收到或付出車費(fèi)補(bǔ)貼數(shù)的集合Mk表示為：

Mk=(pay,times)

(4)

其中，pay為用戶付出或得到的車費(fèi)補(bǔ)貼數(shù)的集合，times為該集合中對(duì)應(yīng)車費(fèi)補(bǔ)貼數(shù)在最近歷史記錄中出現(xiàn)的次數(shù)。

2.3URLP方法實(shí)現(xiàn)

2.3.1 位置區(qū)域劃分

URLP方法針對(duì)長(zhǎng)期短途用戶做出推薦，故相似度高的用戶必然位于同一區(qū)域。為了降低方法復(fù)雜度，首先根據(jù)要為之推薦的那名車主的位置，劃分一個(gè)適當(dāng)大小區(qū)域，抽取該區(qū)域所有乘客數(shù)據(jù)進(jìn)行推薦。也就是說，每為一名車主推薦都根據(jù)該車主位置進(jìn)行一次用戶群劃分。具體區(qū)域劃分規(guī)則需要根據(jù)城市大小、交通狀況等做具體分析。例如，為大連市某區(qū)車主A推薦時(shí)，根據(jù)大連市大小、交通狀況，可以以A常簽到位置連線為中心線東西各擴(kuò)充2 km，選擇常簽到位置在這個(gè)區(qū)域的乘客作為待選用戶進(jìn)行下步計(jì)算。在以下步驟中認(rèn)為用戶?；顒?dòng)區(qū)域相同，為具有上下班拼車可能的潛在用戶群。

2.3.2 基于位置的相似度計(jì)算

步驟2 根據(jù)文本挖掘中提取文章關(guān)鍵詞的技術(shù)TF-IDF方法處理用戶k的路線集合R。

(5)

(6)

(7)

步驟3 對(duì)于經(jīng)過TF-IDF技術(shù)處理過的用戶屬性集合Uk=(IDk,Rk)，其中：

Rk=(pk1,pk2,…,pki,…,pkn)

(8)

(9)

(10)

(11)

步驟4 對(duì)用戶k位置向量Rk進(jìn)行標(biāo)準(zhǔn)化處理：

(12)

步驟5 根據(jù)文獻(xiàn)[19]中證明的基于位置的相似度算法，基于本模型特點(diǎn)進(jìn)行修改后，車主x與乘客y基于位置的相似度：

(13)

2.3.3 基于用戶間隱性社交網(wǎng)絡(luò)的信任值計(jì)算

車主與乘客進(jìn)行一次拼車，相當(dāng)于進(jìn)行了一次“交流”或者“合作”，從而建立一種隱性社交圈?！昂献鳌贝螖?shù)多的用戶間會(huì)更加熟悉，對(duì)于各自習(xí)慣、守時(shí)程度等都有較好適應(yīng)性，從而建立一種信任關(guān)系。根據(jù)最近歷史記錄中用戶的拼車記錄，建立用戶間社交網(wǎng)絡(luò)，為車主個(gè)性化推薦“合作”次數(shù)多的乘客可以提高推薦的滿意度。特別注意，這里的歷史記錄時(shí)間為近期(具體時(shí)間段根據(jù)具體實(shí)例選取)，因?yàn)橛脩糸g的信任可能隨著時(shí)間發(fā)生轉(zhuǎn)移。本文用戶社交網(wǎng)絡(luò)為一個(gè)稀疏的無向非加權(quán)網(wǎng)絡(luò)，且包含多個(gè)連通子網(wǎng)，但不考慮“朋友”的“朋友”這種間接關(guān)系對(duì)于推薦的影響?？紤]到僅有過一次“合作”的用戶間可能不存在這種信任。僅有的一次“合作”可能為偶然且相互并不滿意，所以沒有出現(xiàn)第二次“合作”。在數(shù)據(jù)預(yù)處理時(shí)將所有大于0的“合作”次數(shù)減1。在計(jì)算用戶的相似性時(shí)，為凸顯“合作”次數(shù)的影響，本文使用了平方根函數(shù)來處理使其值在[0,1]區(qū)間，常見的處理函數(shù)還有指數(shù)函數(shù)、線性函數(shù)和對(duì)數(shù)函數(shù)等。這里我們不給予詳述，可參考文獻(xiàn)[20]。則用戶x與用戶y的信任值為：

(14)

其中，timesxy車主x和乘客y的近期合作次數(shù)。

2.3.4 用戶關(guān)于車費(fèi)補(bǔ)貼偏好的計(jì)算

另一個(gè)對(duì)于拼車出行有影響的是車費(fèi)補(bǔ)貼多少。有的車主愿意免費(fèi)搭載順路的乘客，有的車主卻愿意為了獲得較高的車費(fèi)補(bǔ)貼而繞路。因此，為了提高推薦滿意度，需要根據(jù)車主近期記錄中對(duì)于車費(fèi)補(bǔ)貼多少的偏好來決定為車主推薦哪些乘客。根據(jù)邊際效益遞減原則[21]，可以選取或根據(jù)歷史數(shù)據(jù)擬合合適函數(shù)，描述用戶對(duì)于車費(fèi)補(bǔ)貼的偏好。用戶對(duì)于車費(fèi)補(bǔ)貼多少的偏好值MP可表示為：

(15)

2.3.5 自適應(yīng)產(chǎn)生推薦列表

總相似度的計(jì)算綜合了位置、社交、車費(fèi)補(bǔ)貼對(duì)用戶行為的影響：

(16)

3 實(shí)驗(yàn)與結(jié)果分析

3.1 實(shí)驗(yàn)數(shù)據(jù)

本文實(shí)驗(yàn)數(shù)據(jù)來自志愿者，數(shù)據(jù)分為GPS數(shù)據(jù)和拼車數(shù)據(jù)兩部分。數(shù)據(jù)預(yù)處理時(shí)需根據(jù)車主位置劃分合適大小區(qū)域，選取該地區(qū)所有乘客作為備選，整理車主和該區(qū)域乘客路線及交易數(shù)據(jù)輸入U(xiǎn)RLP方法，最后形成推薦。則實(shí)驗(yàn)應(yīng)該選擇一個(gè)固定區(qū)域。本文實(shí)驗(yàn)選擇大連市白領(lǐng)較多的某區(qū)。在該地區(qū)選擇100名拼車軟件常用用戶(10名車主，90名乘客)，使用Google開發(fā)的手機(jī)軟件My Tracks記錄其60個(gè)工作日上下班時(shí)間段(6∶30-8∶30與16∶30-19∶30)GPS記錄，該部分記錄用于進(jìn)行路線匹配，計(jì)算用戶間關(guān)于位置的相似度。整理志愿者手機(jī)上實(shí)驗(yàn)期間，上下班時(shí)段拼車記錄，用于挖掘用戶間社交關(guān)系及對(duì)車費(fèi)補(bǔ)貼偏好。

3.2 評(píng)價(jià)標(biāo)準(zhǔn)

本文推薦列表的形成采用推薦系統(tǒng)常用的Top-N方法[22]。實(shí)驗(yàn)中按 80∶20 的比例將用戶拼車數(shù)據(jù)隨機(jī)地分為訓(xùn)練集和測(cè)試集。用訓(xùn)練集中數(shù)據(jù)學(xué)習(xí)用戶偏好做出推薦，如果測(cè)試集中車主與推薦列表中任一乘客有過拼車記錄，認(rèn)為推薦成功。為了確定URLP方法中最佳?值并評(píng)價(jià)該方法，本文使用了對(duì)于推薦列表順序敏感的平均準(zhǔn)確率MAP(Mean Average Precision)和平均排序倒數(shù)MRR(Mean Reciprocal Rank)兩個(gè)評(píng)價(jià)指標(biāo)；為了將URLP方法與傳統(tǒng)協(xié)同過濾推薦算法對(duì)比，使用了對(duì)列表長(zhǎng)度敏感的準(zhǔn)確率(Precision)評(píng)價(jià)指標(biāo)。

3.2.1 平均排序倒數(shù)

(17)

其中，rankij表示為第i位車主推薦時(shí)推薦成功的排位為j，M為需要為之推薦的車主數(shù)量，N為推薦列表長(zhǎng)度。

3.2.2 準(zhǔn)確率與平均準(zhǔn)確率

準(zhǔn)確率衡量推薦的乘客有多少是準(zhǔn)確的，即被車主接受的，用來衡量推薦的整體質(zhì)量。平均準(zhǔn)確率MAP是每個(gè)相關(guān)文檔被檢索后準(zhǔn)確率的平均值的算術(shù)平均值[23]。當(dāng)我們給車主x推薦拼車乘客，那么推薦列表最前面的最好應(yīng)該是正確的推測(cè)。因此，我們使用MAP去強(qiáng)調(diào)高排名的相關(guān)用戶。對(duì)于一個(gè)測(cè)試集，令R(i)是根據(jù)訓(xùn)練集數(shù)據(jù)為車主做出的推薦列表，T(i)是車主在測(cè)試集上的行為列表。準(zhǔn)確率Precision：

(18)

平均準(zhǔn)確率MAP：

(19)

其中，M為需要為之推薦的車主數(shù)量，ri表示為車主i推薦的乘客中被接納的數(shù)量，Precisioni@k是車主i的推薦列表中排名為k的乘客的準(zhǔn)確率。

3.3 實(shí)驗(yàn)步驟及結(jié)果分析

首先，我們根據(jù)收集的用戶手機(jī)端數(shù)據(jù)，分析用戶每天上班時(shí)間與下班時(shí)間。當(dāng)每天早晨，用戶位置發(fā)生較大位移開始記為其出發(fā)時(shí)間，每天下午，用戶位置發(fā)生較大位移為其回家時(shí)間。選取其中一天，繪成散點(diǎn)圖如圖2所示。

圖2 用戶每日上下班時(shí)間

由圖2可以發(fā)現(xiàn)，用戶早晨出行時(shí)間集中在6：30-8：30，下午出行時(shí)間集中在16：30-19：30。符合上班族拼車時(shí)間段較固定的預(yù)想。

為了測(cè)試URLP方法的有效性，實(shí)驗(yàn)前提出三個(gè)問題：

Q1：URLP方法中，?如何影響推薦準(zhǔn)確度？

Q2：如果僅考慮位置或者僅考慮社交和車費(fèi)補(bǔ)貼，推薦效果如何？

Q3：針對(duì)以拼車為典型的資源共享平臺(tái)中的用戶推薦問題，與傳統(tǒng)協(xié)同過濾算法相比，URLP方法是否更加有效？

對(duì)于Q1，首先取推薦列表長(zhǎng)度N=10，計(jì)算不同?取值下MRR、MAP值。

圖3 ?對(duì)MRR、MAP的影響

由圖3可以看出，當(dāng)?=0時(shí)，MAP和MRR的值都較小，這說明當(dāng)僅考慮社交和車費(fèi)補(bǔ)貼時(shí)推薦效果不好；當(dāng)0≤?≤0.2，隨著?值增大，推薦結(jié)果的準(zhǔn)確度大幅度提高，說明車主是否接受推薦的乘客與出行路線匹配度有關(guān)；當(dāng)?=0.7時(shí)，MAP和MRR取得最大值，推薦準(zhǔn)確度最佳；當(dāng)0.7≤?≤1，隨著?值增大，MAP和MRR值減小，說明僅僅推薦出行路線匹配度高的乘客推薦效果也不好，這可能是由于有的乘客與車主雖然路線匹配度高，但是由于性別、社會(huì)背景、車費(fèi)補(bǔ)貼等原因車主并不愿意與之拼車。當(dāng)考慮社交因素時(shí)，有過多次拼車的車主和乘客，即社交關(guān)系緊密的用戶間，在性別、社會(huì)背景等隱性影響拼車的方面上可以互相包容，更容易再次拼車。綜上，首先可以確定在URLP方法中當(dāng)?=0.7時(shí)推薦效果最佳，其次可以初步確定考慮位置、社交、車費(fèi)補(bǔ)貼作為用戶偏好進(jìn)行學(xué)習(xí)是必要的。

對(duì)于Q2，分別取推薦列表長(zhǎng)度N為5、10、15、…、30，對(duì)比測(cè)試集計(jì)算推薦準(zhǔn)確率，考慮下列三種情況：①僅考慮位置，即取?=1；②僅考慮社交和車費(fèi)補(bǔ)貼，即取?=0；③URLP方法，考慮位置、社交和車費(fèi)補(bǔ)貼三個(gè)因素，取?=0.7。

由圖4、圖5可以看出，URLP方法準(zhǔn)確率和召回率最高。當(dāng)僅考慮位置時(shí)，即僅僅考慮路線的匹配程度，由于上述的用戶的性別、社會(huì)背景等復(fù)雜不可量化因素的影響，推薦效果并不好。這是本文提出考慮其他兩個(gè)因素的原因。當(dāng)僅考慮社交和車費(fèi)補(bǔ)貼時(shí)，受到拼車記錄中非上班拼車記錄的等原因的影響，推薦準(zhǔn)確率比較低。我們收集的拼車記錄僅僅為上下班時(shí)間段的拼車記錄，但該時(shí)段也可能存在非上下班拼車，例如：根據(jù)車主歷史拼車記錄，在上班時(shí)段車主位置變化為由A到B，某日車主可能住在C地，則第二日其可能偶然進(jìn)行了一次由C到B的拼車；車主也可能偶然進(jìn)行了一次繞路較多的拼車。在僅考慮社交和車費(fèi)補(bǔ)貼時(shí)，這種數(shù)據(jù)將大大降低推薦的準(zhǔn)確率。本文的目的是為上下班車主推薦順路拼車乘客，當(dāng)僅考慮社交和車費(fèi)補(bǔ)貼時(shí)，為了達(dá)到該目的，就需要排除干擾數(shù)據(jù)，故需要考慮位置因素。

對(duì)于Q3，采用常見的用社交網(wǎng)絡(luò)改進(jìn)協(xié)同過濾算法的方法TCF(Traditional Collaborative Filtering)，認(rèn)為與同一乘客有過拼車記錄的車主為鄰近用戶，且拼車次數(shù)越多用戶相似度越高，分別取推薦列表長(zhǎng)度N為5、10、15、…、30對(duì)比測(cè)試集計(jì)算準(zhǔn)確率。

圖4 不同因素對(duì)準(zhǔn)確率影響

圖5 不同因素對(duì)召回率的影響

如圖4、圖5所示，考慮社交因素的協(xié)同過濾方法推薦準(zhǔn)確度比URLP方法差，但在推薦列表長(zhǎng)度5≤N≤20時(shí)準(zhǔn)確度高于僅考慮位置或者僅考慮社交和車費(fèi)補(bǔ)貼；當(dāng)推薦列表長(zhǎng)度繼續(xù)增加時(shí)，協(xié)同過濾方法準(zhǔn)確度下降速率加快，說明列表增加的推薦多為無效推薦，僅僅用社交衡量用戶間相似度不夠準(zhǔn)確。URLP方法召回率最高，TCF方法與僅考慮位置時(shí)召回率曲線接近，說明考慮社交和費(fèi)用因素有助于提高推薦列表中被用戶接受的推薦結(jié)果個(gè)數(shù)，傳統(tǒng)協(xié)同過濾針對(duì)長(zhǎng)期拼車問題適應(yīng)性較差。URLP方法考慮因素比TCF方法更多，推薦準(zhǔn)確率更高，也證明了考慮社交和費(fèi)用的有效性。針對(duì)拼車用戶推薦問題，如果想使用協(xié)同過濾方法需要考慮更多因素，有待研究者用更好方式改進(jìn)傳統(tǒng)協(xié)同過濾算法。

圖6 不同推薦位置推薦成功率

圖6為N取不同值時(shí)，推薦列表中不同位置推薦結(jié)果的接受比例。即：所有推薦表中排名第N(N=1,2,…,5)的推薦結(jié)果，與測(cè)試集對(duì)比，成功的結(jié)果占推薦列表個(gè)數(shù)的比例，某位置柱狀圖缺失是因?yàn)樵撐恢脹]有被用戶接受的結(jié)果。分析圖6可以發(fā)現(xiàn)，列表中第一個(gè)推薦結(jié)果的接收比例最高，第二個(gè)結(jié)果其次。進(jìn)一步證明了本文URLP方法對(duì)推薦結(jié)果的排名是有效的——高排名的推薦結(jié)果接受率更高。

4 結(jié) 語(yǔ)

本文針對(duì)搭乘共享中的長(zhǎng)期需求，提出一種考慮用戶位置、社交、費(fèi)用三個(gè)偏好的個(gè)性化推薦方法，該方法可以根據(jù)用戶不同，自適應(yīng)改變?nèi)齻€(gè)因素權(quán)重，從而更好地作出推薦。通過對(duì)60個(gè)工作日通勤拼車用戶的追蹤獲得數(shù)據(jù)，用實(shí)驗(yàn)驗(yàn)證了該推薦方法的有效性。這種推薦方法的提出，豐富了LBSNs推薦框架中路線相似度的計(jì)算方法，同時(shí)，對(duì)于拼車、眾包快遞等問題中信息過載問題的解決具有較大現(xiàn)實(shí)意義。

本文只是該研究的一小部分結(jié)果。首先對(duì)于本文選取的會(huì)影響用戶行為的因素只是較重要的三個(gè)，其他因素例如用戶完成訂單數(shù)量、其他用戶評(píng)價(jià)等都可能產(chǎn)生影響。如何更合理篩選影響因素、如何學(xué)習(xí)量化篩選出的因素等都是下一步需要解決的問題。其次對(duì)于本文已經(jīng)選擇的三個(gè)因素，如何更準(zhǔn)確模型化也需要進(jìn)一步研究。例如，如何更準(zhǔn)確計(jì)算路線間相似度。

[1] 蔡余杰，黃祿金. 共享經(jīng)濟(jì)[M]. 北京：企業(yè)管理出版社, 2015: 1-15.

[2] 王茂福. 拼車的發(fā)展及其效應(yīng)[J]. 中國(guó)軟科學(xué), 2010(11): 54-61.

[3] Friginal J, Gambs S, Guiochet J, et al. Towards privacy-driven design of a dynamic carpooling system[J]. Pervasive and Mobile Computing, 2014, 14: 71-82.

[4] Boukhater C M, Dakroub O, Lahoud F, et al. An Intelligent and Fair GA Carpooling Scheduler as a Social Solution for Greener Transportation[C]//2014 17th IEEE Mediterranean Electrotechnical Conference (MELECON), 2014: 182-186.

[5] Huang S c, Jiau M K, Lin C H. A Genetic-Algorithm-Based Approach to Solve Carpool Service Problems in Cloud Computing[J]. IEEE Transactions on Intelligent Transportation Systems, 2015, 16(1): 352-364.

[6] Knapen L, Yasar A, Cho S, et al. Exploiting graph-theoretic tools for matching in carpooling applications[J]. Journal of Ambient Intelligence and Humanized Computing, 2014, 5(3): 393-407.

[7] Hartman I B A, Keren D, Dbai A A, et al. Theory and Practice in Large Carpooling Problems[J]. Procedia Computer Science, 2014, 32: 339-347.

[8] Hussain I, Knapen L, Galland S, et al. Organizational and Agent-based Automated Negotiation Model for Carpooling[J]. Procedia Computer Science, 2014, 37: 396-403.

[9]KnapenL,HartmanIBA,KerenD,etal.Scalabilityissuesinoptimalassignmentforcarpooling[J].JournalofComputerandSystemSciences, 2015, 81(3): 568-584.

[10]GallandS,KnapenL,YasarAUH,etal.Multi-agentsimulationofindividualmobilitybehaviorincarpooling[J].TransportationResearchPartC:EmergingTechnologies, 2014, 45: 83-98.

[11]QuerciaD,LathiaN,CalabreseF,etal.RecommendingSocialEventsfromMobilePhoneLocationData[C]//2010IEEE10thInternationalConferenceonDataMining(ICDM), 2010: 971-976.

[12]ZhengY,ZhouX.ComputingwithSpatialTrajectories[M].NewYork:Springer, 2011: 63-107.

[13]YangD,ZhangD,ChenL,etal.NationTelescope:Monitoringandvisualizinglarge-scalecollectivebehaviorinLBSNs[J].JournalofNetworkandComputerApplications, 2015, 55: 170-180.

[14]BaoJ,ZhengY,WilkieD,etal.Recommendationsinlocation-basedsocialnetworks:asurvey[J].GeoInformatica, 2015, 19(3): 525-565.

[15]ZhengY,ZhangL,MaZ,etal.Recommendingfriendsandlocationsbasedonindividuallocationhistory[J].ACMTransactionsontheWeb, 2011, 5(1): 1-47.

[16]LiaoHY,ChenKY,LiuDR.Virtualfriendrecommendationsinvirtualworlds[J].DecisionSupportSystems, 2015, 69: 59-69.

[17]GriesnerJB,AbdessalemT,NaackeH.POIRecommendation:TowardsFusedMatrixFactorizationwithGeographicalandTemporalInfluences[C]//Proceedingsofthe9thACMConferenceonRecommenderSystems, 2015: 301-304.

[18]GaoH,TangJ,LiuH.Addressingthecold-startprobleminlocationrecommendationusinggeo-socialcorrelations[J].DataMiningandKnowledgeDiscovery, 2015, 29(2): 299-323.

[19] 劉樹棟，孟祥武. 一種基于移動(dòng)用戶位置的網(wǎng)絡(luò)服務(wù)推薦方法[J]. 軟件學(xué)報(bào), 2014, 25(11): 2556-2574.

[20] 何鵬，李兵，楊習(xí)輝，等.Roster：一種開發(fā)者潛在同行推薦方法[J]. 計(jì)算機(jī)學(xué)報(bào), 2014, 37(4): 859-872.

[21]RollinsK,LykeA.TheCaseforDiminishingMarginalExistenceValues[J].JournalofEnvironmentalEconomicsandManagement, 1998, 36(3): 324-344.

[22]DeshpandeM,KarypisG.Item-BasedTop-NRecommendationAlgorithms[J].ACMTransactionsonInformationSystems, 2004, 22(1): 143-177.

[23]CraswellN.MeanReciprocalRank[M].NewYork:SpringerUS, 2009: 1664-1876.

PERSONALIZED RECOMMENDATION METHOD OF LONG-DISTANCE CAR SHARING BASED ON SOCIAL NETWORK

Zhong Qiuyan Li Yueyang Chu Xiang

(InstituteofInformationManagementandInformationTechnology,FacultyofManagementandEconomics,DalianUniversityofTechnology,Dalian116024,Liaoning,China)

In the service industry such as automobile, lodging and so on, the personalized recommendation method with the sharing service is insufficient, which reduces the user’s physical examination. In this paper, take the sharing problem as an example, consider the location, social, cost three factors, proposed URLP method for the user to recommend long-term cooperation object. Firstly, the location similarity between the owner and the passenger is calculated based on the user behavior matrix. Secondly, the social network based on location is established through historical transaction data learning, and then fits the user’s fare preference function based on recent transaction records. Finally, the recommendation lists are generated adaptively according to the influence of three kinds of factors. Experimental results show that the URLP method has good accuracy. Although, URLP method to car sharing as an example, but the method can also be applied to crowdsourcing express and distribution and other fields.

Car sharing Personalized recommendation LBSNs TF-IDF

2016-02-04。國(guó)家自然科學(xué)基金重點(diǎn)項(xiàng)目(71533001)。仲秋雁，教授，主研領(lǐng)域：管理信息系統(tǒng)。李岳陽(yáng)，碩士生。初翔，博士生。

TP3

A

10.3969/j.issn.1000-386x.2017.04.045