Thuật toán k-láng giềng gần nhất (k-nearest-neighbors) là một phương pháp phân loại không tạo ra giả định về cấu trúc của mối quan hệ giữa thành viên lớp (Y) và các biến dự báo X₁, X₂,..., Xₙ.
Đây là một phương pháp phi tham số (nonparametric) vì nó không bao gồm ước lượng tham số trong một dạng hàm giả định, bao gồm dạng tuyến tính giả định trong hồi quy tuyến tính. Phương pháp này rút ra dữ liệu từ sự tương đồng giữa các giá trị biến dự báo của dữ liệu trong tập dữ liệu.
Lợi ích của các phương pháp k-NN là tính toàn vẹn (integrity) của chúng và không cần giả định tham số. Khi có một tập huấn luyện lớn, các phương pháp này thực hiện đặc biệt tốt, khi mỗi lớp được đặc trưng bởi một số tổ hợp giá trị biến dự báo.
Ví dụ, trong cơ sở dữ liệu bất động sản, có thể có nhiều tập {loại nhà, số phòng, khu vực, giá yêu cầu, v.v.} đặc trưng cho các nhà bán nhanh so với những nhà ở lại lâu trên thị trường.
Có ba khó khăn với việc khai thác thực tế sức mạnh của phương pháp k-NN.
Mặc dù không cần thời gian để tính tham số từ dữ liệu huấn luyện (như trường hợp các mô hình tham số bao gồm hồi quy), thời gian tìm láng giềng gần nhất trong một tập huấn luyện lớn có thể là hạn chế. Nhiều khái niệm đã được triển khai để vượt qua khó khăn này. Khái niệm chính như sau:
- Có thể giảm thời gian tính khoảng cách bằng cách làm việc trong chiều giảm chiều (reduced dimension) sử dụng kỹ thuật giảm chiều như phân tích thành phần chính (principal components analysis).
- Có thể sử dụng các cấu trúc dữ liệu tinh vi như cây tìm kiếm (search trees) để tăng tốc xác định láng giềng gần nhất. Phương pháp này thường chấp nhận một láng giềng "gần như gần nhất" (almost nearest) để tăng tốc. Một ví dụ là dùng bucketing (chia thành thùng), nơi dữ liệu được gom vào các thùng sao cho dữ liệu trong mỗi thùng gần nhau.
Số lượng dữ liệu cần thiết trong tập huấn luyện để đủ lớn tăng theo cấp số mũ với số lượng biến dự báo p. Điều này là vì khoảng cách kỳ vọng đến láng giềng gần nhất tăng xấu với p trừ khi kích thước tập huấn luyện tăng theo cấp số mũ với p. Hiện tượng này được gọi là nguyền chiều (curse of dimensionality), một vấn đề cơ bản liên quan đến một số phương pháp phân loại, dự đoán và phân cụm.
k-NN là "người học lười biếng" (lazy learner) — Phép tính tốn thời gian bị trì hoãn đến thời điểm dự đoán. Cho mỗi dữ liệu cần dự đoán, nó tính khoảng cách từ toàn bộ tập dữ liệu huấn luyện chỉ tại thời điểm dự đoán. Hành vi này hạn chế sử dụng thuật toán này cho dự đoán thời gian thực nhiều dữ liệu cùng lúc.