LBS中基于轨迹的用户行为特征分析①

陈典全

（厦门雅迅网络股份有限公司，福建 厦门361008）

0 引 言

基于位置的服务（LBS）是整个移动互联网的基础应用之一，日、韩、北美、欧洲等都推出了众多基于位置的服务，国内也有不少企业推出位置相关的产品和服务并获得成功。国外比较流行的应用有Foursquare、Color、Kuipp等，国内新浪微博、玩转四方、大众点评等也融合了与位置相关的信息。

在LBS应用中，针对用户行动轨迹的产品设计是一个值得深入探讨、有很大想象空间的话题，对用户的行动轨迹数据进行挖掘，可以衍生出众多有趣的应用［1]。2011年初爆出iPhone、Android可记录用户行踪轨迹，证明了Apple、Google也对用户行动轨迹深感兴趣。

一旦记录了用户的行动轨迹，就可以对轨迹数据进行分析、挖掘，掌握用户的行为特征，从而为用户提供具有直接针对性、个性化、智能化的基于位置的服务，改变目前LBS服务单纯依赖于签到、弹性社交、问答等几个简单模式，从而极大改善用户的使用体验。

将以用户原始记录的轨迹数据为基础，进行轨迹简化、时空融合、行为特征分析等几方面的研究，为推出个性化LBS服务产品奠定技术基础。

所有研究内容以用户授权采集轨迹数据、不触犯用户隐私为前提。

1 用户轨迹简化

在LBS应用中，部分用户为了与好友分享自己的经历，或者为了记录自己有纪念意义的行动过程，会乐于将自己的行动轨迹上传并保存到LBS服务提供商系统中。基本的流程是用户通过有卫星定位（北斗、GPS等）的手持或车载设备（典型设备是具备卫星定位的手机）采集到位置信息，通过公用无线网络上传到LBS运营商的服务器，经过处理后保存在数据库中，供用户自己或者授权的其他用户查看。

但是，大多数用户设备对位置上传的功能设置比较简单，最常见的是设置取样时间间隔，即每隔一定时间采集位置数据并上传。这种模式将导致上传到LBS运营商服务器的轨迹数据有大量的无效的冗余信息，不但占用数据库存储空间，还不利于用户轨迹的再次分享传输。

轨迹简化的算法有很多种，最常用的是DP算法（Douglas和Peuker提出），该算法至今仍然广泛应用于制图学领域。其基本原理如图1所示。

图1 DP算法基本原理

假定如图轨迹需要简化，事先设定一个可以容忍的垂直距离td，a作为固定点，b作为浮动点。先找出所有轨迹中到线ab垂直距离最大的c点，判断fc是否大于td，如果大于，则c作为新的浮动点；再找出a、c两点间到线ac的垂直距离最大的d点，判断de是否大于td，如果de＞td，d成为新的浮动点，c作为保留点存储，否则，d成为新的固定点，而ad之间所有的其它点将丢弃。

DP算法实现起来比较简单，但用在轨迹简化中存在两个问题：

用户以不同方式运动（驾驶或步行）单位时间内运动距离差别很大，用单一的可容忍垂直距离判断有可能使得步行轨迹大量丢弃，而往往步行轨迹对用户来说更有意义。

没有考虑停留时间。用户在某点停留往往表示附近有其感兴趣的内容，这对于用户行为特征分析尤为重要。

文献［2]提出了一种改进的轨迹简化算法，采用步行和驾驶分段处理、考虑相邻轨迹点角度变化等优化手段，能够使得轨迹的简化更为合理。

图2示出了某一用户轨迹图，用户驾车从城市快速道成功大道行驶到轮渡，坐渡船到达鼓浪屿码头，步行游览一周，其中在皓月园景点入内参观停留。

图2 用户原始轨迹图

如果采用DP算法简化，如图3所示，驾车段轨迹损失不大，但步行段则与实际差别很大，而用户重点参观的皓月园景点轨迹则全部丢弃。

根据实际应用需求，并参考文献［2]，对DP算法进行以下改进：

