随着GPS终端、Pad、智能手机等位置感知设备的广泛普及，各类新型社交网络手机应用不断涌现，促使移动社交网络(mobile social networks)得到了快速发展。移动社交网络也称基于位置的社交网络(location-based social networks, LBSN)，本质是提供一个在人群中分享兴趣、爱好、状态和活动等信息的平台^[1]。如国内的腾讯QQ、微信、新浪微博、人人网，国外的Twitter、Facebook、Gowalla、Foursquare等，这些LBSN应用聚集了大量移动用户。据We Are Social公司在2016年数字报告^[2]中指出，2016年全球社交网络用户约19.7亿，占全球总人口的27%。LBSN中海量带有位置信息的社会媒体数据可被用于各类挖掘应用研究，如挖掘用户兴趣偏好、好友推荐、兴趣点推荐、热点路径推荐等^[3]。

移动社交网络正逐渐改变着人们的生活方式和生活习惯，给人类社会带来前所未有的变革以及巨大的经济收益^[4]。同时它也吸引了一些不法者盗取用户账号及信息进行各种恶意行为，影响了用户的正常使用，损害了用户利益，甚至给用户带来了巨大的经济损失。因此，面向移动社交网络，追踪用户的历史签到位置数据，从用户移动行为特征视角，对用户状态进行在线异常检测，这对于移动社交网络的安全、用户的隐私保护等具有重要意义。

针对移动社交网络异常账号的检测问题，学术界和工业界都提出了大量检测方案^[5]，主要包括基于行为特征的检测、基于内容的检测、基于图的检测和无监督学习的异常检测方法等。而针对移动社交网络中签到位置数据异常检测研究还比较少。本文从用户的移动位置特征视角对异常签到位置进行检测，针对移动社交网络用户异常签到检测问题，提出了一类基于签到位置的在线异常检测方法。首先，在基于距离的异常检测基础上，提出了两种异常签到模型，即基于历史位置的异常签到(history location based outlier，H-Outlier)和基于好友圈的异常签到(friendship based outlier，F-Outlier)；其次，针对H-Outlier，提出了一种优化的检测算法H-Opt，利用优化的检测状态与邻居搜索机制降低检测时间；然后，针对F-Outlier，基于提出的3个优化策略，提出了一种基于触发的优化检测算法F-Opt，将连续在线异常检测转化成了基于触发的异常检测方式，本文采用滑动窗口技术实现H-Opt和F-Opt；最后，在真实的移动社交网络用户签到数据集上，验证了所提算法的有效性和效率。

在移动社交网络中用户往往会在新地点进行签到或登录，所以H-Outlier检测到的异常签到地点很有可能并非真正的异常。为排除这些伪异常状况，本文提出了好友圈的概念和基于好友圈的异常签到模型F-Outlier，这是因为在移动社交网络中50%~70%的行为可由周期行为解释，还有10%~30%行为可根据好友关系行为解释^[6]。也就是说，在移动社交网络中用户往往与认识的好友共同出现在不经常签到的地点，如朋友聚餐、商务活动或者公务出差等。针对这些伪异常，我们通过检测好友圈中好友签到位置来判断用户的签到是否为真正的异常签到。

1 相关工作

Knorr和Ng^[7]最早提出了基于距离的空间异常(DB -Outlier)检测问题。给定一个数据集合，若某数据点的邻域内的数据个数小于给定阈值，则该数据点为基于距离的异常点。之后，Knorr等^[8]将基于距离的异常模型应用到时空轨迹数据异常检测中。Ramaswamy等^[9]提出了一种基于k近邻的异常定义，根据数据点到第k近邻的距离检测出n个k近邻距离最大的数据点作为异常点。Breunig等^[10]提出另外一类基于密度的数据异常类型，通过计算本地异常因子LOF来检测局部异常点数据，但该算法存在较高计算复杂度问题。

在数据流异常检测方面，Yang等^[11]采用滑动窗口方式在数据流上挖掘基于邻居的模式，主要包括基于密度的聚类和基于距离的异常检测。Angiulli等^[12]通过在数据流上分析数据点是否为“safe inlier”来优化检测方法。Kontaki等^[13]利用“safe inlier”设计了一种事件触发的数据流异常检测优化算法。Cao等^[14]提出了一种数据流异常检测框架，该框架可用于处理基于距离的和基于k近邻的两类异常检测模型。

