Data Preprocessing

In Bin 1: [4, 8, 15], the boundaries are 4 and 15.

• 8 is closer to 4 than to 15.

• Resulting Bin: [4, 4, 15].

A teacher records study hours and exam scores for 30 students.
One student studied 2 hours but scored 95 (unusually high — maybe copied).
Another studied 8 hours but scored 20 (unusually low — maybe sick).

• Regression fits a line: $\text{Score} = 40 + 6 \times \text{Hours}$

• Both students deviate far from the line $\rightarrow$ flagged as noisy records

• Options: smooth them to their predicted value, or remove them entirely

A bank has 1 million transaction records.

• Clustering groups them into normal spending clusters:
  Groceries cluster, Rent cluster, Entertainment cluster

• A transaction of $50,000 at 3 AM falls far outside every cluster

• $\Rightarrow$ Flagged as an outlier — potential fraud or data entry error

Key insight: No rule was written manually — the data itself revealed what is “unusual.”

A student dataset has 10 attributes:
Math, Physics, Chemistry, Biology, History, Geography, English, CS, Economics, PE

• PCA applied $\rightarrow$ finds that the first 2 principal components explain 88% of total variance

• Data projected from 10 dimensions $\rightarrow$ 2 dimensions

• PC$_1$ may represent “Science aptitude”; PC$_2$ may represent “Humanities aptitude”

• Remaining 8 components discarded — small information loss, major storage gain

• Clustering and classification now run on 2 features instead of 10

Dataset has attributes: {Age, Income, ZipCode, Gender, Purchase_History, WebClicks}
Task: Predict whether a customer will buy.

• Step 1: Test each alone $\rightarrow$ Purchase_History gives best accuracy $\rightarrow$ selected

• Step 2: Add one more $\rightarrow$ Income improves accuracy $\rightarrow$ selected

• Step 3: Age adds marginal gain $\rightarrow$ selected

• Step 4: ZipCode, Gender, WebClicks add no improvement $\rightarrow$ stopped

• Final subset: {Purchase_History, Income, Age}

Same dataset: {Age, Income, ZipCode, Gender, Purchase_History, WebClicks}

• Step 1: Remove ZipCode $\rightarrow$ accuracy unchanged $\rightarrow$ eliminated

• Step 2: Remove Gender $\rightarrow$ accuracy unchanged $\rightarrow$ eliminated

• Step 3: Remove WebClicks $\rightarrow$ slight drop, but acceptable $\rightarrow$ eliminated

• Step 4: Removing any of {Age, Income, Purchase_History} causes significant drop $\rightarrow$ stop

• Final subset: {Age, Income, Purchase_History} — same result as forward selection

Dataset attributes: Age, Income, ZipCode, Gender, Purchase_History, WebClicks
Target: Will the customer buy? (Yes / No)
After building the decision tree on training data:

• Root split: Purchase_History — most informative attribute; splits data most cleanly

• Level 1: Income (left branch) and Age (right branch) — next most relevant

• Level 2: Income appears again under Age — still relevant in that context

• Final selected subset: {Purchase_History, Income, Age} — 3 of 6 attributes

• ZipCode, Gender, WebClicks were never chosen for any split — discarded as irrelevant

Imagine a bag with 10 coloured balls. You want to pick 3.

• SRSWR: Pick a Red ball $\to$ record it $\to$ put it back.
  Next turn, the same Red ball can be picked again. Bag always has 10 balls.

• SRSWOR: Pick a Red ball $\to$ keep it out.
  Now only 9 balls remain. That Red ball is gone forever from the pool.

A university has 1,000 students across three streams:

Result: The 100-student sample looks exactly like the full university — same proportions, smaller size.

You want to know if a giant pot of soup needs more salt. You taste 5 spoonfuls.

• Scenario A — Good Sample (Stirred):
  Stir the pot thoroughly first, then take spoons from different depths and sides.
  $\Rightarrow$ The 5 spoonfuls represent the whole pot accurately.

• Scenario B — Biased Sample (Unstirred):
  Take all 5 spoons from the top where salt has settled.
  $\Rightarrow$ You conclude the soup is too salty — but the bottom is bland.
  This is sampling bias.

• Scenario C — Too Small a Sample:
  Taste only 1 spoon from a 100-litre pot.
  $\Rightarrow$ High variance — one spoon may not be representative at all.

Lesson: A good sample must be both random (stirred) and large enough (5+ spoons).

A dataset has the location (lat, long) of 10,000 houses in a city.

• Clustering groups them into 5 city zones (North, South, East, West, Centre)

• Each zone is represented by its centroid — the average location

• Analysis now runs on 5 points instead of 10,000

• Patterns like “crime is high in the East zone” are still discoverable

Trade-off: Fine-grained detail within a zone is lost — only the zone-level pattern survives.

