APP下载

一种基于网络表示学习的生活模式挖掘方法

2020-12-28蔡郑贾利娟孙扬清

电脑知识与技术 2020年31期
关键词:语义

蔡郑 贾利娟 孙扬清

摘要:近几年,随着移动终端设备的普及以及移动社交网络的发展,大量的时空信息数据得以被采集并上传到网络云端,使得获取时空信息变得相对简单。随着相关数据的累积,越来越多的学者开始投入到相关的研究之中。该文通过网络表示学习的方法对时空信息进行了预处理,再结合自然语言处理将用户一定时间范围内的活动通过主题向量来表示,然后通过聚类和频繁模式发掘等方法发掘出用户的生活模式。实验结果验证了本文方法的有效性。

关键词: 时空信息;语义;网络表示;主题向量;生活模式

中图分类号:TP393        文献标识码:A

文章编号:1009-3044(2020)31-0081-05

Abstract: In recent years, with the popularization of mobile terminal devices and the growth of mobile social networks, a large amount of spatiotemporal information data can be collected and uploaded to the cloud. With the accumulation of relevant data,more and more scholars begin to devote themselves to relevant research. In this paper, the spatiotemporal information is preprocessed by the way of deep wandering, The idea of natural language processing is used to express the activities of users over a period of time as topic vectors, and then the experiment results of users' life patterns are discovered through clustering and frequent pattern mining to verify the effectiveness of the proposed method.

Key words:spatial-temporalinformation; semantic;deepwalk;topic word vector;frequent pattern

随着互联网技术、移动通讯技术、卫星定位技术的快速发展以及移动终端的大量普及,越来越多的时空信息数据被采集并上传到云端保存。比如,人们使用社交App进行“打卡”时,会上传打卡的时间和位置;打车App会实时上报车辆的位置信息;移动终端设备也会实时上报包含位置信息的信令数据[1-4]。我们把对象(移动终端用户、社交App用户、打车App用户)在一段时间内经过的所有位置信息收集起来,就可以得到该对象在这段时间内活动的时空轨迹。

如何从对象的时空轨迹数据中挖掘出其生活模式是本文的研究重点。对象的生活模式通常是隐含在其时空轨迹中的,例如,对象会在每周三和周五的晚上去健身房打卡,在周末会去商场购物等。也就是说,对象的生活模式是與时间密切相关的,不同的时间段对应着不同的生活模式。一旦挖掘出对象的生活模式,就可以将其应用到诸如公安破案[5,6]、热门路径推荐[7]、社会关系推荐[8]、动物的迁移模式[9]研究等多个现实场景。因此,挖掘出对象的生活模式不仅极具挑战,也是一项具有重大意义的工作。

传统的生活模式的挖掘大多是基于时间序列的频繁模式[10-11]的挖掘,即使用最长公共子序列(LCSS),动态时间规划(DTW)等算法从对象的历史时空轨迹中挖掘出其生活模式。这些算法的特征是计算量大、对噪音和缺失数据敏感、要求序列数据之间必须是可比较或者计算距离的。但是,出于法律和对研究对象隐私保护等方面考虑,一些轨迹中的位置信息都是使用地点编号、兴趣点编号或者基站号来表示,导致传统算法无法直接应用到这些轨迹数据上。另一方面,在计算轨迹点之间的距离时,由于通达性的原因,地理位置上的距离有时候并不能反映真实的距离,会导致时空轨迹之间的相似度计算并不准确。

针对以上问题,本文基于网络表示学习技术[11]提出了一种新的生活模式挖掘方法:通过结合自然语言处理的思想,将时空轨迹点之间的通达性看作其上下文语义信息,可以将轨迹点映射为连续向量空间中的低维稠密嵌入向量,将对象一段时间内的活动轨迹转换为主题向量,最后利用传统的频繁模式发掘算法从海量时空轨迹中发掘出对象隐藏的生活模式。

本文的主要贡献如下:

1)基于网络表示学习和自然语言处理的思想,通过时空轨迹的上下文语义来表达位置信息,将稀疏不连续的位置编号映射为低维的嵌入向量来表示,解决了这些位置信息无法直接比较和计算距离的问题。

2)将对象一段时间内的时空轨迹转换为对应的主题向量后,减少了通过频繁模式挖掘生活模式时的计算量。

3)在出租车数据上进行了深入的实验研究,实验结果表明本文提出的方法能够有效地发掘出人们的生活模式。

1相关工作

近些年来,随着移动定位技术的发展,各种各样的轨迹数据被采集出来,比如手机的信令数据、出租车的轨迹数据、社交网络的签到信息、交通卡口过车信息等。这些数据在出行预测、智慧城市、公安破案等领域都得到了广泛的应用。

