数据挖掘——关联分析

关联分析

重要术语

二元表示： 非对称二元变量。在购物篮数据中，出现了的用 1 表示，没出现的用 0 表示。

项集： 数据的所有项的子集称为项集。

支持度计数： 数据中包含这个项集的数据行的个数。

关联规则： 形如$X \rightarrow Y$的蕴含表达式，$X \cap Y = \emptyset$。

关联规则的强度衡量：
支持度：$s(X \rightarrow Y)=\frac{\sigma (X \cup Y)}{N}$,$N$为总记录数
置信度：$c(X \rightarrow Y)=\frac{(\sigma (X \cup Y)}{\sigma (X)}$

关联规则发现： 找出所有超出了支持度阈值和置信度阈值的规则。

1. 频繁项集的产生：发现满足最小支持度阈值的所有项集，被称为频繁项集。
2. 规则的产生：从频繁项集中提取高置信度的规则，被称为强规则。

频繁项集的产生

项集格(lattice structure)：

对有$k$个项的数据集，可能有$2^k-1$个频繁项集(由二次项定理得出)。
最差的方法： 对每个候选项集($2^k-1$)都计算支持度计数。计算复杂度为：$O(NMw)$ ($N$表示事务数，$M$表示候选项数，$w$表示事务的最大宽度)

降低计算复杂度的方法：

1. 减少候选项集的数目($M$)。 先验原理(apriori)，是一种不用计算支持度值而删除某些候选项集的有效方法。
2. 减少比较次数。 使用更高级的数据结构或者存储候选项集或者压缩数据集的方法来减少比较次数。