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

In the modern trains operated by the Dutch Railways (Nederlandse Spoorwegen) in the Netherlands, there are on-board train management systems continuously monitoring the conditions of various train modules such as traction, climate, brake electronics and so forth. When an abnormal or particular situation occurs, the system will generate and store an event log on the local disk or on a remote disk using wireless data communications. These diagnostic events might give an indication of the train condition, and currently critical events are selected by business rules to give alarms on failure or malfunction to the control room. To give a better prediction on the trains status based on the condition monitoring data, sequences of diagnostic events instead of individual critical events are analyzed in this work. Moreover, train delays instead of train failures are used as targets for providing more insight on the degeneration behavior of trains. We have adopted the word sequence kernel for learning the similarity between all sequence pairs, where each diagnostic event is considered as a word. To include multi-length word interpretations, we propose to combine the word sequence kernels of various lengths, where length=1 means one word is matched, length=2 means two words are matched, and so on. A kernel machine or similarity-based model can be learned directly on this combined word sequence kernel. The experimental results demonstrate that combining word sequence kernels of different lengths can bring a richer description to similarity measurements and gives better prediction performance.@en

In the modern trains operated by the Dutch Railways (Nederlandse Spoorwegen) in the Netherlands, there are on-board train management systems continuously monitoring the conditions of various train modules such as traction, climate, brake electronics and so forth. When an abnormal or particular situation occurs, the system will generate and store an event log on the local disk or on a remote disk using wireless data communications. These diagnostic events might give an indication of the train condition, and currently critical events are selected by business rules to give alarms on failure or malfunction to the control room. To give a better prediction on the trains status based on the condition monitoring data, sequences of diagnostic events instead of individual critical events are analyzed in this work. Moreover, train delays instead of train failures are used as targets for providing more insight on the degeneration behavior of trains. We have adopted the word sequence kernel for learning the similarity between all sequence pairs, where each diagnostic event is considered as a word. To include multi-length word interpretations, we propose to combine the word sequence kernels of various lengths, where length=1 means one word is matched, length=2 means two words are matched, and so on. A kernel machine or similarity-based model can be learned directly on this combined word sequence kernel. The experimental results demonstrate that combining word sequence kernels of different lengths can bring a richer description to similarity measurements and gives better prediction performance.@en

The question is discussed from where the patterns arise that are recognized in the world. Are they elements of the outside world, or do they originate from the concepts that live in the mind of the observer? It is argued that they are created during observation, due to the knowledge on which the observation ability is based. For an experienced observer this may result in a direct recognition of an object or phenomenon without any reasoning. Afterwards and using conscious effort he may be able to supply features or arguments that he might have used for his recognition. The discussion is phrased in the philosophical debate between monism, in which the observer is an element of the observed world, and dualism, in which these two are fully separated. Direct recognition can be understood from a monistic point of view. After the definition of features and the formulation of a reasoning, dualism may arise. An artificial pattern recognition system based on these specifications thereby creates a clear dualistic situation. It fully separates the two worlds by physical sensors and mechanical reasoning. This dualistic position can be solved by a responsible integration of artificially intelligent systems in human controlled applications. A set of simple experiments based on the classification of histopathological slides is presented to illustrate the discussion.@en

