FNC: A fast neighborhood calculation framework

摘要

Efficiency has always been a key issue in neighborhood calculations. This study analyzes the low efficiency of traditional neighborhood calculation and concludes that the root cause lies in the large number of repetitive and unnecessary calculations because of the large neighborhood search range. To solve the problem, this study proposes a fast neighborhood calculation framework (FNC), including a neighborhood acceleration method with respect to a single attribute and a neighborhood acceleration method with respect to joint attributes. After avoiding many repetitive and unnecessary calculations, the efficiency of the neighborhood calculation can be significantly improved, and its time complexity is reduced from O(n2) to O(nlogn). This study also proves that the proposed framework is valid for different distance functions. Also, the proposed framework is applied to the popular research on neighborhood rough set attribute reduction. L∞-norm and L2-norm are used to verify the proposed framework is valid for different distance functions in the experiments. Multiple detailed experiments have been carried out on seventeen datasets. The experimental results demonstrate that, with the reduction results unchanged, the efficiency of the accelerated algorithms by FNC is greatly improved compared to the original algorithms. The effectiveness and efficiency of the proposed framework have been well verified. All codes have been released in the open source library at http://www.cquptshuyinxia.com/FNC.html.