Unsupervised Classification: Similarity Measures, Classical and Metaheuristic Approaches, and Applications

Description

Clustering is an important unsupervised classification technique where data points are grouped such that points that are similar in some sense belong to the same cluster. Cluster analysis is a complex problem as a variety of similarity and dissimilarity measures exist in the literature. This is the first book focused on clustering with a particular emphasis on symmetry-based measures of similarity and metaheuristic approaches. The aim is to find a suitable grouping of the input data set so that some criteria are optimized, and using this the authors frame the clustering problem as an optimization one where the objectives to be optimized may represent different characteristics such as compactness, symmetrical compactness, separation between clusters, or connectivity within a cluster. They explain the techniques in detail and outline many detailed applications in data mining, remote sensing and brain imaging, gene expression data analysis, and face detection. The book will be useful to graduate students and researchers in computer science, electrical engineering, system science, and information technology, both as a text and as a reference book. It will also be useful to researchers and practitioners in industry working on pattern recognition, data mining, soft computing, metaheuristics, bioinformatics, remote sensing, and brain imaging. Unsupervised Classification Preface Contents Chapter 1: Introduction 1.1 Introduction 1.2 Data Types with Examples 1.3 Pattern Recognition: Preliminaries 1.3.1 Data Acquisition 1.3.2 Feature Selection 1.3.3 Classification 1.3.4 Clustering 1.3.5 Distance Measures in Clustering 1.3.6 Model Selection 1.3.7 Model Order Selection 1.4 Robustness to Outliers and Missing Values 1.5 Fuzzy Set-Theoretic Approach: Relevance and Features 1.6 Applications of Pattern Recognition and Learning 1.7 Summary and Scope of the Book Chapter 2: Some Single- and Multiobjective Optimization Techniques 2.1 Introduction 2.2 Single-Objective Optimization Techniques 2.2.1 Overview of Genetic Algorithms 2.2.1.1 Genetic Algorithms: Basic Principles and Features Population Encoding/Decoding Mechanism Objective Function and Associated Fitness Evaluation Techniques Selection/Reproduction Procedure Crossover Mutation Probabilities to Perform Genetic Operations 2.2.2 Simulated Annealing 2.2.2.1 Basic Principle 2.2.2.2 Annealing Schedule 2.2.2.3 Algorithm 2.3 Multiobjective Optimization 2.3.1 Multiobjective Optimization Problems 2.3.1.1 Formal Definition of MOOPs 2.3.1.2 Dominance Relation and Pareto Optimality Properties of Dominance Relation [77] 2.3.1.3 Performance Measures 2.3.2 Various Methods to Solve MOOPs 2.3.3 Recent Multiobjective Evolutionary Algorithms 2.3.4 MOOPs and SA 2.4 An Archive-Based Multiobjective Simulated Annealing Technique: AMOSA 2.4.1 Introduction 2.4.2 Archived Multiobjective Simulated Annealing (AMOSA) 2.4.3 Archive Initialization 2.4.4 Clustering the Archive Solutions 2.4.5 Amount of Domination 2.4.6 The Main AMOSA Process 2.4.7 Complexity Analysis 2.5 Simulation Results 2.5.1 Comparison Measures 2.5.2 Comparison of Binary-Encoded AMOSA with NSGA-II and PAES 2.5.2.1 Discussion of the Results 2.5.3 Comparison of Real-Coded AMOSA with the Algorithm of Smith et al. and Real-Coded NSGA-II 2.5.4 Discussion on Annealing Schedule 2.6 Discussion and Conclusions Chapter 3: Similarity Measures 3.1 Introduction 3.2 Definitions 3.2.1 Need for Measuring Similarity 3.3 Similarity/Dissimilarity for Binary Variables 3.4 Distance for Nominal/Categorical Variable 3.4.1 Method 1: Each Category Is Represented by a Single Binary Variable [278] 3.4.2 Method 2: Each Category Is Represented by Several Binary Variables [278] 3.5 Distance for Ordinal Variables 3.5.1 Normalized Rank Transformation 3.5.2 Spearman Distance 3.5.3 Footrule Distance 3.6 Distance for Quantitative Variables 3.6.1 Euclidean Distance 3.6.2 Minkowski Distance of Order lambda 3.6.3 City Block Distance 3.6.4 Chebyshev Distance 3.6.5 Canberra Distance 3.6.6 Bray-Curtis Distance 3.6.7 Angular Separation 3.6.8 Correlation Coefficient 3.6.9 Mahalanobis Distance 3.7 Normalization Methods 3.8 Summary Chapter 4: Clustering Algorithms 4.1 Introduction 4.2 Preliminaries 4.2.1 Definition of Clustering 4.2.2 Some Clustering Techniques 4.3 Partitional Clustering Techniques 4.3.1 K-Means Clustering Technique 4.3.2 K-Medoid Clustering Technique 4.3.3 Fuzzy C-Means Clustering Algorithm 4.4 Distribution-Based Clustering Approach 4.5 Hierarchical Clustering Techniques Linkage Clustering Algorithms 4.6 Density-Based Clustering Techniques 4.7 Grid-Based Clustering Techniques 4.8 Some Recent Clustering Techniques 4.9 Some Evolutionary Approaches to Clustering 4.9.1 Algorithms for a Fixed Value of the Number of Clusters 4.9.2 Algorithms with Variable Number of Clusters 4.10 MOO and Clustering 4.11 Summary Chapter 5: Point Symmetry-Based Distance Measures and Their Applications to Clustering 5.1 Introduction 5.2 Some Existing Symmetry-Based Distance Measures 5.3 A New Definition of the Point Symmetry Distance [27] 5.4 Some Properties of dps(x, c) 5.5 Kd-Tree-Based Nearest Neighbor Computation 5.6 GAPS: The Genetic Clustering Scheme with New PS-Distance [27] 5.6.1 Chromosome Representation and Population Initialization 5.6.2 Fitness Computation 5.6.3 Selection 5.6.4 Crossover 5.6.5 Mutation 5.6.6 Termination 5.6.7 Complexity Analysis 5.7 On the Convergence Property of GAPS 5.7.1 Preliminaries To Check Whether the Mutation Matrix is Positive Conditions on Selection 5.7.2 Convergence Proof 5.8 Experimental Results of GAPS 5.8.1 Data Sets Used 5.8.2 Implementation Results 5.8.3 Summary Chapter 6: A Validity Index Based on Symmetry: Application to Satellite Image Segmentation 6.1 Introduction 6.2 Some Existing Cluster Validity Indices 6.2.1 BIC Index 6.2.2 Calinski-Harabasz Index 6.2.3 Silhouette Index 6.2.4 DB Index 6.2.5 Dunn's Index 6.2.6 Xie-Beni Index 6.2.7 PS Index 6.2.8 I-Index 6.2.9 CS-Index 6.3 Sym-Index: The Symmetry-Based Cluster Validity Index 6.3.1 The Cluster Validity Measure 6.3.1.1 Motivation 6.3.1.2 Formulation of Sym-Index 6.3.1.3 Explanation 6.3.2 Mathematical Justification Uniqueness and Global Optimality of the K-Partition 6.3.3 Interaction Between the Different Components of Sym-Index 6.4 Experimental Results 6.4.1 Data Sets 6.4.2 Comparative Results 6.4.3 Analysis of Results 6.5 Incorporating dps in Some Existing Cluster Validity Indices 6.6 Point Symmetry-Based Cluster Validity Indices 6.6.1 Symmetry-Based Davies-Bouldin Index (Sym-DB Index) 6.6.2 Symmetry-Based Dunn's Index (Sym-Dunn Index) 6.6.3 Symmetry-Based Generalized Dunn's Index (Sym-GDunn Index) 6.6.4 New Symmetry Distance-Based PS-Index (Sym-PS Index) 6.6.5 Symmetry-Based Xie-Beni Index (Sym-XB Index) 6.6.6 Symmetry-Based FS-Index (Sym-FS Index) 6.6.7 Symmetry-Based K-Index (Sym-K Index) 6.6.8 Symmetry-Based SV-Index (Sym-SV Index) 6.7 Experimental Results 6.7.1 Discussion of Results 6.8 Application to Remote Sensing Imagery 6.8.1 Simulated Circle Image (SCI) 6.8.2 SPOT Image of Kolkata 6.9 Discussion and Conclusions Chapter 7: Symmetry-Based Automatic Clustering 7.1 Introduction 7.2 Some Existing Genetic Algorithm-Based Automatic Clustering Techniques 7.3 Description of VGAPS 7.3.1 Chromosome Representation and Population Initialization 7.3.2 Fitness Computation 7.3.3 Genetic Operations and Terminating Criterion 7.3.3.1 Selection 7.3.3.2 Crossover 7.3.3.3 Mutation 7.3.3.4 Termination Criterion 7.4 On the Convergence Property of VGAPS 7.4.1 To Check Whether the Mutation Matrix Is Positive 7.4.2 Conditions on Selection 7.5 Data Sets Used and Implementation Results 7.5.1 Data Sets Used 7.5.2 Results and Discussions 7.5.2.1 Exploring Sym-Index as a Fitness Function 7.5.2.2 Exploring the VGAPS-Clustering 7.6 Extending VGAPS to Fuzzy Clustering 7.6.1 Fuzzy Symmetry-Based Cluster Validity Index Framework of the Formulation 7.6.2 Fuzzy-VGAPS Clustering 7.6.2.1 Chromosome Representation and Population Initialization 7.6.2.2 Fitness Computation Computing the Membership Values Updating the Centers Fitness Calculation 7.6.2.3 Selection, Crossover, and Mutation 7.6.2.4 Termination 7.7 Implementation Results and Comparative Study 7.7.1 Discussion of Results Summary of Results 7.7.2 Application to MR Brain Image Segmentation 7.7.3 Experimental Results 7.8 Summary Chapter 8: Some Line Symmetry Distance-Based Clustering Techniques 8.1 Introduction 8.2 The Line Symmetry-Based Distance 8.2.1 Definition 8.3 GALSD: The Genetic Clustering Scheme with Line Symmetry-Based Distance 8.3.1 String Representation and Population Initialization 8.3.2 Fitness Computation 8.3.3 Genetic Operators 8.4 Experimental Results 8.4.1 Data Sets Used 8.4.2 Discussion of Results 8.4.3 Computation Time 8.5 Application to Face Recognition 8.5.1 Human Face Detection Algorithm 8.5.2 Experimental Results 8.6 A Generalized Line Symmetry-Based Distance and Its Application to Data Clustering A Generalized Line Symmetry-Based Distance 8.7 Implementation Results 8.7.1 Data Sets Used 8.7.2 Discussion of Results Summary of Results 8.8 Discussion and Conclusions Chapter 9: Use of Multiobjective Optimization for Data Clustering 9.1 Introduction 9.2 MOPS: Multiobjective Clustering Using Point Symmetry Distance 9.2.1 Selection of a Solution from the Archive 9.2.2 Experimental Results 9.3 VAMOSA: Symmetry-Based Multiobjective Clustering Technique for Automatic Evolution of Clusters 9.3.1 Data Sets Used for Experiment 9.3.2 Experimental Results Summary of Results 9.4 A Generalized Automatic Clustering Algorithm in a Multiobjective Framework 9.4.1 GenClustMOO: Multiobjective Clustering Technique 9.4.1.1 String Representation and Population Initialization 9.4.1.2 Assignment of Points 9.4.1.3 Objective Functions Used 9.4.1.4 Connectivity-Based Cluster Validity Index: Con-index 9.4.1.5 Relative Neighborhood Graph [282] 9.4.1.6 Measuring the Connectivity Among a Set of Points 9.4.1.7 Definition of the Connectivity-Based Cluster Validity Index 9.4.2 Subcluster Merging for Objective Function Calculation 9.5 Experimental Results 9.5.1 Data Sets Used 9.5.2 Discussion of Results Summary of Results 9.6 Discussion and Conclusions References Index