Book summary “Data mining”: summary

Introduction

You face the computational challenge of handling heterogeneous data types and massive scales across modern repositories. You need a rigorous intersection of computer science and statistics to extract actionable knowledge without losing analytical accuracy. Data mining provides this foundation by organizing complex algorithmic processes around four core superproblems.

Charu C. Aggarwal structures this book to guide you from fundamental building blocks to advanced applications and privacy safeguards. You will explore association patterns, classification, cluster analysis, and outlier detection before examining complex domains like data streams and graphs.

• How do you efficiently extract frequent itemsets from massive transaction logs?
• Which classification models best predict labels for unseen instances?
• What mechanisms isolate true data anomalies from noise?

1. Association Pattern Mining

Association pattern mining identifies co-occurring groups of items in transaction databases, traditionally quantified by support and directional confidence. Transactions are binary multidimensional records where items are represented as 1 or 0. The support of an itemset is the fraction of transactions containing it as a subset. Association rules are generated based on both support and confidence thresholds.

Association pattern mining extracts frequently co-occurring itemsets and rules from transaction databases using efficient counting strategies and search space pruning.

A classic example from data mining folklore is the rule {beer} -> {diapers}, suggesting that buying beer makes diapers more likely to be bought. For instance, you can examine Table 4.1 to see 5 transactions and calculate that the support of the itemset {1, 2} is 2 out of 5.

Foundations and Apriori Algorithm

The support monotonicity and downward closure properties dictate that every subset of a frequent itemset must also be frequent. This enables efficient search space pruning. Because any subset of an itemset contained in a transaction is also contained in it, the support of a subset is at least equal to that of the superset. Algorithms leverage this to avoid counting candidate supersets when their subsets are infrequent.

The Apriori algorithm performs a breadth-first, level-wise search of the candidate space. It iteratively generates candidate itemsets through joins and prunes them using the downward closure property. Apriori starts by counting 1-itemsets, then joins frequent k-itemsets to generate candidate (k+1)-itemsets. It uses hash trees for efficient support counting across database passes.

You can execute Apriori using these specific operational steps:

• Count supports of individual items to generate frequent 1-itemsets.
• Join pairs of frequent k-itemsets sharing common items in the first k-1 positions to create candidate (k+1)-itemsets.
• Check whether all k-subsets of each candidate itemset are present in the frequent k-itemsets, pruning those that fail.
• Determine candidate support by counting occurrences in the transaction database and retaining those meeting minimum support.

Advanced Counting and Summarization

Enumeration trees provide a hierarchical, non-repetitive lexicographic representation of itemsets. This unifies prefix-based and suffix-based pattern mining algorithms. An enumeration tree organizes itemsets such that children extend parents with items occurring later in lexicographic order. Almost all frequent pattern mining algorithms can be interpreted as variations of enumeration-tree growth.

Recursive suffix-based pattern growth methods use compact trie structures like FP-Trees to compress transaction databases and eliminate explicit candidate generation. FP-growth builds a prefix tree where paths represent transactions with occurrence counts. It extracts conditional FP-trees for suffixes. Mathematically, its recursion tree is structurally identical to a reverse-lexicographic enumeration tree.

You build an FP-growth model by following these precise actions:

• Remove infrequent items from the database and order remaining items by decreasing support.
• Insert transactions successively into a trie structure, incrementing overlapping prefix counts and creating new paths for non-overlapping portions.
• Construct conditional FP-trees for each item by chasing pointer threads, adjusting node counts upwards, and removing infrequent items.
• Extract frequent patterns directly when all nodes in a conditional FP-tree lie on a single path.

2. Data Classification

Classification builds supervised predictive models from labeled training data to estimate class labels for unseen instances using diverse algorithmic paradigms.

Unlike clustering which groups unlabeled data by similarity, classification learns user-defined group structures from example data. The process has two phases. A training phase builds a summary mathematical model of the labeled groups. A testing phase determines the class labels or numerical scores of unseen test instances.

Applications include customer target marketing where demographic profiles predict product interest, and medical disease management where patient test features predict treatment outcomes.

Feature selection removes irrelevant or redundant variables before classification using filter, wrapper, or embedded models. Filter models evaluate features using crisp mathematical criteria independent of the classifier. Wrapper models evaluate feature subsets by testing them within a specific classification algorithm. Embedded models isolate relevant features directly from the internal solution or weights of a classification model.

Decision trees build a hierarchical, top-down tree structure of split criteria on feature variables. This partitions training data and minimizes class mixing at the leaves. Splits can be univariate using a single attribute or multivariate using multiple attributes. To prevent overfitting from noisy training data, algorithms use post-pruning mechanisms or early stopping criteria. These include the minimum description length principle or a holdout validation set.

