基于上下文的道路推薦系統(tǒng)

□張 萌

( 山西財經大學 信息管理學院，山西 太原 030006)

基于上下文的道路推薦系統(tǒng)

□張 萌

( 山西財經大學 信息管理學院，山西 太原 030006)

隨著城市化建設高速發(fā)展，市區(qū)道路交通擁堵問題日益加劇，如何合理選擇合適的出行道路成為人們面臨的出行難題。利用上下文、移動網絡等信息為用戶進行實時道路推薦能夠緩解交通擁堵，減輕人們的出行壓力。

上下文；推薦系統(tǒng)；深度優(yōu)先搜索；交通出行

隨著城市經濟高速增長，特別是在較發(fā)達城市地區(qū)，交通的壓力越來越大。嚴重的交通堵塞問題，直接影響到城市經濟發(fā)展和居民出行，出行擁堵成為一個亟待解決的交通問題。以無線傳感網絡(Wireless sensor network)為基礎的智能交通系統(tǒng)(Intelligent transportation systems)成為交通管理的有效技術。由于其成本較低，易于安裝等特點，已經有許多WSN技術的研究者將其利用在交通測量領域，文獻[1]提出了一個利用無線傳感器網絡的交通安全測量模型。Liang[2]采用無線傳感器網絡來檢測交通流，實驗表明節(jié)點平均即檢測率達到90%。另一方面，許多研究者將傳感器安裝在車輛中，希望能得到更加精確的交通道路情況。

推薦系統(tǒng)[3]作為個性化服務[4,5]的重要研究領域,在電子商務領域和信息檢索方向已取得了成果，并被引入到移動應用、物聯(lián)網廣告等許多新興領域。文獻[6]中，Phanich等人提出了一種基于上下文的美食推薦系統(tǒng)，為用戶推薦適合的營養(yǎng)食品。Wang等人[7]提出了一個實時的道路推薦系統(tǒng)。而由于車流是不斷變化的，普通的線路推薦系統(tǒng)沒有考慮實時性問題，并不能緩解交通堵塞問題。為緩解交通壓力，Long L等人[8]提出了一種具有實時性個性化的自助游推薦系統(tǒng)。Meehan等人[9]提出了一種基于上下文感知的智能旅游混合推薦系統(tǒng)，為用戶提供良好的出行體驗。本文在現(xiàn)有的上下文推薦研究基礎上，利用WSN技術，提出一種基于上下文信息的實時道路推薦模型。

一、上下文感知推薦系統(tǒng)

自20世紀90年代上下文感知概念提出以來，至今“上下文”這一復雜概念還未有一個統(tǒng)一定義。Dey[10]將其定義為：用戶描述實體狀態(tài)的任何信息，其中實體包括人、地點等。而在上下文感知推薦系統(tǒng)中的“上下文”也未有一個統(tǒng)一的定義[11]，通常是結合實際的應用情景或者用戶需求完成合適的定義。

作為“普適計算”核心領域的上下文感知計算理論，自動發(fā)現(xiàn)和利用位置、環(huán)境等上下文信息為用戶提供服務等研究已經取得許多研究成果[12]。合理利用上下文環(huán)境(時間、位置、情緒等)為推薦系統(tǒng)提供更多用戶信息，能夠提高推薦質量和用戶滿意度。

一個完整的上下文感知推薦系統(tǒng)由以下幾部分組成:

(一)上下文獲取。通過顯示、隱式、推理等手段對上下文信息進行獲取，這一過程屬于系統(tǒng)的數(shù)據采集階段。其中，顯示獲取能更為精確的獲取上下文信息，但在多數(shù)情況下顯示獲取難以獲取有意義的上下文信息。因此，隱式獲取和依靠推理來獲取信息的方式顯得尤為重要。

(二)上下文建模。在推薦系統(tǒng)研究中，為方便推理和形式化表示信息，大多數(shù)研究人員使用鍵值對、向量模型等方式對上下文進行建模。其他的建模方式還有標記語言、圖模型、邏輯模型等都有其專門針對的應用領域。

