【人工智能】基于时空周期模式挖掘的活动语义识别方法

第16卷第1期 智能系统学报 Vol.16 No.1 2021年1月 CAAI Transactions on Intelligent Systems Jan.2021 D0L:10.11992tis.202012035 基于时空周期模式挖掘的活动语义识别方法 郭茂祖2，邵首飞2，赵玲玲3，李阳2 (1.北京建筑大学电气与信息工程学院，北京100044：2.北京建筑大学建筑大数据智能处理方法研究北京市 重点实验室，北京100044：3.哈尔滨工业大学计算机科学与技术学院，黑龙江哈尔滨150001) 摘要：传统的活动语义识别研究侧重从时空轨迹的空间信息中提取人类的活动语义，对时空轨迹数据的时间 特性挖掘不足。本文兼顾时间和空间特征，提出了一种基于周期模式挖掘的活动语义识别方法。首先将分离 出的活动轨迹数据通过空间距离进行密度聚类分成不同轨迹簇：然后，根据轨迹簇的时序特征挖掘个体对特定 位置的访问周期，基于该访问周期，并结合在该位置的停留时间，及其附近兴趣点分布等特征构建分类模型， 识别人类个体的活动语义。基于签到数据和仿真数据的实验结果表明，结合周期特征的活动语义识别方法相 比没有加入周期特征的实验结果有效提升识别精度20%以上，在2个相同的签到数据集下，对比其他的识别方 法提升精度10%以上。 关键词：时空轨迹：时空紧密相连性：密度聚类：停留时间：活动语义识别：周期模式挖掘：随机森林 中图分类号：TP181文献标志码：A文章编号：1673-4785(2021)01-0162-08 中文引用格式：郭茂祖，邵首飞，赵玲玲，等.基于时空周期模式挖掘的活动语义识别方法J.智能系统学报，2021,16(1)： 162-169. 英文引用格式：GUO Maoz,SHAO Shoufei,,ZHAO Lingling,etal.Active semantic recognition method based on spatial-temporal period pattern mining[Jl.CAAI transactions on intelligent systems,2021,16(1):162-169. Active semantic recognition method based on spatial-temporal period pattern mining GUO Maozu,SHAO Shoufei,ZHAO Lingling',LI Yang2 (1.School of Electrical and Information Engineering,Beijing University of Civil Engineering and Architecture,Beijing 100044, China;2.Beijing Key Laboratory of Intelligent Processing for Building Big Data,Beijing University of Civil Engineering and Archi- tecture,Beijing 100044,China;3.School of Computer Science and Technology,Harbin Institute of Technology,Harbin 150001, China) Abstract:Active semantic recognition aims to mine people's activities from spatial-temporal data recording through the smart equipment they carry.Traditional studies paid more attention to studying the spatial features of spatial-temporal data but failed to mine temporal features adequately.Considering both features,this work proposes an active semantic recognition method based on period pattern mining.First,trajectories that have already been separated from raw traject- ories are clustered based on the spatial distance.The periods of reference spots that are frequently visited by the people are then mined according to the sequence of clustering.Based on the visit period and combined with the residence time at the location and the distribution of interest points nearby,a classification model is constructed to identify the activity semantics of human individuals.The experimental results on the check-in dataset and simulation data show that the val- id recognition accuracy of active semantic recognition combined with periodic characteristics increases by 20%more than that without periodic characteristics.Under the same two check-in datasets and compared with other recognition methods,the accuracy is improved by more than 10%. Keywords:spatial-temporal trajectory;spatial-temporal close connection;density clustering;stay time;active semantic recognition;period pattern mining;random forest 活动语义识别是指从人类的时空轨迹数据或 收稿日期：2020-12-20. 基金项目：国家自然科学基金项目(61871020)， 离散的位置序列中挖掘出人类的活动信息Ⅲ。智 通信作者：赵玲玲.E-mail:zhaoll@hit.edu.cn 能移动终端的广泛应用提供了海量的个体位置相

DOI: 10.11992/tis.202012035 基于时空周期模式挖掘的活动语义识别方法 郭茂祖1,2，邵首飞1,2，赵玲玲3 ，李阳1,2 （1. 北京建筑大学 电气与信息工程学院，北京 100044; 2. 北京建筑大学 建筑大数据智能处理方法研究北京市 重点实验室，北京 100044; 3. 哈尔滨工业大学 计算机科学与技术学院，黑龙江 哈尔滨 150001） 摘 要：传统的活动语义识别研究侧重从时空轨迹的空间信息中提取人类的活动语义，对时空轨迹数据的时间 特性挖掘不足。本文兼顾时间和空间特征，提出了一种基于周期模式挖掘的活动语义识别方法。首先将分离 出的活动轨迹数据通过空间距离进行密度聚类分成不同轨迹簇；然后，根据轨迹簇的时序特征挖掘个体对特定 位置的访问周期，基于该访问周期，并结合在该位置的停留时间，及其附近兴趣点分布等特征构建分类模型， 识别人类个体的活动语义。基于签到数据和仿真数据的实验结果表明，结合周期特征的活动语义识别方法相 比没有加入周期特征的实验结果有效提升识别精度 20% 以上，在 2 个相同的签到数据集下，对比其他的识别方 法提升精度 10% 以上。 关键词：时空轨迹；时空紧密相连性；密度聚类；停留时间；活动语义识别；周期模式挖掘；随机森林 中图分类号：TP181 文献标志码：A 文章编号：1673−4785(2021)01−0162−08 中文引用格式：郭茂祖, 邵首飞, 赵玲玲, 等. 基于时空周期模式挖掘的活动语义识别方法 [J]. 智能系统学报, 2021, 16(1): 162–169. 英文引用格式：GUO Maozu, SHAO Shoufei, ZHAO Lingling, et al. Active semantic recognition method based on spatial-temporal period pattern mining[J]. CAAI transactions on intelligent systems, 2021, 16(1): 162–169. Active semantic recognition method based on spatial-temporal period pattern mining GUO Maozu1,2 ，SHAO Shoufei1,2 ，ZHAO Lingling3 ，LI Yang1,2 (1. School of Electrical and Information Engineering, Beijing University of Civil Engineering and Architecture, Beijing 100044, China; 2. Beijing Key Laboratory of Intelligent Processing for Building Big Data, Beijing University of Civil Engineering and Archi￾tecture, Beijing 100044, China; 3. School of Computer Science and Technology, Harbin Institute of Technology, Harbin 150001, China) Abstract: Active semantic recognition aims to mine people’s activities from spatial-temporal data recording through the smart equipment they carry. Traditional studies paid more attention to studying the spatial features of spatial-temporal data but failed to mine temporal features adequately. Considering both features, this work proposes an active semantic recognition method based on period pattern mining. First, trajectories that have already been separated from raw traject￾ories are clustered based on the spatial distance. The periods of reference spots that are frequently visited by the people are then mined according to the sequence of clustering. Based on the visit period and combined with the residence time at the location and the distribution of interest points nearby, a classification model is constructed to identify the activity semantics of human individuals. The experimental results on the check-in dataset and simulation data show that the val￾id recognition accuracy of active semantic recognition combined with periodic characteristics increases by 20% more than that without periodic characteristics. Under the same two check-in datasets and compared with other recognition methods, the accuracy is improved by more than 10%. Keywords: spatial-temporal trajectory; spatial-temporal close connection; density clustering; stay time; active semantic recognition; period pattern mining; random forest 活动语义识别是指从人类的时空轨迹数据或 离散的位置序列中挖掘出人类的活动信息[1]。智 能移动终端的广泛应用提供了海量的个体位置相 收稿日期：2020−12−20. 基金项目：国家自然科学基金项目 (61871020). 通信作者：赵玲玲. E-mail：zhaoll@hit.edu.cn. 第 16 卷第 1 期 智 能 系 统 学 报 Vol.16 No.1 2021 年 1 月 CAAI Transactions on Intelligent Systems Jan. 2021

第1期 郭茂祖，等：基于时空周期模式挖掘的活动语义识别方法 ·163· 关的时空数据，如社交媒体签到数据、GPS(global 收入、居住等特征和支持向量机(support vector positioning system)轨迹数据和手机信令数据等。 machine,SVM)模型来识别用户的活动语义。文 这些数据为精细粒度下个体的活动识别提供了有 献[14]利用社交签到数据，融合签到地点频次等 力支撑。相比原始的时空轨迹数据或位置序列信 信息识别活动语义。文献[15]采用聚类方法获取 息，带有语义的活动轨迹数据更能直观地反应人 空间热度特征并利用极限梯度提升(eXtreme 类的具体活动，这有助于深人了解每个个体的生 gradient boosting,XGBoost)建模识别用户活动模 活模式，发现个体的个性需求，为个体提供定制化 式。文献20]逐步提取用户的实时位置，将运动 服务，也可以发现与个体活动模式相同或相似的 过程中访问的地点与人类的活动相关联起来，进 群体，进而识别群体的共性特征和需求)。这些 而推断用户进行的活动。上述方法的核心思想是 信息的挖掘可以用于配置交通资源和资源规划， 从活动轨迹点的空间信息提取特征来建模，但是 如公交车的班次和地点的设定、共享单车的投放 用户的轨迹信息在空间和时间上是紧密相连的， 量和投放地点、商场的选址等，从而达到优化社 因此该类方法忽略了时间特性，导致该类方法的 会资源配置、精细化满足各种群体的不同需求的 识别结果过度依赖于POI获取的准确性而忽视了 目的s 用户某些活动难以准确获取相应POI的实际问 人类的活动轨迹在空间上是多重交叉的四 题，而且容易混淆用户在不同时间访问相近的地 在时间上表现出序列性和一定的周期性s1。已 方发生的不同活动。 有的大部分方法都是在GPS轨迹数据的空间特 人类活动具有显著的周期性特征，已有的 征一活动地，点的POI(point of interest)数据和运动 研究就轨迹的周期性进行挖掘，如文献[16]中就 特征（速度、加速度）之上构建分类模型，进而识 移动对象频繁访问某一地方的核心点(reference 别用户的活动语义1。该类方法忽略了活动轨 spot)提取用户空间信息，并融合傅里叶变换 迹的时间特性，导致该类方法的识别结果过度依 (fourier transform)获取用户的时间信息。通过提 赖于POI获取的准确性，而忽视了用户某些活 取核心点提取用户的空间信息，再通过傅里叶变 动，难以准确获取相应POI的实际问题，而且容 换检测活动发生的周期，提取用户的时间信息。 易混淆用户在不同时间访问相近的地方发生的不 使用傅里叶变换挖掘用户活动周期时必须获取轨 同活动，本文在文献[16-17]提取用户活动轨迹周 迹数据的均值采样，但是由于天气的原因无法获 期模式的方法上使用LombScargle1.11方法挖掘 取均值采样的轨迹数据。此时必须通过线性插值 用户轨迹数据的周期作为用户活动特征中的周期 的方法使不规则的样本变成均值的轨迹。但是由 特征，再结合用户活动的持续时间、活动中心点 于轨迹数据量庞大的原因，这种插值会带来巨大 附近POL,及活动发生的年份、月份、季节、日期、 的计算量。文献[17]在此基础上，先将单个用户 是否是节假日和是否是周末等时间特征)，使用 轨迹数据运用基于密度的带噪声应用空间聚类 随机森林分类器挖掘用户活动语义。 (density based spatial clustering of application with noise,.DBSCAN),聚类后获取用户的活动轨迹点， 1相关研究 再结合OpenStreetMap中的POI信息进行地，点匹 现有的活动语义识别方法可以分为：基于空 配得到带有地点特征的轨迹数据，最后使用 间特征的识别方法和基于运动特征的识别方法。 LombScargle1&2)算法挖掘用户活动的周期。该 文献[11]从用户活动的空间角度，采用活动地点 算法可以直接从非规则采样的轨迹中挖掘出用户 的POI数据挖掘语义信息。并且考虑到POI数据 的活动周期。但是文献[16-17]均是挖掘用户轨 不均匀以及POI在不同地区主题下对用户活动的 迹的周期模式，并没有结合用户活动产生的轨迹 影响度不同等因素，引入隐含狄利克雷分布(lat 点的空间信息挖掘用户的活动语义。 ent dirichlet allocation,LDA)主题模型提取活动地 2周期模式挖掘 点POI的主题特征。通过地区内POI与主题的相 关程度来确定在该主题下POI对用户活动的影响 针对个体的部分活动存在周期性这一特征，本 度，从而确定用户在活动地点产生的活动模式。 文从访问位置的周期性挖掘出发，将周期性活动 文献[12]使用移动基站提供的数据集结合Open- 的周期提取、停留时间、周期性活动的相关POI StreetMap上的POI信息对用户的行为进行识别 进行提取，构成以时空周期性为核心的特征表示。 和预测。文献[13]设计自助数据采集系统，以志 单个用户产生的活动轨迹表示为一个三维的 愿者的方式采集数据，并利用用户的轨迹、年龄、 时空序列，则用户一天的活动序列S可以表示为

