Attribute reduction based on overlap degree and k-nearest-neighbor rough sets in decision information systems

The k-nearest-neighbor rule is a popular classification technique, and rough set theory is an effective mathematical tool to deal with the uncertainty of data. Rough set models based on k-nearest-neighbor relations have a strong ability to approximate decisions, but the calculation is very time-consuming. In this paper, we model the overlap degree of objects from different categories in advance to accelerate the attribute reduction and improve the classification performance of the selected attributes. Firstly, we define the coincidence degree (CD) and distance (DIS) of objects from different categories to measure the coverage and distance of between-class objects. Secondly, we combine CD and DIS to define the overlap degree (OD) to pre-sort attributes, then use k-nearest-neighbor rough sets to filter inconsistent and redundant attributes. The pre-sort operation based on OD can greatly reduce the number of searches for attributes and ensure that the attributes with high separability should be selected first. Furthermore, we design a fast reduction algorithm (OD&KNN) to obtain a reduct with the ability to approximate decisions as well as the original attributes but with lower OD. Comparing experimental results and time complexity of OD&KNN with state-of-the-art algorithms, OD&KNN is more efficient for high-dimensional data while ensuring classification accuracy.