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

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