This ebook gives the starting student an introduction into the eld of pattern recognition. It may serve as reference to others by giving intuitive descriptions of the terminology. The book is the rst in a series of ebooks on topics and examples in the eld. Our goal is an informal explanation of the concepts. For thorough mathematical descriptions we refer to the textbooks and lectures. In ten chapters the topics of pattern recognition are summarized and its terminology is introduced. In the glossary about 200 terms are described. All glossary terms are linked, forward and backward by hypertext. In the glossary chapter external links are provided to internet pages, papers tutorials, Wikipedia entries, examples, etcetera. Internal links are in dark blue in order to preserve the readability. External links are in blue. This ebook is offered by the authors of a website on pattern recognition tools, http://37steps.com/. Here more information, software, data and examples can be found. The book itself does not assume the use of specific software. The code for generating the examples, however, is written in Matlab using PRTools. It can be inspected by clicking on the gures or example links.@en

Sometimesnoveloroutlierdatahastobedetected.Theoutliersmayindicatesomeinterestingrareevent,ortheyshouldbedisregardedbecausetheycannotbereliablyprocessedfurther.Intheidealcasethattheobjectsarerepresentedbyverygoodfeatures,thegenuinedataformsacompactclusterandagoodoutliermeasureisthedistancetotheclustercenter.Thispaperproposesthreenewformulationsto¿ndagoodclustercentertogetherwithanoptimizedp-distancemeasure.Experimentsshowthatforsomerealworlddatasetsverygoodclassi¿cationresultsareobtainedandthat,morespeci¿cally,the1-distanceisparticularlysuitedfordatasetscontainingdiscretefeaturevalues.@en

Abstract A conventional way to discriminate between objects represented by dissimilarities is the nearest neighbor method. A more efficient and sometimes a more accurate solution is offered by other dissimilarity-based classifiers. They construct a decision rule based on the entire training set, but they need just a small set of prototypes, the so-called representation set, as a reference for classifying new objects. Such alternative approaches may be especially advantageous for non-Euclidean or even non-metric dissimilarities. The choice of a proper representation set for dissimilarity-based classifiers is not yet fully investigated. It appears that a random selection may work well. In this paper, a number of experiments has been conducted on various metric and non-metric dissimilarity representations and prototype selection methods. Several procedures, like traditional feature selection methods (here effectively searching for prototypes), mode seeking and linear programming are compared to the random selection. In general, we find out that systematic approaches lead to better results than the random selection, especially for a small number of prototypes. Although there is no single winner as it depends on data characteristics, the k-centres works well, in general. For two-class problems, an important observation is that our dissimilarity-based discrimination functions relying on significantly reduced prototype sets (3¿10% of the training objects) offer a similar or much better classification accuracy than the best k-NN rule on the entire training set. This may be reached for multi-class data as well, however such problems are more difficult. Keywords: Dissimilarity; Representation; Prototype selection; Normal density based classifiers; Nearest neighbor rule@en

Feature based approaches to pattern recognition suffer from the fact that feature representations of different classes of objects may overlap. This is the consequence of reducing the description of an object to a feature vector. As a result an error free recognition system is even asymptotically (for infinite training sizes) impossible. In this paper it is argued that this limitation does not hold for dissimilarity based representations. Suggestions are made how this may be exploited in practice.@en

A common way of expressing string similarity in structural pattern recognition is the edit distance. It allows one to apply the kNN rule in order to classify a set of strings. However, compared to the wide range of elaborated classi¿ers known from statistical pattern recognition, this is only a very basic method. In the present paper we propose a method for transforming strings into n-dimensional real vector spaces based on prototype selection. This allows us to subsequently classify the transformed strings with more sophisticated classi¿ers, such as support vector machine and other kernel based methods. In a number of experiments, we show that the recognition rate can be signi¿cantly improved by means of this procedure.@en

A common way of expressing string similarity in structural pattern recognition is the edit distance. It allows one to apply the kNN rule in order to classify a set of strings. However, compared to the wide range of elaborated classi¿ers known from statistical pattern recognition, this is only a very basic method. In the present paper we propose a method for transforming strings into n-dimensional real vector spaces based on prototype selection. This allows us to subsequently classify the transformed strings with more sophisticated classi¿ers, such as support vector machine and other kernel based methods. In a number of experiments, we show that the recognition rate can be signi¿cantly improved by means of this procedure.@en

