GATE DA

Data types and data transformation

Normalisation, discretisation, sampling and compression

This topic covers how attribute values are classified (nominal, ordinal, interval, ratio; discrete or continuous) and how raw data is prepared for analysis: rescaling (normalisation), grouping into bins (discretisation), drawing a subset (sampling) and shrinking (compression and reduction). Most calculations here are short — scale a value, form and smooth bins, find a sampling probability or allocation, size a code — and each depends on using the exact formula and stating its convention.

1 previous-year question · 1 solved · 7 practice questions

Data types: the four measurement scales

An attribute is classified in two independent ways. By measurement scale it is nominal, ordinal, interval or ratio. By value set it is discrete (finite or countably infinite set of values, such as counts or categories) or continuous (any real value in a range, such as length). Each scale allows every operation of the one before it plus more, so the scales are nested.

Scale	Meaningful operations	Typical summary	Example
Nominal	equal or not equal	mode	blood group, postal code, colour
Ordinal	equal, order (<, >)	mode, median	grade A/B/C, size S/M/L/XL
Interval	equal, order, differences (+, -)	mode, median, mean, standard deviation	temperature in Celsius, calendar year
Ratio	equal, order, differences, ratios (x, /)	all, including geometric mean	length, mass, age, temperature in kelvin, a count

The deciding feature of ratio data is a true zero: zero means none of the quantity, so 40 kg is twice 20 kg. Celsius has an arbitrary zero, so 40 degrees Celsius is not twice as hot as 20 degrees; the scale is interval. Differences are meaningful on an interval scale, ratios are not.

Quick classification procedure

Values are only labels with no order: nominal.
Values have an order but gaps between them are not meaningful (grades, ratings): ordinal.
Gaps are equal and meaningful but zero is arbitrary: interval.
Zero means absence and ratios make sense: ratio.
Separately: can the values be listed one by one (discrete) or do they fill an interval (continuous)?

EXAM TIP

A numeric-looking attribute is not automatically interval or ratio. A postal code or a roll number is nominal, and a 1-to-5 satisfaction rating is ordinal. Also, a count (number of items) is discrete but ratio, and a binary attribute with two labels is nominal (symmetric or asymmetric depending on whether both outcomes are equally important).

Normalisation: rescaling attribute values

