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.
Ý tưởng trong phương pháp k-láng giềng gần nhất là nhận diện k bản ghi trong tập dữ liệu huấn luyện giống nhất với dữ liệu mới cần phân loại. Có thể dùng các bản ghi tương tự (láng giềng) này để phân loại bản ghi mới vào một lớp, gán dữ liệu mới cho lớp chiếm ưu thế giữa các láng giềng này. Nó chỉ ra các giá trị của các biến dự báo cho bản ghi mới này bằng X₁, X₂,..., Xₙ.
Một câu hỏi trung tâm là làm thế nào để tính khoảng cách giữa dữ liệu tùy thuộc vào giá trị biến dự báo của chúng. Đo lường khoảng cách nổi tiếng là khoảng cách Euclid (Euclidean distance). Khoảng cách Euclid giữa hai bản ghi (X₁, X₂,..., Xₙ) và (U₁, U₂,..., Uₙ) là:
$$\mathrm{\sqrt{(X_1-U_1)^2+(X_2-U_2)^2+...+(X_n-U_n)^2}}$$
Thuật toán k-NN phụ thuộc vào nhiều phép tính khoảng cách (giữa mỗi dữ liệu cần dự báo và mỗi dữ liệu trong tập huấn luyện), và do đó khoảng cách Euclid, vốn rẻ về mặt tính toán, là phổ biến nhất trong k-NN.
Có thể cân bằng các thang đo mà các biến dự báo khác nhau có thể có, trong hầu hết các trường hợp, các biến dự báo phải được chuẩn hóa (standardized) trước khi tính khoảng cách Euclid. Các trung bình và độ lệch chuẩn dùng để chuẩn hóa dữ liệu mới là của dữ liệu huấn luyện, và dữ liệu mới không tham gia vào việc tính chúng. Dữ liệu xác thực, như dữ liệu mới, cũng không tham gia vào tính toán này.
Sau khi tính khoảng cách giữa dữ liệu cần phân loại và các bản ghi hiện có, cần một quy tắc để gán lớp cho bản ghi cần phân loại, tùy thuộc vào các lớp của các láng giềng của nó.
Trường hợp đơn giản nhất là k = 1, nơi chúng ta tìm dữ liệu gần nhất (láng giềng gần nhất) và phân loại dữ liệu mới thuộc cùng lớp với láng giềng gần nhất của nó.
Đây là một факт bất thường rằng ý tưởng đơn giản, trực quan này dùng một láng giềng gần nhất đơn lẻ để phân loại bản ghi có thể mạnh mẽ khi chúng ta có nhiều bản ghi trong tập huấn luyện. Nó ra là tỷ lệ phân loại sai của thiết kế 1-láng giềng gần nhất có tỷ lệ phân loại sai không quá gấp đôi lỗi khi có thể hiểu chính xác các hàm mật độ xác suất cho mỗi lớp.