应用时间滑动窗口模型的轨迹相似性研究

韩奕， 杜彦辉， 陈庆港， 芦天亮

(中国人民公安大学 信息技术与网络安全学院， 北京 100038)

随着互联网及移动互联网的发展，各类网络应用由于其强大的便携性、服务性和共享性，成为当今社会不可或缺的一部分，人们生活、工作、娱乐形式也已发生深刻转变. 根据中国互联网络信息中心(CNNIC)2月3日发布的《中国互联网络发展状况统计报告》中显示，截至2020年12月，中国网民规模达9.89亿[1]. 与此同时，社交网络身份多重化、虚拟化、匿名化特征越来越显著，一些不法分子通过网络传播极端言论，严重危害了社会治安，对社交网络用户身份研究及账号关联分析也受到了广泛关注.

当前，针对社交网络虚拟身份的账号相似性研究主要分为3类：一类是基于账号特征特征，如用户名、头像、生日、所在地、好友列表、兴趣标签等进行相似性分析；一类是基于好友关系，如关注人、粉丝列表等构建社交网络拓扑进行相似性分析；一类是基于自然语言理解，通过发布言论、语言风格等文本内容进行相似性分析.

(1) 基于账号特征分析方法.

基于特征属性的账号关联方法是根据不同维度的用户属性，判断不同网络账号是否为同一自然人的分析方法. 通常采用分类法或赋权法计算账号相似度，该种分析方法提出时间较早，且当前仍作为主流研究方法之一. 常用的特征属性如用户名、头像、生日、所在地、职业、教育等. 早在2009年，ZAFARANI等[2]就对多个社交网络平台的用户名进行了相似度统计验证分析. 2015年，刘东、吴泉源等[3]提出一种依靠用户名特征进行同一判定的方法，通过提取用户名隐含特征、量化特征、统计特征概率分布，提出一种从候选集合中找出与目标账号有高潜关联关系的其他账号计算方法. 此外，Acquisti等[4]利用人脸识别技术对账号头像进行处理，通过人脸相似度判断用户头像是否属于同一个人. 同时，还有较多文献[5-6]也针对用户头像计算图片相似度进行账号匹配. 但依据文献[7]研究表明，仅66%的用户会在社交网络账号中设置用户头像. 上述基于网络账号特征熟悉进行关联分析的研究方法，需在特定实验数据的环境下，特别是样本集足够大、特征信息足够多或目标确在样本库中，才能取得较好验证效果，不具备普适性.

(2) 基于好友关系分析方法.

好友关系、社交网络、兴趣爱好是一种相对固定的社交属性，因此在账号关联关系的任务中具有较好的研究前景. TAN等[8]利用网络拓扑图将好友关系转化为矩阵，一般而言，账号之间的关联关系是可以通过邻接矩阵进行表示，但在大规模网络中，这个矩阵太过稀疏. ZHANG等[9]提出了CONSNET算法，综合社交网络拓扑图的局部匹配信息和全局匹配信息，利用能量模型来解决用户身份关联问题. PEDARSANI等[10]采用贝叶斯算法进行用户身份关联，在两个规模不大且确实存在许多关联用户的网络中进行验证，取得了一定效果. 徐乾等[11]提出了WHUI算法，通过在好友关系结构上构建带权超图以描述关系结构，然后根据节点的拓扑结构特征计算相似度. 但是，利用社交网络或好友关系进行账号关联分析的方法难度较大，目前取得的研究成果很难适用于复杂的网络社交环境，计算复杂度及分析效率仍不理想.

(3) 基于内容识别分析方法.

基于网络用户发布的信息内容进行身份关联，即运用自然语言理解进行身份识别，且自然语言处理领域研究中有许多相关的研究. 例如ZHENG等[12]提出的通过账号发布的言论、书写风格识别账号身份. 但在跨社交网络的用户身份关联任务中，网络语言内容不规范、文本字数有限，且转载转发内容较多，仅通过文本处理进行关联的难度大. ALMISHARI等[13]通过实验证实了基于文本风格进行用户身份关联的可操作性. 此外，还有基于表情符号、句法结构研究虚拟身份情感强度、情感倾向性方面的研究[14-15].

