IKNN: Informative K-Nearest Neighbor Pattern Classification

Lecture notes in computer sciencePublished 29 August 2007

Yang Song, Jian Huang, Ding Zhou, Hongyuan Zha, C. Lee Giles

DOI10.1007/978-3-540-74976-9_25

Source URL

Citations210

SJR quartileQ2

SJR score0.35

SNIP0.55

TL;DR

A new metric that measures the informativeness of objects to be classified, which can be applied as a query-based distance metric to measure the closeness between objects, and two novel KNN procedures are proposed.

Abstract

The K-nearest neighbor (KNN) decision rule has been a ubiquitous classification tool with good scalability. Past experience has shown that the optimal choice of K depends upon the data, making it laborious to tune the parameter for different applications. We introduce a new metric that measures the informativeness of objects to be classified. When applied as a query-based distance metric to measure the closeness between objects, two novel KNN procedures, Locally Informative-KNN (LI-KNN) and Globally Informative-KNN (GI-KNN), are proposed. By selecting a subset of most informative objects from neighborhoods, our methods exhibit stability to the change of input parameters, number of neighbors(K) and informative points (I). Experiments on UCI benchmark data and diverse real-world data sets indicate that our approaches are application-independent and can generally outperform several popular KNN extensions, as well as SVM and Boosting methods.

Keywords

Computer ScienceEngineering

IEEE Transactions on Information TheoryNearest neighbor pattern classification

16,134 Citations1967Thomas M. Cover, Peter E. Hart

The nearest neighbor decision rule assigns to an unclassified sample point the classification of the nearest of a set of previously classified points, so it may be said that half the classification information in an infinite sample set is contained in the nearest neighbor.

Improved boosting algorithms using confidence-rated predictions

2,568 Citations1998Robert E. Schapire, Yoram Singer

On the algorithmic implementation of multiclass kernel-based vector machines

1,790 Citations2002Koby Crammer, Yoram Singer

This paper describes the algorithmic implementation of multiclass kernel-based vector machines using a generalized notion of the margin to multiclass problems, and describes an efficient fixed-point algorithm for solving the reduced optimization problems and proves its convergence.

Distance Metric Learning for Large Margin Nearest Neighbor Classification

1,707 Citations2005Kilian Q. Weinberger, John Blitzer +1 more

SVM-KNN: Discriminative Nearest Neighbor Classification for Visual Category Recognition

1,116 Citations2006Hao Zhang, Alexander C. Berg +2 more

This work considers visual category recognition in the framework of measuring similarities, or equivalently perceptual distances, to prototype examples of categories and proposes a hybrid of these two methods which deals naturally with the multiclass setting, has reasonable computational complexity both in training and at run time, and yields excellent results in practice.

Journal of the American Statistical AssociationConvexity, Classification, and Risk Bounds

1,019 Citations2006Peter L. Bartlett, Michael I. Jordan +1 more

A general quantitative relationship between the risk as assessed using the 0–1 loss and the riskAs assessed using any nonnegative surrogate loss function is provided, and it is shown that this relationship gives nontrivial upper bounds on excess risk under the weakest possible condition on the loss function.

Lecture notes in computer scienceText Categorization Using Weight Adjusted k-Nearest Neighbor Classification

353 Citations2001Eui-Hong Han, George Karypis +1 more

A Weight Adjusted k-Nearest Neighbor (WAKNN) classification that learns feature weights based on a greedy hill climbing technique and two performance optimizations of WAKNN that improve the computational performance by a few orders of magnitude, but do not compromise on the classification quality.

View PDF

IEEE Transactions on Pattern Analysis and Machine IntelligenceLocally adaptive metric nearest-neighbor classification

305 Citations2002Carlotta Domeniconi, Jing Peng +1 more

A chi-squared distance analysis is used to compute a flexible metric for producing neighborhoods that are highly adaptive to query locations and the class conditional probabilities are smoother in the modified neighborhoods, whereby better classification performance can be achieved.

Boosting Nearest Neighbor Classi.ers for Multiclass Recognition

54 Citations2006Vassilis Athitsos, Stan Sclaroff

An algorithm that uses boosting to learn a distance measure for multiclass k-nearest neighbor classification and achieves lower error rates in some of the datasets, which indicates that it is a method worth considering for nearest neighbor recognition in various pattern recognition domains.

Efficient Nearest Neighbor Classification Using a Cascade of Approximate Similarity Measures

54 Citations2005Vassilis Athitsos, Jonathan Alon +1 more

The proposed method for efficient nearest neighbor classification in non-Euclidean spaces with computationally expensive similarity/distance measures is experimentally evaluated in the domain of handwritten digit recognition using shape context matching, indicating a speed-up of two to three orders of magnitude is gained over brute force search.