KNN (K-Nearest Neighbors) là gì?

K-nearest neighbors (KNN) dự đoán kết quả dựa trên các ví dụ huấn luyện đã được gán nhãn gần nhất với điểm truy vấn. Đối với phân loại, các láng giềng bỏ phiếu cho lớp. Đối với hồi quy, các giá trị mục tiêu của chúng được lấy trung bình hoặc kết hợp theo cách khác.

KNN là một phương pháp dựa trên các mẫu, không tổng quát hoá: quá trình huấn luyện chủ yếu chỉ lưu trữ các ví dụ huấn luyện và một chỉ mục tìm kiếm tùy chọn. Điều này không loại bỏ nhu cầu chia dữ liệu thành các tập huấn luyện, kiểm chứng và kiểm tra. Đánh giá trên dữ liệu giữ lại là cần thiết để lựa chọn k, metric khoảng cách, xử lý đặc trưng và quy tắc bỏ phiếu.

Những điểm chính

• KNN dự đoán cục bộ; nó không chia dữ liệu thành các cụm trước.
• Việc chuẩn hoá đặc trưng là quan trọng vì khoảng cách xác định các ví dụ nào được coi là láng giềng.
• k nhỏ có thể gây nhiễu, trong khi k lớn có thể làm mờ cấu trúc cục bộ.
• Không gian chiều cao, các đặc trưng không liên quan, mất cân bằng lớp và tìm kiếm chậm có thể hạn chế hiệu năng.

Cách hoạt động của phân loại KNN

1. Biểu diễn truy vấn và các ví dụ huấn luyện trong cùng không gian đặc trưng.
2. Tính khoảng cách từ truy vấn đến các ví dụ huấn luyện.
3. Chọn k ví dụ gần nhất.
4. Dự đoán lớp đa số hoặc sử dụng bỏ phiếu có trọng số theo khoảng cách.

Weighted voting gives closer neighbors more influence. Ties need a documented rule, and equal-distance neighbors with different labels can make results depend on ordering or implementation details.

Hồi quy KNN

Đối với hồi quy, dự đoán thường là trung bình của các mục tiêu của các láng giềng. Trọng số theo khoảng cách có thể giảm ảnh hưởng của các quan sát xa hơn. Trung vị hoặc tổng hợp bền vững có thể hữu ích khi các mục tiêu cục bộ chứa các ngoại lệ.

Các metric khoảng cách

Khoảng cách Euclid thường được dùng cho các đặc trưng liên tục, khoảng cách Manhattan tính tổng các chênh lệch tuyệt đối, và khoảng cách cosine tập trung vào hướng hơn là độ lớn. Các metric khác áp dụng cho dữ liệu nhị phân, phân loại, địa lý, chuỗi hoặc embedding đã học.

Calling KNN “non-parametric” means it does not assume a fixed finite-dimensional functional form for the decision boundary. It still assumes that the selected representation and metric make nearby points relevant to one another.

Tại sao việc chuẩn hoá quan trọng

Nếu một đặc trưng có giá trị từ 0 đến 1 và đặc trưng khác từ 0 đến 100.000, khoảng cách Euclid thông thường sẽ bị chi phối bởi đặc trưng thứ hai. Việc chuẩn hoá, chuẩn hoá lại (normalization) hoặc các biến đổi đặc thù cho miền nên được thực hiện trên phần dữ liệu huấn luyện và áp dụng cho dữ liệu kiểm chứng, kiểm tra và sản xuất.

Các đặc trưng không liên quan cũng làm méo mó các vùng lân cận. Lựa chọn đặc trưng, giảm chiều hoặc các biểu diễn đã học có thể giúp, nhưng mỗi lựa chọn phải được xác thực mà không gây rò rỉ dữ liệu.

Lựa chọn k

Với k = 1, mô hình có thể theo sát nhiễu và các ví dụ bị gán nhãn sai. Khi k tăng lên, các dự đoán trở nên mượt hơn và ít nhạy cảm với một điểm duy nhất. Nếu k quá lớn, các lớp hoặc vùng xa sẽ chi phối và mô hình sẽ thiếu khớp (underfit).

Lựa chọn k thông qua cross-validation trên dữ liệu huấn luyện. Đối với phân loại nhị phân, một k lẻ giảm nhưng không loại bỏ hoàn toàn các trường hợp hòa. Trọng số lớp, chia dữ liệu phân tầng, lựa chọn ngưỡng và các metric phù hợp quan trọng khi các lớp mất cân bằng.

Lời nguyền của độ cao chiều

Trong không gian chiều cao, các khoảng cách có thể trở nên kém thông tin vì các ví dụ thưa thớt và khoảng cách gần nhất và xa nhất trở nên tương đối giống nhau. KNN có thể yêu cầu một lượng dữ liệu khổng lồ để duy trì các vùng lân cận cục bộ có ý nghĩa. Đây là lời nguyền của độ cao chiều.

