知识卡片
Apriori的扫描代价与提速
根本开销:Apriori 每验证一层候选,都要把整个交易库扫一遍来计数。层数随最长频繁项集增长,单次扫描成本随数据量增长,两者相乘就是它的主要瓶颈;低阈值下候选集本身还可能爆炸。
五种缓解手段: - 分区:把库切成若干块,任何全局频繁项集必在至少一个分区中频繁,可先在分区内挖候选再全局校验。 - 采样:用较低阈值在子集上挖,再回全库核对,牺牲完备性换速度。 - 交易压缩:不含任何频繁 k 项集的交易,在后续扫描中不可能再贡献计数,可直接丢弃。 - 基于哈希的项集计数:用哈希桶计数提前判定某候选不可能频繁,省掉精确计数。 - 动态项集计数:只把子集都已被估计为频繁的项集加入候选,并允许在不同层之间提前启动计数。
判断:五种手段都在“少扫、少算、早剪”上做文章,代价是可能漏掉规则,需按业务对完备性的要求取舍。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第5章 高级分析理论与方法:关联规则 · 查看原书依据
然而,取决于数据集大小,Apriori算法可以是计算代价昂贵的。对于每一个级别的支持度,该算法需要扫描整个数据库以获得结果。因此,随着数据库的增长,它在每次运行计算时会需要更多的时间。
参考来源
- 位置:《数据科学与大数据分析 数据的发现 分析 可视化与表示》第5章 高级分析理论与方法:关联规则(源文件:extracted/数据科学与大数据分析 数据的发现 分析 可视化与表示/_epub-src/text/part0015_split_007.html)
- 结论依据:5.7 节指出 Apriori 需为每一级支持度扫描整个数据库、随库增长耗时增加,并列出分区、采样、交易压缩、哈希计数、动态项集计数五种改进方法。
- 原始内容:然而,取决于数据集大小,Apriori算法可以是计算代价昂贵的。对于每一个级别的支持度,该算法需要扫描整个数据库以获得结果。因此,随着数据库的增长,它在每次运行计算时会需要更多的时间。