一种基于语义的轨迹流数据清洗方法研究

姜雅雯，余建坤,2，陆镜弛

(1.云南财经大学 信息学院, 云南 昆明 650000;2.云南财经大学 云南省经济社会大数据研究院, 云南 昆明 650000)

在数据呈现爆炸式增长的现代社会，众多的企业组织会投入大量的时间、精力去搜集和分析数据以求获得更高的经济价值，但如果过多的关注对数据的分析而不注意数据本身质量，为此会付出沉重的代价.文献[1]表明数据的质量对研究存在至关重要的影响，数据的质量问题会给结果造成重大影响，有统计表明，美国企业因数据质量造成的额外成本高达6110亿美元一年[2]，而在医疗数据中有占到75%临床重要发现因为数据的问题被延迟公开[3]，除了成本问题，数据的质量很有可能会影响到分析的最终结果，导致前期努力付之一炬，例如英国生物银行耗时12年的一个健康检测项目得到了与事实截然不符的结论[4]，因此提高数据的质量是数据清洗的首要任务.

为了获取较高质量的数据，同时也为了确保原始数据的质量不被破坏，文献[5]提出一种基于约束条件的流数据清理方法——利用数据到达速度作为限制条件，依据数据间的最小距离来修复数据；与平滑方法相比，该方法时间性能有所改善且修复数据精度更高，但此法注重于修复，不能有效去除冗余，清洗后的数据量依旧很大.流数据的数据质量除了受到大面积误差或大的尖峰误差的影响外，不严重偏离事实的小错误也会影响到数据的质量，文献[6]提出一种基于统计的数据清洗方法，通过已到达的连续数据速度的概率分布来对异常数据进行清理，确保数据的准确性，实验证明此方法可有效修复偏离事实较小的小错误，但对大面积的异常或连续异常数据的修复效果不佳，达不到提高整体数据质量的要求.文献[7]提出一种基于高效关联度的聚簇建模思想来进行数据清洗，利用组间成员的联系判断对象所在小组，维护小组内的动态变化以提高清洗的准确性，该方法有效的提高了数据的质量但清洗完的数据量依旧很大，数据保存成本较高.文献[8]提出一种改进的分布式增量数据聚合方法，对数据进行清洗提取，可确保数据的准确性与可靠性，但清洗投入成本较大且过程较为复杂.以上方法注重于提升数据的质量，却忽略了数据的成本问题.

由于流数据的数据分析往往需要投入大量的人力和物力，耗费较高的成本，为此人们在进行流数据清洗时就开始考虑优化、缩减成本的方法.Hadoop高效、可伸缩性的分布式处理满足降低成本的需求，基于Hadoop的流数据清洗相关研究应运而生[9-10]，但在实践中发现，并行计算框架会在实现过程中出现冗余的MapReduce，给数据带来新的冗余，这样清洗完数据的质量会有影响.基于密度的聚类处理方法能有效压缩数据体积以降低成本[11～13]，但随着数据量的增长，算法的执行时间呈指数增长，清洗数据的成本也随之增长，因此该方法不太适用于流数据.为降低算法执行成本，文献[14]在前人的基础上提出了改进的IMR算法，在预测错误的最小检验中迭代的进行修复，提高数据质量密度.实验表明可以将算法的线性时间复杂度降到恒定时间，可以凭借较低的时间成本获取较高质量的数据，但由于清洗的密度较高，清洗完成的数据量较大，数据的保存成本也随之增加.

除了成本问题外，流数据所蕴含的语义信息也是十分重要的，它可以加强用户对数据的理解，帮助优化对数据的查询与分析.文献[15]指出将轨迹流数据的分析整合与具体的应用场景是相结合，可提前判断得出与轨迹分析相关的空间特征类型(例如，旅馆，旅游地点).文献[16]指出一些轨迹数据分析研究存在的问题便是缺乏语义信息的分析，为获得更多有价值的信息需要依靠更复杂的查询，如数据挖掘算法，并且在现实情况中，数据中的移动行为等问题需要通过结合轨迹和语义信息来分析判断.文献[17]向我们展示了在不添加语义信息和添加语义信息两种情况下同一个查询的结果，实验表明在没有语义的轨迹中，轨迹与相关地理信息对象的关系需要进行多次的重复计算，效率较低，而添加了抽取到的语义信息的轨迹在可视化图表中可清晰看出客户的行为动态，无需再次查找计算.