关的时空数据，如社交媒体签到数据、GPS(global positioning system) 轨迹数据和手机信令数据等[2]。 这些数据为精细粒度下个体的活动识别提供了有 力支撑。相比原始的时空轨迹数据或位置序列信 息，带有语义的活动轨迹数据更能直观地反应人 类的具体活动，这有助于深入了解每个个体的生 活模式，发现个体的个性需求，为个体提供定制化 服务，也可以发现与个体活动模式相同或相似的 群体，进而识别群体的共性特征和需求[3]。这些 信息的挖掘可以用于配置交通资源和资源规划[4] ， 如公交车的班次和地点的设定、共享单车的投放 量和投放地点、商场的选址等，从而达到优化社 会资源配置、精细化满足各种群体的不同需求的 目的[1, 5-6]。 人类的活动轨迹在空间上是多重交叉的[7] ， 在时间上表现出序列性和一定的周期性[8-10]。已 有的大部分方法都是在 GPS 轨迹数据的空间特 征—活动地点的 POI(point of interest) 数据和运动 特征 (速度、加速度) 之上构建分类模型，进而识 别用户的活动语义[11-15]。该类方法忽略了活动轨 迹的时间特性，导致该类方法的识别结果过度依 赖于 POI 获取的准确性，而忽视了用户某些活 动，难以准确获取相应 POI 的实际问题，而且容 易混淆用户在不同时间访问相近的地方发生的不 同活动，本文在文献 [16-17] 提取用户活动轨迹周 期模式的方法上使用 LombScargle[18-19] 方法挖掘 用户轨迹数据的周期作为用户活动特征中的周期 特征，再结合用户活动的持续时间、活动中心点 附近 POI，及活动发生的年份、月份、季节、日期、 是否是节假日和是否是周末等时间特征[15] ，使用 随机森林分类器挖掘用户活动语义。 1 相关研究 现有的活动语义识别方法可以分为：基于空 间特征的识别方法和基于运动特征的识别方法。 文献 [11] 从用户活动的空间角度，采用活动地点 的 POI 数据挖掘语义信息。并且考虑到 POI 数据 不均匀以及 POI 在不同地区主题下对用户活动的 影响度不同等因素，引入隐含狄利克雷分布 (lat￾ent dirichlet allocation，LDA) 主题模型提取活动地 点 POI 的主题特征。通过地区内 POI 与主题的相 关程度来确定在该主题下 POI 对用户活动的影响 度，从而确定用户在活动地点产生的活动模式。 文献 [12] 使用移动基站提供的数据集结合 Open￾StreetMap 上的 POI 信息对用户的行为进行识别 和预测。文献 [13] 设计自助数据采集系统，以志 愿者的方式采集数据，并利用用户的轨迹、年龄、 收入、居住等特征和支持向量机 (support vector machine, SVM) 模型来识别用户的活动语义。文 献 [14] 利用社交签到数据，融合签到地点频次等 信息识别活动语义。文献 [15] 采用聚类方法获取 空间热度特征并利用极限梯度提升 (eXtreme gradient boosting，XGBoost) 建模识别用户活动模 式。文献 [20] 逐步提取用户的实时位置，将运动 过程中访问的地点与人类的活动相关联起来，进 而推断用户进行的活动。上述方法的核心思想是 从活动轨迹点的空间信息提取特征来建模，但是 用户的轨迹信息在空间和时间上是紧密相连的， 因此该类方法忽略了时间特性，导致该类方法的 识别结果过度依赖于 POI 获取的准确性而忽视了 用户某些活动难以准确获取相应 POI 的实际问 题，而且容易混淆用户在不同时间访问相近的地 方发生的不同活动。 人类活动具有显著的周期性特征[9] ，已有的 研究就轨迹的周期性进行挖掘，如文献 [16] 中就 移动对象频繁访问某一地方的核心点 (reference spot) 提取用户空间信息，并融合傅里叶变换 (fourier transform) 获取用户的时间信息。通过提 取核心点提取用户的空间信息，再通过傅里叶变 换检测活动发生的周期，提取用户的时间信息。 使用傅里叶变换挖掘用户活动周期时必须获取轨 迹数据的均值采样，但是由于天气的原因无法获 取均值采样的轨迹数据。此时必须通过线性插值 的方法使不规则的样本变成均值的轨迹。但是由 于轨迹数据量庞大的原因，这种插值会带来巨大 的计算量。文献 [17] 在此基础上，先将单个用户 轨迹数据运用基于密度的带噪声应用空间聚类 (density based spatial clustering of application with noise，DBSCAN)，聚类后获取用户的活动轨迹点， 再结合 OpenStreetMap 中的 POI 信息进行地点匹 配得到带有地点特征的轨迹数据，最后使 用 LombScargle[18, 21] 算法挖掘用户活动的周期。该 算法可以直接从非规则采样的轨迹中挖掘出用户 的活动周期。但是文献 [16-17] 均是挖掘用户轨 迹的周期模式，并没有结合用户活动产生的轨迹 点的空间信息挖掘用户的活动语义。 2 周期模式挖掘 针对个体的部分活动存在周期性这一特征，本 文从访问位置的周期性挖掘出发，将周期性活动 的周期提取、停留时间、周期性活动的相关 POI 进行提取，构成以时空周期性为核心的特征表示。 S 单个用户产生的活动轨迹表示为一个三维的 时空序列，则用户一天的活动序列 可以表示为 第 1 期 郭茂祖，等：基于时空周期模式挖掘的活动语义识别方法 ·163·

