Data Transformations
Open in the Padhaiko app7.1 Attribute selection: Filter vs. wrapper methods
Real-world datasets often include dozens or thousands of attributes, many of which are irrelevant (uncorrelated with the target) or redundant (strongly correlated duplicates of other features). Irrelevant and redundant attributes slow down training, degrade -NN distance metrics, mislead Naive Bayes by double-counting correlated evidence, and cause decision trees to fragment data unnecessarily.
Attribute selection (feature selection) searches for a minimal, high-signal subset of attributes using one of two main paradigms:
| Aspect | Filter Methods | Wrapper Methods |
|---|---|---|
| Evaluation Criterion | Intrinsic data statistics (Information Gain, Chi-square, correlation, CFS merit) | Cross-validated accuracy/AUC of the actual target learning algorithm |
| Dependency on Learner | Model-agnostic (independent of classifier) | Tightly coupled to the chosen classifier |
| Computational Cost | Very fast ( or scoring) | Expensive (trains and cross-validates the model for every candidate subset) |
| Overfitting Risk | Low (does not tune subsets to a specific learner's quirks) | Higher (searching subsets via CV can overfit the validation folds) |
| Examples | Information Gain ranking, Correlation-based Feature Selection (CFS), ReliefF | Forward selection, Backward elimination, Best-first wrapper search |
Search Strategies and CFS Merit Score
Because evaluating all non-empty subsets is infeasible for large , subset evaluators (both CFS filters and wrappers) rely on heuristic search:
- Greedy Forward Selection: Start with and iteratively add the attribute improving the score most until no gain occurs.
- Greedy Backward Elimination: Start with all attributes and iteratively drop the least useful attribute.
- Best-First Search / Bidirectional Search: Maintain a priority queue of evaluated subsets to escape local optima.
In Correlation-based Feature Selection (CFS), a subset of attributes is scored by balancing feature–class relevance () against feature–feature redundancy ():
A subset scores highest when its features correlate strongly with the class yet minimally with one another.
7.2 Discretization: Unsupervised vs. entropy-based supervised discretization
Many data mining methods—such as Apriori association mining, discrete Naive Bayes, and decision tables—require nominal (categorical) attributes. Discretization transforms a continuous numeric attribute into a finite set of ordered intervals.
1. Unsupervised Discretization (Ignores Class Labels)
- Equal-Width (Equal-Interval) Binning: Partition into bins of equal width:
- Drawback: Severely distorted by outliers—one extreme value stretches one edge far out and crams almost all normal instances into a single bin.
- Equal-Frequency (Equal-Depth) Binning: Sort the instances and divide them into bins each containing approximately instances (adjusting boundaries if identical values cross a bin edge).
- Advantage: Robust to outliers and skewed distributions, though it still ignores where class labels actually change.
2. Entropy-Based Supervised Discretization (Fayyad & Irani)
Supervised discretization inspects the class labels to place split cutpoints precisely at boundaries that separate classes cleanly.
Fayyad–Irani Entropy-MDL Discretization
- Sort training instances by the numeric attribute and identify candidate boundary cutpoints where adjacent sorted instances have different class labels.
- Choose the cutpoint maximizing Information Gain:
- MDL Stopping Criterion: Recursively split and only if the Information Gain exceeds the MDL coding overhead:
where (, and are the numbers of distinct classes in ).
If an entire numeric attribute has no threshold passing the MDL check, it produces a single interval—effectively performing automatic feature elimination at the same time!
7.3 Projections: Principal Components Analysis (PCA) and random projections
Rather than dropping original columns (feature selection), projection methods transform the -dimensional input space into a lower-dimensional -dimensional subspace () by taking linear combinations of attributes.
1. Principal Components Analysis (PCA)
PCA finds orthogonal axes (principal components) that capture the maximum variance in the data:
- Center (and Standardize) the Data: Subtract each attribute's mean (and divide by its standard deviation when features have different physical units).
- Compute the Covariance Matrix: .
- Eigendecomposition: Solve , ordering eigenvalues with orthonormal eigenvectors .
- Project onto Top- Components: Retain the smallest capturing a target variance fraction (e.g., ):
- Limitations of PCA: PCA is unsupervised—the direction of largest variance is not guaranteed to align with class separation. Projected components are also linear blends of all original features, reducing interpretability.
2. Random Projections
When is huge (e.g., text vocabulary terms), computing a covariance matrix () is too slow. Random projection multiplies by a random matrix (whose entries are drawn from or sparse Achlioptas values with probabilities ).
Johnson–Lindenstrauss (JL) Lemma
For any set of points in and any distortion tolerance , there exists a linear map into dimensions (independent of !) such that all pairwise Euclidean distances are preserved within a factor of with high probability.
Random projections run in (even faster with sparse matrices), require no covariance matrix, and work directly on streaming high-dimensional data.
7.4 Sampling and data cleansing: Handling outliers and one-class learning
1. Sampling Techniques
- Simple Random Sampling: Draw instances uniformly without (or with) replacement.
- Stratified Sampling: Sample within each class independently so rare minority classes retain their exact proportions.
- Reservoir Sampling (for Data Streams): When stream length is unknown, maintain a fixed reservoir of size in one pass: store the first items, then for each , keep item with probability (replacing a uniformly random slot in the reservoir). Every item seen so far has exact probability of being in the sample!
- Class Imbalance Resampling: Oversample the minority class (e.g., SMOTE synthetic interpolation) or undersample the majority class strictly inside training sets.
2. Data Cleansing and Handling Outliers
Outliers arise either from measurement/entry errors (corrupted readings to be corrected or removed) or genuine rare phenomena (fraud, network intrusion, equipment fault to be detected).
- Univariate & Statistical Detection: Flag values with or outside Tukey's IQR fences .
- Multivariate & Distance/Density Detection: Flag points whose -NN distance or Local Outlier Factor (LOF) far exceeds neighbors' local density.
- Class-Noise Cleansing (Edited Nearest Neighbor / Ensemble Filtering): Remove training rows repeatedly misclassified by cross-validated learners (only after confirming they reflect labeling errors, never blindly dropping hard legitimate boundary cases).
3. One-Class Learning
In one-class classification (anomaly/novelty detection), training data contains instances of only the normal (target) class—negative examples are absent, too diverse to sample, or costly to label (e.g., all possible failure modes of a turbine).
- Density-Based One-Class Learning: Fit a Gaussian or Mixture Model to normal data and flag queries with .
- One-Class SVM / SVDD: Either separate normal data from the origin in kernel feature space with maximum margin (Schölkopf) or enclose normal data inside a minimum-radius hypersphere (Support Vector Data Description). Points outside the boundary are flagged as anomalies.
Worked Examples
CFS Merit Score and Equal-Width vs. Equal-Frequency Binning
- A feature subset of attributes has average feature–class correlation and average feature–feature intercorrelation . Compute its CFS Merit score.
- Discretize the sorted numeric readings below into bins using (a) equal-width binning and (b) equal-frequency binning:
Part 1 — Computing the CFS Merit Score ():
Part 2(a) — Equal-Width Binning (): Range is , so bin width is:
Intervals are :
- Bin 1 : ( items!)
- Bin 2 :
- Bin 3 :
- Bin 4 : ( outlier)
Notice how the single outlier leaves two bins completely empty.
Part 2(b) — Equal-Frequency Binning ( items per bin):
- Bin 1:
- Bin 2:
- Bin 3:
- Bin 4:
Equal-frequency binning keeps all bins populated despite the outlier .
- CFS Merit .
- Equal-width bins (): , , , . Equal-frequency bins ( items each): , , , .
PCA Variance Retention and IQR Outlier Detection
- Performing PCA on a -dimensional standardized dataset yields eigenvalues . How many principal components must be retained to preserve at least of total variance?
- A sensor attribute has quartiles and . Using Tukey's rule, compute the outlier fences and determine whether readings and are flagged as outliers.
Part 1 — Cumulative Explained Variance in PCA: Total variance .
- Retaining component: .
- Retaining components: .
Thus principal components suffice (reducing dimensionality by while keeping of variance).
Part 2 — Computing IQR and Outlier Fences:
Checking the two readings against :
- normal (not flagged).
- flagged as an upper outlier.
- Retain principal components (explaining of total variance).
- Fences are (); is normal, while is an outlier.
Exercises
Practice Exercises — Data Transformations
Compare filter and wrapper attribute selection methods. Why must attribute selection be nested inside cross-validation rather than run once on the full dataset beforehand?
Filter vs. Wrapper Methods: Filters score feature subsets using intrinsic data properties (entropy, correlation, CFS merit) independently of any classifier—making them fast and general, though oblivious to a specific learner's inductive bias. Wrappers embed the actual target classifier inside a cross-validation loop to evaluate subsets—often achieving higher tailored accuracy, at much higher computational cost and higher risk of overfitting the validation folds.
Preventing Data Leakage: If attribute selection scans the entire dataset including test instances before splitting into CV folds, features that happen to correlate with test labels by chance are selected, leaking test information into the model and causing overly optimistic accuracy estimates.
Filters use fast, model-agnostic data metrics; wrappers use the target learner via CV for tailored accuracy at higher cost. Selection must run inside training folds only so test labels do not leak into feature choice.
Contrast unsupervised binning (equal-width / equal-frequency) with Fayyad–Irani entropy-based supervised discretization. Suppose a -instance sorted attribute X has values and labels . Evaluate Information Gain at the boundary and compare it with the MDL stopping threshold ().
Unsupervised vs. Supervised Discretization: Unsupervised binning ignores class labels and can group opposite classes into the same bin or split a homogeneous class across bins. Supervised entropy-based discretization inspects class labels, picks boundary cutpoints maximizing Information Gain, and stops only when further splits fail an MDL significance bound.
Evaluating Split ():
- .
- Both (all ) and (all ) are pure, so .
- .
- MDL threshold:
Since , the split at is accepted.
Unsupervised binning ignores labels; Fayyad–Irani finds pure class boundaries and prunes via MDL. At , , so the split is accepted.
Compare Principal Components Analysis (PCA) and Random Projections in terms of mathematical mechanism, computational complexity, and preservation of pairwise distances vs. variance.
PCA vs. Random Projections:
- PCA: Computes the covariance matrix and extracts its top- orthonormal eigenvectors, capturing maximum variance in time. It is data-dependent and optimal for linear reconstruction error, though computationally heavy for huge and blind to class labels.
- Random Projections: Multiply data by a random matrix (Gaussian or sparse ) in time without inspecting the data distribution. By the Johnson–Lindenstrauss Lemma, preserves all pairwise Euclidean distances within regardless of , making it ideal for ultra-high-dimensional text or streaming vectors.
PCA computes data-dependent orthogonal eigenvectors maximizing variance (), whereas random projections use a data-independent random matrix () guaranteed by the Johnson–Lindenstrauss Lemma to preserve pairwise distances in dimensions.
Describe reservoir sampling for streaming datasets of unknown length. If a reservoir maintains items from a stream, what is the acceptance probability of the arriving item and the arriving item, and what is each seen item's overall probability of residing in the reservoir after items?
Reservoir Sampling Algorithm: Store the first stream items directly in the reservoir. For every subsequent item , generate a random integer ; if (probability ), replace reservoir slot with item , otherwise discard item .
Acceptance and Final Inclusion Probabilities ():
- Acceptance probability at : ().
- Acceptance probability at : ().
- By induction, after items have passed, every single item has an exact uniform probability of being in the reservoir.
Reservoir sampling fills slots and accepts item with probability into a random slot. For , acceptance probabilities are at and at , giving every item a uniform inclusion probability after items.
What is one-class learning, when is it preferred over binary classification, and how do density estimation and One-Class SVM (SVDD) solve it?
Concept and Motivation of One-Class Learning: One-class learning trains a model using examples from only a single target ("normal") class, without requiring representative negative examples. It is preferred in domains like machine fault detection, zero-day intrusion detection, or biometric verification where abnormal states are rare, unknown in advance, or too diverse to sample fairly.
Two Solution Approaches:
- Density Estimation: Fit a probability distribution (e.g., Gaussian or GMM) to normal training data and flag test instances whose density falls below a threshold.
- One-Class SVM / SVDD: Map normal points via a kernel and either push a maximum-margin hyperplane away from the origin or fit a minimal-volume hypersphere around the normal instances; any query falling outside the learned boundary is classified as an anomaly.
One-class learning models only normal instances when negative anomalies are absent or unrepresentative. It is solved via density thresholding (flagging low- queries) or One-Class SVM / SVDD (bounding normal points with a margin hyperplane or minimal hypersphere).