Preface xix
Notation xxiii
1 Introduction to Statistical Pattern Recognition 1
1.1 Statistical Pattern Recognition 1
1.1.1 Introduction 1
1.1.2 The Basic Model 2
1.2 Stages in a Pattern Recognition Problem 4
1.3 Issues 6
1.4 Approaches to Statistical Pattern Recognition 7
1.5 Elementary Decision Theory 8
1.5.1 Bayes? Decision Rule for Minimum Error 8
1.5.2 Bayes? Decision Rule for Minimum Error ?
Reject Option 12
1.5.3 Bayes? Decision Rule for Minimum Risk 13
1.5.4 Bayes? Decision Rule for Minimum Risk ? Reject
Option 15
1.5.5 Neyman?Pearson Decision Rule 15
1.5.6 Minimax Criterion 18
1.5.7 Discussion 19
1.6 Discriminant Functions 20
1.6.1 Introduction 20
1.6.2 Linear Discriminant Functions 21
1.6.3 Piecewise Linear Discriminant Functions 23
1.6.4 Generalised Linear Discriminant Function 24
1.6.5 Summary 26
1.7 Multiple Regression 27
1.8 Outline of Book 29
1.9 Notes and References 29
Exercises 31
2 Density Estimation ? Parametric 33
2.1 Introduction 33
2.2 Estimating the Parameters of the Distributions 34
2.2.1 Estimative Approach 34
2.2.2 Predictive Approach 35
2.3 The Gaussian Classifier 35
2.3.1 Specification 35
2.3.2 Derivation of the Gaussian Classifier Plug-In Estimates
37
2.3.3 Example Application Study 39
2.4 Dealing with Singularities in the Gaussian Classifier 40
2.4.1 Introduction 40
2.4.2 Na¨ive Bayes 40
2.4.3 Projection onto a Subspace 41
2.4.4 Linear Discriminant Function 41
2.4.5 Regularised Discriminant Analysis 42
2.4.6 Example Application Study 44
2.4.7 Further Developments 45
2.4.8 Summary 46
2.5 Finite Mixture Models 46
2.5.1 Introduction 46
2.5.2 Mixture Models for Discrimination 48
2.5.3 Parameter Estimation for Normal Mixture Models 49
2.5.4 Normal Mixture Model Covariance Matrix Constraints 51
2.5.5 How Many Components? 52
2.5.6 Maximum Likelihood Estimation via EM 55
2.5.7 Example Application Study 60
2.5.8 Further Developments 62
2.5.9 Summary 63
2.6 Application Studies 63
2.7 Summary and Discussion 66
2.8 Recommendations 66
2.9 Notes and References 67
Exercises 67
3 Density Estimation ? Bayesian 70
3.1 Introduction 70
3.1.1 Basics 72
3.1.2 Recursive Calculation 72
3.1.3 Proportionality 73
3.2 Analytic Solutions 73
3.2.1 Conjugate Priors 73
3.2.2 Estimating the Mean of a Normal Distribution with Known
Variance 75
3.2.3 Estimating the Mean and the Covariance Matrix of a
Multivariate Normal Distribution 79
3.2.4 Unknown Prior Class Probabilities 85
3.2.5 Summary 87
3.3 Bayesian Sampling Schemes 87
3.3.1 Introduction 87
3.3.2 Summarisation 87
3.3.3 Sampling Version of the Bayesian Classifier 89
3.3.4 Rejection Sampling 89
3.3.5 Ratio of Uniforms 90
3.3.6 Importance Sampling 92
3.4 Markov Chain Monte Carlo Methods 95
3.4.1 Introduction 95
3.4.2 The Gibbs Sampler 95
3.4.3 Metropolis?Hastings Algorithm 103
3.4.4 Data Augmentation 107
3.4.5 Reversible Jump Markov Chain Monte Carlo 108
3.4.6 Slice Sampling 109
3.4.7 MCMC Example ? Estimation of Noisy Sinusoids 111
3.4.8 Summary 115
3.4.9 Notes and References 116
3.5 Bayesian Approaches to Discrimination 116
3.5.1 Labelled Training Data 116
3.5.2 Unlabelled Training Data 117
3.6 Sequential Monte Carlo Samplers 119
3.6.1 Introduction 119
3.6.2 Basic Methodology 121
3.6.3 Summary 125
3.7 Variational Bayes 126
3.7.1 Introduction 126
3.7.2 Description 126
3.7.3 Factorised Variational Approximation 129
3.7.4 Simple Example 131
3.7.5 Use of the Procedure for Model Selection 135
3.7.6 Further Developments and Applications 136
3.7.7 Summary 137
3.8 Approximate Bayesian Computation 137
3.8.1 Introduction 137
3.8.2 ABC Rejection Sampling 138
3.8.3 ABC MCMC Sampling 140
3.8.4 ABC Population Monte Carlo Sampling 141
3.8.5 Model Selection 142
3.8.6 Summary 143
3.9 Example Application Study 144
3.10 Application Studies 145
3.11 Summary and Discussion 146
3.12 Recommendations 147
3.13 Notes and References 147
Exercises 148
4 Density Estimation ? Nonparametric 150
4.1 Introduction 150
4.1.1 Basic Properties of Density Estimators 150
4.2 k-Nearest-Neighbour Method 152
4.2.1 k-Nearest-Neighbour Classifier 152
4.2.2 Derivation 154
4.2.3 Choice of Distance Metric 157
4.2.4 Properties of the Nearest-Neighbour Rule 159
4.2.5 Linear Approximating and Eliminating Search Algorithm
159
4.2.6 Branch and Bound Search Algorithms: kd-Trees 163
4.2.7 Branch and Bound Search Algorithms: Ball-Trees 170
4.2.8 Editing Techniques 174
4.2.9 Example Application Study 177
4.2.10 Further Developments 178
4.2.11 Summary 179
4.3 Histogram Method 180
4.3.1 Data Adaptive Histograms 181
4.3.2 Independence Assumption (Naïve Bayes) 181
4.3.3 Lancaster Models 182
4.3.4 Maximum Weight Dependence Trees 183
4.3.5 Bayesian Networks 186
4.3.6 Example Application Study ? Naïve Bayes Text
Classification 190
4.3.7 Summary 193
4.4 Kernel Methods 194
4.4.1 Biasedness 197
4.4.2 Multivariate Extension 198
4.4.3 Choice of Smoothing Parameter 199
4.4.4 Choice of Kernel 201
4.4.5 Example Application Study 202
4.4.6 Further Developments 203
4.4.7 Summary 203
4.5 Expansion by Basis Functions 204
4.6 Copulas 207
4.6.1 Introduction 207
4.6.2 Mathematical Basis 207
4.6.3 Copula Functions 208
4.6.4 Estimating Copula Probability Density Functions 209
4.6.5 Simple Example 211
4.6.6 Summary 212
4.7 Application Studies 213
4.7.1 Comparative Studies 216
4.8 Summary and Discussion 216
4.9 Recommendations 217
4.10 Notes and References 217
Exercises 218
5 Linear Discriminant Analysis 221
5.1 Introduction 221
5.2 Two-Class Algorithms 222
5.2.1 General Ideas 222
5.2.2 Perceptron Criterion 223
5.2.3 Fisher?s Criterion 227
5.2.4 Least Mean-Squared-Error Procedures 228
5.2.5 Further Developments 235
5.2.6 Summary 235
5.3 Multiclass Algorithms 236
5.3.1 General Ideas 236
5.3.2 Error-Correction Procedure 237
5.3.3 Fisher?s Criterion ? Linear Discriminant
Analysis 238
5.3.4 Least Mean-Squared-Error Procedures 241
5.3.5 Regularisation 246
5.3.6 Example Application Study 246
5.3.7 Further Developments 247
5.3.8 Summary 248
5.4 Support Vector Machines 249
5.4.1 Introduction 249
5.4.2 Linearly Separable Two-Class Data 249
5.4.3 Linearly Nonseparable Two-Class Data 253
5.4.4 Multiclass SVMs 256
5.4.5 SVMs for Regression 257
5.4.6 Implementation 259
5.4.7 Example Application Study 262
5.4.8 Summary 263
5.5 Logistic Discrimination 263
5.5.1 Two-Class Case 263
5.5.2 Maximum Likelihood Estimation 264
5.5.3 Multiclass Logistic Discrimination 266
5.5.4 Example Application Study 267
5.5.5 Further Developments 267
5.5.6 Summary 268
5.6 Application Studies 268
5.7 Summary and Discussion 268
5.8 Recommendations 269
5.9 Notes and References 270
Exercises 270
6 Nonlinear Discriminant Analysis ? Kernel and
Projection Methods 274
6.1 Introduction 274
6.2 Radial Basis Functions 276
6.2.1 Introduction 276
6.2.2 Specifying the Model 278
6.2.3 Specifying the Functional Form 278
6.2.4 The Positions of the Centres 279
6.2.5 Smoothing Parameters 281
6.2.6 Calculation of the Weights 282
6.2.7 Model Order Selection 284
6.2.8 Simple RBF 285
6.2.9 Motivation 286
6.2.10 RBF Properties 288
6.2.11 Example Application Study 288
6.2.12 Further Developments 289
6.2.13 Summary 290
6.3 Nonlinear Support Vector Machines 291
6.3.1 Introduction 291
6.3.2 Binary Classification 291
6.3.3 Types of Kernel 292
6.3.4 Model Selection 293
6.3.5 Multiclass SVMs 294
6.3.6 Probability Estimates 294
6.3.7 Nonlinear Regression 296
6.3.8 Example Application Study 296
6.3.9 Further Developments 297
6.3.10 Summary 298
6.4 The Multilayer Perceptron 298
6.4.1 Introduction 298
6.4.2 Specifying the MLP Structure 299
6.4.3 Determining the MLP Weights 300
6.4.4 Modelling Capacity of the MLP 307
6.4.5 Logistic Classification 307
6.4.6 Example Application Study 310
6.4.7 Bayesian MLP Networks 311
6.4.8 Projection Pursuit 313
6.4.9 Summary 313
6.5 Application Studies 314
6.6 Summary and Discussion 316
6.7 Recommendations 317
6.8 Notes and References 318
Exercises 318
7 Rule and Decision Tree Induction 322
7.1 Introduction 322
7.2 Decision Trees 323
7.2.1 Introduction 323
7.2.2 Decision Tree Construction 326
7.2.3 Selection of the Splitting Rule 327
7.2.4 Terminating the Splitting Procedure 330
7.2.5 Assigning Class Labels to Terminal Nodes 332
7.2.6 Decision Tree Pruning ? Worked Example 332
7.2.7 Decision Tree Construction Methods 337
7.2.8 Other Issues 339
7.2.9 Example Application Study 340
7.2.10 Further Developments 341
7.2.11 Summary 342
7.3 Rule Induction 342
7.3.1 Introduction 342
7.3.2 Generating Rules from a Decision Tree 345
7.3.3 Rule Induction Using a Sequential Covering Algorithm
345
7.3.4 Example Application Study 350
7.3.5 Further Developments 351
7.3.6 Summary 351
7.4 Multivariate Adaptive Regression Splines 351
7.4.1 Introduction 351
7.4.2 Recursive Partitioning Model 351
7.4.3 Example Application Study 355
7.4.4 Further Developments 355
7.4.5 Summary 356
7.5 Application Studies 356
7.6 Summary and Discussion 358
7.7 Recommendations 358
7.8 Notes and References 359
Exercises 359
8 Ensemble Methods 361
8.1 Introduction 361
8.2 Characterising a Classifier Combination Scheme 362
8.2.1 Feature Space 363
8.2.2 Level 366
8.2.3 Degree of Training 368
8.2.4 Form of Component Classifiers 368
8.2.5 Structure 369
8.2.6 Optimisation 369
8.3 Data Fusion 370
8.3.1 Architectures 370
8.3.2 Bayesian Approaches 371
8.3.3 Neyman?Pearson Formulation 373
8.3.4 Trainable Rules 374
8.3.5 Fixed Rules 375
8.4 Classifier Combination Methods 376
8.4.1 Product Rule 376
8.4.2 Sum Rule 377
8.4.3 Min, Max and Median Combiners 378
8.4.4 Majority Vote 379
8.4.5 Borda Count 379
8.4.6 Combiners Trained on Class Predictions 380
8.4.7 Stacked Generalisation 382
8.4.8 Mixture of Experts 382
8.4.9 Bagging 385
8.4.10 Boosting 387
8.4.11 Random Forests 389
8.4.12 Model Averaging 390
8.4.13 Summary of Methods 396
8.4.14 Example Application Study 398
8.4.15 Further Developments 399
8.5 Application Studies 399
8.6 Summary and Discussion 400
8.7 Recommendations 401
8.8 Notes and References 401
Exercises 402
9 Performance Assessment 404
9.1 Introduction 404
9.2 Performance Assessment 405
9.2.1 Performance Measures 405
9.2.2 Discriminability 406
9.2.3 Reliability 413
9.2.4 ROC Curves for Performance Assessment 415
9.2.5 Population and Sensor Drift 419
9.2.6 Example Application Study 421
9.2.7 Further Developments 422
9.2.8 Summary 423
9.3 Comparing Classifier Performance 424
9.3.1 Which Technique is Best? 424
9.3.2 Statistical Tests 425
9.3.3 Comparing Rules When Misclassification Costs are Uncertain
426
9.3.4 Example Application Study 428
9.3.5 Further Developments 429
9.3.6 Summary 429
9.4 Application Studies 429
9.5 Summary and Discussion 430
9.6 Recommendations 430
9.7 Notes and References 430
Exercises 431
10 Feature Selection and Extraction 433
10.1 Introduction 433
10.2 Feature Selection 435
10.2.1 Introduction 435
10.2.2 Characterisation of Feature Selection Approaches 439
10.2.3 Evaluation Measures 440
10.2.4 Search Algorithms for Feature Subset Selection 449
10.2.5 Complete Search ? Branch and Bound 450
10.2.6 Sequential Search 454
10.2.7 Random Search 458
10.2.8 Markov Blanket 459
10.2.9 Stability of Feature Selection 460
10.2.10 Example Application Study 462
10.2.11 Further Developments 462
10.2.12 Summary 463
10.3 Linear Feature Extraction 463
10.3.1 Principal Components Analysis 464
10.3.2 Karhunen?Lo`eve Transformation 475
10.3.3 Example Application Study 481
10.3.4 Further Developments 482
10.3.5 Summary 483
10.4 Multidimensional Scaling 484
10.4.1 Classical Scaling 484
10.4.2 Metric MDS 486
10.4.3 Ordinal Scaling 487
10.4.4 Algorithms 490
10.4.5 MDS for Feature Extraction 491
10.4.6 Example Application Study 492
10.4.7 Further Developments 493
10.4.8 Summary 493
10.5 Application Studies 493
10.6 Summary and Discussion 495
10.7 Recommendations 495
10.8 Notes and References 496
Exercises 497
11 Clustering 501
11.1 Introduction 501
11.2 Hierarchical Methods 502
11.2.1 Single-Link Method 503
11.2.2 Complete-Link Method 506
11.2.3 Sum-of-Squares Method 507
11.2.4 General Agglomerative Algorithm 508
11.2.5 Properties of a Hierarchical Classification 508
11.2.6 Example Application Study 509
11.2.7 Summary 509
11.3 Quick Partitions 510
11.4 Mixture Models 511
11.4.1 Model Description 511
11.4.2 Example Application Study 512
11.5 Sum-of-Squares Methods 513
11.5.1 Clustering Criteria 514
11.5.2 Clustering Algorithms 515
11.5.3 Vector Quantisation 520
11.5.4 Example Application Study 530
11.5.5 Further Developments 530
11.5.6 Summary 531
11.6 Spectral Clustering 531
11.6.1 Elementary Graph Theory 531
11.6.2 Similarity Matrices 534
11.6.3 Application to Clustering 534
11.6.4 Spectral Clustering Algorithm 535
11.6.5 Forms of Graph Laplacian 535
11.6.6 Example Application Study 536
11.6.7 Further Developments 538
11.6.8 Summary 538
11.7 Cluster Validity 538
11.7.1 Introduction 538
11.7.2 Statistical Tests 539
11.7.3 Absence of Class Structure 540
11.7.4 Validity of Individual Clusters 541
11.7.5 Hierarchical Clustering 542
11.7.6 Validation of Individual Clusterings 542
11.7.7 Partitions 543
11.7.8 Relative Criteria 543
11.7.9 Choosing the Number of Clusters 545
11.8 Application Studies 546
11.9 Summary and Discussion 549
11.10 Recommendations 551
11.11 Notes and References 552
Exercises 553
12 Complex Networks 555
12.1 Introduction 555
12.1.1 Characteristics 557
12.1.2 Properties 557
12.1.3 Questions to Address 559
12.1.4 Descriptive Features 560
12.1.5 Outline 560
12.2 Mathematics of Networks 561
12.2.1 Graph Matrices 561
12.2.2 Connectivity 562
12.2.3 Distance Measures 562
12.2.4 Weighted Networks 563
12.2.5 Centrality Measures 563
12.2.6 Random Graphs 564
12.3 Community Detection 565
12.3.1 Clustering Methods 565
12.3.2 Girvan?Newman Algorithm 568
12.3.3 Modularity Approaches 570
12.3.4 Local Modularity 571
12.3.5 Clique Percolation 573
12.3.6 Example Application Study 574
12.3.7 Further Developments 575
12.3.8 Summary 575
12.4 Link Prediction 575
12.4.1 Approaches to Link Prediction 576
12.4.2 Example Application Study 578
12.4.3 Further Developments 578
12.5 Application Studies 579
12.6 Summary and Discussion 579
12.7 Recommendations 580
12.8 Notes and References 580
Exercises 580
13 Additional Topics 581
13.1 Model Selection 581
13.1.1 Separate Training and Test Sets 582
13.1.2 Cross-Validation 582
13.1.3 The Bayesian Viewpoint 583
13.1.4 Akaike?s Information Criterion 583
13.1.5 Minimum Description Length 584
13.2 Missing Data 585
13.3 Outlier Detection and Robust Procedures 586
13.4 Mixed Continuous and Discrete Variables 587
13.5 Structural Risk Minimisation and the
Vapnik?Chervonenkis Dimension 588
13.5.1 Bounds on the Expected Risk 588
13.5.2 The VC Dimension 589
References 591
Index 637
