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

Tập mục thường xuyên tối đa (Maximal Frequent Itemsets) là gì?

Một tập mục thường xuyên tối đa (maximal frequent itemset) được biểu diễn như một tập mục thường xuyên mà không có siêu tập (supersets) trực tiếp nào là thường xuyên. Các tập mục trong lưới được chia thành hai nhóm như những cái thường xuyên và những cái không thường xuyên. Một biên tập mục thường xuyên (frequent itemset border), được xác định bởi một đường nét đứt.

Mỗi tập mục nằm trên biên là thường xuyên, trong khi những cái nằm dưới biên (các nút được tô đen) là không thường xuyên. Giữa các tập mục ở gần biên, {a, d}, {a, c, e}, và {b, c, d, e} được coi là tập mục thường xuyên tối đa vì các siêu tập trực tiếp của chúng là không thường xuyên.

Một tập mục bao gồm {a, d} là thường xuyên tối đa vì các siêu tập trực tiếp, {a, b, d}, {a, c, d}, và {a, d, e}, là không thường xuyên. Ngược lại, {a, c} là không tối đa vì siêu tập trực tiếp, {a, c, e}, là thường xuyên.

Tập mục thường xuyên tối đa cung cấp một biểu diễn nhỏ gọn (compact representation) của các tập mục thường xuyên. Nói cách khác, chúng hình thành tập nhỏ nhất các tập mục từ đó tất cả các tập mục thường xuyên có thể được suy ra. Ví dụ, các tập mục thường xuyên có thể được chia thành hai nhóm như sau:

  • Tập mục thường xuyên bắt đầu bằng mặt hàng a và có thể bao gồm mặt hàng c, d, hoặc e. Nhóm này chứa tập mục bao gồm {a}, {a, c}, {a, d}, {a, e}, và {a, c, e}.
  • Tập mục thường xuyên bắt đầu bằng mặt hàng b, c, d, hoặc e. Nhóm này chứa tập mục bao gồm {b}, {b, c}, {c, d}, {b, c, d, e}, v.v.

Tập mục thường xuyên áp dụng trong nhóm đầu tiên là tập con của {a, c, e} hoặc {a, d}, trong khi những cái áp dụng trong nhóm thứ hai là tập con của {b, c, d, e}. Do đó, các tập mục thường xuyên tối đa {a, c, e}, {a, d}, và {b, c, d, e} cung cấp biểu diễn nhỏ gọn của các tập mục thường xuyên.

Tập mục thường xuyên tối đa cung cấp biểu diễn giá trị cho các tập dữ liệu có thể tạo ra rất nhiều tập mục thường xuyên, vì có số mũ các tập mục thường xuyên trong dữ liệu như vậy. Phương pháp này thực tế chỉ khi một thuật toán hiệu quả tồn tại để rõ ràng tìm tập mục thường xuyên tối đa mà không phải liệt kê các tập con.

Mặc dù cung cấp biểu diễn nhỏ gọn, tập mục thường xuyên tối đa không bao gồm dữ liệu hỗ trợ (support information) của các tập con của chúng. Ví dụ, hỗ trợ của các tập mục thường xuyên tối đa {a,c,e}, {a,d}, và {b,c,d,e} không đưa ra bất kỳ ý tưởng nào về hỗ trợ của các tập con của chúng.

Một lần lặp thêm qua tập dữ liệu là cần thiết để quyết định số đếm hỗ trợ của các tập mục thường xuyên không tối đa. Trong một số trường hợp, có thể mong muốn có một biểu diễn tối thiểu của các tập mục thường xuyên bảo toàn dữ liệu hỗ trợ.