A charitable donation dataset uses age and salary features to split records and separate donors from nondonors in leaf nodes.

Rule-based classifiers utilize if-then rules matching antecedents to consequents. They offer greater flexibility than rigid decision tree hierarchies. Rules can be mutually exclusive and exhaustive like decision trees, or unordered and overlapping. The latter require rule ordering or conflict resolution. Algorithms like sequential covering iteratively learn one rule at a time and prune training data.

The Naive Bayes classifier is a generative probabilistic model. It applies Bayes theorem with the simplifying assumption of class-conditional feature independence. It estimates the posterior probability of a class given feature values by computing prior class probabilities and conditional feature probabilities. Laplacian smoothing is used to prevent zero-probability estimates caused by sparse training data.

A charitable organization solicits donations from a population where 30 percent have an age greater than 50, illustrating conditional probability estimation.

Logistic regression is a discriminative probabilistic linear classifier that models class-membership probabilities using a logistic function. It maps linear combinations of feature variables to probabilities between 0 and 1. Parameters are optimized via maximum likelihood estimation using gradient ascent methods since no closed-form solution exists.

Support Vector Machines construct maximum margin separating hyperplanes between binary classes to maximize generalization power on uncertain boundary regions. For linearly separable data, the hard-margin optimization minimizes the norm of the weight vector subject to margin constraints. For nonseparable data, soft-margin SVMs introduce slack variables and penalties like hinge loss. The kernel trick replaces explicit high-dimensional feature transformations with kernel similarity functions.

Neural networks simulate biological neural systems through computational units that adjust connection weights iteratively in response to prediction errors. The basic perceptron uses a single output layer for linear activation functions, updated via mistake-driven gradient descent. Multilayer feed-forward networks incorporate hidden layers. They can approximate arbitrary nonlinear functions using the backpropagation algorithm.

Instance-based learning classifiers are lazy learners that delay training until classification time by finding nearest neighbors among training examples. The dominant class label among the closest training instances is reported as the relevant class. This is often weighted by inverse distance. Distance metrics can be enhanced using the unsupervised Mahalanobis metric or supervised linear discriminant analysis to reshape neighborhoods.

Classifier evaluation uses rigorous methodologies and quantitative measures to test generalization accuracy, compare models, and tune parameters. Evaluation methodologies include holdout, cross-validation, and bootstrap sampling. Quantification metrics include unweighted accuracy, cost-sensitive accuracy, precision-recall curves, and Receiver Operating Characteristic curves.

A hypothetical dataset with 100 points from which 5 points belong to the positive class in the ranking illustration is used to rank instances and generate ROC and precision-recall curves for Algorithm A, Algorithm B, a random algorithm, and a perfect oracle using 10-fold cross validation.

Advanced Concepts and Scalability

Advanced architectures scale classifiers to massive repositories, handle imbalanced classes, incorporate unlabeled records, and combine predictions through ensemble techniques.

Binary classifiers like support vector machines can be adapted to multiclass problems using one-against-rest or one-against-one meta-algorithms. In the one-against-rest approach, $k$ models are built where each class is tested against all remaining classes combined. In the one-against-one approach, $k(k-1)/2$ models are built for every pair of classes. This can be computationally faster for kernel SVMs due to smaller training subsets.

Imbalanced data sets require modifying standard classification algorithms through example reweighting or resampling to maximize cost-weighted accuracy. When positive and negative examples are severely imbalanced, standard classifiers default to the majority class. Using a cost matrix or reweighting examples and undersampling normal classes ensures that the higher cost of misclassifying rare classes is properly accounted for during model training.

In credit card activity data, a 1:99 rare to normal ratio in credit card fraud detection example shows that 99% of points may be normal while only 1% are fraudulent. This causes nearest-neighbor classifiers with $k=100$ to misclassify rare instances if unweighted.

Large-scale decision tree construction requires disk-optimized algorithms like RainForest and BOAT to minimize memory and input-output bottlenecks. RainForest uses AVC-sets to store count statistics of distinct attribute values for each node in main memory. This avoids multidimensional data scans. BOAT uses bootstrapped samples to construct trees in parallel, imposing confidence intervals on splits. It converts them to crisp criteria in just 2 scans over the database required by the BOAT algorithm.

Support vector machines scale to large data sets by optimizing working subsets iteratively and pruning non-support vectors. SVMLight addresses quadratic memory scaling by optimizing small working sets iteratively rather than loading the entire kernel matrix. It also uses shrinking heuristics to discard training examples that do not lie near the decision boundary.

