Advances in Statistical Pattern Recognition
Published 1 January 1987
Anil K. Jain
Citations53
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
Current research emphasis in pattern recognition is on designing efficient algorithms, studying small sample properties of various estimators and decision rules, implementing the algorithms on novel computer architecture, and incorporating context and domain-specific knowledge in decision making.
Abstract
Statistical pattern recognition is now a mature discipline which has been successfully applied in several application domains. The primary goal in statistical pattern recognition is classification, where a pattern vector is assigned to one of a finite number of classes and each class is characterized by a probability density function on the measured features. A pattern vector is viewed as a point in the multidimensional space defined by the features. Design of a recognition system based on this paradigm requires careful attention to the following issues: type of classifier (single-stage vs. hierarchical), feature selection, estimation of classification error, parametric vs. nonparametric decision rules, and utilizing contextual information. Current research emphasis in pattern recognition is on designing efficient algorithms, studying small sample properties of various estimators and decision rules, implementing the algorithms on novel computer architecture, and incorporating context and domain-specific knowledge in decision making.
Keywords
Computer Science
Pattern classification and scene analysis
12,643 Citations1973Richard O. Duda, Peter E. Hart
Society for Industrial and Applied Mathematics eBooksThe Jackknife, the Bootstrap and Other Resampling Plans
7,903 Citations1982Bradley Efron
Journal of the American Statistical AssociationEstimating the Error Rate of a Prediction Rule: Improvement on Cross-Validation
2,161 Citations1983Bradley Efron
IEEE Transactions on ComputersA Branch and Bound Algorithm for Feature Subset Selection
1,240 Citations1977Narendra, Fukunaga
A feature subset selection algorithm based on branch and bound techniques is developed to select the best subset of m features from an n-feature set with the computational effort of evaluating only 6000 subsets.
Journal of the American Statistical AssociationEstimating the Error Rate of a Prediction Rule: Improvement on Cross-Validation
581 Citations1983Bradley Efron
Handbook of statistics39 Dimensionality and sample size considerations in pattern recognition practice
556 Citations1982A. Jain, B. Chandrasekaran
It is shown that as the number of samples increases, not only does the designer have more confidence in the performance of the classifier, but also more measurements can be incorporated in the design of the classify without the fear of peaking in its performance.
IEEE Transactions on Pattern Analysis and Machine IntelligenceA Problem of Dimensionality: A Simple Example
427 Citations1979G.V. Trunk
In pattern recognition problems it has been noted that beyond a certain point the inclusion of additional parameters (that have been estimated) leads to higher probabilities of error, so the probability of error approaches one-half as the dimensionality increases and parameters are estimated.
IEEE Transactions on Pattern Analysis and Machine IntelligenceAutomated Construction of Classifications: Conceptual Clustering Versus Numerical Taxonomy
317 Citations1983Ryszard S. Michalski, Robert E. Stepp
A method for automated construction of classifications called conceptual clustering is described and compared to methods used in numerical taxonomy, in which descriptive concepts are conjunctive statements involving relations on selected object attributes and optimized according to an assumed global criterion of clustering quality.
Pattern RecognitionValidity studies in clustering methodologies
300 Citations1979Richard C. Dubes, Anil K. Jain
This paper provides a semi-tutorial review of the state-of-the-art in cluster validity, or the verification of results from clustering algorithms, and covers ways of measuring clustering tendency, the fit of hierarchical and partitional structures and indices of compactness and isolation for individual clusters.
IEEE Transactions on Information TheoryConsiderations of sample and feature size
292 Citations1972Donald H. Foley
The design-set error rate for a two-class problem with multivariate normal distributions is derived as a function of the sample size per class (N) and dimensionality (L) and is demonstrated to be an extremely biased estimate of either the Bayes or test- set error rate.
Advances in computersClustering Methodologies in Exploratory Data Analysis
287 Citations1980Richard C. Dubes, Anil Jain
The chapter focuses on the four operations highlighted by reviewing techniques for assessing the tendency of the data to cluster, performing the clustering itself, and evaluating the validity of the results, and introduces the concept of intrinsic dimensionality that helps determine an appropriate number of factors for representing data.
IEEE Transactions on ComputersComputational Geometry—A Survey
285 Citations1984Lee, Preparata
The state of the art of computational geometry is surveyed, a discipline that deals with the complexity of geometric problems within the framework of the analysis of algorithms.
IEEE Transactions on Systems Man and CyberneticsOn the Possible Orderings in the Measurement Selection Problem
256 Citations1977Thomas M. Cover, Jan Van Campenhout
It is shown that for any ordering on the probability of error as a function of the subset of measurements (subject to an obvious set monotonicity condition), there exists a multivariate normal two-hypothesis problem N(K) versus N(¿¿,K) that exhibits this ordering.
The Annals of StatisticsLarge Sample Optimality of Least Squares Cross-Validation in Density Estimation
231 Citations1983Peter Hall
IEEE Transactions on Pattern Analysis and Machine IntelligenceNonparametric Discriminant Analysis
223 Citations1983Keinosuke Fukunaga, James M. Mantock
Using the same basic framework, a procedure is proposed to test the structural similarity of two distributions, and the form which results provides a unified view of the parametric nearest mean reclassification algorithm and the nonparametric valley seeking algorithm.
An inference technique for integrating knowledge from disparate sources
222 Citations1981Thomas D. Garvey, John D. Lowrance +1 more
IEEE Transactions on Pattern Analysis and Machine IntelligenceBootstrap Techniques for Error Estimation
202 Citations1987Anil K. Jain, Richard C. Dubes +1 more
Results on the application of several bootstrap techniques in estimating the error rate of 1-NN and quadratic classifiers show that, in most cases, the confidence interval of a bootstrap estimator of classification error is smaller than that of the leave-one-out estimator.
Pattern Recognition LettersPattern Recognition in Practice VI
192 Citations1999E. S. Gelsema, Jifke F. Veenland
This special issue contains most of the papers presented at the conference ``Pattern Recognition in Practice VI'' held on Vlieland, The Netherlands, from 2 to 4 June 1999, to stimulate interaction between pattern recognition professionals and scientists from other disciplines who bring pattern recognition techniques into practice.
IEEE Transactions on Pattern Analysis and Machine IntelligenceHierarchical Classifier Design Using Mutual Information
183 Citations1982Ishwar K. Sethi, G. P. R. Sarvarayudu
A nonparametric algorithm is presented for the hierarchical partitioning of the feature space that generates an efficient partitioning tree for specified probability of error by maximizing the amount of average mutual information gain at each partitioning step.
Pattern RecognitionGraph theoretical clustering based on limited neighbourhood sets
173 Citations1982R.B. Urquhart
The method is locally sensitive, hierarchic and based on the concept of limited neighbourhood sets, which means clusters that are either disjoint or homogeneous and separable by sharp changes in point density may be detected.
Pattern RecognitionAn optimal orthonormal system for discriminant analysis
148 Citations1985Toshiniko Okada, Shingo Tomita
The new discriminant analysis with orthonormal coordinate axes of the feature space is proposed, which is more powerful than the traditional one in so far as the discriminatory power and the mean error probability for coordinate axes are concerned.
IEEE Transactions on Pattern Analysis and Machine IntelligenceA Step Towards Unification of Syntactic and Statistical Pattern Recognition
136 Citations1986K. S. Fu
A combined syntactic-semantic approach based on attributed grammars is suggested, intended to be an initial step toward unification of syntactic and statistical approaches to pattern recognition.
Pattern RecognitionThe use of context in pattern recognition
129 Citations1978Godfried T. Toussaint
A tutorial survey of techniques for using contextual information in pattern recognition is presented, with emphasis on the problems of image classification and text recognition, where the text is in the form of machine and handprinted characters, cursive script, and speech.
IEEE Transactions on Pattern Analysis and Machine IntelligenceAn Optimal Global Nearest Neighbor Metric
118 Citations1984Keinosuke Fukunaga, Thomas E. Flick
A quadratic metric dAO (X, Y) =[( X - Y)T AO(X - Y)]¿ is proposed which minimizes the mean-squared error between the nearest neighbor asymptotic risk and the finite sample risk.
IEEE Transactions on Pattern Analysis and Machine IntelligenceAutomated classification of nucleated blood cells using a binary tree classifier
109 Citations1980Jack K. Mui, King‐Sun Fu
The binary tree classifier with a quadratic discriminant function using up to ten features at each nonterminal node was applied to classify 1294 cells into one of 17 classes.
IEEE Transactions on Pattern Analysis and Machine IntelligenceEvaluation of Projection Algorithms
96 Citations1981Gautam Biswas, Anil K. Jain +1 more
A combination of two popular mapping algorithms-Sammon's mean-square error technique and the triangulation method-is proposed to overcome the limitations in the individual algorithms.
Pattern RecognitionMaximum likelihood discriminant analysis on the plane using a Markovian model of spatial context
92 Citations1985John Haslett
A method for utilising spatial information in performing discriminant analysis on multivariate data at each point on a regular lattice, as for example with LANDSAT, seems to be encouraging.
IEEE Transactions on Pattern Analysis and Machine IntelligenceOn an Extended Fisher Criterion for Feature Selection
87 Citations1981Witold Malina
This correspondence considers the extraction of features as a task of linear transformation of an initial pattern space into a new space, optimal with respect to discriminating the data.
Pattern RecognitionContextual classification of multispectral image data
85 Citations1981Philip H. Swain, Stephen B. Vardeman +1 more
Experimental results based on both simulated and real multispectral remote sensing data demonstrate the effectiveness of the contextual classifier.
IEEE Transactions on Pattern Analysis and Machine IntelligenceTesting for Uniformity in Multidimensional Data
81 Citations1984Stephen P. Smith, Anil K. Jain
A simple, computationally efficient method for generating a uniformly distributed sample over a set which approximates the convex hul of the data and test for uniformity by using Friedman-Rafsky's minimal spanning tree (MST) based test is provided.
IEEE Transactions on Pattern Analysis and Machine IntelligenceConceptual Clustering in Knowledge Organization
81 Citations1985Yizong Cheng, King-Sun Fu
Concepts used in knowledge description are divided into tangible ones and intermediate ones depending on whether or not they appear in the input or the output of the system.
IEEE Transactions on Pattern Analysis and Machine IntelligenceParallel Branch-and-Bound Formulations for AND/OR Tree Search
81 Citations1984Vipin Kumar, Laveen N. Kanal
Two general schemes for performing branch-and-bound (B&B) search in parallel are discussed, applicable in principle to most of the problems which can be solved by B&B.
IEEE Transactions on Pattern Analysis and Machine IntelligenceThe Use of Shrinkage Estimators in Linear Discriminant Analysis
71 Citations1982Roger Peck, John Van Ness
This paper studies using a shrinkage estimate for the covariance matrix in the linear algorithm, because its simple structure allows one to more easily ascertain the effects of the use of shrinkage estimates.
IEEE Transactions on Pattern Analysis and Machine IntelligenceA VLSI Systolic Architecture for Pattern Clustering
71 Citations1985Lionel M. Ni, Anil K. Jain
A two-level pipelined systolic pattern clustering array is proposed and the modularity and the regularity of the system architecture make it suited for VLSI implementations.
IEEE Transactions on Pattern Analysis and Machine IntelligencePredicting the Required Number of Training Samples
70 Citations1983H. M. Kalayeh, D. A. Landgrebe
A criterion which measures the quality of the estimate of the covariance matrix of a multivariate normal distribution is developed and the necessary number of training samples is predicted.
Pattern Recognition LettersAn improved branch and bound algorithm for computing k-nearest neighbors
65 Citations1985Behrooz Kamgar-Parsi, Laveen N. Kanal
Experimental results using samples from bivariate Gaussian and uniform distributions suggest that the number of distance computations required by the modified algorithm is typicaly one fourth of that of the Fukunaga-Narendra algorithm.
IEEE Transactions on Pattern Analysis and Machine IntelligenceBias of Nearest Neighbor Error Estimates
61 Citations1987Keinosuke Fukunaga, D.M. Hummels
It is shown that when the dimensionality of the data is high, it may not be possible to estimate the asymptotic error simply by increasing the sample size, and a new procedure is suggested to alleviate this problem.
Pattern Recognition LettersApplication of bootstrap and other resampling techniques: Evaluation of classifier performance
61 Citations1985Michael R. Chernick, V. K. Murthy +1 more
This paper presents a simulation comparing various resampling procedures for estimating classification error rate, for the two-class and three-class problems.
Pattern RecognitionThe artificial intelligence approach to pattern recognition—a perspective and an overview
58 Citations1985N. Nandhakumar, J.K. Aggarwal
The paper reviews salient issues in the application of conventional techniques for extraction of information and the systems that use the artificial intelligence approach are characterized with respect to three key properties.
Pattern RecognitionControl strategies in pattern analysis
57 Citations1984Makoto Nagao
The importance of the declarative method in pattern analysis, especially in the patterns of complex objects, is stressed and the feedback and recursive applications of analysis algorithms are mentioned to obtain the accurate results.
Pattern RecognitionOn the dominance of non-parametric Bayes rule discriminant algorithms in high dimensions
55 Citations1980John Van Ness
Monte Carlo results presented here further confirm the relatively good performance of non-parametric Bayes theorem type algorithms compared to parametric (linear and quadratic) algorithms and point out certain procedures which should be used in the selection of the density estimation windows for non- Parametric algorithms to improve their performance.
Fresenius Zeitschrift für Analytische ChemieApplications of pattern recognition
55 Citations1982D.L. Massart, L.M.C. Buydens +13 more
Pattern RecognitionThe ALSM algorithm — an improved subspace method of classification
47 Citations1983Erkki Oja, Maija Kuusela
A variant of the original learning rule is analyzed and results are given on its application to the classification of phonemes in automatic speech recognition.
IEEE Transactions on Pattern Analysis and Machine IntelligenceAn Integrated Algorithm for Text Recognition: Comparison with a Cascaded Algorithm
45 Citations1983Jonathan J. Hull, Sargur N. Srihari +1 more
Two algorithms, one based on integrating the knowledge sources in a single step and the other based on sequentially cascading bottom-up and top-down processes, are compared in terms of computational/storage requirements and results of experimentation.
IEEE Transactions on Systems Man and CyberneticsSynthesizing Knowledge: A Cluster Analysis Approach Using Event Covering
45 Citations1986David Chiu, Andrew K. C. Wong
An event-covering method for synthesizing knowledge gathered from empirical observations based on the detection of statistically significant events through the use of a special clustering algorithm, capable of clustering ordered and unordered discrete-valued data that are subject to noise perturbation.
IEEE Transactions on Pattern Analysis and Machine IntelligenceA Fast Algorithm for Nonparametric Probability Density Estimation
38 Citations1982J.‐G. Postaire, Christian Vasseur
A fast algorithm for the well-known Parzen window method to estimate density functions from the samples is described and makes the computation of the same density estimates with a substantial reduction of computer time possible, especially for data of high dimensionality.
Pattern RecognitionTree classifier design with a permutation statistic
35 Citations1986Xiaobo Li, Richard C. Dubes
A permutation statistic is proposed as a basis for designing binary tree classifiers of d -dimensional patterns and the design procedure whereby each non-terminal node is assigned a feature and a threshold on that feature.
IEEE Transactions on Information TheoryThe optimum nonlinear features for a scatter criterion in discriminant analysis
28 Citations1977Keinosuke Fukunaga, Shin Ando
The trace of the between-class scatter matrix normalized by the mixture scatter matrix is chosen as the criterion to measure the degree of overlap among class distributions, and it is shown that the {\em a posteriori} probability functions maximize this criterion.
IEEE Transactions on Pattern Analysis and Machine IntelligenceClassification Error for a Very Large Number of Classes
25 Citations1984Keinosuke Fukunaga, Thomas E. Flick
The error associated with classifying to a single class is shown to depend mainly on average nearest-neighbor distance between class means, noise level, and effective dimensionality of the class mean distribution and not much on other aspects of the distribution, noise correlation, or number of classes.
IEEE Transactions on Pattern Analysis and Machine IntelligenceCandide's Practical Principles of Experimental Pattern Recognition
25 Citations1983George Nagy
This correspondence calls attention to several frequently used assumptions and techniques culled from the pattern recognition literature.
Pattern Recognition LettersApproximative fast nearest-neighbour recognition
24 Citations1983Laurent Miclet, M. Dabouz
This work analyzes (on pseudo-randomly generated data) the errors committed with a log(N) algorithm, attempting to recognize the nearest neighbour among N vectors, and proposes improvements in O(log(N), and presents an example of application on speech data.
IEEE Transactions on Pattern Analysis and Machine IntelligenceNoah-A Bottom-Up Word Hypothesizer for Large-Vocabulary Speech Understanding Systems
23 Citations1981A. Smith, Lee D. Erman
The design and performance of Noah are presented, a bottom-up word hypothesizer which is capable of handling large vocabularies-more than 10 000 words, and the performance is presented as a function of the vocabulary size.
IEEE Transactions on Pattern Analysis and Machine IntelligenceApplications of Quadtree, Octree, and Binary Tree Decomposition Techniques to Shape Analysis and Pattern Recognition
21 Citations1985B.B. Chaudhuri
The binary tree, quadtree, and octree decomposition techniques are reexamined for pattern recognition and shape analysis applications and it has been shown that the quadtree andOctree techniques can be used to find the shape hull of a set of points in space while their n-dimensional generalization can be use for divisive hierarchical clustering.
IEEE Transactions on Pattern Analysis and Machine IntelligenceA Test of the Gaussian-ness of a Data Set Using Clustering
18 Citations1986Keinosuke Fukunaga, Thomas E. Flick
The properties of the ``magnifying glass'' method of clustering'' lead to the development of a technique for testing data to determine whether or not it is Gaussian and an example of a non-Gaussian distribution is given to show the sensitivity of the proposed Gaussian test.
IEEE Transactions on Pattern Analysis and Machine IntelligenceClassification by Thresholding
15 Citations1983Alan H. Feiveson
A procedure is given which substantially reduces the processing time needed to perform maximum likelihood classification on large data sets by using a set of fixed thresholds which, if exceeded by one probability density function, makes it unnecessary to evaluate a competing density function.
Elsevier eBooksFROM NUMBERS TO SYMBOLS TO KNOWLEDGE STRUCTURES: PATTERN RECOGNITION AND ARTIFICIAL INTELLIGENCE PERSPECTIVES ON THE CLASSIFICATION TASK
15 Citations1986Bharath Chandrasekaran
A very general information processing task: classification is considered, and the evolution of the algorithms from numerical parameter setting schemes through those using symbolic abstractions and then relations between symbolic entities, and finally to complex symbolic descriptions which incorporate explicit domain knowledge are traced.
IEEE Transactions on ComputersGeneralized Clustering for Problem Localization
11 Citations1978Fukunaga, Kevin R. Short
The general procedure of conventional clustering is modified for various applications involving problem localization, and the concept of clustering criteria which are used for partitioning a training set, and depend upon certain a priori information with regards to the training set are introduced.
Information Processing LettersConvex hull made easy
11 Citations1986Michael Kallay
Given a finite set S of n points and a point q in R d, deciding if q ϵconv S is a matter of one linear program of size n, after a very simple linear-time preprocessing of S is solved.
IEEE Transactions on Pattern Analysis and Machine IntelligenceData Structures in Kernel Density Estimation
10 Citations1985Luc Devroye, Fred Machell
Frequent evaluations of this estimate are for example needed for plotting, error estimation, Monte Carlo estimation of probabilities and functionals, and pattern classification.
Pattern Recognition LettersSome practical aspects of covariance estimation
9 Citations1985Jerome P. Keating, Robert Mason
It is shown that alternative robust estimators of the covariance matrix are appealing in analyzing VCG data when outliers are present in the sample and should be greatly expanded in order to validate the asymptotic properties of S.
Pattern Recognition LettersLinear, structured covariance estimation: An application to pattern classification for remote sensing
8 Citations1986S.D. Morgera
The advantage of estimating the covariance using a linear, structured model over the conventionally used general sample covariance is quantified in terms of the expected improvement in signal-to-interference ratio as a function of available sample size.
IEEE Transactions on Pattern Analysis and Machine IntelligenceExtremes in the Complexity of Computing Metric Distances Between Partitions
8 Citations1984W. H. Day, Robert Wells
Pattern Recognition LettersInsert and delete algorithms for maintaining dynamic Delaunay triangulations
6 Citations1982Pierre A. Devijver, Michel M. Dekesel
Two algorithms are described, Insert and Delete, which permit to maintain a dynamic Delaunay triangulation of the training set and argue that, from the viewpoint of computational complexity, an iterative approach using a dynamic Triangulation is most desirable.