数据挖掘基础概念和算法（英文）.pdf

【实例简介】数据挖掘基础概念和算法英文，Data Mining and Analysis-Fundamental Concepts and Algorithms

【文件目录】

Contents
Preface 1
1 Data Mining and Analysis 4
1.1 Data Matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2 Attributes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.3 Data: Algebraic and Geometric View . . . . . . . . . . . . . . . . . . 7
1.3.1 Distance and Angle . . . . . . . . . . . . . . . . . . . . . . . . 9
1.3.2 Mean and Total Variance . . . . . . . . . . . . . . . . . . . . 13
1.3.3 Orthogonal Projection . . . . . . . . . . . . . . . . . . . . . . 14
1.3.4 Linear Independence and Dimensionality . . . . . . . . . . . . 15
1.4 Data: Probabilistic View . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.4.1 Bivariate Random Variables . . . . . . . . . . . . . . . . . . . 24
1.4.2 Multivariate Random Variable . . . . . . . . . . . . . . . . . 28
1.4.3 Random Sample and Statistics . . . . . . . . . . . . . . . . . 29
1.5 Data Mining . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
1.5.1 Exploratory Data Analysis . . . . . . . . . . . . . . . . . . . . 31
1.5.2 Frequent Pattern Mining . . . . . . . . . . . . . . . . . . . . . 33
1.5.3 Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
1.5.4 Classification . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
1.6 Further Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
1.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
I Data Analysis Foundations 37
2 Numeric Attributes 38
2.1 Univariate Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
2.1.1 Measures of Central Tendency . . . . . . . . . . . . . . . . . . 39
2.1.2 Measures of Dispersion . . . . . . . . . . . . . . . . . . . . . . 43
2.2 Bivariate Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
2.2.1 Measures of Location and Dispersion . . . . . . . . . . . . . . 49
2.2.2 Measures of Association . . . . . . . . . . . . . . . . . . . . . 50
DRAFT @ 2013-07-10 11:07. Please do not distribute. Feedback is Welcome.
Note that this book shall be available for purchase from Cambridge University Press and other
standard distribution channels, that no unauthorized distribution shall be allowed, and that the
reader may make one copy only for personal on-screen use.
CONTENTS ii
2.3 Multivariate Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
2.4 Data Normalization . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
2.5 Normal Distribution . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
2.5.1 Univariate Normal Distribution . . . . . . . . . . . . . . . . . 61
2.5.2 Multivariate Normal Distribution . . . . . . . . . . . . . . . . 63
2.6 Further Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
2.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
3 Categorical Attributes 71
3.1 Univariate Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
3.1.1 Bernoulli Variable . . . . . . . . . . . . . . . . . . . . . . . . 71
3.1.2 Multivariate Bernoulli Variable . . . . . . . . . . . . . . . . . 74
3.2 Bivariate Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
3.2.1 Attribute Dependence: Contingency Analysis . . . . . . . . . 88
3.3 Multivariate Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
3.3.1 Multi-way Contingency Analysis . . . . . . . . . . . . . . . . 95
3.4 Distance and Angle . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
3.5 Discretization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
3.6 Further Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
3.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
4 Graph Data 105
4.1 Graph Concepts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
4.2 Topological Attributes . . . . . . . . . . . . . . . . . . . . . . . . . . 110
4.3 Centrality Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
4.3.1 Basic Centralities . . . . . . . . . . . . . . . . . . . . . . . . . 115
4.3.2 Web Centralities . . . . . . . . . . . . . . . . . . . . . . . . . 117
4.4 Graph Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
4.4.1 Erdös-Rényi Random Graph Model . . . . . . . . . . . . . . . 129
4.4.2 Watts-Strogatz Small-world Graph Model . . . . . . . . . . . 133
4.4.3 Barabási-Albert Scale-free Model . . . . . . . . . . . . . . . . 139
4.5 Further Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
4.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148
5 Kernel Methods 150
5.1 Kernel Matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155
5.1.1 Reproducing Kernel Map . . . . . . . . . . . . . . . . . . . . 156
5.1.2 Mercer Kernel Map . . . . . . . . . . . . . . . . . . . . . . . . 158
5.2 Vector Kernels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
5.3 Basic Kernel Operations in Feature Space . . . . . . . . . . . . . . . 166
5.4 Kernels for Complex Objects . . . . . . . . . . . . . . . . . . . . . . 173
5.4.1 Spectrum Kernel for Strings . . . . . . . . . . . . . . . . . . . 173
5.4.2 Diffusion Kernels on Graph Nodes . . . . . . . . . . . . . . . 175
DRAFT @ 2013-07-10 11:07. Please do not distribute. Feedback is Welcome.
Note that this book shall be available for purchase from Cambridge University Press and other
standard distribution channels, that no unauthorized distribution shall be allowed, and that the
reader may make one copy only for personal on-screen use.
CONTENTS iii
5.5 Further Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180
5.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180
6 High-Dimensional Data 182
6.1 High-Dimensional Objects . . . . . . . . . . . . . . . . . . . . . . . . 182
6.2 High-Dimensional Volumes . . . . . . . . . . . . . . . . . . . . . . . . 184
6.3 Hypersphere Inscribed within Hypercube . . . . . . . . . . . . . . . . 187
6.4 Volume of Thin Hypersphere Shell . . . . . . . . . . . . . . . . . . . 189
6.5 Diagonals in Hyperspace . . . . . . . . . . . . . . . . . . . . . . . . . 190
6.6 Density of the Multivariate Normal . . . . . . . . . . . . . . . . . . . 191
6.7 Appendix: Derivation of Hypersphere Volume . . . . . . . . . . . . . 195
6.8 Further Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 200
6.9 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 200
7 Dimensionality Reduction 203
7.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203
7.2 Principal Component Analysis . . . . . . . . . . . . . . . . . . . . . . 208
7.2.1 Best Line Approximation . . . . . . . . . . . . . . . . . . . . 208
7.2.2 Best Two-dimensional Approximation . . . . . . . . . . . . . 212
7.2.3 Best r-dimensional Approximation . . . . . . . . . . . . . . . 216
7.2.4 Geometry of PCA . . . . . . . . . . . . . . . . . . . . . . . . 221
7.3 Kernel Principal Component Analysis (Kernel PCA) . . . . . . . . . 224
7.4 Singular Value Decomposition . . . . . . . . . . . . . . . . . . . . . . 232
7.4.1 Geometry of SVD . . . . . . . . . . . . . . . . . . . . . . . . 233
7.4.2 Connection between SVD and PCA . . . . . . . . . . . . . . . 234
7.5 Further Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 236
7.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 237
II Frequent Pattern Mining 239
8 Itemset Mining 240
8.1 Frequent Itemsets and Association Rules . . . . . . . . . . . . . . . . 240
8.2 Itemset Mining Algorithms . . . . . . . . . . . . . . . . . . . . . . . 244
8.2.1 Level-Wise Approach: Apriori Algorithm . . . . . . . . . . . 246
8.2.2 Tidset Intersection Approach: Eclat Algorithm . . . . . . . . 249
8.2.3 Frequent Pattern Tree Approach: FPGrowth Algorithm . . . 256
8.3 Generating Association Rules . . . . . . . . . . . . . . . . . . . . . . 259
8.4 Further Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 262
8.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 263
DRAFT @ 2013-07-10 11:07. Please do not distribute. Feedback is Welcome.
Note that this book shall be available for purchase from Cambridge University Press and other
standard distribution channels, that no unauthorized distribution shall be allowed, and that the
reader may make one copy only for personal on-screen use.
CONTENTS iv
9 Summarizing Itemsets 268
9.1 Maximal and Closed Frequent Itemsets . . . . . . . . . . . . . . . . . 268
9.2 Mining Maximal Frequent Itemsets: GenMax Algorithm . . . . . . . 272
9.3 Mining Closed Frequent Itemsets: Charm algorithm . . . . . . . . . 274
9.4 Non-Derivable Itemsets . . . . . . . . . . . . . . . . . . . . . . . . . . 277
9.5 Further Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 283
9.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 284
10 Sequence Mining 288
10.1 Frequent Sequences . . . . . . . . . . . . . . . . . . . . . . . . . . . . 288
10.2 Mining Frequent Sequences . . . . . . . . . . . . . . . . . . . . . . . 289
10.2.1 Level-Wise Mining: GSP . . . . . . . . . . . . . . . . . . . . . 291
10.2.2 Vertical Sequence Mining: SPADE . . . . . . . . . . . . . . . 292
10.2.3 Projection-Based Sequence Mining: PrefixSpan . . . . . . . . 295
10.3 Substring Mining via Suffix Trees . . . . . . . . . . . . . . . . . . . . 297
10.3.1 Suffix Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . 297
10.3.2 Ukkonen’s Linear Time Algorithm . . . . . . . . . . . . . . . 300
10.4 Further Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 308
10.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 308
11 Graph Pattern Mining 313
11.1 Isomorphism and Support . . . . . . . . . . . . . . . . . . . . . . . . 313
11.2 Candidate Generation . . . . . . . . . . . . . . . . . . . . . . . . . . 317
11.2.1 Canonical Code . . . . . . . . . . . . . . . . . . . . . . . . . . 319
11.3 The gSpan Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 322
11.3.1 Extension and Support Computation . . . . . . . . . . . . . . 325
11.3.2 Canonicality Checking . . . . . . . . . . . . . . . . . . . . . . 329
11.4 Further Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 330
11.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 332
12 Pattern and Rule Assessment 336
12.1 Rule and Pattern Assessment Measures . . . . . . . . . . . . . . . . 336
12.1.1 Rule Assessment Measures . . . . . . . . . . . . . . . . . . . . 337
12.1.2 Pattern Assessment Measures . . . . . . . . . . . . . . . . . . 346
12.1.3 Comparing Multiple Rules and Patterns . . . . . . . . . . . . 349
12.2 Significance Testing and Confidence Intervals . . . . . . . . . . . . . 353
12.2.1 Fisher Exact Test for Productive Rules . . . . . . . . . . . . . 353
12.2.2 Permutation Test for Significance . . . . . . . . . . . . . . . . 358
12.2.3 Bootstrap Sampling for Confidence Interval . . . . . . . . . . 363
12.3 Further Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 366
12.4 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 367
DRAFT @ 2013-07-10 11:07. Please do not distribute. Feedback is Welcome.
Note that this book shall be available for purchase from Cambridge University Press and other
standard distribution channels, that no unauthorized distribution shall be allowed, and that the
reader may make one copy only for personal on-screen use.
CONTENTS v
III Clustering 369
13 Representative-based Clustering 370
13.1 K-means Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . 371
13.2 Kernel K-means . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 374
13.3 Expectation Maximization (EM) Clustering . . . . . . . . . . . . . . 380
13.3.1 EM in One Dimension . . . . . . . . . . . . . . . . . . . . . . 382
13.3.2 EM in d-Dimensions . . . . . . . . . . . . . . . . . . . . . . . 385
13.3.3 Maximum Likelihood Estimation . . . . . . . . . . . . . . . . 392
13.3.4 Expectation-Maximization Approach . . . . . . . . . . . . . . 396
13.4 Further Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 399
13.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 400
14 Hierarchical Clustering 403
14.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 403
14.2 Agglomerative Hierarchical Clustering . . . . . . . . . . . . . . . . . 406
14.2.1 Distance between Clusters . . . . . . . . . . . . . . . . . . . . 406
14.2.2 Updating Distance Matrix . . . . . . . . . . . . . . . . . . . . 410
14.2.3 Computational Complexity . . . . . . . . . . . . . . . . . . . 412
14.3 Further Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 412
14.4 Exercises and Projects . . . . . . . . . . . . . . . . . . . . . . . . . . 413
15 Density-based Clustering 416
15.1 The DBSCAN Algorithm . . . . . . . . . . . . . . . . . . . . . . . . 417
15.2 Kernel Density Estimation . . . . . . . . . . . . . . . . . . . . . . . . 420
15.2.1 Univariate Density Estimation . . . . . . . . . . . . . . . . . 421
15.2.2 Multivariate Density Estimation . . . . . . . . . . . . . . . . 423
15.2.3 Nearest Neighbor Density Estimation . . . . . . . . . . . . . . 426
15.3 Density-based Clustering: DENCLUE . . . . . . . . . . . . . . . . . 427
15.4 Further Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 433
15.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 433
16 Spectral and Graph Clustering 437
16.1 Graphs and Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . 437
16.2 Clustering as Graph Cuts . . . . . . . . . . . . . . . . . . . . . . . . 445
16.2.1 Clustering Objective Functions: Ratio and Normalized Cut . 447
16.2.2 Spectral Clustering Algorithm . . . . . . . . . . . . . . . . . . 450
16.2.3 Maximization Objectives: Average Cut and Modularity . . . . 454
16.3 Markov Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . 462
16.4 Further Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 469
16.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 470
DRAFT @ 2013-07-10 11:07. Please do not distribute. Feedback is Welcome.
Note that this book shall be available for purchase from Cambridge University Press and other
standard distribution channels, that no unauthorized distribution shall be allowed, and that the
reader may make one copy only for personal on-screen use.
CONTENTS vi
17 Clustering Validation 472
17.1 External Measures . . . . . . . . . . . . . . . . . . . . . . . . . . . . 473
17.1.1 Matching Based Measures . . . . . . . . . . . . . . . . . . . . 473
17.1.2 Entropy Based Measures . . . . . . . . . . . . . . . . . . . . . 478
17.1.3 Pair-wise Measures . . . . . . . . . . . . . . . . . . . . . . . . 481
17.1.4 Correlation Measures . . . . . . . . . . . . . . . . . . . . . . . 485
17.2 Internal Measures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 488
17.3 Relative Measures . . . . . . . . . . . . . . . . . . . . . . . . . . . . 497
17.3.1 Cluster Stability . . . . . . . . . . . . . . . . . . . . . . . . . 504
17.3.2 Clustering Tendency . . . . . . . . . . . . . . . . . . . . . . . 507
17.4 Further Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 512
17.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 513
IV Classification 515
18 Probabilistic Classification 516
18.1 Bayes Classifier . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 516
18.1.1 Estimating the Prior Probability . . . . . . . . . . . . . . . . 517
18.1.2 Estimating the Likelihood . . . . . . . . . . . . . . . . . . . . 517
18.2 Naive Bayes Classifier . . . . . . . . . . . . . . . . . . . . . . . . . . 523
18.3 Further Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 527
18.4 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 527
19 Decision Tree Classifier 529
19.1 Decision Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 531
19.2 Decision Tree Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . 534
19.2.1 Split-point Evaluation Measures . . . . . . . . . . . . . . . . 535
19.2.2 Evaluating Split-points . . . . . . . . . . . . . . . . . . . . . . 536
19.2.3 Computational Complexity . . . . . . . . . . . . . . . . . . . 545
19.3 Further Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 545
19.4 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 546
20 Linear Discriminant Analysis 548
20.1 Optimal Linear Discriminant . . . . . . . . . . . . . . . . . . . . . . 548
20.2 Kernel Discriminant Analysis . . . . . . . . . . . . . . . . . . . . . . 555
20.3 Further Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 562
20.4 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 562
21 Support Vector Machines 565
21.1 Linear Discriminants and Margins . . . . . . . . . . . . . . . . . . . 565
21.2 SVM: Linear and Separable Case . . . . . . . . . . . . . . . . . . . . 571
21.3 Soft Margin SVM: Linear and Non-Separable Case . . . . . . . . . . 576
DRAFT @ 2013-07-10 11:07. Please do not distribute. Feedback is Welcome.
Note that this book shall be available for purchase from Cambridge University Press and other
standard distribution channels, that no unauthorized distribution shall be allowed, and that the
reader may make one copy only for personal on-screen use.
CONTENTS vii
21.3.1 Hinge Loss . . . . . . . . . . . . . . . . . . . . . . . . . . . . 577
21.3.2 Quadratic Loss . . . . . . . . . . . . . . . . . . . . . . . . . . 581
21.4 Kernel SVM: Nonlinear Case . . . . . . . . . . . . . . . . . . . . . . 582
21.5 SVM Training Algorithms . . . . . . . . . . . . . . . . . . . . . . . . 587
21.5.1 Dual Solution: Stochastic Gradient Ascent . . . . . . . . . . . 587
21.5.2 Primal Solution: Newton Optimization . . . . . . . . . . . . . 592
22 Classification Assessment 601
22.1 Classification Performance Measures . . . . . . . . . . . . . . . . . . 601
22.1.1 Contingency Table Based Measures . . . . . . . . . . . . . . . 603
22.1.2 Binary Classification: Positive and Negative Class . . . . . . 606
22.1.3 ROC Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . 610
22.2 Classifier Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . 615
22.2.1 K-fold Cross-Validation . . . . . . . . . . . . . . . . . . . . . 616
22.2.2 Bootstrap Resampling . . . . . . . . . . . . . . . . . . . . . . 617
22.2.3 Confidence Intervals . . . . . . . . . . . . . . . . . . . . . . . 619
22.2.4 Comparing Classifiers: Paired t-Test . . . . . . . . . . . . . . 624
22.3 Bias-Variance Decomposition . . . . . . . . . . . . . . . . . . . . . . 626
22.3.1 Ensemble Classifiers . . . . . . . . . . . . . . . . . . . . . . . 631
22.4 Further Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 637
22.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 638
Index 640