传统的生活模式发掘多采用隐马尔可夫模型,频繁模式[14-16]等方法。这些方法通常需要提取时空轨迹中的停留点,再使用停留点来代表用户的历史轨迹模型。停留点[17]指的是对象在某个地方停留了一段时间,比如商场、酒店、休息或者工作的地点,通过停留点可以将用户的历史轨迹表达为一个停留点序列,如:[s 1?t1s 2?t2s 3?t3…?tn-1s n],其中s表示停留点的中心坐标,[?t]表示停留的时长,[?t]的阀值通常需要手动指定。有了用户历史轨迹的模型,就可以使用FP-growth、Apriori等算法挖掘出其中的频繁项集,或者通过对这些频繁模式进行组合和连接,发现一些表征了用户生活、行为规律的顺序模式[18]。但是这种基于停留点的学习方式存在以下几个方面的问题:

1)对数据质量要求高,噪声和缺失数据都会影响停留点的检测,降低模型的准确率。例如,出于省电的目的,有些定位设备在或者电量不足时会主动降低采样频率,导致采样到的数据稀少,无法判出停留点;城市地形由于高楼大厦的遮挡存在定位不准确以及坐标漂移等现象,这些情况都会极大地影响挖掘结果的准确性。

2)计算量大,对于使用经纬度来表示位置信息的轨迹数据来说,通过使用haversine公式[19]来计算停留点之间的距离时突出问题是计算量大。为了减轻计算量,目前通用的做法是将经纬度映射为geohash[23]编码,当geohash编码相同时可以认为位置是接近的。但是这种做法又会引入边界问题,即存在geohash编码不同但是位置却接近的情况,如图1所示。

3)轨迹数据是离散的,出于隐私保护和法律方面的原因,一些时空轨迹数据使用编号来表示位置,例如社交网络签到数据通常使用兴趣点的编号来表示坐标,手机信令数据采用基站号来表示位置等。这些离散的轨迹数据无法直接应用到传统的挖掘算法中。

针对这些问题,近些年人们开始利用网络表示学习[12,20-22]的方法将时空轨迹数据中用户访问过的顶点映射到致密的嵌入向量中。有人通过统计观察发现,如果对时空轨迹中的这些顶点进行随机游走,顶点出现次数的冥律分布与自然语言处理中单词出现次数的冥律分布一致且遵循zipfs定律[12],这意味着自然语言处理中常用的词向量模型也可以应用在网络表示学习中。

网络表示学习首先利用轨迹点之间的通达性来进行随机游走(DeepWalk),生成各个轨迹点的上下文信息,再利用轨迹点的上下文信息通过表示学习来获取轨迹点的低维嵌入向量。一方面,随机游走能够通过降低异常数据点的出现次数来降低其影响;另一方面,这些低维的嵌入向量能够反映原先时空轨迹数据的某些特性,如果两个轨迹点可以通达,那么这两个点的嵌入向量是类似的,位置更接近的轨迹点之间的向量也是更相似的;嵌入向量使得计算离散的轨迹点之间的距离变成可能,可以将一些常用的聚类算法应用到轨迹点的嵌入向量上。所以本文也采用网络表示学习的方法,将时空轨迹数据转换为嵌入向量,再基于嵌入向量进行生活模式的发掘。

2基于网络表示学习的生活模式挖掘方法

2.1定义

模型中用到的相关符号以及对应解释如表1所示。

定义1:时空轨迹

对于指定用户[u]的时空轨迹[T(u)={vi,ti|0≤i≤n,  vi∈V}],对于任意 [i

定义2:连通图

给定连通图[G=(V,  E)],[E]表示轨迹点之间连通性,[V]是轨迹点的集合。[v∈V]代表连通图的各个顶点,[e∈E]代表连通图的各条边。

定义3:轨迹点的嵌入向量

定义4:活动主题

用户[u]在时间区间[?t]内的时空轨迹可以表示[v1,t1,x1,v2,t2,x2,vn,tn,xntn=t1+?t , t1

定义5:生活模式

对于一个用户[u],其生活模式是一系列三元組的集合[Lu= t1,  t1+?t1,  p1,  t2,  t2+?t2,  p2, ……, tn,  tn+?tn,  pn]。其中[t,  t+?t]分别表示生活模式的开始和结束时间,[p表示这段时间内的活动主题,]例如每晚的18:00-20:00去公园散步,每天的8:00-9:00骑自行车上班等。

2.2生活模式挖掘方法

挖掘方法的结构如图2所示,由三个模块组成:生成图,网络表示学习、生活模式发现。

1)生成图

生成图的主要目的为了构建连通图[G],通过遍历所有对象的轨迹的集合[T],将轨迹点作为顶点,将轨迹点之间的连通性作为边添加到连通图中,其主要步骤如下:

2)网络表示学习

