Hệ gợi ý bằng thuật toán Sørensen–Dice trong Rails với gem Predictor

205
sử dụng gem Predictor

Bài viết này là các phần liên quan tới hệ gợi ý được sử dụng cho đồ án tốt nghiệp của mình

Thuật toán Chỉ số Sørensen–Dice

Định nghĩa

Chỉ số Sørensen–Dice là một phương pháp thống kê được sử dụng để đánh giá sự giống nhau của hai mẫu. Nó được phát triển độc lập bởi Thorvald Sørensen và Lee Raymond Dice.

Công thức

Công thức ban đầu của Sørensen được dự định sẽ được áp dụng cho dữ liệu rời rạc. Cho hai bộ X và Y, Chỉ số Sørensen-Dice được định nghĩa như sau:

Trong đó: |X| và |Y| là số phần tử các bộ X, Y. DSC ở đây sẽ bằng 2 lần thương của số phần tử chung của 2 bộ chia cho tổng số phần tử của 2 bộ.

Khi áp dụng cho các bộ dữ liệu boolean, sử dụng các định nghĩa true positive (TP), false positive (FP) và false negative (FN), ta có thể viết dưới dạng:

Nó khác với chỉ số Jaccard chỉ tính true positive một lần ở cả tử số và mẫu số. DSC là thương số của độ tương tự và nằm trong khoảng từ 0 đến 1. Nó có thể được xem như là thước đo độ tương tự trên các tập hợp.

So sánh với thuật toán Chỉ mục Jaccard

Hệ số này không khác lắm về hình thức so với Chỉ mục Jaccard. Trong thực tế, nếu cho giá trị Chỉ số Sørensen–Dice là S, Chỉ mục Jaccard là J, ta có:  và S = 2J/(1+J).

Tuy nhiên, Chỉ số Sørensen–Dice không tuân theo bất đẳng thức tam giác nên có thể được coi là phiên bản bán số liệu của Chỉ mục Jaccard.

Chỉ số Sørensen–Dice cũng chỉ nhận giá trị từ 0 đến 1 như Chỉ mục Jaccard, nhưng hàm khác biệt tương ứng

của Chỉ số Sørensen–Dice lại không phải là số liệu khoảng cách phù hợp do không thoả mãn bất đẳng thức tam giác

  Thuật toán sắp xếp nào là nhanh nhất?
  Thuật toán trong lập trình – Đôi điều tản mạn

Ứng dụng thực tế

Ứng dụng chủ yếu của Chỉ số Sørensen–Dice hiện tại là ở trong các lĩnh vực Sinh thái học và các lĩnh vực của Công nghệ thông tin như Nhận dạng hình ảnh và So sánh chuỗi kí tự.

Giới thiệu về gem Predictor

Predictor là 1 gem được phát triển bởi công ty Pathgather và được quảng cáo là chính công ty cũng đang sử dụng gem này cho Recommender System của chính công ty. Đây là Github của gem: https://github.com/Pathgather/predictor

Theo như README của gem thì nó được forked lại từ gem Recommendify của Paul Asmuth, 1 gem được viết bởi ngôn ngữ Ruby và C và được viết lại nhằm mục đích:

  • Đưa ra hiệu quả và trải nghiệm tốt hơn bằng cách sử dụng Redis cho hầu hết logic.
  • Cung cấp các mục tương tự như “Người dùng đọc sách này cũng đọc …”
  • Cung cấp dự đoán được cá nhân hóa dựa trên lịch sử quá khứ của người dùng, chẳng hạn như “Bạn đã đọc 10 cuốn sách này, vì vậy bạn cũng có thể muốn đọc …”

Gem này hiện tại đang sử dụng 2 thuật toán cho việc gợi ý là Jaccard và Sørensen–Dice. Và mặc dù là gem của 1 công ty nhưng công ty cũng rất sẵn lòng được commit bởi tất cả các lập trình viên Ruby trên thế giới.

Thuật toán Sørensen–Dice trong gem Predictor

Tại README của gem, chúng ta có hướng dẫn sử dụng như sau:

Về hướng dẫn sử dụng thì sẽ thuộc phần sau, nhưng ở đây có 2 điều cần quan tâm measure: và :sorensen_coefficient

Và giải thích của measure ở đây:

Như vậy theo dòng code bên trên, chúng ta chỉ cần quyết định tên method và method đó được sử dụng. Còn không thì mặc định là Jaccard.

Và về cách cài đặt của :sorensen_coefficient:

Theo như module trên, ta có thể thấy method sorensen_coefficient đã được dựng rất sát so với công thức đã cho ban đầu. Thế nên ta hoàn toàn yên tâm khi sử dụng theo đúng hướng dẫn sử dụng là ta sẽ có hệ gợi ý dựa trên thuật toán Sørensen–Dice.

Cài đặt và sử dụng gem

