Giải thuật k hàng xóm gần nhất

Đừng nhầm lẫn với gom cụm k-means.

Trong thống kê, giải thuật k hàng xóm gần nhất (hay còn gọi là thuật toán k hàng xóm gần nhất, viết tắt từ tiếng Anh k-NN) là một phương pháp thống kê phi tham số (nonparametric statistics) được đề xuất bởi Thomas M. Cover để sử dụng cho phân loại bằng thống kê và phân tích hồi quy.^[1] Cụm từ hàng xóm có thể hiểu là láng giềng hoặc lân cận.

Trong cả hai trường hợp, đầu vào chứa các ví dụ huấn luyện k gần nhất trong không gian thuộc tính (feature space). Đầu ra phụ thuộc vào việc k-NN được dùng cho phân loại hay cho hồi quy:

• Trong phân loại k-NN, đầu ra là một thành viên lớp. Một đối tượng được phân loại theo đa số phiếu bầu của các hàng xóm của nó, với đối tượng được phân vào lớp phổ biến nhất trong số k hàng xóm gần nhất (k là một số nguyên dương, thường có giá trị nhỏ). Nếu k = 1, đối tượng đơn giản được gán cho lớp của hàng xóm đơn gần nhất.

• Trong hồi quy k-NN, đầu ra là một giá trị thuộc tính của đối tượng. Giá trị là giá trị trung bình của các giá trị hàng xóm k gần nhất.

Tham khảo

1. Altman, Naomi S. (1992). “An introduction to kernel and nearest-neighbor nonparametric regression” (PDF). The American Statistician. 46 (3): 175–185. doi:10.1080/00031305.1992.10475879. hdl:1813/31637.

Đọc thêm

• Belur V. Dasarathy biên tập (1991). Nearest Neighbor (NN) Norms: NN Pattern Classification Techniques. ISBN 978-0-8186-8930-7.
• Shakhnarovich, Gregory; Darrell, Trevor; Indyk, Piotr biên tập (2005). Nearest-Neighbor Methods in Learning and Vision. MIT Press. ISBN 978-0-262-19547-8.