针对移动对象的轨迹数据，Lee等^[15]提出了一种划分-检测的轨迹异常检测框架，将轨迹划分成t-partition序列，通过计算t-partition间的距离和密度，以发现异常的子t-partition。Bu等^[16]提出了一种连续监控移动对象实时轨迹数据流的异常检测算法，该方法关注在检测单个移动对象实时轨迹数据中的异常子轨迹段。文献[17]针对海量移动对象系统中异常对象，提出了一种基于邻居的异常移动对象检测方法，可发现不同于其他邻居对象运动轨迹的异常对象。

2 问题定义

本节首先给出一些重要的定义和表示，然后对基于距离的移动社交网络异常签到模型进行描述。

定义1  基于距离的位置异常。 给定位置数据集D、距离阈值d、邻居点数量阈值k，对于位置数据点o∈D，如果|{p|dist(p, o)≤d, p∈D}|≤k，则称o是一个基于距离的位置异常点。

U={u₁, u₂, ..., u_m}表示移动社交网络的所有用户集，用户u_i在t_j时间点的签到位置表示为p_jⁱ。

本文采用基于签到位置数量的滑动窗口W来处理移动社交网络中实时的签到数据，窗口长度标记为|W|=w，也就是说，W中包含w个签到位置。

定义2  基于历史位置的异常签到。给定距离阈值d、邻居点数量阈值k，滑动窗口W，对于用户u_i的签到位置p_bⁱ∈w，如果|{p_jⁱ|dist(p_jⁱ, p_bⁱ)≤d, p_jⁱ∈W}≤k，则称签到位置p_bⁱ是一个基于历史位置的异常签到点，记为H-Outlier。

从定义2可以看出，H-Outlier是基于自身历史签到位置的，这也是因为用户日常活动轨迹记录往往具有周期性^[18]。

设Fr(u_i)表示用户u_i的所有直接好友集合。与QQ、微信等社交网络的好友圈的定义不同，这里给出的好友圈定义既包括用户u_i直接好友又包括与u_i有一定数量共同好友的间接好友。

定义3  好友圈。给定支持阈值m，用户u_i的好友圈包括u_i的所有直接好友和与u_i存在至少m个共同直接好友的间接好友，即Fr(u_i)∪{u_j||Fr(u_i)∩Fr(u_j)|≥m}，简记为Net(u_i)。

定义4  基于好友圈的异常签到。给定距离阈值d、好友圈包含的好友数量阈值k_f、时间△t，对于基于历史位置的异常签到点p_aⁱ，如果|{u_s|∃p_j^s, dist(p_j^s, p_aⁱ)≤d, |t_a-t_j|≤△t, u_s∈Net(u_i)}|≤k_f, p_aⁱ是一个基于好友圈的异常签到点，记为F-Outlier。

根据定义4可知，F-Outlier是在H-Outlier定义的基础上定义的，因此，F-Outlier集合是H-Outlier集合的子集。

文中涉及的符号名称及描述由表 1给出。

3 基于历史位置的异常签到检测算法

本节将详细介绍H-Outlier的在线检测算法。为了提升检测效率，首先介绍检测算法采用的几种优化策略，然后给出详细的检测算法。

3.1 优化策略

若两个签到位置之间距离小于给定距离阈值d，称它们互为邻居点。

1) 签到位置的状态

