EP07_01 — 🟢 Step-by-Step k-NN Classifier

7.18.1.1 📋 Implementation Guidelines

1. Quantity and parameter: Read the integer \(N\) (number of training examples) and the odd integer \(k\) (number of neighbors).
2. Training examples: For each of the \(N\) examples, read three values: the \(x\) and \(y\) coordinates (real numbers) and the label \(r\) (integer, \(0\) or \(1\)).
3. Queries: Read the integer \(Q\) (number of query points) and then the coordinates \(x_q\), \(y_q\) (real numbers) of each query.
4. Distance: For each query, compute the Euclidean distance to all training examples: \[ d(x_q, x_i) = \sqrt{(x_q - x_i)^2 + (y_q - y_i)^2}. \]
5. Neighbor selection: Sort the examples by increasing distance and select the first \(k\). In case of a distance tie at the boundary of the \(k\)-th neighbor, break the tie by the example read first in the input (stable reading order).
6. Majority voting: Count the votes for each class among the \(k\) selected neighbors. If there is a tie in the voting (only possible when \(k\) is even, which should not occur per the guideline in item 1, but handle defensively), assign the class of the closest neighbor among the tied classes.
7. Output: For each query, in input order, print the predicted class. At the end, print the total number of queries classified as class 1.

7.18.1.2 📌 Computational Constraints

• Fixed metric: use exclusively the Euclidean distance (not the squared distance) for the sorting, although the comparison result is the same.
• \(k\) always odd: the input guarantees \(k\) odd and \(k \le N\); still, implement the tie-breaking from item 6 for robustness.
• Stability: when sorting by distance, preserve the relative order of examples with the same distance (stable sorting).

7.18.1.3 🧠 Theoretical Foundation

7.18.1.4 📦 Input and Output Specification (VPL)

Input:

• Line 1: Integers \(N\) and \(k\), separated by spaces.
• Next \(N\) lines: three values per line — \(x\), \(y\) (real numbers) and \(r\) (integer \(\in \{0,1\}\)), separated by spaces.
• Next line: integer \(Q\).
• Next \(Q\) lines: two values per line — \(x_q\), \(y_q\) (real numbers), separated by spaces.

Output:

• \(Q\) lines, each with the predicted class (0 or 1) for the respective query, in input order.
• Last line: Total class 1: X.

7.18.1.5 📌 Examples

%%writefile EP07_01.py
# Python code

Overwriting EP07_01.py

TestSuite("EP07_01.py").run()

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

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