The task of mining erasable patterns(EPs)is a data mining problem that can help factory managers come up with the best product plans for the future.This problem has been studied by many scientists in recent times,and ...The task of mining erasable patterns(EPs)is a data mining problem that can help factory managers come up with the best product plans for the future.This problem has been studied by many scientists in recent times,and many approaches for mining EPs have been proposed.Erasable closed patterns(ECPs)are an abbreviated representation of EPs and can be con-sidered condensed representations of EPs without information loss.Current methods of mining ECPs identify huge numbers of such patterns,whereas intelligent systems only need a small number.A ranking process therefore needs to be applied prior to use,which causes a reduction in efficiency.To overcome this limitation,this study presents a robust method for mining top-rank-k ECPs in which the mining and ranking phases are combined into a single step.First,we propose a virtual-threshold-based pruning strategy to improve the mining speed.Based on this strategy and dPidset structure,we then develop a fast algorithm for mining top-rank-k ECPs,which we call TRK-ECP.Finally,we carry out experiments to compare the runtime of our TRK-ECP algorithm with two algorithms modified from dVM and TEPUS(Top-rank-k Erasable Pattern mining Using the Subsume concept),which are state-of-the-art algorithms for mining top-rank-k EPs.The results for the running time confirm that TRK-ECP outperforms the other experimental approaches in terms of mining the top-rank-k ECPs.展开更多
A new algorithm based on an FC-tree （frequent closed pattern tree） and a max-FCIA （maximal frequent closed itemsets algorithm） is presented, which is used to mine the frequent closed itemsets for solving memory an...A new algorithm based on an FC-tree （frequent closed pattern tree） and a max-FCIA （maximal frequent closed itemsets algorithm） is presented, which is used to mine the frequent closed itemsets for solving memory and time consuming problems. This algorithm maps the transaction database by using a Hash table,gets the support of all frequent itemsets through operating the Hash table and forms a lexicographic subset tree including the frequent itemsets.Efficient pruning methods are used to get the FC-tree including all the minimum frequent closed itemsets through processing the lexicographic subset tree.Finally,frequent closed itemsets are generated from minimum frequent closed itemsets.The experimental results show that the mapping transaction database is introduced in the algorithm to reduce time consumption and to improve the efficiency of the program.Furthermore,the effective pruning strategy restrains the number of candidates,which saves space.The results show that the algorithm is effective.展开更多
This paper presents a new efficient algorithm for mining frequent closed itemsets. It enumerates the closed set of frequent itemsets by using a novel compound frequent itemset tree that facilitates fast growth and eff...This paper presents a new efficient algorithm for mining frequent closed itemsets. It enumerates the closed set of frequent itemsets by using a novel compound frequent itemset tree that facilitates fast growth and efficient pruning of search space. It also employs a hybrid approach that adapts search strategies, representations of projected transaction subsets, and projecting methods to the characteristics of the dataset. Efficient local pruning, global subsumption checking, and fast hashing methods are detailed in this paper. The principle that balances the overheads of search space growth and pruning is also discussed. Extensive experimental evaluations on real world and artificial datasets showed that our algorithm outperforms CHARM by a factor of five and is one to three orders of magnitude more efficient than CLOSET and MAFIA.展开更多
Previous research works have presented convincing arguments that a frequent pattern mining algorithm should not mine all frequent but only the closed ones because the latter leads to not only more compact yet complete...Previous research works have presented convincing arguments that a frequent pattern mining algorithm should not mine all frequent but only the closed ones because the latter leads to not only more compact yet complete result set but also better efficiency. Upon discovery of frequent closed XML query patterns, indexing and caching can be effectively adopted for query performance enhancement. Most of the previous algorithms for finding frequent patterns basically introduced a straightforward generate-and-test strategy. In this paper, we present SOLARIA＊, an efficient algorithm for mining frequent closed XML query patterns without candidate maintenance and costly tree-containment checking. Efficient algorithm of sequence mining is involved in discovering frequent tree-structured patterns, which aims at replacing expensive containment testing with cheap parent-child checking in sequences. SOLARIA＊ deeply prunes unrelated search space for frequent pattern enumeration by parent-child relationship constraint. By a thorough experimental study on various real-life data, we demonstrate the efficiency and scalability of SOLARIA＊ over the previous known alternative. SOLARIA＊ is also linearly scalable in terms of XML queries＇ size.展开更多
文摘The task of mining erasable patterns(EPs)is a data mining problem that can help factory managers come up with the best product plans for the future.This problem has been studied by many scientists in recent times,and many approaches for mining EPs have been proposed.Erasable closed patterns(ECPs)are an abbreviated representation of EPs and can be con-sidered condensed representations of EPs without information loss.Current methods of mining ECPs identify huge numbers of such patterns,whereas intelligent systems only need a small number.A ranking process therefore needs to be applied prior to use,which causes a reduction in efficiency.To overcome this limitation,this study presents a robust method for mining top-rank-k ECPs in which the mining and ranking phases are combined into a single step.First,we propose a virtual-threshold-based pruning strategy to improve the mining speed.Based on this strategy and dPidset structure,we then develop a fast algorithm for mining top-rank-k ECPs,which we call TRK-ECP.Finally,we carry out experiments to compare the runtime of our TRK-ECP algorithm with two algorithms modified from dVM and TEPUS(Top-rank-k Erasable Pattern mining Using the Subsume concept),which are state-of-the-art algorithms for mining top-rank-k EPs.The results for the running time confirm that TRK-ECP outperforms the other experimental approaches in terms of mining the top-rank-k ECPs.
基金The National Natural Science Foundation of China(No.60603047)the Natural Science Foundation of Liaoning ProvinceLiaoning Higher Education Research Foundation(No.2008341)
文摘A new algorithm based on an FC-tree （frequent closed pattern tree） and a max-FCIA （maximal frequent closed itemsets algorithm） is presented, which is used to mine the frequent closed itemsets for solving memory and time consuming problems. This algorithm maps the transaction database by using a Hash table,gets the support of all frequent itemsets through operating the Hash table and forms a lexicographic subset tree including the frequent itemsets.Efficient pruning methods are used to get the FC-tree including all the minimum frequent closed itemsets through processing the lexicographic subset tree.Finally,frequent closed itemsets are generated from minimum frequent closed itemsets.The experimental results show that the mapping transaction database is introduced in the algorithm to reduce time consumption and to improve the efficiency of the program.Furthermore,the effective pruning strategy restrains the number of candidates,which saves space.The results show that the algorithm is effective.
文摘This paper presents a new efficient algorithm for mining frequent closed itemsets. It enumerates the closed set of frequent itemsets by using a novel compound frequent itemset tree that facilitates fast growth and efficient pruning of search space. It also employs a hybrid approach that adapts search strategies, representations of projected transaction subsets, and projecting methods to the characteristics of the dataset. Efficient local pruning, global subsumption checking, and fast hashing methods are detailed in this paper. The principle that balances the overheads of search space growth and pruning is also discussed. Extensive experimental evaluations on real world and artificial datasets showed that our algorithm outperforms CHARM by a factor of five and is one to three orders of magnitude more efficient than CLOSET and MAFIA.
基金This work is supported in part by the National Natural Science Foundation of China under Grant No.60573094the National Grand Fundamental Research 973 Program of China under Grant No.2006CB303103+1 种基金the National High Technology Development 863 Program of China under Grant No.2006AA01A101Tsinghua Basic Research Foundation under Grant No.JCqn2005022.
文摘Previous research works have presented convincing arguments that a frequent pattern mining algorithm should not mine all frequent but only the closed ones because the latter leads to not only more compact yet complete result set but also better efficiency. Upon discovery of frequent closed XML query patterns, indexing and caching can be effectively adopted for query performance enhancement. Most of the previous algorithms for finding frequent patterns basically introduced a straightforward generate-and-test strategy. In this paper, we present SOLARIA＊, an efficient algorithm for mining frequent closed XML query patterns without candidate maintenance and costly tree-containment checking. Efficient algorithm of sequence mining is involved in discovering frequent tree-structured patterns, which aims at replacing expensive containment testing with cheap parent-child checking in sequences. SOLARIA＊ deeply prunes unrelated search space for frequent pattern enumeration by parent-child relationship constraint. By a thorough experimental study on various real-life data, we demonstrate the efficiency and scalability of SOLARIA＊ over the previous known alternative. SOLARIA＊ is also linearly scalable in terms of XML queries＇ size.