Numeric class prediction uses linear regression, generalized linear models, and regression trees to minimize squared error. They prevent overfitting through regularization. Linear regression minimizes the squared error objective function, which can be solved via the Moore-Penrose pseudoinverse. Overfitting is prevented using Tikhonov regularization with an L2-penalty or Lasso with an L1-penalty. Generalized linear models extend this to exponential distributions using link functions, and regression trees apply local linear models within leaf partitions to achieve an R-statistic ranging from 0 to 1 in linear models.

Unlabeled data improves classification accuracy by revealing underlying manifold structures and feature joint distributions where labeled instances are sparse. Methods such as self-training, co-training across disjoint feature sets, semisupervised Bayes classification with EM, transductive support vector machines, and graph-based learning leverage unlabeled records. These ensure label distributions vary smoothly over dense data regions.

In document classification, unlabeled text documents help associate rare words like Einstein with the Science category through co-occurrence with common words like Physics.

Active learning queries an oracle for labels of the most informative instances to maximize classification accuracy at a fixed acquisition cost. Query systems select informative instances using heterogeneity-based models like uncertainty sampling and query-by-committee. They also use performance-based models like expected error reduction, or representativeness-based models that weight dense space regions to avoid outliers.

Ensemble methods combine multiple classifiers to reduce bias, variance, or both, resulting in more robust predictions than individual models. Bagging and random forests reduce variance through bootstrapping and randomized feature selection. Boosting iteratively reweights misclassified instances to reduce bias, creating strong learners from weak ones. Stacking trains a second-level combiner classifier on the predictions of first-level models.

3. Cluster Analysis

Clustering partitions unlabelled data into cohesive groups using similarity or density criteria across representative, hierarchical, and advanced models.

Feature selection for clustering aims to remove noisy, uninformative attributes without the benefit of external class labels. It uses either filter models or wrapper models. Filter models evaluate feature subsets independently during a preprocessing phase. Wrapper models integrate a clustering algorithm directly with an internal cluster validity criterion.

• Filter models: Associate a score with each feature using a similarity-based criterion and remove data points or attributes that do not meet the required score.
• Wrapper models step 1: Use a clustering algorithm on the current subset of selected features to fix cluster labels for the data points.
• Wrapper models step 2: Use any supervised criterion to quantify the quality of individual features with respect to the labels, and select the top-k features.

Representative-based algorithms partition data by discovering a high-quality set of representatives. They iteratively alternate between assigning points to the closest representative and optimizing the representative location. These algorithms assume the number of clusters $k$ is specified by the user. They minimize the sum of distances from data points to their closest representatives. Variations include $k$-means, $k$-medians, and $k$-medoids.

Using an initial random seed set that poorly splits natural clusters, the $k$-representatives approach successfully converges to a reasonable clustering within 10 iterations as representatives drift toward distinct natural clusters.

• (Assign step) Assign each data point to its closest representative in the representative set using the chosen distance function.
• (Optimize step) Determine the optimal representative for each cluster that minimizes its local objective function.

Hierarchical clustering algorithms organize data into a multilevel tree structure. They offer multigranularity insights through either bottom-up agglomerative merging or top-down divisive partitioning. Bottom-up methods successively merge the closest pairs of clusters based on metrics like single linkage or Ward's method. Top-down methods recursively split nodes using a flat clustering subroutine.

The Open Directory Project organizes Web pages into a hierarchy where the top level divides into broad topics like arts and science, and science further divides into biology and physics.

• Bottom-up agglomerative step: Start with individual data points in separate clusters, find the closest pair of clusters based on the merging criterion, and merge them into a single cluster while updating the distance matrix.
• Top-down divisive step: Initialize the tree at the root node containing all data points, and recursively split nodes using a flat-clustering algorithm until a target height or minimum node size is achieved.

Probabilistic model-based clustering assumes data is generated from a mixture of probability distributions. It uses soft assignment probabilities optimized via the expectation-maximization algorithm. Density-based algorithms identify fine-grained dense building blocks to construct clusters of arbitrary shape without requiring the number of clusters as a-priori input. Graph-based clustering transforms data objects of any type into a similarity neighborhood graph and applies spectral clustering. Non-negative matrix factorization embeds sparse data matrices into a lower-dimensional latent basis system.

Scalability and Advanced Clustering

Categorical data clustering requires adapting standard representative-based algorithms by using probability histograms or modes instead of numerical averages. High-dimensional clustering uses subspace or projected clustering methods to handle irrelevant features and the concentration of distances. Semisupervised clustering leverages external guidance through pointwise supervision or pairwise constraints to align unsupervised clusters with application-specific goals. Cluster ensembles combine multiple alternative clustering models into a single consensus clustering.