考虑到位置轨迹相对于社交网络用户的其他特征更具有普适性，能客观、真实反映用户行为习惯，因此，本文对国内主流的社交平台用户的位置数据进行采集，提出基于时间滑动窗口的轨迹相似性匹配算法，计算用户相似性. 本文依托真实位置数据开展社交网络环境中用户轨迹相似性研究，主要创新如下.

① 本文针对社交网络中用户位置数据离散度高的情况，引入计算机网络中滑动窗口协议概念，有效提高了离散型坐标点在轨迹匹配算法中的计算有效率，即通过调整时间窗口大小计算不同用户位置轨迹集合的相似度.

② 本文构建了基于新浪微博、滴滴出行国内流量平台的用户位置数据集，在较大规模的真实数据中验证离散型位置数据在用户相似性研究的准确性，并将该算法结合实际案例分析其有效性.

1 问题分析

纵观现有的研究方法，主要存在以下问题：一是用于分析挖掘的实验样本过多依赖于公开信息，但是，这些与个人信息有关的公开数据是由用户自行编辑的，真实性无法保证. 二是较多的文献以Facebook、Twitter等社交软件的用户数据作为研究基础，这类平台与国内网名语言体系和行为习惯均不相同，不宜作为国内社交网络用户分析的实验数据. 三是与用户真实身份相关的信息如姓名、手机号、地理位置类涉及用户隐私，样本资源匮乏.

因此，本文在做网络用户真实身份研究时，对上述存在的问题解决思路如下：从数据采集入手，选择国内具有广泛用户群体的流量APP作为数据源；选择具有普适性且主客观不易更改的属性特征，即将地理位置作为相似性研究的核心依据；将数据采集时间跨度适当延长，使位置记录条数足够多，可用于刻画目标群体的时空轨迹特征.

2 相似性匹配算法

2.1 算法设计

鉴于社交网络用户的位置数据较离散，不能以连续的轨迹路径计算相似度. 但在实际生活中，人们出行规律通常具有时间周期性，如每天早上8:00—17:00经常出现在单位，21:00—6:00通常在家中. 因此，若将离散的社交位置数据结合独立、连续的时间片段，可以表现一个周而复始的过程. 这里，本文为了提高离散坐标点在轨迹匹配算法中的计算有效率，论文引入计算机网络中滑动窗口协议的概念，即通过调整时间窗口大小来计算不同用户轨迹集合的相似度.

定义 1用户轨迹(user trajectory)：用户轨迹定义为经过日期去特征化处理后，仅保留时间的位置坐标集合，用T={p1,p2,…,pt}表示. 每个坐标pi包含3个属性值，(lon,lat)是坐标点pi的GPS坐标，t是(lon,lat)被记录下来的时间. 一个用户在同一社交网络中产生的所有位置信息都记录在同一位置集合中.

定义 2滑动窗口协议(sliding window protocol)：在网络协议中，用于网络数据传输时的流量控制，以避免拥塞的发生. 该协议允许发送方在停止并等待确认前发送多个数据分组. 由于发送方不必每发一个分组就停下来等待确认，因此该协议可以加速数据的传输，提高网络吞吐量.

定义 3时间滑动窗口轨迹匹配算法(time sliding window trajectory matching algorithm)：如果两组轨迹在时间或空间上表现出相似性，则两个用户在活动过程中会频繁出现在附近的时间范围或空间范围，且出现得越频繁、相似程度越大. 这里，“附近的时间范围”可根据情况自定义时间片大小.

TA∈DA和TB∈DB是来自两个不同社交网络数据集(DA和DB)的两个轨迹集合，如果TA和TB是同一个真实用户产生的，则称TA和TB互相匹配. 论文最终目的是尽可能多且准确的识别出匹配的轨迹对.

