宋小小 陈晓辉 刘冲

桂林理工大学 广西 541004

0 引言

数据挖掘是一门新兴起的交叉学科，主要研究事务数据库、关系数据库中的数据项之间潜在有用的新颖的规律。它的主要方法包括：分类、关联规则、聚类、特征、回归分析、变化和偏差分析等。关联规则挖掘就是从海量的数据中寻找数据项间的关联关系，它是数据挖掘领域中研究的热点问题。关联规则表示数据库中一组对象之间具有某种关联关系的规则，其主要挖掘对象是事务数据库。这种数据库大量的应用在零售业，而条形码技术的发展使得数据的收集变得更加方便、更加完整。关联规则就是在这些交易项目中去寻找某种关联关系。1993年，Agrawal等人首先提出了挖掘顾客交易项目中项集间的关联规则问题，此后诸多的研究人员对关联规则挖掘问题进行了大量的研究与改进。

1 Apriori算法

1.1 算法简介

Apriori算法是1993年由Agrawal等人提出的一个经典的挖掘关联规则算法，它通过对事务数据库的多趟扫描来发现所有的频繁项目集。

该算法采用“逐层搜索”的迭代方法，利用向下封闭特性，由 k-频繁项目集生成(k+1)-频繁项目集。第一趟扫描数据库计算出 1-频繁项目集集合(记为：L1)；接着，反复行下面的两个步骤计算k-频繁项目集，直到生成k-频繁项目集的集合(记为：Lk)为空：

(1) 连接：(k-1)-频繁项目集集合进行自连接运算，生成候选k-项目集集合。

(2) 剪枝：上一步生成的候选k-项目集集合是k-频繁项目集集合的超集。通过扫描数据库计算候选k-项目集集合中每个候选项目集的支持度，并与给定的最小支持度进行比较，较大的就是k-频繁项目集。……