一种有效的基于图的关联规则挖掘算法  

An efficient graph-based algorithm for discovering association rules

作　　者：陈明[1,2] 史忠植[2] 王文杰[1] 

机构地区：[1]中国科学院研究生院信息科学与工程学院 [2]中国科学院计算技术研究所智能信息处理重点实验室

出　　处：《计算机应用》2006年第11期2654-2656,共3页journal of Computer Applications

基　　金：国家自然科学基金资助项目(60435010;90604017;60675010);国家973项目(2003CB317004);北京市自然科学基金资助项目(4052025)

摘　　要：基于图的关联规则挖掘算法是一种通过构建关联图并直接生成候选频繁项集,进而验证得到所有频繁项集的算法。在该算法中,对候选项集的验证操作占用了大量的时间,为此提出了改进算法。改进主要体现在两个方面:按支持度降序对频繁1项重新编号再构建关联图;利用Apriori性质删减用来生成候选项集的冗余扩展项节点。实验结果表明,在最小支持度阈值较小时,改进算法有效减少了冗余的候选频繁项集,提高了算法的性能。The algorithm for discovering association roles based on graph only scans the database once to construct an association graph and then traverses the graph to generate all frequent itemsets. It costs too much time in proving the candidate frequent itemsets to be really frequent. An improved algorithm was proposed. The improvements were renumbering the frequent 1 item in the support degree descending order and utilizing the Apriori property to prune the redundant extended items which were used to generate the candidate frequent itemsets. Experiment results show that the improved algorithm prune the redundant candidate frequent itemsets when the minimum support degree is small, and the performance is improved.

关 键 词：数据挖掘 关联规则 关联图 频繁项集 

分 类 号：TP311.13[自动化与计算机技术—计算机软件与理论]