第12卷第5期 智能系统学报 Vol.12 No.5 2017年10月 CAAI Transactions on Intelligent Systems 0ct.2017 D0I:10.11992/tis.201706027 网络出版地址：http:/kns.cmki.net/kcms/detail/23.1538.TP.20170831.1058.016.html 移动社交网络异常签到在线检测算法 赵冠哲，齐建鹏，于彦伟，刘兆伟，宋鹏 (烟台大学计算机与控制工程学院，山东烟台264005) 摘要：随着智能手机、Pd等智能移动设备的广泛普及，移动社交网络的应用得到了快速发展。本文针对移动社交 网络中用户异常签到位置检测问题，提出了一类基于用户移动行为特征的异常签到在线检测方法。首先，在基于距 离的异常模型基础上，提出了基于历史位置(H-Outlier)和基于好友圈(F-Outlier)两种异常签到模型：然后，针对H- Outlier提出了一种优化的检测算法H-Opt,利用所提的签到状态模型与优化的邻居搜索机制降低检测时间：针对F. Outlier提出了一种基于触发的优化检测算法F-Opt,将连续的在线异常检测转化成了基于触发的异常检测方式：最 后，在真实的移动社交网络用户签到数据集上，验证了所提算法的有效性。实验结果显示，F-Opt显著降低了H-Op 的异常检测错误率：同时，相比于LUE算法，F-0pt和H-0pt的效率分别平均提升了2.34倍和2.45倍。 关键词：移动社交网络；异常检测：签到位置：基于距离的异常：好友圈：签到状态：邻居搜索：时间触发检测 中图分类号：TP391文献标志码：A文章编号：1673-4785(2017)05-0752-08 中文引用格式：赵冠哲，齐建鹏，于彦伟，等.移动社交网络异常签到在线检测算法[J].智能系统学报，2017,12(5)：752-759. 英文引用格式：ZHA0 Guanzhe,QI Jianpeng,YU Yanwei,,etal.Online check-in outlier detection method in mobile social networks[J].CAAI transactions on intelligent systems,2017,12(5):752-759. Online check-in outlier detection method in mobile social networks ZHAO Guanzhe,QI Jianpeng,YU Yanwei,LIU Zhaowei,SONG Peng (School of Computer and Control Engineering,Yantai University,Yantai 264005,China) Abstract:With the increasing popularization of smartphone,Pads and other smart mobile devices,the use of mobile social networks has also developed rapidly.In this paper,we propose an online method for detecting check- in outliers based on user mobility behavior in mobile social networks.First.based on a distance-based outlier model,we propose two check-in outlier models with respect to historical location(H-Outlier)and friend circle (F- Outlier),respectively.Second,for the H-Outlier,we propose an optimized detection algorithm called H-Opt, which utilizes the proposed check-in status model and an optimized neighbor searching mechanism to reduce computation time.For the F-Outlier,we propose a trigger-based optimized detection algorithm called F-Opt,which transforms continuous online outlier detection into trigger-based outlier detection.Lastly,we present our experimental results,based on a real-world check-in dataset,which demonstrate the effectiveness of the proposed algorithm.Our experimental results show that F-Opt significantly reduces the error rate of H-Opt outlier detection. In addition,compared with the LUE algorithm,the F-Opt and H-Opt algorithms improved efficiency by 2.34 and 2.45 times,respectively. Keywords:location-based social networks;outlier detection;check-in location;distance-based outlier;friend circle;status of check-in;neighbor searching;time-triggered detection 随着GPS终端、Pad、智能手机等位置感知设备 了快速发展。移动社交网络也称基于位置的社交 的广泛普及，各类新型社交网络手机应用不断涌 网络(location-based social networks,LBSN),本质是 现，促使移动社交网络(mobile social networks)得到 提供一个在人群中分享兴趣、爱好、状态和活动等 收稿日期：2017-06-08.网络出版日期：2017-08-31. 信息的平台)。如国内的腾讯QQ、微信、新浪微 基金项目：国家自然科学基金项目(61403328,61572419)：山东省重点 博、人人网，国外的Twitter、Facebook、Gowalla、 研发计划项目(2015GSF115009):山东省自然科学基金项目 (ZR2014Q016):烟台大学研究生科技创新基金项目Foursquare等，这些LBSN应用聚集了大量移动用 (YDZD1712). 通信作者：于彦伟.E-mail:yuyanwei(@ytu.cdu.cm. 户。据We Are Social公司在2016年数字报告[)中
第 １２ 卷第 ５ 期 智 能 系 统 学 报 Ｖｏｌ．１２ №．５ ２０１７ 年 １０ 月 ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ Ｏｃｔ． ２０１７ ＤＯＩ：１０．１１９９２ ／ ｔｉｓ．２０１７０６０２７ 网络出版地址：ｈｔｔｐ： ／ ／ ｋｎｓ．ｃｎｋｉ．ｎｅｔ ／ ｋｃｍｓ／ ｄｅｔａｉｌ ／ ２３．１５３８．ＴＰ．２０１７０８３１．１０５８．０１６．ｈｔｍｌ 移动社交网络异常签到在线检测算法 赵冠哲，齐建鹏，于彦伟，刘兆伟，宋鹏 （烟台大学 计算机与控制工程学院，山东 烟台 ２６４００５） 摘 要：随着智能手机、Ｐａｄ 等智能移动设备的广泛普及，移动社交网络的应用得到了快速发展。 本文针对移动社交 网络中用户异常签到位置检测问题，提出了一类基于用户移动行为特征的异常签到在线检测方法。 首先，在基于距 离的异常模型基础上，提出了基于历史位置 （Ｈ⁃Ｏｕｔｌｉｅｒ）和基于好友圈 （Ｆ⁃Ｏｕｔｌｉｅｒ）两种异常签到模型；然后，针对 Ｈ⁃ Ｏｕｔｌｉｅｒ 提出了一种优化的检测算法 Ｈ⁃Ｏｐｔ，利用所提的签到状态模型与优化的邻居搜索机制降低检测时间；针对 Ｆ⁃ Ｏｕｔｌｉｅｒ 提出了一种基于触发的优化检测算法 Ｆ⁃Ｏｐｔ，将连续的在线异常检测转化成了基于触发的异常检测方式；最 后，在真实的移动社交网络用户签到数据集上，验证了所提算法的有效性。 实验结果显示，Ｆ⁃Ｏｐｔ 显著降低了 Ｈ⁃Ｏｐｔ 的异常检测错误率；同时，相比于 ＬＵＥ 算法，Ｆ⁃Ｏｐｔ 和 Ｈ⁃Ｏｐｔ 的效率分别平均提升了 ２．３４ 倍和 ２．４５ 倍。 关键词：移动社交网络；异常检测；签到位置；基于距离的异常；好友圈；签到状态；邻居搜索；时间触发检测 中图分类号：ＴＰ３９１ 文献标志码：Ａ 文章编号：１６７３－４７８５（２０１７）０５－０７５２－０８ 中文引用格式：赵冠哲，齐建鹏，于彦伟，等．移动社交网络异常签到在线检测算法［Ｊ］． 智能系统学报， ２０１７， １２（５）： ７５２－７５９． 英文引用格式： ＺＨＡＯ Ｇｕａｎｚｈｅ， ＱＩ Ｊｉａｎｐｅｎｇ， ＹＵ Ｙａｎｗｅｉ， ｅｔ ａｌ． Ｏｎｌｉｎｅ ｃｈｅｃｋ⁃ｉｎ ｏｕｔｌｉｅｒ ｄｅｔｅｃｔｉｏｎ ｍｅｔｈｏｄ ｉｎ ｍｏｂｉｌｅ ｓｏｃｉａｌ ｎｅｔｗｏｒｋｓ［Ｊ］． ＣＡＡＩ ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｉｎｔｅｌｌｉｇｅｎｔ ｓｙｓｔｅｍｓ， ２０１７， １２（５）： ７５２－７５９． Ｏｎｌｉｎｅ ｃｈｅｃｋ⁃ｉｎ ｏｕｔｌｉｅｒ ｄｅｔｅｃｔｉｏｎ ｍｅｔｈｏｄ ｉｎ ｍｏｂｉｌｅ ｓｏｃｉａｌ ｎｅｔｗｏｒｋｓ ＺＨＡＯ Ｇｕａｎｚｈｅ， ＱＩ Ｊｉａｎｐｅｎｇ， ＹＵ Ｙａｎｗｅｉ， ＬＩＵ Ｚｈａｏｗｅｉ， ＳＯＮＧ Ｐｅｎｇ （Ｓｃｈｏｏｌ ｏｆ Ｃｏｍｐｕｔｅｒ ａｎｄ Ｃｏｎｔｒｏｌ Ｅｎｇｉｎｅｅｒｉｎｇ， Ｙａｎｔａｉ Ｕｎｉｖｅｒｓｉｔｙ， Ｙａｎｔａｉ ２６４００５， Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｗｉｔｈ ｔｈｅ ｉｎｃｒｅａｓｉｎｇ ｐｏｐｕｌａｒｉｚａｔｉｏｎ ｏｆ ｓｍａｒｔｐｈｏｎｅ， Ｐａｄｓ ａｎｄ ｏｔｈｅｒ ｓｍａｒｔ ｍｏｂｉｌｅ ｄｅｖｉｃｅｓ， ｔｈｅ ｕｓｅ ｏｆ ｍｏｂｉｌｅ ｓｏｃｉａｌ ｎｅｔｗｏｒｋｓ ｈａｓ ａｌｓｏ ｄｅｖｅｌｏｐｅｄ ｒａｐｉｄｌｙ． Ｉｎ ｔｈｉｓ ｐａｐｅｒ， ｗｅ ｐｒｏｐｏｓｅ ａｎ ｏｎｌｉｎｅ ｍｅｔｈｏｄ ｆｏｒ ｄｅｔｅｃｔｉｎｇ ｃｈｅｃｋ⁃ ｉｎ ｏｕｔｌｉｅｒｓ ｂａｓｅｄ ｏｎ ｕｓｅｒ ｍｏｂｉｌｉｔｙ ｂｅｈａｖｉｏｒ ｉｎ ｍｏｂｉｌｅ ｓｏｃｉａｌ ｎｅｔｗｏｒｋｓ． Ｆｉｒｓｔ， ｂａｓｅｄ ｏｎ ａ ｄｉｓｔａｎｃｅ⁃ｂａｓｅｄ ｏｕｔｌｉｅｒ ｍｏｄｅｌ， ｗｅ ｐｒｏｐｏｓｅ ｔｗｏ ｃｈｅｃｋ⁃ｉｎ ｏｕｔｌｉｅｒ ｍｏｄｅｌｓ ｗｉｔｈ ｒｅｓｐｅｃｔ ｔｏ ｈｉｓｔｏｒｉｃａｌ ｌｏｃａｔｉｏｎ （Ｈ⁃Ｏｕｔｌｉｅｒ） ａｎｄ ｆｒｉｅｎｄ ｃｉｒｃｌｅ （Ｆ⁃ Ｏｕｔｌｉｅｒ）， ｒｅｓｐｅｃｔｉｖｅｌｙ． Ｓｅｃｏｎｄ， ｆｏｒ ｔｈｅ Ｈ⁃Ｏｕｔｌｉｅｒ， ｗｅ ｐｒｏｐｏｓｅ ａｎ ｏｐｔｉｍｉｚｅｄ ｄｅｔｅｃｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｃａｌｌｅｄ Ｈ⁃Ｏｐｔ， ｗｈｉｃｈ ｕｔｉｌｉｚｅｓ ｔｈｅ ｐｒｏｐｏｓｅｄ ｃｈｅｃｋ⁃ｉｎ ｓｔａｔｕｓ ｍｏｄｅｌ ａｎｄ ａｎ ｏｐｔｉｍｉｚｅｄ ｎｅｉｇｈｂｏｒ ｓｅａｒｃｈｉｎｇ ｍｅｃｈａｎｉｓｍ ｔｏ ｒｅｄｕｃｅ ｃｏｍｐｕｔａｔｉｏｎ ｔｉｍｅ． Ｆｏｒ ｔｈｅ Ｆ⁃Ｏｕｔｌｉｅｒ， ｗｅ ｐｒｏｐｏｓｅ ａ ｔｒｉｇｇｅｒ⁃ｂａｓｅｄ ｏｐｔｉｍｉｚｅｄ ｄｅｔｅｃｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｃａｌｌｅｄ Ｆ⁃Ｏｐｔ， ｗｈｉｃｈ ｔｒａｎｓｆｏｒｍｓ ｃｏｎｔｉｎｕｏｕｓ ｏｎｌｉｎｅ ｏｕｔｌｉｅｒ ｄｅｔｅｃｔｉｏｎ ｉｎｔｏ ｔｒｉｇｇｅｒ⁃ｂａｓｅｄ ｏｕｔｌｉｅｒ ｄｅｔｅｃｔｉｏｎ． Ｌａｓｔｌｙ， ｗｅ ｐｒｅｓｅｎｔ ｏｕｒ ｅｘｐｅｒｉｍｅｎｔａｌ ｒｅｓｕｌｔｓ， ｂａｓｅｄ ｏｎ ａ ｒｅａｌ⁃ｗｏｒｌｄ ｃｈｅｃｋ⁃ｉｎ ｄａｔａｓｅｔ， ｗｈｉｃｈ ｄｅｍｏｎｓｔｒａｔｅ ｔｈｅ ｅｆｆｅｃｔｉｖｅｎｅｓｓ ｏｆ ｔｈｅ ｐｒｏｐｏｓｅｄ ａｌｇｏｒｉｔｈｍ． Ｏｕｒ ｅｘｐｅｒｉｍｅｎｔａｌ ｒｅｓｕｌｔｓ ｓｈｏｗ ｔｈａｔ Ｆ⁃Ｏｐｔ ｓｉｇｎｉｆｉｃａｎｔｌｙ ｒｅｄｕｃｅｓ ｔｈｅ ｅｒｒｏｒ ｒａｔｅ ｏｆ Ｈ⁃Ｏｐｔ ｏｕｔｌｉｅｒ ｄｅｔｅｃｔｉｏｎ． Ｉｎ ａｄｄｉｔｉｏｎ， ｃｏｍｐａｒｅｄ ｗｉｔｈ ｔｈｅ ＬＵＥ ａｌｇｏｒｉｔｈｍ， ｔｈｅ Ｆ⁃Ｏｐｔ ａｎｄ Ｈ⁃Ｏｐｔ ａｌｇｏｒｉｔｈｍｓ ｉｍｐｒｏｖｅｄ ｅｆｆｉｃｉｅｎｃｙ ｂｙ ２．３４ ａｎｄ ２．４５ ｔｉｍｅｓ， ｒｅｓｐｅｃｔｉｖｅｌｙ． Ｋｅｙｗｏｒｄｓ：ｌｏｃａｔｉｏｎ⁃ｂａｓｅｄ ｓｏｃｉａｌ ｎｅｔｗｏｒｋｓ； ｏｕｔｌｉｅｒ ｄｅｔｅｃｔｉｏｎ； ｃｈｅｃｋ⁃ｉｎ ｌｏｃａｔｉｏｎ； ｄｉｓｔａｎｃｅ⁃ｂａｓｅｄ ｏｕｔｌｉｅｒ； ｆｒｉｅｎｄ ｃｉｒｃｌｅ； ｓｔａｔｕｓ ｏｆ ｃｈｅｃｋ⁃ｉｎ； ｎｅｉｇｈｂｏｒ ｓｅａｒｃｈｉｎｇ； ｔｉｍｅ－ｔｒｉｇｇｅｒｅｄ ｄｅｔｅｃｔｉｏｎ 收稿日期：２０１７－０６－０８． 网络出版日期：２０１７－０８－３１． 基金项目：国家自然科学基金项目（６１４０３３２８， ６１５７２４１９）； 山东省重点 研发计划项目（２０１５ＧＳＦ１１５００９）； 山东省自然科学基金项目 （ＺＲ２０１４ＦＱ０１６ ）； 烟 台 大 学 研 究 生 科 技 创 新 基 金 项 目 （ＹＤＺＤ１７１２）． 通信作者：于彦伟． Ｅ⁃ｍａｉｌ：ｙｕｙａｎｗｅｉ＠ ｙｔｕ．ｅｄｕ．ｃｎ． 随着 ＧＰＳ 终端、Ｐａｄ、智能手机等位置感知设备 的广泛普及，各类新型社交网络手机应用不断涌 现，促使移动社交网络（ｍｏｂｉｌｅ ｓｏｃｉａｌ ｎｅｔｗｏｒｋｓ）得到 了快速发展。 移动社交网络也称基于位置的社交 网络（ｌｏｃａｔｉｏｎ⁃ｂａｓｅｄ ｓｏｃｉａｌ ｎｅｔｗｏｒｋｓ， ＬＢＳＮ），本质是 提供一个在人群中分享兴趣、爱好、状态和活动等 信息的平台［１］ 。 如国内的腾讯 ＱＱ、微信、新浪微 博、 人 人 网， 国 外 的 Ｔｗｉｔｔｅｒ、 Ｆａｃｅｂｏｏｋ、 Ｇｏｗａｌｌａ、 Ｆｏｕｒｓｑｕａｒｅ 等，这些 ＬＢＳＮ 应用聚集了大量移动用 户。 据 Ｗｅ Ａｒｅ Ｓｏｃｉａｌ 公司在 ２０１６ 年数字报告［２］ 中
第5期 赵冠哲，等：移动社交网络异常签到在线检测算法 ·753· 指出，2016年全球社交网络用户约19.7亿，占全球 (DB-Outlier)检测问题。给定一个数据集合，若某 总人口的27%。LBSN中海量带有位置信息的社会 数据点的邻域内的数据个数小于给定阈值，则该数 媒体数据可被用于各类挖掘应用研究，如挖掘用户 据点为基于距离的异常点。之后，Knor等)将基 兴趣偏好、好友推荐、兴趣点推荐、热点路径推 于距离的异常模型应用到时空轨迹数据异常检测 荐等[3 中。Ramaswamy等[)提出了一种基于k近邻的异 移动社交网络正逐渐改变着人们的生活方式 常定义，根据数据点到第k近邻的距离检测出n个 和生活习惯，给人类社会带来前所未有的变革以及 巨大的经济收益。同时它也吸引了一些不法者 k近邻距离最大的数据点作为异常点。Breunig 盗取用户账号及信息进行各种恶意行为，影响了用 等[]提出另外一类基于密度的数据异常类型，通过 户的正常使用，损害了用户利益，甚至给用户带来 计算本地异常因子LOF来检测局部异常点数据，但 了巨大的经济损失。因此，面向移动社交网络，追 该算法存在较高计算复杂度问题。 踪用户的历史签到位置数据，从用户移动行为特征 在数据流异常检测方面，Yang等Im采用滑动 视角，对用户状态进行在线异常检测，这对于移动 窗口方式在数据流上挖掘基于邻居的模式，主要包 社交网络的安全、用户的隐私保护等具有重要意义。 括基于密度的聚类和基于距离的异常检测。 针对移动社交网络异常账号的检测问题，学术 Angiulli等通过在数据流上分析数据点是否为 界和工业界都提出了大量检测方案[)，主要包括基 “safe inlier'”来优化检测方法。Kontaki等u]利用 于行为特征的检测、基于内容的检测、基于图的检 “safe inlier'”设计了一种事件触发的数据流异常检 测和无监督学习的异常检测方法等。而针对移动 测优化算法。Cao等[提出了一种数据流异常检 社交网络中签到位置数据异常检测研究还比较少。 测框架，该框架可用于处理基于距离的和基于k近 本文从用户的移动位置特征视角对异常签到位置 进行检测，针对移动社交网络用户异常签到检测问 邻的两类异常检测模型。 题，提出了一类基于签到位置的在线异常检测方 针对移动对象的轨迹数据，Lee等[us]提出了一 法。首先，在基于距离的异常检测基础上，提出了 种划分-检测的轨迹异常检测框架，将轨迹划分成- 两种异常签到模型，即基于历史位置的异常签到 partition序列，通过计算t-partition间的距离和密度， (history location based outlier,H-Outlier)和基于好友 以发现异常的子t-partition。Bu等6提出了一种连 圈的异常签到(friendship based outlier,.F-Outlier); 续监控移动对象实时轨迹数据流的异常检测算法， 其次，针对H-Outlier,提出了一种优化的检测算法 该方法关注在检测单个移动对象实时轨迹数据中 H-Opt,利用优化的检测状态与邻居搜索机制降低 的异常子轨迹段。文献「17]针对海量移动对象系 检测时间：然后，针对F-Outlier,基于提出的3个优 统中异常对象，提出了一种基于邻居的异常移动对 化策略，提出了一种基于触发的优化检测算法F- 象检测方法，可发现不同于其他邻居对象运动轨迹 Opt,将连续在线异常检测转化成了基于触发的异常 的异常对象。 检测方式，本文采用滑动窗口技术实现H-Opt和F- Opt:最后，在真实的移动社交网络用户签到数据集 2 问题定义 上，验证了所提算法的有效性和效率。 在移动社交网络中用户往往会在新地点进行 本节首先给出一些重要的定义和表示，然后对 签到或登录，所以H-Outlier检测到的异常签到地点 基于距离的移动社交网络异常签到模型进行描述。 很有可能并非真正的异常。为排除这些伪异常状 定义1基于距离的位置异常。给定位置数据 况，本文提出了好友圈的概念和基于好友圈的异常 集D、距离阈值d、邻居点数量阈值k,对于位置数据 签到模型F-Outlier.,这是因为在移动社交网络中 点o∈D,如果{pdist(p,o)≤d,p∈D}≤k, 50%~70%的行为可由周期行为解释，还有10%~ 则称0是一个基于距离的位置异常点。 30%行为可根据好友关系行为解释6)。也就是说， U={u1,山2，…，山m}表示移动社交网络的所有 在移动社交网络中用户往往与认识的好友共同出 现在不经常签到的地点，如朋友聚餐、商务活动或 用户集，用户“：在t时间点的签到位置表示为p。 本文采用基于签到位置数量的滑动窗口W来 者公务出差等。针对这些伪异常，我们通过检测好 友圈中好友签到位置来判断用户的签到是否为真 处理移动社交网络中实时的签到数据，窗口长度标 正的异常签到。 记为|W=w,也就是说，W中包含w个签到位置。 定义2基于历史位置的异常签到。给定距离 相关工作 阈值d、邻居点数量阈值k,滑动窗口W,对于用户u: Knor和Ng)最早提出了基于距离的空间异常 的签到位置p6∈w,如果|{p|dist(p,p)≤d
指出，２０１６ 年全球社交网络用户约 １９．７ 亿，占全球 总人口的 ２７％。 ＬＢＳＮ 中海量带有位置信息的社会 媒体数据可被用于各类挖掘应用研究，如挖掘用户 兴趣偏 好、 好 友 推 荐、 兴 趣 点 推 荐、 热 点 路 径 推 荐等［３］ 。 移动社交网络正逐渐改变着人们的生活方式 和生活习惯，给人类社会带来前所未有的变革以及 巨大的经济收益［４］ 。 同时它也吸引了一些不法者 盗取用户账号及信息进行各种恶意行为，影响了用 户的正常使用，损害了用户利益，甚至给用户带来 了巨大的经济损失。 因此，面向移动社交网络，追 踪用户的历史签到位置数据，从用户移动行为特征 视角，对用户状态进行在线异常检测，这对于移动 社交网络的安全、用户的隐私保护等具有重要意义。 针对移动社交网络异常账号的检测问题，学术 界和工业界都提出了大量检测方案［５］ ，主要包括基 于行为特征的检测、基于内容的检测、基于图的检 测和无监督学习的异常检测方法等。 而针对移动 社交网络中签到位置数据异常检测研究还比较少。 本文从用户的移动位置特征视角对异常签到位置 进行检测，针对移动社交网络用户异常签到检测问 题，提出了一类基于签到位置的在线异常检测方 法。 首先，在基于距离的异常检测基础上，提出了 两种异常签到模型，即基于历史位置的异常签到 （ｈｉｓｔｏｒｙ ｌｏｃａｔｉｏｎ ｂａｓｅｄ ｏｕｔｌｉｅｒ，Ｈ⁃Ｏｕｔｌｉｅｒ）和基于好友 圈的异常签到（ ｆｒｉｅｎｄｓｈｉｐ ｂａｓｅｄ ｏｕｔｌｉｅｒ，Ｆ⁃Ｏｕｔｌｉｅｒ）； 其次，针对 Ｈ⁃Ｏｕｔｌｉｅｒ，提出了一种优化的检测算法 Ｈ⁃Ｏｐｔ，利用优化的检测状态与邻居搜索机制降低 检测时间；然后，针对 Ｆ⁃Ｏｕｔｌｉｅｒ，基于提出的 ３ 个优 化策略，提出了一种基于触发的优化检测算法 Ｆ⁃ Ｏｐｔ，将连续在线异常检测转化成了基于触发的异常 检测方式，本文采用滑动窗口技术实现 Ｈ⁃Ｏｐｔ 和 Ｆ⁃ Ｏｐｔ；最后，在真实的移动社交网络用户签到数据集 上，验证了所提算法的有效性和效率。 在移动社交网络中用户往往会在新地点进行 签到或登录，所以 Ｈ⁃Ｏｕｔｌｉｅｒ 检测到的异常签到地点 很有可能并非真正的异常。 为排除这些伪异常状 况，本文提出了好友圈的概念和基于好友圈的异常 签到模型 Ｆ⁃Ｏｕｔｌｉｅｒ，这是因为在移动社交网络中 ５０％ ～７０％的行为可由周期行为解释，还有 １０％ ～ ３０％行为可根据好友关系行为解释［６］ 。 也就是说， 在移动社交网络中用户往往与认识的好友共同出 现在不经常签到的地点，如朋友聚餐、商务活动或 者公务出差等。 针对这些伪异常，我们通过检测好 友圈中好友签到位置来判断用户的签到是否为真 正的异常签到。 １ 相关工作 Ｋｎｏｒｒ 和 Ｎｇ ［７］最早提出了基于距离的空间异常 （ＤＢ⁃Ｏｕｔｌｉｅｒ）检测问题。 给定一个数据集合，若某 数据点的邻域内的数据个数小于给定阈值，则该数 据点为基于距离的异常点。 之后，Ｋｎｏｒｒ 等［８］ 将基 于距离的异常模型应用到时空轨迹数据异常检测 中。 Ｒａｍａｓｗａｍｙ 等［９］ 提出了一种基于 ｋ 近邻的异 常定义，根据数据点到第 ｋ 近邻的距离检测出 ｎ 个 ｋ 近邻 距 离 最 大 的 数 据 点 作 为 异 常 点。 Ｂｒｅｕｎｉｇ 等［１０］提出另外一类基于密度的数据异常类型，通过 计算本地异常因子 ＬＯＦ 来检测局部异常点数据，但 该算法存在较高计算复杂度问题。 在数据流异常检测方面，Ｙａｎｇ 等［１１］ 采用滑动 窗口方式在数据流上挖掘基于邻居的模式，主要包 括基 于 密 度 的 聚 类 和 基 于 距 离 的 异 常 检 测。 Ａｎｇｉｕｌｌｉ 等［１２］通过在数据流上分析数据点是否为 “ｓａｆｅ ｉｎｌｉｅｒ” 来优化检测方法。 Ｋｏｎｔａｋｉ 等［１３］ 利用 “ｓａｆｅ ｉｎｌｉｅｒ”设计了一种事件触发的数据流异常检 测优化算法。 Ｃａｏ 等［１４］ 提出了一种数据流异常检 测框架，该框架可用于处理基于距离的和基于 ｋ 近 邻的两类异常检测模型。 针对移动对象的轨迹数据，Ｌｅｅ 等［１５］ 提出了一 种划分⁃检测的轨迹异常检测框架，将轨迹划分成 ｔ⁃ ｐａｒｔｉｔｉｏｎ 序列，通过计算 ｔ⁃ｐａｒｔｉｔｉｏｎ 间的距离和密度， 以发现异常的子 ｔ⁃ｐａｒｔｉｔｉｏｎ。 Ｂｕ 等［１６］ 提出了一种连 续监控移动对象实时轨迹数据流的异常检测算法， 该方法关注在检测单个移动对象实时轨迹数据中 的异常子轨迹段。 文献［１７］ 针对海量移动对象系 统中异常对象，提出了一种基于邻居的异常移动对 象检测方法，可发现不同于其他邻居对象运动轨迹 的异常对象。 ２ 问题定义 本节首先给出一些重要的定义和表示，然后对 基于距离的移动社交网络异常签到模型进行描述。 定义 １ 基于距离的位置异常。 给定位置数据 集 Ｄ、距离阈值 ｄ、邻居点数量阈值 ｋ，对于位置数据 点 ｏ ∈ Ｄ ，如果 { ｐ ｄｉｓｔ(ｐ，ｏ) ≤ ｄ，ｐ ∈ Ｄ} ≤ ｋ， 则称 ｏ 是一个基于距离的位置异常点。 Ｕ ＝ ｛ｕ１ ，ｕ２ ，．．．，ｕｍ ｝ 表示移动社交网络的所有 用户集，用户 ｕｉ在 ｔ ｊ 时间点的签到位置表示为 ｐ ｉ ｊ 。 本文采用基于签到位置数量的滑动窗口 Ｗ 来 处理移动社交网络中实时的签到数据，窗口长度标 记为 Ｗ ＝ ｗ ，也就是说，Ｗ 中包含 ｗ 个签到位置。 定义 ２ 基于历史位置的异常签到。 给定距离 阈值 ｄ、邻居点数量阈值 ｋ，滑动窗口 Ｗ，对于用户 ｕｉ 的签到位置 ｐ ｉ ｂ ∈ ｗ， 如果 ｛ｐ ｉ ｊ ｄｉｓｔ（ｐ ｉ ｊ ，ｐ ｉ ｂ） ≤ ｄ， 第 ５ 期 赵冠哲，等：移动社交网络异常签到在线检测算法 ·７５３·
.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时，并不需要
ｐ ｉ ｊ ∈ Ｗ｝ ≤ｋ， 则称签到位置 ｐ ｉ ｂ 是一个基于历史位 置的异常签到点，记为Ｈ⁃Ｏｕｔｌｉｅｒ。 从定义 ２ 可以看出，Ｈ⁃Ｏｕｔｌｉｅｒ 是基于自身历史 签到位置的，这也是因为用户日常活动轨迹记录往 往具有周期性［１８］ 。 设 Ｆｒ （ ｕｉ ） 表示用户 ｕｉ 的所有直接好友集合。 与 ＱＱ、微信等社交网络的好友圈的定义不同，这里 给出的好友圈定义既包括用户 ｕｉ直接好友又包括与 ｕｉ有一定数量共同好友的间接好友。 定义 ３ 好友圈。 给定支持阈值 ｍ，用户ｕｉ的好 友圈包括ｕｉ的所有直接好友和与ｕｉ存在至少 ｍ 个共 同 直 接 好 友 的 间 接 好 友， 即 Ｆｒ （ ｕｉ ） ∪ {ｕｊ Ｆｒ（ｕｉ）∩Ｆｒ（ｕｊ） ≥ｍ} ，简记为 Ｎｅｔ（ｕｉ）。 定义 ４ 基于好友圈的异常签到。 给定距离阈 值 ｄ、好友圈包含的好友数量阈值 ｋｆ、时间 △ｔ ，对于 基于历史位置的异常签到点 ｐ ｉ ａ ，如果 ｛ｕｓ ∃ｐ ｓ ｊ ， ｄｉｓｔ（ｐ ｓ ｊ ，ｐ ｉ ａ ） ≤ ｄ， ｔ ａ － ｔ ｊ ≤ △ｔ，ｕｓ ∈ Ｎｅｔ（ｕｉ）｝ ≤ ｋｆ，ｐ ｉ ａ 是一个基于好友圈的异常签到点， 记为 Ｆ⁃ Ｏｕｔｌｉｅｒ。 根据定义 ４ 可知，Ｆ⁃Ｏｕｔｌｉｅｒ 是在 Ｈ⁃Ｏｕｔｌｉｅｒ 定义 的基础上定义的，因此，Ｆ⁃Ｏｕｔｌｉｅｒ 集合是 Ｈ⁃Ｏｕｔｌｉｅｒ 集合的子集。 文中涉及的符号名称及描述由表 １ 给出。 表 １ 符号名称及描述 Ｔａｂｌｅ １ Ｓｙｍｂｏｌｓ ａｎｄ ｉｔｓ ｄｅｓｃｒｉｐｔｉｏｎｓ 名称 解释 ｐ ｉ ｊ 用户ｕｉ在ｔ ｊ时间的签到位置 Ｗ 基于签到位置数量的滑动窗口 ｄ 距离阈值 ｋ 邻居点数量阈值 Ｆｒ（ｕｉ） 用户ｕｉ的直接好友集合 ｍ 共同直接好友数量阈值 Ｎｅｔ（ｕｉ） 用户ｕｉ的好友圈 ｐ．Ｎｅｉ ｂｅｆｏｒｅ 签到位置 ｐ 之前的邻居集合 ｐ．Ｎｅｉ ａｆｔｅｒ 签到位置 ｐ 之后的邻居集合 ｋｆ 好友圈中邻居点数量阈值 Ｄ 签到位置数据流 △ｔ 触发项的有效期 ３ 基于历史位置的异常签到检测算法 本节将详细介绍 Ｈ⁃Ｏｕｔｌｉｅｒ 的在线检测算法。 为了提升检测效率，首先介绍检测算法采用的几种 优化策略，然后给出详细的检测算法。 ３．１ 优化策略 若两个签到位置之间距离小于给定距离阈值 ｄ，称它们互为邻居点。 １）签到位置的状态 传统检测方法仅将用户的签到位置分为正常 和异常两种状态，而通过在滑动窗口下用户签到位 置的检测发现，签到位置的状态可进一步细分，以 便减少距离计算。 在滑动窗口 Ｗ 中签到位置 ｐ 的 状态可分为：①确定的正常点。 如果 ｐ 在 Ｗ 中邻居 数量大于等于 ｋ，并且在 ｐ 点之后邻居数量也大于 等于 ｋ，这时不管 Ｗ 如何滑动，位置 ｐ 在滑出窗口之 前，在窗口内邻居数量一定大于等于 ｋ 个，因此，此 时 ｐ 的状态可以认定为确定的正常签到点，记为 ｓａｆｅ⁃ｉｎｌｉｅｒ。 ②不确定的正常点。 如果 ｐ 在 Ｗ 中邻 居数量大于等于 ｋ，但是在 ｐ 点之后邻居数量小于 ｋ，这时 ｐ 虽然是一个正常状态的签到位置，但是当 Ｗ 滑动时，在位置 ｐ 之前的邻居可能会滑出窗口，ｐ 的状态可能会变成异常状态，此时的 ｐ 可认为是一 个不确定的正常点，记为 ｕｎｓａｆｅ⁃ｉｎｌｉｅｒ。 ③确定的异 常点。 设签到位置 ｐ 之前的邻居集合为ｐ．Ｎｅｉ ｂｅｆｏｒｅ， 之后的邻居集合为ｐ．Ｎｅｉ ａｆｔｅｒ，如果 ｐ 在 Ｗ 中邻居数量 小于 ｋ，在 ｐ 之前有 ｍｂｅｆｏｒｅ个位置，如果 ｐ．Ｎｅｉ ａｆｔｅｒ 小 于 ｋ⁃ｍｂｅｆｏｒｅ，这时不管 Ｗ 如何滑动，位置 ｐ 在滑出窗 口之前，都不可能包括 ｋ 个邻居，因此，此时 ｐ 的状 态可以认定为确定的异常签到点，记为 ｓａｆｅ⁃ｏｕｔｌｉｅｒ。 ④异常点。 剩下的异常签到点都划归为这一类，记 为 ｏｕｔｌｉｅｒ。 很明显，一旦确定 ｓａｆｅ⁃ｉｎｌｉｅｒ 和 ｓａｆｅ⁃ｏｕｔｌｉｅｒ 状态 之后不必再对这些签到位置进行重新检测。 而随 着窗口滑动， ｏｕｔｌｉｅｒ 和 ｕｎｓａｆｅ⁃ｉｎｌｉｅｒ 仍需重新检测 状态。 ２）优化的邻居点搜索机制 根据上述签到位置的状态划分方法，我们将签 到位置的邻居点分为在 ｐ 签到之前和在 ｐ 签到之后 两个 部 分， 以 便 快 速 确 定 签 到 位 置 的 状 态。 若 ｐ．Ｎｅｉ ａｆｔｅｒ ≥ｋ，ｐ 为 ｓａｆｅ⁃ｉｎｌｉｅｒ；若 ｐ．Ｎｅｉ ａｆｔｅｒ ＜ ｋ，但 ｐ．Ｎｅｉ ｂｅｆｏｒｅ ＋ ｐ．Ｎｅｉ ａｆｔｅｒ ≥ ｋ， ｐ 为 ｕｎｓａｆｅ⁃ｉｎｌｉｅｒ；若 ｐ．Ｎｅｉ ｂｅｆｏｒｅ ＋ ｐ．Ｎｅｉ ａｆｔｅｒ ＜ｋ，并且 ｐ．Ｎｅｉ ａｆｔｅｒ ＜ｋ⁃ｍｂｅｆｏｒｅ， ｐ 为 ｓａｆｅ⁃ｏｕｔｌｉｅｒ；其他情况下，ｐ 为 ｏｕｔｌｉｅｒ。 通过观察发现，随着滑动窗口的滑动，对于签 到位 置 ｐ 的 所 有 邻 居 点 ｐ． Ｎｅｉ ｂｅｆｏｒｅ 和 ｐ． Ｎｅｉ ａｆｔｅｒ， ｐ．Ｎｅｉ ｂｅｆｏｒｅ中的位置点不断滑出窗口，而 ｐ．Ｎｅｉ ａｆｔｅｒ则一 直处在窗口内，直到 ｐ 也滑出窗口才会失效。 因此， 在搜索 ｐ 的邻居时可优先搜索在其之后的邻居，越 靠后的邻居有效期越长；而在其之前的邻居，越靠 近 ｐ 存活期越长。 基于该观察，在滑动窗口内从最 后一个签到位置向前依次搜索邻居，满足优先搜索 Ｎｅｉ ａｆｔｅｒ，又实现了从最近到最远搜索 Ｎｅｉ ｂｅｆｏｒｅ。 ３） 最少邻居点搜索机制 若查找出签到位置 ｐ 的所有邻居，需扫描一遍 窗口。 受文献［１４］ 启发，在检测点 ｐ 时，并不需要 ·７５４· 智 能 系 统 学 报 第 １２ 卷
第5期 赵冠哲，等：移动社交网络异常签到在线检测算法 ·755. 搜索出所有邻居，当满足k个时，即可判定位置p的 20)if lpNeitore then 状态，但是同时为了结合上述的优化策略1)和2)， 21)Per·status更新为outlier 我们给出最少邻居点搜索机制。 4 给定签到位置p和新签到位置P,若 基于好友圈的异常检测算法 lp.Nei|≥k同时IpNeior|≥k,则无需计算 本节将详细介绍基于好友圈的异常签到 p与pea的距离。此时位置p已经确定为safe-inlier, F-Outlier的检测算法。F-Outlier定义在H-Outlier之 而p也已确定为unsafe-inlier。否则，将继续计算 上，对于当前窗口W上H-Outlier需进一步验证是否 P到所有之前签到位置的距离，以确定P为 为F-Outlier。H-Outlier仅在用户自身近期的历史签 outlier。采用该机制，既满足了所有签到位置状态 到位置上查找邻居点（滑动窗口W内），而F-Outlier 的检测又实现了最少的距离计算。 则在其好友圈用户的最近签到位置中搜索邻居点 3.2H-0 utlier在线检测算法 (△t时间差内)。 算法1给出了H-Outlier的优化检测算法，对于 为了进一步降低F-Outlier检测的时间消耗，本 新签到位置Pw,对窗口W中所有签到位置进行状 节同样给出了3个优化策略。 态重新检测。首先，按照优化的邻居搜索机制，从 1)最少好友搜索机制 窗口内最后一个位置，依次向前搜索邻居，如第1行 与H-Outlier检测的最少邻居点搜索机制相似， 所示。然后，采用最少邻居点搜索机制，判定位置P: 检测用户u,签到位置p。的状态时，并非需要完整搜 和P是否都已确定状态，若已确定，则不用再继续 索一遍Net(w:),若已存在k个好友在t内在同一地 搜索邻居2)~4)行，否则，继续计算距离，更新邻居 点（小于给定距离d)签到过，则可以停止搜索，此时 集合（见5）~7))。如果p,的状态不是safe-inlier或 可判定pi并非F-Outlier。 safe-outlier,则根据搜索邻居情况更新其状态，如 2)历史邻近好友优先原则 8)~17)所示。如果P搜索到k个在其之前的邻 在社会学领域研究中发现，人们在某一段时间 居，状态更新为unsafe-inlier(见l8)~19)),检测完 内往往与相同一群人存在较密集的交互4)。根据 窗口W后，若邻居数量依然少于k个，状态标记为 上述社会学的发现，我们对每个用户维护一个邻近 outlier. 好友的排序列表L,用于记录历史邻近签到状况，最 算法1H-Outlier优化检测算法 近一次的邻近签到好友排在首位，每次搜索邻近好 输入当前窗口W,k,d,Pw; 友时同时更新列表次序可以较大概率快速搜索邻 输出所有p∈W的状态。 近的签到好友，以排除H-Outlier,而不用随机遍历 1)fori从Wa到Wan do Net(u;). 2)ifp:sta是safe-inlier或者p.sta是safe-outlier 3)基于时间触发的检测机制 3)if pnex·sta是unsafe-inlier then 当签到位置p.在当前时刻检测为F-Outlier后， 4)继续 在后续的△1内需要不断重新检测它的状态是否有 5)else if p:与pen的距离≤d then 变化，但是当好友圈用户没有签到数据更新时，重 6)将p:添加到pNeibeore 新检测会导致冗余计算。因此，提出了一种基于时 7)将Pen添加到P:.Nei 间触发的检测机制。 8)else 每个用户u维护一个触发列表trigger,触发列 9)ifp:与pe的距离≤d then 表中每项表示为〈p。〉，当用户u更新签到数据时， 1O)将p:添加到pNeibefor 触发对p.的F-Outlier状态重检测。可以看出，每 1l)将poen添加到p.Neiafer 个触发项都存在一个有效期，即It。-t.I≤△t,当前时 12)if Ip:.Neie then 间t.与△t。的时间差不大于△t,超过该时间差，触 l3)p.status更新为safe-inlier 发项自动失效。 14)else if p:Neirp:Nei then 基于时间触发的检测机制将连续异常检测转 l5)p:.status更新为unsafe-inlier 化成了基于触发的检测，当有新签到数据时，才对 16)else if lp:Neir-m then 未过期的签到位置进行重新检测，大大减少了额外 l7)p:.status更新为safe-inlier 的周期性重新检测成本。 18)if pNeieore then 算法2描述了采用优化策略的F-Outlier的检 19)Pstatus更新为unsafe-inlier 测过程，针对用户“，的新签到位置p,首先执行H
搜索出所有邻居，当满足 ｋ 个时，即可判定位置 ｐ 的 状态，但是同时为了结合上述的优化策略 １）和 ２）， 我们给出最少邻居点搜索机制。 给定 签 到 位 置 ｐ 和 新 签 到 位 置 ｐｎｅｗ ， 若 ｐ．Ｎｅｉ ａｆｔｅｒ ≥ ｋ 同时 ｐｎｅｗ ．Ｎｅｉ ｂｅｆｏｒｅ ≥ｋ，则无需计算 ｐ 与 ｐｎｅｗ的距离。 此时位置 ｐ 已经确定为 ｓａｆｅ⁃ｉｎｌｉｅｒ， 而 ｐｎｅｗ也已确定为 ｕｎｓａｆｅ⁃ｉｎｌｉｅｒ。 否则，将继续计算 ｐｎｅｗ到所有之前签到位置的距离， 以确定 ｐｎｅｗ 为 ｏｕｔｌｉｅｒ。 采用该机制，既满足了所有签到位置状态 的检测又实现了最少的距离计算。 ３．２ Ｈ⁃Ｏｕｔｌｉｅｒ 在线检测算法 算法 １ 给出了 Ｈ⁃Ｏｕｔｌｉｅｒ 的优化检测算法，对于 新签到位置 ｐｎｅｗ ，对窗口 Ｗ 中所有签到位置进行状 态重新检测。 首先，按照优化的邻居搜索机制，从 窗口内最后一个位置，依次向前搜索邻居，如第 １ 行 所示。 然后，采用最少邻居点搜索机制，判定位置 ｐｉ 和 ｐｎｅｗ是否都已确定状态，若已确定，则不用再继续 搜索邻居 ２） ～４）行，否则，继续计算距离，更新邻居 集合（见 ５） ～７））。 如果 ｐｉ的状态不是 ｓａｆｅ⁃ｉｎｌｉｅｒ 或 ｓａｆｅ⁃ｏｕｔｌｉｅｒ，则根据搜索邻居情况更新其状态，如 ８） ～１７） 所示。 如果 ｐｎｅｗ搜索到 ｋ 个在其之前的邻 居，状态更新为 ｕｎｓａｆｅ⁃ｉｎｌｉｅｒ（见 １８） ～ １９）），检测完 窗口 Ｗ 后，若邻居数量依然少于 ｋ 个，状态标记为 ｏｕｔｌｉｅｒ。 算法 １ Ｈ⁃Ｏｕｔｌｉｅｒ 优化检测算法 输入 当前窗口 Ｗ，ｋ，ｄ，ｐｎｅｗ ； 输出 所有 ｐ ∈ Ｗ 的状态。 １）ｆｏｒ ｉ 从 Ｗｅｎｄ到 Ｗｓｔａｒｔ ｄｏ ２）ｉｆ ｐｉ ．ｓｔａ 是 ｓａｆｅ⁃ｉｎｌｉｅｒ 或者 ｐｉ ．ｓｔａ 是 ｓａｆｅ⁃ｏｕｔｌｉｅｒ ３） ｉｆ ｐｎｅｗ ．ｓｔａ 是 ｕｎｓａｆｅ⁃ｉｎｌｉｅｒ ｔｈｅｎ ４）继续 ５） ｅｌｓｅ ｉｆ ｐｉ与 ｐｎｅｗ的距离≤ｄ ｔｈｅｎ ６）将 ｐｉ添加到 ｐｎｅｗ ．Ｎｅｉ ｂｅｆｏｒｅ ７）将 ｐｎｅｗ添加到 ｐｉ ．Ｎｅｉ ａｆｔｅｒ ８） ｅｌｓｅ ９）ｉｆ ｐｉ与 ｐｎｅｗ的距离≤ｄ ｔｈｅｎ １０）将 ｐｉ添加到 ｐｎｅｗ ．Ｎｅｉ ｂｅｆｏｒｅ １１）将 ｐｎｅｗ添加到 ｐｉ ．Ｎｅｉ ａｆｔｅｒ １２） ｉｆ ｐｉ ．Ｎｅｉ ａｆｔｅｒ ≥ｋ ｔｈｅｎ １３）ｐｉ ．ｓｔａｔｕｓ 更新为 ｓａｆｅ⁃ｉｎｌｉｅｒ １４）ｅｌｓｅ ｉｆ ｐｉ ．Ｎｅｉ ｂｅｆｏｒｅ ＋ ｐｉ ．Ｎｅｉ ａｆｔｅｒ ≥ｋ ｔｈｅｎ １５）ｐｉ ．ｓｔａｔｕｓ 更新为 ｕｎｓａｆｅ⁃ｉｎｌｉｅｒ １６）ｅｌｓｅ ｉｆ ｐｉ ．Ｎｅｉ ｂｅｆｏｒｅ ＜ｋ⁃ｍｂｅｆｏｒｅ ｔｈｅｎ １７）ｐｉ ．ｓｔａｔｕｓ 更新为 ｓａｆｅ⁃ｉｎｌｉｅｒ １８）ｉｆ ｐｎｅｗ ．Ｎｅｉ ｂｅｆｏｒｅ ≥ｋ ｔｈｅｎ １９）ｐｎｅｗ ．ｓｔａｔｕｓ 更新为 ｕｎｓａｆｅ⁃ｉｎｌｉｅｒ ２０） ｉｆ ｐｎｅｗ ．Ｎｅｉ ｂｅｆｏｒｅ ＜ｋ ｔｈｅｎ ２１）ｐｎｅｗ ．ｓｔａｔｕｓ 更新为 ｏｕｔｌｉｅｒ ４ 基于好友圈的异常检测算法 本节 将 详 细 介 绍 基 于 好 友 圈 的 异 常 签 到 Ｆ⁃Ｏｕｔｌｉｅｒ的检测算法。 Ｆ⁃Ｏｕｔｌｉｅｒ 定义在 Ｈ⁃Ｏｕｔｌｉｅｒ 之 上，对于当前窗口 Ｗ 上 Ｈ⁃Ｏｕｔｌｉｅｒ 需进一步验证是否 为 Ｆ⁃Ｏｕｔｌｉｅｒ。 Ｈ⁃Ｏｕｔｌｉｅｒ 仅在用户自身近期的历史签 到位置上查找邻居点（滑动窗口 Ｗ 内），而 Ｆ⁃Ｏｕｔｌｉｅｒ 则在其好友圈用户的最近签到位置中搜索邻居点 （ △ｔ 时间差内）。 为了进一步降低 Ｆ⁃Ｏｕｔｌｉｅｒ 检测的时间消耗，本 节同样给出了 ３ 个优化策略。 １）最少好友搜索机制 与 Ｈ⁃Ｏｕｔｌｉｅｒ 检测的最少邻居点搜索机制相似， 检测用户 ｕｉ签到位置 ｐ ｉ ａ 的状态时，并非需要完整搜 索一遍 Ｎｅｔ（ｕｉ），若已存在 ｋｆ个好友在 ｔ 内在同一地 点（小于给定距离 ｄ）签到过，则可以停止搜索，此时 可判定 ｐ ｉ ａ 并非 Ｆ－Ｏｕｔｌｉｅｒ。 ２）历史邻近好友优先原则 在社会学领域研究中发现，人们在某一段时间 内往往与相同一群人存在较密集的交互［４］ 。 根据 上述社会学的发现，我们对每个用户维护一个邻近 好友的排序列表 Ｌｆ，用于记录历史邻近签到状况，最 近一次的邻近签到好友排在首位，每次搜索邻近好 友时同时更新列表次序可以较大概率快速搜索邻 近的签到好友，以排除 Ｈ⁃Ｏｕｔｌｉｅｒ，而不用随机遍历 Ｎｅｔ（ｕｉ）。 ３）基于时间触发的检测机制 当签到位置 ｐ ｉ ａ 在当前时刻检测为 Ｆ⁃Ｏｕｔｌｉｅｒ 后， 在后续的 Δｔ 内需要不断重新检测它的状态是否有 变化，但是当好友圈用户没有签到数据更新时，重 新检测会导致冗余计算。 因此，提出了一种基于时 间触发的检测机制。 每个用户 ｕ 维护一个触发列表 ｔｒｉｇｇｅｒ，触发列 表中每项表示为〈ｐ ｉ ａ 〉， 当用户 ｕ 更新签到数据时， 触发对 ｐ ｉ ａ 的 Ｆ－Ｏｕｔｌｉｅｒ 状态重检测。 可以看出，每 个触发项都存在一个有效期，即｜ ｔ ｃ －ｔ ａ ｜ ≤Δｔ，当前时 间 ｔ ｃ 与 Δｔ ａ 的时间差不大于 Δｔ，超过该时间差，触 发项自动失效。 基于时间触发的检测机制将连续异常检测转 化成了基于触发的检测，当有新签到数据时，才对 未过期的签到位置进行重新检测，大大减少了额外 的周期性重新检测成本。 算法 ２ 描述了采用优化策略的 Ｆ⁃Ｏｕｔｌｉｅｒ 的检 测过程，针对用户 ｕｉ的新签到位置 ｐ ｉ ｃ，首先执行 Ｈ⁃ 第 ５ 期 赵冠哲，等：移动社交网络异常签到在线检测算法 ·７５５·
·756· 智能系统学报 第12卷 Outlier检测，如1)所示，如果p.是一个H-Outlier,则 对比方法。算法1描述的基于历史位置的异常 继续检测p是否为F-Outlier.,如2)~12)所示。根据 检测算法记为H-Opt算法，算法2描述的基于好友 历史邻近好友优先原则，从L中由前向后搜索好 圈的异常检测算法记为F-Opt算法，对比方法记为 友，若存在邻近签到的好友，则插入好友邻居集合 LUE(lazy with update events)算法[s) Neia,并将该好友放置于L首位（见4）~7))，然后 评估方法。采用所有用户在单个窗口内异常 根据最少好友搜索机制，满足k,个好友，停止搜索 率来评估所提方法的有效性。实验结果取所有滑 (见8)~9))。搜索完一遍u,好友圈之后，认为满足 动窗口下的平均值。对于效率评估，通过变化各重 k条件，则认定为F-Outlier.,并将放入好友圈Net 要参数，采用单个窗口平均消耗的CPU时间和内存 (:)中每个用户的trigger列表中，如10)~12) 占用来评估算法的性能。每次窗口滑动一个新签 所示。 到位置。 算法2F-Outlier检测算法 5.1有效性评估 输入新的签到p、k、d; 首先，对H-Opt和F-Opt算法的有效性进行了 输出所有的F-Outlier 评估与分析。默认参数设置：d=300m,0=20,k= l)对于状态为H-Outlier的pd 4,k,=3,△t=3h,m=4。H-0pt与F-0pt的异常检测 2)if p .sta outlier then 结果如图1所示。图1(a)描述的是变化参数k对 3)forj取值1,2，…，lNet(u,)|do 不同算法的有效性影响。可以发现，随着k的增加， 4)L获取j后给u H-Opt和F-Opt检测出的异常率都呈线性增加，这 5)ifp与pa的距离≤d then 是因为增加邻居点数量阈值k会使较多的签到点被 6)将pa,添加到.Neim 认定为H-Outlier。由于F-Outlier基于H-Outlier,随 着H-Outlier数量的增加，F-Outlier也会有所上升， 7)将u插入到L首位 这与它们定义相符。同时还可以发现，随着k的增 8)if pi .Nei then 加，F-Opt算法与H-Opt算法在异常率检测上的差 9)p..sta更新为F-Inlier、break 异不断增大，即F-Opt的异常误判率不断降低。当 10)if p .Neira then k=7时，降低的异常率已达到1.09%，也就是说，F 1l)p.sta更新为F-0 utlier 0 utlier有效排除了30.27%的伪异常。 12)将p.添加到Nei(u:).trigger 4.0r H-Outlier l3)u,.trigger更新到Trigger 3.5 -F-Outlier 14)for每个pa∈Trigger do 3.0 15)iflt.t.|≤△t并且p.与p.的距离≤d then 2.5 16)将p.添加到pNei 2.0 17)if p Neifri,then 1.5 18)p。.sta更新为F-Inlier 1.0 19)将p.从w.trigger中删除 0.5 6 接下来，就要触发，的trigger列表，如13)~ 个 19)所示。每个触发项。，若仍在有效期内，且与p (a)参数k对异常率的影响 为邻居，则判断它邻居点的数量是否满足k,若满 2.6 -H-Outlier 足，则更新p。的状态，并将其移出u,的trigger列表 2.4 -F-Outlier (见17)~19)。 2.2 5实验评估 .20 1.8 实验平台配置为4.0GHz7-6700k处理器， 1.6 8GB内存，Windows7操作系统，所有算法由Java 1.4 实现。 数据集。实验数据集采用的是基于位置的移动社 10 15 20 25 30 个 交网络Gowalla真实数据集)。数据集中包括了 (b)参数W对异常率的影响 195591个用户，95万条好友关系，收集了2009年2月~ 图1。不同参数下的算法异常率 2010年10月之间的644万个签到位置数据。 Fig.1 Outlier rate under different parameters
Ｏｕｔｌｉｅｒ 检测，如 １）所示，如果 ｐ ｉ ｃ 是一个 Ｈ⁃Ｏｕｔｌｉｅｒ，则 继续检测ｐ ｉ ｃ是否为 Ｆ⁃Ｏｕｔｌｉｅｒ，如 ２） ～ １２）所示。 根据 历史邻近好友优先原则，从 Ｌｆ 中由前向后搜索好 友，若存在邻近签到的好友，则插入好友邻居集合 Ｎｅｉ ｆｒｉ，并将该好友放置于 Ｌｆ首位（见 ４） ～ ７）），然后 根据最少好友搜索机制，满足 ｋｆ 个好友，停止搜索 （见 ８） ～９））。 搜索完一遍 ｕｉ好友圈之后，认为满足 ｋｆ条件，则认定为 Ｆ⁃Ｏｕｔｌｉｅｒ，并将放入好友圈 Ｎｅｔ （ｕｉ） 中每个用户的 ｔｒｉｇｇｅｒ 列表中， 如 １０） ～ １２） 所示。 算法 ２ Ｆ⁃Ｏｕｔｌｉｅｒ 检测算法 输入 新的签到 ｐ ｉ ｃ 、ｋｆ、ｄ； 输出 所有的 Ｆ⁃Ｏｕｔｌｉｅｒ。 １）对于状态为 Ｈ⁃Ｏｕｔｌｉｅｒ 的 ｐ ｉ ｃ ２）ｉｆ ｐ ｉ ｃ ．ｓｔａ 为 ｏｕｔｌｉｅｒ ｔｈｅｎ ３）ｆｏｒ ｊ 取值 １，２，…， Ｎｅｔ（ｕｉ） ｄｏ ４） Ｌｆ获取 ｊ 后给 ｕｊ ５）ｉｆ ｐ ｉ ｃ 与 ｐ ｉ ｃ ±△ｔ 的距离≤ｄ ｔｈｅｎ ６） 将 ｐ ｉ ｃ ±△ｔ 添加到 ｐ ｉ ｃ ．Ｎｅｉ ｆｒｉ ７）将 ｕｊ插入到 Ｌｆ首位 ８）ｉｆ ｐ ｉ ｃ ．Ｎｅｉ ｆｒｉ ≥ｋｆ ｔｈｅｎ ９） ｐ ｉ ｃ ．ｓｔａ 更新为 Ｆ⁃Ｉｎｌｉｅｒ、ｂｒｅａｋ １０）ｉｆ ｐ ｉ ｃ ．Ｎｅｉ ｆｒｉ ＜ｋｆ ｔｈｅｎ １１） ｐ ｉ ｃ ．ｓｔａ 更新为 Ｆ⁃Ｏｕｔｌｉｅｒ １２）将 ｐ ｉ ｃ 添加到 Ｎｅｉ（ｕｉ）．ｔｒｉｇｇｅｒ １３） ｕｉ ．ｔｒｉｇｇｅｒ 更新到 Ｔｒｉｇｇｅｒ １４）ｆｏｒ 每个 ｐ ｉ ａ ∈ Ｔｒｉｇｇｅｒ ｄｏ １５）ｉｆ ｔ ａ －ｔ ｃ ≤ △ｔ 并且 ｐ ｉ ｃ 与 ｐ ｊ ａ 的距离≤ｄ ｔｈｅｎ １６）将 ｐ ｉ ｃ 添加到 ｐ ｉ ａ ．Ｎｅｉ ｆｒｉ １７）ｉｆ ｐ ｉ ａ ．Ｎｅｉｆｒｉ ≥ｋｆ ｔｈｅｎ １８） ｐ ｉ ａ ．ｓｔａ 更新为 Ｆ⁃Ｉｎｌｉｅｒ １９）将 ｐ ｉ ａ 从 ｕｊ ．ｔｒｉｇｇｅｒ 中删除 接下来，就要触发 ｕｉ 的 ｔｒｉｇｇｅｒ 列表，如 １３） ～ １９）所示。 每个触发项 ｐ ｊ ａ ，若仍在有效期内，且与 ｐ ｉ ｃ 为邻居，则判断它邻居点的数量是否满足 ｋｆ，若满 足，则更新 ｐ ｊ ａ 的状态，并将其移出 ｕｉ的 ｔｒｉｇｇｅｒ 列表 （见 １７） ～１９））。 ５ 实验评估 实验平台配置为 ４． ０ ＧＨｚ ｉ７⁃６７００ｋ 处理器， ８ ＧＢ内存， Ｗｉｎｄｏｗｓ７ 操作系统， 所有算法由 Ｊａｖａ 实现。 数据集。 实验数据集采用的是基于位置的移动社 交网络 Ｇｏｗａｌｌａ 真实数据集［１８］ 。 数据集中包括了 １９５ ５９１个用户，９５ 万条好友关系，收集了２００９ 年２ 月～ ２０１０ 年 １０ 月之间的 ６４４ 万个签到位置数据。 对比方法。 算法 １ 描述的基于历史位置的异常 检测算法记为 Ｈ⁃Ｏｐｔ 算法，算法 ２ 描述的基于好友 圈的异常检测算法记为 Ｆ⁃Ｏｐｔ 算法，对比方法记为 ＬＵＥ（ｌａｚｙ ｗｉｔｈ ｕｐｄａｔｅ ｅｖｅｎｔｓ）算法［１３］ 。 评估方法。 采用所有用户在单个窗口内异常 率来评估所提方法的有效性。 实验结果取所有滑 动窗口下的平均值。 对于效率评估，通过变化各重 要参数，采用单个窗口平均消耗的 ＣＰＵ 时间和内存 占用来评估算法的性能。 每次窗口滑动一个新签 到位置。 ５．１ 有效性评估 首先，对 Ｈ⁃Ｏｐｔ 和 Ｆ⁃Ｏｐｔ 算法的有效性进行了 评估与分析。 默认参数设置：ｄ ＝ ３００ ｍ，ｗ ＝ ２０，ｋ ＝ ４，ｋｆ ＝ ３，Δｔ ＝ ３ ｈ，ｍ ＝ ４。 Ｈ⁃Ｏｐｔ 与 Ｆ⁃Ｏｐｔ 的异常检测 结果如图 １ 所示。 图 １（ａ）描述的是变化参数 ｋ 对 不同算法的有效性影响。 可以发现，随着 ｋ 的增加， Ｈ⁃Ｏｐｔ 和 Ｆ⁃Ｏｐｔ 检测出的异常率都呈线性增加，这 是因为增加邻居点数量阈值 ｋ 会使较多的签到点被 认定为 Ｈ⁃Ｏｕｔｌｉｅｒ。 由于 Ｆ⁃Ｏｕｔｌｉｅｒ 基于 Ｈ⁃Ｏｕｔｌｉｅｒ，随 着 Ｈ⁃Ｏｕｔｌｉｅｒ 数量的增加，Ｆ⁃Ｏｕｔｌｉｅｒ 也会有所上升， 这与它们定义相符。 同时还可以发现，随着 ｋ 的增 加，Ｆ⁃Ｏｐｔ 算法与 Ｈ⁃Ｏｐｔ 算法在异常率检测上的差 异不断增大，即 Ｆ⁃Ｏｐｔ 的异常误判率不断降低。 当 ｋ ＝ ７时，降低的异常率已达到 １．０９％，也就是说，Ｆ⁃ Ｏｕｔｌｉｅｒ 有效排除了 ３０．２７％的伪异常。 （ａ）参数 ｋ 对异常率的影响 （ｂ）参数 Ｗ 对异常率的影响 图 １ 不同参数下的算法异常率 Ｆｉｇ．１ Ｏｕｔｌｉｅｒ ｒａｔｅ ｕｎｄｅｒ ｄｉｆｆｅｒｅｎｔ ｐａｒａｍｅｔｅｒｓ ·７５６· 智 能 系 统 学 报 第 １２ 卷
第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
图 １（ｂ）显示的是变化参数 Ｗ 对不同算法的有 效性影响。 由图 １ 可以看出，随着 Ｗ 的增大，异常 率不断下降。 这是因为当增大 Ｗ 时，邻居点的历史 签到时间范围也随之增加，从而签到的邻居点数量 也会相应增加，使 Ｈ⁃Ｏｕｔｌｉｅｒ 和 Ｆ⁃Ｏｕｔｌｉｅｒ 的异常率随 之减少，这也与它们定义相符。 同时可以看出，Ｆ⁃ Ｏｐｔ 的异常率明显低于 Ｈ⁃Ｏｐｔ 算法，这也证明了 Ｆ⁃ Ｏｕｔｌｉｅｒ 检测的有效性。 为了更好地考察 Ｆ⁃Ｏｐｔ 算法的有效性，进一步 对 Ｆ⁃Ｏｐｔ 算法进行了评估。 图 ２ 是 ｋｆ、Δｔ 和 ｍ 在不 同组合时，Ｆ⁃Ｏｕｔｌｉｅｒ 相比 Ｈ⁃Ｏｕｔｌｉｅｒ 降低的异常率情 况。 如图 ２（ａ）所示，当 ｋｆ 值从 ２ 变化到 ６ 时，考虑 间接好友的 Ｆ⁃Ｏｕｔｌｉｅｒ 进一步降低了 Ｈ⁃Ｏｕｔｌｉｅｒ 的异 常率。 共同好友的要求越低（ｍ 值越小），异常的降 低率越高，即伪异常越少，当 ｍ ＝ ２ 时，相对仅考虑 直接好友，Ｆ⁃Ｏｕｔｌｉｅｒ 异常的降低率平均提高了 ８％。 图 ２（ｂ）展示的是当 ｋｆ ＝ ４ 时，Δｔ 从 １ ～ ５ 变化，对算 法异常降低率的影响。 可以发现，随着 Δｔ 的增加， 异常的降低率在不断增大，这是因为搜索的时间区 间增加，在时间区间内邻近签到好友的数量也在增 加。 同样地，考虑好友圈的 Ｆ⁃Ｏｕｔｌｉｅｒ 减少了更多伪 异常。 在 Δｔ ≤ ４ 时，Ｆ⁃Ｏｕｔｌｉｅｒ 减少的异常率变化不 大，这也说明大多邻近好友的签到是在较短时间差 内完成。 （ａ）参数 ｋｆ、ｍ 对异常降低率的影响 （ｂ）参数 Δｔ、ｍ 对异常降低率的影响 图 ２ 不同参数对 Ｆ⁃Ｏｐｔ 异常降低率的影响 Ｆｉｇ． ２ Ｆ⁃Ｏｐｔ ｏｕｔｌｉｅｒ ｄｅｃｒｅａｓｉｎｇ ｒａｔｅ ｗ．ｒ．ｔ． ｄｉｆｆｅｒｅｎｔ ｐａｒａｍｅｔｅｒｓ ５．２ 效率评估 本节评估了滑动窗口 Ｗ 和邻居点数量 ｋ 对 Ｈ⁃ Ｏｐｔ 和 Ｆ⁃Ｏｐｔ 算法的消耗时间和内存的影响，并与 ＬＵＥ 算法进行了对比分析。 默认参数：ｄ ＝ ３００，ｋｆ ＝ ３， Δｔ ＝ ３ ｈ，ｍ ＝ ４。 在图 ３（ａ）中，固定 ｋ ＝ ４，Ｗ 从 １０ 变化到 ３０，随 着 Ｗ 的增加，３ 个算法消耗的时间都有所增加，这是 因为窗口增加，都需要增加对异常点邻居搜索范 围，而 ＬＵＥ 需要计算当前签到点与窗口内所有签到 点的距离，所以导致了耗时较长。 同时，随着窗口 增长，Ｈ⁃Ｏｕｔｌｉｅｒ 和 Ｆ⁃Ｏｕｔｌｉｅｒ 数量反而越少，虽然搜 索邻居的范围增加导致了总消耗时间增加，但是由 于采用了优化的邻居搜索机制和最少邻居搜索机 制，仅有异常点增加了邻居搜索，因此，消耗的 ＣＰＵ 时间 增长越来越缓慢，而 Ｆ⁃Ｏｐｔ 算法需要再次检测的异常点 变少也使得消耗的时间越来越少。 相比于 ＬＵＥ，Ｆ⁃Ｏｐｔ 和Ｈ⁃Ｏｐｔ 分别平均提升了２．３４、２．４５ 倍效率。 在图 ３（ｂ） 中固定 Ｗ＝ ２０，ｋ 从 ２ 变化到 ６。 随着 ｋ 的增加，３ 个 算法消耗的 ＣＰＵ 时间也逐渐增加。 虽然 Ｆ⁃Ｏｐｔ 算 法需要重新检测更多 Ｈ⁃Ｏｕｔｌｉｅｒ 异常，但 Ｆ⁃Ｏｐｔ 算法 并没有快速增加时间消耗，仅平均增加了 ０．００２ ｍｓ。 这也体现了我们提出的基于触发的优化检测策略 的作用。 相比于 ＬＵＥ，Ｆ⁃Ｏｐｔ 和 Ｈ⁃Ｏｐｔ 分别平均提 升了 ２．３１、２．３６ 倍效率。 （ａ）参数 Ｗ 对 ＣＰＵ 消耗时间的影响 （ｂ）参数 ｋ 对 ＣＰＵ 消耗时间的影响 图 ３ 不同参数下的算法消耗的时间 Ｆｉｇ．３ ＣＰＵ ｔｉｍｅ ｗ．ｒ．ｔ． ｄｉｆｆｅｒｅｎｔ ｐａｒａｍｅｔｅｒｓ 第 ５ 期 赵冠哲，等：移动社交网络异常签到在线检测算法 ·７５７·
·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
在内存方面，如图 ４ 所示，随着 Ｗ 的增加，３ 个 算法消耗的内存也逐渐增加。 这是因为随着滑动 窗口的增长， 窗口内存储的签到点也随之增多。 ＬＵＥ 算法需要储存窗口存储所有签到点的邻居点， 消耗的内存较多。 Ｈ⁃Ｏｐｔ 和 Ｆ⁃Ｏｐｔ 消耗内存较少，这 是因为采用了优化的邻居搜索机制和最少邻居搜 索机制。 由于增加了 Ｆ⁃Ｏｕｔｌｉｅｒ 好友圈的邻近签到 存储，Ｆ⁃Ｏｐｔ 略高于 Ｈ⁃Ｏｐｔ。 图 ４ 参数 Ｗ 和 ｋ 变化下内存的消耗情况 Ｆｉｇ．４ Ｍｅｍｏｒｙ ｗ．ｒ．ｔ． ｐａｒａｍｅｔｅｒ Ｗ ａｎｄ ｋ 随着 ｋ 的增加，３ 个算法消耗的内存也在增加。 这是因为所有算法都需要寻找更多的邻居。 Ｈ⁃Ｏｐｔ 和 Ｆ⁃Ｏｐｔ 消耗内存增长缓慢，这是因为 Ｈ⁃Ｏｐｔ 算法 采用最少邻居点搜索机制，随着 ｋ 值的增加，在 Ｈ⁃ Ｏｐｔ 算法中需要存储的自身签到点也随之增加。 相 比于 ＬＵＥ，Ｆ⁃Ｏｐｔ 和 Ｈ⁃Ｏｐｔ 分别平均减少了 ３０％和 ３２％的内存消耗。 接下来，进一步评估了参数 ｍ、ｋｆ和 Δｔ 对 Ｆ⁃Ｏｐｔ 算法效率的影响。 我们测试了变化 ｋｆ和 Δｔ 对多个 ｍ 值下 Ｆ⁃Ｏｐｔ 算法效率的影响，如图 ５ 所示。 固定 Ｗ＝ ２０，ｋ ＝ ４，ｄ ＝ ３００，在图 ５（ａ）中固定 Δｔ ＝ ３ ｈ，在 图 ５ （ｂ）中固定 ｋｆ ＝ ３，可以看出，随着 ｋｆ 和 Δｔ 增加， Ｆ⁃Ｏｐｔ 消耗的 ＣＰＵ 时间都逐渐增加。 这是因为 ｋｆ 增加，使得邻近签到好友搜索的个数增加； Δｔ 增加 使得时间区间增加。 因此消耗的 ＣＰＵ 时间也要相 应增加。 同时也发现，不考虑间接好友时的 Ｆ⁃Ｏｐｔ 算法消耗最多时间，考虑间接好友时共同好友数量 ｍ 值越少，使用的检测时间越少。 这是因为 ｍ 值越 小，Ｎｅｔ（ｕ）集合越大，虽然搜索范围增加了，伪异常 也增多了，由于我们采用了历史邻近好友优先原则 和基于触发的检测机制，可快速发现伪异常，有效 提升了算法检测效率。 结合图 ２ 的实验结果可以说 明，在移动社交网络异常签到检测中考虑用户间接 好友的必要性和优势。 （ａ）参数 ｋｆ 和 ｍ （ｂ）参数 Δｔ 和 ｍ 图 ５ 不同参数变化的算法 ＣＰＵ 时间 Ｆｉｇ．５ ＣＰＵ ｔｉｍｅ ｗ．ｒ．ｔ． ｄｉｆｆｅｒｅｎｔ ｐａｒａｍｅｔｅｒｓ ６ 结束语 本文提出了一种针对移动社交网络异常签到 位置的在线检测方法。 基于距离的异常检测，定义 了基于历史位置和基于好友圈的两种异常签到模 型。 然后，针对两种异常签到模型，分别提出了优 化的检测算法，从签到位置的状态模型、优化的邻 居搜索机制和基于时间触发的检测机制方面有效 降低了检测时间。 最后，在真实的移动社交网络用 户签到数据集上，验证了所提模型与算法的有效性 和效率。 下一步将结合用户的操作行为进一步研 究有效的移动社交网络异常检测方法。 参考文献： ［１］於志文， 周兴社， 郭斌． 移动社交网络中的感知计算模 型、平台与实践［Ｊ］． 中国计算机学会通讯，２０１２，８（５）： １５－２１． ［ ２ ］ ＷＥ ＡＲＥ ＳＯＣＩＡＬ ＬＴＤ． ＤＩＧＩＴＡＬ ＩＮ ２０１６ ［ ＥＢ／ ＯＬ］． ［２０１７⁃０３⁃１０］． ｈｔｔｐ： ／ ／ ｗｅａｒｅｓｏｃｉａｌ． ｃｏｍ／ ｕｋ ／ ｓｐｅｃｉａｌ⁃ｒｅｐｏｒｔｓ／ ｄｉｇｉｔａｌ⁃ｉｎ－２０１６． ［３ ］ ＺＨＥＮＧ Ｙｕ， ＸＩＥ Ｘ． Ｌｏｃａｔｉｏｎ⁃ｂａｓｅｄ ｓｏｃｉａｌ ｎｅｔｗｏｒｋｓ： ｌｏｃａｔｉｏｎｓ ［ Ｊ］． Ｃｏｍｐｕｔｉｎｇ ｗｉｔｈ ｓｐａｔｉａｌ ｔｒａｊｅｃｔｏｒｉｅｓ， ２０１１： ２７７－３０８． ·７５８· 智 能 系 统 学 报 第 １２ 卷
第5期 赵冠哲，等：移动社交网络异常签到在线检测算法 ·759· [4]萧世掄.基于位置服务与人类活动的关系和影响[J].中 [15 LEE J G,HAN J,LI X.Trajectory outlier detection: 国计算机学会通讯，2010,6(6)：30-35. a partition-and-detect framework[C]//International Confe- [5]张玉清，吕少卿，范丹.在线社交网络中异常帐号检测 rence on Data Engineering.Cancun,Mexico,2008: 方法研究[J].计算机学报，2015,38(10)：2011-2027. 140-149. ZHANG Yuqing,LV Shaoqing,FAN Dan.Anomaly detection [16]BU Yingyi,CHEN L.FU W C,et al.Efficient anomaly in online social networks[].Chinese journal of computers, monitoring over moving object trajectory streams[C]// 2015,38(10):2011-2027. ACM SIGKDD International Conference on Knowledge [6]CHO E.MYERS S A,LESKOVEC J.Friendship and Discovery and Data Mining.Paris.France,2009: mobility:user movement in location-based social networks 159-168. [C ]//ACM SIGKDD International Conference on [17]YU Yanwei,CAO Lei,RUNDENSTEINER E A,et al. Knowledge Discovery and Data Mining.San Diego,USA, Detecting moving object outliers in massive-scale 2011:1082-1090. trajectory streams C ]//ACM SIGKDD International [7]KNORR E M,NG R T.Algorithms for mining distance- Conference on Knowledge Discovery and Data Mining. based outliers in large datasets [C]//International New York,USA,2014:422-431. Conference on Very Large Data Bases.New York,USA, 1998:392-403. [18]LI Zhenhui,WANG J,Han J.Mining event periodicity [8]KNORR E M,NG R T,TUCAKOV V.Distance-based from incomplete observations C ]/ACM SIGKDD outliers:algorithms and applications [J].Vldb journal, International Conference on Knowledge Discovery and 2000,8(3/4):237-253. Data Mining.Beijing,China,2012:444-452. [9 RAMASWAMY S,RASTOGI R,SHIM K.Efficient 作者简介： algorithms for mining outliers from large data sets[C]/ 赵冠哲，男，1992年生，硕士研究 ACM SIGMOD International Conference on Management of 生，主要研究方向为数据挖掘。 Data.Dallas,USA,2000:427-438. [10]BREUNIG MARKUS M.LOF:identifying density-based local outliers[J].ACM sigmod record,2000,29(2): 93-104. [11]YANG D,RUNDENSTEINER E A,Ward M O.Neighbor- based pattern detection for windows over streaming data 齐建鹏，男，1992年生，硕士研究 [C]//International Conference on Extending Database 生，主要研究方向为数据挖掘。 Technology:Advances in Database Technology.Saint Petersburg,Russia,2009:529-540. [12 ANGIULLI F,FASSETTI F.Detecting distance-based outliers in streams of data C]//Sixteenth ACM Conference on Conference on Information and Knowledge Management.Lisboa,Portugal,2007:811-820. 于彦伟，男，1986年生，讲师，博士 [13]KONTAKI M,GOUNARIS A.PAPADOPOULOS A N,et 主要研究方向为时空数据挖掘、流式数 al.Continuous monitoring of distance-based outliers over data streams[C]//IEEE,International Conference on 据处理、分布式计算。主持国家自然科 学基金青年基金1项，参与国家自然科 Data Engineering.Hannover,Germany,2011:135-146. 学基金面上项目1项，山东省重点研发 [14]CAO L,YANG D,WANG Q,et al.Scalable distance- 计划项目1项。发表学术论文30余篇。 based outlier detection over high-volume data streams [C]//International Conference on Data Engineering. Chicago,USA,2014:76-87
［４］萧世埨． 基于位置服务与人类活动的关系和影响［Ｊ］． 中 国计算机学会通讯， ２０１０，６（６）： ３０－３５． ［５］张玉清， 吕少卿， 范丹． 在线社交网络中异常帐号检测 方法研究［Ｊ］． 计算机学报， ２０１５， ３８（１０）： ２０１１－２０２７． ＺＨＡＮＧ Ｙｕｑｉｎｇ，ＬＶ Ｓｈａｏｑｉｎｇ，ＦＡＮ Ｄａｎ． Ａｎｏｍａｌｙ ｄｅｔｅｃｔｉｏｎ ｉｎ ｏｎｌｉｎｅ ｓｏｃｉａｌ ｎｅｔｗｏｒｋｓ［Ｊ］． Ｃｈｉｎｅｓｅ ｊｏｕｒｎａｌ ｏｆ ｃｏｍｐｕｔｅｒｓ， ２０１５， ３８（１０）： ２０１１－２０２７． ［６ ］ ＣＨＯ Ｅ， ＭＹＥＲＳ Ｓ Ａ， ＬＥＳＫＯＶＥＣ Ｊ． Ｆｒｉｅｎｄｓｈｉｐ ａｎｄ ｍｏｂｉｌｉｔｙ：ｕｓｅｒ ｍｏｖｅｍｅｎｔ ｉｎ ｌｏｃａｔｉｏｎ⁃ｂａｓｅｄ ｓｏｃｉａｌ ｎｅｔｗｏｒｋｓ ［ Ｃ ］ ／ ／ ＡＣＭ ＳＩＧＫＤＤ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｋｎｏｗｌｅｄｇｅ Ｄｉｓｃｏｖｅｒｙ ａｎｄ Ｄａｔａ Ｍｉｎｉｎｇ． Ｓａｎ Ｄｉｅｇｏ， ＵＳＡ， ２０１１： １０８２－１０９０． ［７］ ＫＮＯＲＲ Ｅ Ｍ， ＮＧ Ｒ Ｔ． Ａｌｇｏｒｉｔｈｍｓ ｆｏｒ ｍｉｎｉｎｇ ｄｉｓｔａｎｃｅ⁃ ｂａｓｅｄ ｏｕｔｌｉｅｒｓ ｉｎ ｌａｒｇｅ ｄａｔａｓｅｔｓ ［ Ｃ ］ ／ ／ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｖｅｒｙ Ｌａｒｇｅ Ｄａｔａ Ｂａｓｅｓ． Ｎｅｗ Ｙｏｒｋ， ＵＳＡ， １９９８： ３９２－４０３． ［８］ ＫＮＯＲＲ Ｅ Ｍ， ＮＧ Ｒ Ｔ， ＴＵＣＡＫＯＶ Ｖ． Ｄｉｓｔａｎｃｅ － ｂａｓｅｄ ｏｕｔｌｉｅｒｓ： ａｌｇｏｒｉｔｈｍｓ ａｎｄ ａｐｐｌｉｃａｔｉｏｎｓ ［ Ｊ ］． Ｖｌｄｂ ｊｏｕｒｎａｌ， ２０００， ８（３ ／ ４）： ２３７－２５３． ［９ ］ ＲＡＭＡＳＷＡＭＹ Ｓ， ＲＡＳＴＯＧＩ Ｒ， ＳＨＩＭ Ｋ． Ｅｆｆｉｃｉｅｎｔ ａｌｇｏｒｉｔｈｍｓ ｆｏｒ ｍｉｎｉｎｇ ｏｕｔｌｉｅｒｓ ｆｒｏｍ ｌａｒｇｅ ｄａｔａ ｓｅｔｓ ［ Ｃ］ ／ ／ ＡＣＭ ＳＩＧＭＯＤ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｍａｎａｇｅｍｅｎｔ ｏｆ Ｄａｔａ． Ｄａｌｌａｓ， ＵＳＡ， ２０００： ４２７－４３８． ［１０］ ＢＲＥＵＮＩＧ ＭＡＲＫＵＳ Ｍ． ＬＯＦ： ｉｄｅｎｔｉｆｙｉｎｇ ｄｅｎｓｉｔｙ－ｂａｓｅｄ ｌｏｃａｌ ｏｕｔｌｉｅｒｓ［ Ｊ］． ＡＣＭ ｓｉｇｍｏｄ ｒｅｃｏｒｄ， ２０００， ２９ （ ２）： ９３－１０４． ［１１］ＹＡＮＧ Ｄ， ＲＵＮＤＥＮＳＴＥＩＮＥＲ Ｅ Ａ， Ｗａｒｄ Ｍ Ｏ． Ｎｅｉｇｈｂｏｒ⁃ ｂａｓｅｄ ｐａｔｔｅｒｎ ｄｅｔｅｃｔｉｏｎ ｆｏｒ ｗｉｎｄｏｗｓ ｏｖｅｒ ｓｔｒｅａｍｉｎｇ ｄａｔａ ［Ｃ ］ ／ ／ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｅｘｔｅｎｄｉｎｇ Ｄａｔａｂａｓｅ Ｔｅｃｈｎｏｌｏｇｙ： Ａｄｖａｎｃｅｓ ｉｎ Ｄａｔａｂａｓｅ Ｔｅｃｈｎｏｌｏｇｙ． Ｓａｉｎｔ Ｐｅｔｅｒｓｂｕｒｇ， Ｒｕｓｓｉａ， ２００９： ５２９－５４０． ［ １２ ］ ＡＮＧＩＵＬＬＩ Ｆ， ＦＡＳＳＥＴＴＩ Ｆ． Ｄｅｔｅｃｔｉｎｇ ｄｉｓｔａｎｃｅ⁃ｂａｓｅｄ ｏｕｔｌｉｅｒｓ ｉｎ ｓｔｒｅａｍｓ ｏｆ ｄａｔａ ［ Ｃ ］ ／ ／ Ｓｉｘｔｅｅｎｔｈ ＡＣＭ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｉｎｆｏｒｍａｔｉｏｎ ａｎｄ Ｋｎｏｗｌｅｄｇｅ Ｍａｎａｇｅｍｅｎｔ． Ｌｉｓｂｏａ， Ｐｏｒｔｕｇａｌ， ２００７：８１１－８２０． ［１３］ＫＯＮＴＡＫＩ Ｍ， ＧＯＵＮＡＲＩＳ Ａ， ＰＡＰＡＤＯＰＯＵＬＯＳ Ａ Ｎ， ｅｔ ａｌ． Ｃｏｎｔｉｎｕｏｕｓ ｍｏｎｉｔｏｒｉｎｇ ｏｆ ｄｉｓｔａｎｃｅ－ｂａｓｅｄ ｏｕｔｌｉｅｒｓ ｏｖｅｒ ｄａｔａ ｓｔｒｅａｍｓ ［ Ｃ］ ／ ／ ＩＥＥＥ， Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｄａｔａ Ｅｎｇｉｎｅｅｒｉｎｇ． Ｈａｎｎｏｖｅｒ， Ｇｅｒｍａｎｙ， ２０１１：１３５－１４６． ［１４］ ＣＡＯ Ｌ， ＹＡＮＧ Ｄ， ＷＡＮＧ Ｑ， ｅｔ ａｌ． Ｓｃａｌａｂｌｅ ｄｉｓｔａｎｃｅ⁃ ｂａｓｅｄ ｏｕｔｌｉｅｒ ｄｅｔｅｃｔｉｏｎ ｏｖｅｒ ｈｉｇｈ⁃ｖｏｌｕｍｅ ｄａｔａ ｓｔｒｅａｍｓ ［ Ｃ ］ ／ ／ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｄａｔａ Ｅｎｇｉｎｅｅｒｉｎｇ． Ｃｈｉｃａｇｏ，ＵＳＡ， ２０１４： ７６－８７． ［１５ ］ ＬＥＥ Ｊ Ｇ， ＨＡＮ Ｊ， ＬＩ Ｘ． Ｔｒａｊｅｃｔｏｒｙ ｏｕｔｌｉｅｒ ｄｅｔｅｃｔｉｏｎ： ａ ｐａｒｔｉｔｉｏｎ⁃ ａｎｄ⁃ｄｅｔｅｃｔ ｆｒａｍｅｗｏｒｋ［Ｃ］ ／ ／ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅ⁃ ｒｅｎｃｅ ｏｎ Ｄａｔａ Ｅｎｇｉｎｅｅｒｉｎｇ． Ｃａｎｃｕｎ， Ｍｅｘｉｃｏ， ２００８： １４０－１４９． ［１６］ ＢＵ Ｙｉｎｇｙｉ， ＣＨＥＮ Ｌ， ＦＵ Ｗ Ｃ， ｅｔ ａｌ． Ｅｆｆｉｃｉｅｎｔ ａｎｏｍａｌｙ ｍｏｎｉｔｏｒｉｎｇ ｏｖｅｒ ｍｏｖｉｎｇ ｏｂｊｅｃｔ ｔｒａｊｅｃｔｏｒｙ ｓｔｒｅａｍｓ ［ Ｃ］ ／ ／ ＡＣＭ ＳＩＧＫＤＤ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｋｎｏｗｌｅｄｇｅ Ｄｉｓｃｏｖｅｒｙ ａｎｄ Ｄａｔａ Ｍｉｎｉｎｇ． Ｐａｒｉｓ， Ｆｒａｎｃｅ， ２００９： １５９－１６８． ［１７］ ＹＵ Ｙａｎｗｅｉ， ＣＡＯ Ｌｅｉ， ＲＵＮＤＥＮＳＴＥＩＮＥＲ Ｅ Ａ， ｅｔ ａｌ． Ｄｅｔｅｃｔｉｎｇ ｍｏｖｉｎｇ ｏｂｊｅｃｔ ｏｕｔｌｉｅｒｓ ｉｎ ｍａｓｓｉｖｅ⁃ｓｃａｌｅ ｔｒａｊｅｃｔｏｒｙ ｓｔｒｅａｍｓ ［ Ｃ ］ ／ ／ ＡＣＭ ＳＩＧＫＤＤ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｋｎｏｗｌｅｄｇｅ Ｄｉｓｃｏｖｅｒｙ ａｎｄ Ｄａｔａ Ｍｉｎｉｎｇ． Ｎｅｗ Ｙｏｒｋ， ＵＳＡ， ２０１４： ４２２－４３１． ［１８］ ＬＩ Ｚｈｅｎｈｕｉ， ＷＡＮＧ Ｊ， Ｈａｎ Ｊ． Ｍｉｎｉｎｇ ｅｖｅｎｔ ｐｅｒｉｏｄｉｃｉｔｙ ｆｒｏｍ ｉｎｃｏｍｐｌｅｔｅ ｏｂｓｅｒｖａｔｉｏｎｓ ［ Ｃ ］ ／ ／ ＡＣＭ ＳＩＧＫＤＤ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｋｎｏｗｌｅｄｇｅ Ｄｉｓｃｏｖｅｒｙ ａｎｄ Ｄａｔａ Ｍｉｎｉｎｇ． Ｂｅｉｊｉｎｇ， Ｃｈｉｎａ， ２０１２： ４４４－４５２． 作者简介： 赵冠哲，男，１９９２ 年生，硕士研究 生，主要研究方向为数据挖掘。 齐建鹏，男，１９９２ 年生，硕士研究 生，主要研究方向为数据挖掘。 于彦伟，男，１９８６ 年生，讲师，博士， 主要研究方向为时空数据挖掘、流式数 据处理、分布式计算。 主持国家自然科 学基金青年基金 １ 项，参与国家自然科 学基金面上项目 １ 项，山东省重点研发 计划项目 １ 项。 发表学术论文 ３０ 余篇。 第 ５ 期 赵冠哲，等：移动社交网络异常签到在线检测算法 ·７５９·