·164· 智能系统学报 第16卷 S={S1,S2,…,Sm} 2.2周期模式挖掘 Si=((Ing,lati,).(Ing,lati).. 对于GPS轨迹数据，一个连续采样的轨迹满 (Ingi,lat,t),i [1,m] 足在某个轨迹簇P:中对任意连续的i,j使得 式中：lng、lat、t表示轨迹点的经度、纬度、时间，i、 -=--成立。一个不连续采样的轨迹满 in表示用户进行第i个活动的第一和最后一个轨 迹点。需要说明的是，活动轨迹并不总是连续的， 足存在连续的i,j使得1t-≠-t-成立。以 它只表示用户在某地发生某个活动时产生的轨迹。 往挖掘序列周期模式使用的方法为傅里叶变换 2.1活动地点匹配 (fourier transform)和自相关(autocorrelation)s,l6。 活动地点匹配是将原始的轨迹序列S依据空 使用傅里叶变换有一个重要的前提条件，要求输 间距离和时间距离使用DBSCAN算法进行聚类， 人的样本必须是均值采样。然而，由于天气和采 进而将聚类后每个轨迹点所在的轨迹簇D标记 样设备故障原因，自然采集的轨迹基本上都是不 为该轨迹点的place-id2。空间上的距离使用经 规则的。因此使用傅里叶变换之前需要进行线性 纬度之间的欧几里得距离，时间距离使用轨迹点 插值，将不规则样本补全。对于大量的轨迹数据 的时间戳差值，最后将空间距离和时间距离的算 来说，线性插值的计算量相当大。LombScargle算 术平均值作为聚类距离，如式(1)。聚类后为每个 法由文献[18]提出用于检测不规则采样时间序列 聚类簇分配一个D作为分类簇中所有对应轨迹 周期，并由文献21]用LombScargle功率-频率图 点的place-.id,聚类的同时能够舍弃一些离群点， 检测出不规则间隔的时间序列周期。该算法能够 聚类后得四维向量：(ng,lat,t,place_id,) 省去计算量大的线性插值，并且能够识别出序列 space_d;=(Ing,-Ing )+(lat;-lat 中所有的周期1。 对于时间序列来说，x是采样时刻对应的 time_di=time;-time; d (space idy+time di 样本值j=l,2,…,N。LombScargle图能够反应出 2 序列的周期，LombScargle周期图通过式(I)计算 算法1 DBSCAN算法。 得出： 输入样本集D=(x1,2,…,x),领域参数 (e,MinPts),样本距离度量方式。 y-cos2f6- 1)初始化核心对象集合2=⑦，聚类簇个数 Pis(f)= k=0,未访问的样本集合「=D,簇划分C=⑦ ∑cos2(2ft,-) 2)for j in1 l,2,…,ndo (1) 3)通过距离度量方式，找到x的ε邻域子样 本集N(x) 2-sin2-》 4)ifN(x）≥MinPts sin2(2nf(t;-T)) 5)2=2U{xl 6)end for 式中：x是时间序列的均值；σ2是时间序列的方 7)while2≠odo 差；其计算为 8)随机选取2中的一个核心对象o,2={o, k=k+1.Ck=o).T=T-fo) 9)if 2cur 10)C={C1,C2,…,Ch,2=2-Cg continue 式中τ是每个f特定的值，以保证对于不规则样 11)else 本的时移不变性，其中τ和∫的关系为 12)2=2-C 13)end if 立smRP 14)在2r中取出一个核心对象o通过邻域距 tan(2(2πf)x)= 离阈值ε找出所有的ε-邻域N(o),4=N(o)nT, Ck=C:U4,r=T-4,2cur =Qcur U(4n2)-o' cos(2(2m)) 15)end while 对于LombScargle图，图中每个峰值表示一个 输出簇划分C={C1,C2,…,C。 周期。LombScargle图是通过错误预警概率(false