因此，本文提出一种基于语义的轨迹流数据清洗方法SSMOT，采用文献[17-18]提出的轨迹数据模型将裸数据转化为语义轨迹，并将语义作为动态过滤指标去除重复采样以降低数据体积，以达到对数据进行高质量的清洗的目的同时将空间地理信息与数据进行整合，清洗完成之后，将从原始数据中得到高质量的语义轨迹数据集，服务于后续数据挖掘.本文使用真实商场数据集进行了实验验证，证明本方法的优势性，对实验结果的比较和分析，将在第4节中详细阐述.

1 理论背景

1.1 轨迹数据模型

轨迹数据产生于车辆的移动、人类的行走、动物的迁徙等行为活动中，这种源于生活的数据往往蕴藏着大量有价值的信息，因此，对它的分析研究也一直没有停歇过.传统的轨迹数据以原始时空位置的形式展现，比如车辆移动轨迹数据会以编号、时间、地点、经纬度的形式展现，但这种数据表现方式并不能体现对象的“运动状态”且运动的空间类型得不到体现.然而在对数据进行分析的过程中，需要的是体现对象运动结构化的数据记录即时间序列间隔，从行程的开始到结束，每一个停留的点都需要被标记，停留的点之间行程段都要在对象的运动中占据一定的时间间隔，为此文献[18]将传统的概念模型扩展到覆盖时空建模维度，从而定义了一个新的轨迹数据模型.

定义1 轨迹是对象的位置演变记录(该对象是指为了实现给定目标而在给定时间间隔内在空间中移动的对象而非静态对象)，轨迹的开始为tbegin，终点为tend.

trajectory:[tbegin,tend]→space

在轨迹中，运动的对象不一定会连续移动.因此，可以通过时间上的定义来对轨迹本身进行时间子间隔序列的分割，在此间隔中，对象位置可以发生变或者并保持固定，若发生位置变化则称之为移动，若位置固定则称之为停留点，至此轨迹可以看成是一系列停留点、移动的集合.

定义2 停留点(stop)是轨迹[tbegin,tend]的一部分，该时间间隔[tbeginstopx,tendstopx]非空并且对象在该时间间隔内没有产生移动.两个停留点的时间间隔始终不相交.

定义3 移动(move)是轨迹[tbegin,tend]的一部分，存在于2个停留点之间或者在tbegin,和第一个停留点之间或者在最后一个停留点和tend之间，该时间间隔[tbeginmovex,tendmovex]非空且呈现在可视化视图中是建立在采样点上的折线.

原始数据通过轨迹数据模型，从样本点转化为停留点和移动的集合，在可视化图表中会得到更为直观的运动状态变化，能更好的发现对象的运动行为规律，分析和预测对象的行为动态.

1.2 语义轨迹模型

在数据挖掘中，更有价值的数据可以帮助人们获取更多的知识.例如人们的日常生活行为数据，研究人员更关心的是人们去了哪些地方、进行了什么活动，分辨这些具有代表意义数据的常用方法就是聚类.然而以数据的密集度作为清洗条件很容易造成一些密集度低但价值高的数据被忽略，从而对数据挖掘的结果产生影响.为了获取较高价值的数据，文献[17]提出了一种语义轨迹模型，重新定义了语义轨迹的停留点和移动，语义轨迹模型的应用可以有效的避免这种情况.图1是根据时间属性将数据采样点连接起来的轨迹，从中只可以看出D1到D4可以有3种非直接到达路径(D1-D2-D5-D4;D1-D5-D4;D1-D3-D4)；而图2结合了语义信息:机场(A)、大巴站(B)、旅行社(Y)、景区(V)、酒店(H)，除了存在3种间接从机场到景区的路径外(分别为机场-大巴站-酒店-景区；机场-酒店-景区；机场-旅行社-景区)，可以看出选择先到达酒店再前往景区的比重大.其中旅行社(Y)的密度较低，在传统的轨迹中该点可能会被忽视，但在语义轨迹中，旅行社(Y)会被保留并参与数据的分析.

定义4 语义轨迹移动定义为以下4种情况之一：

1) 在轨迹T的2个连续停止时间之间的最大连续子轨迹；