Giảm chiều hoặc các embedding đặc thù cho nhiệm vụ có thể giúp, nhưng hình học của embedding cần được xác thực cho khái niệm tương đồng mong muốn.

Hiệu suất tìm kiếm

Một truy vấn brute-force so sánh điểm mới với mọi ví dụ đã lưu. Cây KD và cây ball tăng tốc một số tìm kiếm chính xác, mặc dù lợi ích của chúng giảm trong không gian chiều cao. Các chỉ mục gần nhất xấp xỉ (approximate nearest-neighbor) đổi lại một lượng nhỏ độ thu hồi để đạt tốc độ và tiết kiệm bộ nhớ lớn. Ý tưởng này cũng là nền tảng cho tìm kiếm tương đồng vector.

Ưu điểm và hạn chế

KNN đơn giản, hỗ trợ các ranh giới quyết định không đều và cung cấp giải thích dựa trên ví dụ một cách trực quan. Tuy nhiên, nó cũng có thể yêu cầu bộ nhớ đáng kể, lộ các ví dụ huấn luyện nhạy cảm, dự đoán chậm và hoạt động kém khi khoảng cách không có ý nghĩa. Đây là một baseline hữu ích — không phải là phương pháp có độ chính xác cao trên hầu hết các vấn đề một cách mặc định.

Khoảng cách, vùng lân cận và hành vi siêu tham số

K-nearest neighbors lưu trữ các ví dụ huấn luyện và dự đoán dựa trên k láng giềng gần nhất theo một khoảng cách đã chọn. Phân loại sử dụng bỏ phiếu đa số hoặc có trọng số theo khoảng cách; hồi quy lấy trung bình các mục tiêu của các láng giềng. Việc chuẩn hoá là thiết yếu vì một đặc trưng có phạm vi lớn có thể chi phối khoảng cách Euclid. Dữ liệu phân loại, thưa thớt, chuỗi hoặc địa lý có thể yêu cầu các khoảng cách Hamming, cosine, edit, great-circle hoặc các khoảng cách đã học. Metric là một giả định mô hình về sự tương đồng, và nó cần được xác thực so với ý nghĩa thực tế của các trường hợp gần nhau.

k nhỏ tạo ra các ranh giới linh hoạt, có phương sai cao và nhạy cảm với nhiễu; k lớn làm mượt các dự đoán và có thể xóa bỏ cấu trúc của các nhóm thiểu số. k lẻ chỉ tránh một số trường hợp hòa trong phân loại nhị phân và không phải là quy tắc chung. Lựa chọn k, khoảng cách, trọng số, tập đặc trưng và tiền xử lý trong quá trình cross-validation. Mất cân bằng lớp có thể khiến việc bỏ phiếu đa số cục bộ bỏ qua các kết quả hiếm, vì vậy cần kiểm tra độ thu hồi theo lớp và thành phần vùng lân cận. Khoảng cách trong không gian chiều cao có xu hướng tập trung, và các đặc trưng không liên quan làm suy giảm vùng lân cận; việc lựa chọn, giảm chiều hoặc các embedding đã học có thể giúp.

Lập chỉ mục, độ không chắc và vận hành trong môi trường sản xuất

Phương pháp suy luận thô so sánh một truy vấn với mọi điểm huấn luyện. Cây KD và cây ball hữu ích trong các chiều thấp phù hợp; các chỉ mục gần nhất xấp xỉ đổi lại độ chính xác để đạt tốc độ và quy mô. Đo độ thu hồi của việc tìm kiếm láng giềng riêng biệt so với chất lượng dự đoán. Bộ nhớ bao gồm các đặc trưng, nhãn và cấu trúc chỉ mục đã lưu. Các cập nhật về mặt khái niệm đơn giản nhưng có thể yêu cầu xây dựng lại chỉ mục, duy trì tính nhất quán phiên bản và truyền bá việc xóa. Bảo vệ các ví dụ huấn luyện nhạy cảm vì việc trả về láng giềng hoặc khoảng cách có thể lộ thông tin.

KNN có thể hiển thị các ví dụ giúp làm cho dự đoán dễ hiểu, nhưng sự gần gũi không đồng nghĩa với nguyên nhân hay công bằng. Cung cấp khoảng cách, biên độ bỏ phiếu và quy tắc từ chối khi các vùng lân cận thưa thớt hoặc mâu thuẫn. Giám sát khoảng cách truy vấn, nhãn láng giềng, độ trôi đặc trưng, độ trễ và kết quả đã xác nhận. Giữ cho các phiên bản tiền xử lý và chỉ mục đồng bộ, và kiểm tra kết quả chính xác so với xấp xỉ sau khi thay đổi. KNN là một baseline cục bộ và phương pháp truy xuất hiệu quả khi khoảng cách có ý nghĩa; nó gặp khó khăn khi sự tương đồng không thể biểu diễn bằng các đặc trưng có sẵn.