A common way of expressing string similarity in structural pattern recognition is the edit distance. It allows one to apply the kNN rule in order to classify a set of strings. However, compared to the wide range of elaborated classi¿ers known from statistical pattern recognition, this is only a very basic method. In the present paper we propose a method for transforming strings into n-dimensional real vector spaces based on prototype selection. This allows us to subsequently classify the transformed strings with more sophisticated classi¿ers, such as support vector machine and other kernel based methods. In a number of experiments, we show that the recognition rate can be signi¿cantly improved by means of this procedure.@en

A common way of expressing string similarity in structural pattern recognition is the edit distance. It allows one to apply the kNN rule in order to classify a set of strings. However, compared to the wide range of elaborated classi¿ers known from statistical pattern recognition, this is only a very basic method. In the present paper we propose a method for transforming strings into n-dimensional real vector spaces based on prototype selection. This allows us to subsequently classify the transformed strings with more sophisticated classi¿ers, such as support vector machine and other kernel based methods. In a number of experiments, we show that the recognition rate can be signi¿cantly improved by means of this procedure.@en

Statisticalinferenceofsensor-basedmeasurementsisintensivelystudiedinpatternrecognition.Itisusuallybasedonfeaturerepresentationsoftheobjectstoberecognized.Suchrepresentations,however,neglecttheobjectstructure.Structuralpatternrecognition,onthecontrary,focussesonencodingtheobjectstructure.Asgeneralproceduresarestillweaklydeveloped,suchobjectdescriptionsareoftenapplicationdependent.Thishamperstheusageofagenerallearningapproach. Thispaperaimstosummarizetheproblemsandpossibilitiesofgeneralstructuralinferenceapproachesforthefamilyofsensor-basedmeasurements:images,spectraandtimesignals,assumingacontinuitybetweenmeasurementsamples.Inparticularitwillbediscussedwhenprobabilisticassumptionsareneeded,leadingtoastatistically-basedinferenceofthestructure,andwhenapure,non-probabilisticstructuralinferenceschememaybepossible.@en

Statisticalinferenceofsensor-basedmeasurementsisintensivelystudiedinpatternrecognition.Itisusuallybasedonfeaturerepresentationsoftheobjectstoberecognized.Suchrepresentations,however,neglecttheobjectstructure.Structuralpatternrecognition,onthecontrary,focussesonencodingtheobjectstructure.Asgeneralproceduresarestillweaklydeveloped,suchobjectdescriptionsareoftenapplicationdependent.Thishamperstheusageofagenerallearningapproach. Thispaperaimstosummarizetheproblemsandpossibilitiesofgeneralstructuralinferenceapproachesforthefamilyofsensor-basedmeasurements:images,spectraandtimesignals,assumingacontinuitybetweenmeasurementsamples.Inparticularitwillbediscussedwhenprobabilisticassumptionsareneeded,leadingtoastatistically-basedinferenceofthestructure,andwhenapure,non-probabilisticstructuralinferenceschememaybepossible.@en

Pairwiseproximitiesdescribethepropertiesofobjectsintermsoftheirsimilarities.Byusingdi¿erentdistance-basedfunctionsonemayencodedi¿erentcharacteristicsofagivenproblem.However,tousetheframeworkofstatisticalpatternrecognitionsomevectorrepresentationshouldbeconstructed.Oneofthesimplestwaystodothatistode¿neanisometricembeddingtosomevectorspace.Inthiswork,wewillfocusonalinearembeddingintoa(pseudo-)Euclideanspace. Thisisusuallywellde¿nedfortrainingdata.Someinadequacy,however,appearswhenprojectingnewortestobjectsduetotheresultingprojectionerrors.Inthispaperweproposeanaugmentedembeddingalgorithmthatenlargesthedimensionalityofthespacesuchthattheresultingprojectionerrorvanishes.Ourpreliminaryresultsshowthatitmayleadtoabetterclassi¿cationaccuracy,especiallyfordatawithhighintrinsicdimensionality.@en

