Survey of Nearest Neighbor Condensing Techniques <s> III. IMPROVING PROTOTYPE SELECTION <s> A further modification to Cover and Hart's nearest neighbor decision rule, the reduced nearest neighbor rule, is introduced. Experimental results demonstrate its accuracy and efficiency. <s> BIB001 </s> Survey of Nearest Neighbor Condensing Techniques <s> III. IMPROVING PROTOTYPE SELECTION <s> A conventional way to discriminate between objects represented by dissimilarities is the nearest neighbor method. A more efficient and sometimes a more accurate solution is offered by other dissimilarity-based classifiers. They construct a decision rule based on the entire training set, but they need just a small set of prototypes, the so-called representation set, as a reference for classifying new objects. Such alternative approaches may be especially advantageous for non-Euclidean or even non-metric dissimilarities. The choice of a proper representation set for dissimilarity-based classifiers is not yet fully investigated. It appears that a random selection may work well. In this paper, a number of experiments has been conducted on various metric and non-metric dissimilarity representations and prototype selection methods. Several procedures, like traditional feature selection methods (here effectively searching for prototypes), mode seeking and linear programming are compared to the random selection. In general, we find out that systematic approaches lead to better results than the random selection, especially for a small number of prototypes. Although there is no single winner as it depends on data characteristics, the k-centres works well, in general. For two-class problems, an important observation is that our dissimilarity-based discrimination functions relying on significantly reduced prototype sets (3-10% of the training objects) offer a similar or much better classification accuracy than the best k-NN rule on the entire training set. This may be reached for multi-class data as well, however such problems are more difficult. <s> BIB002
Condensing algorithms try to find a significant reduction of all prototypes so that the 1-NN classification gives results as close as possible to those obtained using all the original prototypes BIB002 . The problem that arises when this approach is used is that it cannot provide a proof about the resulting sets minimality. To correct this slight defect, the modern heuristics or metaheuristics came to complete them. The metaheuristics are strategies that guide the search towards an optimal solution. These techniques are designed to explore the search space efficiently in order to determine solutions (almost) optimal. They may contain mechanisms to avoid blocking in areas of space research. Two types of metaheuristics have been successful in their hybridization with the traditional KNN: genetic algorithms and tabu search. Genetic algorithms (GA) are an optimization technique guided by the principles of natural evolution and genetics, with a high presence of implicit parallelism. These algorithms perform a search in complex, large, and multimodal landscapes, and provide solutions for the quasi-optimal objective function. The tabu search (TS) is a method of dynamic neighborhood, which selects, at each iteration, the best solution of the first local optimum by finding the best neighbor. www.ijacsa.thesai.org IV. HEURISTIC METHODS BASED ON THE CONDENSING K-NN RULE In 1968 Hart  was the first to propose a method reducing the size of stored data for the nearest neighbor decision. This method is called "The Condensed Nearest Neighbor Rule" (CNN). The new idea about this rule compared to the traditional KNN is the process of selecting a subset TCNN from the initial training set TNN. TCNN must be as effective as TNN in the classification of unknown patterns. Actually the CNN rule minimizes the number of models stored, keeping only a subset of training data for classification, and employing a technique of low absorption. The basic idea is to look for very similar training models, and those that do not add additional information and eliminate them. This rule presents a case where TCNN consistency is not achieved, when TNN is already the minimum set. In this case TCNN will be equal to TNN, if this happens, the algorithm will end if there are two equal models of different classes, but TCNN must classify patterns correctly. The technique that corrects this case of inconsistency is the "Reduced Nearest Neighbor rule" (RNN) introduced by Gates BIB001 . This rule is an extension of the CNN rule, and like CNN, RNN reduces TNN. The RNN algorithm starts at TRNN=TCNN and removes every instance from TRNN if this deletion does not cause a misclassification of another instance in TNN by the remaining instances in TRNN. From the perspective of computing, it is more expensive than the rule proposed by Hart, but it will always produce a subset of CNN, and thus will be less expensive in terms of computing and storage at the classification stage.