Tìm hiểu về giải thuật phát hiện luật kết hợp

Đã bao giờ khi mua hàng trên mạng, lúc chuẩn bị check out bạn thấy hệ thống gợi ý thêm một số sản phẩm mà bạn nhớ ra lúc đầu mình định mua nhưng lại quên mất chúng. Đó là một ứng dụng của Machine Learning trong việc xây dựng hệ gợi ý mà đang được sử dụng rất phổ biến trong các trang web bán lẻ hiện nay. Hôm nay ta cùng tìm hiểu một thuật toán phát hiện luật kết hợp đơn giản mà có thể ứng dụng trong hệ thống gợi ý này nhé.

Giả sử trong quá khứ chúng ta có tập các giao dịch sau:
image
Ví dụ này sẽ được sử dụng xuyên suốt bài viết để giúp mọi người hiểu rõ hơn về thuật toán nhé!

Trước khi bắt đầu, ta cần làm rõ một số khái niệm:

Luật kết hợp là gì?

Với một tập các giao dịch cho trước (lịch sử mua hàng của khách hàng chẳng hạn), luật kết hợp là các luật cho phép dự đoán khả năng xuất hiện trong một giao dịch của các mục (items) này dựa trên việc xuất hiện của các mục khác. Ở đây mỗi mục (item) bạn có thể coi như là 1 sản phẩm. Ví dụ về luật kết hợp nhé:
image
Giải thích rõ hơn nhé, luật kết hợp 1 ngụ ý khi khách hàng mua diaper thì khả năng cao là khách sẽ mua thêm beer, hay ở luật 2 muốn nói khi họ mua milk và bread thì có thể sẽ mua thêm egg và coke.

Tiêu chí đánh giá luật kết hợp

Vậy những luật kết hợp thỏa mãn những tiêu chí nào thì sẽ được chọn? Chắc chắn không thể chọn một cách ngẫu nhiên, bừa bãi một luật bất kỳ vì như thế kết quả gợi ý hoàn toàn hỗn loạn và không phản ánh đúng ý muốn của người dùng. Ở đây sẽ có những thông số đánh giá chất lượng của một luật. Cụ thể hơn ta cùng tìm hiểu nhé
Giả sử với luật kết hợp X->Y, trong đó X, Y là các tập mục (itemset). Ta có 2 thông số đánh giá chất lượng của luật kết hợp này là độ hỗ trợ và độ tin cậy.

Độ hỗ trợ (support) s: Với một tập mục T bất kỳ, độ hỗ trợ của tập mục này là tỷ lệ giao dịch chứa T đối với tất cả các giao dịch. Một tập mục có độ hỗ trợ lớn hơn một ngưỡng nhất định được gọi là tập mục thường xuyên.
Xét luật kết hợp trên, độ hỗ trợ của luật cho biết tỷ lệ giao dịch chứa cả X và Y đối với tất cả các giao dịch. Ví dụ:
image
Độ tin cậy (Confidence) c: cho biết tỷ lệ giao dịch chứa cả X và Y đối với các giao dịch chứa X. Ví dụ:
image
Và chỉ những luật kết hợp nào có độ hỗ trợ lớn hơn hoặc bằng giá trị ngưỡng minsup và độ tin cậy lớn hơn hoặc bằng giá trị ngưỡng minconf thì mới được chọn thôi nhé!

Quy trình phát hiện luật kết hợp

Một cách đơn giản để phát hiện các luật kết hợp là bằng cách liệt kê tất cả các luật có thể sinh được từ tập tất cả các mục, sau đó với mỗi luật tính giá trị độ hỗ trợ và độ tin cậy xem có thỏa mãn điều kiện ràng buộc phía trên không. Có điều, quá trình vét cạn này quả là cực mất nhiều thời gian với một chi phí tính toán khổng lồ và không hề khả thi trong thực tế.

Ở đây, chúng ta có một giải thuật cắt tỉa Apriori giúp giảm bớt rất nhiều không gian tìm kiếm và làm cải thiện đáng kể hiệu quả thuật toán. Cụ thể sẽ gồm 2 bước chính sau:

  • Sinh ra các tập mục thường xuyên: tập mục có độ hỗ trợ lớn hơn hoặc bằng minsup
  • Sinh ra các luật kết hợp có độ tin cậy cao từ các tập mục thường xuyên.

Quá trình sinh các tập mục thường xuyên

