TF-IDF và Cosine Similarity

Bài viết này được lấy cảm hứng từ bài viết “Tf-Idf and Cosine Similarity” của tác giả Jana Vembunarayanan. Cá nhân mình rất thích các bài viết về kỹ thuật với văn phong rõ ràng, sử dụng ví dụ dễ hiểu để mô tả những technical concept. Mình thấy bài viết của tác giả Jana đã làm được điều này. Phần lớn ý tưởng của bài viết này được lấy từ bài viết của tác giả Jana.

TF- IDF và Cosine Similarity là các kỹ thuật hay và đẹp trong xử lý data. Sau khi đọc xong bài viết này, các bạn sẽ hiểu rõ hơn cách sử dụng chúng như thế nào.

Năm 1998, Google xử lý trung bình 9800 tìm kiếm mỗi ngày. Năm 2016, số lượng tìm kiếm trung bình mỗi ngày trên Google là hơn 9 tỉ lượt tìm kiếm. Biểu đồ dưới đây sẽ cho ta thông tin chi tiết về mức tăng trưởng về số lần tìm kiếm trên Google.

Hình 1: Mức tăng về số lượt tìm kiếm trên Google. Nguồn: statisticbrain.com

Lý do chính trong thành công của Google chính là thuật toán PageRank. Thuật toán PageRank quyết định xem danh tiếng và độ tin cậy của một website như thế nào. Nhưng bên cạnh đó còn có một phần khác nữa đã tạo nên thành công của Google. Cụm từ tìm kiếm (query) do người dùng nhập vào cần được xử lý để matching với các tài liệu trên Internet. Bài viết sẽ tập trung vào phần thứ hai này. Mình sẽ tạo ra ba document (tài liệu) để mô tả phần matching này hoạt động như thế nào.

Document 1 Người lên ngựa kẻ chia bào. Rừng phong thu đã nhốm màu quan san
Document 2 Ô hay buồn vương cây ngô đồng. Vàng rơi vàng rơi thu mênh mông
Document 3 Một chiều về bên bến sông thu. Nghe tin em cưới á cái đù.

Document 1 là một câu thơ trong Truyện Kiều của Nguyễn Du. Document 2 là một câu thơ trong bài thơ Tỳ Bà của Bích Khê. Document 3 là một câu thơ trong một bài thơ (mình không nhớ tên) của Nguyễn Nhật Ánh.

Hãy tưởng tượng rằng chúng ta đang tìm kiếm trong một data set hoặc trên Internet ( và giả sử Internet chỉ có 3 tài liệu này) với từ khóa chúng ta nhập là: sông thu.

Tìm kiếm của chúng ta là một free text query, nghĩa là các từ khóa được gõ một cách tùy ý trong ô tìm kiếm và không có sự kết nối giữa các từ với nhau. Theo cách tìm kiếm này, nếu chúng ta nhập sông thu hay thu sông thì thuật toán cũng shows cho chúng ta các kết quả giống nhau.

Hãy đi vào chi tiết từng bước để xem phần matching tìm kiếm này hoạt động như thế nào.

Bước 1 : Term Frequency (TF – hay tần số xuất hiện của một từ)

Term Frequency (TF) là tần số xuất hiện của một từ trong một văn bản. Bên dưới là bảng chi tiết cho các từ và tần số của chúng trong mỗi văn bản.

TF của Document 1

Document 1 người lên ngựa kẻ chia bào rừng
Term Frequency 1 1 1 1 1 1 1
  phong thu đã nhốm màu quan san
  1 1 1 1 1 1 1

TF Document 2

Document 2 ô hay buồn vương cây ngô
Term Frequency 1 1 1 1 1 1
  đồng vàng rơi thu mênh mông
  1 2 2 1 1 1

TF của Document 3

Document 3 một chiều về bên bến sông thu
Term Frequency 1 1 1 1 1 1 1
  nghe tin em cưới á cái đù
  1 1 1 1 1 1 1