Ví dụ thực tế: KNN cho việc thay thế sản phẩm

Một nhà bán lẻ biểu diễn sản phẩm bằng các thuộc tính số tiêu chuẩn, tính tương thích phân loại và một embedding văn bản đã học, sau đó định nghĩa một khoảng cách có trọng số được các bộ phận mua hàng xem xét. K và các trọng số được lựa chọn dựa trên các lần ra mắt sản phẩm sau, không phải các hàng ngẫu nhiên. Đánh giá kiểm tra độ thu hồi các sản phẩm thay thế liên quan, các đề xuất không tương thích, khoảng cách, độ bao phủ danh mục và kết quả cho các mặt hàng hiếm. Một baseline dựa trên độ phổ biến cho thấy liệu sự tương đồng cục bộ có tạo giá trị hay không.

Một chỉ mục xấp xỉ được so sánh với các láng giềng chính xác về độ thu hồi và độ trễ. Các truy vấn không có mặt hàng tương thích gần sẽ trả về không có đề xuất thay vì ép buộc một láng giềng. Việc xóa sản phẩm và sửa chữa thuộc tính được truyền tới chỉ mục thông qua các cập nhật có phiên bản. Giám sát theo dõi phân phối khoảng cách, kết quả trống, ghi đè và kết quả thương mại mà không nhầm lẫn doanh số với tính tương thích thực tế. Các điều khoản nhạy cảm của nhà cung cấp được loại trừ khỏi giải thích, và các ví dụ trả về vẫn là bằng chứng của sự tương đồng — không phải khẳng định các sản phẩm là tương đương.

Bằng chứng triển khai và sẵn sàng vận hành

Một quyết định triển khai sản xuất cần hơn một buổi trình diễn thành công. Xác định người dùng mục tiêu, môi trường hoạt động, đầu vào, đầu ra, các phụ thuộc, người chịu trách nhiệm và hậu quả của mỗi lỗi quan trọng. Thiết lập một baseline có thể tái tạo và một bộ đánh giá có phiên bản trước khi tinh chỉnh. Kiểm tra các trường hợp bình thường, điều kiện biên, đầu vào sai dạng hoặc thiếu, sự dịch chuyển phân phối, mất kết nối phụ thuộc, lạm dụng, và các nhóm hoặc môi trường có khả năng bị thiếu hỗ trợ. Đo lường chất lượng nhiệm vụ cùng với hiệu chuẩn hoặc độ không chắc, độ trễ, thông lượng, chi phí tài nguyên, khả năng tiếp cận, quyền riêng tư và bảo mật. Ghi lại mọi biến đổi và ngưỡng để một người đánh giá độc lập có thể tái tạo kết quả và phân biệt bằng chứng với một nguyên mẫu hấp dẫn.

Trước khi ra mắt, chỉ định quyền hạn cho việc phát hành, ngoại lệ, thay đổi, quay lại và ngừng sử dụng. Sử dụng triển khai theo giai đoạn, duy trì một phương án dự phòng an toàn và xác minh giám sát bằng cách đưa vào các lỗi cố ý. Telemetry vận hành nên tiết lộ chất lượng đầu vào, hành vi đầu ra, phiên bản mô hình hoặc quy tắc, tình trạng phụ thuộc, can thiệp của con người và kết quả đã xác nhận mà không thu thập dữ liệu nhạy cảm không cần thiết. Xác định ngưỡng cảnh báo và người chịu trách nhiệm phản hồi, sau đó xem xét bằng chứng thực tế sau khi triển khai thay vì giả định hiệu năng ngoại tuyến sẽ kéo dài. Đánh giá lại mỗi khi nguồn dữ liệu, người dùng, mô hình, nhà cung cấp, chính sách, phần cứng hoặc mục tiêu thay đổi. Một hệ thống được duy trì cũng cần có tài liệu phục hồi, học hỏi từ sự cố, quy trình xóa và lưu trữ, và một điểm rõ ràng khi nó nên bị vô hiệu hoá hoặc thay thế.

Câu hỏi thường gặp

KNN có giai đoạn huấn luyện không?

Nó có ít việc điều chỉnh tham số, nhưng vẫn có một quy trình phát triển: tiền xử lý được học từ dữ liệu huấn luyện, một chỉ mục có thể được xây dựng, và k, metric, trọng số và các đặc trưng được lựa chọn qua việc kiểm chứng.

KNN có giống K-means không?

Không. KNN chủ yếu là một phương pháp dự đoán cục bộ có giám sát. K-means là một thuật toán phân cụm không giám sát trong đó K là số trung tâm cụm.

Tham khảo chính

• scikit-learn: Nearest Neighbors
• scikit-learn: Cross-validation