1.1.5 优化改进

为了解决上述算法的缺点，研究人员提出了下列解决方案。

基于散列的计数（散列项集到对应的桶中）：一种基于散列的计数可以用于压缩候选k-项集的集合[3]。例如，当扫描数据库中的每个事务，由C1中的候选1-项集产生频繁1-项集L1时，可以将每个事务产生的所有2-项集散列（即映射）到散列表结构的不同桶中（表1-2）。在散列表中，对应的桶计数低于支持度阈值的2-项集不可能是频繁的，因此应该从候选项集中删除。这种基于散列的技术可以显著地压缩需要考察的k-项集（特别是当k=2时）。表1-2给出了用散列函数h（x,y）=（（x的序）×10+（y的序）mod7）创建散列表H2。

注：该散列表在由C1确定L1时通过扫描事务数据库产生。如果最小支持度为3，则桶0、1、3和4中的项集不可能是频繁的，因此它们将不包含在C2中。

事务压缩：压缩进一步迭代扫描的事务数。不包含任何频繁k-项集的事务不可能包含任何频繁（k+1）-项集。因此，这种事务在其后的考虑中，可以加上标记或者删除，因为针对j-项集（j<k）的数据库扫描不再需要它们[4]。

划分：它只需要扫描两次数据库，就能挖掘频繁项集（如图1-1所示）[5]，包含两个阶段。在阶段I，算法把D中的事务划分成n个非重叠的分区。如果D中事务的最小相对支持度阈值为min_sup，则每个分区的最小支持度计数为min_sup×该分区中的事务数。对于每个分区，找出所有的局部频繁项集（即在该分区内的频繁项集）。

频繁项集局部是整个数据库D的频繁项集的超集。然而，D的任何频繁项集至少在某个局部频繁项集中出现过一次。因此，所有局部频繁项集都是D的候选项集。来自所有分区的局部频繁项集作为D的全局候选项集。在阶段II，第二次扫描D，评估每个候选项集的实际支持度，以确定全局频繁项集。划分的目的是使每个分区都能放入内存，以便Apriori算法可以快速地扫描数据分区，找出局部频繁项集。

为了降低这种可能性，使用比最小支持度低的支持度阈值找出S的局部频繁项集（记为LS）。然后，数据库的其余部分用于计算LS中每个项集的实际频度。可以使用一种机制来确定是否所有的频繁项集都包含在LS中。如果LS实际包含了D中的所有频繁项集，则只需要扫描一次D；否则，需要进行第二次扫描，找出在第一次扫描时遗漏的频繁项集。当效率最为关键时，如计算密集的应用，抽样方法特别合适。

动态项数计数：在扫描的不同点添加候选项集。动态项集计数技术将数据库划分为用开始点标记的块[6-7]。不同于Apriori算法仅在每次完整的数据库扫描前确定新的候选，这种算法可以在任何时间点添加新的候选项集。该算法使用该时间点的计数作为实际计数的下界，如果到该时间点为止的计数满足最小支持度，则将该项集添加到频繁项集的集合中，并且可以用来产生更长的候选项集。该算法找出所有频繁项集所需要的数据库扫描次数比Apriori算法少[2]。