(三)上下文用戶偏好提取。用戶在不同條件下對項目的偏好可能不同，如何為用戶偏好建模成為上下文感知推薦系統(tǒng)的關鍵問題之一。目前，有兩種較為成熟的上下文用戶偏好提取技術的研究思路：定量分析與定性分析。定量分析起源與20世紀70年代的用戶建模技術[13]，隨著信息技術的發(fā)展與多種學科交叉融合，逐漸成為推薦系統(tǒng)研究的關鍵領域之一。對于定量分析上下文的用戶偏好提取技術，是指利用評分量化并計算提取用戶偏好。而定性研究上下文用戶偏好提取則主要從邏輯推理等角度來考察用戶偏好在上下文信息約束下的變化趨勢。

(四)上下文感知推薦生成。如何利用上下文信息為用戶生成推薦,是上下文感知推薦的核心部分。通常有兩種劃分方式：基于傳統(tǒng)推薦系統(tǒng)劃分以及基于上下文信息劃分。

其中基于傳統(tǒng)推薦系統(tǒng)劃分將其分為基于協(xié)同過濾、內容的上下文推薦，混合式上下文感知推薦?；趨f(xié)同過濾方式充分利用集體智慧思想來發(fā)現(xiàn)用戶新的興趣，但其稀疏性、冷啟動等問題導致其在數(shù)據量較大時推薦效果不理想。而基于內容的上下文感知推薦，利用上下文信息，挖掘用戶在不同條件下的興趣偏好，但其涉及的特征選擇、推薦范圍、新用戶問題同樣導致其在部分情況下不能有效為用戶推薦。針對上述問題，一些研究人員按照不同策略將不同類型的推薦模型進行組合，在犧牲實時性等情況下提高了推薦準確度。

而基于上下文信息的推薦生成包括[4]：上下文預過濾，上下文后過濾，上下文建模。其主要區(qū)別在于推薦過程中何時利用上下文信息進行過濾，然后根據構建的模型為用戶進行推薦。

(五)上下文感知的效用評價。效用評價對于模型檢驗其性能發(fā)現(xiàn)其存在的問題十分重要。目前，上下文感知推薦系統(tǒng)主要以傳統(tǒng)推薦中使用的效用評價方式進行檢驗。包括:MAE,Precision,Recall,F1,RSME等等。在獲得性能評價結果后，需要根據檢驗結果對模型進行進一步分析研究，并進行相應的改進。

二、基于上下文的道路推薦

地理位置是十分重要的上下文信息之一，對于用戶出行道路選擇有著重要的影響。本節(jié)就基于上下文的道路推薦系統(tǒng)架構模式、信息傳遞以及推薦模型進行介紹。

(一)系統(tǒng)架構

本節(jié)介紹如何利用無線傳感器網絡為交通推薦收集信息。如圖1所示，系統(tǒng)包括由節(jié)點組成的交通道路網絡，為用戶分析信息和提供推薦的服務器。用戶將需求發(fā)送到服務器，系統(tǒng)根據用戶需求以及交通道路圖信息，根據推薦模型分析并返回給用戶適合的道路列表。

圖1 系統(tǒng)架構

交通網絡由傳感器作為節(jié)點，安裝于汽車以及人員較為密集的公共場所，如著名的景點或餐廳。當用戶發(fā)送請求時，車輛上的無線傳感器將用戶需求以及周邊信息(目的地、經緯度等)發(fā)送到服務器，服務器根據檢測到的信息，通過相應的推薦模型為用戶找到合適的路徑。

(二)基于上下文的交通推薦模型

首先對節(jié)點之間的行車時間進行估計，以解決時效性問題。其次，推薦路徑要滿足用戶的個性化需求。

1.節(jié)點間時間估計

由于交通流的實時性，最短的距離并不意味著我們可以用最短的時間到達目的地。首先我們需要估算兩節(jié)點(無線傳感器AB之間的距離)的時間消耗，計算方式如下:

其中tA,B為路段需要時間，SA,B為路段AB之間的距離，VA,B是無線傳感器得到的路段車輛時速。根據公式1，搜索算法可以找到更多從起點到目的地的路徑。服務器根據用戶所提供的信息以及當時交通道路網絡情況為用戶提供的合適的路徑。

2.道路推薦

圖2 系統(tǒng)示例

如圖2所示，其中節(jié)點1、10為用戶的出發(fā)地與目的地，節(jié)點7、8為知名的餐廳，節(jié)點3、5為名勝景區(qū)。用戶要求在出行中游玩一個景點，并在一個餐廳就餐。節(jié)點間的距離為布置的無線傳感器距離，而該路車輛行駛速度為無線傳感器根據車流量實時檢測的車速。根據公式1，我們可以清晰的計算出多條到目的地的行車路線。表1，列出了部分路徑計算信息。

