Statistical Pattern Recognition： A Review

Statistical Pattern Recognition: A Review

Anil K. Jain, Fellow, IEEE, Robert P.W. Duin, and Jianchang Mao, Senior Member, IEEE

AbstractÐThe primary goal of pattern recognition is supervised or unsupervised classification. Among the various frameworks in

which pattern recognition has been traditionally formulated, the statistical approach has been most intensively studied and used in

practice. More recently, neural network techniques and methods imported from statistical learning theory have been receiving

increasing attention. The design of a recognition system requires careful attention to the following issues: definition of pattern classes,

sensing environment, pattern representation, feature extraction and selection, cluster analysis, classifier design and learning, selection

of training and test samples, and performance evaluation. In spite of almost 50 years of research and development in this field, the

general problem of recognizing complex patterns with arbitrary orientation, location, and scale remains unsolved. New and emerging

æ

1INTRODUCTION

B

Y the time they are five years old, most children can

recognize digits and letters. Small characters, large

characters, handwritten, machine printed, or rotatedÐall

are easily recognized by the young. The characters may be

written on a cluttered background, on crumpled paper or

may even be partially occluded. We take this ability for

granted until we face the task of teaching a machine how to

elusive goal.

The best pattern recognizers in most instances are

humans, yet we do not understand how humans recognize

patterns. Ross [140] emphasizes the work of Nobel Laureate

Herbert Simon whose central finding was that pattern

recognition is critical in most human decision making tasks:

ªThe more relevant patterns at your disposal, the better

your decisions will be. This is hopeful news to proponents

of artificial intelligence, since computers can surely be

taught to recognize patterns. Indeed, successful computer

processors, and domain knowledge to make decisions

automatically.

Automatic (machine) recognition, description, classifica-

tion, and grouping of patterns are important problems in a

variety of engineering and scientific disciplines such as

biology, psychology, medicine, marketing, computer vision,

artificial intelligence, and remote sensing. But what is a

pattern? Watanabe [163] defines a pattern ªas opposite of a

chaos; it is an entity, vaguely defined, that could be given a

2) unsupervised classification (e.g., clustering) in which the

pattern is assigned to a hitherto unknown class. Note that

the recognition problem here is being posed as a classifica-

tion or categorization task, where the classes are either

defined by the system designer (in supervised classifica-

tion) or are learned based on the similarity of patterns (in

unsupervised classification).

Interest in the area of pattern recognition has been

renewed recently due to emerging applications which are

not only challenging but also computationally more

recognition, called affective computing which will give a

computer the ability to recognize and express emotions, to

respond intelligently to human emotion, and to employ

mechanisms of emotion that contribute to rational decision

making. A common characteristic of a number of these

applications is that the available features (typically, in the

thousands) are not usually suggested by domain experts,

but must be extracted and optimized by data-driven

procedures.

The rapidly growing and available computing power,

cost). In many of the emerging applications, it is clear that

no single approach for classification is ªoptimalº and that

Consequently, combining several sensing modalities and

classifiers is now a commonly used practice in pattern

recognition.

The design of a pattern recognition system essentially

involves the following three aspects: 1) data acquisition and

preprocessing, 2) data representation, and 3) decision

of examples (training set) is an important and desired

attribute of most pattern recognition systems. The four best

known approaches for pattern recognition are: 1) template

matching, 2) statistical classification, 3) syntactic or struc-

tural matching, and 4) neural networks. These models are

pattern recognition method exists with different interpreta-

tions. Attempts have been made to design hybrid systems

involving multiple models [57]. A brief description and

curves, or shapes) of the same type. In template matching,

pattern to be recognized is available. The pattern to be

recognized is matched against the stored template while

taking into account all allowable pose (translation and

rotation) and scale changes. The similarity measure, often a

correlation, may be optimized based on the available

training set. Often, the template itself is learned from the

training set. Template matching is computationally de-

manding, but the availability of faster processors has now

nection weights so that a network can efficiently perform a

specific classification/clustering task. The increasing popu-

larity of neural network models to solve pattern recognition

