A novel fast constructing neighborhood covering algorithm for efficient classification

摘要

Due to the nonparametric property and the robustness to complex data, neighborhood covering model has been widely used for data classification. However, there are two defects which limit its performance. One is that most existing methods based on neighborhood covering suffer high computational complexity to train the model. The other is that the significance of neighborhood is evaluated only by the number of samples in the neighborhood, which leads to some overlaps among each neighborhood and diminishes the classification ability of the model. Therefore, to resolve the above issues, a new fast constructing neighborhood covering algorithm for efficient classification (FNC-EC) is proposed in this paper. First, data samples are divided into k disjoint clusters by k-means algorithm. Next, an adaptive neighborhood radius is defined for constructing neighborhood. And the k-means algorithm is utilized to process the heterogeneous neighborhoods, so that all neighborhoods are homogeneous. Then, the local density and relative distance of neighborhood center are defined for evaluating the significance of neighborhood, and a neighborhood selection method based on local density and relative distance is proposed for classification task. Finally, the experimental results demonstrate that FNC-EC performs well in classification results and efficiency.