传统检测方法仅将用户的签到位置分为正常和异常两种状态，而通过在滑动窗口下用户签到位置的检测发现，签到位置的状态可进一步细分，以便减少距离计算。在滑动窗口W中签到位置p的状态可分为：①确定的正常点。如果p在W中邻居数量大于等于k，并且在p点之后邻居数量也大于等于k，这时不管W如何滑动，位置p在滑出窗口之前，在窗口内邻居数量一定大于等于k个，因此，此时p的状态可以认定为确定的正常签到点，记为safe-inlier。②不确定的正常点。如果p在W中邻居数量大于等于k，但是在p点之后邻居数量小于k，这时p虽然是一个正常状态的签到位置，但是当W滑动时，在位置p之前的邻居可能会滑出窗口，p的状态可能会变成异常状态，此时的p可认为是一个不确定的正常点，记为unsafe-inlier。③确定的异常点。设签到位置p之前的邻居集合为p.Nei_before，之后的邻居集合为p.Nei_after，如果p在W中邻居数量小于k，在p之前有m_before个位置，如果|p.Nei_after|小于k-m_before，这时不管W如何滑动，位置p在滑出窗口之前，都不可能包括k个邻居，因此，此时p的状态可以认定为确定的异常签到点，记为safe-outlier。④异常点。剩下的异常签到点都划归为这一类，记为outlier。

很明显，一旦确定safe-inlier和safe-outlier状态之后不必再对这些签到位置进行重新检测。而随着窗口滑动，outlier和unsafe-inlier仍需重新检测状态。

2) 优化的邻居点搜索机制

根据上述签到位置的状态划分方法，我们将签到位置的邻居点分为在p签到之前和在p签到之后两个部分，以便快速确定签到位置的状态。若|p.Nei_after| ≥k，p为safe-inlier；若|p.Nei_after| < k，但|p.Nei_before |+|p.Nei_after| ≥ k，p为unsafe-inlier；若|p.Nei_before| + |p.Nei_after| < k，并且|p.Nei_after| < k-m_before，p为safe-outlier；其他情况下，p为outlier。

通过观察发现，随着滑动窗口的滑动，对于签到位置p的所有邻居点p.Nei_before和p.Nei_after，p.Nei_before中的位置点不断滑出窗口，而p.Nei_after则一直处在窗口内，直到p也滑出窗口才会失效。因此，在搜索p的邻居时可优先搜索在其之后的邻居，越靠后的邻居有效期越长；而在其之前的邻居，越靠近p存活期越长。基于该观察，在滑动窗口内从最后一个签到位置向前依次搜索邻居，满足优先搜索Nei_after，又实现了从最近到最远搜索Nei_before。

3) 最少邻居点搜索机制

若查找出签到位置p的所有邻居，需扫描一遍窗口。受文献[14]启发，在检测点p时，并不需要搜索出所有邻居，当满足k个时，即可判定位置p的状态，但是同时为了结合上述的优化策略1)和2)，我们给出最少邻居点搜索机制。

给定签到位置p和新签到位置p_new，若|p.Nei_after|≥ k同时|p_new.Nei_before| ≥k，则无需计算p与p_new的距离。此时位置p已经确定为safe-inlier，而p_new也已确定为unsafe-inlier。否则，将继续计算p_new到所有之前签到位置的距离，以确定p_new为outlier。采用该机制，既满足了所有签到位置状态的检测又实现了最少的距离计算。

3.2 H-Outlier在线检测算法

算法1给出了H-Outlier的优化检测算法，对于新签到位置p_new，对窗口W中所有签到位置进行状态重新检测。首先，按照优化的邻居搜索机制，从窗口内最后一个位置，依次向前搜索邻居，如第1行所示。然后，采用最少邻居点搜索机制，判定位置p_i和p_new是否都已确定状态，若已确定，则不用再继续搜索邻居2)~4)行，否则，继续计算距离，更新邻居集合(见5)~7))。如果p_i的状态不是safe-inlier或safe-outlier，则根据搜索邻居情况更新其状态，如8)~17)所示。如果p_new搜索到k个在其之前的邻居，状态更新为unsafe-inlier(见18)~19))，检测完窗口W后，若邻居数量依然少于k个，状态标记为outlier。

算法1  H-Outlier优化检测算法

输入 当前窗口W，k，d，p_new；

输出  所有p∈W的状态。

1) for i从W_end到W_start do

2) if p_i.sta是safe-inlier或者p_i.sta是safe-outlier

3) if p_new.sta是unsafe-inlier then

4) 继续

5) else if p_i与p_new的距离≤d then

6) 将p_i添加到p_new.Nei_before

7) 将p_new添加到p_i.Nei_after

8) else