Pairwiseproximitiesdescribethepropertiesofobjectsintermsoftheirsimilarities.Byusingdi¿erentdistance-basedfunctionsonemayencodedi¿erentcharacteristicsofagivenproblem.However,tousetheframeworkofstatisticalpatternrecognitionsomevectorrepresentationshouldbeconstructed.Oneofthesimplestwaystodothatistode¿neanisometricembeddingtosomevectorspace.Inthiswork,wewillfocusonalinearembeddingintoa(pseudo-)Euclideanspace. Thisisusuallywellde¿nedfortrainingdata.Someinadequacy,however,appearswhenprojectingnewortestobjectsduetotheresultingprojectionerrors.Inthispaperweproposeanaugmentedembeddingalgorithmthatenlargesthedimensionalityofthespacesuchthattheresultingprojectionerrorvanishes.Ourpreliminaryresultsshowthatitmayleadtoabetterclassi¿cationaccuracy,especiallyfordatawithhighintrinsicdimensionality.@en

Pairwiseproximitiesdescribethepropertiesofobjectsintermsoftheirsimilarities.Byusingdi¿erentdistance-basedfunctionsonemayencodedi¿erentcharacteristicsofagivenproblem.However,tousetheframeworkofstatisticalpatternrecognitionsomevectorrepresentationshouldbeconstructed.Oneofthesimplestwaystodothatistode¿neanisometricembeddingtosomevectorspace.Inthiswork,wewillfocusonalinearembeddingintoa(pseudo-)Euclideanspace. Thisisusuallywellde¿nedfortrainingdata.Someinadequacy,however,appearswhenprojectingnewortestobjectsduetotheresultingprojectionerrors.Inthispaperweproposeanaugmentedembeddingalgorithmthatenlargesthedimensionalityofthespacesuchthattheresultingprojectionerrorvanishes.Ourpreliminaryresultsshowthatitmayleadtoabetterclassi¿cationaccuracy,especiallyfordatawithhighintrinsicdimensionality.@en

In classifier combining, one tries to fuse the information that is given by a set of base classifiers. In such a process, one of the difficulties is how to deal with the variability between classifiers. Although various measures and many combining rules have been suggested in the past, the problem of constructing optimal combiners is still heavily studied. In this paper, we discuss and illustrate the possibilities of classifier embedding in order to analyse the variability of base classifiers, as well as their combining rules. Thereby, a space is constructed in which classifiers can be represented as points. Such a space of a low dimensionality is a Classifier Projection Space (CPS). In the first instance, it is used to design a visual tool that gives more insight into the differences of various combining techniques. This is illustrated by some examples. In the end, we discuss how the CPS may also be used as a basis for constructing new combining rules.@en

Dissimilarity representations are of interest when it is hard to define well-discriminating features for the raw measurements. For an exploration of such data, the techniques of multidimensional scaling (MDS) can be used. Given a symmetric dissimilarity matrix, they find a lower-dimensional configuration such that the distances are preserved. Here, Sammon nonlinear mapping is considered. In general, this iterative method must be recomputed when new examples are introduced, but its complexity is quadratic in the number of objects in each iteration step. A simple modification to the nonlinear MDS, allowing for a significant reduction in complexity, is therefore considered, as well as a linear projection of the dissimilarity data. Now, generalization to new data can be achieved, which makes it suitable for solving classification problems. The linear and nonlinear mappings are then used in the setting of data visualization and classification. Our experiments show that the nonlinear mapping can be preferable for data inspection, while for discrimination purposes, a linear mapping can be recommended. Moreover, for the spatial lower-dimensional representation, a more global, linear classifier can be built, which outperforms the local nearest neighbor rule, traditionally applied to dissimilarities.@en

In image retrieval systems, images can be represented by single feature vectors or by clouds of points. A cloud of points offers a more flexible description but suffers from class overlap. We propose a novel approach for describing clouds of points based on support vector data description (SVDD). We show that combining SVDD-based classifiers improves the retrieval precision. We investigate the performance of the proposed retrieval technique on a database of 368 texture images and compare it to other methods.@en

