K-Nearest Neighbors (KNN)

Láng giềng gần nhất (KNN) là một thuật toán mạnh mẽ và trực quan được sử dụng trong lĩnh vực học có giám sát cho cả các tác vụ phân loại và hồi quy. Nhờ tính đơn giản, KNN thường được phân loại là một "bộ học lười" vì không xây dựng model hoặc học các tham số trong giai đoạn huấn luyện. Thay vào đó, thuật toán ghi nhớ toàn bộ tập dữ liệu huấn luyện và chỉ thực hiện tính toán khi có yêu cầu dự đoán. Nguyên tắc cốt lõi của thuật toán dựa trên độ tương đồng của các đặc trưng: thuật toán giả định rằng các điểm dữ liệu có thuộc tính tương tự tồn tại gần nhau trong không gian đặc trưng đa chiều.

Cách thuật toán hoạt động#

Cơ chế của Láng giềng gần nhất (KNN) được điều khiển bởi các phép tính khoảng cách. Khi một điểm truy vấn mới được đưa vào, thuật toán tìm kiếm tập dữ liệu đã lưu để tìm 'K' mẫu huấn luyện gần với đầu vào mới nhất.

1. Đo khoảng cách: Hệ thống tính khoảng cách giữa điểm truy vấn và mọi điểm khác trong cơ sở dữ liệu. Metric phổ biến nhất là khoảng cách Euclid, dùng để đo khoảng cách theo đường thẳng giữa các điểm. Các metric khác như khoảng cách Manhattan (hình học taxi) hoặc khoảng cách Minkowski có thể được sử dụng tùy thuộc vào loại dữ liệu.

2. Lựa chọn láng giềng: Sau khi tính khoảng cách, thuật toán sắp xếp chúng và xác định 'K' mục gần nhất hàng đầu.

3. Ra quyết định: - Đối với phân loại: Thuật toán sử dụng hệ thống "bỏ phiếu đa số". Nhãn lớp xuất hiện thường xuyên nhất trong số K láng giềng sẽ được gán cho điểm truy vấn. Cách này được sử dụng rộng rãi trong các tác vụ phân loại hình ảnh cơ bản. - Đối với hồi quy: Dự đoán được tính bằng cách lấy trung bình các giá trị của K láng giềng gần nhất để ước tính một biến liên tục.

Lựa chọn 'K' phù hợp#

Việc chọn giá trị tối ưu cho 'K' là một bước quan trọng trong tinh chỉnh hyperparameter. Lựa chọn K ảnh hưởng đáng kể đến hiệu năng của model và khả năng khái quát hóa trên dữ liệu mới.

• Giá trị K thấp: K nhỏ (ví dụ: K=1) khiến model rất nhạy với nhiễu và các giá trị ngoại lệ trong dữ liệu, điều này có thể dẫn đến overfitting.
• Giá trị K cao: K lớn làm mượt các ranh giới quyết định, giảm ảnh hưởng của nhiễu nhưng có khả năng làm mờ các pattern riêng biệt, dẫn đến underfitting.

Các ứng dụng trong thực tế#

Mặc dù đơn giản hơn so với các neural network sâu, KNN vẫn giữ vai trò quan trọng trong AI hiện đại, đặc biệt khi kết hợp với các kỹ thuật trích xuất đặc trưng tiên tiến.

• Hệ thống gợi ý: KNN hỗ trợ lọc cộng tác trong lĩnh vực streaming nội dung và thương mại điện tử. Bằng cách xác định những người dùng có lịch sử xem hoặc hành vi mua hàng tương tự (các láng giềng), các nền tảng có thể đề xuất những sản phẩm mà người dùng có khả năng yêu thích dựa trên sở thích của "các láng giềng gần nhất".
• Phát hiện bất thường: Trong an ninh mạng và tài chính, KNN được sử dụng để phát hiện bất thường. Các giao dịch hoặc hoạt động mạng được ánh xạ trong một không gian đặc trưng; mọi điểm dữ liệu mới nằm cách xa các cụm dày đặc của hoạt động "bình thường" đều được đánh dấu là có khả năng gian lận hoặc vi phạm bảo mật.
• Tìm kiếm trực quan: Các engine tìm kiếm vector hiện đại thường dựa vào các thuật toán Láng giềng gần đúng (ANN)—một biến thể được tối ưu hóa của KNN—để nhanh chóng truy xuất các hình ảnh tương tự dựa trên các embedding nhiều chiều do các model như YOLO26 tạo ra.

Thách thức và các yếu tố cần cân nhắc#

Mặc dù hiệu quả, KNN vẫn gặp phải lời nguyền số chiều. Khi số lượng đặc trưng (chiều) tăng lên, các điểm dữ liệu trở nên thưa thớt và các metric khoảng cách mất đi tính hiệu quả. Ngoài ra, vì lưu trữ toàn bộ dữ liệu huấn luyện, KNN có thể tiêu tốn nhiều bộ nhớ và chịu độ trễ suy luận cao trên các tập dữ liệu lớn. Để giải quyết vấn đề này, các kỹ sư thường tiền xử lý dữ liệu bằng các kỹ thuật giảm số chiều như Phân tích thành phần chính (PCA) hoặc sử dụng các cấu trúc dữ liệu chuyên dụng như KD-Trees để tăng tốc quá trình tìm kiếm. Để mở rộng quy mô tập dữ liệu và huấn luyện model ở cấp doanh nghiệp, việc sử dụng Ultralytics Platform có thể giúp quản lý các tài nguyên tính toán cần thiết cho việc tiền xử lý dữ liệu phức tạp.

Phân biệt KNN với K-Means#

Điều quan trọng là phải phân biệt Láng giềng gần nhất (KNN) với phân cụm K-Means, vì tên gọi tương tự của chúng thường gây nhầm lẫn.

• KNN là một thuật toán học có giám sát sử dụng dữ liệu được gán nhãn để đưa ra dự đoán.
• K-Means là một thuật toán học không giám sát được sử dụng để nhóm dữ liệu chưa gán nhãn thành các cụm dựa trên những điểm tương đồng về cấu trúc.

Ví dụ triển khai#

Đoạn code sau minh họa một workflow phân loại KNN đơn giản bằng thư viện Scikit-learn phổ biến. Trong ngữ cảnh computer vision, các "đặc trưng" đầu vào thường được trích xuất bởi một model deep learning như YOLO26 trước khi được truyền vào bộ phân loại KNN.

from sklearn.neighbors import KNeighborsClassifier

# Simulated feature vectors (e.g., extracted from YOLO26) and labels
# Features: [Size, Redness], Labels: 0=Apple, 1=Orange
features = [[0.8, 0.9], [0.9, 0.8], [0.2, 0.3], [0.3, 0.2]]
labels = [0, 0, 1, 1]

# Initialize KNN with 3 neighbors
knn = KNeighborsClassifier(n_neighbors=3)
knn.fit(features, labels)

# Predict the class of a new object [Size=0.85, Redness=0.85]
prediction = knn.predict([[0.85, 0.85]])
print(f"Predicted Class: {prediction[0]} (0=Apple, 1=Orange)")