6.3.2.1　频繁项集介绍

对给定的事务数据库，关联规则挖掘要挖掘出其中数据之间的相互关系，并以推导规则的形式来给出这种联系。

目前的关联规则挖掘通常分解为下面两个步骤来执行：

（1）生成频繁项集：其任务是生成所有满足最小支持度阈值的项集，这些被称作频繁项集（Frequent Itemset）。

（2）生成规则：其任务是从上一步生成的频繁项集中提取所有高置信度的规则。

相对频繁项集生成而言，规则的生成较为简单和直观。通常，生成频繁项集所需的计算开销远大于生成规则所需的计算开销。目前，对关联规则挖掘的研究主要集中在提高频繁项集生成的效率上。

6.3.2.2　TDA挖掘算法

TDA挖掘算法的主要思想是：首先扫描水平事务数据库，生成垂直事务数据库，垂直事务数据库按项的支持事务列表的计数排序，并将支持事务列表的计数小于min＿sup（支持度阈值）的项删除即得到TDA事务数据库。根据性质1我们知道，TDA事务数据库的项就是1－项频繁项集L1，且该1－项集是有序的，按照支持事务列表从大到小排列。将L1与L1进行连接得到2项候选项集C2，并根据性质2对C2进行计数得到频繁项集L2。TDA挖掘算法从（k－1）－项频繁项集得到k－项频繁项集与Apriori算法一样，需要经过连接、剪枝、计数，所不同的是在计数时，使用的是TDA事务数据库，使用项集中的各项支持事务列表求交集的方法进行计数，由于项的支持事务列表是有序的，故效率较高。

6.3.2.3　TDA挖掘算法的具体步骤如下

算法：TDA挖掘算法

输入：事务数据库D；最小支持度、最小置信度阈值。(www.daowen.com)

输出：D中的频繁项集。

步骤：

（1）扫描水平事务数据库，得到垂直事务数据库，并将垂直事务数据库按项的支持列表进行排序。

（2）将项的支持事务列表计数小于min＿sup的项删除，得到TDA事务数据库。

（3）扫描TDA事务数据库得到频繁项集L1。

（4）通过L1与L1进行连接得到2项候选项集C2。

（5）通过TDA事务数据库及性质2对C2进行计数，得到2－项频繁项集L2。

（6）将Lk－1与Lk－1（k＞2）进行连接得到k－项集X。

（7）通过频繁子集定理，即频繁k－项集中的子集（k－1）－项集也是频繁项集，对项集X进行剪枝得到候选项集Ck。如｛a，b，c，d，e｝∩｛a，b，c，d，f｝＝｛a，b，c，d，e，f｝，而4项子集｛a，b，c，e，f｝可能不属于4－项频繁集L4。

（8）通过TDA事务数据库及性质3对Ck进行计数，得到k－项频繁项集Lk，如果Lk≠φ，重复第（6）步。