Cover Page

WILEY SERIES ON METHODS AND APPLICATIONS IN DATA MINING

Series Editor: Daniel T. Larose

Discovering Knowledge in Data: An Introduction to Data Mining, Second Edition • Daniel T. Larose and Chantal D. Larose

Data Mining for Genomics and Proteomics: Analysis of Gene and Protein Expression Data • Darius M. Dziuda

Knowledge Discovery with Support Vector Machines • Lutz Hamel

Data‐Mining on the Web: Uncovering Patterns in Web Content, Structure, and Usage • Zdravko Markov and Daniel T. Larose

Data Mining Methods and Models • Daniel T. Larose

Practical Text Mining with Perl • Roger Bilisoly

Data Mining and Predictive Analytics • Daniel T. Larose and Chantal D. Larose

Pattern Recognition: A Quality of Data Perspective • Władysław Homenda and Witold Pedrycz

PATTERN RECOGNITION

A Quality of Data Perspective

 

 

WŁADYSŁAW HOMENDA

The Faculty of Mathematics and Information Science, Warsaw University of Technology Warsaw, Poland

and

The Faculty of Economics and Informatics in Vilnius, University of BiaŁystok Vilnius, Lithuania

WITOLD PEDRYCZ

The Systems Research Institute, Polish Academy of Sciences Warsaw, Poland

and

The Department of Electrical and Computer Engineering, University of Alberta Edmonton, Alberta, Canada

 

 

 

 

 

 

 

Wiley Logo

PREFACE

Pattern recognition has established itself as an advanced area with a well‐defined methodology, a plethora of algorithms, and well‐defined application areas. For decades, pattern recognition has been a subject of intense theoretical and applied research inspired by practical needs. Prudently formulated evaluation strategies and methods of pattern recognition, especially a suite of classification algorithms, constitute the crux of numerous pattern classifiers. There are numerous representative realms of applications including recognizing printed text and manuscripts, identifying musical notation, supporting multimodal biometric systems (voice, iris, signature), classifying medical signals (including ECG, EEG, EMG, etc.), and classifying and interpreting images.

With the abundance of data, their volume, and existing diversity arise evident challenges that need to be carefully addressed to foster further advancements of the area and meet the needs of the ever‐growing applications. In a nutshell, they are concerned with the data quality. This term manifests in numerous ways and has to be perceived in a very general sense. Missing data, data affected by noise, foreign patterns, limited precision, information granularity, and imbalanced data are commonly encountered phenomena one has to take into consideration in building pattern classifiers and carrying out comprehensive data analysis. In particular, one has to engage suitable ways of transforming (preprocessing) data (patterns) prior to their analysis, classification, and interpretation.

The quality of data impacts the very essence of pattern recognition and calls for thorough investigations of the principles of the area. Data quality exhibits a direct impact on architectures and the development schemes of the classifiers. This book aims to cover the essentials of pattern recognition by casting it in a new perspective of data quality—in essence we advocate that a new framework of pattern recognition along with its methodology and algorithms has to be established to cope with the challenges of data quality. As a representative example, it is of interest to look at the problem of the so‐called foreign (odd) patterns. By foreign patterns we mean patterns not belonging to a family of classes under consideration. The ever‐growing presence of pattern recognition technologies increases the importance of identifying foreign patterns. For example, in recognition of printed texts, odd patterns (say, blots, grease, or damaged symbols) appear quite rarely. On the other hand, in recognition problem completed for some other sources such as geodetic maps or musical notation, foreign patterns occur quite often and their presence cannot be ignored. Unlike printed text, such documents contain objects of irregular positioning, differing in size, overlapping, or having complex shape. Thus, too strict segmentation results in the rejection of many recognizable symbols. Due to the weak separability of recognized patterns, segmentation criteria need to be relaxed and foreign patterns similar to recognized symbols have to be carefully inspected and rejected.

The exposure of the overall material is structured into two parts, Part I: Fundamentals and Part II: Advanced Topics: A Framework of Granular Computing. This arrangement reflects the general nature of the main topics being covered.