4. Outlier Analysis

An outlier is formally defined as an observation that deviates so heavily from other observations that it raises suspicions of being generated by a different underlying mechanism. Outliers represent a complementary concept to clusters. While clustering finds groups of similar data points, outlier analysis identifies isolated points. They are also known as abnormalities, discordants, deviants, or anomalies. They have critical applications in data cleaning, credit card fraud detection, and network intrusion detection.

Outlier detection identifies rare data anomalies that deviate significantly from expected behavioral norms using statistical, distance, and density models.

Univariate and Distance Methods

Extreme value analysis isolates data points located at the statistical tails of a probability distribution, which corresponds to the outskirts of the data space. Univariate extreme values are evaluated using z-numbers and tail confidence tests on a normal or student t-distribution. Absolute z-values greater than 3 correspond to cumulative tail areas under 0.01 percent. For multivariate data, the Mahalanobis distance to the data mean serves as an extreme-value score, modeling the probability distribution as a single Gaussian cluster. Probabilistic mixture models generalize multivariate extreme value analysis by assuming data is generated from a mixture of multiple distributions. They define outliers as points with low likelihood fit.

Distance-based outlier detection evaluates an object's outlier score using its distance to its $k$-nearest neighbor. This provides a finer granularity than global clustering models. Using the $k$-nearest neighbor distance allows algorithms to distinguish between ambient noise and truly isolated anomalies because ambient noise exhibits a lower $k$-nearest neighbor distance. To manage high computational complexity, optimization strategies include indexing structures and pruning methods like the early termination trick.

You implement this distance pruning using a structured sequence:

• Pick a sample of size $s$ from the database and compute all pairwise distances between the sample and the database.
• Determine the top $k$-ranked outlier in the sample to establish a lower bound on the $k$-ranked outlier score for the entire database.
• Compute upper bounds on the $k$-nearest neighbor distance for remaining points based on the sample.
• Exclude points from further consideration if their upper bound falls below the established lower bound.
• Apply the $k$-nearest neighbor approach to the remaining candidate set.

The Local Outlier Factor method adjusts for variations in local cluster density by normalizing an object's distance using the average point-specific distances in its locality. The instance-specific Mahalanobis distance adjusts to varying local cluster shapes and orientations by computing neighborhoods via an agglomerative single-linkage approach.

High-Dimensional Subspace Outliers

High-dimensional outlier detection requires subspace methods because irrelevant and noisy dimensions create masking and dilution effects that obscure anomalies in full-dimensional space. As dimensionality increases, outliers are often lost in low-dimensional projections because different anomalies manifest in disjoint subsets of dimensions. Subspace outlier detection associates an outlier with one or more specific subspaces where its abnormal behavior is exposed.

In a credit card fraud application, one customer anomaly is tracked via purchase location and frequency. Another is tracked via purchase size and timing. This means all features matter globally but only subsets matter locally.

Grid-based rare subspace exploration uses discretization and sparsity coefficients to locate low-density regions in lower-dimensional projections. Genetic algorithms are used for grid search in rare subspace exploration to navigate the combinatorial explosion of possible dimensions and combinations.

You explore rare subspaces using these grid steps:

• Discretize each attribute of the data into equidepth ranges.
• Construct grid cells of dimensionality $d$ by selecting intervals from different dimensions.
• Compute the sparsity coefficient for cubes using Eq. 9.5.
• Report data points containing abnormal sparse projections as outliers.

A 4-dimensional problem with ten ranges yields strings of length 4 where each position takes 11 possible values including the don't care symbol, such as *2*6. Random subspace sampling techniques like feature bagging repeatedly execute outlier detection algorithms on random subsets of features to improve robustness. Outlier ensemble methods combine scores from multiple component models, normalizations, and combination functions to protect against overfitting. Proper score normalization and combination functions like the maximum function are critical in outlier ensembles to successfully uncover well-hidden anomalies.

5. Mining Data Streams and Complex Domains

Advanced data mining extends foundational superproblems to handle continuous streams, text documents, time series, sequences, spatial coordinates, graphs, and web networks.

Data Streams and Text Mining

Data streams accumulate continuously, requiring specialized streaming frameworks because storing everything is unfeasible. Processing streams introduces the hard one-pass constraint, concept drift, load shedding, and massive-domain constraints involving enormous attribute value spaces. Transaction streams from credit cards, web click-streams, social streams from Twitter, and network traffic streams generate massive volumes.

Reservoir sampling maintains an unbiased sample from a stream without disk storage. To implement memoryless reservoir sampling:

• Include the first $s$ data points in the reservoir always.
• For the $n$-th incoming stream point, insert it into the reservoir with probability $s$ divided by $n$.
• If the newly incoming data point was inserted, eject one of the old data points in the reservoir at random.

Bloom filters provide a space-efficient binary bit array structure for probabilistic set-membership queries. You can execute these queries by performing specific operations:

• Initialize all bits in the bloom filter to 0.
• For each incoming stream element, apply the $k$ independent hash functions.
• Set the corresponding bits in the bloom filter to 1.
• To check membership, compute hash functions and check if all corresponding bit entries are 1.

Count-min sketches track frequency counts in massive-domain streams. You can query and update them using these practices:

• Initialize all entries in the $d$ numeric arrays of the count-min sketch to 0.
• For each incoming stream element, apply the $d$ hash functions to find the cell indices.
• Increment the selected cell in each numeric array by 1 or by the item's positive frequency.
• Retrieve frequency estimates by taking the minimum value across the corresponding array elements.

Text data requires a vector space representation using a bag-of-words model. Raw documents undergo stop word removal, stemming, and punctuation stripping.

Graphs, Web Data, and Privacy

Graphs model complex relationships, but matching them is computationally expensive. Ullman's algorithm and graph kernels help compute similarities and find frequent substructures.

Web data combines content information and usage data. Crawlers fetch pages using a frontier list and a seed set of URLs. You can guide this crawling process with concrete steps:

• Add the seed set of URLs to the frontier list.
• Pick one URL from the frontier list using the selection algorithm and delete it.
• Fetch the URL using the HTTP protocol.
• Store the fetched page in a local repository and extract the internal URLs.
• Add extracted URLs to the frontier list provided they have not been visited, tracked via a hash table.

Privacy preservation protects sensitive personal attributes during data publishing. Linkage attacks combine quasi-identifiers like age and ZIP code with public records. The $k$-anonymity model prevents re-identification by grouping records into equivalence classes. You can generate $k$-anonymous subsets using specific geometric cuts:

• Select a rectangular region containing at least $k$ data points where a valid split into $k$-anonymous subsets exists.
• Split the rectangular region along an axis-parallel dimension so that each resulting part contains at least $k$ data points.
• Update the set of rectangular regions until they cannot be split further without violating $k$-anonymity.

Conclusion

Data mining unites foundational algorithmic paradigms into a coherent framework for extracting actionable knowledge from complex repositories. You must integrate association analysis, classification, clustering, and outlier detection across specialized domains like text, graphs, and continuous streams. Success depends on careful data preparation, rigorous algorithm selection, and strict adherence to privacy preservation principles.

1. Clean and preprocess your raw data carefully to handle noise, missing values, and scaling issues before applying any algorithmic models.
2. Select your algorithmic paradigm by matching the data structure, labeled availability, and scalability requirements of your specific problem.
3. Incorporate privacy constraints into your workflow early to protect sensitive individual records through perturbation or anonymization techniques.
4. Evaluate your models continuously using domain-appropriate validation measures to ensure generalization and guard against overfitting.
5. Adapt your analytical pipelines to handle evolving data streams and complex relational structures like graphs and text corpora.

10 Key Ideas

1. Association pattern mining efficiently extracts frequently co-occurring itemsets and rules from transaction databases using support monotonicity and downward closure properties for search space pruning.
2. Classification builds supervised predictive models from labeled training data to estimate class labels for unseen instances using diverse algorithmic paradigms like decision trees, support vector machines, and neural networks.
3. Cluster analysis partitions unlabelled data into cohesive groups using similarity or density criteria across representative, hierarchical, and advanced models.
4. Outlier detection identifies rare data anomalies that deviate significantly from expected behavioral norms using statistical tail distributions, distance measurements, and local density models.
5. Specialized streaming frameworks handle continuous data streams by employing memoryless reservoir sampling, space-efficient bloom filters, and count-min sketches to bypass hard one-pass storage constraints.
6. Text data extraction represents unstructured documents using a bag-of-words vector space model after applying stop word removal, stemming, and punctuation stripping.
7. Time series analysis models temporal data points sequentially to extract underlying trends and patterns across continuous chronological intervals.
8. Sequential pattern mining identifies temporally ordered events and recurrent subsequences within chronological transaction databases.
9. Graph metrics and algorithms like Ullman's method and graph kernels quantify complex structural similarities and find frequent substructures across web networks and relational graphs.
10. Privacy preservation techniques protect sensitive personal attributes during data publishing by grouping records into equivalence classes using the $k$-anonymity model to prevent linkage attacks.