A Fast and Scalable Fuzzy-rough Nearest Neighbor Algorithm

In this paper, classification efficiency of the conventional K-nearest neighbor algorithm is enhanced by improving the KNN search and exploiting fuzzy-rough uncertainty. A new algorithm FFRNN (Fast Fuzzy-rough Nearest Neighbor) is proposed, which approximates a set of potential candidates of nearest neighbors by examining the absolute difference of total variation between each data of the training set and the unclassified object. Then, the k-nearest neighbors are searched from the candidate set. Moreover, fuzzy and rough uncertainties are exploited. It is shown that FFRNN is faster and higher classification accuracy than KNN and FRNN algorithm. Besides, FFRNN can distinguish between equal evidence and ignorance, thus the class confidence values do not necessarily sum up to one and the semantics of the class confidence values becomes richer.