A New Algorithm For Sample Selection Based On The Reachable And Coverage

To overcome the drawbacks that Nearest Neighbour classification requires huge computation and memory storage, this paper proposes a new algorithm (ISSARC: Iterative Sample Selection Algorithm based on Reachable and Coverage) based on the conceptions of Reachable and Coverage. In this algorithm, a new function is introduced to evaluate the classification ability for each sample. According to the measuring function, a sample with the best classification ability is added to the subset and the samples which can be classified correctly are deleted in each iteration until the condensed subset is no longer getting smaller. It can be seen from analysis that time complexity of ISSARC is O (n2). The experimental results on two artificial data sets and some real data sets demonstrate the effectiveness and the feasibility of the proposed algorithm. Compared to traditional methods, such as MCS, ICF and ENN, the condensed sets obtained by ISSARC is superior in compression ratio and classification accuracy.