PadhaikoAll subjects

Data Transformations

Data Mining (ENCT 435)

Open in the Padhaiko app

7.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:

AspectFilter MethodsWrapper Methods
Evaluation CriterionIntrinsic data statistics (Information Gain, Chi-square, correlation, CFS merit)Cross-validated accuracy/AUC of the actual target learning algorithm
Dependency on LearnerModel-agnostic (independent of classifier)Tightly coupled to the chosen classifier
Computational CostVery fast ( or scoring)Expensive (trains and cross-validates the model for every candidate subset)
Overfitting RiskLow (does not tune subsets to a specific learner's quirks)Higher (searching subsets via CV can overfit the validation folds)
ExamplesInformation Gain ranking, Correlation-based Feature Selection (CFS), ReliefFForward 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:

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)

  1. Equal-Width (Equal-Interval) Binning: Partition into bins of equal width:
  1. 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.

Definition

Fayyad–Irani Entropy-MDL Discretization

  1. Sort training instances by the numeric attribute and identify candidate boundary cutpoints where adjacent sorted instances have different class labels.
  2. Choose the cutpoint maximizing Information Gain:
  1. 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:

  1. Center (and Standardize) the Data: Subtract each attribute's mean (and divide by its standard deviation when features have different physical units).
  2. Compute the Covariance Matrix: .
  3. Eigendecomposition: Solve , ordering eigenvalues with orthonormal eigenvectors .
  4. Project onto Top- Components: Retain the smallest capturing a target variance fraction (e.g., ):

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 ).

Theorem

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

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).

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).


Worked Examples

Example 1

CFS Merit Score and Equal-Width vs. Equal-Frequency Binning (6 marks)

  1. A feature subset of attributes has average feature–class correlation and average feature–feature intercorrelation . Compute its CFS Merit score.
  2. 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 .

Answer:
  1. CFS Merit .
  2. Equal-width bins (): , , , . Equal-frequency bins ( items each): , , , .
Example 2

PCA Variance Retention and IQR Outlier Detection (6 marks)

  1. Performing PCA on a -dimensional standardized dataset yields eigenvalues . How many principal components must be retained to preserve at least of total variance?
  2. 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.
Answer:
  1. Retain principal components (explaining of total variance).
  2. Fences are (); is normal, while is an outlier.

Exercises

Practice Exercises — Data Transformations

Question 1

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.

Answer:

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.

Question 2

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.

Answer:

Unsupervised binning ignores labels; Fayyad–Irani finds pure class boundaries and prunes via MDL. At , , so the split is accepted.

Question 3

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.
Answer:

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.

Question 4

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.
Answer:

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.

Question 5

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:

  1. 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.
  2. 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.
Answer:

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).

← Implementations: Real Machine Learning Schemes (part 2: 6.3–6.4)Moving On: Applications and Beyond →