An enhanced approximation algorithm to find minimum representative pattern sets

Abstract

The problem of selecting as few as the possible number of sets that would cover the whole universal set is called a set cover. The commonly used set cover algorithm GreedySetCover gives a better approximation result. There are various alternative algorithms for GreedySetCover are proposed in the research, depending on the nature of the problem. This paper proposes an enhanced GreedySetCover algorithm such as MaxFrequentGroupGreedy to find the minimum number of representative pattern sets by combining two or more maximum frequent itemsets groups and checking set cover among them. The groups are combined by using the percentage difference formula and set cover is done by removing the itemset which is contained in another itemset in the combined group. The effectiveness of this approach is tested on frequent itemsets which are determined from NCFP-tree and ModifiedRPset algorithms and a reduced number of representative itemsets is obtained. The reduced itemsets approximate all other itemsets.