Top

previous chapter Rule-Based Systems

next chapter Neural Networks

Hint

Swipe to navigate through the chapters of this book

2016 | OriginalPaper | Chapter

10. Pattern Recognition and Cluster Analysis

Author: Mariusz Flasiński

Publisher: Springer International Publishing

Published in: Introduction to Artificial Intelligence

» Get access to the full version

Abstract

Let us begin with a terminological remark, which concerns the notion of a pattern. In pattern recognition and cluster analysis various objects, phenomena, processes, structures, etc. can be considered as patterns.

Please log in to get access to this content

To get access to this content you need the following product:

Computer Science Explorer

Purchase now

In structural pattern recognition patterns are represented by structural representations, similarly to syntactic pattern recognition. However, their recognition is done with the help of pattern matching methods, not, as in the syntactic approach, by applying formal grammars and automata.

For example, patients can be considered as patterns and then pattern recognition can consist of classifying them into one of several disease entities.

For example in the area of Business Intelligence we can try to group customers on the basis of their features such as the date of their last purchase, the total value of their purchases for the last two months, etc. into categories which determine a sales strategy (e.g., cross-selling, additional free services/products).

A component represents some feature of the pattern.

If patterns are images, then noise filtering, smoothing/sharpening, enhancement, and restoration are typical preprocessing operations. Then, features such as edges, characteristic points, etc. are identified. Finally, image segmentation and object identification are performed.

This interesting phenomenon is discussed, e.g., in [235].

The most popular feature extraction methods include Principal Component Analysis (PCA), Independent Component Analysis, and Linear Discriminant Analysis. The issues related to feature extraction methods are out of the scope of Artificial Intelligence. Therefore, they are not discussed in the book. The reader can find a good introduction to this area in monographs cited at the end of this chapter.

This can be done, for example, with the help of the search methods introduced in Chap. 4.

Later we equate a pattern with its representation in the form of a feature vector.

In our “fish example” a reference pattern corresponds to a fish of the mean length and the mean weight in a given class.

In our fish example this means that an unknown fish corresponding to an unknown pattern in Fig. 10.1b is classified as a sprat ( \(\omega ^{1}\)), because it resembles the “reference sprat” \(\mathbf {R}^{1}\) more than the “reference eel” \(\mathbf {R}^{2}\). (That is, it is nearer to the “reference sprat” in the feature space.).

Evelyn Fix—a professor of statistics of the University of California, Berkeley, a Ph.D. student and then a principal collaborator of the eminent Polish-American mathematician and statistician Jerzy Spława-Neyman, who introduced the notion of a confidence interval (also, the Neyman-Pearson lemma).

Joseph Lawson Hodges, Jr—an eminent statistician (Hodges-Lahmann estimator, Hodges’ estimator) at the University of California, Berkeley, a Ph.D. student of Jerzy Spława-Neyman.

Thomas M. Cover—a professor at Stanford University, an author of excellent papers concerning models based on statistics and information theory.

Peter E. Hart—a professor of the Stanford University, a computer scientists (a co-author of a heuristic search method \(A^{*}\) and the model based on the Hough transform).

Vladimir Naumovich Vapnik—a professor at the Institute of Control Sciences, Moscow from 1961 to 1990, then at AT&T Bell Labs and NEC Laboratories, Princeton. His work concerns mainly statistics and Artificial Intelligence (Vapnik–Chervonenkis theory).

This is why the method is called Support Vector Machines.

Richard O. Duda—a professor of electrical engineering at San Jose State University. His achievements concern pattern recognition. He defined the Hough transform. He is a co-author of the excellent monograph “Pattern Classification and Scene Analysis”.

The basic notions of probability theory are introduced in Appendices I.1, B.1 and I.2.

Thomas Bayes—an eminent English mathematician and a Presbyterian minister. The “father” of statistics.

We may know, for example, that there are four times more patterns belonging to the class \(\omega ^{1}\) than patterns belonging to the class \(\omega ^{2}\) in nature. Then, \(P(\omega ^{1}) = 4/5\) and \(P(\omega ^{2}) = 1/5\).

The height of the bar for an interval [ a, b] should be \(h = p/w\), where p is the number of elements of the learning set which belong to the given class and are in the interval [ a, b], and w is the number of all elements of the learning set which belong to the given class.

John Ross Quinlan—an Australian computer scientist, a researcher at the University of Sydney and the RAND Corporation. His research concerns machine learning, decision theory, and data exploration.

Various metrics are introduced in Appendix G.2.

Hugo Steinhaus—a Polish mathematician, a professor of Jan Kazimierz University in Lwów (now Lviv, Ukraine) and Wrocław University, a Ph.D. student of David Hilbert, a co-founder of the Lwów School of Mathematics (together with, among others, Stefan Banach and Stanisław Ulam). His work concerns functional analysis (Banach-Steinhaus theorem), geometry, and mathematical logic.

James B. MacQueen—a psychologist, a professor of statistics at the University of California, Los Angeles. His work concerns statistics, cluster analysis, and Markov processes.

Stephen Curtis Johnson—a researcher at Bell Labs and AT&T, then the president of USENIX. A mathematician and a computer scientist. He has developed cpp—a C language compiler, YACC—a UNIX generator of parsers, int—a C code analyzer, and a MATLAB compiler.

In this case we begin with clusters containing single patterns and we can end up with one big cluster containing all patterns of a sample set.

In this case we begin with one big cluster containing all patterns of a sample set and we can end up with clusters containing single patterns.

Title

Pattern Recognition and Cluster Analysis

Book

Introduction to Artificial Intelligence

Print ISBN: 978-3-319-40020-4

Electronic ISBN: 978-3-319-40022-8

https://doi.org/10.1007/978-3-319-40022-8

DOI

https://doi.org/10.1007/978-3-319-40022-8_10

Author:

Mariusz Flasiński

Publisher

Springer International Publishing

Sequence number

Chapter number

Chapter 10