一种基于用户兴趣的位置服务推荐算法
2017-09-19邰淳亮孙知信
邰淳亮，谢 怡，孙知信,2
(1.南京邮电大学 计算机学院，江苏 南京 210003；2.南京邮电大学 物联网学院，江苏 南京 210003)
一种基于用户兴趣的位置服务推荐算法
邰淳亮1，谢 怡1，孙知信1,2
(1.南京邮电大学 计算机学院，江苏 南京 210003；2.南京邮电大学 物联网学院，江苏 南京 210003)
随着移动网络经济用户数、商户数和覆盖范围的扩大，基于用户位置的商家信息推送势必会经历“信息爆炸”和“信息过载”，而解决因信息过载导致用户与商家之间的信息迷失的最有效办法是基于用户兴趣的用户位置服务(LBS)推荐。为此，在分别从位置服务技术、用户的兴趣模型，以及个性化推荐算法三个方面深入研究移动位置服务的个性化推荐系统、分析个性化推荐研究现状以及对比分析各种推荐算法的基础上，基于贝叶斯理论，提出了一种适用于移动位置服务的个性化推荐算法。该算法能准确地预测用户在某一情景下消费的兴趣偏好。为验证所提出算法的有效性和可行性，基于所构建的推荐系统进行了实验验证测试。实验结果表明，所提出的算法能够有效地向移动用户提供个性化推荐服务。
位置服务；用户建模；个性化推荐；用户兴趣
0 引 言
自20世纪末诞生以来，推荐系统在互联网领域发挥着重要作用，电子商务、音乐、视频等推荐系统不断服务着人们的生活。随着移动网络经济用户数、商户数和覆盖范围的扩大，基于用户位置的商家信息推送势必会经历“信息爆炸”和“信息过载”，而解决因信息过载导致用户与商家之间的信息迷失的最有效办法是基于用户兴趣的用户位置服务(LBS)推荐。相比较于传统的PC设备，移动设备的特点是随身携带方便，但是页面承载的信息量十分有限，此特点决定了信息的展现需要更精准地符合用户的个体需求，这些因素推动着基于LBS推荐系统研究的深入[1]。
为此，在分别从位置服务技术、用户兴趣模型，以及个性化推荐算法三个方面深入研究移动位置服务的个性化推荐系统、分析个性化推荐研究现状以及对比分析各种推荐算法的基础上，基于贝叶斯理论，提出了一种适用于移动位置服务的个性化推荐算法。该算法利用贝叶斯方法预测用户在某一情景下消费的概率，设计并实现了基于用户兴趣的位置服务推荐系统，并对系统进行了实验验证测试，以验证该算法的有效性和可行性。
1 相关技术研究
1.1位置服务
LBS(Location-Based Service，基于位置的服务)在物流、导航、娱乐、电子商务等领域都有广泛的应用。O2O就是LBS典型的应用方向。一个LBS应用主要由四个方面构成：移动终端、定位技术、通信网络、服务和内容，这四部分相互配合，为用户提供基于位置的信息服务。定位技术是LBS的实现基础，只有解决好了定位问题，才能为用户提供高质量的位置服务。目前定位技术可以分为三类：基于网络的定位技术、基于卫星的定位技术和感知定位技术。位置服务开发平台(LBS平台)根据LBS应用的特点，从不同类型的LBS应用中抽象出它们的共性，进而把这些共性封装在一个平台上，使LBS平台成为一个通用的和易于扩展的位置服务开发平台，在此平台的基础上开发出具备各种功能的LBS应用系统[2]。
1.2用户兴趣建模
个性化推荐系统是以用户需求、兴趣或者偏好为基础，结合信息特征，建立起用户与信息对象之前的联系，提供针对性的信息服务。所以，在推荐系统中，首先要解决用户兴趣模型建立的问题，即用户兴趣模型如何表示与更新，其次是如何利用用户兴趣模型进行个性化推荐。用户兴趣模型是关于用户兴趣、特征和活动知识的表示模型[3]。用户兴趣建模过程主要分为：用户识别、用户信息获取和用户建模[4-7]。
1.3个性化推荐算法
内容过滤推荐系统是基于内容过滤算法(Content-Based Filtering，CBF)，对于某一项目，假如在内容上与该用户之前感兴趣的信息项目相似，那么可以推断用户也对该项目感兴趣。所以该算法的重点在于评估用户没发现的物品与用户之前喜欢的物品之间的相似程度。
CBF基于内容推荐的依赖，使其无法对难以解析的信息对象实现推荐，比如音视频等多媒体信息。另外该算法没有充分利用用户群体的知识，无法发现潜在的信息需求，很难实现具有联想性的推荐。
协作过滤推荐(Collaborative Filtering，CF)源于“集体智慧”的思想，利用相关其他用户的偏好来预测当前用户的偏好，也可以是当前用户与其他用户在部分项目中的偏好数据来预测其潜在偏好，通过发现与用户兴趣相似的邻居用户，并将邻居用户感兴趣的信息项目推荐给目标用户[8]。协同过滤推荐克服了基于内容推荐的两点不足：内容分析能力有限以及无法挖掘用户潜在兴趣。
文献[9]发现，在实际应用中，用户一般只会评价比例很少的一部分物品，因此导致评分矩阵一般较为稀疏，所以协同过滤算法面临的主要难题是用户评分数据稀疏性问题。同时，用户兴趣和需求会随着时间与空间的变化而发生变化，但是传统的协同过滤并没有考虑情景因素对用户偏好的影响。目前，关于协同过滤算法的研究集中在数据稀疏性和情景因素方面。
尽管移动推荐系统的基本思想与传统互联网推荐系统相似，但传统的互联网用户的推荐方法不能直接用到移动推荐中[10]。文献[11]提出一种根据应用类型来确定不同的位置定位精度的方法，比如基于位置的广告推荐和好友推荐所需的位置精度相对较低，而导航等服务则需要较高的精度，那么在不同的情景下使用合适的定位算法。文献[12]利用贝叶斯分类法，把当前时间上下文进行分类，分为工作日和周末。文献[13]在为智能设备推荐电影时，也考虑了上下文因素，包括位置、动作、室内室外、是否为节假日和时间。文献[14]分析了用户购买时间和项目上架时间的关系，将用户的购买记录按购买时间分成不同的购买组，如早期、当前、后期等，该方法考虑了时间推移对用户兴趣变化的影响。
在移动位置服务推荐中，不少文献把内容过滤推荐和协作过滤推荐组合在一起，解决单一推荐方法存在的问题，或者重点考虑用户的上下文环境，忽略了用户评分这一因素。因此将从用户评分中发现用户偏好，并且考虑用户情景对推荐结果的影响，设计一种基于用户兴趣的位置服务推荐算法。
2 基于用户兴趣的位置服务推荐算法
2.1用户评分特征
用户在商家消费完后，对商家的特色、服务产生直观的看法，此时用户对商家的评分可以反映出对商家的喜爱程度，进而可以推广为对这一类商家的喜爱程度。为了能量化用户对商家的评分特征，评分量表使用五分制，覆盖从“非常不喜欢”到“非常喜欢”，由于商家信息经过标签化处理，用户可以对每个标签关键词进行评分，细化了用户对商家的评价。
2.1.1 建立用户评分标签
用户通过对商家的标签关键词给予评分来表达对商家的喜爱程度。每个商家含有多个标签关键词，每个用户可以对多个商家的多个标签关键词进行评分，分数范围为1至5，1分表示不喜欢，5分表示很喜欢，分数高低反映出用户对商家的喜爱程度。由于标签还可以自由组合，形成新的商家信息，因此分析用户对商家的评分信息，其重点不在于发现哪些商家获得较高的评分值，而主要是找到被用户赋予较高分值的是哪些标签，把这些标签提取出来，并进行相关组合，那么可以得到其他含有此类标签的商家，这些商家将作为推荐候选。图1是用户-商家-标签-评分之间的关系。
图1 用户-商家-标签-评分之间的关系
标签可以看作是项目的内容，基于标签的推荐从本质上可以视为基于内容过滤的推荐，维护好每个物品特征的详细列表，将这些信息保存在数据库中，根据用户不同的兴趣，用这些特征描述他们的偏好，推荐要做的就是将物品特征和用户偏好匹配起来，而这也正是分析用户-商家-标签-评分间关系的目的，进而发现用户的评分特征。文献[15]在电影领域利用基于标签的推荐，方法是组合两种数据源，分别是奈飞评分数据库和互联网电影数据库。
同样地，在本地生活领域的服务推荐中也可以利用评分标签云，每个商家可以视为一组特征关键词。通过分析用户的历史评分信息，建立起用户不同评分等级所包含的标签关键词。例如，从历史评分记录中发现用户A经常评5分的商家通常会有标签“火锅”、“川湘菜”或“环境优雅”等，那么根据这些信息，可以找出用户A没有评分但含有标签“火锅”、“川湘菜”和“环境优雅”这样关键词的商家，并猜测这些商家会被用户A评5分。
设某个特定用户u∈U，U是所有用户的集合；某个商家m∈M，M是所有商家的集合；评分值记为r∈R，R是可能评分值的集合，且R={1，2，…，5}。
定义Mu为用户u评分的商家集合，用户u∈U对商家m∈Mu的评分值记为fu(m)∈R。K是所有标签关键词的全集，Km为与商家m有关的标签关键词集合。
根据以上条件，定义nk(u,r)表示用户u评分为r的商家中，标签关键词k出现的频次。其中，用户u的评分值为r，k∈K代表关键词，因此nk(u,r)可以定义为：
nk(u,r)=
|{m|m∈Mu∧k∈Km∧fu(m)=r}|
(1)
这一数值反映了用户将评分等级设为r时，在这一分值等级下，标签k的分布情况，间接体现了用户的偏好。
定义Nu,r为元组(k,nk(u,r))的集合，那么Nu,r表示被用户u评分为r的所有关键词标签，以及这些标签出现的次数。所以用Nu,r可以刻画在不同的评分等级下用户的标签评分特征。由此也可以推出，找到用户评分为5时出现次数最多的标签关键词，假如某一商家的标签恰好与这些标签重合，也就可以认为用户对该商家的评分为5，用户非常喜欢该商家。
2.1.2 基于用户评分特征的匹配
由上一节可知，Nu,r刻画了用户的标签评分特征，反映出用户对某一类型商家的偏好程度。为了预测用户对某一没有消费过商家的评分，只需将商家的标签与用户的标签评分特征Nu,r进行匹配，当交集最大时，就可以得到预测评分。
σ(u,m*,r)=|{(k,nk)∈Nu,r|k∈Km*}|
(2)
当用户评分特征Nu,r与商家m*相关的标签集合交集最大时，就能得到评分r*。如果预测评分越高，说明用户对该商家越满意，应加入到推荐列表中。
2.2用户情景需求
移动位置服务的一大特点是用户的位置环境处于实时变化中，因此对位置服务的需求也在时刻变化。把用户需求作为用户兴趣模型的重要一部分，把季节、时间和节假日之间的组合进行分类，得到每种类别下用户消费某一类标签商家的概率。
2.2.1 用户情景分类
所描述的用户情景需求包括季节、时间和节假日三个属性，用三元组Cs表示如下：
Cs=
(3)
其中，Si表示第i种季节，依次对应为春夏秋冬；T由三个时间段组成，分别对应上午、中午和下午；H表示节假日，“1”表示节假日，“0”表示非节假日。
根据排列组合的规则，用户情景有24种情况，例如C1=<1,1,0>，表示春天、上午和非节假日。系统需要记录用户在不同情景下的商家消费情况，用户的历史消费记录可以表示为情景信息与商家标签信息的组合，定义record为用户历史消费记录，则可表示为：
record=
(4)
例如，用户u在12月5号中午在一家环境优雅的西餐厅点了一份价格适中的西冷牛排，那么该条记录可以表示为：
recordu=<冬天，中午，非节假日|西餐，牛排，价格合理，环境优雅>
(5)
2.2.2 用户消费倾向预估
用户消费情景，也可以表述为用户消费时的上下文环境。在特定的情景下，用户的需求会比较确定。例如，用户A喜欢在夏天吃冰淇淋，冬天喜欢吃火锅，那么当该用户外出时，拿出手机查询周围的商家时，就应该分析该用户所处的季节，进而推荐相应的商家。文献[12]通过分析用户所处的上下文环境，为移动用户推荐合适的电影。文献[13]对文献[12]提出的算法进行改进，并且在上下文环境中增加了用户动作、设备是否在用户手上、具体时间等，利用SVM、k值最近邻等方法对上下文环境进行识别，最后通过20名实验者来判断推荐的电影是否满意。由此可以看出，文献[12]和文献[13]在电影推荐领域运用贝叶斯分类法则，用一组特征关键词表示电影信息，在用户观看记录中，将电影信息和观看时的上下文环境组合在一起，便于预测今后在某个情景下用户观影的倾向。
从上文的商家信息标签化处理可以得到，商家信息也能用一组特征标签向量表示，而且用户的消费情景也可以用季节、时间和节假日三个属性表示，这三个属性通过自由组合，能够形成24种用户情景，用户消费记录中所要保存的是在每种情景下用户消费过的商家特征标签向量。所以，在移动位置服务推荐领域，也可以运用贝叶斯法则，给定用户的消费记录，整理出每种情景下消费某一类标签商家的次数，由此预估用户下次再遇到相似的情景时，选择商家消费的概率。
通过分析用户的历史消费记录，运用贝叶斯法则，计算出用户u在某一种情景下，消费某一组标签向量商家的概率。
(6)
(7)
其中，n(fi,Cj)表示在消费情景Cj下，选择包含标签fi商家的次数；n(Cj)表示在Cj条件下所有标签的出现次数；|Vj|表示在Cj条件下出现标签的个数。
2.3个性化推荐
个性化商家推荐列表的生成综合评估了用户的实时地理位置，历史评分特征和情景需求。通过用户的地理位置，系统拉取了周围各种类型的商家信息，然后根据用户的评分特征和情景需求，筛选出符合用户兴趣的商家。图2显示了个性推荐生成过程。
图2 个性化推荐生成
对于用户u，商家m*的加权预估评分值计算。
(8)
根据最后得出的加权预估评分值，分值越高的商家越值得向用户推荐。
3 基于用户兴趣的位置服务推荐系统设计
3.1系统流程框架
用户登录系统，首先获取的是用户实时地理位置，然后是用户历史消费记录和用户的评分数据，基于这些信息能够挖掘出用户的兴趣，构建用户兴趣模型，而且商家的语句性描述信息也要进行标签化处理，以便匹配用户兴趣，生成推荐列表。系统流程如图3所示。
图3 系统流程图
3.2系统功能模块设计
设计的基于用户兴趣的位置服务推荐系统主要分为三个模块：商家信息管理模块、用户兴趣模型模块和个性化推荐模块，在每个模块下面又做进一步的细分，其中商家信息模块负责提取商家的关键信息，并且用一组特征向量表示，便于后续个性化推荐中与用户兴趣进行匹配，而用户兴趣模型则主要把用户的兴趣特征提取出来，也是为个性化推荐服务。图4显示了系统细分的模块。
4 推荐系统的实现
该系统采用SSH2(Struts2+Spring+Hibernate)框架进行开发，将系统分为表现层、业务层、数据持久层。Struts2实现了MVC模型，首先利用拦截器获取用户的实时请求信息，充当了控制层的作用，获取用户的请求信息之后，与业务层进行交互，结果将返回到具体的表现层界面，最后表现层中包含的页面信息将会返回到具体的客户端。Android客户端采用的是MVC(Model-View-Controller)模型，视图层建立View视图模型，以XML文件的方式进行界面设计，用于接收消息，并对数据进行展示和更新的操作，控制层Controller则通过控制器Activity，与用户进行交互，用于接收View视图的操作请求，同时，对于处理完成的数据交给View层进行数据更新，保证Model和View的同步。模型层Model接收来自Controller的数据，对数据进行处理，同时完成程序的业务逻辑处理，将处理完成的数据通知Controller，保证视图的实时更新。
图4 系统细分模块图
测试系统依次实现登录、获取位置信息、添加标签、完成推荐等功能。系统测试如图5所示。
图5 基于用户兴趣的位置服务推荐系统测试图
5 结束语
智能设备与移动互联网的发展普及，有效地促进了移动用户对智能设备功能的多方面需求，促使其生活方式发生诸多变化。智能设备的应用催生了基于用户兴趣的位置服务推荐系统。为此，围绕时间因素，提出了基于用户历史评分和兴趣消费情景的用户服务推荐系统。而作为推荐系统的算法，其效果多依赖于用户主观因素，仍缺乏其实际推荐效果的考察。为此，对提出算法进行了实验验证。实验结果表明，该算法能够有效地向移动用户提供个性化推荐服务。
移动互联网时代的到来，信息资源的获取和推送可以以任何方式发生在任何时间和任何地点，移动位置推荐系统利用移动环境在信息推荐方面的优势，克服其不利因素，基于用户偏好来预测和过滤不相关的信息，为移动用户提供个性化服务，为解决“移动信息过载”提供了一种有效方式。
[1] Jannach D,Zanker M,Felfernig A,et al.推荐系统[M].蒋 凡,译.北京:人民邮电出版社,2013.
[2] 盛 珍.基于Android平台的LBS应用系统开发技术研究[D].昆明：云南大学，2012.
[3] Razmerita L.An ontology-based framework for modeling user behavior-a case study in knowledge management[J].IEEE Transaction on Systems and Humans,2011,41(4):772-783.
[4] 袁 柳，张龙波.个性化检索中的用户特征模型研究[J].计算机工程与应用,2011,47(15):19-24.
[5] Wetzker R,Zimmermann C,Bauckhage C,et al.I tag,you tag:translating tags for advanced user model[C]//Proceedings of the third ACM international conference on web search and data mining.[s.l.]:ACM,2010:71-80.
[6] 任 磊.推荐系统关键技术研究[D].上海：华东师范大学，2012.
[7] 孟祥武，王 凡，史艳翠,等.移动用户需求获取技术及其应用[J].软件学报，2014,25(3)：439-456.
[8] 王立才，孟祥武，张玉洁.上下文感知推荐系统[J].软件学报，2012,23(1)：1-20.
[9] Bobadilla J,Ortega F,Hernando A,et al.A collaborative filtering approach to mitigate the new user cold start problem[J].Knowledge-Based System,2012,26:225-238.
[10] 孟祥武，胡 勋，王立才,等.移动推荐系统及其应用[J].软件学报，2013,24(1)：91-108.
[11] Basiri A,Lohan E S.Overview of positioning technologies from fitness-to-purpose point of view[C]//International conference on localization and GNSS.Helsinki,Finland:IEEE,2014:1-7.
[12] Yu Z,Zhou X,Zhang D,et al.Supporting context-aw-are media recommendation for smart phones[J].IEEE Pervasive Computing,2006,5(3):68-75.
[13] Moradeyo A,Teresa M.Supporting context-aware cloud-based media recommendation for smartphones[C]//2nd IEEE international conference on mobile cloud computing,service and engineering.Oxford,England:IEEE,2014:109-117.
[14] Lee T Q,Park Y,Park Y T.A time-based approach to effective recommender systems using implicit feedback[J].Expert Systems with Applications,2008,34(4):3055-3062.
[15] Szomszor C,Cattuto H,Alani K,et al.Folksonomies,the semantic web,and movie recommendation[C]//Workshop on bridging the gap between semantic Web and Web 2.0.Innsbruck,Austria:Springer,2007:71-84.
A Recommendation Algorithm of Location Service Based on User Interest
TAI Chun-liang1，XIE Yi1，SUN Zhi-xin1,2
(1.School of Computer Science,Nanjing University of Posts and Telecommunications,Nanjing 210003,China；2.School of IOT,Nanjing University of Posts and Telecommunications,Nanjing 210003,China)
With the increase of consumers and merchants,information pushing services based on consumers’ localities are deemed to go through information explosion and communication overload.Locality service recommendation based on consumers’ interests is an effective method to deal with information misleading between consumers and merchants stemmed from the information overload.In order to solve the problem mentioned above,after the individual recommendation system based on mobile locality has been researched on three aspects,locality service technique,consumers’ interest model and individual recommendation algorithms respectively as well as the status of investigation on individual recommendation and contrast analysis on various recommendation algorithms.Based on Bayesian theory,an individual recommendation algorithm suitable for mobile location services is proposed,which can predict consumers’ consumption interest accurately in a certain scenario.In order to verify its effectiveness and feasibility,a series of simulation experiments for verification have been conducted with the established recommendation system,which show that it has provided efficient individual recommendation services to mobile consumers.
location-based service;user modeling;personalized recommendation;user interest
2016-08-13
：2016-11-24 < class="emphasis_bold">网络出版时间
时间：2017-07-11
国家自然科学基金资助项目(60973140,61170276,61373135)；江苏省产学研项目(BY2013011)；江苏省科技型企业创新基金项目(BC2013027)；江苏省高校自然科学研究重大项目(12KJA520003)
邰淳亮(1989-)，男，硕士研究生，研究方向为基于网络的计算机软件应用技术;孙知信，博士,教授，研究方向为计算机网络与安全。
http://kns.cnki.net/kcms/detail/61.1450.TP.20170711.1452.006.html
TP301.6
:A
:1673-629X(2017)09-0064-06
10.3969/j.issn.1673-629X.2017.09.014
