Partitional clustering via nonsmooth optimization

✍ Scribed by Bagirov A.M., Karmitsa N., Taheri S

• Publisher: Springer
• Year: 2020
• Tongue: English
• Leaves: 343
• Category: Library

✦ Table of Contents

Preface......Page 7
Acknowledgments......Page 8
Introduction......Page 9
Contents......Page 11
Symbols and Notations......Page 16
Abbreviations......Page 18
Part I Preliminaries......Page 20
1.1 Introduction......Page 21
1.2 Notations and Definitions......Page 23
1.3 Similarity Measures......Page 24
1.4 Types of Clustering Algorithms......Page 27
1.5 Applications of Clustering......Page 29
2.1 Introduction......Page 32
2.2.1 Convex Sets......Page 33
2.2.2 Separating Hyperplanes......Page 35
2.2.3 Continuous, Lipschitz Continuous, and Convex Functions......Page 36
2.3.1 Subdifferentials of Convex Functions......Page 39
2.3.2 Nonconvex Analysis......Page 41
2.3.3 Subdifferential Calculus......Page 45
2.3.4 Quasidifferentials......Page 48
2.4 Optimality Conditions......Page 50
2.5 Discrete Gradient......Page 52
2.6.1 Piecewise Partially Separable and ChainedFunctions......Page 54
2.6.2 Properties of Piecewise Partially SeparableFunctions......Page 56
2.6.3 Calculation of Discrete Gradients......Page 57
2.7 DC Optimization......Page 58
2.8 Smoothing of Nonsmooth Functions......Page 62
2.8.2 Reformulation of Minimax Problem......Page 63
2.8.3 Hyperbolic Smoothing of the Maximum Function......Page 65
2.8.4 Hyperbolic Smoothing of the Minimum Function......Page 66
3.1 Introduction......Page 68
3.2 Subgradient Method......Page 70
3.3 Proximal Bundle Method......Page 72
3.4 Limited Memory Bundle Method......Page 76
3.4.1 Convergence of the LMBM......Page 81
3.5 DC Diagonal Bundle Method......Page 84
3.5.1 Convergence of the DCD-Bundle......Page 90
3.6 Nonsmooth DC Method......Page 94
3.6.1 Convergence of the NDCM......Page 97
3.7 DC Algorithm......Page 100
3.7.1 Convergence of the DCA......Page 102
3.8 Discrete Gradient Method......Page 103
3.8.1 Convergence of the DGM......Page 106
3.9 Smoothing Method......Page 109
3.9.1 Convergence of the HSM......Page 110
Part II Clustering Algorithms......Page 112
4.1 Introduction......Page 113
4.2 Mixed Integer Programming Model......Page 114
4.3 Nonsmooth Optimization Model......Page 115
4.4 Nonsmooth DC Optimization Model......Page 121
4.5 Auxiliary Clustering Problem......Page 125
4.5.1 DC Representation of Auxiliary Cluster Function......Page 129
4.6.1 Optimality Conditions for Clustering Problem......Page 132
4.6.2 Optimality Conditions for Auxiliary Clustering Problem......Page 137
4.7.1 Hyperbolic Smoothing of Functions d1 and d∞......Page 141
4.7.2 Hyperbolic Smoothing of the Cluster Function......Page 143
4.7.3 Smoothing of Auxiliary Cluster Function......Page 145
4.7.4 Partial Smoothing of DC Cluster Function......Page 147
4.7.5 Partial Smoothing of DC Auxiliary ClusterFunction......Page 148
5.1 Introduction......Page 150
5.2 k-Means Algorithm and Its Variants......Page 151
5.2.1 k-Means Algorithm......Page 152
5.2.2 Variants of k-Means Algorithm......Page 155
5.2.3 Global k-Means Algorithm......Page 158
5.3.1 k-Medians Algorithm......Page 161
5.3.2 Variants of k-Medians Algorithm......Page 164
5.4 k-Medoids Algorithm......Page 166
5.5 Fuzzy c-Means Algorithm......Page 169
5.6.1 Mixture Models......Page 171
5.6.3 Expectation Maximization Clustering Algorithm......Page 173
5.7 Self-Organizing Map Algorithm......Page 175
6.1 Introduction......Page 179
6.2 Tabu Search Clustering Algorithm......Page 180
6.3 Simulated Annealing Clustering Algorithm......Page 183
6.4 Genetic Algorithm for Clustering......Page 186
6.5 Artificial Bee Colony Clustering Algorithm......Page 188
6.6 Particle Swarm Optimization Clustering Algorithm......Page 191
6.7 Ant Colony Optimization Clustering Algorithm......Page 194
7.1 Introduction......Page 198
7.2 Finding a Center of One Cluster......Page 199
7.3 General Incremental Clustering Algorithm......Page 200
7.4 Computation of Set of Starting Cluster Centers......Page 202
7.5 Multi-Start Incremental Clustering Algorithm......Page 207
7.6 Incremental k-Medians Algorithm......Page 208
8.1 Introduction......Page 214
8.2 Modified Global k-Means Algorithm......Page 215
8.3 Fast Modified Global k-Means Algorithm......Page 219
8.4 Limited Memory Bundle Method for Clustering......Page 224
8.5 Discrete Gradient Clustering Algorithm......Page 228
8.6 Smooth Incremental Clustering Algorithm......Page 233
9.1 Introduction......Page 237
9.2 Incremental Nonsmooth DC Clustering Algorithm......Page 238
9.3 DC Diagonal Bundle Clustering Algorithm......Page 244
9.4 Incremental DCA for Clustering......Page 249
Part III Implementations and Evaluations of Clustering Algorithms......Page 254
10.1 Introduction......Page 255
10.2 Optimal Number of Clusters......Page 256
10.3 Cluster Validity Indices......Page 257
10.3.1 Optimal Value of Objective Function......Page 258
10.3.2 Davies–Bouldin Index......Page 259
10.3.3 Dunn Index......Page 260
10.3.5 Krzanowski–Lai Index......Page 261
10.3.7 Bayesian Information Criterion......Page 262
10.3.10 Xie-Beni Index......Page 263
10.3.11 Sym Index......Page 264
10.3.12 I Index......Page 265
10.3.13 Calinski–Harabasz Index......Page 266
10.4 Silhouette Coefficients and Plots......Page 267
10.5 Rand Index......Page 269
10.6 Adjusted Rand Index......Page 271
10.7 Purity......Page 272
10.8 Normalized Mutual Information......Page 273
10.9 F-Score......Page 274
10.10.1 Accuracy......Page 275
10.10.2 Number of Distance Function Evaluations......Page 276
10.10.3 Computational Time......Page 277
11.2 Implementations of Clustering Algorithms......Page 279
11.3.1 Extra Small Data Sets......Page 282
11.3.3 Medium Sized Data Sets......Page 283
11.3.5 Very Large Data Sets......Page 284
11.4 Parameters Selection in Finding Starting Cluster Centers......Page 285
12.2 Importance of Procedure for Finding Starting Cluster Centers......Page 290
12.3.1 Results for Extra Small Data Sets......Page 293
12.3.2 Results for Small Data Sets......Page 297
12.3.3 Results for Medium Sized Data Sets......Page 301
12.3.4 Results for Large Data Sets......Page 306
12.3.5 Results for Very Large Data Sets......Page 316
12.4.1 Optimal Values for Cluster Functions......Page 319
12.4.2 Computational Time......Page 320
12.4.3 Visualization of Results......Page 322
13 Concluding Remarks......Page 324
References......Page 327
Index......Page 340