首先，按照TA，TB轨迹下的ti进行时间片分域，在|tai-tbi|≤α条件下，对比轨迹点pai与pbi的欧氏距离dabi，当dabi≤β时，本文认为pai与pbi在ti邻域内轨迹匹配.

(1)

(2)

式中，‖TA‖表示轨迹点的个数. 基于时间滑动窗口首先计算TA轨迹中的轨迹点在TB轨迹的时间临域出现的比重，然后计算TB轨迹中轨迹点在TA轨迹的时间临域出现的比重，最后两者加权再平均. 只有当两条轨迹互相出现在对方临域的比重都比较大(即判断是否同源的阈值)时，才能说明二者相似.

如果两组地理位置集合在时间、空间上表现出相似性，即测试集中的数据出现在训练集中对应时间片段附近的位置，并统计出全时段出现频率，如果超过一定阈值，则认为这两个用户对应同一个人. 基于所有轨迹的Sim值比较，确定最佳阈值，调整参数α和β，确保判断结果保持高准状态. 在实际计算中，当时间窗口和距离尺度过小时，直接计算轨迹相似性会导致过于强调局部特征，而忽略整体相似的特性；而当时间窗口和距离尺度过大时，会导致结果精确率降低. 因此，本文需要根据不同轨迹特征，综合考虑Sim阈值、参数α和β的取值.

2.2 指标评价

论文参考精确率、准确率、召回率错误率、漏报率，并按照F值作为衡量算法性能的综合评价标准. 具体定义如式(3)～式(8)所示.

Accuracy=(tp+tn)/(P+N)

(3)

Precision=tp/(tp+fp)

(4)

Recall=tp/(tp+fn)

(5)

ErrorRate=(fp+fn)/(P+N)

(6)

MissRate=fn/(tp+fn)

(7)

F=2×pc×rc/(pc+rc)

(8)

式中：tp为指实际存在匹配账号，算法判断存在且判断正确的次数；fn为指实际存在匹配账号，算法判断不存在匹配账号，或算法判断存在但判断错误的次数；fp为指实际不存在匹配账号，但被算法判断存在匹配账号的次数；tn为指实际不存在匹配账号，算法判断不存在的次数.F值为准确率和召回率的调和平均数，是算法性能的总和评价指标.

3 实验与分析

3.1 数据采集

论文开发了一套自动化接口调用程序，从电脑端构造和发送请求，接受和处理服务器响应并返回的周边用户位置信息(图1). 这里对北京地区五环内的微博用户进行了位置探测，采集到3 965 150个独立账号，约24 660 014条记录. 其中，记录数大于100条的用户，有9 704个账号，作为第一个实验数据集.

图1 位置信息请求响应模型Fig.1 Location information reguest response model

同样的，论文采集了滴滴出行约101 774个用户的160 268条行程数据. 其中，采集到出行记录大于20次的用户，有53个账号. 由于滴滴订单的数据类型为行程信息，每一条出行记录包含出发地和目的地看做两个位置点，因此将每条记录拆解为两个离散的轨迹点，再根据两地导航距离计算行程时间，补全订单到达时间，以此形成的数据集作为第二个实验数据.

针对实验过程中涉及到的用户位置信息，本文将采取必要措施，最大限度地保证这些信息被用于本文实验范围内，并作出如下承诺：第一，本文不向任何个人、机构等第三方提供实验数据；第二，除本文展示的实验内容和数据外，将不会使用获取的用户资料信息实施攻击渗透.

3.2 数据处理

由于真实的多源网络用户位置数据难以获取，本文将微博用户、滴滴用户的地理位置数据集划分为两个部分，分别看作来同一个测试群体在两个不同时期的数据. 具体的，论文将数据集1中，2017年9月—2018年3月的记录作为训练集，记作DA；2018年4月—2018年9月期间的记录作为测试集中的正样本，同时，为了计算精确率、误报率与漏报率，这里还需构造与测试集中用户等量的其他用户记录作为负样本，最终所构造的测试集记作DB. 数据集2亦同，详见表1所示.

