# 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)$:

![Biểu đồ toạ độ 5 điểm huấn luyện](/images/math/stats/knn-coordinates.svg)

- **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

Cả 5 điểm đều được dự đoán đúng:
$$
\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).