基于密度的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倍.
引用本文（GB/T 7714）
Fang Liu, Liu Fang, 齐建鹏, 等. 基于密度的Top- n 局部异常点快速检测算法[J]. 未知来源, 2019.
引文网络
本站仅收录题录与摘要供学习参考，全文版权归属出版方；如有侵权请联系我们删除。