邵阔义等：基于交通网络数据优化的地理信息推荐系统 ·1653· 立的模型来分类，可以分为基于领域的模型、基于图的 纬度进行计算（本文使用百度地图提供的Geocoding 推荐模型和基于矩阵分解的推荐模型等. API进行地理信息编码的操作).在进行空间中不同 本文采用的是协同过滤算法，其推荐思想是通过 点之间的距离计算后，推荐算法会根据两个地点间的 挖掘用户的历史行为数据记录来给用户推荐他们可能 距离远近对推荐结果进行调整.首先，使用最基本的 感兴趣的物品.文献5]第一次提出了协同过滤的推 两点间距离计算的方法，直接度量两点间的欧几里德 荐思想，并提出基于用户的协同过滤思想.在此基础 距离.由于地球是一个椭球体，而不是平面，因此不能 上，文献16)进一步提出基于物品的协同过滤思想. 直接对经纬度进行欧几里德距离计算.式(5)所示为 基于物品的协同过滤思想指出，用户会喜欢跟他 地球上两点间经纬度距离计算的公式： 以前喜欢的物品相似的物品。因此，根据该思想给用 户推荐他们感兴趣的物品，则必须先获得他以前喜欢 D=2arcsin Vsin?a +coscos :sin ×6378.137. 的物品信息，然后找到和这些物品相似的物品并推荐 (5) 给该用户.与基于用户的协同过滤不同，该算法思想 式中，p为纬度，a为两点之间的纬度的差值，b为两点 要求计算两个（或多个）物品的相似度.但与之相似的 之间经度的差值，而常数6378.137为地球半径（单位 是，该算法思想通过两个（或多个）物品被同时喜欢的 为km),这里所有的经纬度值都需要转化为弧度制. 用户数的多少来衡量相似度的大小.假设给定物品i 根据式(5)可以对使用经纬度表示的任意两点进 和j,令V()为喜欢物品i的用户集，N()为喜欢物品j 行欧几里德距离的计算.然而，直线距离更近的两个 的用户集，则物品i和物品j的相似度可以通过如下公 点并不能够代表这两个点的真实距离更近.例如，如 式衡量： 图2所示，图中两条横向直线为道路两侧，纵向图形为 sim(i,)=IN(i)N()I (1) N() 人行天桥，除该人行天桥外用户无法穿过该道路，A、B 用户在间隔很短的时间内产生的行为往往具有更 和C为三个商户位置，用户当前处于A处.可以看出 高的相似度，因此本文中使用的物品相似度计算方法 用户在A点时距离C更近，应向其推荐C处的商户. 采用下式n叼： 然而，从A到C需先经过B之后过天桥才能到达，远 1 超过A到B的距离.因此，向用户推荐C处的商户排 sim(ij)t 名不应该高于B处商户的排名. (2) √个N()IING)T 式中：α是时间衰减参数，其取值根据推荐系统的特点 不同而不同，如果系统中用户的兴趣变化快，则应当取 较大的a,否则取较小的a:Iia-tgI表示用户u对于 产品i和产品j产生行为的时间间隔 计算出物品之间的相似度后，基于物品的协同过 图2直线距离非最近距离的示意图 滤算法通过如下公式来衡量用户u对物品的兴趣大 Fig.2 Schematic diagram of closest distance 小： 通过图2所示的简单示例可以看出，对于推荐系 p(uj)=∑ sim(j,i). (3) 统而言，应当向用户推荐实际距离更近的物品，而不是 ics(.Anx(u) 其中，N(u)是用户u喜欢的物品数，S(i,k)表示与物 直线距离最近的物品.在实际生活中，这种实际距离 品i最相似的k件物品，「表示用户u对物品i的兴趣 远大于直线距离的情况十分常见. 偏好 1.2.2基于交通网络数据的距离计算 类似式(2)近期的行为更能体现用户当前的兴 基于交通网络数据进行距离计算可以提高推荐系 趣，应当在推荐时对其增加一定的权重7，则修正公 统推荐结果的准确性，为用户提供更好的使用体验 式(3)为 因此，在本节中将给出利用交通网络数据进行距离计 1 算的方法. p(u)=∑sim(,1+Bl。-a (4) iss(.DnN(u) 为了使用交通网络数据进行距离计算，必须借助 式中，。是当前时刻，B是衰减系数. 于成熟的地理信息系统，使用其关于两点间距离计算 1.2基于交通网络数据优化的地理信息推荐算法 或路径规划的API来获取到它们的实际距离.使用百 1.2.1基于经纬度的距离计算 度地图所提供的Direction API来进行距离计算，该API 基于地点上下文的推荐利用交通网络数据来度量 可以进行步行、驾车以及公交换乘三种形式的路径查 地图上两点之间的距离，因此需要利用各个地点的经 询，并返回json格式或者xml格式的查询结果数据.邵阔义等: 基于交通网络数据优化的地理信息推荐系统 立的模型来分类，可以分为基于领域的模型、基于图的 推荐模型和基于矩阵分解的推荐模型等． 本文采用的是协同过滤算法，其推荐思想是通过 挖掘用户的历史行为数据记录来给用户推荐他们可能 感兴趣的物品． 文献［15］第一次提出了协同过滤的推 荐思想，并提出基于用户的协同过滤思想． 在此基础 上，文献［16］进一步提出基于物品的协同过滤思想． 基于物品的协同过滤思想指出，用户会喜欢跟他 以前喜欢的物品相似的物品． 因此，根据该思想给用 户推荐他们感兴趣的物品，则必须先获得他以前喜欢 的物品信息，然后找到和这些物品相似的物品并推荐 给该用户． 与基于用户的协同过滤不同，该算法思想 要求计算两个( 或多个) 物品的相似度． 但与之相似的 是，该算法思想通过两个( 或多个) 物品被同时喜欢的 用户数的多少来衡量相似度的大小． 假设给定物品 i 和 j，令 N( i) 为喜欢物品 i 的用户集，N( j) 为喜欢物品 j 的用户集，则物品 i 和物品 j 的相似度可以通过如下公 式衡量: sim( i，j) = | N( i) ∩N( j) | N( i) ． ( 1) 用户在间隔很短的时间内产生的行为往往具有更 高的相似度，因此本文中使用的物品相似度计算方法 采用下式［17］: sim( i，j) u∈N ∑( i) ∩N( j) 1 1 + α | tui － tuj | 槡| N( i) | | N( j) | ． ( 2) 式中: α 是时间衰减参数，其取值根据推荐系统的特点 不同而不同，如果系统中用户的兴趣变化快，则应当取 较大的 α，否则取较小的 α; | tui － tuj | 表示用户 u 对于 产品 i 和产品 j 产生行为的时间间隔． 计算出物品之间的相似度后，基于物品的协同过 滤算法通过如下公式来衡量用户 u 对物品 j 的兴趣大 小: p( u，j) = i∈S( ∑ j，k) ∩N( u) sim( j，i) ． ( 3) 其中，N( u) 是用户 u 喜欢的物品数，S( i，k) 表示与物 品 i 最相似的 k 件物品，rui表示用户 u 对物品 i 的兴趣 偏好． 类似式( 2) 近期的行为更能体现用户当前的兴 趣，应当在推荐时对其增加一定的权重［17］，则修正公 式( 3) 为 p( u，j) = i∈S( ∑ j，k) ∩N( u) sim( j，i) 1 1 + β | t0 － tui | ． ( 4) 式中，t0是当前时刻，β 是衰减系数． 1. 2 基于交通网络数据优化的地理信息推荐算法 1. 2. 1 基于经纬度的距离计算 基于地点上下文的推荐利用交通网络数据来度量 地图上两点之间的距离，因此需要利用各个地点的经 纬度进行计算( 本文使用百度地图提供的 Geocoding API 进行地理信息编码的操作) ． 在进行空间中不同 点之间的距离计算后，推荐算法会根据两个地点间的 距离远近对推荐结果进行调整． 首先，使用最基本的 两点间距离计算的方法，直接度量两点间的欧几里德 距离． 由于地球是一个椭球体，而不是平面，因此不能 直接对经纬度进行欧几里德距离计算． 式( 5) 所示为 地球上两点间经纬度距离计算的公式: D = 2arcsin sin2 a 2 + cos φ1 cos φ2 sin2 b 槡 2 × 6378. 137． ( 5) 式中，φ 为纬度，a 为两点之间的纬度的差值，b 为两点 之间经度的差值，而常数 6378. 137 为地球半径( 单位 为 km) ，这里所有的经纬度值都需要转化为弧度制． 根据式( 5) 可以对使用经纬度表示的任意两点进 行欧几里德距离的计算． 然而，直线距离更近的两个 点并不能够代表这两个点的真实距离更近． 例如，如 图 2 所示，图中两条横向直线为道路两侧，纵向图形为 人行天桥，除该人行天桥外用户无法穿过该道路，A、B 和 C 为三个商户位置，用户当前处于 A 处． 可以看出 用户在 A 点时距离 C 更近，应向其推荐 C 处的商户． 然而，从 A 到 C 需先经过 B 之后过天桥才能到达，远 超过 A 到 B 的距离． 因此，向用户推荐 C 处的商户排 名不应该高于 B 处商户的排名． 图 2 直线距离非最近距离的示意图 Fig． 2 Schematic diagram of closest distance 通过图 2 所示的简单示例可以看出，对于推荐系 统而言，应当向用户推荐实际距离更近的物品，而不是 直线距离最近的物品． 在实际生活中，这种实际距离 远大于直线距离的情况十分常见． 1. 2. 2 基于交通网络数据的距离计算 基于交通网络数据进行距离计算可以提高推荐系 统推荐结果的准确性，为用户提供更好的使用体验． 因此，在本节中将给出利用交通网络数据进行距离计 算的方法． 为了使用交通网络数据进行距离计算，必须借助 于成熟的地理信息系统，使用其关于两点间距离计算 或路径规划的 API 来获取到它们的实际距离． 使用百 度地图所提供的 Direction API 来进行距离计算，该 API 可以进行步行、驾车以及公交换乘三种形式的路径查 询，并返回 json 格式或者 xml 格式的查询结果数据． · 3561 ·