②剪枝：计算k-项集的支持数，根据上面的定义supNum(Rk)=|TIDS(Xk)|，该计算过程不需要再扫描数据库，避免了I/O操作，提高了算法的效率。如果supNum(Rk)≥minSupNum，则< Xk , |TIDS(Xk)|> Î L；否则，从集合L’k中删除Rk。
3.2 改进的算法描述
输入：数据库D，最小支持数minSupNum
输出：D中的频繁项目集L
算法描述：
① L’1 = findFrequentOneItemSets(D); //扫描数据库D生成1-项集的集合L’1。
② for each OneItemSet <X1, TIDS(X1)>ÎL’1 //生成频繁1-项集的集合
if (|TIDS(X1)| ≥ minSupNum)
L = L ∪ {<X1, |TIDS(X1)|>};
else
L’1 = L’1 - {<X1, TIDS(X1)>};
③ for (k=2; L’k-1≠Ф; k++)
L’k = L’k-1∞L’k-1;
For each k_ItemSet <Xk, TIDS(Xk)> ÎL’k
if (|TIDS(Xk)| ≥ minSupNum)
L = L ∪ {<Xk, |TIDS(Xk)|>};
else
L’k = L’k - {<Xk, 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
基于Struts和EJB的Web Service框架研究
柱体表面缺陷区域面积自动检测系统的研究