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:
Nếu tập
và tập
đều rỗng, mặc định
. Giá trị của
luôn phải thoả mãn điều kiện sau:
Độ 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:
Ý 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:
={Haruka Kudo, Okuyama Kazusa, Noa Tsurushima},
={Okuyama Kazusa, Noa Tsurushima, Chika Osaki},
={Haruka Kudo, Sakurako Okubo, Hiroe Igeta}. Ta có:
Phần Giao | Phần Hợp |
---|---|
={Okuyama Kazusa, Noa Tsurushima} | ={Haruka Kudo, Okuyama Kazusa, Noa Tsurushima, Chika Osaki} |
={} | ={Okuyama Kazusa, Noa Tsurushima, Chika Osaki, Haruka Kudo, Sakurako Okubo, Hiroe Igeta} |
={Haruka Kudo} | ={Okuyama Kazusa, Noa Tsurushima, Haruka Kudo, Sakurako Okubo, Hiroe Igeta} |
Dễ thấy theo
,
,
. Ta thấy điểm tương đồng giữa
và
cao hơn nên có thể lấy diễn viên từ danh sách
để gợi ý cho
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)
1 2 3 4 5 | <span class="token keyword">def</span> <span class="token function">jaccard_similarity</span><span class="token punctuation">(</span>list1<span class="token punctuation">,</span> list2<span class="token punctuation">)</span><span class="token punctuation">:</span> s1 <span class="token operator">=</span> <span class="token builtin">set</span><span class="token punctuation">(</span>list1<span class="token punctuation">)</span> s2 <span class="token operator">=</span> <span class="token builtin">set</span><span class="token punctuation">(</span>list2<span class="token punctuation">)</span> <span class="token keyword">return</span> <span class="token builtin">len</span><span class="token punctuation">(</span>s1<span class="token punctuation">.</span>intersection<span class="token punctuation">(</span>s2<span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token operator">/</span> <span class="token builtin">len</span><span class="token punctuation">(</span>s1<span class="token punctuation">.</span>union<span class="token punctuation">(</span>s2<span class="token punctuation">)</span><span class="token punctuation">)</span> |
Sau khi có hàm trên, chúng ta sẽ thử nghiệm 2 list như sau:
1 2 3 4 | A <span class="token operator">=</span> <span class="token punctuation">[</span><span class="token string">'Haruka Kudo'</span><span class="token punctuation">,</span> <span class="token string">'Okuyama Kazusa'</span><span class="token punctuation">,</span> <span class="token string">'Noa Tsurushima'</span><span class="token punctuation">]</span> B <span class="token operator">=</span> <span class="token punctuation">[</span><span class="token string">'Okuyama Kazusa'</span><span class="token punctuation">,</span> <span class="token string">'Noa Tsurushima'</span><span class="token punctuation">,</span> <span class="token string">'Chika Osaki'</span><span class="token punctuation">]</span> <span class="token keyword">print</span><span class="token punctuation">(</span>jaccard_similarity<span class="token punctuation">(</span>A<span class="token punctuation">,</span> B<span class="token punctuation">)</span><span class="token punctuation">)</span> |
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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 | <span class="token keyword">def</span> <span class="token function">simple_recommender_sys</span><span class="token punctuation">(</span>list1<span class="token punctuation">,</span> list2<span class="token punctuation">,</span> list3<span class="token punctuation">)</span><span class="token punctuation">:</span> J1 <span class="token operator">=</span> jaccard_similarity<span class="token punctuation">(</span>list1<span class="token punctuation">,</span> list2<span class="token punctuation">)</span> J2 <span class="token operator">=</span> jaccard_similarity<span class="token punctuation">(</span>list2<span class="token punctuation">,</span> list3<span class="token punctuation">)</span> J3 <span class="token operator">=</span> jaccard_similarity<span class="token punctuation">(</span>list3<span class="token punctuation">,</span> list1<span class="token punctuation">)</span> <span class="token keyword">if</span> J1 <span class="token operator">></span> J2<span class="token punctuation">:</span> <span class="token keyword">if</span> J1 <span class="token operator">></span> J3<span class="token punctuation">:</span> <span class="token keyword">print</span><span class="token punctuation">(</span><span class="token string">"["</span><span class="token punctuation">,</span>list1<span class="token punctuation">,</span><span class="token string">", "</span><span class="token punctuation">,</span>list2<span class="token punctuation">,</span><span class="token string">"]"</span><span class="token punctuation">)</span> <span class="token keyword">elif</span> J1 <span class="token operator">==</span> J3<span class="token punctuation">:</span> <span class="token keyword">print</span><span class="token punctuation">(</span><span class="token string">"["</span><span class="token punctuation">,</span>list1<span class="token punctuation">,</span><span class="token string">", "</span><span class="token punctuation">,</span>list2<span class="token punctuation">,</span><span class="token string">"], ["</span><span class="token punctuation">,</span>list1<span class="token punctuation">,</span><span class="token string">", "</span><span class="token punctuation">,</span>list3<span class="token punctuation">,</span><span class="token string">"]"</span><span class="token punctuation">)</span> <span class="token keyword">else</span><span class="token punctuation">:</span> <span class="token keyword">print</span><span class="token punctuation">(</span><span class="token string">"["</span><span class="token punctuation">,</span>list1<span class="token punctuation">,</span><span class="token string">", "</span><span class="token punctuation">,</span>list3<span class="token punctuation">,</span><span class="token string">"]"</span><span class="token punctuation">)</span> <span class="token keyword">elif</span> J1 <span class="token operator">==</span> J2<span class="token punctuation">:</span> <span class="token keyword">if</span> J1 <span class="token operator">></span> J3<span class="token punctuation">:</span> <span class="token keyword">print</span><span class="token punctuation">(</span><span class="token string">"["</span><span class="token punctuation">,</span>list1<span class="token punctuation">,</span><span class="token string">", "</span><span class="token punctuation">,</span>list2<span class="token punctuation">,</span><span class="token string">"], ["</span><span class="token punctuation">,</span>list2<span class="token punctuation">,</span><span class="token string">", "</span><span class="token punctuation">,</span>list3<span class="token punctuation">,</span><span class="token string">"]"</span><span class="token punctuation">)</span> <span class="token keyword">elif</span> J1 <span class="token operator">==</span> J3<span class="token punctuation">:</span> <span class="token keyword">print</span><span class="token punctuation">(</span><span class="token string">"["</span><span class="token punctuation">,</span>list1<span class="token punctuation">,</span><span class="token string">", "</span><span class="token punctuation">,</span>list2<span class="token punctuation">,</span><span class="token string">"], ["</span><span class="token punctuation">,</span>list2<span class="token punctuation">,</span><span class="token string">", "</span><span class="token punctuation">,</span>list3<span class="token punctuation">,</span><span class="token string">"], ["</span><span class="token punctuation">,</span>list1<span class="token punctuation">,</span><span class="token string">", "</span><span class="token punctuation">,</span>list3<span class="token punctuation">,</span><span class="token string">"]"</span><span class="token punctuation">)</span> <span class="token keyword">else</span><span class="token punctuation">:</span> <span class="token keyword">print</span><span class="token punctuation">(</span><span class="token string">"["</span><span class="token punctuation">,</span>list1<span class="token punctuation">,</span><span class="token string">", "</span><span class="token punctuation">,</span>list3<span class="token punctuation">,</span><span class="token string">"]"</span><span class="token punctuation">)</span> <span class="token keyword">elif</span> J1 <span class="token operator"><</span> J2<span class="token punctuation">:</span> <span class="token keyword">if</span> J2 <span class="token operator">></span> J3<span class="token punctuation">:</span> <span class="token keyword">print</span><span class="token punctuation">(</span><span class="token string">"["</span><span class="token punctuation">,</span>list2<span class="token punctuation">,</span><span class="token string">", "</span><span class="token punctuation">,</span>list3<span class="token punctuation">,</span><span class="token string">"]"</span><span class="token punctuation">)</span> <span class="token keyword">elif</span> J2 <span class="token operator">==</span> J3<span class="token punctuation">:</span> <span class="token keyword">print</span><span class="token punctuation">(</span><span class="token string">"["</span><span class="token punctuation">,</span>list2<span class="token punctuation">,</span><span class="token string">", "</span><span class="token punctuation">,</span>list3<span class="token punctuation">,</span><span class="token string">"], ["</span><span class="token punctuation">,</span>list1<span class="token punctuation">,</span><span class="token string">", "</span><span class="token punctuation">,</span>list3<span class="token punctuation">,</span><span class="token string">"]"</span><span class="token punctuation">)</span> <span class="token keyword">else</span><span class="token punctuation">:</span> <span class="token keyword">print</span><span class="token punctuation">(</span><span class="token string">"["</span><span class="token punctuation">,</span>list1<span class="token punctuation">,</span><span class="token string">", "</span><span class="token punctuation">,</span>list3<span class="token punctuation">,</span><span class="token string">"]"</span><span class="token punctuation">)</span> simple_recommender_sys<span class="token punctuation">(</span>A<span class="token punctuation">,</span> B<span class="token punctuation">,</span> C<span class="token punctuation">)</span> |
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
1 2 3 4 5 | <span class="token comment"># import the necessary packages</span> <span class="token keyword">from</span> collections <span class="token keyword">import</span> namedtuple <span class="token keyword">import</span> numpy <span class="token keyword">as</span> np <span class="token keyword">import</span> cv2 |
Và để đựng các vật thể trong hộp như trên, thuật toán được viết như sau:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | <span class="token keyword">def</span> <span class="token function">jaccard_similarity</span><span class="token punctuation">(</span>boxA<span class="token punctuation">,</span> boxB<span class="token punctuation">)</span><span class="token punctuation">:</span> <span class="token comment"># determine the (x, y)-coordinates of the intersection rectangle</span> xA <span class="token operator">=</span> <span class="token builtin">max</span><span class="token punctuation">(</span>boxA<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">,</span> boxB<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">)</span> yA <span class="token operator">=</span> <span class="token builtin">max</span><span class="token punctuation">(</span>boxA<span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">,</span> boxB<span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">)</span> xB <span class="token operator">=</span> <span class="token builtin">min</span><span class="token punctuation">(</span>boxA<span class="token punctuation">[</span><span class="token number">2</span><span class="token punctuation">]</span><span class="token punctuation">,</span> boxB<span class="token punctuation">[</span><span class="token number">2</span><span class="token punctuation">]</span><span class="token punctuation">)</span> yB <span class="token operator">=</span> <span class="token builtin">min</span><span class="token punctuation">(</span>boxA<span class="token punctuation">[</span><span class="token number">3</span><span class="token punctuation">]</span><span class="token punctuation">,</span> boxB<span class="token punctuation">[</span><span class="token number">3</span><span class="token punctuation">]</span><span class="token punctuation">)</span> <span class="token comment"># compute the area of intersection rectangle</span> interArea <span class="token operator">=</span> <span class="token builtin">max</span><span class="token punctuation">(</span><span class="token number">0</span><span class="token punctuation">,</span> xB <span class="token operator">-</span> xA <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">)</span> <span class="token operator">*</span> <span class="token builtin">max</span><span class="token punctuation">(</span><span class="token number">0</span><span class="token punctuation">,</span> yB <span class="token operator">-</span> yA <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">)</span> <span class="token comment"># compute the area of both the prediction and ground-truth</span> <span class="token comment"># rectangles</span> boxAArea <span class="token operator">=</span> <span class="token punctuation">(</span>boxA<span class="token punctuation">[</span><span class="token number">2</span><span class="token punctuation">]</span> <span class="token operator">-</span> boxA<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span> <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">)</span> <span class="token operator">*</span> <span class="token punctuation">(</span>boxA<span class="token punctuation">[</span><span class="token number">3</span><span class="token punctuation">]</span> <span class="token operator">-</span> boxA<span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span> <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">)</span> boxBArea <span class="token operator">=</span> <span class="token punctuation">(</span>boxB<span class="token punctuation">[</span><span class="token number">2</span><span class="token punctuation">]</span> <span class="token operator">-</span> boxB<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span> <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">)</span> <span class="token operator">*</span> <span class="token punctuation">(</span>boxB<span class="token punctuation">[</span><span class="token number">3</span><span class="token punctuation">]</span> <span class="token operator">-</span> boxB<span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span> <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">)</span> <span class="token comment"># compute the Jaccard Index value by taking the intersection</span> <span class="token comment"># area and dividing it by the sum of prediction + ground-truth</span> <span class="token comment"># areas - the interesection area</span> jaccard_index <span class="token operator">=</span> interArea <span class="token operator">/</span> <span class="token builtin">float</span><span class="token punctuation">(</span>boxAArea <span class="token operator">+</span> boxBArea <span class="token operator">-</span> interArea<span class="token punctuation">)</span> <span class="token comment"># return the Jaccard Index value value</span> <span class="token keyword">return</span> jaccard_index |
Ở 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à
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 | <span class="token comment"># define the list of example detections</span> examples <span class="token operator">=</span> <span class="token punctuation">[</span> Detection<span class="token punctuation">(</span><span class="token string">"demo.jpg"</span><span class="token punctuation">,</span> <span class="token punctuation">[</span><span class="token number">39</span><span class="token punctuation">,</span> <span class="token number">63</span><span class="token punctuation">,</span> <span class="token number">203</span><span class="token punctuation">,</span> <span class="token number">112</span><span class="token punctuation">]</span><span class="token punctuation">,</span> <span class="token punctuation">[</span><span class="token number">54</span><span class="token punctuation">,</span> <span class="token number">66</span><span class="token punctuation">,</span> <span class="token number">198</span><span class="token punctuation">,</span> <span class="token number">114</span><span class="token punctuation">]</span><span class="token punctuation">)</span> <span class="token punctuation">]</span> <span class="token comment"># loop over the example detections</span> <span class="token keyword">for</span> detection <span class="token keyword">in</span> examples<span class="token punctuation">:</span> <span class="token comment"># load the image</span> image <span class="token operator">=</span> cv2<span class="token punctuation">.</span>imread<span class="token punctuation">(</span>detection<span class="token punctuation">.</span>image_path<span class="token punctuation">)</span> <span class="token comment"># draw the ground-truth bounding box along with the predicted</span> <span class="token comment"># bounding box</span> cv2<span class="token punctuation">.</span>rectangle<span class="token punctuation">(</span>image<span class="token punctuation">,</span> <span class="token builtin">tuple</span><span class="token punctuation">(</span>detection<span class="token punctuation">.</span>gt<span class="token punctuation">[</span><span class="token punctuation">:</span><span class="token number">2</span><span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">,</span> <span class="token builtin">tuple</span><span class="token punctuation">(</span>detection<span class="token punctuation">.</span>gt<span class="token punctuation">[</span><span class="token number">2</span><span class="token punctuation">:</span><span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">,</span> <span class="token punctuation">(</span><span class="token number">0</span><span class="token punctuation">,</span> <span class="token number">255</span><span class="token punctuation">,</span> <span class="token number">0</span><span class="token punctuation">)</span><span class="token punctuation">,</span> <span class="token number">2</span><span class="token punctuation">)</span> cv2<span class="token punctuation">.</span>rectangle<span class="token punctuation">(</span>image<span class="token punctuation">,</span> <span class="token builtin">tuple</span><span class="token punctuation">(</span>detection<span class="token punctuation">.</span>pred<span class="token punctuation">[</span><span class="token punctuation">:</span><span class="token number">2</span><span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">,</span> <span class="token builtin">tuple</span><span class="token punctuation">(</span>detection<span class="token punctuation">.</span>pred<span class="token punctuation">[</span><span class="token number">2</span><span class="token punctuation">:</span><span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">,</span> <span class="token punctuation">(</span><span class="token number">0</span><span class="token punctuation">,</span> <span class="token number">0</span><span class="token punctuation">,</span> <span class="token number">255</span><span class="token punctuation">)</span><span class="token punctuation">,</span> <span class="token number">2</span><span class="token punctuation">)</span> <span class="token comment"># compute the Jaccard Index value and display it</span> jaccard_index <span class="token operator">=</span> jaccard_similarity<span class="token punctuation">(</span>detection<span class="token punctuation">.</span>gt<span class="token punctuation">,</span> detection<span class="token punctuation">.</span>pred<span class="token punctuation">)</span> cv2<span class="token punctuation">.</span>putText<span class="token punctuation">(</span>image<span class="token punctuation">,</span> <span class="token string">"Jaccard index: {:.4f}"</span><span class="token punctuation">.</span><span class="token builtin">format</span><span class="token punctuation">(</span>jaccard_index<span class="token punctuation">)</span><span class="token punctuation">,</span> <span class="token punctuation">(</span><span class="token number">10</span><span class="token punctuation">,</span> <span class="token number">30</span><span class="token punctuation">)</span><span class="token punctuation">,</span> cv2<span class="token punctuation">.</span>FONT_HERSHEY_SIMPLEX<span class="token punctuation">,</span> <span class="token number">0.6</span><span class="token punctuation">,</span> <span class="token punctuation">(</span><span class="token number">0</span><span class="token punctuation">,</span> <span class="token number">255</span><span class="token punctuation">,</span> <span class="token number">0</span><span class="token punctuation">)</span><span class="token punctuation">,</span> <span class="token number">2</span><span class="token punctuation">)</span> <span class="token keyword">print</span><span class="token punctuation">(</span><span class="token string">"{}: {:.4f}"</span><span class="token punctuation">.</span><span class="token builtin">format</span><span class="token punctuation">(</span>detection<span class="token punctuation">.</span>image_path<span class="token punctuation">,</span> jaccard_index<span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token comment"># show the output image</span> cv2<span class="token punctuation">.</span>imshow<span class="token punctuation">(</span><span class="token string">"Image"</span><span class="token punctuation">,</span> image<span class="token punctuation">)</span> cv2<span class="token punctuation">.</span>waitKey<span class="token punctuation">(</span><span class="token number">0</span><span class="token punctuation">)</span> |
Đâ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/