基于上下文的道路推荐系统

□张 萌

( 山西财经大学 信息管理学院，山西 太原 030006)

基于上下文的道路推荐系统

□张 萌

( 山西财经大学 信息管理学院，山西 太原 030006)

随着城市化建设高速发展，市区道路交通拥堵问题日益加剧，如何合理选择合适的出行道路成为人们面临的出行难题。利用上下文、移动网络等信息为用户进行实时道路推荐能够缓解交通拥堵，减轻人们的出行压力。

上下文；推荐系统；深度优先搜索；交通出行

随着城市经济高速增长，特别是在较发达城市地区，交通的压力越来越大。严重的交通堵塞问题，直接影响到城市经济发展和居民出行，出行拥堵成为一个亟待解决的交通问题。以无线传感网络(Wireless sensor network)为基础的智能交通系统(Intelligent transportation systems)成为交通管理的有效技术。由于其成本较低，易于安装等特点，已经有许多WSN技术的研究者将其利用在交通测量领域，文献[1]提出了一个利用无线传感器网络的交通安全测量模型。Liang[2]采用无线传感器网络来检测交通流，实验表明节点平均即检测率达到90%。另一方面，许多研究者将传感器安装在车辆中，希望能得到更加精确的交通道路情况。

推荐系统[3]作为个性化服务[4,5]的重要研究领域,在电子商务领域和信息检索方向已取得了成果，并被引入到移动应用、物联网广告等许多新兴领域。文献[6]中，Phanich等人提出了一种基于上下文的美食推荐系统，为用户推荐适合的营养食品。Wang等人[7]提出了一个实时的道路推荐系统。而由于车流是不断变化的，普通的线路推荐系统没有考虑实时性问题，并不能缓解交通堵塞问题。为缓解交通压力，Long L等人[8]提出了一种具有实时性个性化的自助游推荐系统。Meehan等人[9]提出了一种基于上下文感知的智能旅游混合推荐系统，为用户提供良好的出行体验。本文在现有的上下文推荐研究基础上，利用WSN技术，提出一种基于上下文信息的实时道路推荐模型。

一、上下文感知推荐系统

自20世纪90年代上下文感知概念提出以来，至今“上下文”这一复杂概念还未有一个统一定义。Dey[10]将其定义为：用户描述实体状态的任何信息，其中实体包括人、地点等。而在上下文感知推荐系统中的“上下文”也未有一个统一的定义[11]，通常是结合实际的应用情景或者用户需求完成合适的定义。

作为“普适计算”核心领域的上下文感知计算理论，自动发现和利用位置、环境等上下文信息为用户提供服务等研究已经取得许多研究成果[12]。合理利用上下文环境(时间、位置、情绪等)为推荐系统提供更多用户信息，能够提高推荐质量和用户满意度。

一个完整的上下文感知推荐系统由以下几部分组成:

(一)上下文获取。通过显示、隐式、推理等手段对上下文信息进行获取，这一过程属于系统的数据采集阶段。其中，显示获取能更为精确的获取上下文信息，但在多数情况下显示获取难以获取有意义的上下文信息。因此，隐式获取和依靠推理来获取信息的方式显得尤为重要。

(二)上下文建模。在推荐系统研究中，为方便推理和形式化表示信息，大多数研究人员使用键值对、向量模型等方式对上下文进行建模。其他的建模方式还有标记语言、图模型、逻辑模型等都有其专门针对的应用领域。

(三)上下文用户偏好提取。用户在不同条件下对项目的偏好可能不同，如何为用户偏好建模成为上下文感知推荐系统的关键问题之一。目前，有两种较为成熟的上下文用户偏好提取技术的研究思路：定量分析与定性分析。定量分析起源与20世纪70年代的用户建模技术[13]，随着信息技术的发展与多种学科交叉融合，逐渐成为推荐系统研究的关键领域之一。对于定量分析上下文的用户偏好提取技术，是指利用评分量化并计算提取用户偏好。而定性研究上下文用户偏好提取则主要从逻辑推理等角度来考察用户偏好在上下文信息约束下的变化趋势。

(四)上下文感知推荐生成。如何利用上下文信息为用户生成推荐,是上下文感知推荐的核心部分。通常有两种划分方式：基于传统推荐系统划分以及基于上下文信息划分。

