数据挖掘——关联规则挖掘

关联数据挖掘

关联分析用于发现隐藏在大型数据集中的令人感兴趣的联系，所发现的模式通常用关联规则或频繁项集的形式表示。

关联规则反映一个事物与其它事物之间的相互依存性和关联性。如果两个或者多个事物之间存在一定的关联关系，那么，其中一个事物发生就能够预测与它相关联的其它事物的发生。

定义：频繁项集

项集（Itemset）

• 包含0个或多个项的集合
  • 例子：{Milk, Bread, Diaper}
• k-项集
  • 如果一个项集包含k个项

支持度计数（Supportcount）($\sigma$)

• 包含特定项集的事务个数
• 例如： $\sigma$({Milk,Bread,Diaper}) = 2

支持度（Support）

• 包含项集的事务数与总事务数的比值
• 例如： s({Milk,Bread, Diaper}) = 2/5

频繁项集（FrequentItemset）

• 满足最小支持度阈值（minsup ）的所有项集

频繁闭项集

• 所谓闭项集，就是指一个项集X，它的直接超集的支持度计数都不等于它本身的支持度计数。如果闭项集同时是频繁的，也就是它的支持度大于等于最小支持度阈值，那它就称为闭频繁项集。

最大频繁项集
最大频繁项集是这样的频繁项集，它的直接超集都不是频繁的

关联规则

关联规则是形如X →Y的蕴含表达式, 其中 X 和 Y 是不相交的项集

• 例子：{Milk, Diaper} →{Beer}

关联规则的强度

• 支持度 Support (s)
  确定项集的频繁程度
• 置信度 Confidence （c）
  确定Y在包含X的事务中出现的频繁程度

关联规则挖掘问题：

给定事务的集合 T, 关联规则发现是指找出支持度大于等于minsup并且置信度大于等于minconf的所有规则, minsup和minconf是对应的支持度和置信度阈值

具体挖掘过程

大多数关联规则挖掘算法通常采用的一种策略是，将关联规则挖掘任务分解为如下两个主要的子任务：

• 频繁项集产生（Frequent Itemset Generation）
  • 其目标是发现满足最小支持度阈值的所有项集，这些项集称作频繁项集。
• 规则的产生（Rule Generation）
  • 其目标是从上一步发现的频繁项集中提取所有高置信度的规则，这些规则称作强规则（strong rule）。

降低产生频繁项集计算复杂度的方法：

1. 减少候选项集的数量
   • 先验原理：(Apriori)
2. 减少比较的次数
   • 替代将每个候选项集与每个事务相匹配，可以使用更高级的数据结构，或存储候选项集或压缩数据集，来减少比较次数(FPGrowth)

Apriori

先验原理：

• 如果一个项集是频繁的，则它的所有子集一定也是频繁的
• 相反，如果一个项集是非频繁的，则它的所有超集也一定是非频繁的

需要一提的是Apriori中所运用到的项的连接准则：

项的连接准则：去掉尾项之后如果二者一样则可以连接
例如本例中{A,C},{B,C},{B,E},{C,E}四者，只有{B,C},{B,E}，两者去掉尾项后的B是相等的，所以是可以连接的{B,C,E}

Apriori算法特点：

优点

• 使用先验性质，大大提高了频繁项集逐层产生的效率
• 简单易理解；数据集要求低

缺点

• 多次扫描数据库
• 候选项规模庞大
• 计算支持度开销大

Apriori算法需要反复的生成候选项，如果项的数目比较大，候选项的数目将达到组合爆炸式的增长

提高Apriori算法性能的方法：

产生关联规则

任务描述：给定频繁项集Y, 查找Y的所有非空真子集$X\in Y$，使得 $X\to Y–X$ 的置信度超过最小置信度阈值minconf

• 例子：If {A,B,C} is a frequent itemset, 候选规则如下：
  $$\begin{gathered} AB\to C \\ A\to BC \\ AC\to B \\ B\to AC \\ BC\to A \\ C\to AB \end{gathered}$$
  如果 |Y| = k, 那么会有 2k–2 个候选关联规则 (不包括 $Y\to \varnothing 、\varnothing \to Y$）

如何高效地从频繁项集中产生关联规则?

• 通常置信度不满足反单调性（anti-monotone property ），例如：
• c(ABC →D) 可能大于也可能小于 c(AB →D)
• 但是，针对同一个频繁项集的关联规则，如果规则的后件满足子集关系，那么这些规则的置信度间满足反单调性
• e.g., $$\begin{gathered} Y=A,B,C,D \\ c(ABC\to D)\ge c(AB\to CD)\ge c(A\to BCD) \end{gathered}$$