图3 使用DP算法简化的轨迹图

将轨迹点中速度为0或者接近于0的点去除（驾驶停车或步行停留），按照前后轨迹点距离和速度的变化并考虑用户轨迹的语义（一般不会短时间驾驶与步行交替），将轨迹划分为驾驶段和步行段。针对驾驶段和步行段使用不同的可容忍垂直距离值进行简化

考虑相邻轨迹点用户方向角度变化以及相邻点之间的距离。有速度、相邻点有一定距离、急转弯（角度变化大）的轨迹点有更大的保留价值

考虑POI匹配、停留时间等因素。将轨迹点与POI进行匹配，并计算与同一个POI匹配的多个轨迹点之间的时间间隔，从而判断用户在该POI停留的时间。与某一POI匹配的轨迹点越多、停留时间越长，那么这些轨迹点中与该POI最近的轨迹点保留价值更高

按照以上优化方法进行轨迹简化，简化后的轨迹损失驾车段与步行段比较均衡，特别是用户重点停留的皓月园保留比较完整，简化后的视觉效果与图2差别不大，但数据量减少80%以上（5s取样，驾驶段容忍距离200m，步行段容忍距离40m，考虑相邻轨迹点角度变化和POI停留时间）。

2 用户轨迹时空融合

在用户轨迹简化的基础上，就可以进行用户轨迹的时空融合，即把用户的轨迹与地图上的POI点进行匹配，并考虑其停留时间，从而推断出用户的行为。可以看出，在轨迹简化阶段考虑用户停留时间因素十分重要。

用户轨迹与POI匹配及其停留时间计算采用Voronoi图算法［3]，如图4所示。

利用Voronoi图对平面上n个离散POI点Pi，按照最邻近原则划分区域；每个点Pi与它的最近邻区域相关联。通过计算轨迹Tj（vj，tj）与各关联区域的交点Xk，可以进一步推算出最匹配的POI点及轨迹受该POI点影响的持续时间。

图4 Voronoi图

研究的重点放在“轨迹与POI匹配并且停留了一定的时间”所代表的语义。要比较准确的分析轨迹所代表的语义需要建立POI－活动映射表（PAM），对每种细分POI所对应的可能活动的时间进行定义。

PAM与POI分类有密切关系，每家地图数据商其分类有所不同，但一般采用两级（最多不超过3级）分类法，大类一般不超过20种，小类数百种。PAM必须建立在LBS运营商所采用的地图数据POI分类基础上。

表1示出了PAM示例，以此表为参考，可以推断图5中的用户轨迹所代表的语义可能是：“在建文楼上课（工作）3h25min”，“在建设银行ATM取款20min”，“在大方素食馆吃饭1h15 min”。

表1 PAM示例

应该说，基于轨迹及PAM来分析用户行为还无法做到语义的完全准确推断，例如“用户在银行停留30min”有可能是“ATM取款”，也有可能是“柜台业务”，甚至有可能两种活动都有发生。

图5 用户轨迹所代表的语义

3 用户行为特征分析

人的行为特征具有规律性、持续性等特征，一个人经常从事的行为可以反映出其偏好、性格特点甚至气质修养。经过用户轨迹简化和时空融合，LBS运营商可以得到大量的用户行为信息［4]，这些信息包含时间、地点、活动、持续时间等内容。

经过一定时间的积累，LBS运营商可以从海量数据中挖掘出大量的用户行为特征信息，并针对用户行为特征推出相应的个性化LBS服务［5]，例如和商家联合推出优惠折扣服务。

从海量用户数据中进行数据挖掘是分析用户行为特征的主要手段。数据挖掘的很多算法都可以应用在行为特征分析中，如应用分类分析法提取用户偏好、时间序列法分析用户行为规律、聚类分析法分析用户群体特征等。

以“体育运动”为例，我们采用聚类分析中的K－means算法对喜爱体育运动的用户年龄、体重分布特征进行分析。

3.1 数据预处理

