Computer >> Máy Tính >  >> Lập trình >> Lập trình

Làm thế nào chúng tôi có thể khai thác các tập phổ biến đã đóng?

Trong cách tiếp cận đơn giản, nó có thể khai thác toàn bộ tập phổ biến thường xuyên và sau đó loại bỏ từng tập phổ biến thường xuyên là một tập con thích hợp và cung cấp hỗ trợ tương tự như tập phổ biến hiện tại.

Phương thức này có thể lấy ra 2 100 −1 tập phổ biến để có được tập phổ biến có độ dài 100, tất cả trước khi nó có thể bắt đầu loại bỏ các tập phổ biến thừa. Một kỹ thuật được khuyến nghị là tìm kiếm các tập phổ biến thường xuyên đã đóng một cách chính xác trong giai đoạn khai thác. Điều này cần chúng tôi cắt bỏ khu vực tìm kiếm ngay khi nó có thể xác định phương pháp của các tập hợp vật phẩm đã đóng trong quá trình khai thác. Có nhiều chiến lược cắt tỉa khác nhau bao gồm những điều sau đây -

Hợp nhất mục - Nếu mỗi giao dịch bao gồm một tập phổ biến X cũng bao gồm một tập phổ biến Y nhưng không phải một tập hợp con thích hợp nào đó của Y, do đó X ∪Y tạo thành một tập phổ biến đóng thường xuyên và không cần phải tìm kiếm một số tập phổ biến bao gồm X nhưng không có Y.

Cắt tỉa tập hợp phụ - Nếu một tập phổ biến X là một tập con thích hợp của một tập phổ biến thường xuyên được phát hiện trước đó Y và support_count (X) =support_count (Y), thì X và tất cả các con của X trong cây liệt kê không thể là tập phổ đóng thường xuyên và do đó có thể cắt tỉa.

Bỏ qua mục - Trong khai thác đầu tiên theo chiều sâu của các tập phổ đóng, ở mọi cấp, có thể có tập hợp tiền tố X liên quan đến bảng tiêu đề và cơ sở dữ liệu dự kiến. Nếu một mục thường xuyên cục bộ p có hỗ trợ tương tự trong nhiều bảng tiêu đề ở một số cấp, nó có thể loại bỏ p khỏi bảng tiêu đề ở các cấp lớn hơn một cách an toàn.

Khi một tập phổ biến mới được thay đổi, điều cần thiết là phải triển khai hai loại kiểm tra đóng như sau -

  • Kiểm tra cường độ cao - Nó có thể kiểm tra xem tập phổ biến mới này có phải là tập thay thế của một số tập phổ biến đã đóng trước đó với sự hỗ trợ tương tự hay không.

  • Kiểm tra tập hợp con - Nó có thể kiểm tra xem tập hợp vật phẩm mới được phát hiện có phải là tập hợp con của tập hợp vật phẩm đã đóng được tìm thấy trước đó hay không với sự hỗ trợ tương tự.

Nó có thể áp dụng các kỹ thuật cắt tỉa hợp nhất vật phẩm theo cấu trúc chia để trị, sau đó kiểm tra tập siêu cấp thực sự được tích hợp sẵn và không bắt buộc phải triển khai kiểm tra tập hợp siêu cao một cách rõ ràng. Điều này là do nếu một tập phổ biến X∪Y được phát hiện muộn hơn tập phổ biến X và mang hỗ trợ tương tự như X, thì nó phải nằm trong cơ sở dữ liệu dự kiến ​​của X và lẽ ra phải được tạo ra trong quá trình hợp nhất tập hợp.

Nó có thể giúp kiểm tra tập hợp con, một cây mẫu nén có thể được xây dựng để hỗ trợ tập hợp các tập vật phẩm đã đóng được khai thác. Cây mẫu giống về cơ chế đối với cây FP ngoại trừ việc tất cả các tập vật phẩm đã đóng được phát hiện được lưu một cách rõ ràng trong các nhánh cây tương ứng.