Chúng ta cùng hình dung nhé: số lượng giao dịch chứa milk, beer chắc chắn luôn lớn hơn số lượng giao dịch chứa milk, beer, bread, điều này tương đồng với độ hỗ trợ của {milk, beer} lớn hơn độ hỗ trợ của {milk, beer, bread}. Khái quát hơn ta có:
image
Đây được gọi là tính đơn điệu của độ hỗ trợ.
Vậy thì nếu một tập mục hiện tại là tập mục không thường xuyên(độ hỗ trợ thấp) thì mọi tập cha của nó đều là tập mục không thường xuyên và ta sẽ không cần phải xét tới chúng.
image

Cụ thể các bước của thuật toán sinh tập mục thường xuyên:

  • Sinh ra tất cả các tập mục thường xuyên mức 1 (các tập mục thường xuyên chỉ chứa 1 mục)
  • Đặt k = 1
  • Lặp lại các bước sau cho đến khi không có thêm bất kỳ tập mục thường xuyên nào được sinh ra:
    Từ các tập mục thường xuyên mức k sinh ra các tập mục mức k+1 cần xét
    Loại bỏ các tập mục mức k+1 chứa các tập con là tập mục không thường xuyên mức k
    Tính độ hỗ trợ cho mỗi tập mục mức k+1 ở trên bằng cách duyệt qua tất cả các giao dịch
    Loại bỏ các tập mục không thường xuyên mức k+1, còn lại ta thu được tập mục thường xuyên mức k+1
    image

Sinh các luật kết hợp từ tập mục thường xuyên

Trước hết ta có thể thấy mỗi luật X->Y sinh ra từ một tập mục là một phân tách nhị phân của các item trong tập mục đó vào 2 phần giả thiết (X) và kết luận (Y).

Bây giờ ta thử xét một tập mục L = {A,B,C,D} và các luật sinh từ tập mục L như sau:
ABC ->D, AB->CD, A->BCD
Ta thử đi tính độ tin cậy của 3 luật trên nhé
image

Và như ta đã nhận xét ở trên: s(A) ≥ s(AB) ≥ s(ABC) nên
c(ABC->D) ≥ c(AB->CD) ≥ c(A->BCD)
Như vậy độ tin cậy của các luật sinh ra từ cùng một tập mục thường xuyên có tính đơn điệu và một luật sẽ bị loại bỏ nếu như tồn tại một luật con của nó không có độ tin cậy cao.

Ta có thể thấy việc áp dụng thuật toán cắt tỉa có thể giảm đáng kể không gian tìm kiếm, từ đó nâng cao rõ rệt hiệu năng tính toán so với việc thực hiện vét cạn đơn thuần.

Ứng dụng

Thuật toán này có thể ứng dụng trong việc xây dựng các hệ gợi ý như đã nói ở phần đầu bài viết. Ngoài ra, dựa vào các luật kết hợp, người ta có thể tối ưu hóa sự phân bố các gian hàng trong cửa hàng sao cho các mặt hàng “gần gũi” nhau được đặt gần nhau để tiện cho khách hàng cũng như tránh trường hợp khách hàng “quên” mất thứ cần mua. Nhìn chung theo đánh giá thì đây là một thuật toán dễ hiểu, khá tường minh, tuy nhiên đòi hỏi các thao tác duyệt để tính các giá trị độ tin cậy khá ảnh hưởng tới độ phức tạp, đặc biệt là khi ta có một số lượng lớn giao dịch. Rõ ràng tuy trên lý thuyết giải thuật rất sáng rõ nhưng khi implement thì đòi hỏi nhiều kĩ năng để có thể tối ưu nhất hiệu quả.

Tài liệu tham khảo

Phát hiện luật kết hợp – Nguyễn Nhật Quang
Link: https://users.soict.hust.edu.vn/quangnn/mldm/slides/L11-Phat_hien_luat_ket_hop.pdf

4 Likes

Trong ecommerce có cái feature rất nhiều bên sử dụng là cross sell. Ngày xưa là kiểu configure tay theo từng sản phẩm, hoặc là theo category (kiểu mua 1 sản phẩm ở đây thì show off 1 sản phẩm liên quan) Nhưng công nhận áp dụng AI/Machine Learning vào thấy hay hẳn nhỉ.

Searching thử, thì Magento Commerce cũng có feature AI Powered Product Recommendation cho khách hàng trong bộ Adobe Sensei của mình. Cả bên Shopify cũng vậy, https://apps.shopify.com/cross-sell Thấy quảng cáo ntn:

NEW! Show AI generated recommendations unique to each product based on sales history, orders & collections. Let the algorithm generate the smart recommendations for you!