LBS 用户签到行为相似性匹配

涂岩恺

（1.厦门雅迅网络股份有限公司，福建厦门361008；2.中国电子科技集团第三十研究所，四川成都610041）

LBS 用户签到行为相似性匹配

涂岩恺1，2

（1.厦门雅迅网络股份有限公司，福建厦门361008；2.中国电子科技集团第三十研究所，四川成都610041）

针对签到点数据不稳定，时间跨度大的特征，提出融合时空模式Housdorff距离匹配的方法来衡量LBS用户行为的相似性，通过实验比较，效果要优于传统方法.

行为相似性；LBS签到点；模式匹配；Housdroff距离

0 引言

在互联网中，LBS（基于位置的服务）应用每天都会产生大量的签到数据.这些数据包括时间、位置、签到点POI属性等信息，反映了用户真实的生活轨迹与兴趣倾向.对这些基于社交网络的签到数据进行挖掘，寻找行为兴趣相似的人群可以定量和估算人们的社会活动特征，进而发掘人们的行为规律，使人们能够更深层地认知智能化城市中社群的生活轨迹、社交行为、环境变动等，不仅能够满足用户越来越强烈的个性化、社会化需求，而且能够为智能商务、个性化推荐提供支持.

由于用户的签到记录是不连贯和碎片化的，时间间隔可能为几分钟、几小时甚至几天几个月，在这样复杂的签到率下难以还原出用户的真实行动轨迹，因此采用网格或交通路网匹配的方式试图还原用户签到点之间的轨迹[1，2]，这类方法在签到点时间间隔较长的情况下会不可避免的产生轨迹估算误差.通过主题相似性判断用户行为相似性[3]，这类方法也要求用户签到点时间间隔不能隔的太远，否则隔几个月的签到本身不具有什么主题意义联系.如果不恢复用户轨迹，直接用点集空间关系的相似性进行用户行为相似性匹配的方法忽略了签到点的先后时间关系，时间间隔较近的签到点顺序隐含了用户的行为顺序与兴趣优先信息[4].笔者用签到点集的时空模式匹配方法进行数据的用户行为挖掘，将同一天内的签到时间顺序与签到点位置数据进行融合，提出一种新的融合时空模式的Hausdorff距离匹配方法进行有效的相似判别，无需进行签到点间的行为轨迹恢复，同时有效的利用了签到时间顺序信息.

1 时空数据融合

相对于完全依靠签到位置时间先后顺序的轨迹信息，或完全抛开时间顺序的点集匹配，都不能达到实际需求.因此需要将离散化的时间信息与位置信息充分融合处理，尽量保留有用的时间信息，又不会因为签到时间间隔太远导致误导用户轨迹.

假设某个LBS用户所有原始签到点集合按时间顺序排列为{P1，P2，P3，...，PM}，每个Pi={x，y，t}（i=1，2，...，M）包含经纬度位置信息（x，y）与时间信息t.将签到点集合经处理分成两类：

1）秩次子集：根据时间信息t，从Pi中提取出属于一天（从当天0∶00∶00到23∶59∶59，一般人的生活规律以天为单位，因此这里也以天为区间分割出秩次子集）的签到点构成单独的子集合Qj={Pj，Pj+1，Pj+2，...，Pj+N}（N≤M），对于构成子集合Qj内的签到点赋予秩次权值rank，即Qj内按时间顺序第1个签到点秩次为rank=1，第2个签到点秩次为rank=2，以此类推，获得秩次后去除时间信息t，得到新的秩次子集合这样就将1天内连续签到的位置与相对时间顺序信息融合保留了下来.

2）孤立点：对于不构成子集合的签到点Pi之间，由于时间隔过远（大于1天），在时间联系上的意义较弱，因此去除时间信息，只保留位置信息，形成孤立签到点Pi=（x，y）.

2 时空模式匹配

综合考虑孤立点之间、秩次子集之间，以及孤立点与秩次子集之间的相似性距离，设假用d（P1，P2）表示点P1点与P2点对应位置（x1，y1）与（x2，y2）的地理直线距离，则：

两个独立点P1与P2之间的相似性距离Ds直接取地理直线距离：

独立点Pi与秩次子集之间的相似性距离Db计算公式如下：

