Đặt vấn đề

Giả sử bạn và tôi đều thích nghe nhạc trên trang mp3.zing.vn. Mỗi người đều nghe khoảng 100 bài nhạc khác nhau. Để đo sự giống nhau giữa danh sách bài hát bạn nghe và danh sách bài hát tôi nghe, thông thường chúng ta sẽ dùng độ đo Jaccard Similarity, được đo bằng cách lấy phần giao (intersection ) chia cho phần hợp (union). Nghĩa là đếm số lượng bài hát cả hai cùng nghe (phần giao) chia cho tổng số bài hát không lặp của cả hai.

Trong trường hợp bạn và tôi đều nghe 100 bài, trong đó có 30 bài giống nhau, vậy phần giao là 30, phần hợp là 170, giá trị Jaccard Similarity sẽ là 30/170.

Độ đo Jaccard Similarity được sử dụng ở phương pháp apriori , FP Growth, … mà các bạn đã có dịp học trong môn khai phá dữ liệu ở Đại học.

Bài toán tìm kiếm văn bản tương đồng

Giả sử bạn quản lý một số lượng lớn văn bản (N= 1 tỷ), và xếp của bạn có nhu cầu nhóm những bài viết giống nhau thành từng cụm. Để:

• Loại bỏ bớt những kết quả trùng trong khung search.

• Nhóm những bài viết vào từng nhóm sự kiện theo dòng thời gian, ví dụ sự kiện ‘cô gái giao gà’, sự kiện ‘dịch cúm corona’, …

• Vì một bất kể lý do nào đó mà trong lúc viết bài này tác giả chưa nghĩ ra.

Khi đó, các vấn đều sau có thể sẽ phát sinh:

• Nhiều phần nhỏ của văn bản này xuất hiện ở một vị trí lộn xộn nào ở một hoặc nhiều văn bản khác.

• Văn bản quá dài nên không thể lưu trữ hết lên bộ nhớ chính (RAM).

• Có quá nhiều cặp văn bản cần phải so sánh.

Để giải quyết bài toán trên, chúng ta sẽ tiếp cận theo hướng sau:

• Shingling: Chuyển văn bản thành tập ký tự, tập từ ….

• Min-Hashing: Chuyển tập ký tự thành 1 chuỗi số hash định danh.

• Locality-Sensitive Hashing: Tìm các văn bản tương đồng dựa vào chuỗi số định danh.

Ở bài viết này, mình chỉ đề cập bước thứ 2 là Min-Hashing. Bước 1 và bước 3 bạn có thể tham khảo thêm trong khóa học, mình có để link bên dưới.

Vì sao phải dùng Min-Hashing

Như bài toán đặt ra ở trên, chúng ta có 1 tỷ văn bản, chúng ta cần N(N-1)/2 = 5*10^17 phép tính Jaccard Similarity. Chúng ta có một server có thể thực hiện 5x10^6 phép so sánh, thì chúng ta phải mất 10^11 giây tương đương 31,710 năm để thực hiện xong.

Thuật toán MinHash sẽ giúp chúng ta một giá trị xấp xỉ giá trị của Jaccard Similarity của hai tập dữ liệu. Ưu điểm của MinHash:

• Có chiều dài đầu ra cố định

• Không phụ thuộc vào chiều dài đầu vào.

Để tính giá trị xấp xỉ Jaccard Similarity (MinHash signatures), đầu tiên ta sẽ tính MinHash của hai tập data, được 2 giá trị hash, sau đó đếm giá trị trùng nhau của 2 chuỗi hash và chia chiều dài gía trị hash, chúng ta sẽ được một giá trị xấp xỉ giá trị Jaccard Similarity.

Ví dụ ta có hai tập tập dữ liệu {a,x,c,d} và {a,x,d,e} hai giá trị hash ta có tương ứng là 1234 và 1235, số ký tự trùng nhau là 3 (1,2,3), chiều dài là 4, vậy ta có giá trị Jaccard Similarity là 3/4.

Phép tính này sẽ hơn việc tính Jaccard Similarity truyền thống, lý do là chúng ta không cần phải tính phần giao và phần hợp của hai tập dữ liệu ( trong trường hợp hai tập có nhiều giá trị thì việc tính càng lâu), và giá trị hash thường có chiều dài ngắn hơn so với số lượng phần trử trong tập dữ liệu, ngoài ra phép so sánh cũng đơn giản hơn nhiều.

Thuật toán MinHash

Ý tưởng của thuật toán khá đơn giản:

ta có hàm hash:

$$ h(x) = (ax+b)%c $$

Trong đó:

• x là số nguyên đầu vào, a và b là hai số được chọn ngẫu nhiên với điều kiện a và b < x

• c là số nguyên tố được chọn ngẫu nhiên, với điều kiện c lớn hơn x.

Cách thuật toán thực hiện như sau:

Với 1 văn bản, chạy thuật toán hash 10 lần, do ta có số a và b là ngẫu nhiên nên 10 lần chạy sẽ cho ra các kết quả khác nhau, lấy giá trị hash nhỏ nhất (do đó thuật toán có tên là min hash) làm thành phần đầu tiên của MinHash signature. Lặp lại quá trình trên 10 lần, chúng ta có MinHash signature với 10 giá trị.

Xong thuật toán, quá dễ.

Cảm ơn các bạn đã quan tâm và theo dõi bài viết, hẹn gặp bạn ở các bài viết tiếp theo.

Tham khảo

• Khóa học Mining of Massive Datasets chương 3 http://www.mmds.org/

• https://mccormickml.com/2015/06/12/minhash-tutorial-with-python-code/