陈伟

（淮南联合大学 计算机系，安徽 淮南232038）

通常，关联规则挖掘是指从一个大型的数据集中发现有趣的关联或相关关系，即从数据集中识别出频繁出现的属性值集（Sets of Attribute-Values），也称为频繁项集（Frequent Itemsets,简称频繁集），然后再利用这些频繁集创建描述关联规则的过程。

1 关联规则挖掘算法

关联规则挖掘算法——Apriori算法是使用候选项集找频繁项集的过程。

Apriori算法通过对数据库D的多趟扫描来发现所有的频繁项目集。在第一趟扫描数据库时，对项集I中的每一个数据项计算其支持度，确定出满足最小支持度的频繁1项集的集合L1，然后，L1用于找频繁2项集的集合L2，如此下去……在后续的第k次扫描中，首先以k-1次扫描中所发现的含k-1个元素的频繁项集的集合Lk-1为基础，生成所有新的候选项目集CK（Candidate Itemsets），即潜在的频繁项目集，然后扫描数据库 D，计算这些候选项目集的支持度，最后从候选集CK中确定出满足最小支持度的频繁k项集的集合Lk,并将Lk作为下一次扫描的基础。重复上述过程直到不再发现新的频繁项目集[1]。

2 关联规则算法的改进

从Apriori算法中由k频繁项集生成k+1频繁项集时，首先生成候选项目集Ck+1，该函数不仅要对 k项集的所有符合Apriori算法条件的数据进行交集，并且要判断候选项目集的所有子集是否在k频繁项集中。该函数生成的许多候选项目集并不是要找的频繁项集，但在扫描数据库时，要记录下这些数据的出现次数，这会耗费大量的CPU开销。如果D中的事务数很大，k频繁项集中项数很多，则侯选项目集的元素个数就会很大，例如2 000个频繁 1项集，将产生 2 000×999/2=999 000个候选2项集。