Please use this identifier to cite or link to this item:
|Title:||A new concise representation of frequent itemsets using generators and a positive border|
|Authors:||Liu, G. |
Frequent itemset mining
|Source:||Liu, G., Li, J., Wong, L. (2008). A new concise representation of frequent itemsets using generators and a positive border. Knowledge and Information Systems 17 (1) : 35-56. ScholarBank@NUS Repository. https://doi.org/10.1007/s10115-007-0111-5|
|Abstract:||A complete set of frequent itemsets can get undesirably large due to redundancy when the minimum support threshold is low or when the database is dense. Several concise representations have been previously proposed to eliminate the redundancy. Generator based representations rely on a negative border to make the representation lossless. However, the number of itemsets on a negative border sometimes even exceeds the total number of frequent itemsets. In this paper, we propose to use a positive border together with frequent generators to form a lossless representation. A positive border is usually orders of magnitude smaller than its corresponding negative border. A set of frequent generators plus its positive border is always no larger than the corresponding complete set of frequent itemsets, thus it is a true concise representation. The generalized form of this representation is also proposed. We develop an efficient algorithm, called GrGrowth, to mine generators and positive borders as well as their generalizations. The GrGrowth algorithm uses the depth-first-search strategy to explore the search space, which is much more efficient than the breadth-first-search strategy adopted by most of the existing generator mining algorithms. Our experiment results show that the GrGrowth algorithm is significantly faster than level-wise algorithms for mining generator based representations, and is comparable to the state-of-the-art algorithms for mining frequent closed itemsets. © Springer-Verlag London Limited 2007.|
|Source Title:||Knowledge and Information Systems|
|Appears in Collections:||Staff Publications|
Show full item record
Files in This Item:
There are no files associated with this item.
checked on Dec 5, 2017
WEB OF SCIENCETM
checked on Dec 5, 2017
checked on Dec 11, 2017
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.