引用本文

刘芳, 齐建鹏, 于彦伟, 曹磊, 赵金东. 基于密度的Top-n局部异常点快速检测算法. 自动化学报, 2019, 45(9): 1756-1771. doi: 10.16383/j.aas.c180425

LIU Fang, QI Jian-Peng, YU Yan-Wei, CAO Lei, ZHAO Jin-Dong. A Fast Algorithm for Density-based Top-n Local Outlier Detection. ACTA AUTOMATICA SINICA, 2019, 45(9): 1756-1771. doi: 10.16383/j.aas.c180425

http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.c180425

关键词

异常检测，局部异常检测，Top-n，剪枝策略 

摘要

局部异常检测（Local outlier factor，LOF）能够有效解决数据倾斜分布下的异常检测问题，在很多应用领域具有较好的异常检测效果.本文面向大数据异常检测，提出了一种快速的Top-n局部异常点检测算法MTLOF（Multi-granularity upper bound pruning based top-n LOF detection），融合索引结构和多层LOF上界设计了多粒度的剪枝策略，以快速发现Top-n局部异常点.首先，提出了四个更接近真实LOF值的上界，以避免直接计算LOF值，并对它们的计算复杂度进行了理论分析；其次，结合索引结构和UB1、UB2上界，提出了两层的Cell剪枝策略，不仅采用全局Cell剪枝策略，还引入了基于Cell内部数据对象分布的局部剪枝策略，有效解决了高密度区域的剪枝问题；再次，利用所提的UB3和UB4上界，提出了两个更加合理有效的数据对象剪枝策略，UB3和UB4上界更加接近于真实LOF值，有利于剪枝更多数据对象，而基于计算复用的上界计算方法，大大降低了计算成本；最后，优化了初始Top-n局部异常点的选择方法，利用区域划分和建立的索引结构，在数据稀疏区域选择初始局部异常点，有利于将LOF值较大的数据对象选为初始局部异常点，有效提升初始剪枝临界值，使得初始阶段剪枝掉更多的数据对象，进一步提高检测效率.在六个真实数据集上的综合实验评估验证MTLOF算法的高效性和可扩展性，相比最新的TOLF（Top-n LOF）算法，时间效率提升可高达3.5倍.

文章导读

近年来, 随着各类智能移动设备的广泛普及, 社交网络、网上购物、移动支付、位置服务等新兴应用不断涌现, 各类海量大数据被采集和处理, 而面向这些大数据的挖掘分析服务已俨然成为一大独具特色的新兴产业.异常检测作为数据挖掘最重要的任务之一, 在网络监测、信用卡欺诈、电信诈骗、金融证券服务、电子商务等各种应用领域都被认为是至关重要的内容.因此, 异常检测在学术界与工业界都受到了越来越多的关注, 在大数据与人工智能应用中, 异常检测也发挥了越来越重要的作用, 例如在北京, 通过对地铁和公交乘车记录的异常检测分析可帮助安保系统识别出潜在的小偷[1].

异常检测旨在从海量数据中识别出与大多数数据样本差异较大的数据对象.目前已存在很多异常检测研究工作[2-4], 如基于距离的异常检测[5-7]、基于邻居的异常检测[8-10]、基于分布的异常检测[11-13]和基于聚类的异常检测[14-15]等.然而, 这些异常检测方法都无法处理数据倾斜分布下的异常检测问题, 因为在倾斜分布的数据中, 不同区域的异常数据可能具有不同的数据特征, 而上述方法都采用全局的异常标准来处理数据对象.基于密度的LOF[16]有效解决了在数据倾斜分布下的异常检测问题.局部异常检测利用每个数据对象相对于其周围邻居的相对密度衡量异常因子, 这样的相对密度反映了局部的数据分布, 也就是说, 对异常的检测是相对于局部数据的, 因此可以处理倾斜分布下的异常检测问题.在实际应用中, 尤其是在大数据系统中, 数据的分布往往是倾斜的, 基于LOF的局部异常检测方法相比其他检测方法在很多应用领域都表现出了较好的异常检测效果[17-18].