StatisticallearningalgorithmsoftenrelyontheEuclideandistance.Inpractice,non-Euclideanornon-metricdissimilaritymeasuresmayarisewhencontours,spectraorshapesarecomparedbyeditdistancesorasaconsequenceofrobustobjectmatching[1,2].Itisanopenissuewhethersuchmeasuresareadvantageousforstatisticallearningorwhethertheyshouldbeconstrainedtoobeythemetricaxioms. Thek-nearestneighbor(NN)ruleiswidelyappliedtogeneraldissimilaritydataasthemostnaturalapproach.Alternativemethodsexistthatembedsuchdataintosuitablerepresentationspacesinwhichstatisticalclassi¿ersareconstructed[3].Inthispaper,weinvestigatetherelationbetweennon-Euclideanaspectsofdissimilaritydataandtheclassi¿cationperformanceofthedirectNNruleandsomeclassi¿erstrainedinrepresentationspaces.Thisisevaluatedonaparameterizedfamilyofeditdistances,inwhichparametervaluescontrolthestrengthofnon-Euclideanbehavior.Our¿ndingisthatthediscriminativepowerofthismeasureincreaseswithincreasingnon-Euclideanandnon-metricaspectsuntilacertainoptimumisreached.Theconclusionisthatstatisticalclassi¿ersperformwellandtheoptimalvaluesoftheparameterscharacterizeanon-Euclideanandsomewhatnon-metricmeasure@en

The nearest neighbor (NN) rule is a simple and intuitive method for solving classification problems. Originally, it uses distances to the complete training set. It performs well, however, it is sensitive to noisy objects, due to its operation on local neighborhoods only. A more global approach is possible by mapping the distance data onto a pseudo- Euclidean space, such that the distances are preserved as well as possible. Then, a classifier built in such a space can outperform the NN rule. However, again all objects from the training set are used for a projection of new data. This paper addresses the issue of reducing the training set while possibly preserving the original structure of the mapped data. Some criteria are introduced and evaluated against two problems, polygon recognition and digit recognition. Our experiments show that the representation mismatch criterion is beneficial for the applications considered. Moreover, the linear classifier built in the pseudo- Euclidean space, determined by 20%¿25% of the training objects, outperforms the NN rule based on all of them.@en

Usually, objects to be classified are represented by features. In this paper, we discuss an alternative object representation based on dissimilarity values. If such distances separate the classes well, the nearest neighbor method offers a good solution. However, dissimilarities used in practice are usually far from ideal and the performance of the nearest neighbor rule suffers from its sensitivity to noisy examples. We show that other, more global classification techniques are preferable to the nearest neighbor rule, in such cases. For classification purposes, two different ways of using generalized dissimilarity kernels are considered. In the first one, distances are isometrically embedded in a pseudo-Euclidean space and the classification task is performed there. In the second approach, classifiers are built directly on distance kernels. Both approaches are described theoretically and then compared using experiments with different dissimilarity measures and datasets including degraded data simulating the problem of missing values. Keywords: dissimilarity, embedding, pseudo-Euclidean space, nearest mean classifier, support vector classifier, Fisher linear discriminant@en

Prototype-based classification relies on the distances between the examples to be classified and carefully chosen prototypes. A small set of prototypes is of interest to keep the computational complexity low, while maintaining high classification accuracy. An experimental study of some old and new prototype optimisation techniques is presented, in which the prototypes are either selected or generated from the given data. These condensing techniques are evaluated on real data, represented in vector spaces, by comparing their resulting reduction rates and classification performance. Usually the determination of prototypes is studied in relation with the nearest neighbour rule. We will show that the use of more general dissimilarity-based classifiers can be more beneficial. An important point in our study is that the adaptive condensing schemes here discussed allow the user to choose the number of prototypes freely according to the needs. If such techniques are combined with linear dissimilarity-based classifiers, they provide the best trade-off of small condensed sets and high classification accuracy. Keywords: Dissimilarity representation; Prototype selection; Adaptive condensing; EM algorithm; Normal density based classifier; Nearest neighbour rule@en