9) if p_i与p_new的距离≤d then

10)将p_i添加到p_new.Nei_before

11)将p_new添加到p_i.Nei_after

12) if |p_i.Nei_after|≥k then

13)p_i.status更新为safe-inlier

14)else if |p_i.Nei_before|+|p_i.Nei_after|≥k then

15)p_i.status更新为unsafe-inlier

16)else if |p_i.Nei_before| < k-m_before then

17)p_i.status更新为safe-inlier

18)if |p_new.Nei_before| ≥k then

19)p_new.status更新为unsafe-inlier

20) if |p_new.Nei_before| < k then

21)p_new.status更新为outlier

4 基于好友圈的异常检测算法

本节将详细介绍基于好友圈的异常签到F-Outlier的检测算法。F-Outlier定义在H-Outlier之上，对于当前窗口W上H-Outlier需进一步验证是否为F-Outlier。H-Outlier仅在用户自身近期的历史签到位置上查找邻居点(滑动窗口W内)，而F-Outlier则在其好友圈用户的最近签到位置中搜索邻居点(△t时间差内)。

为了进一步降低F-Outlier检测的时间消耗，本节同样给出了3个优化策略。

1) 最少好友搜索机制

与H-Outlier检测的最少邻居点搜索机制相似，检测用户u_i签到位置p_aⁱ的状态时，并非需要完整搜索一遍Net(u_i)，若已存在k_f个好友在t内在同一地点(小于给定距离d)签到过，则可以停止搜索，此时可判定p_aⁱ并非F-Outlier。

2) 历史邻近好友优先原则

在社会学领域研究中发现，人们在某一段时间内往往与相同一群人存在较密集的交互^[4]。根据上述社会学的发现，我们对每个用户维护一个邻近好友的排序列表L_f，用于记录历史邻近签到状况，最近一次的邻近签到好友排在首位，每次搜索邻近好友时同时更新列表次序可以较大概率快速搜索邻近的签到好友，以排除H-Outlier，而不用随机遍历Net(u_i)。

3) 基于时间触发的检测机制

当签到位置p_aⁱ在当前时刻检测为F-Outlier后，在后续的Δt内需要不断重新检测它的状态是否有变化，但是当好友圈用户没有签到数据更新时，重新检测会导致冗余计算。因此，提出了一种基于时间触发的检测机制。

每个用户u维护一个触发列表trigger，触发列表中每项表示为〈p_aⁱ〉，当用户u更新签到数据时，触发对p_aⁱ的F-Outlier状态重检测。可以看出，每个触发项都存在一个有效期，即|t_c-t_a|≤Δt，当前时间t_c与Δt_a的时间差不大于Δt，超过该时间差，触发项自动失效。

基于时间触发的检测机制将连续异常检测转化成了基于触发的检测，当有新签到数据时，才对未过期的签到位置进行重新检测，大大减少了额外的周期性重新检测成本。

算法2描述了采用优化策略的F-Outlier的检测过程，针对用户u_i的新签到位置p_cⁱ，首先执行H-Outlier检测，如1)所示，如果p_cⁱ是一个H-Outlier，则继续检测p_cⁱ是否为F-Outlier，如2)~12)所示。根据历史邻近好友优先原则，从L_f中由前向后搜索好友，若存在邻近签到的好友，则插入好友邻居集合Nei_fri，并将该好友放置于L_f首位(见4)~7))，然后根据最少好友搜索机制，满足k_f个好友，停止搜索(见8)~9))。搜索完一遍u_i好友圈之后，认为满足k_f条件，则认定为F-Outlier，并将放入好友圈Net(u_i)中每个用户的trigger列表中，如10)~12)所示。

算法2  F-Outlier检测算法

输入  新的签到p_cⁱ、k_f、d；

输出  所有的F-Outlier。

1) 对于状态为H-Outlier的p_cⁱ

2) if p_cⁱ.sta为outlier then

3) for j取值1，2，…，|Net(u_i)| do

4) L_f获取j后给u_j

5) if p_cⁱ与p_c±△tⁱ的距离≤d then

6) 将p_c±△tⁱ添加到p_cⁱ.Nei_fri