局部异常检测方法[16]需要计算每个数据对象的LOF异常因子, 然后通过排序找出LOF值较大的数据点作为异常对象, 而LOF定义了相对密度, 要求查找每个数据的k近邻及可达距离, 因此检测计算成本非常高, 很难满足对大规模数据的异常检测效率需求.最新研究[19]针对Top-n局部异常点检测, 提出了一种基于LOF上界剪枝的检测算法(Top-n LOF, TOLF), 利用Cell索引和LOF上界对数据对象进行剪枝, 较大地提升了局部异常点检测的效率.尽管如此, TOLF在Cell剪枝中仅采用了一个全局的两点间最小距离cpmin进行剪枝, 当全局cpmin较小时, 将严重影响Cell剪枝效果, 甚至失效, 此外, 针对数据对象剪枝的LOF上界相比真实LOF值较大且计算复杂度较高, 使得剪枝效果也有限.

针对这些问题, 本文提出了一种改进的Top-n局部异常点检测算法MTLOF, 融合索引结构和多层LOF上界设计剪枝策略, 实现了高效的局部异常点检测. 1)为避免直接计算LOF值, 提出了四个更接近真实LOF值的LOF上界(UB1−UB4), 并对它们的计算复杂度进行了理论分析; 2)利用索引结构和UB1、UB2上界, 提出了两层的Cell剪枝策略, 不仅采用全局Cell剪枝策略, 还引入了基于Cell内部数据对象分布的局部剪枝策略, 有效解决了高密度区域的剪枝问题; 3)利用提出的UB3和UB4上界, 提出了两个更加合理有效的数据对象剪枝策略, UB3和UB4上界更加接近于真实LOF值, 有利于剪枝更多数据对象, 而基于计算复用的LOF上界计算方法, 大大降低了计算成本; 4)优化了初始候选Top-n局部异常点的选择方法, 利用均匀区域划分和建立的索引结构, 在数据分布的稀疏区域选择初始局部异常点, 有利于选择LOF值较大的数据对象作为初始局部异常点, 有效提升初始临界值(Cutoff threshold) ct, 使得在初始阶段剪枝掉更多的Cell和数据对象. 5)在六个不同维度的真实数据集上的综合实验评估验证了MTLOF算法的高效性和可扩展性, 相比最新的TOLF算法, 提升的效率可高达3.5倍.

本文结构如下:第1节讨论相关工作; 第2节定义基本概念和问题; 第3节给出详细的检测算法; 第4节进行实验验证和分析; 第5节总结全文.

图 3  基于Cell索引的剪枝示例

图 4  区域划分示例

图 5  总体效率对比评估

本文提出了一个面向大数据的高效的Top-n局部异常点检测算法MTLOF.首先, 为了避免直接计算数据对象的LOF值, 提出了四个计算复杂度更低并且更接近于真实LOF值的上界.其次, 结合索引结构和LOF上界, 引入了两层的Cell剪枝策略.然后, 针对未被剪枝的Cell内部数据对象, 利用UB3(p)和UB4(p)上界提出了两个更加合理有效的剪枝策略.此外, 还利用均匀区域划分和建立的索引结构, 优化了初始候选局部异常点的选取方法, 使得LOF值较大的数据对象被选取为初始局部异常点.最后, 在六个真实数据集上的综合实验评估验证了所提MTLOF算法的有效性, 相比LOF、MC和TOLF算法, 检测效率可分别提升30、18和2.6倍.

下一步工作将考虑借助分布式计算平台, 设计分布式异常检测算法以进一步提升检测效率, 此外, 还计划面向不断快速增长的海量高速数据集, 研究实时的Top-n局部异常点检测方法.

作者简介

刘芳

烟台大学计算机与控制工程学院硕士研究生.2017年获得烟台大学计算机科学与技术专业学士学位.主要研究方向为数据挖掘.E-mail:liufang0812@163.com

齐建鹏  

烟台大学计算机与控制工程学院硕士研究生.2015年获得烟台大学计算机科学与技术专业学士学位.主要研究方向为数据挖掘, 分布式计算.E-mail:jianpengqi@126.com

曹磊   

麻省理工学院计算机科学与人工智能实验室博士后.2016年获得伍斯特理工学院计算机科学专业博士学位.主要研究方法为数据挖掘, 机器学习.E-mail:lcao@csail.mit.edu

赵金东  

烟台大学计算机与控制工程学院副教授.2012年获得北京科技大学计算机科学与技术专业博士学位.主要研究方法为无线传感器网络, 分布式计算.E-mail:zhjdong@126.com

于彦伟   

烟台大学计算机与控制工程学院副教授, 美国宾夕法尼亚州立大学信息科学与技术学院博士后.2014年获得北京科技大学计算机科学与技术专业博士学位.主要研究方法为数据挖掘, 机器学习, 分布式计算.本文通信作者.E-mail:yuyanwei@ytu.edu.cn