An Efficient Subset-Lattice Algorithm for Mining Closed Frequent Itemsets in Data Streams

摘要

There are many applications of using association rules in data streams, such as market analysis, network security, sensor networks and web tracking. Mining closed frequent item sets is a further work of mining association rules, which aims to find the subsets of frequent item sets that could extract all frequent item sets. Formally, a closed frequent item set is a frequent item set which has no superset with the same support as it. One of well-known algorithms for mining closed frequent item sets based on the sliding window model is the New Moment algorithm. However, the New Moment algorithm could not efficiently mine closed frequent item sets in data streams, since they will generate closed frequent item sets and many unclosed frequent item sets. Moreover, when data in the sliding window is incrementally updated, the New Moment algorithm needs to reconstruct the whole tree structure. Therefore, we propose the Subset-Lattice algorithm which embeds the property of subsets into the lattice structure to efficiently mine closed frequent item sets over a data stream sliding window. Moreover, when data in the sliding window is incrementally updated, our Subset-Lattice algorithm will not reconstruct the whole lattice structure.