Nearest Neighbor Classifier

Khái niệm

Thuật toán đầu tiên mà chúng ta học là Nearest Neighbor Classifier. Tiếng việt được gọi là người láng giềng gần nhất, nhưng đôi khi cũng được gọi là người hàng xóm kế bên… Riêng mình, mình thích gọi là “NN”. Vậy NN là gì? Đơn giản mà hiểu:

Nearest Neighbor Classifier là phương pháp mà bạn dự đoán nhãn của 1 đối tượng dựa vào nhãn của đối tượng gần nó nhất.

Hơi khó hiểu phải không. Lấy ví dụ như này cho đơn giản nà. Trong một lớp có 3 thằng tên : Nam, Man, Men. Bây giờ có 1 thằng A bước vào lớp, cô giáo đố bạn tên thằng đó là gì? Khó quá phải ko? Bạn đang tính nói: “em ko biết”. Thế là cô giáo nhanh miệng đưa ra gợi ý: “Tên thằng này giống với tên của 1 trong 3 thằng còn lại”. Và bây giờ đáp án có vẻ dễ dàng hơn rồi. Bạn có thể dùng thuật toán NN để đoán bằng cách: Thằng A nó đứng gần thằng nào nhất thì tên thằng A sẽ là tên thằng đó. Và bạn thấy thằng A đứng gần thằng Nam nhất => thằng A tên Nam. Đấy, đấy chính là “người láng giềng gần nhất”. Thuật toán nghe có vẻ thiệt xàm xí đúng ko? Thực ra không phải đâu, với những bức ảnh giống nhau thì khoảng cách (Distance) được tính ra giữa 2 bức ảnh đó sẽ có giá trị thấp. Điều này dẫn tới việc áp dụng NN trong hình ảnh đạt hiệu quả rất tốt.

Cách tính khoảng cách

Như đã được hiểu ở trên, thuật toán NN là thuật toán dự đoán nhãn của một đối tượng dựa vào nhãn của đối tượng gần nó nhất. Vậy làm sao để biết 2 đối tượng gần nhau hay xa nhau. Tất nhiên, chúng ta có những độ đo riêng để đo khoảng cách của 2 đối tượng. Nhưng trong bài này, mình chỉ giới thiệu về 2 độ đo cơ bản: Manhattan, Euclidean

Manhattan Distance

Đầu tiên và đơn giản nhất là độ đo khoảng cách Manhattan. Cho 2 điểm A(x1,y1) và B(x2,y2) trong cùng một mặt phẳng. Khoảng cách Manhattan được tính bằng: Manhattan : D = |x2-x1|+|y2-y1| Tương tự với các điểm trong không gian xyz: A(x1,y1,z1) và B(x2,y2,z2) thì D = |x2-x1| + |y2-y1| + |z2-z1|.Để áp dụng manhattan cho việc tính khoảng cách giữa 2 bức hình, ta có thể tưởng tượng như sau. Với 2 bức hình đầu vào có kích thước 4*4 pixel. Khoảng cách giữa 2 bức hình là tổng khoảng cách giữa các pixel tương ứng giữa 2 bức hình. Công thức tổng quát có thể viết tương ứng như sau: d1(I1,I2)=∑p|Ip2−Ip1| Trong đó: Ip1 và Ip2 lần lượt là các điểm ảnh trên bức hình 1 và bức hình 2.

Euclidean Distance

Với 2 điểm A(x1,y1) và B(x2,y2) trong cùng một mặt phẳng. Khoảng cách Euclidean được tính bằng: Eucliean : D = √(x2 - x1)² + (y2-y1)²Tương tự với các điểm trong không gian xyz: A(x1,y1,z1) và B(x2,y2,z2) thì D = √(x2 - x1)² + (y2-y1)²+ (z2-z1)².Công thức tổng quát cho khoảng cách giữa 2 bức hình dựa trên độ đo euclidean được biểu diễn như sau: d1(I1,I2)= ∑p√(Ip2 - Ip1)² .