K-Nearest Neighbors (KNN): Sai số huấn luyện và cạm bẫy láng giềng

Thuật toán K-Nearest Neighbors (KNN) phân loại một điểm dựa trên biểu quyết đa số từ $K$ quan sát gần nhất theo khoảng cách Euclid.

Xét tập huấn luyện gồm 5 điểm hai chiều $(X_1, X_2)$:

• Lớp [−]: #1 (0,0), #2 (0,1), #3 (2,0)
• Lớp [+]: #4 (2,3), #5 (3,1)

Yêu cầu: Tính sai số huấn luyện (training error rate) với $K = 3$.

---

1. Bản chất của Training Error trong KNN

Khi tính sai số trên tập huấn luyện, kho dữ liệu tham chiếu chính là tập huấn luyện. Với mỗi điểm $x_i$, chính nó cũng là một láng giềng có khoảng cách bằng 0. Vì vậy, tập $K=3$ láng giềng gần nhất gồm chính nó và 2 điểm gần nó nhất.

Xét khoảng cách Euclid bình phương $d^2 = \Delta X_1^2 + \Delta X_2^2$:

• #1 (0,0) [−]: Láng giềng ${1, 2, 3}$ (khoảng cách $0, 1, 4$) $\to 3[−] \implies$ Đúng.
• #2 (0,1) [−]: Láng giềng ${2, 1, 3}$ (khoảng cách $0, 1, 5$) $\to 3[−] \implies$ Đúng.
• #3 (2,0) [−]: Láng giềng ${3, 5, 1}$ (khoảng cách $0, 2, 4$) $\to 2[−], 1[+] \implies$ Đúng.
• #4 (2,3) [+]: Láng giềng ${4, 5, 2}$ (khoảng cách $0, 5, 8$) $\to 2[+], 1[−] \implies$ Đúng.
• #5 (3,1) [+]: Láng giềng ${5, 3, 4}$ (khoảng cách $0, 2, 5$) $\to 2[+], 1[−] \implies$ Đúng.

---

2. Kết luận & Cạm bẫy đề thi

$$ \text{Training Error Rate} = \frac{0}{5} = \mathbf{0{,}0} \quad (\text{Chọn A}). $$

⚠️ Cạm bẫy: Nếu nhầm sang Leave-One-Out (LOOCV) — loại trừ chính điểm đó ra — thì điểm #4 và #5 sẽ bị đoán sai thành $[−]$ (do chỉ còn $1[+], 2[−]$), dẫn đến sai số $2/5 = 0{,}4$ (đáp án bẫy C).