Series: Machine Learning Fundamentals – Bài 27
Ở các bài trước, chúng ta đã tìm hiểu từ Logistic Regression, Decision Tree, Random Forest, các thuật toán Boosting (XGBoost, LightGBM, CatBoost) cho đến Support Vector Machine (SVM). Hầu hết các thuật toán này đều cần trải qua bước huấn luyện (Training) để tìm ra một hàm số hoặc các quy tắc phân chia dữ liệu.
Tuy nhiên, có một thuật toán cực kỳ đơn giản, không hề “học” bất kỳ tham số nào trong quá trình huấn luyện nhưng vẫn giải quyết hiệu quả cả bài toán Phân loại (Classification) và Hồi quy (Regression): K-Nearest Neighbors (KNN).
K-Nearest Neighbors là gì?
K-Nearest Neighbors (KNN) là một thuật toán học có giám sát (Supervised Learning) thuộc nhóm Lazy Learning (học lười biếng) và Non-parametric (phi tham số).
-
Lazy Learning: KNN không xây dựng một mô hình toán học tổng quát trong giai đoạn Training. Nó chỉ đơn giản là “ghi nhớ” toàn bộ dữ liệu huấn luyện. Việc tính toán chỉ thực sự diễn ra khi có một điểm dữ liệu mới cần dự đoán (Inference).
-
Non-parametric: KNN không đưa ra bất kỳ giả định nào về dạng phân phối của dữ liệu.
Triết lý cốt lõi của KNN rất tự nhiên: “Gần mực thì đen, gần đèn thì sáng” – các điểm dữ liệu có đặc trưng tương tự nhau sẽ nằm gần nhau trong không gian biểu diễn.
Class A o o ? (Điểm mới) x x Class B
o \ | / x x
o | x
-------------------------------------------------
Dự đoán cho điểm ?: Tìm K điểm gần nhất và bỏ phiếu (Majority Voting)
Cách K-Nearest Neighbors hoạt động
Quy trình dự đoán cho một điểm dữ liệu mới $X_{new}$ bao gồm 4 bước cơ bản:
-
Chọn số lượng hàng xóm $K$ (ví dụ: $K = 3$ hoặc $K = 5$).
-
Tính khoảng cách từ điểm $X_{new}$ đến tất cả các điểm dữ liệu trong Dataset huấn luyện.
-
Sắp xếp và chọn ra $K$ điểm có khoảng cách ngắn nhất đến $X_{new}$.
-
Đưa ra dự đoán:
-
Với bài toán Phân loại (Classification): Áp dụng bỏ phiếu theo số đông (Majority Voting). Lớp nào xuất hiện nhiều nhất trong $K$ hàng xóm sẽ là kết quả dự đoán.
-
Với bài toán Hồi quy (Regression): Tính giá trị trung bình (Mean hoặc Median) của $K$ hàng xóm.
-
Các phương pháp đo khoảng cách phổ biến
Để xác định đâu là “hàng xóm gần nhất”, KNN sử dụng các công thức đo khoảng cách trong không gian toán học:
1. Khoảng cách Euclidean (Phổ biến nhất)
Khoảng cách theo đường thẳng giữa hai điểm $P(x_1, y_1)$ và $Q(x_2, y_2)$:
2. Khoảng cách Manhattan (L1 Distance)
Khoảng cách di chuyển theo các trục tọa độ vuông góc (dạng mạng lưới đường phố):
3. Khoảng cách Minkowski
Dạng tổng quát của cả Euclidean và Manhattan (với tham số $p$):
-
Khi $p = 1 \implies$ Khoảng cách Manhattan.
-
Khi $p = 2 \implies$ Khoảng cách Euclidean.
Cách chọn K trong K-Nearest Neighbors
Giá trị $K$ đóng vai trò quyết định đến hiệu suất của mô hình:
-
Khi $K$ quá nhỏ ($K = 1$): Mô hình cực kỳ nhạy cảm với nhiễu và Outliers $\rightarrow$ Dễ bị Overfitting.
-
Khi $K$ quá lớn ($K = N$): Mô hình sẽ dự đoán mọi điểm mới về lớp chiếm đa số trong toàn bộ Dataset $\rightarrow$ Dễ bị Underfitting.
K nhỏ (K=1) ──> Mẫu quá chi tiết ──> Overfitting
K tối ưu ──> Ranh giới mượt ──> Good Fit
K lớn (K=N) ──> Quá phẳng ──> Underfitting
Quy tắc kinh nghiệm chọn K:
-
Chọn $K$ là số lẻ khi làm bài toán Phân loại 2 lớp (Binary Classification) để tránh trường hợp hòa phiếu.
-
Giá trị $K$ thường được chọn theo công thức kinh nghiệm $K \approx \sqrt{N}$ (với $N$ là số mẫu dữ liệu).
-
Sử dụng Cross-Validation và GridSearchCV để tìm ra $K$ tối ưu nhất cho từng bộ dữ liệu.
Dữ liệu có cần Feature Scaling không?
CỰC KỲ BẮT BUỘC.
Vì KNN dựa hoàn toàn vào khoảng cách hình học, các Feature có vạch quy mô lớn sẽ áp đảo hoàn toàn các Feature có vạch quy mô nhỏ.
Ví dụ: Nếu cột Tuổi có giá trị từ $18 – 60$, còn cột Thu nhập có giá trị từ $5,000,000 – 100,000,000$, khoảng cách giữa hai điểm sẽ bị chi phối $99.9\%$ bởi Thu nhập.
Do đó, bắt buộc phải dùng StandardScaler hoặc MinMaxScaler trước khi đưa dữ liệu vào KNN.
Ưu điểm và Nhược điểm của K-Nearest Neighbors
Ưu điểm
-
Đơn giản, dễ hiểu: Không cần giả định phức tạp về phân phối dữ liệu.
-
Không tốn thời gian Training: Giai đoạn huấn luyện gần như bằng 0 giây.
-
Tự nhiên với bài toán Multi-class: Dễ dàng mở rộng cho bài toán phân loại nhiều lớp.
Nhược điểm
-
Chậm khi dự đoán (Inference Time): Với Dataset lớn, việc tính khoảng cách tới hàng triệu điểm dữ liệu tại mỗi lượt dự đoán tốn rất nhiều thời gian và tài nguyên CPU/RAM.
-
Nhạy cảm với Lời nguyền số chiều (Curse of Dimensionality): Khi số lượng Features quá nhiều, khoảng cách giữa các điểm trở nên xấp xỉ bằng nhau, khiến KNN mất đi độ chính xác.
-
Nhạy cảm với Outliers và Missing Values: Cần làm sạch dữ liệu cẩn thận trước khi huấn luyện.
Khi nào nên dùng K-Nearest Neighbors?
-
Dữ liệu có kích thước vừa và nhỏ (dưới vài chục nghìn dòng).
-
Số lượng Features thấp (đã qua các bước giảm chiều dữ liệu như PCA).
-
Cần một mô hình Baseline nhanh chóng mà không muốn mất công cấu hình tham số phức tạp.
-
Ứng dụng trong các hệ thống gợi ý đơn giản (Recommender Systems) dựa trên độ tương đồng giữa các User/Item.
Tóm tắt
-
K-Nearest Neighbors phân loại dựa trên độ tương đồng khoảng cách với $K$ hàng xóm gần nhất.
-
Bắt buộc phải Feature Scaling dữ liệu trước khi chạy KNN.
-
Khoảng cách Euclidean là lựa chọn phổ biến nhất.
-
Chọn $K$ bằng Cross-Validation để tránh Overfitting ($K$ quá nhỏ) hoặc Underfitting ($K$ quá lớn).
Tài liệu tham khảo
-
Scikit-Learn Documentation: K-Nearest Neighbors in Scikit-Learn
-
Cover & Hart (1967): Nearest neighbor pattern classification – Bài báo đặt nền móng cho KNN.
Khóa học tại MCNA Technology School
Nếu bạn muốn thực hành Machine Learning, Python và xây dựng các mô hình trên dữ liệu thực tế, có thể tham khảo:
-
🤖 Combo 5 khóa AI & Power BI: Xem khóa học AI & Power BI
-
🐍 Combo Python: Xem Combo Python
Tác giả: Bùi Đình Tuyển – Data Analyst tại MCNA Technology School
📞 Hotline: 0939.866.825 (Mr. Minh Khang)
🌐 Website: MCNA Technology School
📍 Hà Nội: 30 Trung Liệt, Đống Đa | Liền kề 44B TT2 Văn Quán, Hà Đông
📍 TP.HCM: 50B Phan Tây Hồ, Cầu Kiệu
