Computational Intelligence - August 2015 - 52

Research
Frontier

Bo Tang and Haibo He

Department of Electrical, Computer, and
Biomedical Engineering, University of
Rhode Island, Kingston, RI, USA

Enn: Extended nearest neighbor Method for Pattern Recognition

Abstract

T

his article introduces a new supervised classification method
- the extended nearest neighbor (ENN) - that predicts input patterns according to the maximum gain of
intra-class coherence. Unlike the classic knearest neighbor (KNN) method, in
which only the nearest neighbors of a
test sample are used to estimate a group
membership, the ENN method makes
a prediction in a "two-way communication" style: it considers not only who
are the nearest neighbors of the test sample,
but also who consider the test sample as
their  nearest neighbors. By exploiting the
generalized class-wise statistics from all
training data by iteratively assuming
all the possible class memberships of a
test sample, the ENN is able to learn
from  the global distribution, therefore
improving pattern recognition performance and providing a powerful technique for a wide range of data analysis
applications.

I. Introduction

With the continuous expansion of data
availability in many areas of engineering
and science, such as biology, communications, social networks, global climate, and
remote sensing, it becomes critical to
identify patterns from vast amounts of
data, to identify members of a predefined
class (classification), or to group patterns
Digital Object Identifier 10.1109/MCI.2015.2437512
Date of publication: 16 July 2015

52

based on their similarities (clustering). In
the setting of a classification, there are
two kinds of classifiers which scientists
and engineers may use: parametric classifiers in which the
underlying joint distributions/models of
the data are assumed
to be known but certain parameters need
to be estimated, and
nonparametric classifiers
in which the classification rules do not
depend explicitly on
the data's underlying
distributions [1]. With
the coming of the Big Data era [2]
[3] [4], nonparametric classifiers have
received particular attention because the
data distributions/models of many classification problems are either unknown or
very difficult to obtain in practice. Previous nonparametric classification methods, such as k-nearest neighbor (KNN),
assume that data which are close together based upon some metrics, such as
Euclidean distance, more likely belong to
the same category. Therefore, given an
unknown sample to be classified, its
nearest neighbors are first ranked and
counted, and then a class membership
assignment is made.
Nearest neighbor-based pattern
recognition methods have several key advantages, such as easy implementation,
Corresponding author: Haibo He (Email: he@ele.
uri.edu).

IEEE ComputatIonal IntEllIgEnCE magazInE | august 2015

competitive performance, and a nonparametric computational basis which is independent of the underlying data
distribution.The first modern study of the
nearest neighbor approach can be traced
back to 1951 by Fix
and Hodges [5]. In
their formalization of
nonparametric discrimination, the consistency of KNN was
established using a
probability density estimation. They proved
that if k " 3 and
©Digital vision
k/n " 0, where k is
the number of selected nearest neighbors
and n is the sample size of the whole data
set, the classification error of the nearest
neighbor method ^R nh can asymptotically converge to the Bayesian rule
(R )): R n " R ) . In another representative
work [6], Cover and Hart proved that for
N -class classification problems, when
k = 1, the classification error of the nearest neighbor method will be bounded
by R ) # R n # R ) (2 - (N/(N - 1)) R ))
when there are infinite samples. This basically means in the large sample case, the
nearest neighbor method has "a probability of error which is less than twice the
Bayes probability of error" [6].These early
classic works laid down a strong theoretical foundation for nearest neighbor based
methods, which have been witnessed in
considerable applications in many different disciplines, such as biological and

1556-603x/15©2015IEEE
http://www.uri.edu
Table of Contents for the Digital Edition of Computational Intelligence - August 2015
