一种基于约束的关联规则挖掘算法

Efficient Algorithm for Mining Association Rules with Constraints

基于约束的关联规则挖掘是一种重要的关联挖掘,能按照用户给出的条件来实行有针对性的挖掘。大多数此类算法仅处理具有一种约束的挖掘,因而其应用受到一定程度的限制。提出一种新的基于约束的关联规则挖掘算法MCAL,它同时处理两种类型的约束:非单调性约束和单调性约束。算法包括3个步骤:第一步,挖掘当前数据集的频繁1项集;第二,应用约束的性质和有效剪枝策略来寻找约束点,同时生成频繁项的条件数据库;最后,递归地应用前面两步寻找条件数据库中频繁项的约束点,以生成满足约束的全部频繁项集。通过实验对比,无论从运行时间还是可扩展性来说,本算法均达到较好的效果。

Association rules mining with constraints is an important association mining method,and it can mine the rules according to the users needs.Most of algorithms deal with one constraint,but in the reality applications,usually there are two or more constraints.In this paper,a novel algorithm for mining association rules with constraint was proposed.It can deal with two constraints simultaneously,namely constraint of anti-monotone and constraint of monotone.The algorithm consists of three phases,first,frequent 1-itemsets are collected over the dataset,second,we apply some prune techniques to the constraints check and a conditional database is generated,and at the end,the final frequent itemsets which are satisfied with the constraints are generated.Experimental results show that the proposed algorithm is efficient both in run time and scalability.