K-Nearest Neighbors (KNN): Hiểu đơn giản qua một ví dụ minh họa
K-Nearest Neighbors (KNN) là một trong những thuật toán học máy đơn giản nhưng hiệu quả. Dựa vào đặc điểm của dữ liệu xung quanh, KNN giúp chúng ta phân loại hoặc dự đoán giá trị của một dữ liệu mới. Trong bài viết này, chúng ta sẽ tìm hiểu về KNN qua một ví dụ minh họa phân loại trái cây.
Nguyên tắc hoạt động của KNN
1. Lưu trữ dữ liệu: KNN chỉ lưu dữ liệu và không xây dựng mô hình phức tạp.
2. Tìm láng giềng gần nhất:
- Khi cần dự đoán cho một điểm dữ liệu mới, KNN tính khoảng cách giữa điểm đó và tất cả các điểm trong dữ liệu huấn luyện.
- Chọn k điểm gần nhất (láng giềng) dựa trên một hàm đo khoảng cách, phổ biến nhất là:
- Khoảng cách Euclid: \( d(p, q) = \sqrt{\sum_{i=1}^{n}(p_i - q_i)^2} \)
- Khoảng cách Manhattan: \( d(p, q) = \sum_{i=1}^{n}|p_i - q_i| \)
3. Dự đoán:
-
- Phân loại: Chọn lớp (nhãn) xuất hiện nhiều nhất trong k láng giềng.
- Hồi quy: Tính trung bình giá trị của k láng giềng.
Đặc điểm chính:
- Lazy Learning: Thuật toán không thực sự "học" trong giai đoạn huấn luyện mà chỉ làm việc khi cần dự đoán (tính toán tại thời điểm chạy).
- Tham số k:
- Chọn k lớn hơn có thể làm giảm nhiễu nhưng dễ dẫn đến việc làm mờ ranh giới giữa các lớp.
- Chọn k nhỏ hơn sẽ nhạy cảm hơn với nhiễu và điểm ngoại lai.
Ưu điểm:
1. Đơn giản và dễ hiểu.
2. Hiệu quả cho các tập dữ liệu nhỏ hoặc vừa phải.
3. Có thể giải quyết cả bài toán phân loại và hồi quy.
Nhược điểm:
1. Chi phí tính toán cao: Do phải tính toán khoảng cách cho tất cả các điểm trong tập dữ liệu.
2. Nhạy cảm với dữ liệu lớn: Khi dữ liệu huấn luyện quá lớn, hiệu năng suy giảm nghiêm trọng.
3. Nhạy cảm với dữ liệu không cân bằng: Nếu một lớp xuất hiện nhiều hơn lớp khác, nó có thể chiếm ưu thế.
4. Phụ thuộc vào cách chọn khoảng cách và k: Kết quả phụ thuộc nhiều vào cách tính khoảng cách và số lượng k.
Ứng dụng:
- Phân loại văn bản.
- Nhận diện mẫu, ví dụ như nhận diện khuôn mặt.
- Dự đoán giá trị (như giá nhà).
Ví dụ: Phân loại Táo và Cam
Dữ liệu
| Kích thước (cm) | Màu sắc (độ đỏ) | Nhãn |
|---|---|---|
| 3 | 200 | Táo |
| 4 | 220 | Táo |
| 5 | 50 | Cam |
| 6 | 30 | Cam |
- Trái cây mới: Kích thước = 4.5, Màu sắc = 100.
Tính khoảng cách
Sử dụng công thức khoảng cách Euclid:
\[ d = \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2} \]
Khoảng cách giữa trái cây mới và từng điểm dữ liệu:
1. Với (3, 200, Táo):
\[
d = \sqrt{(4.5 - 3)^2 + (100 - 200)^2} = \sqrt{1.5^2 + (-100)^2} \approx 100.01
\]
2. Với (4, 220, Táo):
\[
d = \sqrt{(4.5 - 4)^2 + (100 - 220)^2} = \sqrt{0.5^2 + (-120)^2} \approx 120.00
\]
3. Với (5, 50, Cam):
\[
d = \sqrt{(4.5 - 5)^2 + (100 - 50)^2} = \sqrt{0.5^2 + 50^2} \approx 50.01
\]
4. Với (6, 30, Cam):
\[
d = \sqrt{(4.5 - 6)^2 + (100 - 30)^2} = \sqrt{1.5^2 + 70^2} \approx 70.02
\]
Kết quả
Sắp xếp khoảng cách:
- (5, 50, Cam): 50.01
- (6, 30, Cam): 70.02
- (3, 200, Táo): 100.01
- (4, 220, Táo): 120.00
Ba láng giềng gần nhất:
- (5, 50, Cam)
- (6, 30, Cam)
- (3, 200, Táo)
Số phiếu:
- Cam: 2
- Táo: 1
Kết luận: Trái cây mới được phân loại là Cam.
Ưu và nhược điểm của KNN
Ưu điểm:
- Dễ hiểu, dễ triển khai.
- Hiệu quả với dữ liệu nhỏ hoặc vừa.
Nhược điểm:
- Chi phí tính toán cao với dữ liệu lớn.
- Nhạy cảm với dữ liệu nhiễu và không cân bằng.
Kết luận
KNN là một thuật toán mạnh mẽ và linh hoạt trong việc phân loại và hồi quy. Với khả năng áp dụng rộng rãi trong các lĩnh vực như nhận diện mẫu, phân loại văn bản, và dự đoán giá trị, KNN là công cụ hữu ích mà bạn nên thử trong các bài toán học máy của mình.
