Partitional clustering via nonsmooth optimization

Preface
	Acknowledgments
Introduction
Contents
Acronyms and Symbols
	Symbols and Notations
	Abbreviations
Part I Preliminaries
	1 Introduction to Clustering
		1.1 Introduction
		1.2 Notations and Definitions
		1.3 Similarity Measures
		1.4 Types of Clustering Algorithms
		1.5 Applications of Clustering
	2 Theory of Nonsmooth Optimization
		2.1 Introduction
		2.2 Preliminaries
			2.2.1 Convex Sets
			2.2.2 Separating Hyperplanes
			2.2.3 Continuous, Lipschitz Continuous, and Convex Functions
		2.3 Concepts of Nonsmooth Analysis
			2.3.1 Subdifferentials of Convex Functions
			2.3.2 Nonconvex Analysis
			2.3.3 Subdifferential Calculus
			2.3.4 Quasidifferentials
		2.4 Optimality Conditions
		2.5 Discrete Gradient
		2.6 Piecewise Partially Separable Functions
			2.6.1 Piecewise Partially Separable and ChainedFunctions
			2.6.2 Properties of Piecewise Partially SeparableFunctions
			2.6.3 Calculation of Discrete Gradients
		2.7 DC Optimization
		2.8 Smoothing of Nonsmooth Functions
			2.8.1 Hyperbolic Smoothing of a Simple Maximum Function
			2.8.2 Reformulation of Minimax Problem
			2.8.3 Hyperbolic Smoothing of the Maximum Function
			2.8.4 Hyperbolic Smoothing of the Minimum Function
	3 Nonsmooth Optimization Methods
		3.1 Introduction
		3.2 Subgradient Method
		3.3 Proximal Bundle Method
		3.4 Limited Memory Bundle Method
			3.4.1 Convergence of the LMBM
		3.5 DC Diagonal Bundle Method
			3.5.1 Convergence of the DCD-Bundle
		3.6 Nonsmooth DC Method
			3.6.1 Convergence of the NDCM
		3.7 DC Algorithm
			3.7.1 Convergence of the DCA
		3.8 Discrete Gradient Method
			3.8.1 Convergence of the DGM
		3.9 Smoothing Method
			3.9.1 Convergence of the HSM
Part II Clustering Algorithms
	4 Optimization Models in Cluster Analysis
		4.1 Introduction
		4.2 Mixed Integer Programming Model
		4.3 Nonsmooth Optimization Model
		4.4 Nonsmooth DC Optimization Model
		4.5 Auxiliary Clustering Problem
			4.5.1 DC Representation of Auxiliary Cluster Function
		4.6 Optimality Conditions
			4.6.1 Optimality Conditions for Clustering Problem
			4.6.2 Optimality Conditions for Auxiliary Clustering Problem
		4.7 Smoothing of Cluster Functions
			4.7.1 Hyperbolic Smoothing of Functions d1 and d∞
			4.7.2 Hyperbolic Smoothing of the Cluster Function
			4.7.3 Smoothing of Auxiliary Cluster Function
			4.7.4 Partial Smoothing of DC Cluster Function
			4.7.5 Partial Smoothing of DC Auxiliary ClusterFunction
	5 Heuristic Clustering Algorithms
		5.1 Introduction
		5.2 k-Means Algorithm and Its Variants
			5.2.1 k-Means Algorithm
			5.2.2 Variants of k-Means Algorithm
			5.2.3 Global k-Means Algorithm
		5.3 k-Medians Algorithm and Its Variants
			5.3.1 k-Medians Algorithm
			5.3.2 Variants of k-Medians Algorithm
		5.4 k-Medoids Algorithm
		5.5 Fuzzy c-Means Algorithm
		5.6 Clustering Algorithms Based on Mixture Models
			5.6.1 Mixture Models
			5.6.2 Maximum Likelihood Estimation
			5.6.3 Expectation Maximization Clustering Algorithm
		5.7 Self-Organizing Map Algorithm
	6 Metaheuristic Clustering Algorithms
		6.1 Introduction
		6.2 Tabu Search Clustering Algorithm
		6.3 Simulated Annealing Clustering Algorithm
		6.4 Genetic Algorithm for Clustering
		6.5 Artificial Bee Colony Clustering Algorithm
		6.6 Particle Swarm Optimization Clustering Algorithm
		6.7 Ant Colony Optimization Clustering Algorithm
	7 Incremental Clustering Algorithms
		7.1 Introduction
		7.2 Finding a Center of One Cluster
		7.3 General Incremental Clustering Algorithm
		7.4 Computation of Set of Starting Cluster Centers
		7.5 Multi-Start Incremental Clustering Algorithm
		7.6 Incremental k-Medians Algorithm
	8 Nonsmooth Optimization Based Clustering Algorithms
		8.1 Introduction
		8.2 Modified Global k-Means Algorithm
		8.3 Fast Modified Global k-Means Algorithm
		8.4 Limited Memory Bundle Method for Clustering
		8.5 Discrete Gradient Clustering Algorithm
		8.6 Smooth Incremental Clustering Algorithm
	9 DC Optimization Based Clustering Algorithms
		9.1 Introduction
		9.2 Incremental Nonsmooth DC Clustering Algorithm
		9.3 DC Diagonal Bundle Clustering Algorithm
		9.4 Incremental DCA for Clustering
Part III Implementations and Evaluations of Clustering Algorithms
	10 Performance and Evaluation Measures
		10.1 Introduction
		10.2 Optimal Number of Clusters
		10.3 Cluster Validity Indices
			10.3.1 Optimal Value of Objective Function
			10.3.2 Davies–Bouldin Index
			10.3.3 Dunn Index
			10.3.4 Hartigan Index
			10.3.5 Krzanowski–Lai Index
			10.3.6 Ball & Hall Index
			10.3.7 Bayesian Information Criterion
			10.3.8 WB Index
			10.3.9 Xu Index
			10.3.10 Xie-Beni Index
			10.3.11 Sym Index
			10.3.12 I Index
			10.3.13 Calinski–Harabasz Index
		10.4 Silhouette Coefficients and Plots
		10.5 Rand Index
		10.6 Adjusted Rand Index
		10.7 Purity
		10.8 Normalized Mutual Information
		10.9 F-Score
		10.10 Performance Profiles in Cluster Analysis
			10.10.1 Accuracy
			10.10.2 Number of Distance Function Evaluations
			10.10.3 Computational Time
	11 Implementations and Data Sets
		11.1 Introduction
		11.2 Implementations of Clustering Algorithms
		11.3 Data Sets
			11.3.1 Extra Small Data Sets
			11.3.2 Small Data Sets
			11.3.3 Medium Sized Data Sets
			11.3.4 Large Data Sets
			11.3.5 Very Large Data Sets
		11.4 Parameters Selection in Finding Starting Cluster Centers
	12 Numerical Experiments
		12.1 Introduction
		12.2 Importance of Procedure for Finding Starting Cluster Centers
		12.3 Performance Results of Incremental Clustering Algorithms
			12.3.1 Results for Extra Small Data Sets
			12.3.2 Results for Small Data Sets
			12.3.3 Results for Medium Sized Data Sets
			12.3.4 Results for Large Data Sets
			12.3.5 Results for Very Large Data Sets
		12.4 Comparative Results with Different Similarity Measures
			12.4.1 Optimal Values for Cluster Functions
			12.4.2 Computational Time
			12.4.3 Visualization of Results
	13 Concluding Remarks
References
Index