Part I addresses the principles of pattern recognition with rejection. The task of a rejection of foreign pattern arises as an extension and an enhancement of the standard schemes and practices of pattern recognition. Essential notions of pattern recognition are elaborated on and carefully revisited in order to clarify on how to augment existing classifiers with a new rejection option required to cope with the discussed category of problems. As stressed, this book is self‐contained, and this implies that a number well‐known methods and algorithms are discussed to offer a complete overview of the area to identify main objectives and to present main phases of pattern recognition. The key topics here involve problem formulation and understanding; feature space formation, selection, transformation, and reduction; pattern classification; and performance evaluation. Analyzed is the evolution of research on pattern recognition with rejection, including historical perspective. Identified are current approaches along with present and forthcoming issues that need to be tackled to ensure further progress in this domain. In particular, new trends are identified and linked with existing challenges. The chapters forming this part revisit the well‐known material, as well as elaborate on new approaches to pattern recognition with rejection. Chapter 1 covers fundamental notions of feature space formation. Feature space is of a paramount relevance implying quality of classifiers. The focus of the chapter is on the analysis and comparative assessment of the main categories of methods used in feature construction, transformation, and reduction. In Chapter 2, we cover a variety of design approaches to the design of fundamental classifiers, including such well‐known constructs as k‐NN (nearest neighbor), naïve Bayesian classifier, decision trees, random forests, and support vector machines (SVMs). Comparative studies are supported by a suite of illustrative examples. Chapter 3 offers a detailed formulation of the problem of recognition with rejection. It delivers a number of motivating examples and elaborates on the existing studies carried out in this domain. Chapter 4 covers a suite of evaluation methods required to realize tasks of pattern recognition with a rejection option. Along with classic performance evaluation approaches, a thorough discussion is presented on a multifaceted nature of pattern recognition evaluation mechanisms. The analysis is extended by dealing with balanced and imbalanced datasets. The discussion commences with an evaluation of a standard pattern recognition problem and then progresses toward pattern recognition with rejection. We tackle an issue of how to evaluate pattern recognition with rejection when the problem is further exacerbated by the presence of imbalanced data. A wide spectrum of measures is discussed and employed in experiments, including those of comparative nature. In Chapter 5, we present an empirical evaluation of different rejecting architectures. An empirical verification is performed using datasets of handwritten digits and symbols of printed music notation. In addition, we propose a rejecting method based on a concept of geometrical regions. This method, unlike rejecting architectures, is a stand‐alone approach to support discrimination between native and foreign patterns. We study the usage of elementary geometrical regions, especially hyperrectangles and hyperellipsoids.

Part II focuses on the fundamental concept of information granules and information granularity. Information granules give rise to the area of granular computing—a paradigm of forming, processing, and interpreting information granules. Information granularity comes hand in hand with the key notion of data quality—it helps identify, quantify, and process patterns of a certain quality. The chapters are structured in a way to offer a top‐down way of material exposure. Chapter 6 brings the fundamentals of information granules delivering the key motivating factors, elaborating on the underlying formalisms (including sets, fuzzy sets, probabilities) along with the operations and transformation mechanisms as well as the characterization of information granules. The design of information granules is covered in Chapter 7. Chapter 8 positions clustering in a new setting, revealing its role as a mechanism of building information granules. In the same vein, it is shown that the clustering results (predominantly of a numeric nature) are significantly augmented by bringing information granularity to the description of the originally constructed numeric clusters. A question of clustering information granules is posed and translated into some algorithmic augmentations of the existing clustering methods. Further studies on data quality and its quantification and processing are contained in Chapter 9. Here we focus on data (value) imputation and imbalanced data—the two dominant manifestations in which the quality of data plays a pivotal role. In both situations, the problem is captured through information granules that lead to the quantification of the quality of data as well as enrich the ensuing classification schemes.

This book exhibits a number of essential and appealing features:

Systematic exposure of the concepts, design methodology, and detailed algorithms. In the organization of the material, we adhere to the top‐down strategy starting with the concepts and motivation and then proceeding with the detailed design materializing in specific algorithms and a slew of representative applications.

A wealth of carefully structured and organized illustrative material. This book includes a series of brief illustrative numeric experiments, detailed schemes, and more advanced problems.

Self‐containment. We aimed at the delivery of self‐contained material providing with all necessary prerequisites. If required, some parts of the text are augmented with a step‐by‐step explanation of more advanced concepts supported by carefully selected illustrative material.

Given the central theme of this book, we hope that this volume would appeal to a broad audience of researchers and practitioners in the area of pattern recognition and data analytics. It can serve as a compendium of actual methods in the area and offer a sound algorithmic framework.

This book could not have been possible without support provided by organizations and individuals.

We fully acknowledge the support provided by the National Science Centre, grant No 2012/07/B/ST6/01501, decision no. UMO‐2012/07/B/ST6/01501.

Dr Agnieszka Jastrzebska has done a meticulous job by helping in the realization of experiments and producing graphic materials. We are grateful to the team of professionals at John Wiley, Kshitija Iyer, and Grace Paulin Jeeva S for their encouragement from the outset of the project and their continuous support through its realization.

Władysław Homenda and Witold Pedrycz

PART I
FUNDAMENTALS