Data Types and Data Transformation — Normalization, Discretization, Sampling, Compression

Attribute types (nominal, binary, ordinal, interval, ratio; discrete vs continuous), data quality issues, and the preprocessing steps the syllabus names — normalisation (min-max, z-score, decimal scaling), smoothing and binning, discretisation (equal-width, equal-frequency, entropy-based, concept hierarchies), sampling (simple random, stratified, cluster, systematic, reservoir) and data reduction and compression (lossless vs lossy, dimensionality and numerosity reduction).

Real data is messy: values on different scales, continuous attributes where categories are needed, too many rows or columns, noise and missing entries. Preprocessing turns raw data into a form that mining and machine learning algorithms can use.

Data types (attribute types)

Type	Meaning	Examples	Meaningful operations
Nominal (categorical)	names/labels, no order	colour, PIN code, blood group	$=$ , $\ne$ , mode
Binary	two states; symmetric or asymmetric	gender, test positive/negative	as nominal
Ordinal	ordered categories, unknown gaps	rating, grade, size S/M/L	$<$ , median, percentiles
Interval	numeric, equal units, no true zero	°C, calendar year	$+$ , $-$ , mean, s.d.
Ratio	numeric with a true zero	height, income, kelvin, counts	all, including ratios

Discrete attributes take countable values (counts, categories); continuous ones take real values.
In databases, the physical data types are INT, DECIMAL(p, s), FLOAT, CHAR(n), VARCHAR(n), DATE, TIMESTAMP, BOOLEAN, BLOB — choosing exact DECIMAL for money avoids floating-point error.

Data quality and cleaning

Missing values: ignore the tuple, fill with a constant, the mean/median (or class-conditional mean), or a predicted value.
Noise: smooth by binning, regression or clustering; detect outliers with z-scores ( $\lvert z\rvert > 3$ ), the IQR rule ( $< Q_1 - 1.5\,\text{IQR}$ or $> Q_3 + 1.5\,\text{IQR}$ ) or clustering.
Inconsistencies and duplicates: reconcile codes and units, deduplicate records.

Normalisation (feature scaling)

Distance-based methods (k-NN, k-means, SVM) and gradient descent are distorted when attributes have different scales.

Method	Formula	Result
Min-max	$v' = \dfrac{v - \min_A}{\max_A - \min_A}(\text{new\_max} - \text{new\_min}) + \text{new\_min}$	range $[0, 1]$ (or any target); sensitive to outliers; out-of-range values for new data
Z-score	$v' = \dfrac{v - \bar A}{\sigma_A}$	mean 0, s.d. 1; preferable with outliers or unknown range
Decimal scaling	$v' = v / 10^j$ , smallest $j$ with $\max\lvert v'\rvert < 1$	shifts the decimal point
Robust scaling	$(v - \text{median})/\text{IQR}$	resistant to outliers

Other transformations: smoothing, aggregation (daily → monthly sales), attribute construction (area from length × width), log transforms for skewed data, one-hot encoding of nominal attributes.

Discretisation

Convert a continuous attribute into intervals (labels), reducing noise and enabling algorithms that need categorical inputs.

Method	How	Supervised?
Equal-width binning	$k$ intervals of width $(\max - \min)/k$	no
Equal-frequency (equal-depth) binning	each bin gets about $n/k$ values	no
Clustering-based	cluster values; clusters become intervals	no
Entropy-based	choose split points maximising information gain about the class	yes
ChiMerge	merge adjacent intervals whose class distributions are similar ( $\chi^2$ test)	yes
Histogram analysis	split at valleys of the histogram	no

Smoothing by binning: after binning, replace values by the bin mean, bin median, or the nearer bin boundary.

Concept hierarchies generalise discretised or categorical values to higher levels (street < city < state < country; age → young/middle-aged/senior) and are central to data warehouses — see data warehousing.

Sampling

Method	Description	When useful
SRSWOR	simple random sample without replacement	default
SRSWR	with replacement (an item can be picked twice)	bootstrap
Stratified	partition into strata (e.g. classes), sample each proportionally	skewed/imbalanced data
Cluster	sample whole groups (pages, households)	when data is naturally grouped
Systematic	every $k$ -th record after a random start	ordered lists, simple; beware periodicity
Reservoir	uniform sample of $k$ from a stream of unknown length in one pass	streams, big data

Python

import random

def reservoir(stream, k):
    sample = []
    for i, x in enumerate(stream):        # i = 0, 1, 2, ...
        if i < k:
            sample.append(x)
        else:
            j = random.randint(0, i)      # inclusive
            if j < k:
                sample[j] = x             # keep x with probability k/(i+1)
    return sample

Every item ends up in the sample with probability $k/n$ . Sampling cost scales with the sample size, not the data size — the key to mining very large data sets.

Data reduction and compression

Dimensionality reduction (fewer attributes):

feature selection (filter, wrapper, embedded methods);
feature extraction: PCA, wavelet transforms, random projections — see PCA.

Numerosity reduction (fewer or smaller data representations):

parametric: regression or log-linear models store only parameters;
non-parametric: histograms, clustering (store centroids), sampling, data cubes (pre-aggregation).

Compression:

Lossless (exact reconstruction)	Lossy (approximate)
run-length encoding, Huffman coding, LZ77/gzip, dictionary encoding	truncated PCA/SVD, wavelet thresholding, JPEG, quantisation

Columnar databases combine dictionary encoding, run-length encoding of sorted columns and bit-packing to compress analytical data many-fold.