Trong thực tế, các văn bản có kích thước (tổng số từ) khác nhau. Trong các văn bản có kích thước lớn, tần số xuất hiện của một từ có thể sẽ nhiều hơn so với các văn bản có kích thước nhỏ hơn. Do đó, chúng ta cần phải normalize (chuẩn hóa) tần số xuất hiện của một từ trong một văn bản dựa trên kích thước của văn bản đó. Một mẹo đơn giản là chúng ta chia số lần xuất hiện của một từ cho tổng số từ trong văn bản. Ví dụ trong Document 2, từ rơi xuất hiện hai lần . Tổng số từ trong Document 2 là 14. Do đó, tần số xuất hiện được chuẩn hóa (normalized TF) của từ rơi2/14 = 0.14. Từ đó, ta có tần số xuất hiện được chuẩn hóa của các từ trong cả 3 tài liệu lần lượt như sau.

Normalized TF cho Document 1:

Document 1 người lên ngựa kẻ chia bào rừng
Term Frequency 0.07 0.07 0.07 0.07 0.07 0.07 0.07
  phong thu đã nhốm màu quan san
  0.07 0.07 0.07 0.07 0.07 0.07 0.07

Normalized TF cho Document 2:

Document 2 ô hay buồn vương cây ngô
Term Frequency 0.07 0.07 0.07 0.07 0.07 0.07
  đồng vàng rơi thu mênh mông
  0.07 0.14 0.14 0.07 0.07 0.07

Normalized TF cho Document 3:

Document 3 một chiều về bên bến sông thu
Term Frequency 0.07 0.07 0.07 0.07 0.07 0.07 0.07
  nghe tin em cưới á cái đù
  0.07 0.07 0.07 0.07 0.07 0.07 0.07

Bước 2: Inverse Document Frequency (IDF – tần số nghịch của một từ trong một data set)

Mục đích chính của việc tìm kiếm văn bản là tìm ra những văn bản trong một data set (hoặc Internet nói chung) có nội dung liên quan nhất với từ tìm kiếm của người dùng. Ở bước 1 (TF), tất cả các từ đều được đánh giá quan trọng ngang nhau.Tuy nhiên, trong thực tế thì có một số từ xuất hiện quá nhiều và không có vai trò quyết định trong việc tìm ra các văn bản có nội dung liên quan với chủ đề mà người dùng tìm kiếm (trong tiếng Anh thì những từ xuất hiện nhiều và ít quan trọng là the, a, he, she, etc…). Chúng ta cần tìm ra một cách để làm giảm trọng số của những từ xuất hiện quá thường xuyên (trên Internet) và tăng trọng số của những từ ít xuất hiện (trên Internet) hơn. Và công cụ toán học Logarithm (Lôgarit) sẽ giúp chúng ta làm được điều này.

Chúng ta hãy tính IDF cho từ chiều trong data set của chúng ta ( data set của chúng ta gồm 3 văn bản: Document 1, Document 2 và Document 3).

IDF(chiều) = 1 + ln(Tổng số văn bản trong data set/Số văn bản chứa từ chiều)

Data set của chúng ta có 3 văn bản : Document 1, Document 2 và Document 3.

Từ chiều xuất hiện trong Document 3.

IDF(chiều) = 1 + ln(3/1) = 1 + 1.0986 = 2.0986.

Bên dưới là bảng IDF của tất cả các từ trong data set. Trong đó từ thu xuất hiện trong cả 3 văn bản nên nó sẽ có điểm số IDF thấp hơn so với các từ chỉ xuất hiện một văn bản.

Từ IDF
người 2.0986
lên 2.0986
ngựa 2.0986
kẻ 2.0986
chia 2.0986
bào 2.0986
rừng 2.0986
phong 2.0986
thu 1
đã 2.0986
nhốm 2.0986
màu 2.0986
quan 2.0986
san 2.0986
ô 2.0986
hay 2.0986
buồn 2.0986
vương 2.0986
cây 2.0986
ngô 2.0986
đồng 2.0986
vàng 2.0986
rơi 2.0986
mênh 2.0986
mông 2.0986
một 2.0986
chiều 2.0986
về 2.0986
bên 2.0986
bến 2.0986
sông 2.0986
nghe 2.0986
tin 2.0986
em 2.0986
cưới 2.0986
á 2.0986
cái 2.0986
đù 2.0986

