·758· 智能系统学报 第12卷 在内存方面，如图4所示，随着W的增加，3个 0.10r 。无间接好友 算法消耗的内存也逐渐增加。这是因为随着滑动 ◆-m-6 0.09 窗口的增长，窗口内存储的签到点也随之增多。 LUE算法需要储存窗口存储所有签到点的邻居点， 0.08 消耗的内存较多。H-Opt和F-Opt消耗内存较少，这 0.07 是因为采用了优化的邻居搜索机制和最少邻居搜 0.061 索机制。由于增加了F-Outlier好友圈的邻近签到 存储，F-Opt略高于H-Opt。 0.05 k,/个 0.24f -LUE 0.22 F-Opt (a)参数k,和m 0.20 -H-Opt 018 0.10m 6-无间接好友 +m=6 0.14 0.09 "-m=4 012 4-m=2 0.10 0.08 0.08 0.06 0.07 材个 0.06 图4参数W和k变化下内存的消耗情况 0.05 Fig.4 Memory w.r.t.parameter W and k 3 4 △h 随着k的增加，3个算法消耗的内存也在增加。 (b)参数△和m 这是因为所有算法都需要寻找更多的邻居。H-Opl 图5不同参数变化的算法CPU时间 和F-Opt消耗内存增长缓慢，这是因为H-Opt算法 Fig.5 CPU time w.r.t.different parameters 采用最少邻居点搜索机制，随着k值的增加，在H- Opt算法中需要存储的自身签到点也随之增加。相 6 结束语 比于LUE,F-Opt和H-0pt分别平均减少了30%和 本文提出了一种针对移动社交网络异常签到 32%的内存消耗。 位置的在线检测方法。基于距离的异常检测，定义 接下来，进一步评估了参数m、k和△t对F-Opt 了基于历史位置和基于好友圈的两种异常签到模 算法效率的影响。我们测试了变化k和△1对多个 型。然后，针对两种异常签到模型，分别提出了优 m值下F-Opt算法效率的影响，如图5所示。固定 化的检测算法，从签到位置的状态模型、优化的邻 W=20,k=4,d=300,在图5(a)中固定△t=3h,在 居搜索机制和基于时间触发的检测机制方面有效 图5(b)中固定k=3,可以看出，随着k,和△1增加， 降低了检测时间。最后，在真实的移动社交网络用 F-Opt消耗的CPU时间都逐渐增加。这是因为k 户签到数据集上，验证了所提模型与算法的有效性 增加，使得邻近签到好友搜索的个数增加：△1增加 和效率。下一步将结合用户的操作行为进一步研 使得时间区间增加。因此消耗的CPU时间也要相 究有效的移动社交网络异常检测方法。 应增加。同时也发现，不考虑间接好友时的F-Opt 参考文献： 算法消耗最多时间，考虑间接好友时共同好友数量 [1]於志文，周兴社，郭斌.移动社交网络中的感知计算模 m值越少，使用的检测时间越少。这是因为m值越 型、平台与实践[J].中国计算机学会通讯，2012,8(5)： 小，Nt(u)集合越大，虽然搜索范围增加了，伪异常 15-21. 也增多了，由于我们采用了历史邻近好友优先原则 [2]WE ARE SOCIAL LTD.DIGITAL IN 2016[EB/OL ] 和基于触发的检测机制，可快速发现伪异常，有效 [2017-03-10].http://wearesocial.com/uk/special-reports/ digital-in-2016. 提升了算法检测效率。结合图2的实验结果可以说 [3]ZHENG Yu,XIE X.Location-based social networks: 明，在移动社交网络异常签到检测中考虑用户间接 locations[].Computing with spatial trajectories,2011: 好友的必要性和优势。 277-308.在内存方面，如图 ４ 所示，随着 Ｗ 的增加，３ 个 算法消耗的内存也逐渐增加。 这是因为随着滑动 窗口的增长， 窗口内存储的签到点也随之增多。 ＬＵＥ 算法需要储存窗口存储所有签到点的邻居点， 消耗的内存较多。 Ｈ⁃Ｏｐｔ 和 Ｆ⁃Ｏｐｔ 消耗内存较少，这 是因为采用了优化的邻居搜索机制和最少邻居搜 索机制。 由于增加了 Ｆ⁃Ｏｕｔｌｉｅｒ 好友圈的邻近签到 存储，Ｆ⁃Ｏｐｔ 略高于 Ｈ⁃Ｏｐｔ。 图 ４ 参数 Ｗ 和 ｋ 变化下内存的消耗情况 Ｆｉｇ．４ Ｍｅｍｏｒｙ ｗ．ｒ．ｔ． ｐａｒａｍｅｔｅｒ Ｗ ａｎｄ ｋ 随着 ｋ 的增加，３ 个算法消耗的内存也在增加。 这是因为所有算法都需要寻找更多的邻居。 Ｈ⁃Ｏｐｔ 和 Ｆ⁃Ｏｐｔ 消耗内存增长缓慢，这是因为 Ｈ⁃Ｏｐｔ 算法 采用最少邻居点搜索机制，随着 ｋ 值的增加，在 Ｈ⁃ Ｏｐｔ 算法中需要存储的自身签到点也随之增加。 相 比于 ＬＵＥ，Ｆ⁃Ｏｐｔ 和 Ｈ⁃Ｏｐｔ 分别平均减少了 ３０％和 ３２％的内存消耗。 接下来，进一步评估了参数 ｍ、ｋｆ和 Δｔ 对 Ｆ⁃Ｏｐｔ 算法效率的影响。 我们测试了变化 ｋｆ和 Δｔ 对多个 ｍ 值下 Ｆ⁃Ｏｐｔ 算法效率的影响，如图 ５ 所示。 固定 Ｗ＝ ２０，ｋ ＝ ４，ｄ ＝ ３００，在图 ５（ａ）中固定 Δｔ ＝ ３ ｈ，在 图 ５ （ｂ）中固定 ｋｆ ＝ ３，可以看出，随着 ｋｆ 和 Δｔ 增加， Ｆ⁃Ｏｐｔ 消耗的 ＣＰＵ 时间都逐渐增加。 这是因为 ｋｆ 增加，使得邻近签到好友搜索的个数增加； Δｔ 增加 使得时间区间增加。 因此消耗的 ＣＰＵ 时间也要相 应增加。 同时也发现，不考虑间接好友时的 Ｆ⁃Ｏｐｔ 算法消耗最多时间，考虑间接好友时共同好友数量 ｍ 值越少，使用的检测时间越少。 这是因为 ｍ 值越 小，Ｎｅｔ（ｕ）集合越大，虽然搜索范围增加了，伪异常 也增多了，由于我们采用了历史邻近好友优先原则 和基于触发的检测机制，可快速发现伪异常，有效 提升了算法检测效率。 结合图 ２ 的实验结果可以说 明，在移动社交网络异常签到检测中考虑用户间接 好友的必要性和优势。 （ａ）参数 ｋｆ 和 ｍ （ｂ）参数 Δｔ 和 ｍ 图 ５ 不同参数变化的算法 ＣＰＵ 时间 Ｆｉｇ．５ ＣＰＵ ｔｉｍｅ ｗ．ｒ．ｔ． ｄｉｆｆｅｒｅｎｔ ｐａｒａｍｅｔｅｒｓ ６ 结束语 本文提出了一种针对移动社交网络异常签到 位置的在线检测方法。 基于距离的异常检测，定义 了基于历史位置和基于好友圈的两种异常签到模 型。 然后，针对两种异常签到模型，分别提出了优 化的检测算法，从签到位置的状态模型、优化的邻 居搜索机制和基于时间触发的检测机制方面有效 降低了检测时间。 最后，在真实的移动社交网络用 户签到数据集上，验证了所提模型与算法的有效性 和效率。 下一步将结合用户的操作行为进一步研 究有效的移动社交网络异常检测方法。 参考文献： ［１］於志文， 周兴社， 郭斌． 移动社交网络中的感知计算模 型、平台与实践［Ｊ］． 中国计算机学会通讯，２０１２，８（５）： １５－２１． ［ ２ ］ ＷＥ ＡＲＥ ＳＯＣＩＡＬ ＬＴＤ． ＤＩＧＩＴＡＬ ＩＮ ２０１６ ［ ＥＢ／ ＯＬ］． ［２０１７⁃０３⁃１０］． ｈｔｔｐ： ／ ／ ｗｅａｒｅｓｏｃｉａｌ． ｃｏｍ／ ｕｋ ／ ｓｐｅｃｉａｌ⁃ｒｅｐｏｒｔｓ／ ｄｉｇｉｔａｌ⁃ｉｎ－２０１６． ［３ ］ ＺＨＥＮＧ Ｙｕ， ＸＩＥ Ｘ． Ｌｏｃａｔｉｏｎ⁃ｂａｓｅｄ ｓｏｃｉａｌ ｎｅｔｗｏｒｋｓ： ｌｏｃａｔｉｏｎｓ ［ Ｊ］． Ｃｏｍｐｕｔｉｎｇ ｗｉｔｈ ｓｐａｔｉａｌ ｔｒａｊｅｃｔｏｒｉｅｓ， ２０１１： ２７７－３０８． ·７５８· 智 能 系 统 学 报 第 １２ 卷