表1 位置数据集信息Tab.1 Information of location dataset

此外，由于社交位置记录具有离散、随机的特点，难以形成连续时空轨迹，因此论文在轨迹匹配时将时间进行降维处理. 即不考虑日期对轨迹的影响，均视作同一天、不同时刻的位置记录，以此刻画目标账号的位置特点.

3.3 实验结果

实验结果如表2和表3所示，数据集2相比于数据集1呈现出更高的准确率. 具体原因在于，滴滴出行位置数据较微博质量更高. 具体的，滴滴出行的数据中的出发地、目的地可能是家庭住址、学校、公司等带有特殊含义的地点；而微博位置数据则更具随意性，可能出现在任意地点，因此，需要足够规模的数据集才能刻画群体时空轨迹特征.

表2 数据集1的实验结果Tab.2 Experimental results of test one

表3 数据集2的实验结果Tab.3 Experimental results of test two

数据集1的实验中，将阈值设定为0.032，即SimAB值大于0.032以上，判断A和B两组轨迹相似. 同时，参数设置较为宽松，从α=5 000 s、β=6 000 m，逐步地，时间窗口和位置距离的约束条件变得苛刻，调整至α=600 s、β=1 000 m. 由此可见，微博用户在行为一致性方面，通常在时间间隔1 000 s、距离2 000 m范围内计算伴随关系效果最优，这在社交空间上研究虚拟身份轨迹相似性领域，具有很强的指导意义.

数据集2的实验中，本文根据实际出行时间、始发地、目的地，结合导航路径粗略计算预计到达时间，将每条出行轨迹转换为两个位置点，再通过调整相似度计算公式的时间窗口和距离参数，计算不同账号的轨迹相似度，结果如表3所示. 可以发现，对于出行前后时间间隔2 800 s、距离800 m范围内匹配到同源样本的F值最优，这在研究出行社交软件用户行为分析中具有较强的指导意义，也比较符合客观事实规律.

从上述实验数据结果中发现，经过调整时间粒度、距离尺度以及阀值，均可以提高网络身份相似性判断的准确率和F值，证明了地理位置在虚拟身份相似性判断中为正相关影响因子，且具有较高的可信度. 在具体的实际应用场景中，甄别网络用户相似性要均衡准确率及召回率，更要根据实际数据质量、数据意义灵活调整参数，提高模型的实用性.

4 案例分析

4.1 特定目标分析

对于已知特定目标账号，如“id=12******02、昵称=北京*******传媒”，查找与其相似度较高的其他账号，按照论文所提算法开展工作，查找与其相似度较高其他用户发现：账号id=12******01、昵称=“双权****双权”的账号与目标账号相似值>0.032，算法判定上述两个账号为同源账号.

本文对上述两个账号的注册信息、微博内容、相册进行查看，发现前者认证信息为北京某文化传媒中心官方账号，后者认证信息为该中心经营者个人账号. 据此，这两个账号均为同一人持有并维护，这一发现再次证明了论文相似性分析算法可用于特定目标关联账号分析.

图2 同源账号信息对比图Fig.2 Comparison chart of same source account imformation

4.2 特定群体分析

对于目标账号所在的特定群体分析，如查找“id=12******02 昵称=北京*******传媒”账号所属群体的成员，根据论文所提算法，这里将时间限定为从8:00—18:00，即白天工作时间作为有效窗口区域，地点不超过目标所在经纬度2 km活动半径作为有效地理区域，查找具有较高相似度的用户群体. 发现账号“id=18******73(囍***梁)”、“id=57******96(双***ttoo)”、“id= 24******81(九***室)”、“id=64******93(Ta***力)”等多个用户与目标账号具有较高的相似度，算法判定上述账号为同一群体.

