Machine Learning and Data Mining

by Kononenko; Kukar

• ISBN13: 9781904275213
• ISBN10: 1904275214
• eBook ISBN(s): 9780857099440, 9781904275213
• Format: Paperback
• Copyright: 2007-04-30
• Publisher: Elsevier Science
• More Book Details
• Purchase Benefits

Summary

This book describes the basics of machine learning principles and algorithms used in data mining. It is suitable for advanced undergraduate and postgraduate students of computer science, researchers who want to adapt algorithms for particular data mining tasks, and advanced users of machine learning and data mining tools. Book jacket.

Author Biography

Igor Kononenko, Professor of Computer and Information Science, University of Ljubljana, Slovenia Matjaz Kukar, Assistant Professor of Computer and Information Science, University of Ljubljana, Slovenia

Table of Contents

Foreword	p. xv
Preface	p. xvii
Introduction	p. 1
The name of the game	p. 2
Overview of machine learning methods	p. 5
Classification	p. 5
Regression	p. 9
Logical relations	p. 11
Equations	p. 13
Clustering	p. 13
Reinforcement learning	p. 14
History of machine learning	p. 15
Symbolic rule learning	p. 15
Neural networks	p. 16
Reinforcement learning	p. 17
Genetic algorithms	p. 19
Statistical methods	p. 20
Formal learning theory	p. 20
Some early successes	p. 21
Automatic Mathematician	p. 21
Eurisko	p. 22
Dendral and Meta-Dendral	p. 22
Model Inference System	p. 23
Applications of machine learning	p. 24
Diagnosing the production process	p. 24
Medical diagnosis	p. 25
Risk evaluation of insurance and loan applicants	p. 25
Image classification	p. 26
Predicting the structure of chemical compounds	p. 27
Game playing	p. 28
Data mining tools and standards	p. 29
Data Mining standards	p. 29
Data Mining tools	p. 31
Summary and further reading	p. 34
Learning and Intelligence	p. 37
What is learning	p. 37
Definition of learning	p. 37
Artificial intelligence research	p. 38
Natural learning	p. 39
Innate and learned	p. 40
Memory	p. 41
Types of natural learning	p. 43
Learning, intelligence, consciousness	p. 47
Amount of intelligence	p. 47
Consciousness	p. 48
Limits of symbolic computability	p. 49
Possibility of artificial intelligence	p. 50
(Im)possibility of artificial consciousness	p. 51
Science and philosophy	p. 53
Why machine learning	p. 55
Summary and further reading	p. 57
Machine Learning Basics	p. 59
Basic principles	p. 59
Learning as modeling	p. 59
Minimum description length principle	p. 62
Incremental (on-line) learning	p. 64
Principle of multiple explanations	p. 65
Estimating probabilities	p. 66
Measures for performance evaluation	p. 68
Classification accuracy and confusion matrix	p. 70
Misclassification costs	p. 71
Class probability estimation	p. 72
Performance evaluation for two-class problems	p. 74
Performance evaluation in regression	p. 78
Bias and variance	p. 79
Estimating performance	p. 81
Reliability of quality estimations	p. 81
Confidence interval	p. 82
Cross validation	p. 83
Bootstrap methods	p. 84
*Comparing performance of ML algorithms	p. 84
Two algorithms on a single domain	p. 85
Two algorithms on several domains	p. 89
Several algorithms on several domains	p. 90
Combining several ML algorithms	p. 91
Combining predictions of several hypotheses	p. 92
Combining algorithms	p. 93
Bagging, boosting and random forests	p. 94
Transduction in machine learning	p. 95
Cost-sensitive learning	p. 97
Function imitation	p. 99
Classifiers for regression and regressors for classification	p. 99
Error-correcting output codes	p. 100
Summary and further reading	p. 102
Knowledge Representation	p. 107
Propositional calculus	p. 108
Representation with attributes	p. 108
Attribute properties and dependencies	p. 108
Classification, regression and association rules	p. 110
Generality of rules	p. 111
Operations on rules	p. 112
Hypothesis space	p. 112
Decision and regression trees	p. 113
*First order predicate calculus	p. 114
Prolog programming language	p. 115
Inductive logic programming	p. 117
Operations on predicates	p. 118
Discriminant and regression functions	p. 121
Linear functions	p. 122
Square and [Phi] functions	p. 123
Artificial neural networks	p. 123
Probability distributions	p. 126
Bayesian classifier	p. 126
Learning examples as probability distribution	p. 127
Naive Bayesian classifier	p. 127
Summary and further reading	p. 128
Learning as Search	p. 131
Exhaustive search	p. 133
Breadth-first search	p. 133
Depth-first search	p. 134
Iterative deepening	p. 134
Bounded exhaustive search (branch and bound)	p. 135
Bounded breadth-first search	p. 136
Bounded depth-first search	p. 138
Best-first search	p. 138
Greedy search	p. 139
Beam search	p. 140
Local optimization	p. 141
Gradient search	p. 142
Simulated annealing	p. 143
Basic algorithm	p. 143
Markovian neural networks	p. 144
Genetic algorithms	p. 146
Basic algorithm	p. 146
Genetic algorithms in machine learning	p. 148
Summary and further reading	p. 150
Attribute Quality Measures	p. 153
Measures for classification	p. 154
Impurity functions	p. 154
Measures based on information content	p. 155
Some other measures	p. 162
ReliefF	p. 164
Measures for regression	p. 168
Change of variance	p. 168
Regressional ReliefF	p. 169
MDL in regression	p. 171
**Formal derivations and proofs	p. 172
Properties of the attribute quality	p. 172
Entropy is an impurity measure	p. 173
Distance measure	p. 174
J-measure	p. 175
Gini-index	p. 177
Relief and Gini-index	p. 177
Variance and Gini-index	p. 178
Summary and further reading	p. 179
Data Preprocessing	p. 181
Representation of complex structures	p. 181
Representation of text documents	p. 182
Representation of images	p. 182
Representation of graphs	p. 183
Discretization of continuous attributes	p. 184
Types of discretization	p. 184
Controlling discretization	p. 185
Fuzzy discretization	p. 185
Attribute binarization	p. 186
Two-class problems	p. 187
Multi-class problems	p. 188
Transforming discrete attributes into continuous	p. 188
Dealing with missing values	p. 189
Visualization	p. 189
Visualizing a single attribute	p. 190
Visualizing pairs of attributes	p. 190
Visualizing several attributes	p. 193
Visualizing results of machine learning	p. 194
Dimensionality reduction	p. 199
Feature subset selection	p. 199
Feature extraction	p. 200
Principal components analysis	p. 201
Independent component analysis	p. 203
Factor analysis	p. 206
Random projections	p. 207
**Formal derivations and proofs	p. 208
Summary and further reading	p. 210
*Constructive Induction	p. 213
Dependence of attributes	p. 215
Dependence of events	p. 215
Bias, variance and attribute dependence	p. 216
Measuring attribute dependence	p. 216
Visualization of attribute dependence	p. 218
Constructive induction with pre-defined operators	p. 219
Constructive induction without pre-defined operators	p. 222
Hypothesis-based constructive induction	p. 222
Constructive induction based on Cartesian products	p. 222
Summary and further reading	p. 225
Symbolic Learning	p. 227
Learning of decision trees	p. 227
Building and using decision trees	p. 227
Building binary decision trees	p. 229
Pruning decision trees	p. 229
Missing and "don't care" values	p. 231
Learning of decision rules	p. 231
Generating a single rule	p. 232
Generating a set of rules	p. 232
Learning of association rules	p. 233
Support and confidence	p. 233
APriori algorithm	p. 234
Improving APriori	p. 235
Learning of regression trees	p. 236
Building and using regression trees	p. 236
Pruning of regression trees	p. 238
*Inductive logic programming	p. 239
Generating a set of rules in FOIL	p. 239
ReliefF for ILP	p. 241
Naive and semi-naive Bayesian classifier	p. 242
Naive Bayesian classifier	p. 242
Explaining decisions	p. 243
Semi-naive Bayesian classifier	p. 244
Practical considerations	p. 248
Bayesian belief networks	p. 249
Bayesian belief networks for classification	p. 250
Classification with Bayesian belief networks	p. 252
Learning the Bayesian network topology	p. 253
Learning tree-augmented naive Bayesian classifiers	p. 255
Summary and further reading	p. 256
Statistical Learning	p. 259
Nearest neighbors	p. 259
K nearest neighbors	p. 259
Weighted k-nearest neighbors	p. 261
Locally weighted regression	p. 261
Discriminant analysis	p. 262
Optimal discriminant function	p. 263
Classification with discriminant function	p. 264
Linear regression	p. 265
Logistic regression	p. 266
*Support vector machines	p. 267
Basic SVM principle	p. 268
Inexact classification	p. 271
SVM method	p. 271
Summary and further reading	p. 273
Artificial Neural Networks	p. 275
Introduction	p. 275
Simple example	p. 275
Distributed memory	p. 278
Properties of ANN	p. 280
Applications	p. 282
Analogy with brain	p. 283
Relation to symbolic AI methods	p. 284
Types of artificial neural networks	p. 285
Topology	p. 285
Application purpose	p. 286
Learning rule	p. 288
Combination function	p. 289
*Hopfield's neural network	p. 291
Discrete model	p. 291
Continuous model	p. 292
*Bayesian neural network	p. 293
Topology and learning rule	p. 293
Discrete models	p. 294
Implementation of Bayesian classifiers	p. 296
Continuous models	p. 297
Perceptron	p. 298
Two-layered perceptron	p. 299
Multi-layered perceptron	p. 302
Problems with backpropagation	p. 305
Radial basis function networks	p. 306
Topology of RBF networks	p. 307
RBF network execution	p. 308
RBF network training	p. 308
Some properties of RBF networks	p. 309
**Formal derivations and proofs	p. 310
Stability of Hopfield's models	p. 310
Stability of BNN models	p. 312
Backpropagation of errors	p. 315
Summary and further reading	p. 317
Cluster Analysis	p. 321
Introduction	p. 321
Clustering and classification	p. 322
Taxonomy of clustering algorithms	p. 323
Measures of dissimilarity	p. 324
Dissimilarity measures for discrete data	p. 325
Dissimilarity measures for continuous data	p. 326
Dissimilarity measures for mixed data	p. 327
Dissimilarity measures for groups of examples	p. 328
Construction and choice of measures	p. 329
Hierarchical clustering	p. 330
Agglomerative hierarchical clustering	p. 330
Divisive hierarchical clustering	p. 333
Practical considerations	p. 336
Partitional clustering	p. 338
Partitioning criteria	p. 338
Partitional algorithms	p. 340
Number of clusters	p. 345
Model-based clustering	p. 346
Finite mixture models	p. 347
Maximum likelihood estimation and EM algorithm	p. 347
Other clustering methods	p. 350
Fuzzy clustering	p. 350
Conceptual clustering	p. 351
Evolutionary clustering	p. 353
Knowledge-based clustering	p. 354
Summary and further reading	p. 356
**Learning Theory	p. 359
Computability theory and recursive functions	p. 361
Computability theory	p. 361
Recursive functions	p. 364
Undecidability of universal formalisms	p. 365
Recursively enumerable sets	p. 366
Formal learning theory	p. 368
Identification	p. 368
Basic theorems	p. 370
Properties of learning functions	p. 372
Learning strategies	p. 372
Computational constraints	p. 373
Infinite languages	p. 376
Some sensible learning strategies	p. 378
Reliability and confidence	p. 381
Properties of input data	p. 382
Evidential relations	p. 382
Noisy and incomplete texts	p. 382
Texts with positive and negative examples	p. 384
Texts with oracles	p. 385
Convergence criteria	p. 386
Convergence	p. 386
Extensional and bounded extensional convergence	p. 387
Convergence towards simple hypotheses	p. 388
Convergence towards recursive hypotheses	p. 388
Implications for machine learning	p. 389
Summary and further reading	p. 390
**Computational Learning Theory	p. 393
Introduction	p. 393
General framework for concept learning	p. 395
Basic notation	p. 395
Some typical concept classes	p. 396
Importance of representation	p. 397
PAC Learning Model	p. 398
Basic PAC learning model	p. 398
Some variations of the PAC learning model	p. 399
Vapnik-Chervonenkis dimension	p. 400
Calculating the VC-Dimension	p. 400
Calculating VC-dimension of complex concept classes	p. 402
VC-dimension and PAC learning model	p. 402
Occam learning	p. 403
Learning in the presence of noise	p. 406
Models of noise	p. 406
Gaining noise tolerance with random classification noise	p. 407
Some results on more complicated models of noise	p. 409
Exact and mistake bounded learning models	p. 410
On-line learning model	p. 410
Query learning model	p. 414
Inherent unpredictability and PAC-reductions	p. 415
Hard problems	p. 415
Reducibility in PAC learning	p. 416
Weak and strong learning	p. 417
Weak and strong learnability	p. 417
Boosting the confidence	p. 418
Boosting the accuracy	p. 418
Summary and further reading	p. 420
*Definitions of some lesser known terms	p. 423
Computational complexity classes	p. 423
Complexity class P	p. 424
Complexity class NP	p. 424
Complexity class RP	p. 424
Asymptotic notation	p. 425
Some bounds for probabilistic analysis	p. 427
Union bound	p. 427
Chernoff bounds	p. 427
Covariance matrix	p. 428
References	p. 429
Index	p. 447
Table of Contents provided by Ingram. All Rights Reserved.