7) 将u_j插入到L_f首位

8) if |p_cⁱ.Nei_fri|≥k_f then

9) p_cⁱ.sta更新为F-Inlier、break

10)if |p_cⁱ.Nei_fri| < k_f then

11) p_cⁱ.sta更新为F-Outlier

12)将p_cⁱ添加到Nei(u_i).trigger

13) u_i.trigger更新到Trigger

14)for每个p_aⁱ∈Trigger do

15)if |t_a-t_c|≤△t并且p_cⁱ与p_a^j的距离≤d then

16)将p_cⁱ添加到p_aⁱ.Nei_fri

17)if |p_aⁱ.Neifri|≥k_f then

18) p_aⁱ.sta更新为F-Inlier

19)将p_aⁱ从u_j.trigger中删除

接下来，就要触发u_i的trigger列表，如13)~19)所示。每个触发项p_a^j，若仍在有效期内，且与p_cⁱ为邻居，则判断它邻居点的数量是否满足k_f，若满足，则更新p_a^j的状态，并将其移出u_i的trigger列表(见17)~19))。

5 实验评估

实验平台配置为4.0 GHz i7-6700k处理器，8 GB内存，Windows7操作系统，所有算法由Java实现。

数据集。实验数据集采用的是基于位置的移动社交网络Gowalla真实数据集^[18]。数据集中包括了195 591个用户，95万条好友关系，收集了2009年2月~2010年10月之间的644万个签到位置数据。

对比方法。算法1描述的基于历史位置的异常检测算法记为H-Opt算法，算法2描述的基于好友圈的异常检测算法记为F-Opt算法，对比方法记为LUE(lazy with update events)算法^[13]。

评估方法。采用所有用户在单个窗口内异常率来评估所提方法的有效性。实验结果取所有滑动窗口下的平均值。对于效率评估，通过变化各重要参数，采用单个窗口平均消耗的CPU时间和内存占用来评估算法的性能。每次窗口滑动一个新签到位置。

5.1 有效性评估

首先，对H-Opt和F-Opt算法的有效性进行了评估与分析。默认参数设置：d=300 m，w= 20，k=4，k_f=3，Δt=3 h，m=4。H-Opt与F-Opt的异常检测结果如图 1所示。图 1(a)描述的是变化参数k对不同算法的有效性影响。可以发现，随着k的增加，H-Opt和F-Opt检测出的异常率都呈线性增加，这是因为增加邻居点数量阈值k会使较多的签到点被认定为H-Outlier。由于F-Outlier基于H-Outlier，随着H-Outlier数量的增加，F-Outlier也会有所上升，这与它们定义相符。同时还可以发现，随着k的增加，F-Opt算法与H-Opt算法在异常率检测上的差异不断增大，即F-Opt的异常误判率不断降低。当k=7时，降低的异常率已达到1.09%，也就是说，F-Outlier有效排除了30.27%的伪异常。

图 1(b)显示的是变化参数W对不同算法的有效性影响。由图 1可以看出，随着W的增大，异常率不断下降。这是因为当增大W时，邻居点的历史签到时间范围也随之增加，从而签到的邻居点数量也会相应增加，使H-Outlier和F-Outlier的异常率随之减少，这也与它们定义相符。同时可以看出，F-Opt的异常率明显低于H-Opt算法，这也证明了F-Outlier检测的有效性。

为了更好地考察F-Opt算法的有效性，进一步对F-Opt算法进行了评估。图 2是k_f、Δt和m在不同组合时，F-Outlier相比H-Outlier降低的异常率情况。如图 2(a)所示，当k_f值从2变化到6时，考虑间接好友的F-Outlier进一步降低了H-Outlier的异常率。共同好友的要求越低(m值越小)，异常的降低率越高，即伪异常越少，当m=2时，相对仅考虑直接好友，F-Outlier异常的降低率平均提高了8%。图 2(b)展示的是当k_f=4时，Δt从1~5变化，对算法异常降低率的影响。可以发现，随着Δt的增加，异常的降低率在不断增大，这是因为搜索的时间区间增加，在时间区间内邻近签到好友的数量也在增加。同样地，考虑好友圈的F-Outlier减少了更多伪异常。在Δt≤4时，F-Outlier减少的异常率变化不大，这也说明大多邻近好友的签到是在较短时间差内完成。