本文对上述账号从注册信息、微博内容、签到位置、相册、好友关注等方面查看，发现上述4个用户在其各自的微博内容均有透露从事刺青工作，且与“id=12******02”账号存在互关、转发等行为，因此，可进一步判定上述账号与目标账号为同一群体. 这一发现再次证明了基于时间滑动窗口轨迹匹配算法可有效用于特定群体的发现与分析.

图3 特定群体成员账号主页对比图Fig.3 Comparison of account home pages of specific group members

5 位置隐私防护建议

根据本文采集的微博与滴滴用户位置数据可以发现，大部分网络服务商在用户隐私数据的保护程度还不够，如果通过大规模数据抓取，能够对特定网络用户或同特定的群体进行预测和分析. 因此，本文分别从APP开发者和用户本身两个角度讲述用户隐私保护方法.

对于APP开发者：(1)增加距离模糊手段. 如将用户位置做线性或非线性偏移，引入“不确定噪点”并放大“噪点”变量. 具体来说，允许用户选择一个半径R作为自己的地理位置的偏移，程序会在以用户真实位置为圆心、R为半径的圆内随机取一个点作为用户的地理位置. 这样其他用户就无法获取到真实的位置信息，进而保护了用户的位置信息. (2)识别和限制非正常网络请求. 如制定反爬虫策略，限制单个IP访问请求次数、建立行为模型，识别规律性较高的爬虫行为；对于涉及用户隐私较高或操作频繁的请求设置访问验证码；提高对虚拟GPS的检测技术，判断该请求永固的行为模式是否真实，从而决定对该位置的请求予以应答等.

对于用户：①分配最少可用权限. 系统安装APP后查看应用开放的权限，一些敏感权限尽量关闭；谨慎授予APP“打开摄像头和麦克风”、“读取短信”、“读取联系人”、“读取位置信息”等权限. 通常来说，用户可以打开“设置”—“隐私”选项，就可以根据自己的需求关闭某些权限了. 一些APP权限设置时还需注意勾选调用场景，如“仅在使用期间开启”，以防止有些软件在后台窃取我们的个人信息. ②按需调整隐私设置. 安装后，进入应用设置功能，查找“隐私”、“隐私设置”等选项，对“允许给我推荐通讯录好友”、“允许通过此手机号搜到我”等类似条款根据个人偏好及信息敏感程度调整进行修改. 通常情况下，上述功能是开启的，因此用户安装后需重新设置. ③及时升级应用版本. 不同网络服务商经常性升级、发布新版本，以此对产品功能、性能以及安全策略进行迭代. 如遇到重大网络安全事件，应及时跟进厂商后续响应，并采取相应措施，如修改密码、升级版本等.

6 结 论

由于社交网络中数据量大，用户属性数据的稀疏性、虚假性和不一致性现象突出，本文重点研究了指标较为客观、真实的位置数据采集方法，选择新浪微博“查看周边”、“签到”服务，和滴滴打车“查看周边订单”服务进行数据探测的技术研究，收集了北京地区新浪微博和滴滴打车用户的位置数据. 同时，本文提出基于时间滑动窗口的轨迹相似性匹配算法，即将用户轨迹按照一定的时间片段、距离远近进行划分，计算不同社交网络用户轨迹的相似性，从而实现网络用户身份相似性计算. 最终确定了地理位置为相似性判断的正相关影响因子，且相似性判断平均F值达到90%以上.

围绕社交网络账号关联分析当前的研究现状，未来可开展的研究方向包括.

(1) 进一步优化地理位置算法规则，提高匿名社交网络中账号关联分析准确性;

(2) 拓展数据采集渠道，为相似性分析提供新的解决思路和数据基础，同时挖掘社交网络环境下其他潜在影响要素，构建完善的虚拟身份关联分析指标体系,特别是选取具有普适性且容易获取的特征属性，如用户昵称、头像、关注好友、粉丝等;

(3) 研究复杂指标体系下账号相似分析的混杂模型和计算方法.