S ={S 1,S 2,··· ,S m} S i ={(lngi1 ,lati1 ,ti1 ),(lngi2 ,lati2 ,ti2 ),··· , (lngin ,latin ,tin)},i ∈ [1,m] lng lat t i1 in i 式中： 、 、 表示轨迹点的经度、纬度、时间， 、 表示用户进行第 个活动的第一和最后一个轨 迹点。需要说明的是，活动轨迹并不总是连续的， 它只表示用户在某地发生某个活动时产生的轨迹。 2.1 活动地点匹配 S (lngi ,lati ,ti ,place_idi ) 活动地点匹配是将原始的轨迹序列 依据空 间距离和时间距离使用 DBSCAN 算法进行聚类， 进而将聚类后每个轨迹点所在的轨迹簇 ID 标记 为该轨迹点的 place-id[22]。空间上的距离使用经 纬度之间的欧几里得距离，时间距离使用轨迹点 的时间戳差值，最后将空间距离和时间距离的算 术平均值作为聚类距离，如式 (1)。聚类后为每个 聚类簇分配一个 ID 作为分类簇中所有对应轨迹 点的 place-id，聚类的同时能够舍弃一些离群点， 聚类后得四维向量： space_di j = √ (lngi −lngj ) 2 +(lati −latj) 2 time_di j =   timei −timej    di j = (space_idi j +time_di j) 2 算法 1 DBSCAN 算法。 D = (x1, x2,··· , xn) (ε,MinPts) 输 入 样本集 , 领域参数 ，样本距离度量方式。 Ω = ∅ k = 0 Γ = D C = ∅ 1) 初始化核心对象集合 ，聚类簇个数 ，未访问的样本集合 ，簇划分 2) for j in 1,2,··· ,n do xj ε Nε ( xj ) 3) 通过距离度量方式，找到 的 邻域子样 本集 Nε ( xj ) 4) if ⩾ MinPts Ω = Ω∪ { xj } 5) 6) end for 7) while Ω , ∅ do Ω o Ωcur = {o} k = k+1 Ck = {o} Γ = Γ −{o} 8) 随机选取 中的一个核心对象 ， ， ， ， 9) if Ωcur = ∅ 10) C = {C1,C2,··· ,Ck}, Ω = Ω−Ck continue 11) else 12) Ω = Ω−Ck 13) end if Ωcur o ′ ε ε− Nε (o ′ ) ∆ = Nε (o ′ )∩Γ Ck = Ck ∪∆ Γ = Γ −∆ Ωcur = Ωcur ∪(∆∩Ω)−o ′ 14) 在 中取出一个核心对象 通过邻域距 离阈值 找出所有的 邻域 ， ， ， ， 15) end while 输出 簇划分 C = {C1,C2,··· ,Ck}。 2.2 周期模式挖掘 pi i, j   tj− tj−1    = |ti −ti−1| i, j   tj− tj−1    , |ti −ti−1| 对于 GPS 轨迹数据，一个连续采样的轨迹满 足在某个轨迹簇 中对任意连续的 使 得 成立。一个不连续采样的轨迹满 足存在连续的 使得 成立。以 往挖掘序列周期模式使用的方法为傅里叶变换 (fourier transform) 和自相关 (autocorrelation)[8, 16]。 使用傅里叶变换有一个重要的前提条件，要求输 入的样本必须是均值采样。然而，由于天气和采 样设备故障原因，自然采集的轨迹基本上都是不 规则的。因此使用傅里叶变换之前需要进行线性 插值，将不规则样本补全。对于大量的轨迹数据 来说，线性插值的计算量相当大。LombScargle 算 法由文献 [18] 提出用于检测不规则采样时间序列 周期，并由文献 [21] 用 LombScargle 功率-频率图 检测出不规则间隔的时间序列周期。该算法能够 省去计算量大的线性插值，并且能够识别出序列 中所有的周期[23]。 xj tj j = 1,2,··· ,N 对于时间序列来说， 是采样 时刻对应的 样本值 。LombScargle 图能够反应出 序列的周期，LombScargle 周期图通过式 (1) 计算 得出： PLS (f) = 1 2σ2      ∑N j=1 ((xj − x¯ ) cos(2π f ( tj −τ ))   2 ∑N j=1 cos2 ( 2π f(tj −τ) ) +   ∑N j=1 ((xj − x¯)sin(2π f(tj −τ))   2 sin2 (2π f(tj −τ))    (1) x σ 式中： 是时间序列的均值； 2 是时间序列的方 差；其计算为 x = 1 N ∑N j=1 xj σ 2 = 1 N −1 ∑N j=1 (xj − x¯) 2 τ f τ f 式中 是每个 特定的值，以保证对于不规则样 本的时移不变性，其中 和 的关系为 tan(2(2π f)τ) = ∑N j=1 sin(2(2π f)tj) ∑N j=1 cos(2(2π f)tj) 对于 LombScargle 图，图中每个峰值表示一个 周期。LombScargle 图是通过错误预警概率 (false ·164· 智 能 系 统 学 报 第 16 卷

第1期 郭茂祖，等：基于时空周期模式挖掘的活动语义识别方法 ·165· alarm probability)来表示该峰值的显著性，其计算为 3.1特征提取 P,(Pmax)=1-[1-exp(-Pma)]W (2) 时空轨迹具有序列性、时空紧密性、不规矩 从式(2)的分布得出，一个有效的功率峰值 的时间间隔、空间层次性和包含背景语义信息等 乙，在给定一个误差α时必须要超过统计显著性的 特征。序列性指前后2个相邻的轨迹点在时间上 值，可由式(3)计算得出： 有先后顺序。紧密性指轨迹的空间特征和时间特 z=-ln1-(1-a) (3) 征紧密相连，不能分割。不规则的时间间隔指现 实生活中由设备采集到的数据是非均值采样。空 算法2周期模式挖掘算法。 间层次性指人的时空轨迹是区域聚集性和在不同 输入P={p,p2,…pnl,其中p={,place-id}, i,j=1,2,…,n 板块下有不同的层次表示。背景语义能一定程度 1)for pi in P do 上反映活动者在这个地方进行的活动类型。针对 这些特性，本文加入了用户活动参考点的经纬度 2)for p;in P do 作为空间特征。通过地图API(application pro- 3)if place-id;place-id gramming interface)获得的POI信息，作为背景语 4)将P,加入P 义特征。进行活动的起始时间、活动的时长、活 5)end for 动的日期（活动发生的年份、月份、日期、是否周 6)P'代入式(1)求出PsL的峰值Pmx,对应频 末)作为时间特征，以及活动的周期特征（包含识 率f,取倒数表示周期T: 别周期过程中每个周期对应的错误预警概率)。 7)按照式(2)求出Pmax的错误预警概率Pm 3.2模型选择 8)q:=t,place-id,T,Pm将g:加入Q中 随机森林是采用有放回抽样的方式从训练集 9)end for 中选取一定比例的样本和一定个数的特征作为子 输出带有周期的GPS轨迹序列Q= 训练集，使用多个决策树在不同的子训练集中进行 {q1,92,…,9n}o 分类，并且将最后多数分类器得到的分类结果作 3活动语义识别 为最终分类结果的分类器。该分类器有较好的抗 噪性，并且在高维和大数据的数据集下有很好的 基于周期模式挖掘的语义识别流程如图1。 分类性能，本文采用随机森林算法识别活动语义。 首先，将用户的活动轨迹聚类成若干个轨迹簇， 3.2.1决策树 然后为不同轨迹簇中的每个轨迹点分配一个独特 决策树模型呈树形结构，在分类问题中，表示 的D作为识别周期模式的地点标识。之后使用 基于特征对实例进行分类的过程。决策树学习过 这些地点标识识别出每个活动发生的周期模式， 程包含3个步骤：特征选择、决策树的生成和决 计算活动轨迹中心点，利用轨迹中心点获取活动 策树的剪枝。 地点附近的POI信息，最后将这些特征作为随机 1)特征选择。 森林分类器的输入识别用户的活动义。 通过计算并比较特征的信息嫡或者基尼系数 进行特征选择。在分类问题中，设有K个类别， 原始轨迹数据 样本属于第k个类别的概率为P,则概率分布的 基尼系数由式(4)得到： Gini(p)=1- (4) 带有活动语 地点匹配 A=1 义的轨迹 样本集合D的基尼指数为 Gini(D)= (5) 带有place-id 的语义轨迹 活动语义识别 式中Ck为数据集D中属于k类的样本子集。如 果数据集D根据特征A在某个取值a上进行分 割，得到D1、D22个部分后，那么在特征A下集合 周期检测 带有周期的 语义轨迹 D的基尼系数表示为 Gini(D.A)=Gini(D) Gini(D2) (6) 图1本文提出的方法总体流程 II IDI Fig.1 Overall procedure of our proposed method 2)决策树生成

alarm probability) 来表示该峰值的显著性，其计算为 Pr (pmax) = 1− [ 1−exp(−pmax) ]N (2) z α 从式 (2) 的分布得出，一个有效的功率峰值 ，在给定一个误差 时必须要超过统计显著性的 值，可由式 (3) 计算得出： z = −ln[ 1−(1−α) 1 N ] (3) 算法 2 周期模式挖掘算法。 P = {p1,p2,··· ,pn} pi = { ti ,place−idi } , i, j = 1,2,··· ,n 输入 ，其中 1) for pi in P do 2) for pj in P do 3) if place−idj ≠ place−idi pj P ′ 4) 将 加入 5) end for P ′ PSL pmax fi Ti 6) 代入式 (1) 求出 的峰值 ,对应频 率 , 取倒数表示周期 7) 按照式 (2) 求出 pmax 的错误预警概率 Pri qi = ti ,place−idi ,Ti 8) ,Pri 将 qi 加入 Q 中 9) end for Q = {q1,q2,··· ,qn} 输 出 带有周期 的 G P S 轨迹序列 。 3 活动语义识别 基于周期模式挖掘的语义识别流程如图 1。 首先，将用户的活动轨迹聚类成若干个轨迹簇， 然后为不同轨迹簇中的每个轨迹点分配一个独特 的 ID 作为识别周期模式的地点标识。之后使用 这些地点标识识别出每个活动发生的周期模式， 计算活动轨迹中心点，利用轨迹中心点获取活动 地点附近的 POI 信息，最后将这些特征作为随机 森林分类器的输入识别用户的活动义。 原始轨迹数据 地点匹配 周期检测 活动语义识别 带有 place-id 的语义轨迹 带有活动语 义的轨迹 带有周期的 语义轨迹 图 1 本文提出的方法总体流程 Fig. 1 Overall procedure of our proposed method 3.1 特征提取 时空轨迹具有序列性、时空紧密性、不规矩 的时间间隔、空间层次性和包含背景语义信息等 特征。序列性指前后 2 个相邻的轨迹点在时间上 有先后顺序。紧密性指轨迹的空间特征和时间特 征紧密相连，不能分割。不规则的时间间隔指现 实生活中由设备采集到的数据是非均值采样。空 间层次性指人的时空轨迹是区域聚集性和在不同 板块下有不同的层次表示。背景语义能一定程度 上反映活动者在这个地方进行的活动类型。针对 这些特性，本文加入了用户活动参考点的经纬度 作为空间特征。通过地图 API (application pro￾gramming interface) 获得的 POI 信息，作为背景语 义特征。进行活动的起始时间、活动的时长、活 动的日期 (活动发生的年份、月份、日期、是否周 末) 作为时间特征，以及活动的周期特征 (包含识 别周期过程中每个周期对应的错误预警概率)。 3.2 模型选择 随机森林是采用有放回抽样的方式从训练集 中选取一定比例的样本和一定个数的特征作为子 训练集，使用多个决策树在不同的子训练集中进行 分类，并且将最后多数分类器得到的分类结果作 为最终分类结果的分类器。该分类器有较好的抗 噪性，并且在高维和大数据的数据集下有很好的 分类性能，本文采用随机森林算法识别活动语义。 3.2.1 决策树 决策树模型呈树形结构，在分类问题中，表示 基于特征对实例进行分类的过程。决策树学习过 程包含 3 个步骤：特征选择、决策树的生成和决 策树的剪枝。 1) 特征选择。 K k pk 通过计算并比较特征的信息熵或者基尼系数 进行特征选择。在分类问题中，设有 个类别， 样本属于第 个类别的概率为 ,则概率分布的 基尼系数由式 (4) 得到： Gini(p) = 1− ∑K k=1 p 2 k (4) 样本集合 D 的基尼指数为 Gini(D) = 1− ∑K k=1 ( |Ck | |D| )2 (5) Ck D k D A a D1 D2 A D 式中 为数据集 中属于 类的样本子集。如 果数据集 根据特征 在某个取值 上进行分 割，得到 、 2 个部分后，那么在特征 下集合 的基尼系数表示为 Gini(D,A) = |D1| |D| Gini(D1)+ |D2| |D| Gini(D2) (6) 2) 决策树生成。 第 1 期 郭茂祖，等：基于时空周期模式挖掘的活动语义识别方法 ·165·