Keywords autofluorescence spectroscopy ¿ cancer detection ¿ combined classifiers ¿ oral cancer ¿ reflectance spectroscopy Abstract Background and Objectives Autofluorescence and diffuse reflectance spectroscopy have been used separately and combined for tissue diagnostics. Previously, we assessed the value of autofluorescence spectroscopy for the classification of oral (pre-)malignancies. In the present study, we want to determine the contributions of diffuse reflectance and autofluorescence spectroscopy to diagnostic performance. Study Design/Materials and Methods Autofluorescence and diffuse reflectance spectra were recorded from 172 oral lesions and 70 healthy volunteers. Autofluorescence spectra were corrected in first order for blood absorption effects using diffuse reflectance spectra. Principal Components Analysis (PCA) with various classifiers was applied to distinguish (1) cancer and (2) all lesions from healthy oral mucosa, and (3) dysplastic and malignant lesions from benign lesions. Autofluorescence and diffuse reflectance spectra were evaluated separately and combined. Results The classification of cancer versus healthy mucosa gave excellent results for diffuse reflectance as well as corrected autofluorescence (Receiver Operator Characteristic (ROC) areas up to 0.98). For both autofluorescence and diffuse reflectance spectra, the classification of lesions versus healthy mucosa was successful (ROC areas up to 0.90). However, the classification of benign and (pre-)malignant lesions was not successful for raw or corrected autofluorescence spectra (ROC areas@en

A linear, discriminative, supervised technique for reducing feature vectors extracted from image data to a lower-dimensional representation is proposed. It is derived from classical linear discriminant analysis (LDA), extending this technique to cases where there is dependency between the output variables, i.e., the class labels, and not only between the input variables. (The latter can readily be dealt with in standard LDA.) The novel method is useful, for example, in supervised segmentation tasks in which high-dimensional feature vectors describe the local structure of the image. The principal idea is that where standard LDA merely takes into account a single class label for every feature vector, the new technique incorporates class labels of its neighborhood in the analysis as well. In this way, the spatial class label configuration in the vicinity of every feature vector is accounted for, resulting in a technique suitable for, e.g. image data. This extended LDA, that takes spatial label context into account, is derived from a formulation of standard LDA in terms of canonical correlation analysis. The novel technique is called the canonical contextual correlation projection (CCCP). An additional drawback of LDA is that it cannot extract more features than the number of classes minus one. In the two-class case this means that only a reduction to one dimension is possible. Our contextual LDA approach can avoid such extreme deterioration of the classification space and retain more than one dimension. The technique is exemplified on a pixel-based medical image segmentation problem in which it is shown that it may give significant improvement in segmentation accuracy. Keywords: Dimensionality reduction; Feature extraction; Contextual information; Canonical correlation analysis; Image data@en

Recently bagging, boosting and the random subspace method have become popular combining techniques for improving weak classifiers. These techniques are designed for, and usually applied to, decision trees. In this paper, in contrast to a common opinion, we demonstrate that they may also be useful in linear discriminant analysis. Simulation studies, carried out for several artificial and real data sets, show that the performance of the combining techniques is strongly affected by the small sample size properties of the base classifier: boosting is useful for large training sample sizes, while bagging and the random subspace method are useful for critical training sample sizes. Finally, a table describing the possible usefulness of the combining techniques for linear classifiers is presented. Key words: Bagging; Boosting; Combining classifiers; Linear classifiers; Random subspaces; Training sample size@en

The generalization from two-class classification to multiclass classification is not straightforward for discriminants which are not based on density estimation. Simple combining methods use voting, but this has the drawback of inconsequent labelings and ties. More advanced methods map the discriminant outputs to approximate posterior probability estimates and combine these, while other methods use error-correcting output codes. In this paper we want to show the possibilities of simple generalizations of the twoclass classification, using voting and combinations of approximate posterior probabilities.@en

The generalization from two-class classification to multiclass classification is not straightforward for discriminants which are not based on density estimation. Simple combining methods use voting, but this has the drawback of inconsequent labelings and ties. More advanced methods map the discriminant outputs to approximate posterior probability estimates and combine these, while other methods use error-correcting output codes. In this paper we want to show the possibilities of simple generalizations of the twoclass classification, using voting and combinations of approximate posterior probabilities.@en

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

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

Sometimesnoveloroutlierdatahastobedetected.Theoutliersmayindicatesomeinterestingrareevent,ortheyshouldbedisregardedbecausetheycannotbereliablyprocessedfurther.Intheidealcasethattheobjectsarerepresentedbyverygoodfeatures,thegenuinedataformsacompactclusterandagoodoutliermeasureisthedistancetotheclustercenter.Thispaperproposesthreenewformulationsto¿ndagoodclustercentertogetherwithanoptimizedp-distancemeasure.Experimentsshowthatforsomerealworlddatasetsverygoodclassi¿cationresultsareobtainedandthat,morespeci¿cally,the1-distanceisparticularlysuitedfordatasetscontainingdiscretefeaturevalues.@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

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

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

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