先给出 AIS 和 SETM 算法的概要, 再针对其算法,把 Apriori 和 AprioriTid 算法的运行过程与之相比较. 接着阐述如何对虚拟数据库进行求值,并且给出运算结果. 最后来总结把 Apriori 和 AprioriTid 算法合并形成 AprioriHybrid 算法在运行上的优点所在, 并证明它的递推性. 3.1 AIS ??当扫描数据库时,生成候选项集且被快速统计;浏览一个事务后,确定前一步找出的哪个频繁项集包含于此事务中, 新的候选项集可通过把事务中的项扩展到这些频繁项集中生成. 频繁项集 l 仅由频繁的项目扩展而成,且这些项目在按字典序排列后会排在 l 中原有的项目之后. 候选集由事务生成并加入到候选项集中继续下一步的运行,否则对应入口记录的条数将会增大,如果他们是之前的事务产生的话. 参考[4] 可对 AIS 算法的细节有更深入的了解. 3.2 SETM ?? SETM 算法是在使用 SQL 时需要计算频繁项集的背景驱动下研究出来的.与 AIS 算法一样, SETM 算法也是快速扫描数据库中的事务产生候选项集, 计算每个候选项集时也一致.但是,使用标准的 SQL 语句运行此算法产生候选集时,把产生候选集与计算分离开来了. 它保存候选项集的复本并与连续结构中的事务 TID 相连接. 过程的最后一步,候选项集的支持度被确定下来并保存和收集在这个连续结构中. SETM 算法记录事务 TID 及其候选项集,为了避免需要运行子集,就利用这个信息确定事务中的频繁项集, k k L C ?是删除不具有最小支持度的候选集后得到的. 假设数据库保存在 TID 列表中, SETM 算法在通过把 kL 存储在 TID 上,就能很容易找出事务中的频繁项集. 实际上,只需要在 TID 列表上对 kL 进行扫描一次就够了,产生候选集可通过有关合并- 链接
全文预览
