Research Of Incremental Updating Algorithm For Association Rules

In the practical application of association rules mining, the mined data always increases, decreases and revises. In order to obtain the expected association rules, users usually adjust the thresholds of minimum support and minimum confidence. The traditional method to deal with this kind of problem is to compute it again with the revised data and threshold, which can not make use of the former computation. As an important problem of association rules mining, the incremental updating of association rules focuses on how to obtain the ideal association rules from making use of the former computation when the original database or the relevant threshold changes. The efficiency of mining process will be greatly improved if the algorithm of association rules can fully makes use of the former computation, instead of applying the new algorithm to the whole transaction database. It is especially important for the large-scale database to update the data dynamically instead of mining from the updated database again and again. The incremental updating algorithm can update data step by step, which can revise and enhance the data which has been provided,and it is a promising goal to various database mining. There are wide applications for the research of incremental updating algorithm of association rules.This study is to deal with incremental updating algorithm for association rules. What we will do is:①To review the algorithm for association rules mining, which is based on the relevant literature and former studies. It focuses on the basic classic association rules mining algorithm and analyzes their positive and negative point; To analyze the search strategy in the algorithm of frequent itemset and summarize the various updating and optimizing strategy of the classic algorithm.②It provides a brief introduction to the NewQAIS algorithm and its application. We have a comparison to Apriori algorithm.③To analyze NewQAIS algorithm's weak point, pointing out improved optimize strategy. Then we provide an improved algorithm of NewQAIS---OFIUA (Ordered Forst Incremental Updating Algorithm).OFIUA algorithm greatly improves the efficiency of computation by introducing the concept of matrix that can transform the transaction to 0-1 matrix by scanning, and compute the support data of itemset by the inner product of vector. To analyze the constitutive feature of the itemset in NewQAIS algorithm, point out its weak point in generative itemset, and introduce the data structure of ordered forest. The ordered tree in ordered forest is independent, which can improve the speed to generate the candidate itemsets in apriori–gen of apriori algorithm. This improved algorithm can be applied not only to update of association rules which is caused by increase of transaction in transaction database, but also to the update of association rules which is caused by the change of the supporting degree with the same transaction database.