数据挖掘中提高Apriori效率的方法

菜鸟之家

1、Apriori算法的核心
用频繁的(k – 1)-项集生成候选的频繁 k-项集
用数据库扫描和模式匹配计算候选集的支持度
Apriori 的瓶颈: 候选集生成
巨大的候选集:
10的四次方 个频繁1-项集要生成 10七次方个候选 2-项集
要找尺寸为100的频繁模式，如 {a1, a2, …, a100}, 你必须先产生2100  1030 个候选集
多次扫描数据库：
如果最长的模式是n的话，则需要 (n +1 ) 次数据库扫描
2、改进方法
1,基于Hash的项集计数: 如果一个 k-项集在hash-tree的路径上的一个计数值低于阈值，那他本身也不可能是频繁的。
2,减少交易记录: 不包含任何频繁k-项集的交易也不可能包含任何大于k的频繁集
3,分割: 一个项集要想在整个数据库中是频繁的，那么他至少在数据库的一个分割上是频繁的。
4,采样: 在给定数据的子集上挖掘，使用小的支持度+完整性验证方法
5,动态项集计数: 在添加一个新的候选集之前，先估计一下是不是他的所有子集都是频繁的。