第5期 赵冠哲，等：移动社交网络异常签到在线检测算法 ·757. 图1(b)显示的是变化参数W对不同算法的有 5.2效率评估 效性影响。由图1可以看出，随着W的增大，异常 本节评估了滑动窗口W和邻居点数量k对H 率不断下降。这是因为当增大W时，邻居点的历史 Opt和F-Opt算法的消耗时间和内存的影响，并与 签到时间范围也随之增加，从而签到的邻居点数量 LUE算法进行了对比分析。默认参数：d=300,k= 也会相应增加，使H-Outlier和F-Outlier的异常率随 3,△t=3h,m=4。 之减少，这也与它们定义相符。同时可以看出，F 在图3(a)中，固定k=4,W从10变化到30，随 Opt的异常率明显低于H-Opt算法，这也证明了F- 着W的增加，3个算法消耗的时间都有所增加，这是 Outlier检测的有效性。 因为窗口增加，都需要增加对异常点邻居搜索范 为了更好地考察F-Opt算法的有效性，进一步 围，而LUE需要计算当前签到点与窗口内所有签到 对F-Opt算法进行了评估。图2是k、△t和m在不 点的距离，所以导致了耗时较长。同时，随着窗口 同组合时，F-Outlier相比H-Outlier降低的异常率情 增长，H-Outlier和F-Outlier数量反而越少，虽然搜 况。如图2(a)所示，当k,值从2变化到6时，考虑 索邻居的范围增加导致了总消耗时间增加，但是由 间接好友的F-Outlier进一步降低了H-Outlier的异 于采用了优化的邻居搜索机制和最少邻居搜索机 常率。共同好友的要求越低(m值越小)，异常的降 制，仅有异常点增加了邻据搜索，因此，消耗的CPU时间 低率越高，即伪异常越少，当m=2时，相对仅考虑 增长越来越缓慢，而F-Opt算法需要再次检测的异常点 直接好友，F-0 utlier异常的降低率平均提高了8%。 图2(b)展示的是当k,=4时，△1从1~5变化，对算 变少也使得消耗的时间越来越少。相比于LUE,F-Op 和H-0pt分别平均提升了2.342.45倍效率。在图3(b) 法异常降低率的影响。可以发现，随着△：的增加， 异常的降低率在不断增大，这是因为搜索的时间区 中固定W=20,k从2变化到6。随着k的增加，3个 间增加，在时间区间内邻近签到好友的数量也在增 算法消耗的CPU时间也逐渐增加。虽然F-Opt算 加。同样地，考虑好友圈的F-Outlier减少了更多伪 法需要重新检测更多H-Outlier异常，但F-Opt算法 异常。在△t≤4时，F-Outlier减少的异常率变化不 并没有快速增加时间消耗，仅平均增加了0.002ms。 大，这也说明大多邻近好友的签到是在较短时间差 这也体现了我们提出的基于触发的优化检测策略 内完成。 的作用。相比于LUE,F-Opt和H-Opt分别平均提 升了2.31、2.36倍效率。 30 m=2 -=4 0.20 一无间接好友 0.18 --LUE 26 F-Opt 0.16 --H-Opt 24 0.14 0.12 0.10 20 0.08 2 3 4 5 0.06 △/h 10 15 20 25 30 (a)参数k,m对异常降低率的影响 WI个 (a)参数W对CPU消耗时间的影响 32 550r △-LUE F-Opt 30 +m=4 #-m=6 500 H-Opt 28 ◆无间接好友 450 26 400 24 350f 22 300 20 250 1 200 2 6 M个 个 (b)参数△，m对异常降低率的影响 (b)参数k对CPU消耗时间的影响 图2不同参数对F-Opt异常降低率的影响 图3不同参数下的算法消耗的时间 Fig.2 F-Opt outlier decreasing rate w.r.t.different parameters Fig.3 CPU time w.r.t.different parameters图 １（ｂ）显示的是变化参数 Ｗ 对不同算法的有 效性影响。 由图 １ 可以看出，随着 Ｗ 的增大，异常 率不断下降。 这是因为当增大 Ｗ 时，邻居点的历史 签到时间范围也随之增加，从而签到的邻居点数量 也会相应增加，使 Ｈ⁃Ｏｕｔｌｉｅｒ 和 Ｆ⁃Ｏｕｔｌｉｅｒ 的异常率随 之减少，这也与它们定义相符。 同时可以看出，Ｆ⁃ Ｏｐｔ 的异常率明显低于 Ｈ⁃Ｏｐｔ 算法，这也证明了 Ｆ⁃ Ｏｕｔｌｉｅｒ 检测的有效性。 为了更好地考察 Ｆ⁃Ｏｐｔ 算法的有效性，进一步 对 Ｆ⁃Ｏｐｔ 算法进行了评估。 图 ２ 是 ｋｆ、Δｔ 和 ｍ 在不 同组合时，Ｆ⁃Ｏｕｔｌｉｅｒ 相比 Ｈ⁃Ｏｕｔｌｉｅｒ 降低的异常率情 况。 如图 ２（ａ）所示，当 ｋｆ 值从 ２ 变化到 ６ 时，考虑 间接好友的 Ｆ⁃Ｏｕｔｌｉｅｒ 进一步降低了 Ｈ⁃Ｏｕｔｌｉｅｒ 的异 常率。 共同好友的要求越低（ｍ 值越小），异常的降 低率越高，即伪异常越少，当 ｍ ＝ ２ 时，相对仅考虑 直接好友，Ｆ⁃Ｏｕｔｌｉｅｒ 异常的降低率平均提高了 ８％。 图 ２（ｂ）展示的是当 ｋｆ ＝ ４ 时，Δｔ 从 １ ～ ５ 变化，对算 法异常降低率的影响。 可以发现，随着 Δｔ 的增加， 异常的降低率在不断增大，这是因为搜索的时间区 间增加，在时间区间内邻近签到好友的数量也在增 加。 同样地，考虑好友圈的 Ｆ⁃Ｏｕｔｌｉｅｒ 减少了更多伪 异常。 在 Δｔ ≤ ４ 时，Ｆ⁃Ｏｕｔｌｉｅｒ 减少的异常率变化不 大，这也说明大多邻近好友的签到是在较短时间差 内完成。 （ａ）参数 ｋｆ、ｍ 对异常降低率的影响 （ｂ）参数 Δｔ、ｍ 对异常降低率的影响 图 ２ 不同参数对 Ｆ⁃Ｏｐｔ 异常降低率的影响 Ｆｉｇ． ２ Ｆ⁃Ｏｐｔ ｏｕｔｌｉｅｒ ｄｅｃｒｅａｓｉｎｇ ｒａｔｅ ｗ．ｒ．ｔ． ｄｉｆｆｅｒｅｎｔ ｐａｒａｍｅｔｅｒｓ ５．２ 效率评估 本节评估了滑动窗口 Ｗ 和邻居点数量 ｋ 对 Ｈ⁃ Ｏｐｔ 和 Ｆ⁃Ｏｐｔ 算法的消耗时间和内存的影响，并与 ＬＵＥ 算法进行了对比分析。 默认参数：ｄ ＝ ３００，ｋｆ ＝ ３， Δｔ ＝ ３ ｈ，ｍ ＝ ４。 在图 ３（ａ）中，固定 ｋ ＝ ４，Ｗ 从 １０ 变化到 ３０，随 着 Ｗ 的增加，３ 个算法消耗的时间都有所增加，这是 因为窗口增加，都需要增加对异常点邻居搜索范 围，而 ＬＵＥ 需要计算当前签到点与窗口内所有签到 点的距离，所以导致了耗时较长。 同时，随着窗口 增长，Ｈ⁃Ｏｕｔｌｉｅｒ 和 Ｆ⁃Ｏｕｔｌｉｅｒ 数量反而越少，虽然搜 索邻居的范围增加导致了总消耗时间增加，但是由 于采用了优化的邻居搜索机制和最少邻居搜索机 制，仅有异常点增加了邻居搜索，因此，消耗的 ＣＰＵ 时间 增长越来越缓慢，而 Ｆ⁃Ｏｐｔ 算法需要再次检测的异常点 变少也使得消耗的时间越来越少。 相比于 ＬＵＥ，Ｆ⁃Ｏｐｔ 和Ｈ⁃Ｏｐｔ 分别平均提升了２．３４、２．４５ 倍效率。 在图 ３（ｂ） 中固定 Ｗ＝ ２０，ｋ 从 ２ 变化到 ６。 随着 ｋ 的增加，３ 个 算法消耗的 ＣＰＵ 时间也逐渐增加。 虽然 Ｆ⁃Ｏｐｔ 算 法需要重新检测更多 Ｈ⁃Ｏｕｔｌｉｅｒ 异常，但 Ｆ⁃Ｏｐｔ 算法 并没有快速增加时间消耗，仅平均增加了 ０．００２ ｍｓ。 这也体现了我们提出的基于触发的优化检测策略 的作用。 相比于 ＬＵＥ，Ｆ⁃Ｏｐｔ 和 Ｈ⁃Ｏｐｔ 分别平均提 升了 ２．３１、２．３６ 倍效率。 （ａ）参数 Ｗ 对 ＣＰＵ 消耗时间的影响 （ｂ）参数 ｋ 对 ＣＰＵ 消耗时间的影响 图 ３ 不同参数下的算法消耗的时间 Ｆｉｇ．３ ＣＰＵ ｔｉｍｅ ｗ．ｒ．ｔ． ｄｉｆｆｅｒｅｎｔ ｐａｒａｍｅｔｅｒｓ 第 ５ 期 赵冠哲，等：移动社交网络异常签到在线检测算法 ·７５７·