Luật giỏ hàng - Apriori và FP-growth
Khai phá luật kết hợp cho giỏ hàng: support confidence lift, ba loại luật, Apriori, hạn chế và FP-growth với cây FP.
Trung bìnhThuật toán ~60 phút
Ôn lại trước khi học
Giới thiệu
Bài này học luật giỏ hàng để gợi ý mua kèm. Luật này giúp tăng giá trị giỏ trung bình.
Kiến thức cần nhớ
Ba thước đo luật
- Support: tỉ lệ giao dịch chứa cả hai vế.
- Confidence: có vế trái thì bao nhiêu phần trăm có vế phải.
- Lift: hút nhau (>1), độc lập (=1), đẩy nhau (<1).
- Ví dụ đời thường: mua mì thì 70% mua trứng kèm.
Apriori cắt tỉa
- Đi theo tầng: tìm món đơn phổ biến rồi ghép đôi, ghép ba.
- Nguyên lý: cha đã hiếm thì con chứa nó còn hiếm hơn.
- Cắt cả nhánh ứng viên mà khỏi cần đếm.
- Ví dụ đời thường: bột đã ế thì combo chứa bột cũng ế.
FP-growth nén cây
- Quét 1: đếm tần suất để xếp món theo thứ tự.
- Quét 2: chèn giao dịch vào cây FP chia sẻ tiền tố.
- Moi mẫu bằng đệ quy từ món hiếm nhất.
- Ví dụ đời thường: nén ngàn hóa đơn thành một cái cây gọn.
| Thuật toán | Cách làm | Điểm yếu |
|---|---|---|
| Apriori | Sinh ứng viên tầng | Quét nhiều, ứng viên phình |
| FP-growth | Nén cây rồi moi | Cây to thì nặng RAM |
Phân loại luật
- Luật hiển nhiên (trivial): ai cũng biết, ví dụ mua bột mì thì mua men. Không đem lại giá trị mới.
- Luật khó giải thích (inexplicable): số liệu mạnh nhưng không có lý do hợp lý, cần kiểm tra lại trước khi tin.
- Luật hành động được (actionable): mới, có lý, dẫn tới quyết định cụ thể như xếp kệ hay tạo combo. Đây là thứ cần tìm.
Ví dụ
- Input: 6 giao dịch, tính luật mì -> trứng -> Output: support, confidence, lift cụ thể.
- Câu này cho thấy 3 số nói 3 chuyện khác nhau.
- Input: nâng ngưỡng support -> Output: tập phổ biến chỉ co lại không nở.
- Câu này kiểm tra tính đơn điệu của cắt tỉa.
💻 Bài tập
Ngôn ngữ: Python 3. Không dùng mlxtend trừ khi đối chiếu. Nộp vào day-051/. Giao dịch là list[frozenset[str]].
Bài 1: Ba độ đo
| Hàm | Công thức |
|---|---|
support(T, items) | Tỉ lệ giao dịch chứa items |
confidence(T, A, B) | support(A ∪ B) / support(A) |
lift(T, A, B) | confidence(A, B) / support(B) |
T = [{mì,trứng,sữa}, {mì,trứng}, {mì,bia}, {trứng,sữa}, {mì,trứng,bia}, {sữa}]
support({mì,trứng}) -> 3/6 = 0.5
confidence({mì}->{trứng}) -> 3/4 = 0.75
lift({mì}->{trứng}) -> 0.75 / (4/6) = 1.125
Bài 2: Apriori
def apriori(T, min_support: float) -> dict[frozenset, float]: ...
def rules(freq: dict, min_conf: float) -> list[tuple[frozenset, frozenset, float, float, float]]:
"""Trả (A, B, support, confidence, lift), sắp theo lift giảm dần."""
Ràng buộc: ở tầng k+1, chỉ sinh ứng viên từ 2 tập phổ biến tầng k chung k-1 phần tử đầu, và cắt ứng viên có tập con không phổ biến.
T trên, min_support=0.5 -> {mì}, {trứng}, {sữa}, {mì,trứng}
Tăng min_support -> số tập phổ biến không tăng (viết test)
In số ứng viên được đếm ở mỗi tầng, có và không có bước cắt tỉa.
Bài 3: FP-growth và dữ liệu thật (nâng cao)
- Cài FP-tree: đếm tần suất, sắp món trong giao dịch theo tần suất giảm dần, chèn vào cây có header table.
- Cài FP-growth đệ quy trên conditional pattern base.
- Chạy trên bộ dữ liệu giỏ hàng công khai (ví dụ Groceries, khoảng 10.000 giao dịch). So thời gian Apriori và FP-growth với
min_support = 0.01, 0.005, 0.002. Kết quả tập phổ biến phải giống nhau. - In 10 luật lift cao nhất và nhận xét 3 luật.
✅ Tiêu chí hoàn thành
- Test mẫu pass.
- Apriori và FP-growth cho cùng tập phổ biến.
- Bảng thời gian Bài 3 có số thật.
- Giải thích được vì sao lift < 1 nghĩa là 2 món "đẩy nhau".
❓ Câu hỏi ôn tập
- Support, confidence, lift đo gì?
- Nguyên lý Apriori cắt tỉa sao?
- FP-growth nén giao dịch vào đâu?
- Bẫy lift cao support tí hon là sao?
🌕 Bạn đã hoàn thành ngày 51. Làm hết bài tập phía trên rồi sang ngày tiếp theo.