EP07_02 — 🟡 Z-score Normalization and Robustness of k-NN to Distinct Scales

7.18.2 EP07_02 🟡 Z-score Normalization and Robustness of k-NN to Distinct Scales

This exercise revisits the classifier implemented in EP07_01, this time under the perspective discussed in the section The Impact of Scale and Feature Normalization of the chapter: k-NN decides based on the distance between vectors, so that a feature measured on a much larger scale than the others tends to dominate the distance calculation, even when it is not the most relevant for separating the classes.

An inspection system records, for each part, its area (in pixels, possibly reaching hundreds or thousands) and its circularity (always between \(0\) and \(1\)). You have been tasked with classifying new parts by k-NN in two ways — with and without the Z-score standardization presented in the chapter — and reporting in which cases the two approaches diverge.

7.18.2.1 📋 Implementation Guidelines

Quantity and parameter: Read the integer \(N\) (number of training examples) and the odd integer \(k\).
Training examples: For each of the \(N\) examples, read three values: the area \(x_1\) (real), the circularity \(x_2\) (real), and the label \(r\) (integer, \(0\) or \(1\)).
Queries: Read the integer \(Q\) and then the coordinates \(x_1, x_2\) of each query.
Classification without normalization: For each query, classify it by k-NN directly on \((x_1, x_2)\), with Euclidean distance and the same tie-breaking rules as in EP07_01 (reading order for tied distances; nearest neighbor among tied classes in the majority vote).
Normalization parameters: Compute the mean \(\mu_j\) and the population standard deviation \(\sigma_j\) (division by \(N\), not \(N-1\) — the same convention adopted by the StandardScaler class) of each feature \(j \in \{1,2\}\), exclusively on the training set.
Standardization: Transform each training and query feature by \[ z_j = \frac{x_j - \mu_j}{\sigma_j}. \] If \(\sigma_j = 0\) (constant feature in the training set), set \(z_j = 0\) for all samples of that feature, avoiding division by zero.
Classification with normalization: Repeat the k-NN classification of item 4, now on the standardized vectors \((z_1, z_2)\), with the same tie-breaking rules.
Output: For each query, in input order, print the two predicted classes. At the end, print the number of queries in which the two classifications diverge.

7.18.2.2 📌 Computational Constraints

Fit on training data only: \(\mu_j\) and \(\sigma_j\) are computed solely from the training set and reapplied to the queries — never recalculated from them. This practice avoids data leakage, mentioned in the normalization section of the chapter.
Population standard deviation: use \(\sigma_j = \sqrt{\frac{1}{N}\sum_i (x_{i,j}-\mu_j)^2}\), not the sample version (division by \(N-1\)).
Constant feature: treat \(\sigma_j = 0\) as a special case (item 6); no division-by-zero error should occur.
Tie-breaking rules: reuse exactly the conventions from EP07_01, both in selecting the \(k\) neighbors and in the majority vote.

7.18.2.3 🧠 Theoretical Foundation

Element	Role
Z-score standardization	Rescales each feature to mean \(0\) and standard deviation \(1\), making heterogeneous scales comparable
Fit on training data only	Ensures that evaluation on queries reflects only what the model learned from the training data
Euclidean distance without normalization	Dominated by the feature with the largest magnitude — here, the area
Divergent prediction	Highlights that the scale of features, not just the algorithm or the data, can determine the k-NN decision boundary

This exercise reinforces, in a controlled manner, the reason why StandardScaler is applied before k-NN throughout the chapter: without this step, circularity features — even when highly discriminative — can be practically ignored by the classifier in the presence of an area feature with a magnitude hundreds of times larger.

7.18.2.4 📦 Input and Output Specification (VPL)

Input:

Line 1: Integers \(N\) and \(k\), separated by a space.
Next \(N\) lines: three values per line — \(x_1\), \(x_2\) (real) and \(r\) (integer \(\in \{0,1\}\)), separated by a space.
Next line: integer \(Q\).
Next \(Q\) lines: two values per line — \(x_1\), \(x_2\) (real) of the query, separated by a space.

Output:

\(Q\) lines, in the format SemNorm=<0|1> ComNorm=<0|1>, in the input order of the queries.
Last line: Divergiu: <int>.

7.18.2.5 📌 Examples

Input	Output	Observation
4 3 10 0.9 0 12 0.85 0 900 0.2 1 950 0.25 1 1 500 0.88	SemNorm=1 ComNorm=0 Divergiu: 1	Without normalization, the area (scale of hundreds) dominates the distance, and the query is classified as class `1`. After standardization, the circularity — much closer to the class `0` samples — becomes comparably weighted, and the prediction changes to `0`.
2 1 0 0.5 0 100 0.5 1 1 60 0.5	SemNorm=1 ComNorm=1 Divergiu: 0	The circularity is constant in the training set (\(\sigma_2=0\)); by the rule of item 6, \(z_2=0\) for all samples, and the classification depends only on the area in both cases.

🎮 Simulator EP07_02: Z-score Normalization and k-NN Distance Feature Standardization

Each example has two features: area (px) and circularity [0, 1]. Toggle normalization and observe the change in the predicted class.

–

Figure 7.22: EP07_02 Simulator: Effect of Z-score Normalization on k-NN Distance

%%writefile EP07_02.py
# Python code

Overwriting EP07_02.py

TestSuite("EP07_02.py").run()

✔️ EP07_02.cases already exists in casos/
📋 5 case(s) loaded from casos/EP07_02.cases

🔍 Testing Python: EP07_02.py
⚠️ EP07_02.py: Empty file (fewer than 3 lines). Tests skipped.