A dataset has 50,000 house sale records with (area $\to$ price).

• Fit a regression: $\text{Price} = 5000 + 3200 \times \text{Area (sq ft)}$

• Now store just two numbers: $\beta_0 = 5000$,\ $\beta_1 = 3200$

• For any new house: plug in area, get predicted price instantly

• 50,000 rows replaced by one equation

Trade-off: Works only if the relationship is truly linear — nonlinear patterns need more complex models.

Scenario: A column Gender with values M/F sorted by gender.
Raw bitmap for M: 1 1 1 1 1 0 0 0 0 0 0 0 (5 M's then 7 F's)

Decode: (5,1) $\to$ 11111, (7,0) $\to$ 0000000 — original bitmap restored exactly.

Input: A B A B A B A B (8 symbols)
RLE output: (1,A)(1,B)(1,A)(1,B)(1,A)(1,B)(1,A)(1,B) — 16 units
Observation: Output is twice the size of input.
Mitigation: Use a literal run escape: sequences of run-length 1 are grouped as a raw literal block instead of individual (1,x) pairs — used in PackBits (Apple) and PCX formats.

Scenario: FACT_SALES sorted by store_key. Store 1 has 50\,000 rows, store 2 has 30\,000 rows.

-- Raw column (80,000 integers):
1,1,1,...,1,  2,2,2,...,2
-- RLE encoded (2 pairs):
(50000, 1), (30000, 2)

Compression ratio: $80\,000 \div 2 = 40\,000\times$ reduction for this column.
Bonus: Aggregate queries (COUNT(*) WHERE store_key = 1) answered directly from the RLE pairs without decompressing.

Compressed stream: (3,X)(1,Y)(4,Z)(2,X)
Step-by-step decode:

Restored string: XXXYZZZZZXX — identical to original.

Approximate English letter frequencies (top 5):

Effect: Common letters cost 2–3 bits; rare letters cost 7–8 bits. Weighted average $\approx 4.2$ bits vs.\ 5-bit fixed — $\sim$16% compression on English text.

Problem: Huffman tree must be transmitted with the compressed data — expensive.
Canonical Huffman: Fix codewords by two rules only:

1. Shorter codes have numerically smaller values.

2. Codes of the same length are consecutive integers.

Transmit only: the list of codeword lengths per symbol (e.g.\ [1,2,3,4,4] for A,B,C,D,E).
Decoder reconstructs canonical codewords from lengths alone — no tree storage needed.
Used in: ZIP, gzip, PNG, HTTP/2 HPACK header compression.

Scenario: Compress a data stream where symbol frequencies are unknown in advance.
Algorithm (FGK / Vitter):

• Both encoder and decoder maintain identical Huffman trees, updated after every symbol.

• New symbols are emitted with an escape code + raw bits; tree restructured immediately.

• No separate frequency pre-scan or tree transmission required.

Trade-off: Slightly worse compression than static Huffman (tree adapts with delay); enables single-pass streaming compression.

Input: Single symbol A with probability $p_A = 1.0$ (only one symbol exists).
Huffman output: codeword 0 (1 bit).
Shannon entropy: $H = -1 \cdot \log_2 1 = 0$ bits/symbol.
Observation: Huffman must assign at least 1 bit — cannot reach the 0-bit theoretical limit.
Solution: Arithmetic coding can approach entropy arbitrarily closely, even for skewed distributions — at the cost of higher computational complexity.

Input String:
BABAABAAA

Initial Dictionary:

LZW Encoding Trace:

Final Output Code Stream:
\[ \boxed{1,\;0,\;2,\;3,\;0,\;6} \]

Final Dictionary:

Input String:
ABABABCB

Initial Dictionary:

LZW Encoding Trace:

Final Output Code Stream:
\[ \boxed{0,\;1,\;3,\;3,\;2,\;1} \]

Final Dictionary:

Input: AAABBBCCDDDDAA (14 symbols, alphabet {A,B,C,D})

Insight:

• RLE wins on long uniform runs.

• Huffman wins when frequencies are skewed but runs are short.

• LZW wins on long files with recurring substrings (not just characters).

• Real compressors (gzip, bzip2) chain multiple methods.

Attribute: Age with values {20, 30, 40, 50, 60}
$\min_A = 20$,    $\max_A = 60$

