Survey of Nearest Neighbor Techniques
---
paper_title: Nearest Neighbor Pattern Classification

paper_content:

The nearest neighbor decision rule assigns to an unclassified sample point the classification of the nearest of a set of previously classified points. This rule is independent of the underlying joint distribution on the sample points and their classifications, and hence the probability of error R of such a rule must be at least as great as the Bayes probability of error R^{\ast} --the minimum probability of error over all decision rules taking underlying probability structure into account. However, in a large sample analysis, we will show in the M -category case that R^{\ast} \leq R \leq R^{\ast}(2 --MR^{\ast}/(M-1)) , where these bounds are the tightest possible, for all suitably smooth underlying distributions. Thus for any number of categories, the probability of error of the nearest neighbor rule is bounded above by twice the Bayes probability of error. In this sense, it may be said that half the classification information in an infinite sample set is contained in the nearest neighbor.
---
paper_title: Query dependent ranking using K-nearest neighbor

paper_content:

Many ranking models have been proposed in information retrieval, and recently machine learning techniques have also been applied to ranking model construction. Most of the existing methods do not take into consideration the fact that significant differences exist between queries, and only resort to a single function in ranking of documents. In this paper, we argue that it is necessary to employ different ranking models for different queries and onduct what we call query-dependent ranking. As the first such attempt, we propose a K-Nearest Neighbor (KNN) method for query-dependent ranking. We first consider an online method which creates a ranking model for a given query by using the labeled neighbors of the query in the query feature space and then rank the documents with respect to the query using the created model. Next, we give two offline approximations of the method, which create the ranking models in advance to enhance the efficiency of ranking. And we prove a theory which indicates that the approximations are accurate in terms of difference in loss of prediction, if the learning algorithm used is stable with respect to minor changes in training examples. Our experimental results show that the proposed online and offline methods both outperform the baseline method of using a single ranking function.
---
paper_title: Improving text categorization methods for event tracking

paper_content:

Automated tracking of events from chronologically ordered document streams is a new challenge for statistical text classification. Existing learning techniques must be adapted or improved in order to effectively handle difficult situations where the number of positive training instances per event is extremely small, the majority of training documents are unlabelled, and most of the events have a short duration in time. We adapted several supervised text categorization methods, specifically several new variants of the k-Nearest Neighbor (kNN) algorithm and a Rocchio approach, to track events. All of these methods showed significant improvement (up to 71% reduction in weighted error rates) over the performance of the original kNN algorithm on TDT benchmark collections, making kNN among the top-performing systems in the recent TDT3 official evaluation. Furthermore, by combining these methods, we significantly reduced the variance in performance of our event tracking system over different data collections, suggesting a robust solution for parameter optimization.
---
paper_title: Tunable nearest neighbor classifier

paper_content:

A tunable nearest neighbor (TNN) classifier is proposed to handle the discrimination problems. The TNN borrows the concept of feature line spaces from the nearest feature line (NFL) classifier, to make use of the information implied by the interaction between each pair of points in the same class. Instead of the NFL distance, a tunable distance metric is proposed in the TNN. The experimental evaluation shows that in the given feature space, the TNN consistently achieves better performance than NFL and conventional nearest neighbor methods, especially for the tasks with small training sets.
---
paper_title: KNN Model-Based Approach in Classification

paper_content:

The k-Nearest-Neighbours (kNN) is a simple but effective method for classification. The major drawbacks with respect to kNN are (1) its low efficiency – being a lazy learning method prohibits it in many applications such as dynamic web mining for a large repository, and (2) its dependency on the selection of a “good value” for k. In this paper, we propose a novel kNN type method for classification that is aimed at overcoming these shortcomings. Our method constructs a kNN model for the data, which replaces the data to serve as the basis of classification. The value of k is automatically determined, is varied for different data, and is optimal in terms of classification accuracy. The construction of the model reduces the dependency on k and makes classification faster. Experiments were carried out on some public datasets collected from the UCI machine learning repository in order to test our method. The experimental results show that the kNN based model compares well with C5.0 and kNN in terms of classification accuracy, but is more efficient than the standard kNN.
---
paper_title: New Algorithms for Efficient High Dimensional Non-parametric Classification

