Thuật toán k-hàng xóm gần nhất là một cách tiếp cận phân loại không tạo ra các 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 yếu tố dự đoán X 1 , X 2 ,…. X n .
Đây là một phương pháp tiếp cận phi tham số vì nó không bao gồm ước lượng các tham số ở dạng hàm giả, bao gồm dạng tuyến tính giả trong hồi quy tuyến tính. Cách tiếp cận này thu thập dữ liệu từ những điểm tương đồng giữa các giá trị dự đoán của dữ liệu trong tập dữ liệu.
Khái niệm trong phương pháp k-gần nhất-láng giềng là nhận ra k bản ghi trong tập dữ liệu huấn luyện giống với dữ liệu mới mà nó được yêu cầu để phân loại. Nó có thể sử dụng các bản ghi tương tự (lân cận) này để xác định bản ghi mới thành một lớp, tạo dữ liệu mới cho lớp chiếm ưu thế giữa các lớp láng giềng này. Nó chỉ ra các giá trị của các yếu tố dự đoán cho bản ghi mới này bởi X 1 , X 2 ,…. X n .
Một câu hỏi trọng tâm là làm thế nào để tính toán khoảng cách giữa các dữ liệu tùy thuộc vào các giá trị dự đoán của chúng. Thước đo khoảng cách nổi tiếng là khoảng cách Euclide. Khoảng cách Euclid giữa hai bản ghi (X 1 , X 2 ,…. X n ) và (U 1 , U 2 ,…. U n ) 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 một số phép tính khoảng cách (giữa mỗi dữ liệu được dự báo và mỗi dữ liệu trong tập huấn luyện), và do đó, khoảng cách Euclide, được tính toán không tốn kém, là khoảng cách phổ biến nhất trong k-NN.
Nó có thể cân bằng các thang đo mà một số yếu tố dự đoán có thể có, trong hầu hết các trường hợp, các yếu tố dự báo phải được tiêu chuẩn hóa trước khi tính toán khoảng cách Euclide. Các phương tiện và độ lệch chuẩn có thể chuẩn hóa dữ liệu mới là phương tiện của dữ liệu huấn luyện và dữ liệu mới không liên quan đến việc tính toán chúng. Dữ liệu xác thực, chẳng hạn như dữ liệu mới, cũng không liên quan đến tính toán này.
Sau khi tính toán khoảng cách giữa dữ liệu được xác định và các bản ghi hiện tại, cần có quy tắc để gán một lớp cho bản ghi được phân loại, tùy thuộc vào các lớp của các hàng xóm của nó.
Trường hợp đơn giản nhất là k =1, trong đó chúng tôi tìm kiế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 là thuộc về lớp bằng với láng giềng gần nhất của nó.
Có một thực tế phi thường là khái niệm đơn giản, dễ hiểu này về việc sử dụng một láng giềng gần nhất duy nhất để phân loại các bản ghi có thể mạnh khi chúng ta có nhiều bản ghi trong tập huấn luyện. Nó thay đổi rằng lỗi 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á hai lần lỗi khi nó có thể hiểu chính xác các hàm mật độ xác suất cho mỗi lớp.