Bước 3 : Tính TF * IDF

Hãy nhớ rằng mục đích của chúng ta là đi tìm văn bản có nội dung liên quan nhất cho cụm từ tìm kiếm : sông thu.

Trong mỗi từ trong cụm từ tìm kiếm, nhân giá trị normalized TF của nó trong mỗi văn bản với giá trị IDF của từ đó để tính được giá trị TF*IDF của một từ trong từng văn bản.

  Document 1 Document 2 Document 3
sông  0 0 0.146902
thu 0.07 0.07 0.07

Bước 4 : Vector Space Model – Cosine Similarity

Chúng ta mô tả mỗi document như là một vector. Một data set được xem như là một tập hợp các vector trong một không gian vector. Mỗi từ trong không gian vector sẽ có trục của riêng nó. Bằng cách sử dụng công thức phía dưới, chúng ta có thể tìm ra độ tương đồng của bất kì tài liệu nào.

Cosine Similarity (d1, d2) = Dot product(d1, d2)/||d1|| * ||d2||

Dot product(d1, d2) = d1[0]*d2[0] + d1[1]*d2[1] + ....d1[n]*d2[n]

||d1|| = square root( d1[0]^2  + d1[1]^2 + ... + d1[n]^2 )

||d2|| = square root( d2[0]^2  + d2[1]^2 + ... + d2[n]^2 )
Hình 2: không gian 2 chiều sông – thu

Vector chỉ làm việc với con số. Trong bài viết này chúng ta đang làm việc với văn bản. Đó là lý do tại sao chúng ta sử dụng TF – IDF để chuyển đổi từ ngữ văn bản thành số để có thể biểu diễn chúng ở dạng vector.

Cụm từ tìm kiếm của người dùng cũng được xem là một vector. Chúng ta tính giá trị TF * IDF cho cụm từ truy vấn.

  TF IDF TF * IDF
sông 0.5 2.0986 1.0493
thu 0.5 1 0.5

Bây giờ chúng ta hãy tính cosine similarity (tương đồng cosine) giữa cụm từ tìm kiếm (Query) và Document 1.

Cosine Similarity(Query, Document 1) = Dot Product(Query, Document 1)/||Query|| *||Document 1||

Dot Product(Query, Document 1) = Query[TF*IDF(sông)] * Document 1[TF*IDF(sông)] + Query[TF*IDF(thu)]*Document 1[TF*IDF(thu)] = 1.0493*0 + 0.5*0.07 = 0.035

||Query|| = square root(Query[TF*IDF(sông)]^2+ Query[TF*IDF(thu)]^2) = squareroot(1.0493^2 + 0.5^2) = 1.1623

||Document 1|| = square root(Document 1[TF*IDF(sông)]^2+ Document 1[TF*IDF(thu)]^2) = squareroot(0^2 + 0.07^2) = 0.07

→ Cosine Similarity(Query, Document 1) = 0.035/(1.1623*0.07) = 0.430167335

Bảng dưới là giá trị cosine similarity giữa cụm từ tìm kiếm và các văn bản có trong data set.

  Document 1 Document 2 Document 3
Cosine Similarity 0.430167335 0.430167335 1

Chúng ta có thể thấy là Document 3 có score cao nhất bằng 1. Lý do là vì Document 3 chứa đồng thời cả hai từ sôngthu. Điều này có nghĩa là khi người dùng tìm kiếm với cụm từ là sông thu thì thuật toán sẽ trả về tài liệu có độ tương đồng cosine lớn nhất với nó là Document 3.

Chia sẻ bài viết

Leave a Comment

Your email address will not be published. Required fields are marked *