基于网格查询的局部离群点检测算法

来源：计算机工程与应用杂志2019年第17期北京时间：

作者：牛少章，欧毓毅，凌捷，顾国生

单位：广东工业大学 计算机学院，广州 510006

摘要：针对基于密度的局部离群因子算法（LOF），需要计算距离矩阵来进行[k]近邻查寻，算法时间复杂度高，不适合大规模数据集检测的问题，提出基于网格查询的局部离群点检测算法。算法利用距离目标网格中的数据点最近的[k]个其他数据点，一定在该目标网格或在该目标网格的最近邻接网格中这一特性，来改进LOF算法的邻域查询操作，以此减少LOF算法在邻域查询时的计算量。实验结果证明，提出的LOGD算法在与原LOF算法具有基本相同的检测准确率的情况下，能够有效地降低离群点检测的时间。

关键词：局部离群因子,[k]近邻,距离矩阵,网格,记忆性,邻域查询