Quy tắc Láng giềng gần nhất (Nearest Neighbour rule) thường tạo ra hiệu suất cao, không cần giả định trước về phân phối mà các thể hiện huấn luyện được rút ra. Nó bao gồm một tập huấn luyện cả trường hợp dương tính (positive) và âm tính (negative). Một mẫu mới được phân loại bằng cách tính khoảng cách đến trường hợp huấn luyện thuận tiện; dấu hiệu của điểm đó sau đó quyết định phân loại của mẫu.
Bộ phân loại k-NN mở rộng khái niệm này bằng cách lấy k điểm gần nhất và tạo dấu hiệu của đa số. Thường chọn k nhỏ và lẻ để chia cắt hòa (thường 1, 3, hoặc 5). Giá trị k lớn hơn giúp giảm hiệu ứng của các điểm nhiễu (noisy points) bên trong tập dữ liệu huấn luyện, và lựa chọn k được triển khai qua cross-validation.
Có một số đặc điểm của Láng giềng gần nhất như sau:
Phân loại láng giềng gần nhất là một yếu tố của các phương pháp tổng quát hơn gọi là học dựa trên thể hiện (instance-based learning). Nó cần các thể hiện huấn luyện cụ thể để làm dự đoán mà không phải hỗ trợ một sự trừu tượng (hoặc mô hình) suy ra từ dữ liệu.
Các thuật toán học dựa trên thể hiện (Instance-based learning algorithms) cần một đo lường sự gần (proximity measure) để quyết định sự tương đồng hoặc khoảng cách giữa các thể hiện và một hàm phân loại (classification function) khôi phục lớp dự đoán của một thể hiện kiểm tra tùy thuộc vào sự gần của nó với các thể hiện khác.
Người học lười biếng (Lazy learners) bao gồm bộ phân loại láng giềng gần nhất không cần xây dựng mô hình. Nhưng phân loại một ví dụ kiểm tra có thể khá đắt vì cần tính giá trị sự gần riêng lẻ giữa kiểm tra và huấn luyện. Ngược lại, người học háo hức (eager learners) dành phần lớn tài nguyên tính toán cho xây dựng mô hình. Vì một mô hình đã được xây dựng, phân loại ví dụ kiểm tra hoàn toàn nhanh.
Bộ phân loại láng giềng gần nhất làm dự đoán của họ dựa trên dữ liệu cục bộ (local data), trong khi cây quyết định và bộ phân loại dựa trên quy tắc cố gắng tìm một mô hình toàn cục (global model) phù hợp với toàn bộ không gian đầu vào. Do quyết định phân loại được tạo cục bộ, bộ phân loại láng giềng gần nhất bị ảnh hưởng bởi nhiễu (noise).
Bộ phân loại láng giềng gần nhất có thể tạo ra ranh giới quyết định hình dạng tùy ý (arbitrarily shaped decision boundaries). Các ranh giới như vậy hỗ trợ biểu diễn mô hình linh hoạt hơn so với cây quyết định và bộ phân loại dựa trên quy tắc bị buộc phải ranh giới quyết định vuông góc (rectilinear decision boundaries).
Bộ phân loại láng giềng gần nhất có thể làm dự đoán sai trừ khi đo lường sự gần phù hợp và giai đoạn tiền xử lý dữ liệu được thực hiện. Ví dụ, xét rằng cần phân loại một tập người dựa trên thuộc tính như chiều cao (đo bằng mét) và cân nặng (đo bằng pound).
Thuộc tính chiều cao có biến động thấp, dao động từ 1.5 m đến 1.85 m, trong khi thuộc tính cân nặng có thể thay đổi từ 90 lb. đến 250 lb. Nếu thang đo của các thuộc tính không được đưa vào ứng dụng, đo lường sự gần có thể bị chi phối bởi sự khác biệt trong cân nặng của một người.