·166· 智能系统学报 第16卷 决策树生成有ID3、C4.5和分类回归树(clas- Sports,,Rest,Medical,Art)。实验中，为了能识别用 sification and regression tree,CART) 户的周期，设定少于5次访问次数的地点为用户 本文用到的是CART算法构建分类树。 不常去的地点，没有周期性，实验中去除了这些数 CART算法采用基尼系数作为评判准则，通过式 据。TKY签到数据中标签分布如图2，标记完的 (6)选取使得基尼系数最小的特征和对应特征取 签到数据如图3。 值递归构建二叉树分类树进行分类。 183957 3)决策树的剪枝。 175 决策树生成算法递归地产生决策树，直到不能 150 进行下去为止。这样的算法产生的树对训练数据 3 100 分类很准确，但对未知数据集的分类往往没有那 么准确一过拟合。解决过拟合的方式是考虑生成 0 树的复杂度，对已经生成的决策树进行简化一剪枝。 25 297鳞313 3.2.2基于随机森林的活动语义分类 的冯四 随机森林是由很多独立的决策树组成的一个 心今s心 森林，每棵树之间相互独立，在最终模型组合时， 活动种类 通过投票的方式决定最终的分类结果。 图2签到数据种类分布 算法3活动语义识别算法。 Fig.2 Distribution of check-ins categories 输入提取完的活动轨迹特征矩阵M。 teer_id plascel)place_itensIT)place name lat Ing time_offet time 154140d5a458dd489535.705139.62540 Twe Apr Shwopping 1)将特征矩阵分成训练集M1和测试集M2。 4b7h884bfssddsd4892Ramen/No35.716 139.8 540 Tu Apr Resta室t 114416f14d9540ea243.3571513948540 Tue Apr Shoppine 2)从训练集M,中随机有放回选取一定比例 868 4el78614hsd181489To0 d Drin35,726139.78540 Tue Apr Resausu四 158 46X304f2a2101r35.66139.73 Tue Apr Work 的样本M1:(1表示第i棵决策树)作为一棵决策树 141 48248489/日3.705139.62340 Tue Apt Shoppag 4e2w1e4d94B0e24335.706139.62540 Tue Apr Shop眼 的输入样本。 :Train Srarine 35. 13秋 1 e Apr Tea 163 Tue Apr Ealertae 03 I的Apr Resta时 3)通过CART方法构建n个决策树，将所有 决策树的分类结果概率最高的作为随机森立分类 图3签到数据样式 Fig.3 Examples of check-ins data 器的结果。 4)n从1~200变化，得到分类器最好精度时 4.2实验结果 对应的决策树的个数。 4.2.1周期模式的识别 5)将训练完成的分类器放在测试集上测试。 识别周期模式中，识别的周期通常指最小正周 输出模型的训练和测试精度。 期，因此需要传入周期的取值范围限制识别出周期 输出模型的精度。 的大小。去除10个月少于5次签到的数据周期为 (0,1440)小时(1个月按30d计算)，某个用户的某 4实验结果与分析 个活动周期一频率图如图4所示，通过图5中周 期一频率图得到最大峰值对应的周期为24.15h。 4.1实验设置 这表明用户在这个地方的活动每隔24.15h会发 本文采用的数据是来自Yang等24]通过 生一次。 Foursquare提供的开发者API收集的来自纽约和 4.2.2活动语义识别结果 东京2个城市用户的签到数据，数据有8个特征： 为了验证周期特征对活动语义识别的有效 用户D、活动地点D、场地类别D、场地类别名 性，本文在相同的实验条件下，对比了加入和不 称、经度、纬度、UTC时间、时间偏移量。东京数 据集TKY包含57万条数据，纽约数据集NYC包 加入周期模式特征进行活动语义的识别的性能。 分别使用准确度、精准率、召回率、F,值对分类结 含22万条数据，这2个城市的签到数据集时间跨 度超过10个月，从2012年4月12日一到 果进行的评价，其计算为 TP 2013年2月16日纽约1083个用户和东京2 precison (7) (TP+FP) 293个用户的签到数据记录。在有无周期对比实 (TP+TN) 验中本文根据签到地点名称采用多专家决策的方 accuracy (8) (TP+FP+TN+FN) 法最终标记为l2类(Shopping,Restaurant,,Work, TP recall (9) Travel,Entertainment,Service,Meeting,Education, (TP+FN)

决策树生成有 ID3、C4.5 和分类回归树 (clas￾sification and regression tree，CART)。 本文用到的 是 CART 算法构建分类树。 CART 算法采用基尼系数作为评判准则，通过式 (6) 选取使得基尼系数最小的特征和对应特征取 值递归构建二叉树分类树进行分类。 3) 决策树的剪枝。 决策树生成算法递归地产生决策树，直到不能 进行下去为止。这样的算法产生的树对训练数据 分类很准确，但对未知数据集的分类往往没有那 么准确—过拟合。解决过拟合的方式是考虑生成 树的复杂度，对已经生成的决策树进行简化—剪枝。 3.2.2 基于随机森林的活动语义分类 随机森林是由很多独立的决策树组成的一个 森林，每棵树之间相互独立，在最终模型组合时， 通过投票的方式决定最终的分类结果。 算法 3 活动语义识别算法。 输入 提取完的活动轨迹特征矩阵 M。 1) 将特征矩阵分成训练集 M1 和测试集 M2。 M1 M1i 2) 从训练集 中随机有放回选取一定比例 的样本 (i 表示第 i 棵决策树) 作为一棵决策树 的输入样本。 3) 通过 CART 方法构建 n 个决策树，将所有 决策树的分类结果概率最高的作为随机森立分类 器的结果。 4) n 从 1~200 变化，得到分类器最好精度时 对应的决策树的个数。 5) 将训练完成的分类器放在测试集上测试。 输出模型的训练和测试精度。 输出 模型的精度。 4 实验结果与分析 4.1 实验设置 本文采用的数据是来 自 Yan g 等 [ 2 4 ] 通 过 Foursquare 提供的开发者 API 收集的来自纽约和 东京 2 个城市用户的签到数据，数据有 8 个特征： 用户 ID、活动地点 ID、场地类别 ID、场地类别名 称、经度、纬度、UTC 时间、时间偏移量。东京数 据集 TKY 包含 57 万条数据，纽约数据集 NYC 包 含 22 万条数据，这 2 个城市的签到数据集时间跨 度 超 过 1 0 个月， 从 201 2 年 4 月 1 2 日 — 到 2013 年 2 月 16 日纽约 1 083 个用户和东京 2 293 个用户的签到数据记录。在有无周期对比实 验中本文根据签到地点名称采用多专家决策的方 法最终标记为 12 类 (Shopping, Restaurant, Work, Travel, Entertainment, Service, Meeting, Education, Sports, Rest, Medical, Art)。实验中，为了能识别用 户的周期，设定少于 5 次访问次数的地点为用户 不常去的地点，没有周期性,实验中去除了这些数 据。TKY 签到数据中标签分布如图 2，标记完的 签到数据如图 3。 150 125 100 75 50 25 0 175 Tra Sho Res Ent Edu Res Wor Ser Spo Mee Med Art 活动种类 183 957 29 788 27 313 19 946 8 501 6 4925 624 4 9534 237 2 197 2 036 1 927 签到次数/10 3 图 2 签到数据种类分布 Fig. 2 Distribution of check-ins categories 图 3 签到数据样式 Fig. 3 Examples of check-ins data 4.2 实验结果 4.2.1 周期模式的识别 识别周期模式中，识别的周期通常指最小正周 期，因此需要传入周期的取值范围限制识别出周期 的大小。去除 10 个月少于 5 次签到的数据周期为 (0, 1440) 小时 (1 个月按 30 d 计算)，某个用户的某 个活动周期—频率图如图 4 所示，通过图 5 中周 期—频率图得到最大峰值对应的周期为 24.15 h。 这表明用户在这个地方的活动每隔 24.15 h 会发 生一次。 4.2.2 活动语义识别结果 为了验证周期特征对活动语义识别的有效 性，本文在相同的实验条件下，对比了加入和不 加入周期模式特征进行活动语义的识别的性能。 分别使用准确度、精准率、召回率、F1 值对分类结 果进行的评价，其计算为 precison = TP (TP+FP) (7) accuracy = (TP+TN) (TP+FP+TN+FN) (8) recall = TP (TP+FN) (9) ·166· 智 能 系 统 学 报 第 16 卷

