Pattern Recognition - Nearest neighbor algorithm

Giải thuật người hàng xóm gần nhất trong nhận dạng mẫu là một phương pháp để phân loại các hiện tượng dựa trên các đặc trưng quan sát được.

Trong giải thuật, mỗi đặc trưng được gán cho một chiều để tạo thành một không gian đặc trưng đa chiều. Một tập huấn luyện các đối tượng với lớp (class) đã biết trước (đã phân loại sẵn) sẽ được xử lí bằng cách trích rút đặc trưng (lấy ra một số đặc trưng) và được biểu diễn (vẽ sơ đồ) vào trong không gian đặc trưng đa chiều đó. Khoảng cách đến gốc (offset) trong mỗi chiều được xem là vec-tơ đặc trưng . Đây là giai đoạn huấn luyện hay học. Vì động cơ có thể được huấn luyện lại để phân loại nhiều hiện tượng khác nhau, nhận dạng mẫu là một phần của ngành học máy.

Giai đoạn kiểm tra bắt đầu với các hiện tượng (phenomena) cần phân loại (lớp của từng hiện tượng chưa được biết trước) và trích rút ra cùng tập các đặc trưng như với tập huấn luyện. Khoảng cách hình học được tính toán giữa vec-tơ đặc trưng mới với mỗi vec-tơ đặc trưng có sẵn từ tập huấn luyện. Khoảng cách ngắn nhất tính toán được, đến vec-tơ đặc trưng trong tập huấn luyện, chính là họ hàng gần nhất. Và lớp (loại) biết trướccủa họ hàng gần nhất đó sẽ cũng là lớp của hiện tượng mà ta đang cần phân loại.

Hiển nhiên, giải thuật này sẽ đòi hỏi cường độ tính toán cao khi tập huấn luyên trở nên lớn. Nhiều sự tối ưu đã và đang được đưa ra, chúng chủ yếu tìm kiếm nhằm giảm số lượng khoảng cách được thực sự tính toán. Một số tối ưu bao gồm phân hoạch không gian đặc trưng, và chỉ tính các khoảng cách với các vec-tơ thuộc một vùng lân cận cụ thể nào đó.

Một số biến thể khác của giải thuật bao gồm giải thuật k hàng xóm gần nhất với k vec-tơ đặc trưng gần nhất sẽ được tính toán, và việc phân loại sẽ dựa vào độ tin cậy cao nhất chỉ khi mọi mọi hàng xóm gần nhất đó nều cùng thuộc một loại (lớp).

Người hàng xóm gần nhất cho ra một số kết quả ổn định vững chắc. Vì số lượng dữ liệu tiếp cận được xem là vô hạn, người hàng xóm gần nhất đảm bảo cho ra tỉ lệ lỗi không vượt quá hai lầntỉ lệ lỗi Bayes (là tỉ lệ lỗi đạt được tối thiểu khi biết sự phân bố dữ liệu). k-người hàng xóm gần nhất được đảm bảo là sẽ tiến tới tỉ lệ lỗi Bayes, với một giá trị nào đó của k.

Nguồn http://vi.wikipedia.org