第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,指出，２０１６ 年全球社交网络用户约 １９．７ 亿，占全球 总人口的 ２７％。 ＬＢＳＮ 中海量带有位置信息的社会 媒体数据可被用于各类挖掘应用研究，如挖掘用户 兴趣偏 好、 好 友 推 荐、 兴 趣 点 推 荐、 热 点 路 径 推 荐等［３］ 。 移动社交网络正逐渐改变着人们的生活方式 和生活习惯，给人类社会带来前所未有的变革以及 巨大的经济收益［４］ 。 同时它也吸引了一些不法者 盗取用户账号及信息进行各种恶意行为，影响了用 户的正常使用，损害了用户利益，甚至给用户带来 了巨大的经济损失。 因此，面向移动社交网络，追 踪用户的历史签到位置数据，从用户移动行为特征 视角，对用户状态进行在线异常检测，这对于移动 社交网络的安全、用户的隐私保护等具有重要意义。 针对移动社交网络异常账号的检测问题，学术 界和工业界都提出了大量检测方案［５］ ，主要包括基 于行为特征的检测、基于内容的检测、基于图的检 测和无监督学习的异常检测方法等。 而针对移动 社交网络中签到位置数据异常检测研究还比较少。 本文从用户的移动位置特征视角对异常签到位置 进行检测，针对移动社交网络用户异常签到检测问 题，提出了一类基于签到位置的在线异常检测方 法。 首先，在基于距离的异常检测基础上，提出了 两种异常签到模型，即基于历史位置的异常签到 （ｈｉｓｔｏｒｙ ｌｏｃａｔｉｏｎ ｂａｓｅｄ ｏｕｔｌｉｅｒ，Ｈ⁃Ｏｕｔｌｉｅｒ）和基于好友 圈的异常签到（ ｆｒｉｅｎｄｓｈｉｐ ｂａｓｅｄ ｏｕｔｌｉｅｒ，Ｆ⁃Ｏｕｔｌｉｅｒ）； 其次，针对 Ｈ⁃Ｏｕｔｌｉｅｒ，提出了一种优化的检测算法 Ｈ⁃Ｏｐｔ，利用优化的检测状态与邻居搜索机制降低 检测时间；然后，针对 Ｆ⁃Ｏｕｔｌｉｅｒ，基于提出的 ３ 个优 化策略，提出了一种基于触发的优化检测算法 Ｆ⁃ Ｏｐｔ，将连续在线异常检测转化成了基于触发的异常 检测方式，本文采用滑动窗口技术实现 Ｈ⁃Ｏｐｔ 和 Ｆ⁃ Ｏｐｔ；最后，在真实的移动社交网络用户签到数据集 上，验证了所提算法的有效性和效率。 在移动社交网络中用户往往会在新地点进行 签到或登录，所以 Ｈ⁃Ｏｕｔｌｉｅｒ 检测到的异常签到地点 很有可能并非真正的异常。 为排除这些伪异常状 况，本文提出了好友圈的概念和基于好友圈的异常 签到模型 Ｆ⁃Ｏｕｔｌｉｅｒ，这是因为在移动社交网络中 ５０％ ～７０％的行为可由周期行为解释，还有 １０％ ～ ３０％行为可根据好友关系行为解释［６］ 。 也就是说， 在移动社交网络中用户往往与认识的好友共同出 现在不经常签到的地点，如朋友聚餐、商务活动或 者公务出差等。 针对这些伪异常，我们通过检测好 友圈中好友签到位置来判断用户的签到是否为真 正的异常签到。 １ 相关工作 Ｋｎｏｒｒ 和 Ｎｇ ［７］最早提出了基于距离的空间异常 （ＤＢ⁃Ｏｕｔｌｉｅｒ）检测问题。 给定一个数据集合，若某 数据点的邻域内的数据个数小于给定阈值，则该数 据点为基于距离的异常点。 之后，Ｋｎｏｒｒ 等［８］ 将基 于距离的异常模型应用到时空轨迹数据异常检测 中。 Ｒａｍａｓｗａｍｙ 等［９］ 提出了一种基于 ｋ 近邻的异 常定义，根据数据点到第 ｋ 近邻的距离检测出 ｎ 个 ｋ 近邻 距 离 最 大 的 数 据 点 作 为 异 常 点。 Ｂｒｅｕｎｉｇ 等［１０］提出另外一类基于密度的数据异常类型，通过 计算本地异常因子 ＬＯＦ 来检测局部异常点数据，但 该算法存在较高计算复杂度问题。 在数据流异常检测方面，Ｙａｎｇ 等［１１］ 采用滑动 窗口方式在数据流上挖掘基于邻居的模式，主要包 括基 于 密 度 的 聚 类 和 基 于 距 离 的 异 常 检 测。 Ａｎｇｉｕｌｌｉ 等［１２］通过在数据流上分析数据点是否为 “ｓａｆｅ ｉｎｌｉｅｒ” 来优化检测方法。 Ｋｏｎｔａｋｉ 等［１３］ 利用 “ｓａｆｅ ｉｎｌｉｅｒ”设计了一种事件触发的数据流异常检 测优化算法。 Ｃａｏ 等［１４］ 提出了一种数据流异常检 测框架，该框架可用于处理基于距离的和基于 ｋ 近 邻的两类异常检测模型。 针对移动对象的轨迹数据，Ｌｅｅ 等［１５］ 提出了一 种划分⁃检测的轨迹异常检测框架，将轨迹划分成 ｔ⁃ ｐａｒｔｉｔｉｏｎ 序列，通过计算 ｔ⁃ｐａｒｔｉｔｉｏｎ 间的距离和密度， 以发现异常的子 ｔ⁃ｐａｒｔｉｔｉｏｎ。 Ｂｕ 等［１６］ 提出了一种连 续监控移动对象实时轨迹数据流的异常检测算法， 该方法关注在检测单个移动对象实时轨迹数据中 的异常子轨迹段。 文献［１７］ 针对海量移动对象系 统中异常对象，提出了一种基于邻居的异常移动对 象检测方法，可发现不同于其他邻居对象运动轨迹 的异常对象。 ２ 问题定义 本节首先给出一些重要的定义和表示，然后对 基于距离的移动社交网络异常签到模型进行描述。 定义 １ 基于距离的位置异常。 给定位置数据 集 Ｄ、距离阈值 ｄ、邻居点数量阈值 ｋ，对于位置数据 点 ｏ ∈ Ｄ ，如果 { ｐ ｄｉｓｔ(ｐ，ｏ) ≤ ｄ，ｐ ∈ Ｄ} ≤ ｋ， 则称 ｏ 是一个基于距离的位置异常点。 Ｕ ＝ ｛ｕ１ ，ｕ２ ，．．．，ｕｍ ｝ 表示移动社交网络的所有 用户集，用户 ｕｉ在 ｔ ｊ 时间点的签到位置表示为 ｐ ｉ ｊ 。 本文采用基于签到位置数量的滑动窗口 Ｗ 来 处理移动社交网络中实时的签到数据，窗口长度标 记为 Ｗ ＝ ｗ ，也就是说，Ｗ 中包含 ｗ 个签到位置。 定义 ２ 基于历史位置的异常签到。 给定距离 阈值 ｄ、邻居点数量阈值 ｋ，滑动窗口 Ｗ，对于用户 ｕｉ 的签到位置 ｐ ｉ ｂ ∈ ｗ， 如果 ｛ｐ ｉ ｊ ｄｉｓｔ（ｐ ｉ ｊ ，ｐ ｉ ｂ） ≤ ｄ， 第 ５ 期 赵冠哲，等：移动社交网络异常签到在线检测算法 ·７５３·