基于有序树的时空关联规则数据挖掘的应用

杨井荣，柳 军

(成都理工大学 工程技术学院，四川 乐山 614007)

0 引 言

目前Apriori算法仍是具有影响力的典型数据挖掘算法，在文献[1]中全面化、系统化、深入化地介绍了该算法，Apriori算法中的两个设计缺陷被发现，这两个缺陷都是与性能效率有关。在算法执行过程中，对于事务数据库的多次读取写入操作，内外存之间频繁进行数据交互导致执行效率大大降低；在算法的中间阶段，候选项集的大量产生，算法的中间过程过于庞大，无论时间消耗是空间消耗都是巨大的。

针对Apriori算法存在的性能问题，研究人员纷纷提出了改进算法。在众多改进算法中，如文献[2]介绍的Partition算法，影响算法的执行效率的关键是如何设定划分后的阈值；文献[3]介绍的Hash算法，影响算法空间效率在于需要建立Hash表；文献[4]介绍的FP-tree(频繁增长模式树)算法，影响算法效率在于存储空间的限制，因为频繁模式增长树的生成随着数据库规模的增大而增大；另外，文献[5]中还介绍了压缩数据的改进算法，算法的依据是按频繁项集的先验性质。

1 关联规则数据挖掘概念及原理

1.1 关联规则

设I={i1,i2,…,im}是一个属性(字段)集合，事务数据库D={t1,t2,…,tn}是一个集合，它的元素全部是集合，即关键字标识TID的集合，每个事务ti(i=1,2,…,n)是I中一组属性集合，即ti∈I，其所含属性个数称为事务长度。关联规则[6]在离散数学中，定义为X=>Y的蕴涵式，其中X⊆I，Y⊆I，X∩Y=∅。关联规则的蕴涵式X=>Y成立的条件有2个:

第一，它要具有支持度support(X=>Y)=count(X∪Y)/‖D‖，在定义中，‖D‖为集合D的基数。count(X)代表项集X在D中出现的次数。最小支持度的定义：由用户确定的一个百分比，即项集A的基数与集合D的基数的百分比，记作Minsupport(最小支持度)。