第1期 郭茂祖，等：基于时空周期模式挖掘的活动语义识别方法 ·167· F1= precison x recall (10) 以看出，Edu和Sho、Spo和Sho、Res和Ser(Ser- 2(precison recall) vice)混淆得最为严重，其原因在于人类在学习 式中：TP、FP、TN、FN表示将正类分正确、将正 运动的活动中，进行活动的时间和场所受个人偏 类分错误、将负类分正确、负类分错误的个数。 好影响比较大，这些活动的持续时间较长，在特 0.7 征方面容易与购物、饮食和社会服务（银行，派出 0.6 所，居委会，政府等社会公共设施内进行的活动) 0.5 等行为混淆。由于人类的这些行为周期性比较明 0.4 显，加上周期模式特征后，这些行为会被更加准 云0.3 确地识别出来。 02 Sho 0.1 Res 0.8 0 Wor 020406080100120140160180 Tra 00.00a0 周期/h Ent 0.6 图4某个特定活动对应的LombScargle功率一频率 Ser Mee Fig.4 LombScargle power-frequency diagram corres- 04 Edu ponding to a specific activity Spo 口无周期 ☐有周期 Res 02 Med 1.0 0.968 0.973 0.951 0.962 Art卓0,1g单6物.鱼cet 0.871 0.874 0.826 0.848 0.8 异翌皇吕温月是温务是是月 预测类别 0.6 图6不加入周期特征的混淆矩阵 0.4 Fig.6 The confusion matrix without period 02 Sho Res 00.: 0 Wor 0.8 准确率 精确率召回率 F Tra Ent 图5有无周期的分类结果 0.6 Ser Fig.5 The histogram without or with period Mee 在周期模式特征中加入错误预警概率作为联 Edu 1.0.010.00.0190 0.4 00 0.0 合周期特征，随机森林最后参数设置为n-estimat- Spo Res 0.2 or=84,在TKY数据集上得到的实验结果如图5 Med 所示。加人周期特征后准确率从0.871提升到 Art..0150.000 0.968,精准率从0.874提升到0.973，召回率从 务盟喜吕盖月兰温务益是 0.826提升到0.951，F1值从0.848提升到0.962。 预测类别 由数值结果可以看出加人周期特征后在各个分类 图7加入周期特征的混淆矩阵 结果中都取得了10%以上的提升。 Fig.7 The confusion matrix with period 分别绘制每个分类的结果，得到加入周期特 为了验证本文方法有更好的识别精度，本文 征前后的混淆矩阵如图6、图7，矩阵横轴表示预 和文献[24-25]在相同的数据集下（东京市签到数 测的类别，纵轴表示真实的类别。方格对角线的 据集、纽约市数据集)进行实验。本文和文献2425] 值表示识别正确的类别占总类别的比值，其中空 都采签到地点名称作为用户的活动语义标签， 白表示值为0，即在预测样本中完成分类正确。 TKY数据集包含的标签个数为247个，NYC包含 从图6中可以看出，没有加入周期前模型对 的标签个数为251个。实验结果如表1，LIA0等阿 Edu(Education)、Spo(Sport)、Res(Restaurant))这几 采用2个基学习器和一个元学习器将时间特征和 种活动的识别精度较低(0.726,0.689,0.707)，加 序列特征整合用于预测用户的活动目的和活动位 入周期模式特征后这些活动的识别效果得到了 置，YANG等2提出一种上下文感知框架对用户 20%左右的提升，识别精度均超过0.9。从图6可 活动偏好进行推理，从而识别用户的活动语义

