第14卷第4期 智能系统学报 Vol.14 No.4 2019年7月 CAAI Transactions on Intelligent Systems Jul.2019 D0:10.11992/tis.201801048 网络出版地址:http:/kns.cnki.net/kcms/detail/23.1538.TP.20180625.0912.002.html 多特征融合的兴趣点推荐算法 涂飞 (重庆理工大学计算机科学与技术学院,重庆400054) 摘要:基于位置社交网络的兴趣点推荐越来越受到工业界和学术界的关注。由于用户签到数据集的稀疏性 以及签到地理位置的聚集性,使得目前的推荐算法效率普遍不高,特别是当用户外出到新的地点时,推荐效果 更是急刷下降。因此本文提出了一种基于用户-区域-内容主题的多特征联合推荐算法(UCRTM),以隐主题模 型为基础,在统一的框架下利用隐含因子关联性融合了用户的偏好、兴趣点的内容以及兴趣点所属地理区域主 题等信息来进行推荐,使得用户无论身处何地,都能获得理想的推荐服务。本文在两种真实的数据集上进行了 实验,结果表明该方法不仅能够克服数据的稀疏性以及弱语义性等问题,而且与其他方法相比具有更高的推荐 准确率。 关键词:位置社交网络:兴趣点推荐:主题模型:困惑度:稀疏性:聚集性:协同过滤:特征融合 中图分类号:TP391.9文献标志码:A文章编号:1673-4785(2019)04-0779-08 中文引用格式:涂飞.多特征融合的兴趣点推荐算法.智能系统学报,2019,14(4):779-786. 英文引用格式:TU Fei..A point of interest recommendation algorithm based on multi-feature fusion.CAAI transactions on intel- 1 igent systems,2019,144):779-786. A point of interest recommendation algorithm based on multi-feature fusion TU Fei (School of Computer Science and Engineering,Chongging University of Technology,Chongqing 400054,China) Abstract:The point of interest recommendation service is receiving increasing attention from the industry and aca- demia.The sparsity of users'activity history datasets and aggregation of geological position prevent the current recom- mendation algorithm efficiency from being high,and especially,when a user goes out to a new city,the recommenda- tion effect will fall sharply.Therefore,this paper presents a user-content-region topic model based on a joint recom- mendation algorithm,considering to the user's preferences,the content of the point of interest,and the geographical area,making users obtain an ideal recommendation service irrespective of their location.An experiment was carried out on two real datasets,and the results show that this method can not only overcome problems such as data sparseness, weak semantic performance,but also has a higher recommendation accuracy compared with other methods. Keywords:location-based social networks;point of interest recommendation;topic model;perplexity;sparseness;ag- gregation;collaborative filtering,multi-feature fusion 基于位置的社交网络LBSN(location based 兴趣点推荐1等多种个性化服务。兴趣点推荐 social network)实现了用户对其访问地理位置的 的目标是向特定用户推荐满足其需求的、具有一 签到功能,并能够发布相应的评论、图片、视频信 定长度的未知兴趣点列表,来增强用户体验。 息与好友分享。通过LBSN可以提供好友推荐B 般来说,推荐的兴趣点包括地点(如饭馆、商场、 公园和影院等)和活动(如演唱会、公益活动 收稿日期:2018-01-27.网络出版日期:2018-06-26 基金项目:国家自然科学基金项目(61272277) 等)两类。与传统电子商务网站的推荐系统不 通信作者:涂飞.E-mail:tufeicq979@163.com. 同,兴趣点推荐有如下的特性:
DOI: 10.11992/tis.201801048 网络出版地址: http://kns.cnki.net/kcms/detail/23.1538.TP.20180625.0912.002.html 多特征融合的兴趣点推荐算法 涂飞 (重庆理工大学 计算机科学与技术学院,重庆 400054) 摘 要:基于位置社交网络的兴趣点推荐越来越受到工业界和学术界的关注。由于用户签到数据集的稀疏性 以及签到地理位置的聚集性,使得目前的推荐算法效率普遍不高,特别是当用户外出到新的地点时,推荐效果 更是急剧下降。因此本文提出了一种基于用户−区域−内容主题的多特征联合推荐算法 (UCRTM),以隐主题模 型为基础,在统一的框架下利用隐含因子关联性融合了用户的偏好、兴趣点的内容以及兴趣点所属地理区域主 题等信息来进行推荐,使得用户无论身处何地,都能获得理想的推荐服务。本文在两种真实的数据集上进行了 实验,结果表明该方法不仅能够克服数据的稀疏性以及弱语义性等问题,而且与其他方法相比具有更高的推荐 准确率。 关键词:位置社交网络;兴趣点推荐;主题模型;困惑度;稀疏性;聚集性;协同过滤;特征融合 中图分类号:TP391.9 文献标志码:A 文章编号:1673−4785(2019)04−0779−08 中文引用格式:涂飞. 多特征融合的兴趣点推荐算法 [J]. 智能系统学报, 2019, 14(4): 779–786. 英文引用格式:TU Fei. A point of interest recommendation algorithm based on multi-feature fusion[J]. CAAI transactions on intelligent systems, 2019, 14(4): 779–786. A point of interest recommendation algorithm based on multi-feature fusion TU Fei (School of Computer Science and Engineering, Chongqing University of Technology, Chongqing 400054, China) Abstract: The point of interest recommendation service is receiving increasing attention from the industry and academia. The sparsity of users’ activity history datasets and aggregation of geological position prevent the current recommendation algorithm efficiency from being high, and especially, when a user goes out to a new city, the recommendation effect will fall sharply. Therefore, this paper presents a user-content-region topic model based on a joint recommendation algorithm, considering to the user’s preferences, the content of the point of interest, and the geographical area, making users obtain an ideal recommendation service irrespective of their location. An experiment was carried out on two real datasets, and the results show that this method can not only overcome problems such as data sparseness, weak semantic performance, but also has a higher recommendation accuracy compared with other methods. Keywords: location-based social networks; point of interest recommendation; topic model; perplexity; sparseness; aggregation; collaborative filtering; multi-feature fusion 基于位置的社交网络 LBSN[1] (location based social network) 实现了用户对其访问地理位置的 签到功能,并能够发布相应的评论、图片、视频信 息与好友分享。通过 LBSN 可以提供好友推荐[2-3] 、 兴趣点推荐[4-5] 等多种个性化服务。兴趣点推荐 的目标是向特定用户推荐满足其需求的、具有一 定长度的未知兴趣点列表,来增强用户体验。一 般来说,推荐的兴趣点包括地点 (如饭馆、商场、 公园和影院等 ) 和 活 动 (如演唱会、公益活动 等) 两类。与传统电子商务网站的推荐系统不 同,兴趣点推荐有如下的特性: 收稿日期:2018−01−27. 网络出版日期:2018−06−26. 基金项目:国家自然科学基金项目 (61272277). 通信作者:涂飞. E-mail:tufeicq1979@163.com. 第 14 卷第 4 期 智 能 系 统 学 报 Vol.14 No.4 2019 年 7 月 CAAI Transactions on Intelligent Systems Jul. 2019
·780· 智能系统学报 第14卷 1)数据的弱语义性:传统的推荐系统中,用 2)引入地理因素的推荐算法:在LBSN中,用 户对商品的评分是显现的,可以表达其偏好程 户与兴趣点的地理距离也是推荐的重要因素,这 度,如五级评分制中5代表很喜欢,而1代表不喜 也是有别于商品推荐的重要特征,这类算法将地 欢。在兴趣点推荐系统中,只能获取用户对兴趣 理信息融人到模型中,如文献[6]认为用户签到 点的访问次数,而签到次数的多少并不能反映用 的兴趣点在地理位置上是符合幂律分布,文献 户的偏好程度。换句话说传统的推荐数据中同时 [8]则认为用户的活动区域是围绕多个中心点展 包含正例和负例,而兴趣点推荐数据仅包含正 开的,进而引入了多中心高斯分布模型。事实证 例,这就使得很多成熟的推荐方法如协同过滤算 明对地理信息建模有助于推荐效果的提升。 法等并不直接适用于兴趣点推荐。 3)引入社交影响的推荐算法:这类方法认为 2)数据的稀疏性:用户对兴趣点的签到矩阵 社交网络上的“朋友”拥有相同的兴趣爱好,结合 朋友的签到访问历史记录进行推荐,如文献 相比于传统的用户-商品评分矩阵更加稀疏,如 [9]利用相似用户进行推荐时,直接利用好友进行 国外著名的LBSN网络一一Gowalla的数据稀疏 推荐,而忽略LBSN中其他用户。文献[8]将社交 度为2.08×10。传统的推荐算法难以直接适用于 关系直接融入到矩阵分解(PMF)算法中,但是实 兴趣点推荐。此外用户的历史活动记录具有聚集 验证明社交关系对推荐准确率的影响不大。 性,通常只集中在居住地或工作地等少数几个区 还有一些方法同时考虑了地理因素、用户的 域。当用户外出时,由于缺少该区域的历史签到 偏好以及社交关系。如文献[10]设计了一种UPS 记录无法做出准确的推荐。 (user,proximity and social-based)算法,将社交影响 3)社交影响不大:传统在线社交网络上的“朋 因子融合到基于用户偏好的协同过滤算法中,以 友”往往具有相似的兴趣爱好,因此很多推荐算法 此来提高用户相似度计算的准确性。实验证明该 通过引入社交关系来处理数据的稀疏性问题,提 算法在稀疏数据环境下的推荐效果并不是很好, 高效率。但是在LBSN中的“朋友”不一定具有相 而且该算法没有考虑用户在不同的地理位置的影 同的兴趣爱好,引入社交关系对兴趣点推荐影响 响。文献[ll]提出了USG(user,social and geo- 不大。 graphical influence based recommendation)推荐算 鉴于此,本文提出了一种新的推荐模型一一 法,综合考虑了用户偏好、社交影响和地理影响, 用户-内容-区域主题模型(user-content-.region top- 采用线性融合技术集成这3种因素,以此来提高 ic model,UCRTM)。该模型同时分析了用户兴 算法的准确率。该方法虽然考虑了地理因素,但 趣、地点特定主题以及所属地理区域主题等多个 是只考虑了用户常驻地特征,推荐的地点都是常 特征,以隐含主题为基础,用统一的框架将各种 驻地附近区域,而且算法的参数不能自适应地调 特征进行融合,在一定程度上克服了用户签到数 节。此外还有很多学者利用概率产生式模型对位 据的稀疏性和弱语义性等问题,实验证明能获得 置社交网络的推荐系统进行研究,将影响用户签 较好的用户体验。 到决策的各种因素进行综合考虑和集成,比如文 献[12]提出的LCARS系统从用户兴趣、地理位 1相关工作 置、兴趣点当地特色3个方面分析,来对用户的 目前基于位置社交网络的兴趣点推荐算法可 签到行为进行建模,文献[13]提出的JUMAI系统 归纳为3类: 更是从用户兴趣、兴趣点所在区域与用户所在区 1)传统推荐算法的直接运用:这类方法认为 域的距离、签到时间,以及兴趣点类别4个角度 用户对兴趣点的签到次数能够代表其偏好程度, 来指导签到决策。文献[14)在此基础上还考虑了 构造用户-兴趣点签到矩阵并利用传统的推荐算 用户在新的地点会产生兴趣漂移情况。但是这些 法进行推荐。如:文献[6]提出的基于用户和兴 模型均没有考虑兴趣点本身的内容,其次上述模 趣点的混合协同过滤算法;文献[7]提出的基于 型在对各因素进行建模时,没有体现自适应的特 正则化矩阵分解(RMF)算法和文献[8]提出的概 性,即针对不同的兴趣点,何种因素对决策起支 率矩阵分解(PMF)算法等。这类方法的本质是尽 配作用。本文提出了用户-区域-内容主题模型, 量完善推荐模型,但由于数据集本身过度稀疏, 真实地模拟了用户对兴趣点签到的决策过程,实 以及数据的弱语义性导致推荐质量并不高。 验证明在稀疏的数据集下有较理想的推荐效果
1) 数据的弱语义性:传统的推荐系统中,用 户对商品的评分是显现的,可以表达其偏好程 度,如五级评分制中 5 代表很喜欢,而 1 代表不喜 欢。在兴趣点推荐系统中,只能获取用户对兴趣 点的访问次数,而签到次数的多少并不能反映用 户的偏好程度。换句话说传统的推荐数据中同时 包含正例和负例,而兴趣点推荐数据仅包含正 例,这就使得很多成熟的推荐方法如协同过滤算 法等并不直接适用于兴趣点推荐。 2) 数据的稀疏性:用户对兴趣点的签到矩阵 相比于传统的用户−商品评分矩阵更加稀疏,如 国外著名的 LBSN 网络——Gowalla 的数据稀疏 度为 2.08×10−4。传统的推荐算法难以直接适用于 兴趣点推荐。此外用户的历史活动记录具有聚集 性,通常只集中在居住地或工作地等少数几个区 域。当用户外出时,由于缺少该区域的历史签到 记录无法做出准确的推荐。 3) 社交影响不大:传统在线社交网络上的“朋 友”往往具有相似的兴趣爱好,因此很多推荐算法 通过引入社交关系来处理数据的稀疏性问题,提 高效率。但是在 LBSN 中的“朋友”不一定具有相 同的兴趣爱好,引入社交关系对兴趣点推荐影响 不大。 鉴于此,本文提出了一种新的推荐模型—— 用户−内容−区域主题模型 (user-content-region topic model, UCRTM)。该模型同时分析了用户兴 趣、地点特定主题以及所属地理区域主题等多个 特征,以隐含主题为基础,用统一的框架将各种 特征进行融合,在一定程度上克服了用户签到数 据的稀疏性和弱语义性等问题,实验证明能获得 较好的用户体验。 1 相关工作 目前基于位置社交网络的兴趣点推荐算法可 归纳为 3 类: 1) 传统推荐算法的直接运用:这类方法认为 用户对兴趣点的签到次数能够代表其偏好程度, 构造用户−兴趣点签到矩阵并利用传统的推荐算 法进行推荐。如:文献 [6] 提出的基于用户和兴 趣点的混合协同过滤算法;文献 [7] 提出的基于 正则化矩阵分解 (RMF) 算法和文献 [8] 提出的概 率矩阵分解 (PMF) 算法等。这类方法的本质是尽 量完善推荐模型,但由于数据集本身过度稀疏, 以及数据的弱语义性导致推荐质量并不高。 2) 引入地理因素的推荐算法:在 LBSN 中,用 户与兴趣点的地理距离也是推荐的重要因素,这 也是有别于商品推荐的重要特征,这类算法将地 理信息融入到模型中,如文献 [6] 认为用户签到 的兴趣点在地理位置上是符合幂律分布,文献 [8] 则认为用户的活动区域是围绕多个中心点展 开的,进而引入了多中心高斯分布模型。事实证 明对地理信息建模有助于推荐效果的提升。 3) 引入社交影响的推荐算法:这类方法认为 社交网络上的“朋友”拥有相同的兴趣爱好,结合 朋友的签到访问历史记录进行推荐,如文 献 [9] 利用相似用户进行推荐时,直接利用好友进行 推荐,而忽略 LBSN 中其他用户。文献 [8] 将社交 关系直接融入到矩阵分解 (PMF) 算法中,但是实 验证明社交关系对推荐准确率的影响不大。 还有一些方法同时考虑了地理因素、用户的 偏好以及社交关系。如文献 [10] 设计了一种 UPS (user, proximity and social-based) 算法,将社交影响 因子融合到基于用户偏好的协同过滤算法中,以 此来提高用户相似度计算的准确性。实验证明该 算法在稀疏数据环境下的推荐效果并不是很好, 而且该算法没有考虑用户在不同的地理位置的影 响。文献 [11] 提出了 USG (user, social and geographical influence based recommendation) 推荐算 法,综合考虑了用户偏好、社交影响和地理影响, 采用线性融合技术集成这 3 种因素,以此来提高 算法的准确率。该方法虽然考虑了地理因素,但 是只考虑了用户常驻地特征,推荐的地点都是常 驻地附近区域,而且算法的参数不能自适应地调 节。此外还有很多学者利用概率产生式模型对位 置社交网络的推荐系统进行研究,将影响用户签 到决策的各种因素进行综合考虑和集成,比如文 献 [12] 提出的 LCARS 系统从用户兴趣、地理位 置、兴趣点当地特色 3 个方面分析,来对用户的 签到行为进行建模,文献 [13] 提出的 JUMAI 系统 更是从用户兴趣、兴趣点所在区域与用户所在区 域的距离、签到时间,以及兴趣点类别 4 个角度 来指导签到决策。文献 [14] 在此基础上还考虑了 用户在新的地点会产生兴趣漂移情况。但是这些 模型均没有考虑兴趣点本身的内容,其次上述模 型在对各因素进行建模时,没有体现自适应的特 性,即针对不同的兴趣点,何种因素对决策起支 配作用。本文提出了用户−区域−内容主题模型, 真实地模拟了用户对兴趣点签到的决策过程,实 验证明在稀疏的数据集下有较理想的推荐效果。 ·780· 智 能 系 统 学 报 第 14 卷
第4期 涂飞:多特征融合的兴趣点推荐算法 ·781· 2用户一区域-内容主题模型 2.2模型的形式化 图2为用户-区域-内容联合推荐模型对应的 2.1模型介绍 概率图。该图右边的部分是一个简单的LDA模 用户是否会对特定的兴趣点签到,会受到以 型,构造了兴趣点描述文档的生成过程。当用户 下3种因素的影响: u对兴趣点l.签到时l的介绍文档d已经存在,文 1)用户自身偏好的影响:一般来说,只有兴 档和单词的主题分布可分别独立计算。当用户对 趣点满足用户的喜好,用户才会欣然前往并产生 兴趣点l签到时,首先要确定l的主题z,z有 签到行为。比如球迷可能去看CBA联赛,而音乐 3种来源,分别为兴趣点介绍文档d中出现过的 爱好者可能去听演唱会。 主题、用户的兴趣以及兴趣点所属地理区域的主 2)兴趣点自身内容的影响:LBSN中基本包 题。采用选择变量X来控制兴趣点的主题z的来 含了对兴趣点的介绍信息,图1是豆瓣活动网站 源,X满足多项式分布,其值分别为user、re- 的页面信息,该页面显示了活动的时间、地点以 gion和content。 及主题。当用户浏览该页面时,可能被活动的主 题信息中某个特征所吸引,才促使了用户的签到 行为。 我8 【书影同观】斯蒂芬·金的异想世界 —第一期《头号书迷) MISTRY 时近候阴日月入70口为 t5上海规a区公省10号8r9n-园Ccat0 古系免功 进市在⅓ 三方县5人时及线酒 节人当图4人烟 活动主盟 到 叉红,应止好数书人期已州件 图1兴趣点简介 Fig.1 A brief introduction of interest points 3)兴趣点所属区域的影响。用户根据自身爱 图2用户区域-内容联合推荐模型 Fig.2 User-content-region based joint recommendation 好或是事先知晓兴趣点的内容而产生的签到行为 model 可认为是有目的,有主观倾向性的。但并不是所 假设模型中用户集合为U,兴趣点集合为L, 有的访问签到行为都是如此。用户的某次签到行 介绍文档集合为D,单词集合为W,区域集合为 为可能开始是漫无目的的,只是随机选择某一地 R,以及主题集合为K,具体生成过程如下: 理区域的某一兴趣点。但是此处的随机也受以下 l)对于任意文档d(deD),根据Dirichlet((aa) 两点约束:1)兴趣点所属区域离用户的距离。当 分布得到文档d在主题上的多项式分布x。 该区域离用户较近时,被用户访问的概率较大, 2)对于任意主题k(keK),根据Dirichlet(Bw)分 否则访问概率较小。2)区域的主题。当用户外出 布可得到词w在主题k上的概率分布;根据 到新的区域时,对该区域一无所知,也无法从其 Dirichlet(B)分布可得到兴趣点I在主题k上的分 ‘相似用户”获得信息,在做决策是否访问某一兴 布p"o 趣点时,往往会受到该区域主题的影响。比如该 3)对于任意用户(u∈U),根据Dirichlet(a)得 区域的风俗习惯、当地人的兴趣喜好,或是当地 到用户u的主题分布mk,根据Dirichlet(a,)得到区 比较著名的人文景点等。 域r的主题分布gnx,根据Dirichlet(ar)得到用户u 用户对兴趣点签到,必定是受到以上3种因 在区域r上分布m。 素其中之一的影响。因此本文提出了一种基于用 4)长度为Na的文档d中,词w的生成过程为: 户-区域-内容的联合推荐模型,利用隐主题因子 ①根据文档d的主题分布x抽样获得主题; 表示上述3种因素,将用户对3种因素的选择过 ②利用单词在上的概率分布,抽样产生 程进行建模。 单词w:o
2 用户−区域−内容主题模型 2.1 模型介绍 用户是否会对特定的兴趣点签到,会受到以 下 3 种因素的影响: 1) 用户自身偏好的影响:一般来说,只有兴 趣点满足用户的喜好,用户才会欣然前往并产生 签到行为。比如球迷可能去看 CBA 联赛,而音乐 爱好者可能去听演唱会。 2) 兴趣点自身内容的影响:LBSN 中基本包 含了对兴趣点的介绍信息,图 1 是豆瓣活动网站 的页面信息,该页面显示了活动的时间、地点以 及主题。当用户浏览该页面时,可能被活动的主 题信息中某个特征所吸引,才促使了用户的签到 行为。 图 1 兴趣点简介 Fig. 1 A brief introduction of interest points 3) 兴趣点所属区域的影响。用户根据自身爱 好或是事先知晓兴趣点的内容而产生的签到行为 可认为是有目的,有主观倾向性的。但并不是所 有的访问签到行为都是如此。用户的某次签到行 为可能开始是漫无目的的,只是随机选择某一地 理区域的某一兴趣点。但是此处的随机也受以下 两点约束:1) 兴趣点所属区域离用户的距离。当 该区域离用户较近时,被用户访问的概率较大, 否则访问概率较小。2) 区域的主题。当用户外出 到新的区域时,对该区域一无所知,也无法从其 “相似用户”获得信息,在做决策是否访问某一兴 趣点时,往往会受到该区域主题的影响。比如该 区域的风俗习惯、当地人的兴趣喜好,或是当地 比较著名的人文景点等。 用户对兴趣点签到,必定是受到以上 3 种因 素其中之一的影响。因此本文提出了一种基于用 户−区域−内容的联合推荐模型,利用隐主题因子 表示上述 3 种因素,将用户对 3 种因素的选择过 程进行建模。 2.2 模型的形式化 u lu lu d lu lu z z d X z X 图 2 为用户−区域−内容联合推荐模型对应的 概率图。该图右边的部分是一个简单的 LDA 模 型,构造了兴趣点描述文档的生成过程。当用户 对兴趣点 签到时 的介绍文档 已经存在,文 档和单词的主题分布可分别独立计算。当用户对 兴趣点 签到时,首先要确定 的主题 , 有 3 种来源,分别为兴趣点介绍文档 中出现过的 主题、用户的兴趣以及兴趣点所属地理区域的主 题。采用选择变量 来控制兴趣点的主题 的来 源 , 满足多项式分布,其值分别为 user、 re - gion 和 content。 η λ x l ω z θ (d) αu θ (u) αd φ (ω) Nd K r u αr θ (r) D R U L βl βw Zu /Zd /Zl φ (l) 图 2 用户-区域-内容联合推荐模型 Fig. 2 User-content-region based joint recommendation model U L D W R K 假设模型中用户集合为 ,兴趣点集合为 , 介绍文档集合为 ,单词集合为 ,区域集合为 ,以及主题集合为 ,具体生成过程如下: d d ∈ D Dirichlet(αd) d θ (d) K 1) 对于任意文档 ( ),根据 分布得到文档 在主题上的多项式分布 。 k k ∈ K Dirichlet(βw) w k φ (w) k Dirichlet(βl) l k φ (l) k 2) 对于任意主题 ( ),根据 分 布可得到词 在主题 上的概率分布 ;根据 分布可得到兴趣点 在主题 上的分 布 。 u u ∈ U Dirichlet(αu) u θ (u) K Dirichlet(αr) r θ (r) K Dirichlet(αur) u r θ (ur) r 3) 对于任意用户 ( ),根据 得 到用户 的主题分布 ,根据 得到区 域 的主题分布 ,根据 得到用户 在区域 上分布 。 4) 长度为 Nd 的文档 d 中,词 wi 的生成过程为: θ (d) ①根据文档 d 的主题分布 K 抽样获得主题 zi; zi φ (w) zi wi ②利用单词在 上的概率分布 抽样产生 单词 。 第 4 期 涂飞:多特征融合的兴趣点推荐算法 ·781·
·782· 智能系统学报 第14卷 5)用户u对兴趣点1的签到过程如下: 2.3 确定参数值 ①根据Dirichlet()抽样得到,根据 模型中变量的联合概率分布为 Multinomial(d)分布得到控制值x; p(L,r,1,z,x,w)= ②如果x=document,.说明兴趣点的主题由文 p(w)p(,x,r,u)p(,r,ux)p(x)= 档d生成。此前已抽样得到文档d中所有单词的 p(w)(p(,x)p(x,)p(x user)+ (1) 主题集合{仁a.…,wu,根据Uniform(em.…,二a) p(I,x)p()p(x=document)+ 分布抽样生成兴趣点的主题: p(E,x)p(rlu)p()p(x region)) ③如果x=user,说明兴趣点的主题来自于的 由式(1)可知该模型需要估计以下6个参数: 用户的偏好:根据兴趣主题分布x抽样获得兴 1)文档的主题分布@;2)主题-词分布p(参数 趣点的主题; 1)、2)为基本LDA模型对应的参数,用于求 ④如果x=region,兴趣点的主题由兴趣点所 p(w):3)兴趣点的主题分布p(即p(3,x):4)用 属区域的主题生成,首先利用用户在区域,上 户兴趣分布;5)用户活动区域分布:6)选择 分布,得到区域r,根据区域r在主题k上的概 率分布k获得主题1。 概率1的多项式分布(即p(x) 6)最后利用兴趣点在主题上的概率分布 文中采用Gibbs抽样方法,过程如下,具体的 p得到1。 参数说明见表1。 表1模型参数说明 Table 1 Model parameter description 参数 含义 d、u、w、1、x、 变量的实例:d为文档,为用户,w为词,为兴趣点,x为控制开关.为主题,r为区域 K、U、D、W、R、L 主题的个数、用户的个数、文档的个数、词的个数、区域的个数、兴趣点的个数 Na d中的单词总数 C” 主题在文档d出现的次数 CWK 词属于主题k的次数 c 兴趣点属于主题的次数 c 用户u的兴趣为主题k的次数 nlj.uset.-j 兴趣点↓的主题来源于用户兴趣的次数 nlj.document.-j 兴趣点↓的主题来源于文档主题的次数 nlj.region.-j 兴趣点!,的主题来源于区域主题的次数 g 文档主题的分布 g) 主题词的分布 d 用户兴趣的分布 fur) 用户活动区域的分布 。 兴趣点的主题分布 dn 区域的主题分布 1 兴趣点的主题选择概率分布 au、aa、ar、ar、fe、Bi、刀 Dirichlet分布的超参数。 1)利用式(2)计算单词在主题上的后验概率, P(=k,x=userj,B,n)o 进而对单词的主题进行抽样, Ck C做+B, CP+ad C,+R。 P(=i=klwi,z-i,W-i,ad.B.)c ∑C,+Ka。∑Ct-,+lA (3 2C密,+Kac+项 刀uer+n4.et,-j (2) L+∑ 2)计算兴趣点主题的后验概率,分3种情况: ①当选择变量x=user时,抽样方程为 ②当选择变量x=document时,抽样方程为
5) 用户 u 对兴趣点 l 的签到过程如下: Dirichlet(η) λl Multinomial(λl) x ①根据 抽样得到 , 根 据 分布得到控制值 ; x = document d d {zw1 ,zw2 , ··· ,zwNd } Uniform(zw1 ,zw2 , ··· ,zwNd ) zl ②如果 ,说明兴趣点的主题由文 档 生成。此前已抽样得到文档 中所有单词的 主题集合 ,根据 分布抽样生成兴趣点的主题 ; x = user θ (u) K zl ③如果 ,说明兴趣点的主题来自于的 用户的偏好:根据兴趣主题分布 抽样获得兴 趣点的主题 ; x = region u r θ (ur) r r r k θ (r) k zl ④如果 ,兴趣点的主题由兴趣点所 属区域的主题生成,首先利用用户 在区域 上 分布 得到区域 , 根据区域 在主题 上的概 率分布 获得主题 。 zl φ (l) zl l 6) 最后利用兴趣点在主题 上的概率分布 得到 。 2.3 确定参数值 模型中变量的联合概率分布为 p(u,r,l,z, x,w) = p(w)p(l|z, x,r,u)p(z,r,u|x)p(x) = p(w)(p(l|z, x)p(z|x, θu )p(x = user)+ p(l|z, x)p(z|x, θd )p(x = document)+ p(l|z, x)p(r|u)p(z|x, θr )p(x = region)) (1) θ (d) φ (w) p(w) φ (l) p(l|z, x) θ (u) θ (ur) λ p(x) 由式 (1) 可知该模型需要估计以下 6 个参数: 1) 文档的主题分布 ;2) 主题−词分布 (参数 1)、 2) 为 基 本 LDA 模型对应的参数,用于求 );3) 兴趣点的主题分布 (即 );4) 用 户兴趣分布 ;5) 用户活动区域分布 ;6) 选择 概率 的多项式分布 (即 )。 文中采用 Gibbs 抽样方法,过程如下,具体的 参数说明见表 1。 表 1 模型参数说明 Table 1 Model parameter description 参数 含义 d、u、w、l、x、z 变量的实例:d为文档,u为用户,w为词,l为兴趣点,x为控制开关,z为主题,r为区域 K、U、D、W、R、L 主题的个数、用户的个数、文档的个数、词的个数、区域的个数、兴趣点的个数 Nd d中的单词总数 C KD kd,−i 主题k在文档d出现的次数 C WK vk,−i 词v属于主题k的次数 C LK lk,−j 兴趣点l属于主题k的次数 C KU ku,−i 用户u的兴趣为主题k的次数 nlj ,user,−j 兴趣点 lj 的主题来源于用户兴趣的次数 nlj ,document,−j 兴趣点 lj 的主题来源于文档主题的次数 nlj ,region,−j 兴趣点 lj 的主题来源于区域主题的次数 θ (d) 文档主题的分布 φ (w) 主题词的分布 θ (u) 用户兴趣的分布 θ (ur) 用户活动区域的分布 φ (l) 兴趣点的主题分布 θ (r) 区域的主题分布 λl 兴趣点的主题选择概率分布 αu、αd、αur、αr、βw、βl、η Dirichlet分布的超参数。 1) 利用式 (2) 计算单词在主题上的后验概率, 进而对单词的主题进行抽样, P(zi = k|wi ,z−i ,w−i ,αd, βw) ∝ C KD kd,−i +αd ∑ k ′ C KD kd,−i +Kαd · C WK wk,−i +βw ∑ w′ C WK wk,−i +Vβw (2) 2) 计算兴趣点主题的后验概率,分 3 种情况: ①当选择变量 x=user 时,抽样方程为 P(zj = k, x = user|lj ,z−j ,αu, βl ,η) ∝ C KU ku,−j +αu ∑ k ′ C KU k ′u,−j +Kαu · C LK lk,−j +βl ∑ l ′ C LK l ′k,−j + Lβl · ηuser +nlj,user,−j L+ ∑ x∈{user,region,document} ηx (3) ②当选择变量 x=document 时,抽样方程为 ·782· 智 能 系 统 学 报 第 14 卷
第4期 涂飞:多特征融合的兴趣点推荐算法 ·783· P(j=k,x=documentlj,=j.B,n)o 直接根据式(16)来计算: Cf C+Br dcument +docment.- (4) N∑C+邛,L+ p(Id,u)= ∑psn-e (16) xeluser,region,document) k= ③当选择变量x=region时,抽样方程为 这也在一定程度上解决了用户或资源的冷启 P(=k.r=r,x=regionllj=jaauBi.n) 动问题。 Chm C+a, 2C,+Rar卫C-,+Ka, 3实验结果与分析 (5) C张+B,刀em+meim- 3.1 数据集 CLBL+ 豆瓣活动是我国最大的社交网络,用户可以 xeluser.region.document) 当式(2)(⑤)迭代一定次数后状态稳,可用式 在该平台上发布和参与各类活动并签到。该数据 (6)(14)近似计算模型的参数值。 集包含了100000多个用户,300000个事件,以 gd= Ckp +aa 及3500000条签到记录。本文经过预处理后选 ∑C阳+Kaa (6) 择了其中20000个用户、15000个活动的150000 条签到记录作为实验数据集。 p= Cw+B。 (7) Foursquare是一个大型的公开数据集,该数据 ΣCK+wBR 集包含11326个用户,182968个兴趣点,实验中 m=+a. 通过筛选选择其中10000个用户、25000个兴趣 C+Ko. (8) 点进行分析。 0= C+Br 3.2实验结果 (9) ∑CW+L邛 为了验证算法的准确性,本文采用了文献[15] 提出的评估方法,具体如下: = CRu au (10) ∑CRr+Rar 1)对于任意用户“,随机选择其签到数据中 的90%作为训练集S,剩余的10%作为测试数据 n= CkR+ar C+Ka. (11) 集T。由于本文要分别计算算法对本地兴趣点和 外地兴趣点推荐的准确率,T根据不同的情况划 刀user+TLaser (12) 分为本地数据和外地数据(以兴趣点所属城市来 区分) Idocument+.document 2)在测试过程中,随机选择用户“尚未签到 (13) 的200个活动构成集合E,假设这些活动是用户 refuser.region.document] nhregion+nregion 不感兴趣的。 (14) 3)将包含用户u的测试集中任意活动e加入 到E中构成201个新的活动集合,根据推荐算法 2.4模型的推荐 选择评分最高的前200个活动作为top-200推荐 估计模型参数后便可用于在线推荐阶段。对 列表,如果活动e出现在推荐列表中,将hits增l, 于特定的用户“、兴趣点1以及其对应的介绍文档 否则hits保持不变(hits为评分常量)。 d,根据式(15)可得u对I签到概率: 4)评估标准查全率为 p(Id.u)=p(x=d)>p()Pwa(ld)+ Recall=#hits ITI (17) k=1 本文选择以下4种算法进行比较: p(x=u)>p()p(=lu)+p(x=r) p(rlu)p(r) I)文献[I7]提出的IKNN算法(item-based k- (15) nearest neighbors algorithm),该算法利用“近邻用 式中p()、p(x、p(eo)、pt0)、p(r)、Pea(eld可 户”来推荐感兴趣的活动,然后根据活动地点离用 以通过模型训练获得。如果是新的兴趣点1,可以 户的远近进行过滤,优先选择离用户较近的感兴 先将其对应文档d的主题分布p(ald在线计 趣的活动。 算,即将文档d加入到测试集D中,重新用 2)文献[I6]提出了CKNN算法(category- Gibbs抽样的方法获得。如果是新的用户,可以 based k-nearest neighbors algorithm),该方法实质上
P(zj = k, x = document|lj ,z−j , βl ,η) ∝ C KD kd Nd · C LK lk +βl ∑ l ′ C LK l ′k + Lβl · ηdocument +nlj,document,−j L+ ∑ x∈{user,region,document} ηx (4) ③当选择变量 x=region 时,抽样方程为 P(zj = k,rj = r, x = region|lj ,z−j ,αu,αur , βl ,η) ∝ C RU ru,−j +αur ∑ r ′ C RU r ′u,−j +Rαur · C KR kr,−j +αr ∑ k ′ C KR k ′r,−j +Kαr · C LK lk,−j +βl ∑ l ′ C LK l ′k,−j + Lβl · ηregion +nlj,region,−j L+ ∑ x∈{user,region,document} ηx (5) 当式 (2)~(5) 迭代一定次数后状态稳,可用式 (6)~(14) 近似计算模型的参数值。 θ (d) = C KD kd +αd ∑ k ′ C KD k ′d +Kαd (6) φ (w) = C WK wk +βw ∑ w′ C WK w′k + Wβw (7) θ (u) = C KU ku +αu ∑ k ′ C KU k ′u +Kαu (8) φ (l) = C LK lk +βl ∑ l ′ C LK l ′k + Lβl (9) θ (ur) = C RU ru +αur ∑ r ′ C RU r ′u +Rαur (10) θ (r) = C KR kr +αr ∑ k ′ C KR k ′r +Kαr (11) λl,user = ηuser +nl,user L+ ∑ x∈{user,region,document} ηx (12) λl,document = ηdocument +nl,document L+ ∑ x∈{user,region,document} ηx (13) λl,region = ηregion +nl,region L+ ∑ x∈{user,region,document} ηx (14) 2.4 模型的推荐 u d u 估计模型参数后便可用于在线推荐阶段。对 于特定的用户 、兴趣点 l 以及其对应的介绍文档 ,根据式 (15) 可得 对 l 签到概率: p(l|d,u) = p(x = d) ∑K k=1 p(l|zk)ptest(zk |d)+ p(x = u) ∑K k=1 p(l|zk)p(zk |u)+ p(x = r) ∑R r=1 ∑K k=1 p(r|u)p(zk |r) (15) p(l|zk) p(x) p(zk |u) p(r|u) p(zk |r) ptest(zk |d) ptest(zk |d) 式中 、 、 、 、 、 可 以通过模型训练获得。如果是新的兴趣点 l,可以 先将其对应文档 d 的主题分布 在线计 算,即将文 档 d 加入到测试 集 D 中,重新 用 Gibbs 抽样的方法获得。如果是新的用户,可以 直接根据式 (16) 来计算: p(l|d,u) = ∑K k=1 p(l|zk)ptest(zk |d) (16) 这也在一定程度上解决了用户或资源的冷启 动问题。 3 实验结果与分析 3.1 数据集 豆瓣活动是我国最大的社交网络,用户可以 在该平台上发布和参与各类活动并签到。该数据 集包含了 100 000 多个用户,300 000 个事件,以 及 3 500 000 条签到记录。本文经过预处理后选 择了其中 20 000 个用户、15 000 个活动的 150 000 条签到记录作为实验数据集。 Foursquare 是一个大型的公开数据集,该数据 集包含 11 326 个用户,182 968 个兴趣点,实验中 通过筛选选择其中 10 000 个用户、25 000 个兴趣 点进行分析。 3.2 实验结果 为了验证算法的准确性,本文采用了文献 [15] 提出的评估方法,具体如下: 1) 对于任意用户 u,随机选择其签到数据中 的 90% 作为训练集 S,剩余的 10% 作为测试数据 集 T。由于本文要分别计算算法对本地兴趣点和 外地兴趣点推荐的准确率,T 根据不同的情况划 分为本地数据和外地数据 (以兴趣点所属城市来 区分)。 2) 在测试过程中,随机选择用户 u 尚未签到 的 200 个活动构成集合 E,假设这些活动是用户 不感兴趣的。 3) 将包含用户 u 的测试集中任意活动 e 加入 到 E 中构成 201 个新的活动集合,根据推荐算法 选择评分最高的前 200 个活动作为 top-200 推荐 列表,如果活动 e 出现在推荐列表中,将 hits 增 1, 否则 hits 保持不变 (hits 为评分常量)。 4) 评估标准查全率为 Recall = #hits |T| (17) 本文选择以下 4 种算法进行比较: 1) 文献 [17] 提出的 IKNN 算法 (item-based knearest neighbors algorithm),该算法利用 “近邻用 户”来推荐感兴趣的活动,然后根据活动地点离用 户的远近进行过滤,优先选择离用户较近的感兴 趣的活动。 2) 文献 [16] 提出了 CKNN 算法 (categorybased k-nearest neighbors algorithm),该方法实质上 第 4 期 涂飞:多特征融合的兴趣点推荐算法 ·783·
·784· 智能系统学报 第14卷 也是协同过滤,将用户的兴趣映射到具体的主 450 ◆K=10 题,进而进行推荐。 425 ■-K=20 ▲K=40 3)文献[11]提出的USG推荐算法,该算法的 400 X-K=80 米-K=160 核心思想还是协同过滤,线性框融合用户偏好、 375 社交影响和地理影响这3种因子。 4)User-Content Topic Model(UCTM)模型和 325 User-Region Topic Model(URTM)模型,这两 300 种模型可看作UCRTM模型的子模型。当 275 document=O时,此时模型忽略兴趣点介绍文档的内 250 40 60 80 容信息,UCRTM模型退化为URTM模型。当 迭代次数 Leem=0时,此时模型忽略兴趣点所处区域的主题 图3困惑度在不同隐含主题下的变化情况 信息,UCRTM模型退化为UCTM模型。 Fig.3 The perplexity changes in the number of different 3.3实验结果 hidden themes 该模型有9个超参数需要设置,对于主题模 400 ◆-R=5 型来说,超参数的值对最后的输出结果影响不 -R=10 375 ★-R=20 大,但是会影响模型的收敛速度,这里设置α、 ×-R=30 350 米-R=40 aa、ar、ar为0.1,Be、B为0.05,所有n的值为 0.01。 325 1)UCRTM模型为概率产生式模型,本文使 300 用困惑度(Perplexity)作为评价标准,对本模型的 275 预测能力进行评估,判断测试集Dtest中兴趣点生 250 成的不确定性,Perplexity的值越小,表示模型生 0 20 40 60 80 迭代次数 成兴趣点的性能越好。Perplexity的计算式为 D 图4困惑度随不同隐含区域下的变化情况 log(p(la) Fig.4 The perplexity changes in the number of different =l Perplexity(Des)=exp (18) hidden region Dest 2)其次比较了各种算法的推荐准确率,因为 式中p(1)由式(15)或(16)得出。由于本模型中 用户的签到具有地域聚集性,本文将测试集分为 包含了两个隐含变量(主题数K和区域数R),为 两类:用户的本地活动测试集、用户的外地活动 了分析这两个变量对模型生成能力的影响,首先 测试集。对豆瓣数据集和Foursquare数据集进行 固定隐含区域数,来观察Perplexity随不同主题数 了分析。图5~8分别给出了6种算法在两种数据 的变化情况。 集下的top-N推荐准确率,推荐列表的长度N在 从图3可以看出,当区域个数固定为R=30 220变化。 时,对于不同的主题数,Perplexity均随着迭代次 0.45 -◆IKNN 数的增加不断减小,当迭代次数达到40次后, 0.40--CKNN Perplexity趋于收敛。而且Perplexity还随着主题 0.35+USG 数K的增大不断减小,当主题数增加到一定程度 0.30 X-UCTM 米-URTM 后,Perplexity不会持续下降,反而会有一些回 0.25 UCRTM 升。如当K=160时,Perplexity的值相比于K=80 0.20 0.15 时反而增大了,这也在一定程度上说明,合适的 0.10 主题数K可以提高模型的推荐效果。同理固定 0.05 主题数K=8O,来观察隐含区域数R对Perplex- 0 ty的影响。如图4所示,区域数与主题数的变化 2468101214161820 情况类似,当R=30时,可以得到最小的Perplex- 图5豆瓣数据集外地活动的推荐准确率比较 ty值。因此本实验中主题数K设置为80,而区域 Fig.5 Comparison of recommended accuracy out of town 数R为30。 for Douban dataset
也是协同过滤,将用户的兴趣映射到具体的主 题,进而进行推荐。 3) 文献 [11] 提出的 USG 推荐算法,该算法的 核心思想还是协同过滤,线性框融合用户偏好、 社交影响和地理影响这 3 种因子。 λl,document λl,region 4) User-Content Topic Model(UCTM) 模型和 User-Region Topic Model (URTM) 模型,这两 种模型可看 作 UCRT M 模型的子模型。当 =0 时,此时模型忽略兴趣点介绍文档的内 容信息,UCRTM 模型退化为 URTM 模型。当 =0 时,此时模型忽略兴趣点所处区域的主题 信息,UCRTM 模型退化为 UCTM 模型。 3.3 实验结果 αu αd αur αr βw βl η 该模型有 9 个超参数需要设置,对于主题模 型来说,超参数的值对最后的输出结果影响不 大,但是会影响模型的收敛速度,这里设置 、 、 、 为 0.1, 、 为 0.05, 所有 的值为 0.01。 1) UCRTM 模型为概率产生式模型,本文使 用困惑度 (Perplexity) 作为评价标准, 对本模型的 预测能力进行评估,判断测试集 Dtest 中兴趣点生 成的不确定性,Perplexity 的值越小,表示模型生 成兴趣点的性能越好。Perplexity 的计算式为 Perplexity(Dtest) = exp − D∑test d=1 log(p(ld)) |Dtest| (18) K R 式中 p(ld ) 由式 (15) 或 (16) 得出。由于本模型中 包含了两个隐含变量 (主题数 和区域数 ),为 了分析这两个变量对模型生成能力的影响,首先 固定隐含区域数,来观察 Perplexity 随不同主题数 的变化情况。 从图 3 可以看出,当区域个数固定为 R=30 时,对于不同的主题数,Perplexity 均随着迭代次 数的增加不断减小,当迭代次数达到 40 次后, Perplexity 趋于收敛。而且 Perplexity 还随着主题 数 K 的增大不断减小,当主题数增加到一定程度 后 ,Perplexity 不会持续下降,反而会有一些回 升。如当 K=160 时, Perplexity 的值相比于 K=80 时反而增大了,这也在一定程度上说明,合适的 主题数 K 可以提高模型的推荐效果。同理固定 主题数 K=80,来观察隐含区域数 R 对 Perplexity 的影响。如图 4 所示,区域数与主题数的变化 情况类似,当 R=30 时,可以得到最小的 Perplexity 值。因此本实验中主题数 K 设置为 80,而区域 数 R 为 30。 250 275 300 325 350 375 400 425 450 困惑度 10 20 40 60 80 迭代次数 K = 10 K = 20 K = 40 K = 80 K = 160 图 3 困惑度在不同隐含主题下的变化情况 Fig. 3 The perplexity changes in the number of different hidden themes 250 275 300 325 350 375 400 困惑度 10 20 40 60 80 迭代次数 R = 5 R = 10 R = 20 R = 30 R = 40 图 4 困惑度随不同隐含区域下的变化情况 Fig. 4 The perplexity changes in the number of different hidden region 2) 其次比较了各种算法的推荐准确率,因为 用户的签到具有地域聚集性,本文将测试集分为 两类:用户的本地活动测试集、用户的外地活动 测试集。对豆瓣数据集和 Foursquare数据集进行 了分析。图 5~8 分别给出了 6 种算法在两种数据 集下的 top-N 推荐准确率,推荐列表的长度 N 在 2~20 变化。 0 0.05 0.10 0.15 0.20 0.25 0.30 0.35 0.40 0.45 2 4 6 8 10 12 14 16 18 20 查全率 N IKNN CKNN USG UCTM URTM UCRTM 图 5 豆瓣数据集外地活动的推荐准确率比较 Fig. 5 Comparison of recommended accuracy out of town for Douban dataset ·784· 智 能 系 统 学 报 第 14 卷
第4期 涂飞:多特征融合的兴趣点推荐算法 ·785· 0.45r ◆IKNN 点的隐含主题同时由用户兴趣分布、兴趣点介绍 0.40 CKNN 文档主题分布以及兴趣点所属区域的主题分布的 0.35 士USG 0.30 -x-UCTM 影响,这些信息是对用户签到数据的有益补充。 部0.25 米URTM g020 UCTM和URTM均只考虑了其中两方面的影响, ◆-UCRTM 所以其推荐的准确程度不如UCRTM模型。 0.15 由图7和图8可以看出,在本地活动推荐中, 0.10 0.05 UCRTM模型同样优于其他各种方法,但考虑到 用户本地签到的数据较多,采用协同过滤类的算 2 4 6 8101214161820 N 法本身能够准确计算用户的相似性,不需要其他 图6 Foursquare数据外地活动的推荐准确率比较 补充信息也能获得较高的准确率,因此最终各种 Fig.6 Comparison of recommended accuracy out of town 方法的性能差距不大。但是本模型能够扩展更多 for Foursquare dataset 的上下文信息,可靠性更高。 0.50 0.45 4结束语 0.40 0.35 本文提出的用户-区域-内容联合推荐模型能 银0.30 够克服数据稀疏性以及弱语义性的影响,与其他 州0.25 0.20 方法相比有较高的推荐的准确率。以后还将进一 0.15 步改善模型,增加环境、时间等上下文因素。其 0.10 ◆IKNN -UCTM 次该模型除了应用于兴趣点推荐外,还能将学习 0.05 -USG ●-UCRTM 0 出的重要参数(如用户的兴趣爱好、用户的活动 68101214161820 布 特性、地理区域的主题等)用于其他的web服 务中。 图7豆瓣数据集本地活动的推荐准确率比较 Fig.7 Comparison of recommended accuracy in locality 参考文献: for Douban dataset 0.50 [1]罗军舟,吴文甲,杨明.移动互联网:终端、网络与服务 0.45 [).计算机学报,2011,3411):2029-2051. 0.40 LUO Junzhou,WU Wenjia,YANG Ming.Mobile internet: 0.35 0.30 terminal devices networks and services[J.Chinese Journ- al of Computers..2011,3411):2029-2051. 0.20 ◆IKNN [2]YU Fei,CHE Nan,LI Zhijun,et al.Friend recommenda- CKNN 0.15 士USG tion considering preference coverage in location-based so- 0.10 UCTM 米URTM cial networks[C]//Proceedings of the 21st Pacific-Asia 0.05 ◆-UCRTM 0 Conference,Advances in Knowledge Discovery and Data 68101214161820 Mining.Jeju,South Korea,2017:91-105. [3]ZHAO Yan,ZHU Jia,JIA Mengdi,et al.A novel hybrid 图8 Foursquare数据本地活话动的推荐确率比较 friends recommendation framework for twitter[C]//Pro- Fig.8 Comparison of recommended accuracy in locality for Foursquare dataset ceedings of the First International Joint Conference,Web and Big Data.Beijing,China,2017:83-97. 由图5和图6可以看出,随着N的不断增加, 各种算法的准确率都是不断提高的。对于外地活 [4]YU Yonghong,WANG Hao,SUN Shuanzhu,et al.Ex- ploiting location significance and user authority for point- 动的推荐,UCRTM、UCTM、URTM优于USG、CK of-interest recommendation[C]//Proceedings of the 21st NN、IKNN算法,因为后3种方法为协同过滤算 Pacific-Asia Conference,Advances in Knowledge Discov- 法,数据的稀疏性对其影响较大,用户或地点相 ery and Data Mining.Jeju,South Korea,2017:119-130. 似性在稀疏的环境下计算不准确,导致推荐准确 [5]INTERDONATO R.INTERDONATO A.Personalized re- 率不高。由于USG算法考虑了社交好友的影响, commendation of points-of-interest based on multilayer 推荐效果略好于CKNN和IKNN算法。而隐含主 local community detection[C]//Proceedings of the 9th In- 题模型受数据稀疏性的影响较小,在模型中兴趣 ternational Conference,Social Informatics.Oxford,2017:
0 0.05 0.10 0.15 0.20 0.25 0.30 0.35 0.40 0.45 2 4 6 8 10 12 14 16 18 20 查全率 N IKNN CKNN USG UCTM URTM UCRTM 图 6 Foursquare 数据外地活动的推荐准确率比较 Fig. 6 Comparison of recommended accuracy out of town for Foursquare dataset 0 0.05 0.10 0.15 0.20 0.25 0.30 0.35 0.40 0.45 0.50 2 4 6 8 10 12 14 16 18 20 查全率 N IKNN CKNN USG UCTM URTM UCRTM 图 7 豆瓣数据集本地活动的推荐准确率比较 Fig. 7 Comparison of recommended accuracy in locality for Douban dataset 0 0.05 0.10 0.15 0.20 0.25 0.30 0.35 0.40 0.45 0.50 2 4 6 8 10 12 14 16 18 20 查全率 N IKNN CKNN USG UCTM URTM UCRTM 图 8 Foursquare 数据本地活动的推荐确率比较 Fig. 8 Comparison of recommended accuracy in locality for Foursquare dataset 由图 5 和图 6 可以看出,随着 N 的不断增加, 各种算法的准确率都是不断提高的。对于外地活 动的推荐,UCRTM、UCTM、URTM 优于 USG、CKNN、IKNN 算法,因为后 3 种方法为协同过滤算 法,数据的稀疏性对其影响较大,用户或地点相 似性在稀疏的环境下计算不准确,导致推荐准确 率不高。由于 USG 算法考虑了社交好友的影响, 推荐效果略好于 CKNN 和 IKNN 算法。而隐含主 题模型受数据稀疏性的影响较小,在模型中兴趣 点的隐含主题同时由用户兴趣分布、兴趣点介绍 文档主题分布以及兴趣点所属区域的主题分布的 影响,这些信息是对用户签到数据的有益补充。 UCTM 和 URTM 均只考虑了其中两方面的影响, 所以其推荐的准确程度不如 UCRTM 模型。 由图 7 和图 8 可以看出,在本地活动推荐中, UCRTM 模型同样优于其他各种方法,但考虑到 用户本地签到的数据较多,采用协同过滤类的算 法本身能够准确计算用户的相似性,不需要其他 补充信息也能获得较高的准确率,因此最终各种 方法的性能差距不大。但是本模型能够扩展更多 的上下文信息,可靠性更高。 4 结束语 本文提出的用户−区域−内容联合推荐模型能 够克服数据稀疏性以及弱语义性的影响,与其他 方法相比有较高的推荐的准确率。以后还将进一 步改善模型,增加环境、时间等上下文因素。其 次该模型除了应用于兴趣点推荐外,还能将学习 出的重要参数 (如用户的兴趣爱好、用户的活动 特性、地理区域的主题等) 用于其他的 web 服 务中。 参考文献: 罗军舟, 吴文甲, 杨明. 移动互联网: 终端、网络与服务 [J]. 计算机学报, 2011, 34(11): 2029–2051. LUO Junzhou, WU Wenjia, YANG Ming. Mobile internet: terminal devices networks and services[J]. Chinese Journal of Computers, 2011, 34(11): 2029–2051. [1] YU Fei, CHE Nan, LI Zhijun, et al. Friend recommendation considering preference coverage in location-based social networks[C]//Proceedings of the 21st Pacific-Asia Conference, Advances in Knowledge Discovery and Data Mining. Jeju, South Korea, 2017: 91–105. [2] ZHAO Yan, ZHU Jia, JIA Mengdi, et al. A novel hybrid friends recommendation framework for twitter[C]//Proceedings of the First International Joint Conference, Web and Big Data. Beijing, China, 2017: 83–97. [3] YU Yonghong, WANG Hao, SUN Shuanzhu, et al. Exploiting location significance and user authority for pointof-interest recommendation[C]//Proceedings of the 21st Pacific-Asia Conference, Advances in Knowledge Discovery and Data Mining. Jeju, South Korea, 2017: 119–130. [4] INTERDONATO R, INTERDONATO A. Personalized recommendation of points-of-interest based on multilayer local community detection[C]//Proceedings of the 9th International Conference, Social Informatics. Oxford, 2017: [5] 第 4 期 涂飞:多特征融合的兴趣点推荐算法 ·785·
·786· 智能系统学报 第14卷 552-571 [12]YIN Hongzhi,CUI Bin,SUN Yizhou,et al.LCARS:A [6]YU Yonghong,GAO Yang,WANG Hao,et al.Joint user spatial item recommender system[J].ACM Transactions knowledge and matrix factorization for recommender sys- on Information Systems,2014,32(3):11. tems[Cl//Proceedings of the 17th International Conference, [13]YIN Hongzhi,CUI Bin,Zhou Xiaofang,et al.Joint mod- Web Information Systems Engineering.Shanghai,China, eling of user check-in behaviors for real-time point-of-in- 2016:77-91. terest recommendation[J].ACM Transactions on Informa- [7]BERJANI B,STRUFE T.A recommendation system for tion Systems,2016,35(2):11. spots in location-based online social networks[C]//Proceed- [14]YIN Hongzhi,ZHOU Xiaofang,CUI Bin,et al.Adapting ings of the 4th Workshop on Social Network Systems. to user interest drift for poi recommendation[J].IEEE Salzburg,Austria,2011:4. Transactions on Knowledge and Data Engineering,2016, [8]CHENG Chen,YANG Haiqin,KING I,et al.Fused mat- 28(10:2566-2581. [15]CREMONESI P.KOREN Y.TURRIN R.Performance of rix factorization with geographical and social influence in recommender algorithms on top-n recommendation location-based social networks[Cl//Proceedings of the 26th AAAI Conference on Artificial Intelligence.Toronto, tasks[Cl//Proceedings of the 4th ACM Conference on Re- commender Systems.Barcelona.Spain,2010:39-46. Canada,2012:17-23. [9]YE Mao,YIN Peifeng,LEE W C.Location recommenda- [16]BAO Jie,ZHENG Yu,MOKBEL M F.Location-based tion for location-based social networks[C]//Proceedings of and preference-aware recommendation using sparse geo- social networking data[C]//Proceedings of the 20th Inter- the 18th SIGSPATIAL International Conference on Ad- national Conference on Advances in Geographic Informa- vances in Geographic Information Systems.San Jose, tion Systems.Redondo Beach,USA,2012:199-208. USA,2010:458-461. [17]LINDEN G.SMITH B.YORK J.Amazon.com recom- [10]FERENCE G,YE Mao,LEE W C.Location recommend- mendations:item-to-item collaborative filtering[J].IEEE ation for out-of-town users in location-based social net- Internet Computing,2003,7(1):76-80. works[C]//Proceedings of the 22nd ACM International Conference on Information and Knowledge Management. 作者简介: San Francisco,USA,2013:721-726. 涂飞,男,1979年生,讲师,主要 研究方向为服务计算、推荐系统。主 [11]YE Mao,YIN Peifeng,LEE W C,et al.Exploiting geo- 持并参研省部级以上科研项目7项。 graphical influence for collaborative point-of-interest re- commendation[C]//Proceedings of the 34th International ACM SIGIR Conference on Research and Development in Information Retrieval.Beijing,China,2011:325-334
552–571. YU Yonghong, GAO Yang, WANG Hao, et al. Joint user knowledge and matrix factorization for recommender systems[C]//Proceedings of the 17th International Conference, Web Information Systems Engineering. Shanghai, China, 2016: 77–91. [6] BERJANI B, STRUFE T. A recommendation system for spots in location-based online social networks[C]//Proceedings of the 4th Workshop on Social Network Systems. Salzburg, Austria, 2011: 4. [7] CHENG Chen, YANG Haiqin, KING I, et al. Fused matrix factorization with geographical and social influence in location-based social networks[C]//Proceedings of the 26th AAAI Conference on Artificial Intelligence. Toronto, Canada, 2012: 17–23. [8] YE Mao, YIN Peifeng, LEE W C. Location recommendation for location-based social networks[C]//Proceedings of the 18th SIGSPATIAL International Conference on Advances in Geographic Information Systems. San Jose, USA, 2010: 458–461. [9] FERENCE G, YE Mao, LEE W C. Location recommendation for out-of-town users in location-based social networks[C]//Proceedings of the 22nd ACM International Conference on Information and Knowledge Management. San Francisco, USA, 2013: 721–726. [10] YE Mao, YIN Peifeng, LEE W C, et al. Exploiting geographical influence for collaborative point-of-interest recommendation[C]//Proceedings of the 34th International ACM SIGIR Conference on Research and Development in Information Retrieval. Beijing, China, 2011: 325–334. [11] YIN Hongzhi, CUI Bin, SUN Yizhou, et al. LCARS: A spatial item recommender system[J]. ACM Transactions on Information Systems, 2014, 32(3): 11. [12] YIN Hongzhi, CUI Bin, Zhou Xiaofang, et al. Joint modeling of user check-in behaviors for real-time point-of-interest recommendation[J]. ACM Transactions on Information Systems, 2016, 35(2): 11. [13] YIN Hongzhi, ZHOU Xiaofang, CUI Bin, et al. Adapting to user interest drift for poi recommendation[J]. IEEE Transactions on Knowledge and Data Engineering, 2016, 28(10): 2566–2581. [14] CREMONESI P, KOREN Y, TURRIN R. Performance of recommender algorithms on top-n recommendation tasks[C]//Proceedings of the 4th ACM Conference on Recommender Systems. Barcelona, Spain, 2010: 39–46. [15] BAO Jie, ZHENG Yu, MOKBEL M F. Location-based and preference-aware recommendation using sparse geosocial networking data[C]//Proceedings of the 20th International Conference on Advances in Geographic Information Systems. Redondo Beach, USA, 2012: 199–208. [16] LINDEN G, SMITH B, YORK J. Amazon. com recommendations: item-to-item collaborative filtering[J]. IEEE Internet Computing, 2003, 7(1): 76–80. [17] 作者简介: 涂飞,男,1979 年生,讲师,主要 研究方向为服务计算、推荐系统。主 持并参研省部级以上科研项目 7 项。 ·786· 智 能 系 统 学 报 第 14 卷