Here normalisation means data transformation to a common scale, not the database normal forms of schema design. It is applied to numeric attributes so that an attribute measured in large units (income) does not dominate distance computations over one measured in small units (age). Three methods are standard. In all of them below, $v$ is an original value of the attribute and $v^{'}$ the transformed one; $min$ , $max$ , $\overset{x}{ˉ}$ and $σ$ are computed from the attribute's values in the data.

MIN-MAX NORMALISATION TO [NEW_MIN, NEW_MAX]

v^{'} = new_{m i n} + \frac{v - min}{max - min} (new_{m a x} - new_{m i n})

Linear map of the observed range onto the target range; for [0,1] it reduces to (v - min)/(max - min). Preserves the shape of the distribution and the order of values. Undefined when max = min (all values equal).

Z-SCORE NORMALISATION

v^{'} = \frac{v - x ˉ}{σ}

Result has mean 0 and standard deviation 1 (under the same convention for sigma). Convention: use the population standard deviation (divide by n) unless the question says sample (divide by n - 1). Not bounded to a fixed range; undefined when sigma = 0. A variant divides by the mean absolute deviation s = (1/n) times the sum of |v - mean| instead of sigma; it is less affected by outliers because deviations are not squared.

DECIMAL SCALING

v^{'} = \frac{v}{1 0 ^{j}}, j = smallest non-negative integer with max ∣ v^{'} ∣ < 1; j = ⌊ lo g_{10} max ∣ v ∣⌋ + 1 if max ∣ v ∣ \geq 1

Moves the decimal point; j is fixed by the value of largest absolute magnitude. Result lies strictly inside (-1, 1). Examples: max|v| = 986 gives j = 3; max|v| = 1000 gives j = 4.

Method	Output range	Affected by outliers?	Keeps order?
Min-max	fixed (for example [0,1])	strongly: one extreme value squeezes the rest into a small part of the range	yes
Z-score	unbounded	yes: an outlier shifts the mean and inflates sigma, but the other values are not forced into a fixed interval	yes
Decimal scaling	(-1, 1)	only through the largest absolute value	yes

WORKED EXAMPLE

The values 2, 4, 4, 4, 5, 5, 7, 9 are to be normalised. (a) Min-max to [0,1] for the value 7. (b) Z-score for the value 9 using the population standard deviation.

Solution

Min-max: min = 2, max = 9, so $v^{'} = (7 - 2) / (9 - 2) = 5/7 \approx 0.714$ .
Mean = (2+4+4+4+5+5+7+9)/8 = 40/8 = 5.
Squared deviations: 9, 1, 1, 1, 0, 0, 4, 16, which sum to 32.
Population variance = 32/8 = 4, so $σ = 2$ .
Z-score of 9 = (9 - 5)/2 = 2. With the sample sd the value would be $4/ 32/7 \approx 1.87$ .

Answer: (a) 5/7, about 0.714. (b) 2 (population sd); about 1.87 if the sample sd is specified.

EXAM TIP

Min-max with a new value outside the original [min, max] gives a result outside the target range (an out-of-bounds error). Decimal scaling needs max|v'| strictly less than 1: if the largest absolute value is 1000, then j = 4 (giving 0.1), not 3 (giving exactly 1).

Discretisation: converting numeric values into bins

Discretisation replaces a continuous or finely valued attribute by a small number of intervals (bins), each of which may carry a label. It reduces data size and prepares data for methods that need categorical input. The two simple unsupervised methods are equal-width and equal-frequency binning, with $k$ bins chosen in advance.

EQUAL-WIDTH BINNING

w = \frac{max - min}{k}, bin i = [min + (i - 1) w, min + i w)

Bins have the same width and usually unequal counts. Convention here: left-closed, right-open, with the last bin closed so the maximum belongs to it.

EQUAL-FREQUENCY (EQUAL-DEPTH) BINNING

depth = \frac{n}{k}

Sort the data and put n/k consecutive values in each bin; widths differ. If k does not divide n, bin sizes are floor(n/k) or ceil(n/k) and the question must say which bins take the extra values. Tied values may need to share a bin.

Smoothing a binned attribute

Smoothing by bin means: replace every value in a bin by the mean of that bin.
Smoothing by bin medians: replace by the bin median.
Smoothing by bin boundaries: replace each value by the nearer of the bin's minimum and maximum; a value exactly midway goes to either (state the rule if it matters).

WORKED EXAMPLE

Sorted data: 4, 8, 15, 21, 21, 24, 25, 28, 34. (a) Partition into 3 equal-frequency bins and smooth by bin means. (b) How many values fall in each of 3 equal-width bins? (c) Smooth the equal-frequency bins of (a) by bin boundaries.

Solution

Equal-frequency depth = 9/3 = 3: bins (4, 8, 15), (21, 21, 24), (25, 28, 34).
Bin means: 27/3 = 9, 66/3 = 22, 87/3 = 29, so the smoothed data is 9, 9, 9, 22, 22, 22, 29, 29, 29.
Equal width: w = (34 - 4)/3 = 10, giving [4,14), [14,24), [24,34].
4 and 8 are in bin 1; 15, 21, 21 are in bin 2 (24 is not below 24); 24, 25, 28, 34 are in bin 3.
Boundaries, bin 1 (min 4, max 15): 8 is 4 from 4 and 7 from 15, so it becomes 4: result 4, 4, 15.
Bin 2 (min 21, max 24): 21, 21, 24 are already boundaries.
Bin 3 (min 25, max 34): 28 is 3 from 25 and 6 from 34, so it becomes 25: result 25, 25, 34.

Answer: (a) 9, 9, 9, 22, 22, 22, 29, 29, 29. (b) 2, 3 and 4 values. (c) 4, 4, 15, 21, 21, 24, 25, 25, 34.

ENTROPY-BASED (SUPERVISED) SPLIT

Info_{T} (D) = \frac{∣ D _{1} ∣}{∣ D ∣} Entropy (D_{1}) + \frac{∣ D _{2} ∣}{∣ D ∣} Entropy (D_{2}), Entropy (D) = - i \sum p_{i} lo g_{2} p_{i}

D_1 and D_2 are the tuples with attribute value at most, and above, the candidate split point T; p_i is the fraction of a set in class i. Choose the T that minimises Info_T(D), which is the same as maximising the information gain Entropy(D) - Info_T(D). Apply recursively to each part until a stopping rule is met.

Other discretisation methods

Histogram analysis: the bins of an equal-width or equal-frequency histogram become the intervals.
Cluster analysis: values are grouped into clusters, and each cluster becomes an interval.
ChiMerge (supervised, bottom-up): start with each distinct value as its own interval and repeatedly merge the adjacent pair with the lowest chi-square value, that is, the pair whose class distributions are most alike.
Concept hierarchy: replace low-level values by higher-level concepts (age 23 to 'young'; city to state to country).

EXAM TIP

Outliers can distort equal-width bins: most values may fall into a few bins while others stay empty. Equal-frequency bins handle skew better. Always sort before binning by frequency, and always check whether a boundary value belongs to the lower or upper bin.

Sampling

Sampling chooses a subset of the $N$ tuples to work with, trading accuracy for speed. In a probability sample each tuple's chance of selection is known, which is what lets the sample be used to estimate quantities of the whole population.

Method	How it works	Use when
Simple random without replacement (SRSWOR)	draw n distinct tuples, every subset of size n equally likely	population fairly uniform
Simple random with replacement (SRSWR)	each draw is independent and uniform over all N tuples; a tuple may repeat	bootstrap resampling; analyses that assume independent draws
Stratified	split into non-overlapping strata, sample within every stratum	strata differ and small groups must not be missed
Cluster (one-stage)	pick whole clusters at random and keep all tuples in them	population is naturally grouped; cheaper to access
Systematic	take every k-th tuple from a random start	ordered list with no periodic pattern

INCLUSION PROBABILITY, SRSWOR

P (tuple in sample) = \frac{n}{N}, number of samples = (n N)

Sample of n distinct tuples from N, all subsets equally likely.

INCLUSION PROBABILITY, SRSWR

P (tuple appears at least once) = 1 - (1 - \frac{1}{N})^{n}

n independent draws, each tuple chosen with probability 1/N per draw; N^n ordered outcomes.

EXPECTED NUMBER OF DISTINCT TUPLES, SRSWR

E [distinct] = N [1 - (1 - \frac{1}{N})^{n}], n = N, N \to \infty : \frac{E [ distinct ]}{N} \to 1 - \frac{1}{e} \approx 0.632

By linearity of expectation over the N tuples. The limit is the bootstrap fact: a with-replacement sample of size N contains about 63.2% of the distinct tuples, and about 36.8% never appear.

PROPORTIONAL ALLOCATION IN STRATIFIED SAMPLING

n_{h} = n \cdot \frac{N _{h}}{N}

Stratum h of size N_h receives a share of the total sample n in proportion to its size; round so that the n_h sum to n.

SYSTEMATIC SAMPLING

k = \frac{N}{n}, sample = {r, r + k, r + 2 k, \dots}, r uniform in {1, \dots, k}

When N = nk exactly, every tuple has inclusion probability 1/k = n/N, but only k distinct samples are possible.

EXAM TIP

Under SRSWR the sample can contain duplicates, so a sample of size n has at most n distinct tuples. Cluster sampling selects groups, not individual tuples, so within a chosen cluster every tuple is taken; stratified sampling samples from every stratum.

Compression and data reduction

Data compression re-encodes data in fewer bits. It is lossless if the original can be rebuilt exactly (run-length encoding, Huffman coding, dictionary methods) and lossy if only an approximation can be rebuilt (quantisation, wavelet or transform coefficients with small terms dropped). Data reduction also includes dimensionality reduction (keep fewer attributes or components, as in principal components, which keeps the directions of largest variance) and numerosity reduction, which replaces the data by a smaller representation: parametric (a regression or log-linear model, storing only its parameters) or non-parametric (a histogram, clusters or a sample).

COMPRESSION RATIO

ratio = \frac{original size}{compressed size}

A ratio above 1 means the data shrank. Space saving = 1 - compressed/original.

FIXED-LENGTH CODE SIZE

bits per symbol = ⌈ lo g_{2} m ⌉

For an alphabet of m >= 2 distinct symbols. A Huffman code never needs more bits per symbol on average than this, and needs fewer for some unequal frequency distributions (not all: probabilities 0.3, 0.3, 0.2, 0.2 give Huffman lengths 2, 2, 2, 2).

AVERAGE CODE LENGTH AND THE ENTROPY BOUND

\overset{ˉ}{L} = i \sum p_{i} l_{i}, H = - i \sum p_{i} lo g_{2} p_{i}, H \leq \overset{ˉ}{L}_{Huffman} < H + 1

p_i is the probability (relative frequency) of symbol i and l_i its code length in bits. No lossless symbol-by-symbol prefix code averages below H; Huffman's code is optimal among them and reaches H exactly when every p_i is a power of 1/2.

WORKED EXAMPLE

A string of 50 characters over the 4 symbols A, B, C, D is stored with a fixed-length code. The same string is run-length encoded as 6 (symbol, count) pairs, each pair needing 2 bits for the symbol and 6 bits for the count. Find both sizes and the compression ratio.

Solution

Fixed length: $⌈ lo g_{2} 4 ⌉ = 2$ bits per symbol, so 50 x 2 = 100 bits.
Run-length: 6 pairs x (2 + 6) = 48 bits.
Ratio = $100/48 \approx 2.08$ .

Answer: 100 bits and 48 bits; ratio about 2.08.

WORKED EXAMPLE

Symbols A, B, C, D occur with probabilities 0.5, 0.25, 0.125, 0.125. Find the Huffman code lengths, the average code length and the entropy, and compare with a fixed-length code.

Solution

Merge the two smallest: C + D = 0.25. Then B + (CD) = 0.5. Then A + (BCD) = 1.
Code lengths: A 1, B 2, C 3, D 3.
Average length = 0.5(1) + 0.25(2) + 0.125(3) + 0.125(3) = 0.5 + 0.5 + 0.375 + 0.375 = 1.75 bits.
Entropy = 0.5(1) + 0.25(2) + 0.125(3) + 0.125(3) = 1.75 bits, because every probability is a power of 1/2.
Fixed length: $⌈ lo g_{2} 4 ⌉ = 2$ bits.

Answer: Lengths 1, 2, 3, 3; average 1.75 bits per symbol, equal to the entropy; the fixed-length code needs 2 bits.

EXAM TIP

Lossless compression never changes any value; lossy compression and discretisation both lose detail, but compression is a storage encoding while discretisation changes the values the analysis sees. Run-length encoding helps only where long runs of equal values exist (sorted or sparse columns).

PREVIOUS-YEAR QUESTIONS

1 question from the DA papers

Try each question first, then open the answer. We placed each question under a topic ourselves; the exam paper does not label topics.

See these papers in full: GATE DA 2024

GATE 2024 DA Q.27

GATE 2024 · DAQ.27 · 1 mark · MCQ

Let the minimum, maximum, mean and standard deviation values for the attribute income of data scientists be 46000, 170000, 96000, and 21000, respectively. The z-score normalized income value of 106000 is closest to which ONE of the following options?

(A)
0.217
(B)
0.476
(C)
0.623
(D)
2.304

Answer and solution

GATE 2024 DA Q.27: answer and solution

See the question in the paper

Tap to open full size

GATE 2024 DA Q.27: answer and solution

PRACTICE

7 questions to test yourself

PRACTICE 11 mark · NAT

The attribute Score has an observed minimum of 20 and maximum of 220. A value of 70 is rescaled by min-max normalisation to the range [-1, 1]. Find the rescaled value.

Answer and solution

Answer: $- 0.5$ (accepted range $\pm 0.001$ )

(70 - 20)/(220 - 20) = 50/200 = 0.25.
v' = -1 + 0.25 x (1 - (-1)) = -1 + 0.5 = -0.5.

PRACTICE 21 mark · MSQ

Which of the following attributes are measured on a ratio scale?

(A)
Temperature in kelvin
(B)
Temperature in Celsius
(C)
Length of a bolt in centimetres
(D)
Postal code of a customer

Answer and solution

Answer: (A), (C)

Kelvin has a true zero (absence of thermal energy), and length has a true zero, so ratios are meaningful: ratio scale.
Celsius has an arbitrary zero: interval.
Postal code is a label: nominal.

PRACTICE 32 marks · NAT

The data set 6, 8, 8, 8, 9, 9, 11, 13 is z-score normalised using the SAMPLE standard deviation (divisor n - 1). Find the sum of the squares of the eight normalised values.

Answer and solution

Answer: $7$ (accepted range $\pm 0.001$ )

Mean = 72/8 = 9.
Sum of squared deviations = 9 + 1 + 1 + 1 + 0 + 0 + 4 + 16 = 32.
Sample variance $s^{2} = 32/7$ .
Sum of $z^{2}$ = (sum of squared deviations)/ $s^{2}$ = 32/(32/7) = 7, which equals n - 1.

PRACTICE 42 marks · NAT

The sorted values 5, 7, 12, 14, 20, 22, 30, 36 are placed in 4 equal-frequency bins (two values per bin) and every value is replaced by the mean of its bin. Find the total squared error, the sum over all eight values of (original - smoothed)^2.

Answer and solution

Answer: $24$ (accepted range $\pm 0.001$ )

Bins: (5, 7), (12, 14), (20, 22), (30, 36) with means 6, 13, 21, 33.
Squared errors per bin: 1+1 = 2, 1+1 = 2, 1+1 = 2, 9+9 = 18.
Total = 2 + 2 + 2 + 18 = 24.

PRACTICE 52 marks · MCQ

A table has 10 tuples. A sample of size 3 is drawn by simple random sampling WITH replacement, each draw choosing one tuple uniformly and independently. What is the probability that a particular given tuple appears at least once in the sample?

(A)
0.300
(B)
0.271
(C)
0.729
(D)
0.100

Answer and solution

Answer: (B)

Probability the tuple is missed in one draw = 9/10.
Missed in all three independent draws = $0. 9^{3} = 0.729$ .
At least once = 1 - 0.729 = 0.271. (0.300 would be the answer for sampling without replacement, 3/10.)

PRACTICE 61 mark · MCQ

The values of an attribute range from -986 to 917. The attribute is normalised by decimal scaling, with j the smallest non-negative integer for which every transformed value has absolute value less than 1. What does the value -986 become?

(A)
-9.86
(B)
-0.986
(C)
-0.0986
(D)
-0.00986

Answer and solution

Answer: (B)

The largest absolute value is 986.
j = 2 gives 9.86, not below 1; j = 3 gives 0.986, below 1. So j = 3 (equivalently floor(log10 986) + 1 = 2 + 1 = 3).
-986 / 10^3 = -0.986.

PRACTICE 71 mark · NAT

A table of 2,000 tuples is divided into three strata of sizes 1,000, 600 and 400. A stratified sample of 50 tuples is drawn with proportional allocation. How many tuples are drawn from the stratum of size 600?

Answer and solution

Answer: $15$

$n_{h} = n \cdot N_{h} / N = 50 \times 600/2000$ .
= 30000/2000 = 15. (The other strata get 25 and 10; 25 + 15 + 10 = 50, so no rounding is needed.)

OFFICIAL GATE 2027 SYLLABUS WORDING

Copied from the GATE 2027 syllabus; see all 2027 syllabi.

GATE DA

data types, data transformation such as normalization, discretization, sampling, compression

Preparing in Kolkata? IAE Academy's course for GATE DA.