F1 = precison×recall 2(precison+recall) (10) 式中：TP、 FP、 TN、FN 表示将正类分正确、将正 类分错误、将负类分正确、负类分错误的个数。 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0 0 20 40 60 80 100 120 140 160 180 周期/h 功率 图 4 某个特定活动对应的 LombScargle 功率—频率 Fig. 4 LombScargle power-frequency diagram corres￾ponding to a specific activity 1.0 0.8 0.6 0.4 0.2 0 准确率 精确率 召回率 F1 0.871 0.968 0.874 0.973 0.826 0.951 0.848 0.962 无周期 有周期 图 5 有无周期的分类结果 Fig. 5 The histogram without or with period 在周期模式特征中加入错误预警概率作为联 合周期特征，随机森林最后参数设置为 n-estimat￾or=84，在 TKY 数据集上得到的实验结果如图 5 所示。加入周期特征后准确率从 0.871 提升到 0.968，精准率从 0.874 提升到 0.973，召回率从 0.826 提升到 0.951，F1 值从 0.848 提升到 0.962。 由数值结果可以看出加入周期特征后在各个分类 结果中都取得了 10% 以上的提升。 分别绘制每个分类的结果，得到加入周期特 征前后的混淆矩阵如图 6、图 7，矩阵横轴表示预 测的类别，纵轴表示真实的类别。方格对角线的 值表示识别正确的类别占总类别的比值，其中空 白表示值为 0，即在预测样本中完成分类正确。 从 图 6 中可以看出，没有加入周期前模型 对 Edu(Education)、 Spo(Sport)、 Res(Restaurant) 这几 种活动的识别精度较低 (0.726，0.689，0.707），加 入周期模式特征后这些活动的识别效果得到了 20% 左右的提升，识别精度均超过 0.9。从图 6 可 以看出，Edu 和 Sho、 Spo 和 Sho、 Res 和 Ser(Ser￾vice) 混淆得最为严重，其原因在于人类在学习、 运动的活动中，进行活动的时间和场所受个人偏 好影响比较大，这些活动的持续时间较长，在特 征方面容易与购物、饮食和社会服务（银行，派出 所，居委会，政府等社会公共设施内进行的活动） 等行为混淆。由于人类的这些行为周期性比较明 显，加上周期模式特征后，这些行为会被更加准 确地识别出来。 Tra Res Res Sho Ent Edu Ser Wor Mee Spo Art Med Sho Res Wor Tra Ent Ser Mee Edu Spo Res Art Med 0.8 0.6 0.4 0.2 0 真实类别 预测类别 图 6 不加入周期特征的混淆矩阵 Fig. 6 The confusion matrix without period Tra Res Res Sho Ent Edu Ser Wor Mee Spo Art Med Sho Res Wor Tra Ent Ser Mee Edu Spo Res Art Med 0.8 0.6 0.4 0.2 0 真实类别 预测类别 图 7 加入周期特征的混淆矩阵 Fig. 7 The confusion matrix with period 为了验证本文方法有更好的识别精度，本文 和文献 [24-25] 在相同的数据集下 (东京市签到数 据集、纽约市数据集) 进行实验。本文和文献 [24-25] 都采签到地点名称作为用户的活动语义标签， TKY 数据集包含的标签个数为 247 个，NYC 包含 的标签个数为 251 个。实验结果如表 1，LIAO 等 [25] 采用 2 个基学习器和一个元学习器将时间特征和 序列特征整合用于预测用户的活动目的和活动位 置，YANG 等 [24] 提出一种上下文感知框架对用户 活动偏好进行推理，从而识别用户的活动语义。 第 1 期 郭茂祖，等：基于时空周期模式挖掘的活动语义识别方法 ·167·

·168· 智能系统学报 第16卷 实验结果如表1所示，在NYC数据集上本文的识 [4]姚迪，张超，黄建辉，等.时空数据语义理解：技术与应用 别方法相对于LIA0提升精度35.9%，相对于 [).软件学报，2018,29(7)：2018-2045. YANG提升了10.8%。在TKY数据集上分别提升 YAO Di.ZHANG Chao.HUANG Jianhui,et al.Semantic 了37.8%和23.7%。实验结果表明周期模式挖掘 understanding of spatio-temporal data:technology and ap- 算法具有更好的识别精度，也验证了用户在长时 plication[J].Journal of software,2018,29(7):2018-2045. 间活动轨迹中周期性的重要作用。 [5]LU Mingqi,CHEN Ling,XU Zhenxing,et al.The discov- 表1识别算法对比结果 ery of personally semantic places based on trajectory data Table 1 The comparison results of recognition algorithms mining[J].Neurocomputing,2016,173:1142-1153 数据集 算法 精度 [6]WAN Chengcheng,ZHU Yanmin,YU Jiadi,et al.SMO- LIAO 0.284 PAT:mining semantic mobility patterns from trajectories of private vehicles[J].Information sciences,2018,429: NYC YANG 0.535 12-25 本文 0.643 [7]ZHANG Dongzhi,LEE K.LEE I.Mining hierarchical se- LIAO 0.401 mantic periodic patterns from GPS-collected spatio-tem- TKY YANG 0.542 poral trajectories[J].Expert systems with applications, 本文 0.779 2019.122:85-101 [8]ZHANG Dongzhi,LEE K,LEE I.Hierarchical trajectory 5结束语 clustering for spatio-temporal periodic pattern mining[J]. Expert systems with applications,2018,92:1-11. 本文通过对比是否加入周期特征的方法，验 [9]SONG Chaoming,KOREN T,WANG Pu,et al.Model- 证了加入周期模式能有效提高活动语义的识别性 ling the scaling properties of human mobility[J].Nature 能；同时，在与LIAO、YANG方法的对比中可以发 physics,.2010,6(10y:818-823. 现本文的方法具有更好的识别精度，验证了本文 [10]SONG Chaoming,QU Zehui,BLUMM N,et al.Limits of 方法的有效性。本文充分利用了人的部分活动带 predictability in human mobility[J].Science,2010, 有显著的周期性这一特点，挖掘了历史活动的周 327(5968):1018-1021. 期模式，来提高对当前活动的识别的准确性。因 [11]苏杭.基于电信位置数据的用户活动推测及行为模式 此本文方法更适合个体活动记录的时间跨度较大 分析D1.北京：北京邮电大学，2018：1-84 的数据场景，以便更好地捕捉活动的周期特征。 SU Hang.User activity inference and behavior pattern 本文的活动语义识别方法是基于周期模式特征为 analysis based on mobile phone data[D].Beijing:Beijing 主要特征，因此对于人的部分不频繁的活动模式 University of Posts and Telecommunications,2018:1-84. 识别效果不佳，这也是未来要研究的方向之一。 [12]崔家祥.基于移动通信数据的用户移动行为分析与位 参考文献： 置预测D1.北京：北京邮电大学，2018：1-73 CUI Jiaxiang.User mobility analysis and location predic- [1]ZHENG Yu.Trajectory data mining:an overview[J].ACM tion based on mobile communication data[D].Beijing: transactions on intelligent systems and technology,2015, Beijing University of Posts and Telecommunications. 6(3:1-41 2018:1-73 [2]SILA-NOWICKA K,VANDROL J,OSHAN T,et al. [13]周超然.基于大规模GPS轨迹数据的活动链信息分析 Analysis of human mobility patterns from GPS trajectories 方法研究D1长春：吉林大学，2017：80-88. and contextual information[J].International journal of geo- ZHOU Chaoran.Research on methods of activity-chain graphical information science,2016,30(5):881-906. information analysis based on large scale GPS tracking [3]郭黎敏，高需，武斌，等.基于停留时间的语义行为模式 data[D].Changchun:Jilin University,2017:80-88. 挖掘).计算机研究与发展，2017,541)：111-122. [14]殷浩腾，刘洋.基于社交属性的时空轨迹语义分析)， GUO Limin,GAO Xu,WU Bin,et al.Discovering com- 中国科学：信息科学，2017,47(8)：1051-1065 mon behavior using staying duration on semantic traject- YIN Haoteng,LIU Yang.Semantic analysis of spatial ory[J].Journal of computer research and development, temporal trajectory in LBSNs[J].Scientia sinica informa- 2017,541):111-122. tionis,2017,47(8):1051-1065

实验结果如表 1 所示，在 NYC 数据集上本文的识 别方法相对于 LIAO 提升精度 35.9%，相对于 YANG 提升了 10.8%。在 TKY 数据集上分别提升 了 37.8% 和 23.7%。实验结果表明周期模式挖掘 算法具有更好的识别精度，也验证了用户在长时 间活动轨迹中周期性的重要作用。 表 1 识别算法对比结果 Table 1 The comparison results of recognition algorithms 数据集 算法 精度 NYC LIAO 0.284 YANG 0.535 本文 0.643 TKY LIAO 0.401 YANG 0.542 本文 0.779 5 结束语 本文通过对比是否加入周期特征的方法，验 证了加入周期模式能有效提高活动语义的识别性 能；同时，在与 LIAO、YANG 方法的对比中可以发 现本文的方法具有更好的识别精度，验证了本文 方法的有效性。本文充分利用了人的部分活动带 有显著的周期性这一特点，挖掘了历史活动的周 期模式，来提高对当前活动的识别的准确性。因 此本文方法更适合个体活动记录的时间跨度较大 的数据场景，以便更好地捕捉活动的周期特征。 本文的活动语义识别方法是基于周期模式特征为 主要特征，因此对于人的部分不频繁的活动模式 识别效果不佳，这也是未来要研究的方向之一。 参考文献： ZHENG Yu. Trajectory data mining: an overview[J]. ACM transactions on intelligent systems and technology, 2015, 6(3): 1–41. [1] SIŁA-NOWICKA K, VANDROL J, OSHAN T, et al. Analysis of human mobility patterns from GPS trajectories and contextual information[J]. International journal of geo￾graphical information science, 2016, 30(5): 881–906. [2] 郭黎敏, 高需, 武斌, 等. 基于停留时间的语义行为模式 挖掘 [J]. 计算机研究与发展, 2017, 54(1): 111–122. GUO Limin, GAO Xu, WU Bin, et al. Discovering com￾mon behavior using staying duration on semantic traject￾ory[J]. Journal of computer research and development, 2017, 54(1): 111–122. [3] 姚迪, 张超, 黄建辉, 等. 时空数据语义理解: 技术与应用 [J]. 软件学报, 2018, 29(7): 2018–2045. YAO Di, ZHANG Chao, HUANG Jianhui, et al. Semantic understanding of spatio-temporal data: technology and ap￾plication[J]. Journal of software, 2018, 29(7): 2018–2045. [4] LU Mingqi, CHEN Ling, XU Zhenxing, et al. The discov￾ery of personally semantic places based on trajectory data mining[J]. Neurocomputing, 2016, 173: 1142–1153. [5] WAN Chengcheng, ZHU Yanmin, YU Jiadi, et al. SMO￾PAT: mining semantic mobility patterns from trajectories of private vehicles[J]. Information sciences, 2018, 429: 12–25. [6] ZHANG Dongzhi, LEE K, LEE I. Mining hierarchical se￾mantic periodic patterns from GPS-collected spatio-tem￾poral trajectories[J]. Expert systems with applications, 2019, 122: 85–101. [7] ZHANG Dongzhi, LEE K, LEE I. Hierarchical trajectory clustering for spatio-temporal periodic pattern mining[J]. Expert systems with applications, 2018, 92: 1–11. [8] SONG Chaoming, KOREN T, WANG Pu, et al. Model￾ling the scaling properties of human mobility[J]. Nature physics, 2010, 6(10): 818–823. [9] SONG Chaoming, QU Zehui, BLUMM N, et al. Limits of predictability in human mobility[J]. Science, 2010, 327(5968): 1018–1021. [10] 苏杭. 基于电信位置数据的用户活动推测及行为模式 分析 [D]. 北京: 北京邮电大学, 2018: 1–84. SU Hang. User activity inference and behavior pattern analysis based on mobile phone data[D]. Beijing: Beijing University of Posts and Telecommunications, 2018: 1–84. [11] 崔家祥. 基于移动通信数据的用户移动行为分析与位 置预测 [D]. 北京: 北京邮电大学, 2018: 1–73. CUI Jiaxiang. User mobility analysis and location predic￾tion based on mobile communication data[D]. Beijing: Beijing University of Posts and Telecommunications, 2018: 1–73. [12] 周超然. 基于大规模 GPS 轨迹数据的活动链信息分析 方法研究 [D]. 长春: 吉林大学, 2017: 80–88. ZHOU Chaoran. Research on methods of activity-chain information analysis based on large scale GPS tracking data[D]. Changchun: Jilin University, 2017: 80–88. [13] 殷浩腾, 刘洋. 基于社交属性的时空轨迹语义分析 [J]. 中国科学: 信息科学, 2017, 47(8): 1051–1065. YIN Haoteng, LIU Yang. Semantic analysis of spatial temporal trajectory in LBSNs[J]. Scientia sinica informa￾tionis, 2017, 47(8): 1051–1065. [14] ·168· 智 能 系 统 学 报 第 16 卷