5.2 效率评估

本节评估了滑动窗口W和邻居点数量k对H-Opt和F-Opt算法的消耗时间和内存的影响，并与LUE算法进行了对比分析。默认参数：d=300，k_f=3，Δt=3 h，m=4。

在图 3(a)中，固定k=4，W从10变化到30，随着W的增加，3个算法消耗的时间都有所增加，这是因为窗口增加，都需要增加对异常点邻居搜索范围，而LUE需要计算当前签到点与窗口内所有签到点的距离，所以导致了耗时较长。同时，随着窗口增长，H-Outlier和F-Outlier数量反而越少，虽然搜索邻居的范围增加导致了总消耗时间增加，但是由于采用了优化的邻居搜索机制和最少邻居搜索机制，仅有异常点增加了邻居搜索，因此，消耗的CPU时间增长越来越缓慢，而F-Opt算法需要再次检测的异常点变少也使得消耗的时间越来越少。相比于LUE，F-Opt和H-Opt分别平均提升了2.34、2.45倍效率。在图 3(b)中固定W=20，k从2变化到6。随着k的增加，3个算法消耗的CPU时间也逐渐增加。虽然F-Opt算法需要重新检测更多H-Outlier异常，但F-Opt算法并没有快速增加时间消耗，仅平均增加了0.002 ms。这也体现了我们提出的基于触发的优化检测策略的作用。相比于LUE，F-Opt和H-Opt分别平均提升了2.31、2.36倍效率。

在内存方面，如图 4所示，随着W的增加，3个算法消耗的内存也逐渐增加。这是因为随着滑动窗口的增长，窗口内存储的签到点也随之增多。LUE算法需要储存窗口存储所有签到点的邻居点，消耗的内存较多。H-Opt和F-Opt消耗内存较少，这是因为采用了优化的邻居搜索机制和最少邻居搜索机制。由于增加了F-Outlier好友圈的邻近签到存储，F-Opt略高于H-Opt。

随着k的增加，3个算法消耗的内存也在增加。这是因为所有算法都需要寻找更多的邻居。H-Opt和F-Opt消耗内存增长缓慢，这是因为H-Opt算法采用最少邻居点搜索机制，随着k值的增加，在H-Opt算法中需要存储的自身签到点也随之增加。相比于LUE，F-Opt和H-Opt分别平均减少了30%和32%的内存消耗。

接下来，进一步评估了参数m、k_f和Δt对F-Opt算法效率的影响。我们测试了变化k_f和Δt对多个m值下F-Opt算法效率的影响，如图 5所示。固定W=20，k=4，d=300，在图 5(a)中固定Δt=3 h，在图 5 (b)中固定k_f=3，可以看出，随着k_f和Δt增加，F-Opt消耗的CPU时间都逐渐增加。这是因为k_f增加，使得邻近签到好友搜索的个数增加；Δt增加使得时间区间增加。因此消耗的CPU时间也要相应增加。同时也发现，不考虑间接好友时的F-Opt算法消耗最多时间，考虑间接好友时共同好友数量m值越少，使用的检测时间越少。这是因为m值越小，Net(u)集合越大，虽然搜索范围增加了，伪异常也增多了，由于我们采用了历史邻近好友优先原则和基于触发的检测机制，可快速发现伪异常，有效提升了算法检测效率。结合图 2的实验结果可以说明, 在移动社交网络异常签到检测中考虑用户间接好友的必要性和优势。

6 结束语

本文提出了一种针对移动社交网络异常签到位置的在线检测方法。基于距离的异常检测，定义了基于历史位置和基于好友圈的两种异常签到模型。然后，针对两种异常签到模型，分别提出了优化的检测算法，从签到位置的状态模型、优化的邻居搜索机制和基于时间触发的检测机制方面有效降低了检测时间。最后，在真实的移动社交网络用户签到数据集上，验证了所提模型与算法的有效性和效率。下一步将结合用户的操作行为进一步研究有效的移动社交网络异常检测方法。