输入:数据库D,最小支持数minSupNum 输出:D中的频繁项目集L 算法描述: ① L’1 = findFrequentOneItemSets(D); //扫描数据库D生成1-项集的集合L’1。 ② for each OneItemSet 1, TIDS(X1)>ÎL’1 //生成频繁1-项集的集合 if (|TIDS(X1)| ≥ minSupNum) L = L ∪ {1, |TIDS(X1)|>}; else L’1 = L’1 - {1, TIDS(X1)>}; ③ for (k=2; L’k-1≠Ф; k++) L’k = L’k-1∞L’k-1; For each k_ItemSet k, TIDS(Xk)> ÎL’k if (|TIDS(Xk)| ≥ minSupNum) L = L ∪ {k, |TIDS(Xk)|>}; else L’k = L’k - {k, TIDS(Xk)>}; ④ return L;
3.3 例举
设数据库D表1所示,最小支持数minSupNum=4,运行改进的算法的过程如图所示:4 总结 改进的Apriori算法,只是在生成L’1时进行了一次数据库扫描,在之后的迭代过程中不需要扫描数据库。与文献2,3,4,5中提出的改进算法相比,使用本文提出的算法大大降低了I/O负载,使得频繁项目集的发现速度大大提高,尤其是在项目集长度较大的情况下。算法的迭代过程不需要复杂的计算,项目集连接仅仅使用集合的并、交运算即可完成,使得该算法易于实现,相信该算法具有一定的理论与实用价值。 但是该算法也有不足:为了减少I/O负载,要求在第一次扫描时把所有的信息装入内存,虽然本算法对数据库进行编码,以二元组的形式存储项集,但是数据挖掘都是基于海量数据的,因此,算法运行时需要大量内存,对此将在今后的研究中进行改进。
参考文献
[1] R. Agrawal, T. Imielinski, and A. Swami. Mining association rules between sets of items in large databases. Proceedings of the ACM SIGMOD Conference on Management of data, pp. 207-216, 1993[2] A. Savasere, E. Omiecinski, and S. Navathe. An efficient algorithm for mining association rules in large databases. Proceedings of the 21st International Conference on Very large Database, 1995[3] J. S. Park, M. S. Chen, and P. S. Yu. An effective hash-based algorithm for mining association rules. Proceedings of ACM SIGMOD International Conference on Management of Data, pages 175-186, San Jose, CA, May 1995[4] H. Mannila, H. Toivonen, and A. Verkamo. Efficient algorithm for discovering association rules. AAAI Workshop on Knowledge Discovery in Databases, 1994, pp. 181-192[5] H. Toivonen. Sampling large databases for association rules. Proceedings of the 22nd International Conference on Very Large Database, Bombay, India, September 1996[6] 罗可, 贺才望. 基于Apriori算法改进的关联规则提取算法. 计算机与数字工程. 2006, 34(4):48-51,55[7] 蔡伟杰,杨晓辉等.关联规则综述.计算机工程.2001, 27(5):31-33,49收稿日期:11月3日 修改日期:11月15日作者简介: 杨光 男 1976-2 助教(硕士);王瑞 女 1978 助教(硕士)。