Trước khi vào phần này thì mình xin được phép upload thiết kế CSDL của mình để mọi người có thể hình dung.

Ở đây mình sẽ gợi ý sự kiện cho người dùng với các yếu tố gợi ý lấy thí nghiệm là tag, place, age_filter và provider_id. Bộ dữ liệu gồm có 12 event,6 tag, 2 user với role provider (project có 3 role là user, provider và admin), age_filter sẽ chạy từ 1 đến 10. Cách thức là lấy tất cả các dữ liệu dạng số để xử lý(tức là với tag, provider và place ta sẽ lấy id). Như vậy, tất cả các dữ liệu thử đều là kiểu int.

Cài đặt và sử dụng

Trước hết thì thêm vào Gemfile của project như sau:

Sau đó thì chạy lệnh bundle là chúng ta đã có gem trong project.

Hãy cài trước Redis vì tiếp theo đó, chúng ta sẽ config

Tiếp theo ta sẽ tạo class

Ta thêm tiếp các dòng sau vào cuối model với mục đích thêm event mới vào recommender khi create và xoá event khỏi recommender khi delete

Tại EventController, ta sẽ viết như sau:

Khi thêm như vậy, ta sẽ lọc ra được toàn bộ dãy các id của các event tương đồng với event đang được show bằng similarities_for. Và để kiểm chứng chúng ta sẽ chuyển sang view, code này khá xấu nên mong các bạn thông cảm. Mình cần nó chạy được để các bạn xem.

Xem thêm clean code là gì?

Kết quả

Mình lấy sự kiện có id = 2. Đây là seed của event trong file seed.rb

và đây là kết quả dữ liệu đổ ra

Các event được gợi ý lần lượt có dữ liệu là 4,5,7,6(chắc chắn là so với 12 event thì đây chỉ bằng 1/3). Mình sẽ gửi các bạn các event có id này có chứa dữ liệu gì ở file seed.rb

Tóm tắt lại chúng ta có thể thấy độ tương đồng của các event theo các thuộc tính mình đem thí nghiệm như sau:

  • Về place, các thuộc tính đã cho mình không chung nhau
  • Về provider, event có id thuộc tập {2,4,7,6} chung 1 provider có id = 2
  • Về age, event có id thuộc tập {2,4} chung age_filter = 5; event có id thuộc tập {5,6} chung age_filter = 8
  • Về tag, event có id=2 chung có các tag chứa id trong tập {4,5,6}, chung {4, 5} với event có id = 5, và chung duy nhất {4} với event có id = 7 và event có id = 6.

Nhìn kết quả này, ta cũng có thể thấy bộ event có id {5,6,7} sẽ luôn xuất hiện trong gợi ý của nhau. Và để kiểm chứng mình cũng vào id=5

Như các bạn đã thấy, gợi ý đầu tiên là tên của event có id = 7 bên trên và thứ hai là tên của event có id = 6.

Về tốc độ thì mình không thấy ảnh hưởng đáng kể ở trong log của rails.

Update và hướng dẫn thử

Sau 1 hồi loay hoay chỉnh giao diện thì mang tiếng là có chứng chỉ Front-end Developer của FreeCodeCamp nhưng thực tế thì mãi mình mới xử HTML/CSS được. Thế nên mình đã sửa phần kết luận và đưa link Git để các bạn có thể lấy về thử. Đây là ảnh của phần các event được recommend:

Hướng dẫn cài đặt:

  • Clone project
  • Cài Docker (Xem thêm Docker là gì?)
  • Trong thư mục project, mở terminal, chạy: docker-compose up --build
  • Mở terminal khác, truy cập thư mục project và chạy: docker exec -ti let-us-go_web_1 /bin/sh. Tại terminal đó lần lượt chạy rails db:migrate và rails db:seed
  • Cuối cùng vào 0.0.0.0:3000 và dùng project

Kết luận

Trên đây là tìm hiểu của mình về gem Predictor và chỉ mới dùng method similarities_for và đang nghiên cứu dở cách dùng predictions_for. Hiện tại tại thời điểm viết bài này code đồ án của mình vẫn có 1 số chỗ cần bổ sung và nâng cấp. Đây là link git của project: https://github.com/BlazingRockStorm/let-us-go . Mình thực sự thực sự cảm ơn các bạn nếu các commit cho mình để cải thiện được chức năng cho tốt hơn.

Rất mong các bạn cảm thấy bài viết có ích. Xin cảm ơn các bạn đã đọc bài viết của mình!

Xem thêm việc làm Ruby Developers hấp dẫn tại TopDev

TopDev via viblo

  Kinh nghiệm phỏng vấn Basecamp - Tại sao 80% các ứng viên kỹ sư phần mềm bị người sáng lập Rails từ chối?
  40 tips giúp bạn code Ruby on Rails bá đạo