网络表示学习以连通图G作为输入,通过深度游走(DeepWalk)[12]和skipgram[17]算法得到各个轨迹点的嵌入向量。以社交网络签到信息为例,就是将网络中的各个轨迹点用一个低维的嵌入向量表示,这些向量能反映出原先网络的某些特性,如果在原网络中两个点的结构类似,那么这两个点表示成的嵌入向量也应该类似,其效果见图4和图5。

基于深度游走(DeepWalk)的网络表示学习的具体步骤如下:

3)生活模式发现

在得到各个轨迹点的嵌入向量后,就可以通过计算对象在一段时间内的活动轨迹的嵌入向量平均值来得到对象的活动主题,当发现对象每天同一时间段的活动主题的相似度超过支持度时,就可以认为对象存在固定的生活模式,具体的算法如下:

3算法验证

3.1数据说明

为了方便进行验证,使用微软研发中心公布的出租车数据[29],其包含了8900辆出租车1周的时空轨迹数据,每条数据包含了用户编号、采样时间、经度和纬度等属性。其数据格式如下表所示:

3.2参数的设置和说明

本次实验主要需要设置两个参数:嵌入向量的长度d和发现生活模式的支持度[θ]。根据业界经验[12],将d设置为300,将[θ]设置为0.8。d设置过大会导致网络表示学习耗费大量的训练时间,设置过小会导致实验精度降低。

3.3实验结果与分析

网络表示学习利用了所有出租车驾驶员的轨迹数据。本实验的第一步,就需要检验其学习效果。随机选取几名驾驶员,将其活动轨迹一方面以热力图的形式进行展示,另一方面使用HDBSCAN算法[30]将所有轨迹点的嵌入向量进行聚类,通过比较聚类结果与热力图中的热点区域是否一致来确认其学习的准确性。限于篇幅本文只展示了一位驾驶员的效果。

从左侧的热力图可以看出,驾驶员的主要在7个地区活动(限于篇幅本文只展示了其中的4个)。同时,右图中驾驶员的所有嵌入向量也被聚类成7类(用不同的颜色标示)。对比左右两图可以发现,学习的结果与实际相符。这说明即使用户的轨迹数据中不包含地理位置信息时,也可以利用轨迹点之间的通达性和网络表示学习得到轨迹点的嵌入向量,并根据这些致密连续的嵌入向量来进行聚类等操作。

得到嵌入向量后,就可以发掘每个驾驶员的生活模式,通过调整时间窗口,发现该驾驶员存在以下明显的生活模式:

结合原始数据进行分析,可以发现驾驶员每天9:00~14:00以及15:00~24:00在东城区(地点7)和西城区(地点6)工作,中午14:00~15:00会在丰台区(地点5)休息,每天凌晨会返回房山区(地点1)休息至次日的9点,如图所示。

可以看到,挖掘结果(表3)与原始数据的分析结果(图10和图11)基本上是相符的,挖掘出来的生活模式符合常理。

4结论

基于对大量轨迹数据的观察和研究,本文提出一种充分利用海量时空轨迹数据,利用表示学习来发掘生活模式的方法。该方法的可以广泛地应用到多个领域,例如好友推荐,犯罪团队发现,交通路网优化等多个方面。为了验证本方法的有效性,本文利用出租车数据集进行了深入的实验,实验结果表明该挖掘方法是有效的。一方面,仅需要使用较少的超参数就能够达到实验目的,另一方面,还能够充分利用没有地理位置信息的时空轨迹数据。

在未来的工作中,我们计划继续优化算法,以应对现实中海量的轨迹数据。同时,还需要考虑到轨迹数据中时序问题,这是本文所忽略的。通过本文提出来的方法,对象的生活模式可以用定长的嵌入向量表示,这为人群的聚类提供了帮助,通过生活模式对应的主题向量进行特定用户群组挖掘,提供更精确的人物画像,亲密度分析以及好友推荐是下一步的研究方向。

参考文献:

[1] 钱琨.基于蜂窝信令数据的移动轨迹清洗和预测方法研究与实现[D].成都:西南交通大学,2016.

[2] 陈晓鹏.基于手机时空轨迹数据的用户移动模式分析与研究[D].长沙:国防科学技术大学,2016.

[3] 凌峰.基于手机位置数据的用户移动模式挖掘与分析[D].北京:北京邮电大学,2017.

[4] 崔邓.基于智能手机轨迹提取停留点的时空聚类算法研究[D].重庆:西南大学,2016.

