基于信令数据的多维度伴随计算分析

徐运海, 李博文, 赖 伟, 史 超

(广州汇智通信技术有限公司，广东 广州 510630)

0 引 言

近十年来，随着全球定位系统(Global Positioning System，GPS)，无线和卫星通信等技术的大力发展，至2020年，每百人拥有手机114.1部，全国移动通信基站总数达到931万个，全年净增90万个，城镇基站信号已达到深度覆盖。移动通信的蓬勃发展，使得产生了越来越多的移动时空轨迹数据，这些数据蕴含丰富的特征。近年来，挖掘伴随关系在公共安全、卫生、交通等行业起到越来越重要的作用。伴随关系是根据主动性决策理论衍生而出的一种概念。一个系统由若干个子系统构成，子系统之间相互依存，子系统之间是否依存以及依存强度关系叫做伴随关系。挖掘实体对象之间的伴随关系具有重要的实际应用价值。

1 相关研究工作

时空伴随分析目前主要分为三个方向：一是基于地理索引，利用GEOHASH或S2对位置建立索引的时空轨迹伴随模式[1]；二是处理海量数据时，使用局部敏感HASH，数据降维达到减少计算量的目的[2]；三是构建轨迹模型的时空伴随数据挖掘分析方法。

地理索引方式，需要知道精确的通信基站位置数据，将经纬度转换成地理索引。但是转换的索引等级是个核心问题，2G/3G基站覆盖范围比4G广，城市中环境复杂，楼层的高低、地下环境等都影响基站的覆盖。如果网格数量很大，势必会增加许多干扰的对象，网格设置过小，又会丢失原本属于该类数据的对象。同时在实际使用过程中，基站经纬度常常存在误报或者偏差，对伴随的精准度造成很大影响。其次不同运营商基站位置不一致，伴随效果不可避免的要比同运营商效果差。

海量数据伴随目前业界通常使用经纬度做hash，对数据进行降维处理，将具备伴随相似的数据聚集起来处理。后期处理仍然需要对数据做逻辑分析。伴随分为特定目标伴随和无目标伴随。区别在于分析时是否特意注重某个目标的轨迹，以特定目标轨迹为锚点，分析伴随目标的相似度。总体来说，要求速度尽可能快的在线实时查询方面，局部敏感hash做伴随方案效果大打折扣。

轨迹模型，很多学者常用聚类算来构建。典型的聚类算法有K-MEANS、DBSC AN、STING、OPTICS等[3-4]。该类模型在时空伴随模式上都存在一定的不足。如DBSCAN算法的时间复杂度要求极高，算法花费九成以上的时间在聚类迭代上。同时还有大部分算法都要求数据在时间和空间上连续，对于离群点忽视，造成伴随结果下降。还有类算法动态时间规划 (Dynamic Time Warping，DTW)，编辑距离(Edit Distance on Real sequence，EDR)和最长公共子序列(Longest Common Sub-Sequeue，LCSS)等分析轨迹的距离比较相似度，缺点是缺少了时间特征，只对轨迹点比较。

伴随分析的数据，一种是具备经纬度的数据源可以使用地理索引方案。另一种不需要经纬度，只需要基站的小区数据。即根据运营商的小区编号LAC、CI或者CGI计算，但是这存在很大的缺陷是只能伴随相同运营商目标，即移动对象只能伴随移动的目标结果，电信的只能伴随出电信的目标。

针对上述算法特点和轨迹数据特点，为符合准实时在线查询要求，解决基站跨运营商伴随和时空属性数据问题需要考虑空间和时间特征。本文提出了多维度特征伴随计算，根据网格和时间特征为准实时查询、提取信令轨迹数据、对经纬度做地理索引，这三种时空伴随分析方法构建轨迹在线库。

针对提出的不同运营商间轨迹数据拟合的问题，提出了加入多维度相似度语义方案的多维度精确伴随算法[5]。在传统轨迹拟合算法上，实现了运营商基站数据的邻基站聚类处理分析；在轨迹相似度上，拓展了点距离相似度、伴随时间相似度、运动距离相似度、起止距离相似度、运动状态相似度和方向相似度等。重点分析了目标伴随起止点，伴随目标数据缺失，伴随目标运动状态不同所带来的问题。

多维度伴随计算分析的流程如图1所示。伴随计算框架底层为存储用户信令轨迹的在线库。数据库选型应具备适合存储大量数据，读取方便的特性。本文选择hbase作为存储号码轨迹数据库。计算模块上分为两部分，一为信令数据的处理模型，构建出邻基站数据；二是伴随的计算模块，根据各个维度特征计算目标相似度。

图1 多维度在线伴随流程

2 轨迹模型和相关定义

定义1 设信令数据中的移动对象OB的时空轨迹TR={P1,P2,…,Pj,…,Pn},其中Pj=(tj,xj,yj,cgij)，tj表示时刻，xj表示经度，yj表示纬度，cgij是基站小区，每个基站都有一个唯一CGI编号。

