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.

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.

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

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

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