在计算孤立点与秩次子集的距离时，利用秩次信息拉大了它们之间的距离，突显了时间顺序差别的特征.在特殊情况下，秩次子集点个数为1的时候，秩次子集退化为孤立点，（2）式中N=0，rank=1，等价于（1）式，说明孤立点是秩次子集个数为1时的特殊形式.

在计算带秩次的点对P′i与P′j的距离时，需要融合秩次相似性权重值wi，j=｜ranki-rankj｜+1，则（4）式中的按如下方法计算：

3 用户行为相似性比较

设两个用户UserA和UserB的签到集合经时空数据融合处理后变换为分别包含若干孤立点与若干秩次子集的集合则两个用户间的行为相似性比较方法如下：

公式（6）是典型Hausdorff距离公式，但是在具体计算集合内部元素距离的时候分别考虑与孤立点与孤立点、孤立点与秩次子集、秩次子集与秩次子集的情况，融合了空间位置与时间秩次信息，因此本文方法本质上是扩展了典型Hausdorff距离方法[5].相似性度量值H值越小，表明用户签到行为相似性越高，依据H值的大小，可以从大量用户数据的比较中得出与当前查询用户最相似的用户（即H值最小的用户），实现用户签到行为相似性挖掘.

4 结语

由于难以准确衡量不同用户是否真的兴趣相似，因此我们实验测试时采用同一个人不同时段的签到数据进行比较检索.实验所有数据来源于厦门雅迅网络股份有限公司“八千优惠”LBS应用[6]，用户数量20 237个，采用2012年历史数据进行挖掘实验，平均每个用户40个以上签到点.2012年6月之前签到数据做为数据库样本，2012年6月之后签到数据做为测试样本.利用测试样本在数据库样本中比对，并按相似性排序比对结果，统计同一人的数据库样本与测试样本相似性排序在第一位的比率.

本文时空模式方法与轨迹方法、主题相似方法、点集匹配方法的匹配正确率如图1所示，对于这类高离散化的签到点行为，轨迹法效果最差，更适合采用本文时空模式融合匹配，取得更为理想的实验结果.但从实验也看的出来，由于签到行为本身具有不稳定性，受签到数据质量的影响，依据签到行为进行相似度判断的准确率还不够高，还没超过40%，只能在协同推荐系统中起辅助作用，如果需要高精度挖掘用户行为相似性，必须在后续研究中融合其它稳定特征.

图1 实验结果比较

[1]郑宇，谢幸.基于用户轨迹挖掘的智能位置服务[J].中国计算机学会通讯，2010，6（6）：23-30.

[2]邹永贵，万建斌，夏英.基于路网的LBSN用户移动轨迹聚类挖掘方法[J].计算机应用研究，2013，30（8）：2410-2414.

[3]闫光辉，舒昕，马志程，等.基于主题和链接分析的微博社区发现算法[J].计算机应用研究，2013，30（7）：1953-1957.

[4]刘树栋，孟祥武.一种基于移动用户位置的网络服务推荐方法[J].软件学报，2014（11）：2556-2574.

[5]HUTTENLOCHERDP，KLANDERMANGA，RucklidgeWJ.ComparingImagesUsingtheHausdorffDistance[J].PatternAnalysisand MachineIntelligence，IEEETransactionson，1993，15（9）：850-863.

[6]陈典全.LBS中基于轨迹的用户行为特征分析[J].全球定位系统，2012，36（6）：58-61.

（责任编辑 李健飞）

LBS User's Checking Behavior Similarity Matching

TU Yan-kai1，2
（1.Xiamen Yaxon Network Co.，Ltd.，Xiamen，Fujian 361008，China；2.The 30th Research Institute of China Electronics Technology Group Corporation，Chengdu，Sichuan 610041，China）

According to the characters of instability and large time span of checking points，a time-space fusion matching method based on Housdroff distance is proposed to measure LBS user′s checking behavior similarity.Experiments show that the method has better performance than traditional methods.

behavior similarity；LBS checking point；pattern matching；Hausdroff distance

T391

：A

：1673-1972（2015）06-0044-03

2015-04-03

厦门市科技计划项目（3502Z20130008）

涂岩恺（1983-），男，福建永安人，工程师，博士，主要从事信号与信息处理研究.