定义2 轨迹维度(trajectory structure)，轨迹维度是属于轨迹内部特征数据的集合。这些特征维度构成了轨迹的信息，分析不同轨迹特点，得到特征在不同情况下的权重值，可增强伴随的准确率。目前本文定义的特征有Trajectory Structure < Distance, Time, Distance, HeadTailDistance, MoveState, Direction>分别为轨迹相似，离散点距离、伴随时间、运动距离，起止距离，运动方向等。同时定义特征权重w1+w2+w3+w4+w5+w6+w7=1,权重阈值均在0～1内。在特殊的情况下，可以设置个别权重等于0或者1。

定义3 相似度计算：根据定义2的内容，把轨迹特征用距离、方向和时间多个特征描述。计算相似度实际上就是比较不同维度特征的区别，引入权重距离(SimDis)的概念来衡量维度的不同。公式2，Normalized为归一化函数，实际上就是每个维度距离的归一化方法。

(1)

Sim(tr1,tr2)=Normalized(SimDis(tr1,tr2))

(2)

两份轨迹点的相似度，计算维度距离与权重积之和。最后通过归一化方法转换为轨迹相似度。

本数据模型中包含了时间信息、经纬度数据和基站信息。提取轨迹数据特征维度，从中衍生出除了轨迹相似外的众多伴随相似距离语义维度[6]。轨迹相似算法计算轨迹点，只能比较空间上点的相似性。为此，添加伴随时间距离维度，伴随时间相似度SimDistime同时可用于解决伴随目标数据是否缺失，完整性多少的问题；基站邻点距离维度SimDispoint用于解决只能伴随相同运营商目标的问题；运动距离维度SimDismove用于比较目标运动距离和每个伴随目标运动距离比值；起止距离维度SimDisOD用于比较目标对象和伴随对象的起点和终点；运动状态维度Sim5用于比较伴随时间内运动状态的改变；方向相似度Sim6用于比较运动方向是否相似。OD点距离用于加强伴随时，起点和终点相同的轨迹权重。

3 邻基站预处理分析

3.1 信令数据特点

基于基站信令数据，挖掘基站的相邻基站是有效分析基站数据聚类模式的方法，即找到当前基站下，移动、联通和电信的附近基站集合。信令数据具有以下三个特点。

1)相比较难以搜集的GPS数据，信令数据具有实时性、出行时空范围全覆盖和完整性的优势。目前数据大部分来源于4G数据，少量来自2G/3G数据，4G基站较2G/3G基站数量多且覆盖范围小，范围半径200 m～1 200 m不等。运营商采取的定位技术不同也会导致定位精度不够。基站的范围对比目标实际位置，如GPS数据，难以得到更细粒度的数据，不能表示用户实际位置。用基站位置分析确切目标位置，分析过程目标行为具有随机性。

2)相同地区下不同运营商的基站位置不尽相同，分析数据对同运营商类型数据效果更好，针对不同运营商的目标对象数据聚类做模型处理，数据依存性明显比同类型数据低。

3)信令数据既是空间数据，又是时序数据，在时空区间内，空间和时间样本采集存在部分脏数据，采样数据不均匀以及信号强度问题导致信号点漂移甚至异常切换问题。数据同时具有离散性，不确定性。

因此，利用信令数据分析目标伴随情况，具有干扰项多、污染重和利用难等特点[7]。

3.2 信令数据预处理

本节主要目标为实现运营商之间的相邻基站计算并提高相邻基站精度。加强目标与关联结果伴随依存强度。数据为信令数据，传统单机计算平台效率缓慢，因此提出基于Spark分布式计算平台进行数据挖掘处理分析。为此从四个方面对数据进行预处理，然后将四份数据融合，具体数据处理实现方法如下：

1)信令数据本身具备基站切换记录信息，通过判定可以得到相同运营商相邻基站对数据。提取信令数据中当前基站与前一个基站数据；聚合基站，得到基站与相邻基站关系数据。并根据每个基站对的切换次数得到切换频次，根据频次计算切换概率。

2)遍历全部信令数据，捕获同号码两个在较短时间(5 s)内且距离符合阈值(800 m)的上下文基站数据，判定为相同运营商间相邻基站对数据。

3)遍历信令数据，对基站位置做索引，根据距离求取基站附近范围800 m内相邻基站集合。

4)基于一机多卡数据，捕获到较短时间(例如5 s)内且属于相同移动设备数据的两条信令数据中的不同基站，将该基站数据对判断为具有相邻关系。

信令数据经过上述预处理后，得到不同基站关系的数据。根据基站切换事件数据，距离分布等信息，不同目标伴随数据经过融合计算得到为一份基站关系数据。

3.3 伴随计算维度

根据目标轨迹数据，从轨迹数据库使用快速伴随初步筛选出排名靠前的目标，此步骤的作用是从轨迹数据库存储对象中，查询目标经过轨迹附近的对象数据。关于查询逻辑不在本文中叙述。查询得到的对象数据使用各个相似度维度进行并发计算，具体算法步骤如下：

1)基站邻点距离相似度。根据目标对象和关联对象在相近的时刻，使用关联对象CGI基站数据查询预处理中邻基站数据，判断目标对象在该时刻的CGI基站是否包含在查询出来的邻基站数据中，若包含，则根据基站的切换概率赋予该关联对象和主对象在该时刻的相似度。