本阶段所使用的数据虽然经过了轨迹简化和时空融合，仍然存在杂乱性、重复性、不完整性等特征，需要对数据进行集成、清洗、简化等预处理，并构建针对“体育运动”特征进行数据挖掘所需要的数据仓库。

选取某一年度的用户轨迹数据，首先进行简化处理，只选取与POI大类“体育”相关的轨迹数据，然后再对噪声数据、脏数据等进行清洗，根据用户群体行为特征分析的需求构建如图6所示的数据仓库维度表和事实表。

3.2 算法原理

数据挖掘的目的是要找出从事体育锻炼的用户群体分布规律，适合于使用聚类算法，采用聚类算法中最典型的 K－means算法［6]。

图6 用于特征分析的事实表和维度表

设定要处理的数据集为Rn，样本是 ｛x（1），…，x（m）｝，每个x（i）∈Rn.

K－means算法是将样本聚类成k个簇，算法步骤如下：

随机选取k个聚类质心，u1，u2，…，uk∈Rn

重复下面过程直到收敛：

｛

对于每一个样例i，计算其应该属于的类：

对于每一个类j，重新计算该类的质心：

k是事先给定的聚类数，ci代表样例i与k个类中距离最近的那个类，ci的值是1到k中的一个。质心μj代表对属于同一个类的样本中心点的猜测，随机选取k个点作为初始质心，第一步对于每一个样本计算其到k个质心中每一个的距离，选取距离最近的那个簇作为ci，经过第一步每一个样本都有了所属的簇；第二步对于每一个簇，重新计算它的质心μi（对年龄和体重值求平均）。重复迭代第一步和第二步直到质心不变或者变化很小。

3.3 结果分析

针对3.2中的K－means算法，依据经验，选取k＝3，亦即找出3类从事体育锻炼的典型人群。经过计算，3个聚类簇中心是：

｛（23.1，59.3），（39.4，67.6），（56.2，66.9）｝

二维值中分别代表的是年龄和体重。3个簇中心分别代表学生或刚参加工作的年轻人、事业家庭稳定后的中年人以及接近退休的老年人。

根据需要，可以继续采用数据挖掘的多种算法（如C4.5、Apriori、CART 等）对与“体育运动”相关的行为特征进行进一步分析，例如不同年龄、性别、职业、学历用户的体育运动频度、持续时间、运动类型等。

根据个体或群体用户的行为特征，LBS运营商就可以推出智能化、个性化的服务，从而极大提升用户的使用体验并获得可持续发展的商业模式。

4 结 论

基于用户的行为特征提供个性化的服务必将是LBS服务的发展趋势，而对用户特性的充分了解是提供个性化服务的基础。

提供了基于轨迹的用户行为特征分析的基本研究方法和主要手段，基于这些研究开发出了初步的产品，但商业化的应用仍有许多细节需要进一步的深入研究。

［1]LBS应用用户行动轨迹设计杂思［EB／OL]［2011－06－28].http：∥www.yeeach.com.

［2]CHEN Yu－kun，JIANG Kai，ZHENG Yu，et al.Trajectory simplification method for location－based social networking services.［C]∥ LBSN＇09Proceedings of the 2009International Workshop on Location Based Social Networks，ACM New York，NY，USA，2009.

［3]XIE Ke－xin，DENG Ke，ZHOU Xiao－fang.From trajectories to activities：a spatio－temporal join approach［C]／／LBSN＇09Proceedings of the 2009International Workshop on Location Based Social Networks，ACM New York，NY，USA，2009.

［4]JAEWAN L，ROMEO M A，M，BOBBY D，et al.Location－aware agent using Data Mining for the Distributed Location－Based Services［C]∥Computational Science and Its Applications Iccsa，2006：867－876 .

［5]陈典全，黄朝阳.基于位置的社会网络（LBSN）研究及其产业化［C]／／第二届中国卫星导航学术年会论文集（上），上海，2011：144－147.

［6]JERRYLEAD.k－means聚类算法［EB／OL].［2001－04－06]http：／／www.cnblogs.com