problems has been primarily due to their seemingly low

dependence on domain-specific knowledge (relative to

model-based and rule-based approaches) and due to the

availability of efficient learning algorithms for practitioners

to use.

Neural networks provide a new suite of nonlinear

algorithms for feature extraction (using hidden layers)

similar to classical statistical pattern recognition methods

(see Table 3). Ripley [136] and Anderson et al. [5] also

discuss this relationship between neural networks and

statistical pattern recognition. Anderson et al. point out that

ªneural networks are statistics for amateurs... Most NNs

conceal the statistics from the user.º Despite these simila-

rities, neural networks do offer several advantages such as,

unified approaches for feature extraction and classification

and flexible procedures for finding good, moderately

nonlinear solutions.

literature on fuzzy classification and fuzzy clustering which

Interested readers can refer to the well-written books on

fuzzy pattern recognition by Bezdek [15] and [16]. In most

of the sections, the various approaches and methods are

summarized in tables as an easy and quick reference for the

reader. Due to space constraints, we are not able to provide

many details and we have to omit some of the approaches

and the associated references. Our goal is to emphasize

those approaches which have been extensively evaluated

the table of contents of all the issues of the IEEE

Transactions on Pattern Analysis and Machine Intelligence,

since its first publication in January 1979, reveals that

approximately 350 papers deal with pattern recognition.

Approximately 300 of these papers covered the statistical

approach and can be broadly categorized into the

following subtopics: curse of dimensionality (15), dimen-

sionality reduction (50), classifier design (175), classifier

combination (10), error estimation (25) and unsupervised

classification (50). In addition to the excellent textbooks

[111] in 1968 and by Kanal [89] in 1974. Nagy described

the early roots of pattern recognition, which at that time

was shared with researchers in artificial intelligence and

perception. A large part of Nagy's paper introduced a

number of potential applications of pattern recognition

and the interplay between feature definition and the

application domain knowledge. He also emphasized the

linear classification methods; nonlinear techniques were

based on polynomial discriminant functions as well as on

potential functions (similar to what are now called the

based on various distance measures between class-

conditional probability density functions and the result-

ing error bounds. Kanal's review also contained a large

section on structural methods and pattern grammars.

In comparison to the state of the pattern recognition field

as described by Nagy and Kanal in the 1960s and 1970s,

today a number of commercial pattern recognition systems

are available which even individuals can buy for personal

use (e.g., machine printed character recognition and

isolated spoken word recognition). This has been made

(e.g., structural pattern recognition, and rule-based sys-

tems). The starting point of our review (Section 2) is the

basic elements of statistical methods for pattern recognition.

It should be apparent that a feature vector is a representa-

tion of real world objects; the choice of the representation

strongly influences the classification results.

The topic of probabilistic distance measures is cur-

rently not as important as 20 years ago, since it is very

difficult to estimate density functions in high dimensional

completely resolved by a proper design of classification

(SVMs), discussed in Section 5, has largely contributed

to this understanding. In many real world problems,

patterns are scattered in high-dimensional (often) non-

linear subspaces. As a consequence, nonlinear procedures

and subspace approaches have become popular, both for

dimensionality reduction (Section 4) and for building

classifiers (Section 5). Neural networks offer powerful

(Section 6). Various approaches to estimating the error

rate of a classifier are presented in Section 7. The topic of

unsupervised classification or clustering is covered in

Section 8. Finally, Section 9 identifies the frontiers of

pattern recognition.

It is our goal that most parts of the paper can be

appreciated by a newcomer to the field of pattern

recognition. To this purpose, we have included a number

of examples to illustrate the performance of various

algorithms. Nevertheless, we realize that, due to space

design a number of commercial recognition systems. In

statistical pattern recognition, a pattern is represented by a

feature vector. Well-known concepts from statistical

decision theory are utilized to establish decision boundaries

between pattern classes. The recognition system is operated

in two modes: training (learning) and classification (testing)

(see Fig. 1). The role of the preprocessing module is to

segment the pattern of interest from the background,

Fig. 1. Model for statistical pattern recognition.