[5] 韩勇.基于大数据技术的公安移动通信数据处理平台设计与实现[J].工程技术(文摘版),2017(24): 318.

[6] 王仲妮,靳涛.时空轨迹数据挖掘在公安经济群体事件管理中的应用[J].现代信息科技,2019(1):78-80.

[7] 栗雨然.基于时空聚类的兴趣点推荐系统设计与实现[D].成都:电子科技大学,2019.

[8] 刘树栋.基于位置的移动社会化网络推荐技术研究[D].北京:北京邮电大学,2015.

[9] 王玉偉.候鸟迁徙移动模式挖掘研究[D].北京:中国科学院,2015.

[10] 陈东.规律性移动对象的时空轨迹挖掘及应用研究[D].济南:山东师范大学,2017.

[11] 万项超.基于周期行为的个人生活模式挖掘研究[D].哈尔滨:哈尔滨工程大学,2012.

[12]PerozziB,Al-RfouR,SkienaS.Deepwalk: Online Learning of Social Representations[C]//Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, New York, 2014:701-710.

[13] 张健钦,仇培元,杜明义.基于时空轨迹数据的出行特征挖掘方法[J].交通运输系统工程与信息,2014,14(6):72-78.

[14] Chen M,LiuY,Yu X H.NLPMM:a next location predictor with Markov modeling[J].Advances in Knowledge Discovery and Data Mining,2014: 186–197.

[15] Chen M,LiuY,Yu X H.Predicting next locations with object clustering and trajectory clustering[J].Advances in Knowledge Discovery and Data Mining,2015: 344–356.

[16] Chen M,Yu X H,LiuY.Mining moving patterns for predicting next location[J].Information Systems,2015,54:156-168.

[17] 李毓瑞,陈红梅,王丽珍,等.基于密度的停留点识别方法[J].大数据,2018,4(5):80-93.

[18] 陈勐,刘洋,王月,等.基于时序特征的移动模式挖掘[J].中国科学:信息科学,2016,46(9):1288-1297.

[19] Hartanto S, Furqan M, Siahaan A P U, et al. Haversine Method in Looking for the Nearest Masjid[J]. International Journal of Engineering Research, 2017,3(8):187-195.

[20] Crivellari A, Beinat E. From Motion Activity to Geo-Embeddings: Generating and Exploring Vector Representations of Locations, Traces and Visitors through Large-Scale Mobility Data[J].International Journal of Geo-Information, 2019,8(3).

[21] Xu Q , Chen H , Zhi H , et al. Algorithm research for user trajectory matching across social media networks based on paragraph2vec[C]. International Conference on Advances in Materials. 2018.

[22] Liu J , Li H , Gao Y , et al. A geohash-based index for spatial data management in distributed memory[C]//2014 22nd International Conference on Geoinformatics. IEEE, 2014.

[23] 陳雪莲.基于时空数据的用户移动行为模式研究[J].无线互联科技, 2019,16(7):167-168.

[24] Xiucheng Li, Kaiqi Zhao, Gao Cong, et al. Deep Representation Learning for Trajectory Similarity Computation[C]// 2018 IEEE 34th International Conference on Data Engineering (ICDE). IEEE, 2018.

[25] Karli S , YücelSaygin. Mining periodic patterns in spatio-temporal sequences at different time granularities[J]. Intelligent Data Analysis, 2013, 13(2):301-335.

[26] 熊伟,吴钊,李兵,等.一种基于语义的时空敏感社会关系模型[J].小型微型计算机系统, 2016(6):1207-1211.

[27] Yang J, Eickhoff C. Unsupervised Spatio-Temporal Embeddings for User and Location Modelling[J]. arXiv: Information Retrieval, 2017.

[28] 郑林江,赵欣,蒋朝辉,等.基于出租车轨迹数据的城市热点出行区域挖掘[J].计算机应用与软件, 2018(1):1-8.

[29] Zheng Y, Yuan J, Xie W, et al. Drive Smartly as a Taxi Driver[C]// Symposia & Workshops on Ubiquitous. IEEE, 2010.

[30] Mcinnes L, Healy J ,Astels S. hdbscan: Hierarchical density based clustering[J].The Journal of Open Source Software, 2017,2(11).

【通联编辑:代影】

猜你喜欢

语义
语言与语义
批评话语分析中态度意向的邻近化语义构建
“社会”一词的语义流动与新陈代谢
“上”与“下”语义的不对称性及其认知阐释
认知范畴模糊与语义模糊
“V+X+算+X”构式的语义功能及语义网络——兼及与“V+X+是+X”构式的转换
“熊孩子”语义新探
语义交换对象在交换模型中的使用
“深+N季”组配的认知语义分析
语义分析与汉俄副名组合