Khai thác dữ liệu lớn · Ôn tập làm bài tay
5 thuật toán khai phá tập phổ biến theo chiều dọc
Bộ tài liệu ôn tập cho bài tập chạy tay (không dùng code) gồm Charm, GenMax, dEclat, dCharm, dGenMax. Mỗi trang đi theo một mạch quen thuộc: trước hết là phần lý thuyết, rồi tới các quy tắc, sau đó là ví dụ giải từng bước, và cuối cùng là phần bài tập tự luyện có sẵn đáp án để đối chiếu.
Bộ dữ liệu dùng chung (Zaki ACTW)
Tất cả ví dụ trong bộ tài liệu này dùng đúng một bảng giao dịch, với ngưỡng phổ biến tối thiểu bằng ba (tức một nửa trong số sáu giao dịch). Học một bộ dữ liệu nhưng thấy rõ khác biệt giữa ba loại tập phổ biến, và giữa hai cách lưu là danh sách giao dịch với danh sách khác biệt.
Bảng dạng ngang
| Giao dịch | Các mặt hàng |
|---|---|
| 1 | A C T W |
| 2 | C D W |
| 3 | A C T W |
| 4 | A C D W |
| 5 | A C D T W |
| 6 | C D T |
Bảng dạng dọc — mỗi mặt hàng có mặt ở đâu
| Mặt hàng | Có mặt ở các giao dịch | Độ phổ biến |
|---|---|---|
| A | 1, 3, 4, 5 | bốn |
| C | 1, 2, 3, 4, 5, 6 | sáu |
| D | 2, 4, 5, 6 | bốn |
| T | 1, 3, 5, 6 | bốn |
| W | 1, 2, 3, 4, 5 | năm |
Độ phổ biến của một mặt hàng là số giao dịch có chứa nó. Cả năm mặt hàng đều có độ phổ biến từ bốn trở lên, đều vượt ngưỡng ba, nên đều phổ biến.
5 thuật toán — phân biệt nhanh
| Thuật toán | Tìm cái gì | Lưu dữ liệu kiểu nào | Dựa trên |
|---|---|---|---|
| Charm | Các tập đóng | danh sách giao dịch | Eclat, thêm bốn tình huống |
| GenMax | Các tập tối đại | danh sách giao dịch | Quay lui, có cắt tỉa bao trùm |
| dEclat | Tất cả tập phổ biến | danh sách khác biệt | Eclat |
| dCharm | Các tập đóng | danh sách khác biệt | Charm |
| dGenMax | Các tập tối đại | danh sách khác biệt | GenMax |
Ba bản có chữ d ở đầu cho ra cùng kết quả như bản gốc; chúng chỉ thay danh sách giao dịch bằng danh sách khác biệt để tính cho nhanh hơn.
Vào từng bài
Nền tảng
Bảng dạng dọc, danh sách giao dịch, danh sách khác biệt, và phân biệt ba loại tập phổ biến. Nên học trước tiên.
Charm
Tìm các tập đóng nhờ bốn tình huống so sánh danh sách giao dịch.
GenMax
Tìm các tập tối đại, có cắt tỉa bằng kiểm tra bao trùm.
dEclat
Tìm tất cả tập phổ biến bằng danh sách khác biệt.
dCharm
Charm làm bằng danh sách khác biệt.
dGenMax
GenMax làm bằng danh sách khác biệt.