2. 浙江大学 CAD & CG国家重点实验室, 杭州 310027;
3. 浙江省大数据智能计算重点实验室, 杭州 310027;
4. 浙江中医药大学附属第三医院, 杭州 310009
2. CAD & CG State Key Lab, Zhejiang University, Hangzhou 310027, China;
3. Key Laboratory of Big Data Intelligent Computing of Zhejiang Province, Hangzhou 310027, China;
4. Third Hospital Affiliated to Zhejiang Chinese Medical University, Hangzhou 310009, China
随着移动智能设备的普及以及定位技术的快速发展，获取个人的位置信息变得愈加便捷。地理位置数据已渗透到各行各业中，连接着物理空间和信息空间中的人和事。其中室外定位技术发展较早，针对人们室外活动规律的研究也较为成熟。而室内环境中目前主要采用WiFi定位技术，由于墙体干扰、环境复杂等原因，目前还没有统一完善的解决方案来挖掘室内空间行为，技术上仍有较大的提升空间。然而数据表明人们在室内环境中度过了80%~90%的个人生活时间，各种研究机构看中室内定位数据的巨大价值，投入了大量的研究，并产生了一批基于室内位置的服务，例如位置签到、线下消费、广告推送等。应用的发展随即催生了海量的室内定位数据，急需高效的处理合理的轨迹数据分析模型和高效的处理算法来应对存在误差和缺失的室内定位数据。本文针对室内环境的特点研究轨迹数据分析框架，能够自动化构建室内空间模型，处理包含有一定错误的定位数据，提取出轨迹中发生的关键事件，并输出含有语义信息的轨迹数据，便于开展上层的应用的分析：例如有公司将顾客在购物中心的移动轨迹和消费行为相结合，想要发掘出顾客感兴趣的商店和业态，探索顾客在线下购物中的活动规律，从而对购物、餐饮、休闲服务的布局做出调整。
本文提出一套分析处理室内定位数据的技术框架，分为室内空间模型构建、数据清洗、事件提取、语义增强四个模块，并充分考虑室内空间约束的影响。在DBSCAN(density-based spatial clustering of applications with noise)算法基础上，利用轨迹的时空特性，提出改进的密度聚类事件提取算法，提取轨迹中重要事件，并引入区间调度算法消解事件冲突问题。开发了一套室内定位数据分析工具集，以可视化方式调整数据清洗和事件提取方法，并展示语义轨迹的时空特性。
1 相关技术移动物体在地理空间中活动而被探测到的位置日志信息称为原始轨迹，包含时间轴上被探测用户的一连串物理位置数值。在获取到原始轨迹后，除了可以转换为特征向量用于一些群体行为分析外[1]，更多的应用是将原始轨迹和外部语义信息相结合来分析用户的移动行为[2]。相比于高频、冗余的原始轨迹数据，语义轨迹的表示不仅能大大减少数据量，同时具备更好描述用户访问空间属性的能力，便于人类理解和上层应用分析。
在提取语义轨迹中主要涉及到数据清洗、空间模型、事件提取和语义增强技术。传感器产生的原始轨迹数据包含大量噪声和缺失，需要进行充分地清洗以排除错误、平滑波动。已有一些经典的方法可用于清洗传感器数据:基于移动速度的过滤方法[3]、均值/中值滤波[4]、平滑技术[4-5]等。空间模型可用于辅助清洗室内定位数据，提供索引以加快空间数据的处理速度。室内环境受其组成元素、定位精度和约束条件的影响，在不同应用场景有着不同的使用方法，包括语义模型、拓扑模型、几何模型和混合模型4类[6-7]。为了从高频、冗余、抽象的原始轨迹中提取出经过摘要的事件轨迹，目前已有大量的文献研究了在室内外提取轨迹关键事件点的方法，主要分为：1)基于中心的方法。利用K-means等无监督学习方法，计算简单，无须训练，但轨迹中停留点的个数难以提前确定，无法应对存在数据分布不一的轨迹。2)基于停留时长的方法。在检测事件时，很多算法对时长的阈值参数较为敏感[4, 8-9]，并针对应用场景做细致的调整。3)基于速度的方法。这是在室外空间常用的方法[10]，但用户在室内空间的移动速度变化小，且移动方向不像路网那样有严格限制。4)基于密度的方法。算法假设聚簇可通过样本分布的紧密度来确定聚簇，常见方法有DBSCAN[11]及其变种[12-13]。5)混合法。将以上涉及的若干变量结合能够形成混合指标，如文[13]根据轨迹的位移和曲线距离定义了移动能力的概念，文[14]使用速度和最小停留时长相结合来判定用户的停留、移动状态。
2 问题描述和系统框架本文研究的问题以原始轨迹作为输入，利用室内空间模型，对数据进行清洗、事件提取和语义增强，转换得到人能够理解、上层应用方便分析处理的语义轨迹。其中原始轨迹的定义如下：
定义1 原始轨迹：利用传感数据计算得到的用户位置信息日志，符合以下形式：traji={oid, [〈loc1, t1〉, 〈loc2, t2〉, …, 〈locn, tn〉]}，其中oid是用户的ID，loci是用户在时间ti的位置信息，且∀i∈[1, n]，ti＜ti+1, loci包含三维信息(x, y, floor)，即在某一楼层内的二维坐标。
原始轨迹能表达一段时间内的用户的物理位置变化，但表达能力有限，数据冗余同构，直接从它进行分析挖掘非常困难。需将轨迹时序同地图语义信息相结合，转换为人易于理解，机器易于处理的语义轨迹形式。
定义2 语义轨迹：包含以下连续事件信息的时空轨迹被称作语义轨迹：STi={oid, [〈f1, r1, ts1, te1, type1〉, …，〈fn, rn, tsn, ten, typen〉]}, 其中typei∈{停留, 移动, 进入, 离开}表示发生事件的类型，fi和ri是事件发生的楼层和语义区域ID，tsi、tei是事件的起始和结束时间。
图 1是一条典型的语义轨迹，表示该用户在2017年2月19日10点左右来到某大厦，从入口大厅进入，并在爱马仕中停留了16 min，先后经过了走廊21和东北侧扶梯，并在古驰停留17 min左右，最后在10点40分左右从2楼天桥离开。语义轨迹使用若干经过、停留事件描绘了用户在40 min内的主要行为，相比于原始轨迹中600多条传感记录更能准确表述人在室内空间中的活动。
|
| 图 1 语义轨迹样例 |
为得到如定义2所示的语义轨迹，不能仅局限于传感数据，还应将外部异构数据融入进来。利用楼层平面图来构建室内空间模型，描述物体在室内空间移动时受到的约束；利用各空间区域的名称、类型、开放时间等语义信息，与事件轨迹相结合，增强轨迹的语义表述能力。整个框架主要包含4个技术流程：1)以楼层平面图为输入，描述室内空间中的房间、围墙、楼梯等基础元素组成的拓扑关系，并为空间查询提供索引；2)以原始轨迹作为输入，室内空间模型为约束，对数据中存在的错误进行纠正、过滤；3)将清洗后的位置数据和室内空间模型结合，将带有时间戳的点数据转换为不同时间段的事件轨迹；4)利用事件轨迹和语义信息，来描述用户的行为。
3 语义轨迹提取流程语义轨迹的提取主要分为构建室内空间模型、数据清洗、事件提取和语义增强4个步骤。以下分别进行介绍说明。
3.1 构建室内空间模型室内空间模型的构建是用于定义空间约束和提供高效空间索引，在文[7]和文[15]中已经有详细描述，其中拓扑关系相对于室外空间的几何、方向、角度信息更为基础重要。本文基于Autodesk开发的CAD图和建筑信息化模型(building information modeling，BIM)广泛使用的IFC图提供的几何信息[16]来自动化构建基本的空间模型，描述各空间元素之间的可达性和约束性，并在此基础上建立合理的度量模型。本文沿用文[17]中提出的最小室内移动距离(minimal indoor walking distance，MIWD)作为度量指标，即在计算空间中两点p1和p2的距离时，物体遵循空间移动约束(不能横跨房间或穿墙而过)所需花费的最短路径长度。为加快MIWD计算速度，还可利用大楼的楼层结构作为天然的图划分，将楼层内的真实门和虚拟门作为内部节点，将连接各楼层的楼梯作为边界节点，构建楼层间和楼层内的门连接图(door to door graph，D2DGraph)，组成拓扑索引。使用楼层的空间信息构建几何索引R-Tree，并将其与拓扑索引相结合形成混合索引。对于室内的障碍物，同样可以根据它们进行室内空间的多区域划分，然后在单位移动时需要遵循区域之间的连接约束。
3.2 数据清洗数据清洗主要是纠正定位数据中的一些错误，以及过滤不合理的定位点。基于室内定位系统工作原理，这里主要包括校正错误的楼层定位数据，并去除由于定位信号波动而产生较大偏差的定位点。这些点在实际WiFi定位系统中普遍存在，占有一定的比例，如不对它们进行处理，这些离群点和孤立点会影响后续事件提取的结果。
当室内定位系统的信号不稳定性时，有可能出现楼层定位跳跃的情况，而人在楼层内活动时倾向于在某个楼层内停留一定时长，且在楼层间移动通常依照一定的方向。因此这里使用中值滤波来应对偶然发生的楼层定位错误的情况，即使用一个滑动窗口来估算当前点的真值，这个滑动窗口恰好覆盖了当前点前后的n个定位点。该方法对于少量出现的短暂错误有良好的修正效果，并且对突现的离群点不敏感，在本文中用于修正楼层定位数据。
修正错误的楼层数据后，系统中仍存在一些不合理的定位点。首先可以通过空间索引的区域检测快速判断点是否在合法区域内，排除一些明显错误的点如定位在地图以外的点；其次要过滤一些因为信号波动引起的漂移点，这里利用混合索引中的D2DGraph矩阵和MIWD。在清洗时，前后2次扫描每一个定位点，通过相邻定位点之间可能的房间路径、定位点到路径上同一房间的门的距离，以及D2DGraph中预计算的各房间门之间的距离，可以高效地计算它们的MIWD以及该点的移动速度，当速度超过约定阈值时，标记该点为候选过滤点，最后将被标记两次的点过滤除去即可。如图 3所示，有定位点p1, p2, …, p7，各点按照时间先后顺序排列。其中p6点由于信号波动，被定位到了房间2中，如果以Euclid距离作为指标来计算空间中各点的距离，则容易认为p6与p5和p7仍然是空间上接近的点。事实上，它们在空间上相距较远，p6已经处于不同的区域，因此可利用最小室内移动距离来计算p5、p6和p6、p7的移动速度，其中
| $ \begin{array}{*{20}{c}} {{d_{{\rm{MIW}}}}({p_5}, \;{p_6}) = {d_{\rm{O}}}({p_5}, \;{d_2}) + }\\ {{d_{\rm{O}}}({d_2}, \;{d_1}) + {d_{\rm{O}}}({d_1}, \;{p_6}), } \end{array} $ |
| $ \begin{array}{*{20}{c}} {{d_{{\rm{MIW}}}}({p_6}, \;{p_7}) = {d_{\rm{O}}}({p_6}, \;{d_1}) + }\\ {{d_{\rm{O}}}({d_1}, \;{d_2}) + {d_{\rm{O}}}({d_2}, \;{p_7}), } \end{array} $ |
| $ \begin{array}{l} v\left( {{p_5},\;{p_6}} \right) = \frac{{{d_{{\rm{MIW}}}}({p_5},\;{p_6})}}{{t({p_5},\;{p_6})}},\\ v({p_6},\;{p_7}) = \frac{{{d_{{\rm{MIW}}}}({p_6},\;{p_7})}}{{t({p_6},\;{p_7})}}, \end{array} $ |
|
| 图 3 漂移定位数据的清洗示例 |
p6先后2次超过速度阈值，被判定为非法点过滤去除。这种方法整体计算复杂度只和定位点的个数呈线性关系，并且能够过滤掉大部分的不合理定位点。如果以Euclid距离为尺度，则有可能错误地将p5、p6、p7归于同一聚簇，使得事件提取产生较大的偏差。
3.3 事件提取根据用户在室内的活动情况，可以将主要的室内活动分为4类：停留、经过、进入和离开事件。
定义3 停留/经过事件：用户在某一区域被探测到一定时长的事件，满足三元组(loc, ts, te)，其中loc是停留区间点的核心，Δt=te-ts是持续时间，它因不同应用决定了事件的停留、经过类型，当Δt≥tstay时是停留事件，当tmove≤Δt=te-ts＜tstay时，表示经过事件，其中tmove是移动时间阈值，用来过滤轨迹中的噪声。
定义4 进入/离开事件：经过数据清洗后，第一个/最后一个合法的定位数据点，将这个点作为进入/离开大楼的事件。
定义5 事件轨迹：经过事件提取后，用户的原始轨迹转变为带有关键事件信息的事件轨迹，ETi={oid, [〈loc1, ts1, te1, type1〉, …, 〈locn, tsn, ten, typen〉]}，∀i∈[1, n]，满足tsi＜tei≤tsi+1，同时∀i∈[1, n]，typei∈{停留, 移动, 进入, 离开}。
基于停留和经过这2种活动模式的特点和定位系统原理可知，单位时间和空间范围内的定位点数量能准确描述这种行为，即“时空密度”特性。下文将详细描述基于时空密度的事件提取算法。
3.3.1 基于时空密度的事件提取算法本文提出的事件提取方法是以空间大小和持续时长为基础的混合方法，同时关注了轨迹中的空间和时间特征，算法以DBSCAN为基础进行了一些调整，下文参照了DBSCAN中的一些概念进行描述。
定义6 εΔt邻域：以参考点p为中心，与参考点的Euclid距离在ε内，时间差在Δt之内的定位数据点。
相对于DBSCAN中的约定，这里不仅要求定位点loc与参考点p在空间上临近，还要求时间差|tloc-tp|＜Δt，在时间上连续。
定义7 核心对象：在点p的εΔt移动邻域内，如果定位点的数目超过minPoints个，则称点p为核心对象。
此处的核心对象的定义与DBSCAN中的相类似，区别在于这里的核心对象是针对时空密度而言的，即在相同的空间和时间范围内，产生的定位数据的频度。当在越短的时间和越小的空间范围内，产生越多的定位记录，则成为核心对象的可能性越高，发生停留事件的趋势越明显。
定义8 直接密度可达：对于样本集合D，如果点p是核心对象，并且点q在p的εΔt移动邻域内，即点q对p的核心对象有贡献，则称点q可以从点p直接密度可达。
具体如图 4所示。算法使用一个ArrayList来保存结果，使用HashMap来存储访问过的节点的状态，以及一个HashMap来记录定位点对应的数组索引。在此基础上，算法随机选取一个没有被访问过的点作为种子，并且查找该点的εΔt邻域内的所有近邻。如果当前点的时空密度超过minPoints，则该点被判定为核心对象，可以形成一个临时的聚簇。此时，可以根据近邻的状态，继续扩张当前聚簇，最后将聚簇添加到结果中。而如果当前的时空密度没有达到阈值，则将该点临时标记为噪声点。为了判定一个种子点是否是核心对象，需要快速查找该点的εΔt移动邻域的对象。传统的DBSCAN算法可以使用R-Tree空间索引来查找空间范围内邻近的定位点，而由于这里处理的轨迹是带有时间先后顺序的定位数据，除了可以用带时间维度的R-Tree外，这里用维护更便捷的HashMap来查找当前种子点的index。然后分别向前和向后扫描轨迹序列，判定当前点是否在ε移动范围内，并添加到近邻列表中，当定位点不在Δt范围内时跳出循环，可以在较低的时间复杂度内完成计算。合理扩张聚簇也是本算法的一个核心问题，与DBSCAN方法类似，先将核心点的近邻初始化为种子队列。然后对每一个没有访问过的种子点，分别查找它们的近邻，并判定该种子的状态，当该点也是核心对象时，那么可以把新的近邻也添加到种子队列中，并更新种子节点的状态，最终返回聚簇结果。
|
| 图 4 基于时空密度的事件提取算法 |
3.3.2 参数选取
本文的算法引入了时间上的约束，需要3个参数ε、Δt和minPoints。其中：ε表示移动邻域的半径，定义了物体的空间移动范围；Δt表示与参考点的时间差，限制了物体的时间变化区间；minPoints表示成为核心对象的最少邻域定位点数，三者共同决定了轨迹的时空密度。minPoints已在文[18]中提供了经典的选择方法，即选为2×dimension-1，因此在本框架中选择5。ε和Δt都会对最终聚簇的数量和大小产生影响：当它们增大时，算法对时空密度的要求降低，趋向于产生少数而较大的聚簇。而较小的阈值可能会受噪声影响形成一系列较小的分段聚簇。由于室内定位系统及用户设备在噪声上的局限性，在调整参数时应避免这种情况。图 5展示了在真实和模拟数据下寻找合适的ε和Δt的方法。当Δt较小的时候，受大量小聚簇的影响，对事件个数的影响很大；大于30 s时，曲线变得平缓，意味着Δt的影响被明显削弱。因此选择该拐点30 s作为参数。而从ε的曲线来看，当ε设定为3 m时，曲线下降的速度相比其它曲线最快，这是因为3 m接近于WiFi室内定位的精度。当参数设置为15 m时，曲线已经接近于一条平滑的直线，即移动邻域达到一定大小时，时间对聚类结果的影响已经变得较为微弱。当ε设定为[3,6] m时，事件数目曲线有明显的拐点，所以ε应当设置在这个范围内。参数的选取也同具体的应用场景有关，除以上方法外，也可以使用本框架中的室内定位数据分析工具集以可视化的方法来验证各种参数下事件提取的结果。
|
| 图 5 邻域、时间阈值与提取事件个数的关系 |
3.3.3 事件冲突的消解
由于定位点存在一定的误差和波动，在事件提取后可能会出现部分聚簇在时间上重叠的情况，即提取出的事件存在冲突的问题。这一问题可以规约为带权的区间调度问题，即目前有n个事件，每个事件Ei都有开始时间si和结束时间fi，事件有一定的权重wi，目标是使各事件之间互相相容且最后保留的事件子集的权重之和Σw最大。其中事件的权重表示为事件的可信度，即定位记录数越多，表示其事件越可信，停留趋势越明显，则相应的权重越高。令OPT(j)表示事件序列{e1, e2, …, en}的子序列{e1, e2, …, ej}的最优解，最终目标是求解得到OPT(n)。令提取的事件按照结束时间排序，能够得到递增序列：f1≤f2≤…≤fn，当i＜j时，则称事件i在事件j之前结束。定义p(j)为使得事件i与事件j不相交的最大标记i＜j，即不发生冲突的最晚事件。因此可得到OPT(j)=max{wj+OPT(p(j)), OPT(j-1)}，如果存在事件冲突，则当前状态可以由较小的子问题的最优解递归求得，因而可以将其转化为带有记忆的动态规划算法，求得最优解。
3.4 语义增强经过事件提取后，带有时间戳的原始轨迹数据转变成了带有时间段的事件轨迹，拥有表达用户在各时间段内活动状态的能力。然而，在数据分析时，用户常需要分析群体之间的相似或者相异性，例如找到对某些商家感兴趣的顾客的特征，发现有异常行为的个体等，这需要将单源的定位数据和外部的语义数据相结合，增强轨迹的表达能力，该过程称为语义增强。本文引入了语义区域，其除了包含基本的空间几何信息之外，还拥有领域特定知识，例如商店名称、业态类型、营业时间、平均单价等。使用室内空间模型的R-Tree索引将事件轨迹的核心点映射到语义空间可将事件轨迹转化为语义轨迹。在语义增强中，还可通过一些语义层的语义信息和语义约束条件进一步优化语义轨迹，如将处于同一语义区域的事件进行合并，或者补全语义轨迹中遗漏的一些事件。例如在2个空间距离较远的停留事件之间可能存在着一些关键的经过事件，可以利用MIWD的约束，发掘途中经过的门信息，补全语义轨迹数据。
4 实验分析 4.1 实验数据实验主要基于2种数据集，其中真实数据集来自某著名购物中心中的一幢7层大楼，部署有一套基于WiFi的室内定位系统，每天为2 000名左右的顾客提供上网服务，并以5 s/条的周期探测大楼内的移动设备，一天产生约100万条有效原始轨迹，如表 1所示。算法验证的真值是4名用户3次的实地考察记录获得，得到12条带标记的移动轨迹。且在单次考察中，4名用户均采用了相同的移动步调，尽可能排除各类设备的工作差异。模拟数据通过开发的基于室内平面地图的数据生成器Vita[19]获取，包括移动对象和原始轨迹的生成。产生的模拟数据用作语义轨迹提取框架的输入，可以进一步验证算法在多样化数据下的有效性和通用性。
| ID | Mac地址 | x | y | 时间 | 地图 |
| 109 694 **** | 8a:15:**: **:04:af | 55.42 | 67.49 | 2017-06-22 13：12：00 | /BLD- B/F2 |
| 109 694 **** | 44:6e:**: **:33:8c | 23.23 | 39.66 | 2017-06-22 13：12：00 | /BLD- B/F3 |
| 109 694 **** | 8a:15:**: **:50:2f | 54.85 | 48.31 | 2017-06-22 13：12：00 | /BLD- B/F2 |
4.2 实验对比
实验将本文算法与另外3种典型的停留检测算法CB-SMoT(clustering-based stops and moves of trajectories)、DBSCAN和TimeBased进行比较，使用清洗后的真实和模拟数据集，从定性和定量两种角度来查看各算法的实验结果。从定性角度，本框架提供了室内定位数据分析可视化工具，将语义轨迹以可视化的方式呈现给用户进行算法的分析调试和结果测试，详见节4.3。定量方法使用序列编辑距离(edit distance on real sequence，EDR)指标[20]，相比准确率(precision)、召回率(recall)和F1值(F1 score)能体现轨迹匹配准确率的同时保留轨迹内先后顺序，更能反映出2条轨迹间的差异性。2条语义轨迹中的事件ri和sj匹配当且仅当：
| $ \begin{array}{*{20}{c}} {\left( {\left( {\left| {{r_{i, x}} - {s_{j, x}}} \right| \le {\varepsilon _x}\& \& \left| {{r_{i, y}} - {s_{j, y}}} \right| \le {\varepsilon _y}} \right)} \right.}\\ {\left. {\left\| {\left( {{P_{{r_i}}} = = {P_{{s_j}}}} \right)} \right.} \right)}\\ {\& \& \left| {\Delta {t_{{r_i}}} - \Delta {t_{{s_j}}}} \right| \le {\varepsilon _t}} \end{array} $ |
其中: εx、εy、εt分别表示x、y、t轴上的阈值，即要求空间位置接近，处于相同语义空间且有相似的持续时长。
表 2展示了基于一次实地调研中某用户原始轨迹数据的计算结果。其中真值为25个事件(7个停留事件，18个经过事件)。结果表示的是使用各种算法提取到的停留和经过事件的个数，如本文算法检测到了23个事件，包含6次停留和17次经过；EDR表示总共所需的编辑距离长度，即将提取的轨迹匹配到真值需要的操作数，并通过插入、删除和替换分别来表示，如本文算法需插入1次停留，2次经过，删除1次经过，替换1次经过事件为另一经过事件后能匹配真值。EDR值越小表示算法的效果越好。与真值对比可知本文算法无论在提取停留事件还是经过事件时，都有比TimeBased和DBSCAN更优的效果。这是因为本文将空间和时间特征进行了结合。同时所有算法均遗漏了部分经过事件，原因在于定位的精度和频率有限，不能捕捉用户移动的所有细节。而经典的移动停留检测算法CB-SMoT在室内环境中效果不显著，因为算法与物体的移动速度有关，在室内环境中无法发挥作用。
| 度量 | 本文算法 | DBSCAN | CB-SMoT | TimeBased |
| 参数 | ε=3 m | |||
| minPoints=5 | — | — | ||
| Δt=30 s | — | Δt=10 s | Δt=20 s | |
| 结果 | 23(6, 17) | 21(6, 15) | 22(5, 17) | 18(5, 13) |
| EDR | 5 | 7 | 8 | 9 |
| 插入 | 3(1, 2) | 5(1, 4) | 5(2, 3) | 8(2, 6) |
| 删除 | 1(0, 1) | 1(0, 1) | 1(0, 1) | 1(0, 1) |
| 替换 | 1(0, 1) | 1(0, 1) | 2(0, 2) | 0(0, 0) |
图 6给出了各算法在准确性指标上的效果对比。考虑到不同实验中轨迹长度的差异，这里对EDR指标做归一化处理，即
| $ {\rm{EDR = }}\frac{{{\rm{Edit}}\;{\rm{Distance}}}}{{{\rm{Max}}\left( {{\rm{len}}\left( {{\rm{tra}}{{\rm{j}}_1}} \right), {\rm{len}}\left( {{\rm{tra}}{{\rm{j}}_2}} \right)} \right)}} $ |
|
| 图 6 在真实和模拟数据集下各算法的准确性指标对比 |
左图给出了基于3次实地考察数据进行实验得到的每次EDR均值，可知在真实数据集下本文的算法有着优于另外3种算法的效果。而TimeBased方法因为室内定位点存在漂移和跳跃，得到的结果与真值存在较大出入。DBSCAN方法仅关注空间特征，当用户在一定范围内频繁移动时，容易被误判为停留事件。为验证算法的通用性和有效性，用数据生成器Vita[19]产生了不同模式下带有噪声的原始轨迹和对应的移动路线真值。右图 3组数据分别表示误差在1、2、3 m左右情况下3次计算得出的平均EDR，可以得到和真实数据类似的结论。
4.3 室内定位数据分析可视化工具本框架还开发了室内定位数据分析可视化工具，包含用于调整室内定位数据分析算法的可视化工具，能直观地表达语义轨迹提取算法的效果，提供了选择算法、调整参数的界面，并以Web服务的方式接入了应用后台，在提交任务后可以及时返回结果，以便开发人员调试分析算法。图 7展示了使用本框架提取的语义轨迹和真实移动路线的对比情况。左侧是算法选择模块，包括MAC地址管理、数据清洗、事件提取算法、楼层平面图的选择；中部是语义轨迹和楼层平面图的可视化展示模块，点表示原始轨迹中的定位点，线表示经过事件提取后的移动路线，根据左侧的算法参数调整呈现不同效果；右侧是语义轨迹的时间特性展示模块，可与左侧和中部页面联动展示。
|
| 图 7 (网络版彩图)室内定位数据分析可视化工具 |
5 结论
本文研究了在室内场景下语义轨迹的提取方法，在保留原始轨迹中的关键信息的同时，压缩了轨迹的存储空间，丰富了上层应用的分析维度。文中提出的算法能快速有效地计算得到语义轨迹，不过针对具体的场景和数据仍有改进空间：在数据清洗这个重要环节中，可针对不同情况做一些细粒度的处理或能更准确地修正、过滤错误数据；在事件提取中，算法的参数选取受到数据质量的影响，可进一步研究自适应调整参数的方法；在语义增强中，可以利用一些基于概率的方法捕获移动对象的运动规律，以更好地补全缺失的事件。
| [1] |
ORELLANA D, WACHOWICZ M, ANDRIENKO N, et al. Uncovering interaction patterns in mobile outdoor gaming[C]//2009 International Conference on Advanced Geographic Information Systems & Web Services. Cancun, Mexico: IEEE, 2009: 177-182.
|
| [2] |
WU F, FU K, WANG Y, et al. A spatial-temporal-semantic neural network algorithm for location prediction on moving objects[J]. Algorithms, 2017, 10(2): 37-37. DOI:10.3390/a10020037 |
| [3] |
MARKETOS G, FRENTZOS E, NTOUTSI I, et al. Building real-world trajectory warehouses[C]//Proceedings of the Seventh ACM International Workshop on Data Engineering for Wireless and Mobile Access. New York, USA: ACM, 2008: 8-15.
|
| [4] |
ZHENG Y. Trajectory data mining:An overview[J]. ACM Transactions on Intelligent Systems and Technology, 2015, 6(3): 29-29. |
| [5] |
LEE S H, LIM I K, LEE J K. Method for improving indoor positioning accuracy using extended Kalman filter[J]. Mobile Information Systems, 2016, 2369103. |
| [6] |
WALTON L, WORBOYS M. An algebraic approach to image schemas for geographic space[C]//Proceedings of the 9th International Conference on Spatial Information Theory. Berlin, Germany: Springer-Verlag, 2009: 357-370.
|
| [7] |
XIE X K, LU H, PEDERSEN T B. Efficient distance-aware query evaluation on indoor moving objects[C]//2013 IEEE 29th International Conference on Data Engineering. Brisbane, QLD, Australia: IEEE, 2013: 434-445.
|
| [8] |
ALVARES L O, BOGORNY V, KUIJPERS B, et al. A model for enriching trajectories with semantic geographical information[C]//Proceedings of the 15th Annual ACM International Symposium on Advances in Geographic Information Systems. New York, USA: ACM, 2007: 22-30.
|
| [9] |
LI Q N, ZHENG Y, XIE X, et al. Mining user similarity based on location history[C]//Proceedings of the 16th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. New York, USA: ACM, 2008: 34-43.
|
| [10] |
GONG L, SATO H, YAMAMOTO T, et al. Identification of activity stop locations in GPS trajectories by density-based clustering method combined with support vector machines[J]. Journal of Modern Transportation, 2015, 23(3): 202-213. DOI:10.1007/s40534-015-0079-x |
| [11] |
ESTER M, KRIEGEL H P, SANDER J, et al. A density-based algorithm for discovering clusters in large spatial databases with noise[C]//Proceedings of the Second International Conference on Knowledge Discovery and Data Mining, Palo Alto, USA: AAAI Press, 1996: 226-231.
|
| [12] |
BIRANT D, KUT A. ST-DBSCAN:An algorithm for clustering spatial-temporal data[J]. Data & Knowledge Engineering, 2007, 60(1): 208-221. |
| [13] |
LUO T, ZHENG X W, XU G L, et al. An improved DBSCAN algorithm to detect stops in individual trajectories[J]. ISPRS International Journal of Geo-Information, 2017, 6(3): 63-78. DOI:10.3390/ijgi6030063 |
| [14] |
YAN Z X, CHAKRABORTY D, PARENT C, et al. Semantic trajectories:Mobility data computation and annotation[J]. ACM Transactions on Intelligent Systems and Technology (TIST), 2013, 4(3): 1-38. |
| [15] |
JENSEN C S, LU H, YANG B. Graph model based indoor tracking[C]//2009 Tenth International Conference on Mobile Data Management: Systems, Services and Middleware. Taipei, China: IEEE, 2009: 122-131.
|
| [16] |
JUNG Y, JOO M. Building information modelling (BIM) framework for practical implementation[J]. Automation in Construction, 2011, 20(2): 126-133. DOI:10.1016/j.autcon.2010.09.010 |
| [17] |
YANG B, LU H, JENSEN C S. Probabilistic threshold k nearest neighbor queries over moving objects in symbolic indoor space[C]//Proceedings of the 13th International Conference on Extending Database Technology. New York, USA: ACM, 2010: 335-346.
|
| [18] |
SANDER J, ESTER M, KRIEGEL H P, et al. Density-based clustering in spatial databases:The algorithm gdbscan and its applications[J]. Data Mining and Knowledge Discovery, 1998, 2(2): 169-194. |
| [19] |
LI H, LU H, CHEN X, et al. Vita:A versatile toolkit for generating indoor mobility data for real-world buildings[J]. Proceedings of the VLDB Endowment, 2016, 9(13): 1453-1456. DOI:10.14778/3007263 |
| [20] |
CHEN L, ÖZSU M T, ORIA V. Robust and fast similarity search for moving object trajectories[C]//Proceedings of the 2005 ACM SIGMOD International Conference on Management of Data. New York, USA: ACM, 2005: 491-502.
|