Computer >> Hướng Dẫn Máy Tính >  >> Lập Trình >> Lập Trình

Làm thế nào để khai phá itemset phổ biến đóng (Closed Frequent Itemsets)?

Trong phương pháp ngây thơ, có thể khai phá tập hoàn chỉnh itemset phổ biến và sau đó loại bỏ mỗi itemset phổ biến là tập con đúng của, và cho hỗ trợ tương tự như, một itemset phổ biến hiện có.

Phương pháp này có thể suy ra 2¹⁰⁰−1 itemset phổ biến để đạt được itemset phổ biến độ dài 100, tất cả trước khi có thể bắt đầu loại bỏ itemset dư thừa. Một kỹ thuật đề xuất là tìm kiếm chính xác itemset phổ biến đóng trong giai đoạn khai phá. Điều này yêu cầu cắt giảm không gian tìm kiếm sớm nhất khi có thể xác định phương pháp itemset đóng trong khai phá. Có nhiều chiến lược cắt giảm bao gồm:

Hợp nhất mục (Item merging) − Nếu mỗi giao dịch chứa itemset phổ biến X cũng chứa itemset Y nhưng không chứa siêu tập đúng nào của Y, thì X ∪ Y hình thành itemset đóng phổ biến và không cần tìm kiếm itemset nào chứa X nhưng không Y.

Cắt giảm tập con (Sub-itemset pruning) − Nếu itemset phổ biến X là tập con đúng của itemset đóng phổ biến Y được khám phá trước đó và support_count(X) = support_count(Y), thì X và tất cả con cháu của X trong cây liệt kê tập không thể là itemset đóng phổ biến và do đó có thể cắt giảm.

Bỏ qua mục (Item skipping) − Trong khai phá độ sâu itemset đóng, tại mỗi mức, có thể có itemset tiền tố X liên quan đến bảng header và cơ sở dữ liệu chiếu. Nếu item phổ biến cục bộ p có hỗ trợ tương tự trong nhiều bảng header ở nhiều mức, có thể cắt giảm an toàn p từ bảng header ở mức cao hơn.

Khi một itemset phổ biến mới được tạo, cần thực hiện hai loại kiểm tra đóng:

  • Kiểm tra siêu tập (Superset checking) − Kiểm tra itemset phổ biến mới này có phải là siêu tập của một số itemset đóng tìm thấy trước đó với hỗ trợ tương tự không.
  • Kiểm tra tập con (Subset checking) − Kiểm tra itemset mới khám phá có phải là tập con của itemset đóng tìm thấy trước với hỗ trợ tương tự không.

Nếu áp dụng kỹ thuật cắt giảm hợp nhất mục dưới cấu trúc chia để trị, thì kiểm tra siêu tập thực sự được tích hợp sẵn và không cần thực hiện rõ ràng kiểm tra siêu tập. Điều này vì nếu itemset phổ biến X∪Y được khám phá sau itemset X, và mang hỗ trợ tương tự như X, nó nên ở trong cơ sở dữ liệu chiếu của X và nên đã được tạo trong hợp nhất itemset.

Để hỗ trợ kiểm tra tập con, một cây mẫu nén (compressed pattern-tree) có thể được xây dựng để hỗ trợ tập itemset đóng được khai phá. Cây mẫu tương tự về cơ chế với FP-tree ngoại trừ tất cả itemset đóng khám phá được lưu rõ ràng trong các nhánh cây tương ứng.