频繁项集 关联规则产生及其经典算法:
格结构(Lattice Structure)常常被用来枚举所有可能的项集。
1.Apriori算法
Apriori算法基于频繁项集性质的先验知识,使用由下至上逐层搜索的迭代方法,即从频繁1项集开始,采用频繁k项集搜索频繁k+1项集,直到不能找到包含更多项的频繁项集为止。
Apriori算法由以下步骤组成,其中的核心步骤是连接步和剪枝步:
2.FP-Growth算法
频繁模式树增长算法(Frequent Pattern Tree Growth)采用分而治之的基本思想,将数据库中的频繁项集压缩到一棵频繁模式树中,同时保持项集之间的关联关系。然后将这棵压缩后的频繁模式树分成一些条件子树,每个条件子树对应一个频繁项,从而获得频繁项集,最后进行关联规则挖掘。
3.辛普森悖论
虽然关联规则挖掘可以发现项目之间的有趣关系,在某些情况下,隐藏的变量可能会导致观察到的一对变量之间的联系消失或逆转方向,这种现象就是所谓的辛普森悖论(Simpson’s Paradox)。
为了避免辛普森悖论的出现,就需要斟酌各个分组的权重,并以一定的系数去消除以分组数据基数差异所造成的影响。同时必须了解清楚情况,是否存在潜在因素,综合考虑。