资源描述：
《基于临时表的apriori改进算法》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、从本学科出发，应着重选对国民经济具有一定实用价值和理论意义的课题。课题具有先进性，便于研究生提出新见解，特别是博士生必须有创新性的成果基于临时表的Apriori改进算法摘要Apriori算法在关联规则领域有很大的影响力，然而由于需要过于频繁的扫描数据库及较大的空间消耗，仍然有需要改进的地方。通过对Apriori算法进行深入研究，本文提出了，通过比较分析，获得了较好的效率和性能。关键词关联规则Apriori算法频繁项集临时表0引言数据挖掘的子集，由此累计每个候选项集的支持频度。最终满足最小支持频度的候选项集组成
2、了频繁项集L。然而,像这样产生候选集的开销极大,特别是频繁集很长或最小支持度非常小时。例如,当有104个频繁1-项集时,Apriori算法就会产生多于107个的候选2-项集。针对Apriori算法的瓶颈，本文提出了一种基于临时表的改进算法。2基于临时表的Apriori改进算法基本思想利用了以下两个事实：(1)对于已知规模的事务数据库D，任意一个项集I的出现频繁度与规模小于
3、I
4、的事务无关。所以在第
5、I
6、次扫描数据库D时，可以删除规模小于
7、I
8、的事务记录。(2)k-候选项集中不包含任何(k-1)-项集的项集一定
9、不是频繁项集，因此k次扫描时可以将这样的事务记录立即删除，从而减少了下次需要扫描的记录数。用临时表来完成频繁项集的选择。首先把(k-1)-项集中的第一个项集添加进临时表中；然后把最后一项不同的其它项集添加进临时表，生成k-项集，计算课题份量和难易程度要恰当，博士生能在二年内作出结果，硕士生能在一年内作出结果，特别是对实验条件等要有恰当的估计。从本学科出发，应着重选对国民经济具有一定实用价值和理论意义的课题。课题具有先进性，便于研究生提出新见解，特别是博士生必须有创新性的成果其频繁度，若频繁度大于最小频繁度，则
10、生成该频繁项并保存，否则删除。依此循环，直至生成所有的频繁项。2.改进算法的描述输入：事务数据库D；最小支持度阈值min_sup输出：D的频繁项集L变量说明：Ck：k-候选项集Lk：k-频繁项集Dk：第k次扫描后的数据库L1={large1-itemsets};//D中的1-项集改进前后的分析比较为便于算法的比较,选取文献[6]中Apriori算法使用的AllElectronics某分店的事务数据库中的数据进行算法模拟,如表1所示。TID项的列表T100I1,I2,I5T200I2,I4T300I2,I3T4
11、00I1,I2,I4T500I1,I3T600I2,I3T700I1,I3T800I1,I2,I3,I5T900I1,I2,I3表1假定min_sup=2,Apriori算法执行过程:(1)算法第一次扫描数据库，确定1-项集及各元素的覆盖频度。如图1所示：(2)利用L1⊕L1来产生候选2-项集C2，由C2确定频繁2-项集。如图2所示：(3)利用L2⊕L2进行连接操作，获得候选3-项集C3，为{(I1,I2,I3),(I1,I2,I5),(I1,I3,I5),(I2,I3,I5),(I2,I4,I5)}。根据A
12、priori“一个频繁项集的所有子集也是频繁的”的性质，可以确定后四个项集不可能是频繁的，因此可以删除它们，从而减少了扫描次数。结果如图3所示：图3(4)课题份量和难易程度要恰当，博士生能在二年内作出结果，硕士生能在一年内作出结果，特别是对实验条件等要有恰当的估计。从本学科出发，应着重选对国民经济具有一定实用价值和理论意义的课题。课题具有先进性，便于研究生提出新见解，特别是博士生必须有创新性的成果利用L3⊕L3进行连接操作得到C4，根据Apriori性质可知C4=Φ。算法至此结束。由此可见，Apriori算法
13、每次扫描都要彻底扫描整个数据库D，而改进后的算法及时的将不符合要求的项集删除，从而减少了下次扫描数据库的记录数；Apriori算法进行连接操作时需生成完整的项集，而使用临时表则只需将最后一个不同的项进行连接，从而节省了大量的存储空间。算法比较结果如下表所示：表2说明：表2中数据库规模是指数据库中的记录数，空间耗费是指生成的候选项集所占的空间。从表2可以看到，在扫描规模上，Apriori每次需要对所有的事务数据库进行扫描，而基于临时表的改进算法在第二趟数据扫描后，数据中二元组T200，T300，T500，T60
14、0，T700被删除，第三次的扫描量减至4。在空间耗费上，第一次对个单项进行判断每一个单项占一位空间，需要的空间耗费为。第二次进行JOIN运算时，需要×2=10×2=20个单元空间，第三次进行JOIN运算，需要×3=18个单元空间。临时表压缩算法采用了逐个动态生成频繁项，依次所需空间均为1。4.结束语本文在对Apriori挖掘算法的深入研究基础上，提出了基于临时表的改进算法。通过分析比较，在减少扫描数
