基于密度的Top-n局部异常点快速检测算法

• 作者: 于彦伟 刘芳 曹磊 赵金东 齐建鹏
• 来源期刊: 自动化学报
• 关键词: 异常检测 局部异常检测 Top-n 剪枝策略
• 年，卷（期）: 2019,（9）
• 所属期刊栏目: 论文与报告
• 页码范围: 1756-1771
• 页数: 16页
• 字数: 15184字
• 语种: 中文
• DOI: 10.16383/j.aas.c180425

摘要

局部异常检测(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倍.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	刘芳	烟台大学计算机与控制工程学院	12	13	2.0	3.0
2	赵金东	烟台大学计算机与控制工程学院	16	122	7.0	10.0
3	齐建鹏	烟台大学计算机与控制工程学院	5	18	3.0	4.0
4	于彦伟	烟台大学计算机与控制工程学院	8	35	4.0	5.0