Frontiers of Data and Computing ›› 2020, Vol. 2 ›› Issue (6): 82-89.

doi: 10.11871/jfdc.issn.2096-742X.2020.06.009

• Technology and Applicaton • Previous Articles     Next Articles

FINFLO: A New Fast Local Outliers Detection Algorithm

YANG Xiaolin1,2,LI Jingjing1,*(),LI Yi1   

  1. 1. Computer Network Information Center, Chinese Academy of Sciences, Beijing 100190, China
    2. University of Chinese Academy of Sciences, Beijing 100049, China
  • Received:2020-08-08 Online:2020-12-20 Published:2020-12-29
  • Contact: LI Jingjing E-mail:jjli@cnic.cn

Abstract:

[Objective] Local density based LOF algorithm has high time complexity, and it tends to misjudge the normal objects at the edge of the cluster as exceptions. The inverse k-nearest-neighbor algorithm is introduced to solve the problem of LOF algorithm in INFLO algorithm. However, it is unnecessary and time-consuming to use the inverse k-nearest-neighbor when calculating the local outlier factor of each object. [Methods] Through the analysis of the two algorithms, this paper proposes a new fast anomaly detection algorithm, named Faster Influenced Outlierness, FINFLO. When calculating the local factors of objects, FINFLO tries to avoid considering reverse k-nearest neighbor objects, and use only k-nearest neighbor objects as much as possible. If the number of reverse k-nearest neighbor objects is not less than the mean of all reverse k-nearest neighbor objects, only k-nearest neighbor objects need to be considered, otherwise reverse k-nearest neighbor objects need to be considered. [Conclusions] Experimental results show that the algorithm can improve the accuracy of outlier detection, reduce the time complexity, and achieve effective local outlier detection.

Key words: local density, outlier factor, local outlier, k-nearest neighbor, reverse k-nearest neighbor