Abstract:
The apriori algorithm has become a classic method for mining association rules. It is widely applied to various fields such as trade decision-making, bank evaluating credit, finance insurance, etc. This method is an effective down-top algorithm for mining frequents, but it will come across time-consuming huge computing problems in mining long pattern frequent itemsets (e.g. 100 items). A new ideal method of top-down mining frequent items is adopted. New conceptions such as transaction and items association information tables, key-items and reduction items, projection DB, etc are proposed, An effective top-down algorithm for mining long pattern frequents is presented. Proposed algorithms can better solve problems of mining long frequents, the validity of proposed algorithms is proved through the analysis of computing complexity, and examples of computation are also given. The computing complexity of the algorithm is related to the average length of items reduction, the complexity approximating 0.5×M 3N×O(2 S×N′ 2) in worst of case, where S is the average length of items reduction under min-support given by the user, N′ is the number of tuples in the relation generalized by the database, N is numbers of the transaction in databases, and M is the average length of item sets in databases. Using heuristic information for pruning useless candidate frequent itemset, the efficiency of the algorithm is improved notably. It is very effective for mining long frequents since S is very short, and the computing complexity approaches polynomial time.