Attribute: Temperature    values: {$-10$, 0, 15, 25, 40}
$\min_A = -10$,    $\max_A = 40$,    $new\_min = -1$,    $new\_max = 1$
Formula: \[ v' = \frac{v - (-10)}{40 - (-10)} \times (1 - (-1)) + (-1) = \frac{v + 10}{50} \times 2 - 1 \]

The income attribute has $\min = 10{,}000$ and $\max = 90{,}000$.
Using min-max normalization to $[0, 1]$, the value $v = 40{,}000$ maps to:
\[ v' = \frac{40000 - 10000}{90000 - 10000} = \frac{30000}{80000} = 0.375 \] If a new value of $95{,}000$ arrives, the mapped value would be: \[ v' = \frac{95000 - 10000}{80000} = \frac{85000}{80000} = 1.0625 > 1 \] This falls outside $[0,1]$ — showing min-max normalization does not handle out-of-range values well.

Attribute: Salary (thousands)    {20, 25, 30, 35, 200}
$\min = 20$,    $\max = 200$

Values 20–35 are all compressed into $[0,\ 0.083]$ due to the outlier 200.
This illustrates the major weakness of min-max normalization.

Attribute: Marks    {50, 60, 70, 80, 90}
\[ \bar{A} = \frac{50+60+70+80+90}{5} = 70 \] \[ \sigma_A = \sqrt{\frac{(50-70)^2+(60-70)^2+(70-70)^2+(80-70)^2+(90-70)^2}{5}} = \sqrt{\frac{400+100+0+100+400}{5}} = \sqrt{200} \approx 14.14 \]

Mean of normalized values $= 0$,    Std Dev $= 1$    (verified)

An attribute Weight_kg has $\bar{A} = 65$ kg and $\sigma_A = 10$ kg.
(a) Normalize $v = 80$ kg: \[ v' = \frac{80 - 65}{10} = \frac{15}{10} = 1.5 \] (b) Normalize $v = 45$ kg: \[ v' = \frac{45 - 65}{10} = \frac{-20}{10} = -2.0 \] (c) What original value maps to $v' = 0.5$? \[ 0.5 = \frac{v - 65}{10} \implies v = 65 + 5 = 70 \text{ kg} \] (d) A value of $v' = -2.0$ means the weight is 2 standard deviations below the mean.

After Z-score normalization, two values are known:
Original value 40 maps to $v' = -1.5$
Original value 70 maps to $v' = 1.5$
Find $\bar{A}$ and $\sigma_A$:
From the two equations: \[ -1.5 = \frac{40 - \bar{A}}{\sigma_A} \qquad \text{and} \qquad 1.5 = \frac{70 - \bar{A}}{\sigma_A} \] Adding both equations: \[ 0 = \frac{(40 + 70) - 2\bar{A}}{\sigma_A} \implies \bar{A} = 55 \] Substituting back: \[ 1.5 = \frac{70 - 55}{\sigma_A} = \frac{15}{\sigma_A} \implies \sigma_A = 10 \]

Attribute: Salary (thousands)    {20, 25, 30, 35, 200}
$\bar{A} = \frac{20+25+30+35+200}{5} = 62$,    $\sigma_A = \sqrt{\frac{(20-62)^2+(25-62)^2+(30-62)^2+(35-62)^2+(200-62)^2}{5}}$
$= \sqrt{\frac{1764+1369+1024+729+19044}{5}} = \sqrt{\frac{23930}{5}} = \sqrt{4786} \approx 69.18$

• Min-max compresses 20–35 into $[0,\ 0.083]$; Z-score spreads them into $[-0.607,\ -0.390]$

• Z-score handles the outlier (200) more gracefully

Attribute: Votes    {350, 800, 1200, 4750, 9600}
$\max(|v|) = 9600$    — 5 digits, so $j = 4$ makes $\max(|v'|) < 1$?
$9600 / 10^4 = 0.96 < 1$    so $j = 4$

After min-max normalization to $[0,1]$, a value maps to $v' = 0.6$.
If $\min_A = 100$ and $\max_A = 600$, find the original value $v$.
\[ 0.6 = \frac{v - 100}{600 - 100} = \frac{v - 100}{500} \] \[ v - 100 = 0.6 \times 500 = 300 \implies v = 400 \]

Two data points $P_1 = (20,\ 10000)$ and $P_2 = (50,\ 40000)$
Attributes: Age $\in [20, 80]$, Salary $\in [10000, 70000]$
Before normalization (Euclidean distance): \[ d = \sqrt{(50-20)^2 + (40000-10000)^2} = \sqrt{900 + 9 \times 10^8} \approx 30000 \] Salary completely dominates the distance.
After min-max normalization to $[0,1]$:
Age: $P_1 \rightarrow \frac{20-20}{60} = 0.0$,    $P_2 \rightarrow \frac{50-20}{60} = 0.5$
Salary: $P_1 \rightarrow \frac{10000-10000}{60000} = 0.0$,    $P_2 \rightarrow \frac{40000-10000}{60000} = 0.5$
\[ d' = \sqrt{(0.5-0.0)^2 + (0.5-0.0)^2} = \sqrt{0.25+0.25} = \sqrt{0.5} \approx 0.707 \] Both attributes now contribute equally to the distance.