高级检索

    一种自顶向下挖掘长频繁项的有效方法

    An Effective Top-Down Data Mining Method for Long Frequents

    • 摘要: Apriori算法已经成为关联规则挖掘中的经典算法 ,被广泛地用于商业决策、银行贷款、金融保险等几乎所有的关联规则挖掘领域之中 该方法是一种自底向上的有效挖掘方法 ,对于长频繁项 (如 10 0个项目 )该方法会遇到非常耗时的巨大计算问题 采用了一种新的自上而下挖掘方法 ,提出了事务项目关联信息表、关键项目、项目约简、投影数据库等新概念 ,利用投影、约简等方法在候选项集生成过程中及时修剪重复分支 ,使算法的实际效率大为提高 ,较好地解决了长频繁项的挖掘问题 通过计算机实验和算法分析证明了这种挖掘方法的有效性和完备性 新算法的计算复杂度与项目集平均约简项长度有关 ,估计为 0 5×M3 N×O(2 S×N′2 ) 其中 ,S为系统在用户给定最小支持度条件下的平均约简项长度 ,N′是数据库所对应关系的元组数 ,N为记录数 ,M为项目集平均长度 对于长频繁项来说S很小 ,计算复杂度接近多项式时间

       

      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.

       

    /

    返回文章
    返回