Giải thuật Jaccard

Tram Ho

Xin chào mọi người. Lâu lắm rồi mới ngoi lên. Và trong bài này mình sẽ viết về 1 thuật toán được ứng dụng khá nhiều trong các chủ đề AI hay ML là Giải thuật Jaccard(hay gọi tiếng Anh là Jaccard Index). Để tag ML ở bài này cũng hơi láo nhưng bí quá không biết tag gì. Mọi người bỏ qua cho mình.

Khái niệm

Giải thuật Chỉ mục Jaccard, hay còn gọi là giải thuật tỉ lệ của giữa phần giao và phần hợp của 2 tập hợp(có thể gọi tắt hơn nữa nhưng mà….), là 1 giải thuật được đưa ra bởi nhà Toán học Pháp Paul Jaccard. Như đã nói ở trên, giải thuật này là kết quả tính toán độ tương đồng giữa giao của 2 tập hợp và hợp của 2 tập hợp, được tính toán như sau:

J(A,B)=∣A∩B∣∣A∪B∣=∣A∩B∣∣A∣+∣B∣−∣A∩B∣J(A,B)=frac{|A∩B|}{|A∪B|}=frac{|A∩B|}{|A|+|B|-|A∩B|}

Nếu tập

AA

và tập

BB

đều rỗng, mặc định

J(A,B)=1J(A,B) = 1

J(A,B)J(A,B)

0⩽J(A,B)⩽10⩽J(A,B) ⩽1

Độ rời rạc Jaccard lại là để đo tỉ lệ độ rời rạc giữa giao và hợp của 2 tập hợp, được tính bằng cách:

dJ(A,B)=1−J(A,B)=∣A∪B∣−∣A∩B∣∣A∪B∣d_J(A, B)=1-J(A,B)=frac{|A∪B|-|A∩B|}{|A∪B|}

Ý nghĩa

Vậy cái đống công thức toán trên có ý nghĩa gì. Hãy nhìn ảnh sau:

Trong ảnh chúng ta có 2 vùng: vùng xanh là vùng đối tượng thật(gọi là kết quả), vùng đỏ là vùng dự đoán. Muốn dự đoán tốt thì cần phải nhận diện vật thể tốt. 2 vùng này sẽ luôn giao nhau và tổng diện tích sẽ giảm dần. Còn diện tích vùng chung của 2 vùng sẽ tăng dần. Ở đây rõ ràng vùng chung càng lớn thì độ chính xác càng cao, nhưng kéo theo đó diện tích tổng sẽ giảm dần. Chính vì thế J(A, B) càng lớn thì phần tử số sẽ lớn, phần mẫu số sẽ nhỏ. Và phân số này sẽ lớn nhất bằng 1 khi 2 vùng xanh đỏ trùng khớp nhau, và nhỏ nhất bằng 0 khi 2 vùng này hoàn toàn không giao nhau.

Văn phong có vẻ hơi lằng nhằng nhưng bên trên chính là ứng dụng của Jaccard trong object detection. Ngoài ra, Jaccard cũng có thể được ứng dụng trong Recommendation System. Có 3 danh sách diễn viên sau:

AA

={Haruka Kudo, Okuyama Kazusa, Noa Tsurushima},

BB

={Okuyama Kazusa, Noa Tsurushima, Chika Osaki},

CC

={Haruka Kudo, Sakurako Okubo, Hiroe Igeta}. Ta có:

Phần GiaoPhần Hợp

A∩BA∩B

A∪BA∪B

B∩CB∩C

B∪CB∪C

A∩CA∩C

A∪CA∪C

Dễ thấy theo

J(A,B)=2/4=0.5J(A,B)=2/4=0.5

J(B,C)=0/6=0J(B,C)=0/6=0

J(A,C)=1/5=0.2J(A,C)=1/5=0.2

AA

và

BB

cao hơn nên có thể lấy diễn viên từ danh sách

AA

để gợi ý cho

BB

và ngược lại.

Triển khai với code 1

Và sau 1 hồi lý thuyết Toán ở trên(và vài phút để các bạn tra cứu mấy cái tên trên nữa🤣🤣), chúng ta sẽ cùng thử xem triển khai của Jaccard ở trong code như thế nào. Và lần này chúng ta sẽ quay lại 2 ví dụ trên nhưng thứ tự sẽ khác đi. 3 danh sách kia sẽ được chuyển thành 3 mảng A, B, C. Nhiệm vụ chúng ta cần làm ở đây là triển khai thuật toán và đưa ra các cặp có độ tương đồng cao nhất.

Đầu tiên là việc cài đặt thuật toán. Việc này khá đơn giản(thực ra cũng có hàm jaccard có sẵn trong python rồi, nhưng chúng ta sẽ thử cài đặt từ đầu)

Sau khi có hàm trên, chúng ta sẽ thử nghiệm 2 list như sau:

Và đây là kết quả đạt được. Đúng chuẩn công thức tính toán

Bước tiếp theo cũng đơn giản. Cần vài câu lệnh điều kiện là ổn. Và thế là chúng ta làm tạm đoạn code bẩn sau

Kết quả là A và B được in ra thế này. Trông không đẹp lắm. Nhưng thôi. Đến đây là chúng ta đã xây được 1 hệ gợi ý con con với 3 phần tử rồi. Lên N phần tử các bạn tự tổng quát nhé

Triển khai với code 2

Vâng. Giờ quay lại bài toán object detection.

Trước hết chúng ta sẽ thêm các thư viện cần thiết

Và để đựng các vật thể trong hộp như trên, thuật toán được viết như sau:

Ở phần demo, mình lấy tạm 1 cái ảnh nền trắng và vẽ 2 cái hộp ra. Sơ lược hướng dẫn thôi mà

Đây là kết quả thu được

Kết bài

Ở bài này, mình chỉ mới giới thiệu các bạn 1 trong các thuật toán được đưa vào trong AI/ML cũng như đào 1 tí về bản chất toán học của AI. Đây là link source code của mình: https://github.com/BlazingRockStorm/Jaccard_Index_Algorithm

Tham khảo

https://en.wikipedia.org/wiki/Jaccard_index
https://www.pyimagesearch.com/2016/11/07/intersection-over-union-iou-for-object-detection/

Chia sẻ bài viết ngay

Nguồn bài viết : Viblo