Chp6 Basic Association Analysis

数据挖掘导论 笔记

6.1 Defination

支持度$s(X \rightarrow Y)=\frac{\sigma(X \cup Y)}{N}$
置信度$c(X \rightarrow Y)=\frac{\sigma(X \cup Y)}{\sigma(X)}$

关联规则的要求：$c \geq minsup, s \geq minconf$

2 steps:
1. 产生平凡项集
2. 产生规则

6.2 Apriori算法

产生候选集办法：$F_1 \times F_{k-1}, F_{k-1} \times F_{k-1}$(剪枝)
计算支持度：使用hash树(对一个事物，产生所有的k项集，利用hash树比较候选集，计算支持度)
置信度剪枝：若$X \rightarrow Y-X \leq minconf => X'\rightarrow Y-X' (X'\subset X)$,既然频繁项集可以以树的形式产生规则，就可以按这个规则剪枝

6.3 频繁项集的紧凑表示

极大频繁项集
闭频繁项集，不丢失支持度信息，用于删除冗余规则
有算法可以直接提取上述紧凑表示

6.4 产生频繁项集的其他方法

项集格遍历
1. 一般到特殊，apriori
2. 特殊到一般，可以用来发现极大频繁项集
3. 双向
4. 等价类，基于前缀或者后缀的等价类
5. DFS，可以用来发现极大频繁项集，一旦发现了之后可以剪枝
6. BFS

数据集的表示会影响IO开销(horizontal & vertical:支持度可以通过取子集并得到)

6.5 FP Growth

6.5.1 FP Tree

是一种输入数据的压缩表示
根节点为null
step1: scan the data set 计算项的支持度，丢弃非频繁项。按支持度递减排序（为了使FP小）
step2: 对于每一个事务，形成一个路径。路径上的点频度都加一

6.5.2 FP-Growth

自底向上的方式探索树。类似于后缀法
每个相同项的节点用指针连起来，这样方便访问
从某个项e开始考虑
思路，先找以e结尾的频繁项集，然后找以ae be ce de结尾的频繁项集，以此类推：
1. 考虑以e结尾的前缀路径的树
2. 首先看他自己是否频繁
3. 把它去了，原来的树转变成条件FP树
3.a 更新前缀路径上的频度，有些不以e结尾
3.b 删除e
3.c 去掉非频繁项,如b
4. 变成发现以a c d为结尾的频繁项集的问题了，递归解决

6.6 Evaluation

第一组标准，objective interestingness measure，based on statistics
第二组标准，揭示了意想不到的信息的。将主管信息加入到模式发现的任务中。
· visualization
· template-based approach
· subjective interestingness measure

6.6.1 Objective Interestingness Measure

based on contingency table
limitation of $minsup & minconf$
$minsup:...$(in the next section)
$minconf:$ 喝咖啡的人占80%，而喝茶中喝咖啡的人有75%，就算置信度高也有问题。(PS:是不是该考虑和bayes因子一样的东西)
客观度量可以用来解决这个局限性

Lift
$lift(A \rightarrow B) = \frac{c(A \rightarrow B)}{s(B)}$

Interest factor
$I(A,B)=\frac{s(A,B)}{s(A)s(B)}$
like the independency test:
$I(A,B) = 1$ implies indenpency
$I(A,B) < 1$ implies negative correlation
$I(A,B) > 1$ implies positive correlation

limitation of interest factor:

I = 1.02

I = 4.08

correlation coefficient
$\phi = \frac{f_{11}f_{00}-f_{01}f_{10}}{\sqrt{f_{1*}f_{*1}f_{2*}f_{*2}}}$
limitation: 上两例的$\phi$一样，因为他将同时出现或不出现视为同等重要。比较适合分析对称的二元变量

IS metric
$IS(A,B)=\frac{s(A,B)}{\sqrt{s(A)s(B)}}$
和余弦度量一样
$IS(A,B)=\sqrt{c(A \rightarrow B)c(B \rightarrow A)}$
limitation: 因为基于支持度，会出现和置信度一样的问题

others
two catalogs: symmetric(用于分析项集) asymmetric(用于分析关联规则)
Table 6-11 6-12 on the book
很多时候他们的度量结果并不一致
为了了解这些度量的区别，需要了解它们的性质
1. 反演性交换0,1 度量不变。具有反演性的度量不适合分析非对称的。
2. 零加性 客观度量在零加操作($f_{00}$增加)下不变。分析词语对的联系购物篮分析需要。
3. 缩放性 客观度量在行列发生放缩一定倍数的时候不变。
总结在Table 6-17

多个二元变量
1. 扩展统计独立性的定义
2. 取各个系数对的min，max or mean...

为了解决辛普森悖论，最好采用分层模型

6.8 Skewness

带来许多问题
难以设置minsup：高会滤掉有意思的低频项，低会产生大量规则，计算量大，提取出高频项和低频项关联的虚假模式，叫cross support
支持度比率:$r(X)=\frac{min(s(i_1),...,s(i_k))}{max(s(i_1),...,s(i_k))}$
$r(X)<h_c，一个指定阈值$则被称为交叉支持模式
可以由检查指定项集的最低置信度规则来检测交叉模式。
1. $conf({i_1,i_2} \rightarrow {i_3,i_4,...,i_k})\leq conf({i_1,i_2,i_3} \rightarrow {i_4,...,i_k})$
所以最低置信度的规则左边只有一个项
2. 在经过1筛选过后，取$i_j,s.t. s(i_j)=max[s(i_1),...,s(i_k)]$
${i_j} \rightarrow \{i_{k \neq i }\}$有最小支持度
3. 可得最小置信度为 $h-confidence(X)=\frac{s(\{i_1,i_2,...,i_k\})}{max[s(i_1),...,s(i_k)]}\leq r(X)$ 这个是反单调的，确保h置信度大于阈值hc即可
h置信度可以保证内部是强关联的，hyperclique pattern超团模式