2) 在轨迹T的初始点和第一个停止时间之间的最大连续子轨迹；

3) 在轨迹T的最后一个停止时间和轨迹终点之间的最大连续子轨迹；

4) 如果轨迹有且只有一个停止时间或者没有停止时间，那么移动则表示为轨迹本身T.

定义5 语义轨迹停留点是移动的组成部分，当移动从开始进入到离开某个空间地理范围的时间超过既定的时间阈值Δc，则停留点定义为S=(RC,tin,tout)，其中RC表示空间地理位置集合，tin和tout表示进入和离开空间地理范围的时间.

定义6 语义轨迹是N个停留点的集合，St=(S1,S2,…,Sn-1,Sn),对任意停留点Si满足定义5的要求，语义轨迹的长度即为其所包含的停留点的个数n，n>=1.

2 数据清洗模型及算法步骤

本文提出的数据清洗模型如图3所示，主要步骤为裸数据转化轨迹、获取语义轨迹和获取SSMOT数据集.

Step 1 误差类型获取：对原始数据进行抽样分析，找出数据误差的类型，对误差进行分析，找到误差的类别，根据误差的分类确定清洗的流程.准确的误差分析是数据清洗的基础和保障.

Step 2 语义信息集合获取：将地理信息整合为语义信息集合，这里面包含了需要添加进最终清洗完数据的语义信息以及作为动态过滤指标的语义属性.

Step 3 轨迹获取：依据文献[18]提出的轨迹数据模型的相关理论，提取停留点和移动并得到轨迹.

Step 4 语义停留点及移动获取：在获取轨迹后，借鉴文献[17]的思路获取语义轨迹，验证轨迹T的每个点是否与RC的几何形状相交，RC为地理空间在平面上的几何映射，在肯定的情况下，查看交叉的持续时间是否大于等于给定的阈值Δc.如果满足上述条件，则将相交的候选停留点视为语义停留点，并记录该语义停留点.

Step 5 SSMOT集合获取:上一步获取的语义轨迹，可成功将地理空间外的数据点过滤掉，但每个被标记的空间内，依旧存在着重复采样和噪点，比如某个人在某家餐厅的吃饭时间超过30 min，我们需要的信息更偏向于餐厅的位置和该客人停留的时间段，而不是30 min内所有的数据采集样本，所以在已获取进入和离开餐厅时间的基础上，需要去除客户位置不变而时间变化的重复采样以及采集设备产生的数据漂移噪点.为此，提出一种基于语义的数据清洗方法SSMOT，在SMOT的基础上使用语义作为动态过滤指标替代固定过滤值，旨在提高数据清洗的质量.

Step 6 对比分析：对清洗完成的数据进行分析，与其他清洗方法进行结果比对，查看数据质量和成本效果；结合步骤一的噪声分析判断数据清洗有没有达到预期效果.

Step 7 输出:输出清洗完成的语义轨迹数据集，完成数据清洗.

3 应用实例

为了验证本文提出的基于语义的商场轨迹流数据清洗模型的可行性，以2015年某商场的真实数据作为应用案例来进行测试.本实验是在配置为酷睿i7-8750H(2.20 GHz 6核)、16 GB 内存的计算机上进行的,系统为Win 10,使用Python(3.6.3)+UltraEdit(25.00.0.68)编写程序.

3.1 数据概括

实验数据部分使用的是来自河南某商场的真实室内轨迹数据集，该数据集是通过商场无线AP(accesspoint)设备采集的,通过信号强弱计算用户距离AP设备的距离，最后获得相应的数据，每个元组分别表示用户ID、x坐标、y坐标、区域ID、采样时刻、连接状态、建筑ID、楼层ID.采样频率为1次/s，该数据集一共有 43 784 744 个采样点,731 739 条轨迹，数据体积为2.11GB.该商场有3层楼，一共164个商户，即该数据集共164个地点.

表1 数据样例

3.2 数据噪声分类