paper_content:

This paper is about non-approximate acceleration of high-dimensional nonparametric operations such as k nearest neighbor classifiers. We attempt to exploit the fact that even if we want exact answers to nonparametric queries, we usually do not need to explicitly find the data points close to the query, but merely need to answer questions about the properties of that set of data points. This offers a small amount of computational leeway, and we investigate how much that leeway can be exploited. This is applicable to many algorithms in nonparametric statistics, memory-based learning and kernel-based learning. But for clarity, this paper concentrates on pure k-NN classification. We introduce new ball-tree algorithms that on real-world data sets give accelerations from 2-fold to 100-fold compared against highly optimized traditional ball-tree-based k-NN. These results include data sets with up to 106 dimensions and 105 records, and demonstrate non-trivial speed-ups while giving exact answers.
---
paper_title: Log-Based Chat Room Monitoring Using Text Categorization: A Comparative Study

paper_content:

The Internet has been utilized in several real life aspects such as online searching, distance learning, and chatting. On the other hand, the Internet has been misused in communication of crime related matters. Monitoring of such communication would aid in crime detection or even crime prevention. This paper presents a text categorization approach for automatic monitoring of chat conversations since the current monitoring techniques are basically manual, which is tedious, costly, and time consuming. We present the results of a cross method comparison between the Naive Bayes, the K-nearest neighbor, and the Support Vector Machine classifiers. Our objective is to determine the most suitable method for the data of chat conversations. Our results showed that the chat room monitoring task can be efficiently automated using the appropriate text categorization method.
---
paper_title: Tunable nearest neighbor classifier

paper_content:

A tunable nearest neighbor (TNN) classifier is proposed to handle the discrimination problems. The TNN borrows the concept of feature line spaces from the nearest feature line (NFL) classifier, to make use of the information implied by the interaction between each pair of points in the same class. Instead of the NFL distance, a tunable distance metric is proposed in the TNN. The experimental evaluation shows that in the given feature space, the TNN consistently achieves better performance than NFL and conventional nearest neighbor methods, especially for the tasks with small training sets.
---
paper_title: KNN Model-Based Approach in Classification

paper_content:

The k-Nearest-Neighbours (kNN) is a simple but effective method for classification. The major drawbacks with respect to kNN are (1) its low efficiency – being a lazy learning method prohibits it in many applications such as dynamic web mining for a large repository, and (2) its dependency on the selection of a “good value” for k. In this paper, we propose a novel kNN type method for classification that is aimed at overcoming these shortcomings. Our method constructs a kNN model for the data, which replaces the data to serve as the basis of classification. The value of k is automatically determined, is varied for different data, and is optimal in terms of classification accuracy. The construction of the model reduces the dependency on k and makes classification faster. Experiments were carried out on some public datasets collected from the UCI machine learning repository in order to test our method. The experimental results show that the kNN based model compares well with C5.0 and kNN in terms of classification accuracy, but is more efficient than the standard kNN.
---

Title: Survey of Nearest Neighbor Techniques

Section 1: INTRODUCTION
Description 1: This section introduces the nearest neighbor (NN) rule, its applications, and various improvements to the k-nearest neighbor (kNN) algorithm, including handling computational complexity and memory requirements.

Section 2: NEAREST NEIGHBOR TECHNIQUES
Description 2: This section categorizes nearest neighbor techniques into structure-less and structure-based approaches and elaborates on various methods and improvements in each category.

Section 3: Structure less NN techniques
Description 3: This subsection details the k-nearest neighbor technique, including weighted kNN, condensed nearest neighbor, reduced nearest neighbor, model-based kNN, rank-based kNN, modified kNN, and other variations that do not rely on structured data organization.

Section 4: Structure based NN techniques
Description 4: This subsection covers structured nearest neighbor techniques such as Ball Tree, k-d Tree, Principal Axis Tree (PAT), Orthogonal Structure Tree (OST), Nearest Feature Line (NFL), and others that use data structures to improve the efficiency of nearest neighbor searches.

Section 5: CONCLUSION
Description 5: This section provides a comparison of the nearest neighbor techniques, summarizing the improvements in speed and space efficiency over the basic kNN technique and discussing the specific applications where each method excels.