Data transformation: normalisation, discretisation, sampling and compression

Data preprocessing turns raw records into data that analysis and learning can use. It has four classic stages:

1. cleaning: missing values, noise and outliers;
2. integration: merging sources and removing redundancy;
3. transformation: normalisation, discretisation and encoding;
4. reduction: sampling, dimensionality reduction and compression.

Exam point. "Normalisation" here means rescaling attribute values. It is unrelated to database normal forms (1NF, 2NF, …).

Normalisation (feature scaling)

Algorithms that use distances (k-NN, k-means, SVM) or gradient descent are distorted when attributes have very different ranges. Rescaling fixes this.

Running data: 200, 300, 400, 600, 1000.

Min–max normalisation

$v' = \frac{v - \min}{\max - \min}\,(\text{new\_max} - \text{new\_min}) + \text{new\_min}.$

• To $[0, 1]$: $(v - 200)/800$ gives 0, 0.125, 0.25, 0.5, 1.
• To $[-1, 1]$, the value 600 becomes $0.5 \times 2 - 1 = 0$.

Facts.

• It keeps the order and the relative distances.
• A single outlier squeezes all the other values together.
• New data outside the old range maps outside $[0, 1]$.

z-score standardisation

$v' = \frac{v - \bar v}{\sigma}.$

• The mean is $2500/5 = 500$, and the deviations are $-300, -200, -100, 100, 500$.
• The population variance is $\frac{400{,}000}{5} = 80{,}000$, so $\sigma \approx 282.8$.
• So 1000 becomes $\frac{500}{282.8} \approx 1.77$, and 200 becomes $\approx -1.06$.

The result has mean 0 and SD 1. It suits roughly normal data and handles outliers better than min–max. A robust variant uses the median and the IQR instead.

Decimal scaling

$v' = v / 10^j$, with $j$ the smallest integer such that $\max\lvert v'\rvert < 1$. Here $\max = 1000$, so $j = 4$, and the values become 0.02, 0.03, 0.04, 0.06 and 0.1.

Other transforms

• Log transform $\log(1 + v)$ tames right-skewed data such as incomes or counts.
• Unit-length scaling $x / \lVert x\rVert$ is used for text vectors, before cosine similarity.

Exam trap. Compute the scaling parameters (min, max, mean, SD) on the training data only, then apply the same parameters to the test data. Computing them on all the data leaks information.

Discretisation (binning)

Discretisation turns a continuous attribute into intervals or categories. It reduces noise and is needed by some algorithms, such as basic ID3 and naive Bayes on counts. It also makes rules easier to read.

Running data (sorted): 5, 7, 8, 12, 15, 18, 20, 22, 23, 30, 31, 35.

Equal-width binning

Split the range into $k$ intervals of equal width $w = (\max - \min)/k$. With $k = 3$, $w = 10$:

• $[5, 15)$: {5, 7, 8, 12}
• $[15, 25)$: {15, 18, 20, 22, 23}
• $[25, 35]$: {30, 31, 35}

It is simple, but skewed data leaves some bins nearly empty, and outliers waste bins.

Equal-frequency (equal-depth) binning

Put the same number of values in each bin. With 3 bins of 4:

• {5, 7, 8, 12}
• {15, 18, 20, 22}
• {23, 30, 31, 35}