表1 部分路徑信息

從表1 可以看到，不同路徑耗時不同，路過的景點和餐廳也不同。如第一條路徑，就不能滿足用戶需求，因其行車路線中并沒有路過餐廳。相反的，第二條路徑可以滿足用戶的基本需求。應當計算出滿足用戶需求的路徑耗時，并為用戶推薦耗時較短的幾條。

三、總結與展望

近年來，城市化發(fā)展以及經濟水平的提高使得交通出行問題越來越嚴重。因此，本文介紹了一種基于無線傳感器的上下文交通道路推薦模型。首先較為系統(tǒng)的介紹了上下文感知系統(tǒng)的研究理論及關鍵研究點。然后，根據無線傳感器得到的上下文以及用戶需求等信息通過深度優(yōu)先方式得到滿足用戶需求的出現(xiàn)線路。該系統(tǒng)能為用戶提供良好的使用體驗，因為其不僅為用戶推薦路徑，在節(jié)省時間的同時滿足了用戶特定的需求。本文在實驗環(huán)境下通過模擬數(shù)據對系統(tǒng)的有效性進行了驗證，保證其能高效地為用戶進行推薦。在后續(xù)的研究中，系統(tǒng)應當對更多的信息進采集，如天氣，更為具體的用戶需求等等，以保證能夠滿足用戶出行要求。

[1]Daponte P, De Vito L, Picariello F, et al. Wireless sensor network for traffic safety. Environmental Energy and Structural Monitoring Systems (EESMS)[J]. 2012 IEEE Workshop on: IEEE.2012:42-49.

[2]Liang B-j. Traffic flow detection based on wireless sensor network [J]. Journal of Networks, 2013(8):1859-1865.

[3]Ricci F, Rokach L, Shapira B. Introduction to recommender systems handbook [J]. Springer, 2011(1).

[4]Adomavicius G, Tuzhilin A. Personalization technologies: A process-oriented perspective [J]. Communications of the ACM, 2005(10):83-90.

[5]Zeng C, Xing C, Zhou L. A survey of personalization technology [J]. Journal of Software, 2002(10):1952-1961.

[6]Phanich M, Pholkul P, Phimoltares S. Food recommendation system using clustering analysis for diabetic patients[J]. Information Science and Applications (ICISA), 2010 International Conference on: IEEE, 2010.

[7]Wang H, Li G, Hu H, et al. R3: A real-time route recommendation system [J]. Proceedings of the VLDB Endowment, 2014(13).

[8]Liu L, Xu J, Liao SS, et al. A real-time personalized route recommendation system for self-drive tourists based on vehicle to vehicle communication [J]. Expert Systems with Applications, 2014(7).

[9]Meehan K, Lunney T, Curran K, et al. Context-aware intelligent recommendation system for tourism[J]. Pervasive Computing and Communications Workshops (PERCOM Workshops), 2013 IEEE International Conference on: IEEE, 2013:328-331.

[10]Dey AK. Understanding and using context [J]. Personal and ubiquitous computing, 2001(1):4-7.

[11]吳吉義, 林志潔, 龔祥國. 基于協(xié)同過濾的移動電子商務個性化推薦系統(tǒng)若干研究[J]. 電子技術應用, 2007(4).

[12]王立才, 孟祥武, 張玉潔. 上下文感知推薦系統(tǒng)[J]. 軟件學報, 2012(1).

[13]Rich E. User modeling via stereotypes[J]. Cognitive science, 1979(4):329-354.

本文責編：趙鳳緩

Context-Based Traffic Recommendation System

Zhang Meng

(School of Information Management, Shanxi University of Finance and Economics, Taiyuan, Shanxi, 030006)

With the rapid development of urban construction, traffic jam issues in cities have become increasingly severe. How to choose the appropriate municipal roads reasonably is a travel problem that people face with. Real-time road recommendation could ease the traffic situation and reduce the pressure of travel by using information of context and mobile network.

context; recommender system; depth first search algorithm; transit travel

2016—08—31

張 萌(1990—)，男，山西太原人，山西財經大學 信息管理學院，在讀碩士研究生。

G570

B

1008—8350(2016)04—0105—03