2)OD点相似度。选取目标对象和关联对象在查询时间段内前10%和后10%的点作为首尾点，计算首尾点之间的距离相似度。

3)伴随时间相似度。将目标对象和关联对象的开始伴随时间和结束伴随时间与查询时间做比较，计算伴随时长和查询时长的比值，比值越接近，表示关联对象的轨迹数据相对目标对象越完整。

4)伴随距离相似度。比较计算每个关联对象在伴随时间段内的运动距离和主对象在查询时间内运动的距离，主要是降低主对象和关联对在同时间处于不同运动状态下的相似度。

5)关联对象运动距离归一化相似度。计算出每个关联对象在查询时间段内的运动距离，将各个关联对象的伴随距离做归一化处理，计算出伴随距离相似度。归一化对于关联对象最大的伴随距离相似度都远小于1的情况，会降低整体平均相似度结果，即使关联对象轨迹与主对象的大体一致，也会得到一个较低的相似度结果。

6)编辑距离。计算查询时间段内的目标对象和关联对象的轨迹序列的编辑距离相似度[8]。传统的轨迹相似算法包括欧式距离， DTW，LCSS和EDR。欧式距离，计算两条轨迹对应点上空间距离的平均值，缺点也很明显，对噪声敏感同时不能度量不同长度的轨迹；DTW灵活，能自动匹配轨迹，对轨迹无限制，但是没有对噪声点处理，一旦遇到噪声点、离群点对轨迹相似度影响较大；最长公共子序列LCSS对噪声做了处理，噪声点和离群点不会计算到结果中。并且最小距离阈值参数ε不易设定；编辑距离EDR对轨迹插入，删除和替换操作达到A轨迹转换成B轨迹，对噪声敏感，同时最小阈值难以设定，与LCSS相比，EDR算法一般情况下算法复杂度更低，而且在实际使用中，信令数据中使用EDR编辑距离测试轨迹相似度比LCSS更好。

7)离线伴随结果相似度。查询目标对象和关联对象是否为常伴随关系对。此处依赖预处理数据模块，预先得到关于常伴随关系特征数据，可通过minhash/LSH算法减少数据处理量，在依据轨迹相似度算法计算目标轨迹是否匹配[9]。关于常伴随数据分析本文不做叙述。

8)状态转换相似度。仅适用于目标对象在查询时间段内有停留的情况，计算目标对象和关联对象是否在相同时间有相同的状态转换[10-11](从运动到停留或从停留到运动)行为发生。

9)运动方向相似度。计算每个关联对象的首尾点和主对象首尾点方向向量，以衡量主对象和关联对象运动方向的相似度。

传统的轨迹相似度算法比较点与点，线与线的拟合情况。随着数据采集的发展，数据种类，需求类型一直在扩大，促使数据分析从简单走向复杂，局部走向全局。即使是具备相同类型的数据，在单一的数据维度看来，是完全不同的，针对数据的情况，数据分析不得不更多地从多维考虑。本文从轨迹线、距离、时间、运动状态、目标关系多个维度分析，比较单一轨迹线有更好的效果。

4 实验结果

实验选取一批移动对象在一段时间内的信令数据，并从中选取多个具有伴随关系的移动对象对，目标为伴随关系对中的一个移动对象去能实际伴随出另一个移动对象。伴随维度特征中如时间特征，运动距离特征等，受限于用户情况，基站空间位置，数据离散情况。即使具备伴随关系的目标群体，各个特性表达也不明显，不具备单独作为伴随相似度的度量，可作为主伴随关系特征的补充。因此分别使用基于轨迹点距离的单个维度的相似度计算和使用多个维度的相似度计算，测试目标对象在伴随结果中的排名，测试结果数据如表1所示。

表1 单维度与多维度伴随覆盖率比较

从表1可以看出，TOP10的覆盖率提升到70%以上，TOP100的覆盖率由单维度的42.8%提升到92.8%，效果非常显著。

5 结 语

针对不同运营商之间的基站位置差异情况，结合信令数据和伴随关系的特点，提出了邻基站数据分析和多维相似度计算的方法。该方法首先通过信令数据挖掘出基站的相邻基站数据，从而体现了伴随过程中不同运营商之间的基站位置差异，接着根据伴随关系的特征分析出多个相似度计算维度，针对该情况下的伴随轨迹特征，使用不同的维度进行计算，从而分析出具有真正伴随关系的对象。根据实测数据，相比于单个维度的伴随计算，多维度伴随计算能够显著提高目标对象的命中率。

多维度伴随计算在目标中长距离运动下，伴随结果目标正确率较高。短距离伴随效果不明显，原因在于短距离运动下，目标时间和空间属性极其离散，并且4G基站覆盖范围较大，干扰数据太多。综上所述，解决短距离伴随，可提出两种方式，一是缩短信号覆盖范围；二是挖掘目标与伴随目标的行为属性，根据日常行为属性关联，提高伴随目标准确率。