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 chứa ước lượng các tham số ở dạng hàm giả định, bao gồm cả dạng tuyến tính giả định trong hồi quy tuyến tính. Phương pháp này lấy dữ liệu từ các đ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.
Lợi ích của các phương pháp k-NN là tính toàn vẹn của chúng và không cần các giả định tham số. Với sự hiện diện của một tập hợp đào tạo khổng lồ, các phương pháp này hoạt động đặc biệt tốt, khi mỗi lớp được đặc trưng bởi một số kết hợp các giá trị dự đoán.
Ví dụ:trong cơ sở dữ liệu bất động sản, có thể có một số tập hợp {loại nhà, số phòng, vùng lân cận, giá chào bán, v.v.} đặc trưng cho những ngôi nhà bán nhanh so với những ngôi nhà duy trì trong thời gian cao ngành.
Có ba khó khăn khi khai thác sức mạnh của phương pháp k-NN một cách thực tế.
Mặc dù không cần thời gian để tính toán các tham số từ dữ liệu huấn luyện (như trường hợp của các mô hình tham số bao gồm hồi quy), thời gian để phát hiện ra các láng giềng gần nhất trong một tập huấn luyện khổng lồ có thể bị hạn chế. Nhiều khái niệm đã được thực hiện để vượt qua khó khăn này. Khái niệm chính như sau -
-
Nó có thể giảm thời gian cần thiết để tính toán khoảng cách bằng cách làm việc trong một thứ nguyên giảm bằng cách sử dụng các kỹ thuật giảm thứ nguyên, chẳng hạn như phân tích các thành phần chính.
-
Nó có thể sử dụng các cấu trúc dữ liệu phức tạp như cây tìm kiếm để tăng tốc độ xác định người hàng xóm gần nhất. Phương pháp này thường giải quyết cho một người hàng xóm “gần như gần nhất” để tăng cường tốc độ. Một trường hợp đang sử dụng bucketing, trong đó dữ liệu được kết hợp thành các nhóm để dữ liệu bên trong mỗi nhóm gần nhau.
Nhiều dữ liệu cần thiết trong tập huấn luyện để đủ điều kiện là lớn sẽ tăng theo cấp số nhân với p của nhiều dự đoán. Điều này là do khoảng cách dự kiến đến người hàng xóm gần nhất sẽ tăng xấu với p trừ khi số lượng của tập huấn luyện tăng lên theo cấp số nhân với p. Hiện tượng này được gọi là lời nguyền về chiều, 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 nhóm.
k-NN là "kẻ lười học" - Việc tính toán tốn nhiều thời gian bị trễ so với thời điểm dự đoán. Đối với mỗi dữ liệu được dự đoán, nó có thể tính toán khoảng cách của nó với toàn bộ 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ế việc sử dụng thuật toán này để dự đoán thời gian thực cho nhiều dữ liệu đồng thời.