Saturday, May 15, 2010

Truy hồi thông tin trong các bộ đánh chỉ mục tìm kiếm

Như đã đề cập ở bài viết trước, bộ đánh chỉ mục (indexer) là một thành phần quan trọng, chuyện trách nhiệm phân tích và xử lý dữ liệu trong máy tìm kiếm. Công việc chính của nó là cắt một bài viết dài thành nhiều từ (word) sau đó xác định trọng số của các từ này trong bài viết.
Tại sao phải xác định trọng số? Nói một cách đơn giản, trọng số là thứ để xác định xem một bài viết có được xếp hạng cao hay thấp khi người dùng tìm kiếm nó…
Tuy nhiên, trước khi tìm hiểu về cách đánh trọng số hiệu quả, chúng ta sẽ đề cập đến một vấn đề cơ bản: Làm sao để cắt một bài viết thành các từ?

Generating document representations

Generating document representations (viết tắt là GenDocReps, tạm dịch là Việc tự sinh các thể hiện tài liệu) có thể hiểu như là việc tách một tài liệu (hoặc một câu truy vấn tìm kiếm) có thể dài đến hàng trăm từ, thành một mảng các từ khóa và cũng cho biết số lần xuất hiện của nó trong tài liệu.
Tôi chỉ đề cập GenDocReps như là cách tách tài liệu thành các từ mà không quan tâm đến khoảng cách các từ cũng như vị trí trước sau. Ví dụ, thành phố với phố thành là như nhau, trong khi việc này không đúng, nhất là với tiếng Việt (tiếng Việt có rất nhiều từ ghép như “cò mồi”…)
Generating Document Representations
Việc này diễn ra trong nhiều bước (Xem hình bên phải):
  • Documents: Việc đầu tiên là lấy đúng nội dung cần, vì một trang web có rất nhiều thông tin khác như các menu, thanh bên,…
  • Structure: Biến tài liệu thành các cấu trúc tương tự như DOM. Chuyện này cũng rất quan trọng như tôi đã đề cập ở đây.
  • Words: Phân tách các tài liệu thành các từ.
  • Stop-words: Loại bỏ các stop-word (như “và”, “đó”, “những”,…) là những từ không quan trọng cho việc tìm kiếm.
  • Nouns: Xác định các danh từ và danh từ riêng, đây là một loại từ rất quan trọng trong tìm kiếm, bởi nó có ý nghĩa phân loại nội dung và người dùng cũng thường hay dùng chúng để tìm kiếm.
  • Stems: Đưa về dạng từ gốc của một từ. Loại này thường xuất hiện trong tiếng Anh, ví dụ stems stem.
  • Terms: Là danh sách các từ kết quả sau khi thực hiện các bước trên, kèm với số lần xuất hiện của nó trong tài liệu

Luật Zipf

Một vấn đề nhỏ gặp phải khi làm việc với các stop-word đó là phải thống kê được các stop-word trong một ngôn ngữ nào đó. Hơn nữa, một bài toán lớn là đôi khi các stop-word cũng có khả năng phân loại khi nó xuất hiện không quá nhiều lần.
Luật Zipf (xem chi tiết trên Wikipedia) đưa ra một giải pháp như sau:
Tần số xuất hiện trong các tài liệu của một từ tỷ lệ nghịch với độ quan trọng của nó
Có thể hiểu như sau: Một từ xuất hiện trong tất cả các tài liệu thì nó gần như không quan trọng trong việc tìm kiếm, đó là trường hợp của stop-word. Càng ít tài liệu sử dụng nó, độ quan trọng khi phân loại của từ đó sẽ càng cao.

Đánh trọng số tf-idf

tf-idf (term frequency–inverse document frequency) là một cách đánh trọng số của từ khá thú vị cho một tài liệu nào đó. Nó dựa trên các nguyên lý trọng số của một từ t là: (Theo Introduction to Information Retrieval)
  • cao nhất khi t xuất hiện nhiều lần trong một số ít tài liệu.
  • thấp khi t xuất hiện một số ít lần trong ít tài liệu hoặc nhiều lần trong nhiều tài liệu.
  • thấp nhất khi t xuất hiện trong hầu hết mọi tài liệu.
Từ đó, người ta đưa ra công thức sau:
Weight (t) = tf(t,d) × idf(t)
Với:
Và:
—————
Bài viết này là một phần của bài thuyết trình môn Hệ thống thông minh của Nguyễn Kim Kha

No comments:

Post a Comment

Biểu mẫu liên hệ

Name

Email *

Message *