.754. 智能系统学报 第12卷 P∈W}|≤k,则称签到位置p是一个基于历史位 和异常两种状态，而通过在滑动窗口下用户签到位 置的异常签到点，记为H-Outlier。 置的检测发现，签到位置的状态可进一步细分，以 从定义2可以看出，H-Outlier是基于自身历史 便减少距离计算。在滑动窗口W中签到位置p的 签到位置的，这也是因为用户日常活动轨迹记录往 状态可分为：①确定的正常点。如果p在W中邻居 往具有周期性[18劉 数量大于等于k,并且在P点之后邻居数量也大于 设F(u:)表示用户，的所有直接好友集合。 等于k,这时不管W如何滑动，位置p在滑出窗口之 与QQ、微信等社交网络的好友圈的定义不同，这里 前，在窗口内邻居数量一定大于等于k个，因此，此 给出的好友圈定义既包括用户“：直接好友又包括与 时p的状态可以认定为确定的正常签到点，记为 u,有一定数量共同好友的间接好友。 safe-inlier。②不确定的正常点。如果p在W中邻 定义3好友圈。给定支持阈值m,用户u的好 居数量大于等于k,但是在P点之后邻居数量小于 友圈包括u,的所有直接好友和与u,存在至少m个共 k,这时p虽然是一个正常状态的签到位置，但是当 同直接好友的间接好友，即(4：)U W滑动时，在位置p之前的邻居可能会滑出窗口，P {4Fr(u:)∩Fr(4)|≥m},简记为Net(u:)。 的状态可能会变成异常状态，此时的p可认为是一 定义4基于好友圈的异常签到。给定距离阈 个不确定的正常点，记为unsafe-.inlier。③确定的异 值d、好友圈包含的好友数量阈值k、时间△t,对于 常点。设签到位置p之前的邻居集合为p.Neipelore, 基于历史位置的异常签到点p。,如果|{“，|3p, 之后的邻居集合为p.Neie,如果p在W中邻居数量 dist(pi,pa)≤d,lta-tl≤△t,u,∈Net(u:)}|≤ 小于k,在p之前有mor个位置，如果lp.Nei|小 k,P。是一个基于好友圈的异常签到点，记为F 于k-mo,这时不管W如何滑动，位置p在滑出窗 Outlier 口之前，都不可能包括k个邻居，因此，此时p的状 根据定义4可知，F-Outlier是在H-Outlier定义 态可以认定为确定的异常签到点，记为safe-outlier。 的基础上定义的，因此，F-Outlier集合是H-Outlier ④异常点。剩下的异常签到点都划归为这一类，记 集合的子集。 为outlier。 文中涉及的符号名称及描述由表1给出。 很明显，一旦确定safe-inlier和safe-outlier状态 表1符号名称及描述 之后不必再对这些签到位置进行重新检测。而随 Table 1 Symbols and its descriptions 着窗口滑动，outlier和unsafe-inlier仍需重新检测 名称 解释 状态。 p 用户u,在1，时间的签到位置 2)优化的邻居点搜索机制 W 基于签到位置数量的滑动窗口 根据上述签到位置的状态划分方法，我们将签 心 距离阈值 邻居点数量阈值 到位置的邻居点分为在p签到之前和在p签到之后 k Fr(u） 用户u的直接好友集合 两个部分，以便快速确定签到位置的状态。若 m 共同直接好友数量阈值 p.Neir|≥k,p为safe-inlier;若lp.Nei|<k,但 Net(u) 用户u,的好友圈 lp.Neibefare|+|p.Nei|≥k,p为unsafe-.inlier;若 p.Neie 签到位置p之前的邻居集合 p.Neie 签到位置p之后的邻居集合 p.Neitor+p.Neiner,p.Neier<-m k 好友圈中邻居点数量國值 p为safe-outlier;其他情况下，p为outlier。 0 签到位置数据流 通过观察发现，随着滑动窗口的滑动，对于签 △t 触发项的有效期 到位置p的所有邻居点p.Neipefare和p.Nei, 3 基于历史位置的异常签到检测算法 p.Nei中的位置点不断滑出窗口，而p.Neie则 直处在窗口内，直到p也滑出窗口才会失效。因此， 本节将详细介绍H-Outlier的在线检测算法。 在搜索p的邻居时可优先搜索在其之后的邻居，越 为了提升检测效率，首先介绍检测算法采用的几种 靠后的邻居有效期越长：而在其之前的邻居，越靠 优化策略，然后给出详细的检测算法。 近P存活期越长。基于该观察，在滑动窗口内从最 3.1优化策略 后一个签到位置向前依次搜索邻居，满足优先搜索 若两个签到位置之间距离小于给定距离阈值 Nei,又实现了从最近到最远搜索Neiw。 d,称它们互为邻居点。 3)最少邻居点搜索机制 1)签到位置的状态 若查找出签到位置p的所有邻居，需扫描一遍 传统检测方法仅将用户的签到位置分为正常 窗口。受文献[14]启发，在检测点p时，并不需要ｐ ｉ ｊ ∈ Ｗ｝ ≤ｋ， 则称签到位置 ｐ ｉ ｂ 是一个基于历史位 置的异常签到点，记为Ｈ⁃Ｏｕｔｌｉｅｒ。 从定义 ２ 可以看出，Ｈ⁃Ｏｕｔｌｉｅｒ 是基于自身历史 签到位置的，这也是因为用户日常活动轨迹记录往 往具有周期性［１８］ 。 设 Ｆｒ （ ｕｉ ） 表示用户 ｕｉ 的所有直接好友集合。 与 ＱＱ、微信等社交网络的好友圈的定义不同，这里 给出的好友圈定义既包括用户 ｕｉ直接好友又包括与 ｕｉ有一定数量共同好友的间接好友。 定义 ３ 好友圈。 给定支持阈值 ｍ，用户ｕｉ的好 友圈包括ｕｉ的所有直接好友和与ｕｉ存在至少 ｍ 个共 同 直 接 好 友 的 间 接 好 友， 即 Ｆｒ （ ｕｉ ） ∪ {ｕｊ Ｆｒ（ｕｉ）∩Ｆｒ（ｕｊ） ≥ｍ} ，简记为 Ｎｅｔ（ｕｉ）。 定义 ４ 基于好友圈的异常签到。 给定距离阈 值 ｄ、好友圈包含的好友数量阈值 ｋｆ、时间 △ｔ ，对于 基于历史位置的异常签到点 ｐ ｉ ａ ，如果 ｛ｕｓ ∃ｐ ｓ ｊ ， ｄｉｓｔ（ｐ ｓ ｊ ，ｐ ｉ ａ ） ≤ ｄ， ｔ ａ － ｔ ｊ ≤ △ｔ，ｕｓ ∈ Ｎｅｔ（ｕｉ）｝ ≤ ｋｆ，ｐ ｉ ａ 是一个基于好友圈的异常签到点， 记为 Ｆ⁃ Ｏｕｔｌｉｅｒ。 根据定义 ４ 可知，Ｆ⁃Ｏｕｔｌｉｅｒ 是在 Ｈ⁃Ｏｕｔｌｉｅｒ 定义 的基础上定义的，因此，Ｆ⁃Ｏｕｔｌｉｅｒ 集合是 Ｈ⁃Ｏｕｔｌｉｅｒ 集合的子集。 文中涉及的符号名称及描述由表 １ 给出。 表 １ 符号名称及描述 Ｔａｂｌｅ １ Ｓｙｍｂｏｌｓ ａｎｄ ｉｔｓ ｄｅｓｃｒｉｐｔｉｏｎｓ 名称 解释 ｐ ｉ ｊ 用户ｕｉ在ｔ ｊ时间的签到位置 Ｗ 基于签到位置数量的滑动窗口 ｄ 距离阈值 ｋ 邻居点数量阈值 Ｆｒ（ｕｉ） 用户ｕｉ的直接好友集合 ｍ 共同直接好友数量阈值 Ｎｅｔ（ｕｉ） 用户ｕｉ的好友圈 ｐ．Ｎｅｉ ｂｅｆｏｒｅ 签到位置 ｐ 之前的邻居集合 ｐ．Ｎｅｉ ａｆｔｅｒ 签到位置 ｐ 之后的邻居集合 ｋｆ 好友圈中邻居点数量阈值 Ｄ 签到位置数据流 △ｔ 触发项的有效期 ３ 基于历史位置的异常签到检测算法 本节将详细介绍 Ｈ⁃Ｏｕｔｌｉｅｒ 的在线检测算法。 为了提升检测效率，首先介绍检测算法采用的几种 优化策略，然后给出详细的检测算法。 ３．１ 优化策略 若两个签到位置之间距离小于给定距离阈值 ｄ，称它们互为邻居点。 １）签到位置的状态 传统检测方法仅将用户的签到位置分为正常 和异常两种状态，而通过在滑动窗口下用户签到位 置的检测发现，签到位置的状态可进一步细分，以 便减少距离计算。 在滑动窗口 Ｗ 中签到位置 ｐ 的 状态可分为：①确定的正常点。 如果 ｐ 在 Ｗ 中邻居 数量大于等于 ｋ，并且在 ｐ 点之后邻居数量也大于 等于 ｋ，这时不管 Ｗ 如何滑动，位置 ｐ 在滑出窗口之 前，在窗口内邻居数量一定大于等于 ｋ 个，因此，此 时 ｐ 的状态可以认定为确定的正常签到点，记为 ｓａｆｅ⁃ｉｎｌｉｅｒ。 ②不确定的正常点。 如果 ｐ 在 Ｗ 中邻 居数量大于等于 ｋ，但是在 ｐ 点之后邻居数量小于 ｋ，这时 ｐ 虽然是一个正常状态的签到位置，但是当 Ｗ 滑动时，在位置 ｐ 之前的邻居可能会滑出窗口，ｐ 的状态可能会变成异常状态，此时的 ｐ 可认为是一 个不确定的正常点，记为 ｕｎｓａｆｅ⁃ｉｎｌｉｅｒ。 ③确定的异 常点。 设签到位置 ｐ 之前的邻居集合为ｐ．Ｎｅｉ ｂｅｆｏｒｅ， 之后的邻居集合为ｐ．Ｎｅｉ ａｆｔｅｒ，如果 ｐ 在 Ｗ 中邻居数量 小于 ｋ，在 ｐ 之前有 ｍｂｅｆｏｒｅ个位置，如果 ｐ．Ｎｅｉ ａｆｔｅｒ 小 于 ｋ⁃ｍｂｅｆｏｒｅ，这时不管 Ｗ 如何滑动，位置 ｐ 在滑出窗 口之前，都不可能包括 ｋ 个邻居，因此，此时 ｐ 的状 态可以认定为确定的异常签到点，记为 ｓａｆｅ⁃ｏｕｔｌｉｅｒ。 ④异常点。 剩下的异常签到点都划归为这一类，记 为 ｏｕｔｌｉｅｒ。 很明显，一旦确定 ｓａｆｅ⁃ｉｎｌｉｅｒ 和 ｓａｆｅ⁃ｏｕｔｌｉｅｒ 状态 之后不必再对这些签到位置进行重新检测。 而随 着窗口滑动， ｏｕｔｌｉｅｒ 和 ｕｎｓａｆｅ⁃ｉｎｌｉｅｒ 仍需重新检测 状态。 ２）优化的邻居点搜索机制 根据上述签到位置的状态划分方法，我们将签 到位置的邻居点分为在 ｐ 签到之前和在 ｐ 签到之后 两个 部 分， 以 便 快 速 确 定 签 到 位 置 的 状 态。 若 ｐ．Ｎｅｉ ａｆｔｅｒ ≥ｋ，ｐ 为 ｓａｆｅ⁃ｉｎｌｉｅｒ；若 ｐ．Ｎｅｉ ａｆｔｅｒ ＜ ｋ，但 ｐ．Ｎｅｉ ｂｅｆｏｒｅ ＋ ｐ．Ｎｅｉ ａｆｔｅｒ ≥ ｋ， ｐ 为 ｕｎｓａｆｅ⁃ｉｎｌｉｅｒ；若 ｐ．Ｎｅｉ ｂｅｆｏｒｅ ＋ ｐ．Ｎｅｉ ａｆｔｅｒ ＜ｋ，并且 ｐ．Ｎｅｉ ａｆｔｅｒ ＜ｋ⁃ｍｂｅｆｏｒｅ， ｐ 为 ｓａｆｅ⁃ｏｕｔｌｉｅｒ；其他情况下，ｐ 为 ｏｕｔｌｉｅｒ。 通过观察发现，随着滑动窗口的滑动，对于签 到位 置 ｐ 的 所 有 邻 居 点 ｐ． Ｎｅｉ ｂｅｆｏｒｅ 和 ｐ． Ｎｅｉ ａｆｔｅｒ， ｐ．Ｎｅｉ ｂｅｆｏｒｅ中的位置点不断滑出窗口，而 ｐ．Ｎｅｉ ａｆｔｅｒ则一 直处在窗口内，直到 ｐ 也滑出窗口才会失效。 因此， 在搜索 ｐ 的邻居时可优先搜索在其之后的邻居，越 靠后的邻居有效期越长；而在其之前的邻居，越靠 近 ｐ 存活期越长。 基于该观察，在滑动窗口内从最 后一个签到位置向前依次搜索邻居，满足优先搜索 Ｎｅｉ ａｆｔｅｒ，又实现了从最近到最远搜索 Ｎｅｉ ｂｅｆｏｒｅ。 ３） 最少邻居点搜索机制 若查找出签到位置 ｐ 的所有邻居，需扫描一遍 窗口。 受文献［１４］ 启发，在检测点 ｐ 时，并不需要 ·７５４· 智 能 系 统 学 报 第 １２ 卷