随着定位技术及通信技术的发展，定位设备被广泛应用，商场内的定位设备会定时采集客户的位置信息并将其汇总，形成大规模的客户轨迹流数据.这些数据中包含了大量的信息，可用于多种场景：客户行为动态模式、商场布局规划以及热门商铺分析等.由于定位设备自身的缘故，加上商场客流量大、商铺分布较为密集等缘故，实时采集的数据可能会出现各种各样的问题，会出现不合理甚至错误的数据.少量的问题数据可能对整体的数据挖掘影响不大，但对单个客户的行为分析时可能会出现严重偏差.例如在对客户进行动态行为分析时，同一个位置坐标反映到另一个楼层，客户所在的店铺就会发生改变，客户实时的兴趣趋向就会发生改变，得到一个错误的行为动态.进过研究发现，商场轨迹流数据噪声分类一般分为2类：一类是由设备所产生的，一类是由人为因素所产生的.

设备产生的噪声：①数据集通过商场无线AP(accesspoint)设备采集的，当用户的手机接入AP设备,我们就能通过信号强弱计算用户距离AP设备的距离，最后获得相应的轨迹数据.但是由与设备的制约，会产生“漂移”数据，例如根据客户ID显示，客户前一秒处于2楼的某家商铺，下一秒会定位到3楼.②由于信号较弱导致采集到的客户数据有所偏差，这类误差通常会出现在设备采集的边缘地带.③设备在获取客户数据产生的不合理误差，如采集时间与实际情况不符合，这类误差的产生通常是由于AP设备设置问题引起的，且这类误差所占比例较小.

人为因素产生的误差：①为研究客户的行为动态，会把商场工作人员产生的数据作为噪声处理，例如保安巡逻、清洁人员打扫产生的数据，这类数据的明显特征是大多数集中在走廊过道处且每日循环往复、有固定的时间间隔，根据此特征可快速区别.②客户在走廊过道产生的数据密度会大于在商店内的数据密度，这对研究客户的商铺行为动态会产生很大的影响，需要加以区分.

4 实验分析

为了验证本文所提出方法的准确性，与文献[19]使用同一份数据进行比较实验，比较结果如下表所示.

表2 实验结果

从表2可以看出，本文提出的方法在减小数据体积，降低成本上优于文献[19]所使用的方法且处理后的数据价值密度得到了明显提高.

如图4所示，未经清洗的数据是杂乱无章的；经过清洗，得到如图5所示的结果，可以发现数据集中密集度较高的是图中红色部分较深的区域，同样的该部分的数据价值密度也较高.经过清洗可以过滤走廊部分密集度高但价值密度低的数据，达到压缩数据体积、降低成本的目的.为了验证数据的质量，从原始数据中随机抽取了某个ID，并对该ID进行清洗分析.实验结果如图6、图7和图8所示.

实验结果表明，语义在清洗过程中起到了很大的作用，使用语义清洗可有效的过滤重复采样和噪声，提高数据质量密度并且语义有助于在清洗过程中发现客户的动态行为.

在清洗前，该ID在3楼的活动状态并不明显，如图6只能看出在火锅店附近聚集的点较多.清洗后发现，该ID 当天的活动轨迹为16∶49(娅茜)——16∶46(抱抱熊)——17∶29-17∶36(食色)——17∶39-18∶10(舍家家居)——18∶28(龙泉青瓷)——19∶02(包子楼)——19∶06(黄记煌)——19∶28(阿三生煎)——19∶46-22∶25(大家庭火锅)——22∶53(艺家瓷).这表明清洗完成的数据没有破坏数据中蕴含的客户行为动态信息，反而可以更方便、更直观的体现用户的动态行为过程.

综上，实验证明本文提出的方法可以有效地压缩数据的体积，缓解由于数据量较大而引起的成本问题，并且提高了数据价值的密度；在数据质量上，该方法没有破坏数据所包含的信息，可以将动态行为信息更直观的表现出来以表现其优越性.

5 结语

本文针对流数据挖掘中的流数据清洗问题进行研究，在现有研究的基础上，综合考虑了数据清洗质量要求和客观地理信息需求，采用轨迹数据模型，提出一种基于语义的轨迹流数据清洗方法用于流数据清洗研究，并采用真实的商场数据进行试验验证.实验结果表明, 本文所采用基于语义的轨迹流数据方法较以往的方法有更高的准确率.然而, 本文实验研究所使用的数据量较大，实验周期较长，虽有了一定的成果，但缺乏算法理论分析的相关内容如算法计算代价分析，算法复杂度分析.未来的工作将围绕该方面进行展开.