Search

The sheer size of all frequent itemsets is one challenging problem in data mining research. Based on both closed itemset and maximal itemset, meta itemset which is a new concise representation of frequent itemset is proposed. It is proved that both closed itemset and maximal itemset are special cases of meta itemset. The set of all closed itemsets and the set of all maximal itemsets form the upper bound and the lower bound of the set of all meta itemsets. Then, property and pruning strategies of meta itemset are discussed. Finally, an efficient algorithm for mining meta itemset is proposed. Experimental results show that the proposed algorithm is effective and efficient. [ABSTRACT FROM AUTHOR]

How to find the core attributes is important for attribute reduction based on rough set. However, there are few literatures discussing this topic, and most existing works are mainly based on Skowron’s discernibility matrix. Till now, there are main three kinds of core attributes: core of the skowron’s discernibility matrix (denoted by Core1(C)), core of the positive region (denoted by Core2(C)), and core of the information entropy (denoted by Core3(C)). Some researchers have been pointed out that these three kinds of cores are not equivalent to each other. Based on the above three kinds of core attributes, we at first propose three kinds of simplified discernibility matrices and their corresponding cores, which are denoted by SDCore1(C), SDCore2(C) and SDCore3(C), respectively. Then it is proved that Core1(C) = SDCore1(C), Core2(C) = SDCore2(C), and Core3(C) = SDCore3(C). Finally, based on three proposed simplified discernibility matrices and their corresponding cores, it is proved that Core2(C) $${\subseteq}$$ Core3(C) $${\subseteq}$$ Core1(C). [ABSTRACT FROM AUTHOR]

Because of the inherent computational complexity, mining the complete frequent item-set in dense datasets remains to be a challenging task. Mining Maximal Frequent Item-set (MFI) is an alternative to address the problem. Set-Enumeration Tree (SET) is a common data structure used in several MFI mining algorithms. For this kind of algorithm, the process of mining MFI's can also be viewed as the process of searching in set-enumeration tree. To reduce the search space, in this paper, a new algorithm, Index-MaxMiner, for mining MFI is proposed by employing a hybrid search strategy blending breadth-first and depth-first. Firstly, the index array is proposed, and based on bitmap, an algorithm for computing index array is presented. By adding subsume index to frequent items, Index-MaxMiner discovers the candidate MFI's using breadth-first search at one time, which avoids first-level nodes that would not participate in the answer set and reduces drastically the number of candidate itemsets. Then, for candidate MFI's, depth-first search strategy is used to generate all MFI's. Thus, the jumping search in SET is implemented, and the search space is reduced greatly. The experimental results show that the proposed algorithm is efficient especially for dense datasets. [ABSTRACT FROM AUTHOR]

Abstract: Efficient algorithms for mining frequent itemsets are crucial for mining association rules as well as for many other data mining tasks. Methods for mining frequent itemsets have been implemented using a BitTable structure. BitTableFI is such a recently proposed efficient BitTable-based algorithm, which exploits BitTable both horizontally and vertically. Although making use of efficient bit wise operations, BitTableFI still may suffer from the high cost of candidate generation and test. To address this problem, a new algorithm Index-BitTableFI is proposed. Index-BitTableFI also uses BitTable horizontally and vertically. To make use of BitTable horizontally, index array and the corresponding computing method are proposed. By computing the subsume index, those itemsets that co-occurrence with representative item can be identified quickly by using breadth-first search at one time. Then, for the resulting itemsets generated through the index array, depth-first search strategy is used to generate all other frequent itemsets. Thus, the hybrid search is implemented, and the search space is reduced greatly. The advantages of the proposed methods are as follows. On the one hand, the redundant operations on intersection of tidsets and frequency-checking can be avoided greatly; On the other hand, it is proved that frequent itemsets, including representative item and having the same supports as representative item, can be identified directly by connecting the representative item with all the combinations of items in its subsume index. Thus, the cost for processing this kind of itemsets is lowered, and the efficiency is improved. Experimental results show that the proposed algorithm is efficient especially for dense datasets. [Copyright &y& Elsevier]