数据挖掘导论（英文影印版）

.2.3.5　feature creation　39
2.3.6　discretization and binarization　41
2.3.7　variable transformation　45
2.4　measures of similarity and dissimilarity　47
2.4.1　basics　47
2.4.2　similarity and dissimilarity between simple attributes　49
2.4.3　dissimilarities between data objects　50
2.4.4　similarities between data objects　52
2.4.5　examples of proximity measures　53
2.4.6　issues in proximity calculation　58
2.4.7　selecting the right proximity measure　60
2.5　bibliographic notes　61
2.6　exercises　64
3　exploring data　71
3.1　the iris data set　71
3.2　summary statistics　72
3.2.1　frequencies and the mode　72
3.2.2　percentiles　73
3.2.3　measures of location: mean and median　73
3.2.4　measures of spread: range and variance　75
3.2.5　multivariate summary statistics　76
3.2.6　other ways to summarize the data　77
3.3　visualization　77
3.3.1　motivations for visualization　77
3.3.2　general concepts　78
3.3.3　techniques　81
3.3.4　visualizing higher-dimensional data　90
3.3.5　do's and don'ts　94
3.4　olap and multidimensional data analysis　95
3.4.1　representing iris data as a multidimensional array　95
3.4.2　multidimensional data: the general case　97
3.4.3　analyzing multidimensional data　98
3.4.4　final comments on multidimensional data analysis　101
3.5　bibliographic notes　102
3.6　exercises　103
4　classification: basic concepts, decision trees, and model evaluation　105
4.1　preliminaries　105
4.2　general approach to solving a classification problem　107
4.3　decision tree induction　108
4.3.1　how a decision tree works　108
4.3.2　how to build a decision tree　110
4.3.3　methods for expressing attribute test conditions　112
4.3.4　measures for selecting the best split　114
4.3.5　algorithm for decision tree induction　119
4.3.6　an example: web robot detection　120
4.3.7　characteristics of decision tree induction　122
4.4　model overfitting　125
4.4.1　overfitting due to presence of noise　127
4.4.2　overfitting due to lack of representative samples　129
4.4.3　overfitting and the multiple comparison procedure　129
4.4.4　estimation of generalization errors　131
4.4.5　handling overfitting in decision tree induction　134
4.5　evaluating the performance of a classifier　135
4.5.1　holdout method　136
4.5.2　random subsampling　136
4.5.3　cross-validation　136
4.5.4　bootstrap　137
4.6　methods for comparing classifiers　137
4.6.1　estimating a confidence interval for accuracy　138
4.6.2　comparing the performance of　two models　139
4.6.3　comparing the performance of two classifiers　140
4.7　bibliographic notes　141
4.8　exercises　144
5　classification: alternative techniques　151
5.1　rule-based classifier　151
5.1.1　how a rule-based classifier works　153
5.1.2　rule-ordering schemes　154
5.1.3　how to build a rule-based classifier　155
5.1.4　direct methods for rule extraction　155
5.1.5　indirect methods for rule extraction　161
5.1.6　characteristics of rule-based classifiers　163
5.2　nearest-neighbor classifiers　163
5.2.1　algorithm　165
5.2.2　characteristics of nearest-neighbor classifiers　165
5.3　bayesian classifiers　166
5.3.1　bayes theorem　166
5.3.2　using the bayes theorem for classification　168
5.3.3　na?ve bayes classifier　169
5.3.4　bayes error rate　175
5.3.5　bayesian belief networks　176
5.4　artificial neural network (ann)　181
5.4.1　perceptron　181
5.4.2　multilayer artificial neural network　184
5.4.3　characteristics of ann　187
5.5　support vector machine (svm)　188
5.5.1　maximum margin hyperplanes　188
5.5.2　linear svm: separable case　190
5.5.3　linear svm: nonseparable case　195
5.5.4　nonlinear svm　198
5.5.5　characteristics of svm　203
5.6　ensemble methods　203
5.6.1　rationale for ensemble method　203
5.6.2　methods for constructing an ensemble classifier　204
5.6.3　bias-variance decomposition　206
5.6.4　bagging　209
5.6.5　boosting　211
5.6.6　random forests　215
5.6.7　empirical comparison among ensemble methods　216
5.7　class imbalance problem　217
5.7.1　alternative metrics　218
5.7.2　the receiver operating characteristic curve　220
5.7.3　cost-sensitive learning　223
5.7.4　sampling-based approaches　225
5.8　multiclass problem　226
5.9　bibliographic notes　228
5.10 exercises　233
6　association analysis: basic concepts and algorithms　241
6.1　problem definition　242
6.2　frequent itemset generation　244
6.2.1　the apriori principle　246
6.2.2　frequent itemset generation in the apriori algorithm　247
6.2.3　candidate generation and pruning　249
6.2.4　support counting　252
6.2.5　computational complexity　255
6.3　rule generation　257
6.3.1　confidence-based pruning　258
6.3.2　rule generation in apriori algorithm　258
6.3.3　an example: congressional voting records　259
6.4　compact representation of frequent itemsets　260
6.4.1　maximal frequent itemsets　260
6.4.2　closed frequent itemsets　262
6.5　alternative methods for generating frequent itemsets　264
6.6　fp-growth algorithm　268
6.6.1　fp-tree representation　268
6.6.2　frequent itemset generation in fp-growth algorithm　270
6.7　evaluation of association patterns　273
6.7.1　objective measures of interestingness　274
6.7.2　measures beyond pairs of binary variables　282
6.7.3　simpson's paradox　283
6.8　effect of skewed support distribution　285
6.9　bibliographic notes　288
6.10 exercises　298
7　association analysis: advanced concepts　307
7.1　handling categorical attributes　307
7.2　handling continuous attributes　309
7.2.1　discretization-based methods　310
7.2.2　statistics-based methods　312
7.2.3　non-discretization methods　314
7.3　handling a concept hierarchy　316
7.4　sequential patterns　318
7.4.1　problem formulation　318
7.4.2　sequential pattern discovery　320
7.4.3　timing constraints　323
7.4.4　alternative counting schemes　327
7.5　subgraph patterns　328
7.5.1　graphs and subgraphs　329
7.5.2　frequent subgraph mining　330
7.5.3　apriori-like method　332
7.5.4　candidate generation　333
7.5.5　candidate pruning　338
7.5.6　support counting　340
7.6　infrequent patterns　340
7.6.1　negative patterns　341
7.6.2　negatively correlated patterns　342
7.6.3　comparisons among infrequent patterns, negative patterns, and negatively correlated patterns　343
7.6.4　techniques for mining interesting infrequent patterns　344
7.6.5　techniques based on mining negative patterns　345
7.6.6　techniques based on support expectation　347
7.7　bibliographic notes　350
7.8　exercises　353
8　cluster analysis: basic concepts and algorithms　363
8.1　overview　365
8.1.1　what is cluster analysis?　365
8.1.2　different types of clusterings　366
8.1.3　different types of clusters　368
8.2　k-means　370
8.2.1　the basic k-means algorithm　371
8.2.2　k-means: additional issues　378
8.2.3　bisecting k-means　380
8.2.4　k-means and different types of clusters　381
8.2.5　strengths and weaknesses　383
8.2.6　k-means as an optimization problem　383
8.3　agglomerative hierarchical clustering　385
8.3.1　basic agglomerative hierarchical clustering algorithm　385
8.3.2　specific techniques　387
8.3.3　the lance-williams formula for cluster proximity　391
8.3.4　key issues in hierarchical clustering　391
8.3.5　strengths and weaknesses　393
8.4　dbscan　393
8.4.1　traditional density: center-based approach　393
8.4.2　the dbscan algorithm　394
8.4.3　strengths and weaknesses　398
8.5　cluster evaluation　398
8.5.1　overview　399
8.5.2　unsupervised cluster evaluation using cohesion and separation　401
8.5.3　unsupervised cluster evaluation using the proximity matrix　406
8.5.4　unsupervised evaluation of hierarchical clustering　408
8.5.5　determining the correct number of clusters　409
8.5.6　clustering tendency　410
8.5.7　supervised measures of cluster validity　411
8.5.8　assessing the significance of cluster validity measures　414
8.6　bibliographic notes　416
8.7　exercises　419
9　cluster analysis: additional issues and algorithms　427
9.1　characteristics of data, clusters, and clustering algorithms　427
9.1.1　example: comparing k-means and dbscan　428
9.1.2　data characteristics　429
9.1.3　cluster characteristics　430
9.1.4　general characteristics of clustering algorithms　431
9.2　prototype-based clustering　433
9.2.1　fuzzy clustering　433
9.2.2　clustering using mixture models　437
9.2.3　self-organizing maps (som)　446
9.3　density-based clustering　451
9.3.1　grid-based clustering　451
9.3.2　subspace clustering　454
9.3.3　denclue: a kernel-based scheme for density-based clustering　457
9.4　graph-based clustering　460
9.4.1　sparsification　461
9.4.2　minimum spanning tree (mst) clustering　462
9.4.3　opossum: optimal partitioning of sparse similarities using metis　463
9.4.4　chameleon: hierarchical clustering with dynamic modeling　464
9.4.5　shared nearest neighbor similarity　468
9.4.6　the jarvis-patrick clustering algorithm　471
9.4.7　snn density　472
9.4.8　snn density-based clustering　473
9.5　scalable clustering algorithms　475
9.5.1　scalability: general issues and approaches　476
9.5.2　birch　477
9.5.3　cure　479
9.6　which clustering algorithm?　482
9.7　bibliographic notes　484
9.8　exercises　488
10　anomaly detection　491
10.1　preliminaries　492
10.1.1　causes of anomalies　492
10.1.2　approaches to anomaly detection　493
10.1.3　the use of class labels　494
10.1.4　issues　495
10.2　statistical approaches　496
10.2.1　detecting outliers in a univariate normal distribution　497
10.2.2　outliers in a multivariate normal distribution　499
10.2.3　a mixture model approach for anomaly detection　500
10.2.4　strengths and weaknesses　502
10.3　proximity-based outlier detection　502
10.3.1　strengths and weaknesses　503
10.4　density-based outlier detection　504
10.4.1　detection of outliers using relative density　505
10.4.2　strengths and weaknesses　506
10.5　clustering-based techniques　506
10.5.1　assessing the extent to which an object belongs to a cluster　507
10.5.2　impact of outliers on the initial clustering　509
10.5.3　the number of clusters to use　509
10.5.4　strengths and weaknesses　509
10.6　bibliographic notes　510
10.7　exercises　513

.