Survey of Nearest Neighbor Condensing Techniques <s> Angiulli introduced the "Fast Condensed Nearest <s> k-nearest neighbor (k-NN) classi"cation is a well-known decision rule that is widely used in pattern classi"cation. However, the traditional implementation of this method is computationally expensive. In this paper we develop two e5ective techniques, namely, template condensing and preprocessing, to signi"cantly speed up k-NN classi"cation while maintaining the level of accuracy. Our template condensing technique aims at “sparsifying” dense homogeneous clusters of prototypes of any single class. This is implemented by iteratively eliminating patterns which exhibit high attractive capacities. Our preprocessing technique "lters a large portion of prototypes which are unlikely to match against the unknown pattern. This again accelerates the classi"cation procedure considerably, especially in cases where the dimensionality of the feature space is high. One of our case studies shows that the incorporation of these two techniques to k-NN rule achieves a seven-fold speed-up without sacri"cing accuracy. ? 2002 Pattern Recognition Society. Published by Elsevier Science Ltd. All rights reserved. <s> BIB001 </s> Survey of Nearest Neighbor Condensing Techniques <s> Angiulli introduced the "Fast Condensed Nearest <s> Instance-based learning algorithms are often faced with the problem of deciding which instances to store for use during generalization. Storing too many instances can result in large memory requirements and slow execution speed, and can cause an oversensitivity to noise. This paper has two main purposes. First, it provides a survey of existing algorithms used to reduce storage requirements in instance-based learning algorithms and other exemplar-based algorithms. Second, it proposes six additional reduction algorithms called DROP1–DROP5 and DEL (three of which were first described in Wilson & Martinez, 1997c, as RT1–RT3) that can be used to remove instances from the concept description. These algorithms and 10 algorithms from the survey are compared on 31 classification tasks. Of those algorithms that provide substantial storage reduction, the DROP algorithms have the highest average generalization accuracy in these experiments, especially in the presence of uniform class noise. <s> BIB002 </s> Survey of Nearest Neighbor Condensing Techniques <s> Angiulli introduced the "Fast Condensed Nearest <s> We present a novel algorithm for computing a training set consistent subset for the nearest neighbor decision rule. The algorithm, called FCNN rule, has some desirable properties. Indeed, it is order independent, and has subquadratic worst case time complexity, while it requires few iterations to converge, and it is likely to select points very close to the decision boundary. We compare the FCNN rule with state of the art competence preservation algorithms on large multidimensional training sets, showing that it outperforms existing methods in terms of learning speed and learning scaling behavior, and in terms of size of the model, while it guarantees a comparable prediction accuracy. <s> BIB003 </s> Survey of Nearest Neighbor Condensing Techniques <s> Angiulli introduced the "Fast Condensed Nearest <s> The K-nearest neighbor (KNN) rule is one of the most widely used pattern classification algorithms. For large data sets, the computational demands for classifying patterns using KNN can be prohibitive. A way to alleviate this problem is through the condensing approach. This means we remove patterns that are more of a computational burden but do not contribute to better classification accuracy. In this brief, we propose a new condensing algorithm. The proposed idea is based on defining the so-called chain. This is a sequence of nearest neighbors from alternating classes. We make the point that patterns further down the chain are close to the classification boundary and based on that we set a cutoff for the patterns we keep in the training set. Experiments show that the proposed approach effectively reduces the number of prototypes while maintaining the same level of classification accuracy as the traditional KNN. Moreover, it is a simple and a fast condensing algorithm. <s> BIB004 </s> Survey of Nearest Neighbor Condensing Techniques <s> Angiulli introduced the "Fast Condensed Nearest <s> Utilizing feature selection in intrusion detection can remove redundant features and improve the speed of the intrusion detection system efficiently on the basis of protecting the integrity of the original data. This paper proposes a new feature selection method that is based on KNN and Tabu search algorithm. The experiment result shows that this method can remove the redundant features, and reduce the time of feature selection. This method not only guarantees the accuracy of detection but also improves the detection speed efficiently. <s> BIB005 </s> Survey of Nearest Neighbor Condensing Techniques <s> Angiulli introduced the "Fast Condensed Nearest <s> In instance-based machine learning, algorithms often suffer from storing large numbers of training instances. This results in large computer memory usage, long response time, and often oversensitivity to noise. In order to overcome such problems, various instance reduction algorithms have been developed to remove noisy and surplus instances. This paper discusses existing algorithms in the field of instance selection and abstraction, and introduces a new approach, the Class Boundary Preserving Algorithm (CBP), which is a multi-stage method for pruning the training set, based on a simple but very effective heuristic for instance removal. CBP is tested with a large number of datasets and comparatively evaluated against eight of the most successful instance-based condensation algorithms. Experiments showed that our algorithm achieved similar classification accuracies, with much improved storage reduction and competitive execution speeds. <s> BIB006
Neighbor rule" (FCNN) BIB003 a scalable algorithm on large multidimensional data sets used to create subsets serving as consistent training sets based on the nearest neighbor decision rule. This algorithm allows selecting points very close to the border decision. It is independent of the order, and has low quadratic complexity. The FCNN rule initializes the consistent subset S with a starting element from each class label of the training set. The starting elements that the rule uses are particularly the class's centroids in the training set. The algorithm is incremental. At each iteration the resulting set is increased till the stop condition is reached. Wilson and Martinez suggested BIB002 a series of six algorithms for sets reduction based on the kNN algorithm where each algorithm improves the previous one. The first reduction technique presented was the DROP1 which constitutes the basic framework on which were built the five other techniques. The DROP1 represents an improvement of the RNN rule, which verifies the accuracy of the resulting set instead of the initial set T. This algorithm is based on the following rule: an instance P is removed only if at least some of its associates (neighbors from same class) in S can be classified correctly without P. The first proposal causes a problem when the noisy instances, which are typically associated with a different class, cover only a small portion of the input space. DROP2 tries to solve this problem by considering the effect of removing an instance on all instances of the initial training T rather than S. For this purpose the rule of DROP1 has been improved to eliminate P if at least an acceptable number of its associates in T can be classified correctly without P. DROP2 sorts S in an attempt to remove the central points before the border points (points which are near from the decision boundaries), however noisy instances can also be on borders, which can cause a change in the removal order. And even if a noisy instance is central attempting to remove it could eliminate border points that should be maintained. Hence DROP3 uses a noise filtering before sorting the instances of S. This is done using a rule that eliminates any instance misclassified by its k nearest neighbors. Except that DROP3 can sometimes remove an overly large number of instances. DROP4 improves DROP3 rule and provides that an instance is removed only if: 1. It is misclassified by its k nearest neighbors, and 2. Its removal does not affect the classification of other instances DROP5 upgrades DROP2 by proposing that the instances are considered beginning from the ones closest to the nearest enemy (an enemy is the nearest neighbor of an instance with a different class) and proceeding to outside. The latest algorithm proposed by Wilson and Martinez BIB005 was the DEL which is similar to DROP3, except that it uses the length coding heuristic for deciding whether an instance can be removed or not. In DEL an instance is removed only if: 1. It is misclassified by its k nearest neighbors, and 2. The removal of the instance does not increase the cost of length encoding Wu, Ianakiev and Govindraju proposed an "Improved KNearest Neighbor Classification" BIB001 . A solution to increase the speed of traditional kNN classification while maintaining its level of accuracy by suggesting two building techniques. The suggested IKNN algorithm is based on iterative elimination of models with high attraction capacity. In the first technique called the model condensing, the authors suggested that all classes have the same probability, and that the training set Ω is initially created by the extraction of vector elements from a large set of images of interest, where each class has an equal representation. This set Ω is refined iteratively. In the second technique, which is the pre-processing, an unknown pattern is compared to a prototype in two stages. In the first stage a rapid evaluation of the potential match is made. The prototypes that fail in the first match are not included in the second. Then, for a complete match, in the www.ijacsa.thesai.org second stage the norms difference of the prototype and the test pattern must be less than a predetermined threshold. The observation that large sets of data had computational requirements which could be prohibitive to classify models using the kNN, has led Fayed and Atia BIB004 to propose the TRKNN, a way to lessen this problem through a condensation approach. The aim of their approach is to eliminate the reasons that makes load the calculation and does not contribute to improve the classification. This approach consists in rejecting the prototypes that are far from the limits and have just a little influence on the KNN classification. To achieve this, the authors first introduced the concept of chain of nearest neighbors which is a sequence of the nearest neighbors from alternating classes. This technique proposes that if the distances of a given model decrease in value, this model is considered to be probably an internal point and can be discarded, whereas if the distances do not decrease too much, then this point probably varies around the limit of classification and it is maintained. In a more recent paper BIB006 the authors introduced a new approach "The Class Boundary Preserving Algorithm" (CBP), a multi-step method for pruning the training set. The proposed method aims at preserving instances that are close to the borders of classes. Because, according to the authors, these instances can provide most of the necessary information to properly describe the underlying distribution. On the other hand instances distant from limits are considered redundant by the authors. The innovation in this approach is the procedure used to divide the training set into two subsets, X B containing the instances near the surface of decision, and X NB containing the internal samples. And because there is a noticeable difference in the importance of information held by these two sets, two different reduction processes were applied on both. The algorithm considers an initial set of n instances related to a set of labels, and involves four main steps. The first step deals with the smoothing of class boundaries, the second allows to distinguish between border and nonborder instances. The third step has to do with the pruning of border instances and the last step is the clustering of nonborder instances. To implement this idea, the authors have used the Mean Shift Clustering algorithm (MSC) which converges to the points of maximum density to determine the cluster centers of the distribution. Then to make the maximum number of neighbors in obtained clusters, the authors applied a merger process which verifies the calculated clusters centers labels, and if the clusters of nearest neighbors share the same label, then the centers are merged.