第1期 郭茂祖，等：基于时空周期模式挖掘的活动语义识别方法 ·169· [15]郭茂祖，张彬，赵玲玲，等.基于联合特征和XGBoost的 [23]VANDERPLAS JT.Understanding the Lomb-Scargle 活动语义识别方法[].计算机应用，2020,40(11)： periodogram[J].The astrophysical journal supplement 3159-3165 series,2018,236(1):1-15. GUO Maozu,ZHANG Bin,ZHAO Lingling,et al.Act- [24]YANG Dingqi,ZHANG Daqing,ZHENG V W,et al. ive semantic recognition method based on joint features Modeling user activity preference by leveraging user spa- and XGBoost[J].Journal of computer applications,2020, tial temporal characteristics in LBSNs[J].IEEE transac- 40(11):3159-3165 tions on systems,man,and cybernetics:systems,2015. [16]LI Zhenhui,DING Bolin,HAN Jiawei,et al.Mining peri- 45(1)129-142. odic behaviors for moving objects[C]//Proceedings of the [25]LIAO Dongliang,ZHONG Yuan,LI Jing.Location pre- 16th ACM SIGKDD International Conference on Know- diction through activity purpose:integrating temporal and ledge Discovery and Data Mining.Washington, sequential models[C]//Proceedings of the 21st Pacific- USA,2010:1099-1108 Asia Conference on Knowledge Discovery and Data Min- [17]ZHANG Dongzhi,LEE K,LEE I.Semantic periodic pat- ing.Jeju,South Korea,2017:711-723 tern mining from spatio-temporal trajectories[J].Informa- tion sciences,2019,502:164-189. 作者简介： [18]LOMB N R.Least-squares frequency analysis of un- 郭茂祖，教授，博士生导师，主要 研究方向为机器学习、智慧城市、生物 equally spaced data[J].Astrophysics and space science, 信息学。主持和参与国家自然科学基 1976,39(2:447-462.. 金面上项目、北京市属高校高水平创 [19]SCARGLE J D.Studies in astronomical time series ana- 新团队建设计划项目和北京市教委科 lysis.II-Statistical aspects of spectral analysis of un- 技计划重点项目等，获得教育部高等 evenly spaced data[J].Astrophysical journal,1982,263: 学校科学研究优秀成果自然科学二等 奖、省科技进步二等奖、吴文俊人工智 835-853 能自然科学奖二等奖等。发表学术论 [20]BOUKHECHBA M.BOUZOUANE A,BOUCHARD B, 文200余篇。 et al.Online recognition of people's activities from raw GPS data:semantic trajectory data analysis[Cl//Proceed- 邵首飞，硕士研究生，主要研究方 向为智能信息处理理论与方法、机器 ings of the 8th ACM International Conference on Pervas- 学习、智慧城市。 ive Technologies Related to Assistive Environments. Corfu,Greece,2015:1-8. [21]GLYNN E F,CHEN Jie,MUSHEGIAN A R.Detecting periodic patterns in unevenly spaced gene expression time series using Lomb-Scargle periodograms[J].Bioinformat- 赵玲玲，副教授，博士，主要研究 ics2006,22(3):310-316. 方向为城市计算、生物信息学。主持 [22]BERMINGHAM L,LEE I.Mining place-matching pat- 和参与多项国家自然科学基金项目。 发表学术论文40余篇。 terns from spatio-temporal trajectories using complex real-world places[J].Expert systems with applications, 2019.122:334-350

郭茂祖, 张彬, 赵玲玲, 等. 基于联合特征和 XGBoost 的 活动语义识别方法 [J]. 计算机应用, 2020, 40(11): 3159–3165. GUO Maozu, ZHANG Bin, ZHAO Lingling, et al. Act￾ive semantic recognition method based on joint features and XGBoost[J]. Journal of computer applications, 2020, 40(11): 3159–3165. [15] LI Zhenhui, DING Bolin, HAN Jiawei, et al. Mining peri￾odic behaviors for moving objects[C]//Proceedings of the 16th ACM SIGKDD International Conference on Know￾ledge Discovery and Data Mining. Washington, USA, 2010: 1099–1108. [16] ZHANG Dongzhi, LEE K, LEE I. Semantic periodic pat￾tern mining from spatio-temporal trajectories[J]. Informa￾tion sciences, 2019, 502: 164–189. [17] LOMB N R. Least-squares frequency analysis of un￾equally spaced data[J]. Astrophysics and space science, 1976, 39(2): 447–462. . [18] SCARGLE J D. Studies in astronomical time series ana￾lysis. II-Statistical aspects of spectral analysis of un￾evenly spaced data[J]. Astrophysical journal, 1982, 263: 835–853. [19] BOUKHECHBA M, BOUZOUANE A, BOUCHARD B, et al. Online recognition of people's activities from raw GPS data: semantic trajectory data analysis[C]//Proceed￾ings of the 8th ACM International Conference on Pervas￾ive Technologies Related to Assistive Environments. Corfu, Greece, 2015: 1–8. [20] GLYNN E F, CHEN Jie, MUSHEGIAN A R. Detecting periodic patterns in unevenly spaced gene expression time series using Lomb–Scargle periodograms[J]. Bioinformat￾ics, 2006, 22(3): 310–316. [21] BERMINGHAM L, LEE I. Mining place-matching pat￾terns from spatio-temporal trajectories using complex real-world places[J]. Expert systems with applications, 2019, 122: 334–350. [22] VANDERPLAS J T. Understanding the Lomb–Scargle periodogram[J]. The astrophysical journal supplement series, 2018, 236(1): 1–15. [23] YANG Dingqi, ZHANG Daqing, ZHENG V W, et al. Modeling user activity preference by leveraging user spa￾tial temporal characteristics in LBSNs[J]. IEEE transac￾tions on systems, man, and cybernetics: systems, 2015, 45(1): 129–142. [24] LIAO Dongliang, ZHONG Yuan, LI Jing. Location pre￾diction through activity purpose: integrating temporal and sequential models[C]//Proceedings of the 21st Pacific￾Asia Conference on Knowledge Discovery and Data Min￾ing. Jeju, South Korea, 2017: 711–723. [25] 作者简介： 郭茂祖，教授，博士生导师，主要 研究方向为机器学习、智慧城市、生物 信息学。主持和参与国家自然科学基 金面上项目、北京市属高校高水平创 新团队建设计划项目和北京市教委科 技计划重点项目等，获得教育部高等 学校科学研究优秀成果自然科学二等 奖、省科技进步二等奖、吴文俊人工智 能自然科学奖二等奖等。发表学术论 文 200 余篇。 邵首飞，硕士研究生，主要研究方 向为智能信息处理理论与方法、机器 学习、智慧城市。 赵玲玲，副教授，博士，主要研究 方向为城市计算、生物信息学。主持 和参与多项国家自然科学基金项目。 发表学术论文 40 余篇。 第 1 期 郭茂祖，等：基于时空周期模式挖掘的活动语义识别方法 ·169·