其中基于传统推荐系统划分将其分为基于协同过滤、内容的上下文推荐，混合式上下文感知推荐。基于协同过滤方式充分利用集体智慧思想来发现用户新的兴趣，但其稀疏性、冷启动等问题导致其在数据量较大时推荐效果不理想。而基于内容的上下文感知推荐，利用上下文信息，挖掘用户在不同条件下的兴趣偏好，但其涉及的特征选择、推荐范围、新用户问题同样导致其在部分情况下不能有效为用户推荐。针对上述问题，一些研究人员按照不同策略将不同类型的推荐模型进行组合，在牺牲实时性等情况下提高了推荐准确度。

而基于上下文信息的推荐生成包括[4]：上下文预过滤，上下文后过滤，上下文建模。其主要区别在于推荐过程中何时利用上下文信息进行过滤，然后根据构建的模型为用户进行推荐。

(五)上下文感知的效用评价。效用评价对于模型检验其性能发现其存在的问题十分重要。目前，上下文感知推荐系统主要以传统推荐中使用的效用评价方式进行检验。包括:MAE,Precision,Recall,F1,RSME等等。在获得性能评价结果后，需要根据检验结果对模型进行进一步分析研究，并进行相应的改进。

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

地理位置是十分重要的上下文信息之一，对于用户出行道路选择有着重要的影响。本节就基于上下文的道路推荐系统架构模式、信息传递以及推荐模型进行介绍。

(一)系统架构

本节介绍如何利用无线传感器网络为交通推荐收集信息。如图1所示，系统包括由节点组成的交通道路网络，为用户分析信息和提供推荐的服务器。用户将需求发送到服务器，系统根据用户需求以及交通道路图信息，根据推荐模型分析并返回给用户适合的道路列表。

图1 系统架构

交通网络由传感器作为节点，安装于汽车以及人员较为密集的公共场所，如著名的景点或餐厅。当用户发送请求时，车辆上的无线传感器将用户需求以及周边信息(目的地、经纬度等)发送到服务器，服务器根据检测到的信息，通过相应的推荐模型为用户找到合适的路径。

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

首先对节点之间的行车时间进行估计，以解决时效性问题。其次，推荐路径要满足用户的个性化需求。

1.节点间时间估计

由于交通流的实时性，最短的距离并不意味着我们可以用最短的时间到达目的地。首先我们需要估算两节点(无线传感器AB之间的距离)的时间消耗，计算方式如下:

其中tA,B为路段需要时间，SA,B为路段AB之间的距离，VA,B是无线传感器得到的路段车辆时速。根据公式1，搜索算法可以找到更多从起点到目的地的路径。服务器根据用户所提供的信息以及当时交通道路网络情况为用户提供的合适的路径。

2.道路推荐

图2 系统示例

如图2所示，其中节点1、10为用户的出发地与目的地，节点7、8为知名的餐厅，节点3、5为名胜景区。用户要求在出行中游玩一个景点，并在一个餐厅就餐。节点间的距离为布置的无线传感器距离，而该路车辆行驶速度为无线传感器根据车流量实时检测的车速。根据公式1，我们可以清晰的计算出多条到目的地的行车路线。表1，列出了部分路径计算信息。

表1 部分路径信息

从表1 可以看到，不同路径耗时不同，路过的景点和餐厅也不同。如第一条路径，就不能满足用户需求，因其行车路线中并没有路过餐厅。相反的，第二条路径可以满足用户的基本需求。应当计算出满足用户需求的路径耗时，并为用户推荐耗时较短的几条。

三、总结与展望

近年来，城市化发展以及经济水平的提高使得交通出行问题越来越严重。因此，本文介绍了一种基于无线传感器的上下文交通道路推荐模型。首先较为系统的介绍了上下文感知系统的研究理论及关键研究点。然后，根据无线传感器得到的上下文以及用户需求等信息通过深度优先方式得到满足用户需求的出现线路。该系统能为用户提供良好的使用体验，因为其不仅为用户推荐路径，在节省时间的同时满足了用户特定的需求。本文在实验环境下通过模拟数据对系统的有效性进行了验证，保证其能高效地为用户进行推荐。在后续的研究中，系统应当对更多的信息进采集，如天气，更为具体的用户需求等等，以保证能够满足用户出行要求。

[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]吴吉义, 林志洁, 龚祥国. 基于协同过滤的移动电子商务个性化推荐系统若干研究[J]. 电子技术应用, 2007(4).

[12]王立才, 孟祥武, 张玉洁. 上下文感知推荐系统[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