Share

Quay lại
Trang chủ / Kiến thức / Phát triển offshore / Thuật toán score đánh giá và xếp hạng trong Elasticsearch

Thuật toán score đánh giá và xếp hạng trong Elasticsearch

15/12/2023
01/12/2021
Thuật toán score đánh giá và xếp hạng trong Elasticsearch

Khi thực hiện tìm kiếm một cái gì đó có thể là trên google, facebook, youtube, soundcloud..., có bao giờ bạn thắc mắc tại sao khi tìm kiếm, các kết quả lại xuất hiện rất đúng và được sắp xếp theo thứ tự như vậy không?

Tất cả những điều trên đều nhờ tới thuật toán score trong Elasticsearch. Trong bài viết này chúng ta sẽ đi tìm hiểu cách thức, thuật toán để đưa ra kết quả và xếp hạng trong công cụ tìm kiếm này. 

Elasticsearch là một công cụ phân tích và tìm kiếm phân tán, miễn phí và mở cho tất cả các loại dữ liệu, bao gồm văn bản, số, không gian địa lý, có cấu trúc và phi cấu trúc. Đây là một công cụ tìm kiếm được sử dụng bởi nhiều công ty lớn như facebook, github, soundcloud,...

Hình 1: Các user đang sử dụng Elasticsearch

Thuật toán BM25

BM25 là phương pháp tìm kiếm trên một tổ hợp từ, và xếp hạng các tập tài liệu dựa trên từng từ của truy vấn xuất hiện trong tài liệu, mà không quan tâm đến mối quan hệ giữa các từ đó trong từng văn bản (chi tiết tại wiki). Đây là một phương pháp xếp hạng tựa như tf-idf và cải tiến dựa trên lý thuyết probabilistic information retrieval, được sử dụng rộng rãi trong tìm kiếm.

trong đó:

  • D: Văn bản

  • Q: Câu truy vấn

  • k1 và b: Những hệ số độc lập, thường sẽ được chọn như sau: k1 = 1.2, b = 0.75 (link)

  • D: số từ trong văn bản D

  • avgdl: độ dài trung bình của văn bản trong tập văn bản

  • f(qi, D): TF (Term Frequency) tần số xuất hiện của từ qi trong văn bản D. Vì mỗi văn bản có độ dài khác nhau, một từ có thể xuất hiện nhiều hơn đối với các văn bản dài. Từ xuất hiện càng nhiều thì điểm càng cao.

  • IDF: (Inverse Document Frequency), đánh giá tầm quan trọng của một từ. Do một số từ như “và”, “của” và “các” thường xuất hiện rất nhiều lần nhưng độ quan trọng là không cao. Như thế chúng ta cần giảm độ quan trọng của những từ này xuống. BM25 có thay đổi 1 chút công thức tính IDF so với IDF ban đầu.

Term frequency (TF) trong BM25

Yếu tố này đánh giá tần suất, tầm quan trọng của một từ trong một văn bản. Giá trị cao thể hiện độ quan trọng cao và nó phụ thuộc vào số lần từ xuất hiện trong văn bản. Không giống với công thức Term Frequency thông thường, TF trong BM25 có cải tiến một chút như sau:

Có thể thấy ở công thức TF thông thường, số lần xuất hiện từ qi trong văn bản được chia cho tổng số từ trong văn bản. Độ dài văn bản quá ngắn hoặc quá dài so với độ dài trung bình của các văn bản thì sẽ khiến cho công thức cũ đưa ra kết quả thiếu chính xác. Vậy nên ở BM25 được thêm vào 3 tham số, với 2 hằng số k1, b và tỉ lệ giữa độ dài của văn bản so với độ dài trung bình của tất cả các văn bản.

Hình 2: Biểu đồ thể hiện sự sai khác giữa TF thông thường và TF trong BM25

Hình 3: Biểu đồ thể hiện giá trị của TF đối với các độ dài khác nhau của văn bản

Inverse document frequency (IDF) trong BM25

IDF trong BM25 thực hiện đánh giá tầm quan trọng của một từ. Do một số từ như “và”, “của” và “các” thường xuất hiện rất nhiều lần nhưng độ quan trọng là không cao, chúng ta cần giảm độ quan trọng của những từ này xuống. BM25 có thay đổi 1 chút công thức tính IDF so với IDF ban đầu.

Từ đó chúng ta sẽ có được công thức Score như ở trên để thực hiện đánh giá và tính điểm các văn bản trong Elasticsearch. Trong ES, các kết quả được trả ra sẽ được sắp xếp từ lớn đến nhỏ theo điểm số đạt được từ công thức Score.

Kết luận

Vậy là chúng ta đã đi qua thuật toán dùng để đánh giá, xếp hạng kết quả theo độ phù hợp BM25 trong Elasticsearch. Đồng thời cũng hiểu được cách sắp xếp kết quả tìm kiếm trong ES.

Cảm ơn mọi người đã theo dõi bài viết này. Để xem thêm những kiến thức khác về công nghệ, hãy truy cập Rabiloo blog

Nếu độc giả quan tâm đến các dịch vụ như: phát triển website, phần mềm, game, trí tuệ nhân tạo, hãy liên hệ với Rabiloo, chúng tôi luôn sẵn sàng tư vấn miễn phí mọi thắc mắc của các bạn.

 

Hẹn mọi người trong những bài viết tiếp theo.

 

Share


Cập nhật bài viết mới nhất từ chuyên gia

Không được để trống
Không được để trống
Không được để trống
Tìm kiếm
Tags
Website là gì? Khái niệm, cấu tạo, phân loại các Website hiện nay
24/11/2023
21/12/2023
Website là gì? Khái niệm, cấu tạo, phân loại các Website hiện nay

Gặp gỡ và lắng nghe

Không được để trống
Không được để trống
Không được để trống