[关闭]
@HaomingJiang 2016-05-31T17:18:34.000000Z 字数 2925 阅读 1894

Chp6 Basic Association Analysis

数据挖掘导论 笔记



6.1 Defination

支持度
置信度

关联规则的要求:

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

6.2 Apriori算法

产生候选集办法:(剪枝)
计算支持度:使用hash树(对一个事物,产生所有的k项集,利用hash树比较候选集,计算支持度)
置信度剪枝:若,既然频繁项集可以以树的形式产生规则,就可以按这个规则剪枝

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
(in the next section)
喝咖啡的人占80%,而喝茶中喝咖啡的人有75%,就算置信度高也有问题。(PS:是不是该考虑和bayes因子一样的东西)
客观度量可以用来解决这个局限性

Lift

Interest factor

like the independency test:
implies indenpency
implies negative correlation
implies positive correlation

limitation of interest factor:

term
880 50
50 20

I = 1.02

term
20 50
50 880

I = 4.08

correlation coefficient

limitation: 上两例的一样,因为他将同时出现或不出现视为同等重要。比较适合分析对称的二元变量

IS metric

和余弦度量一样

limitation: 因为基于支持度,会出现和置信度一样的问题

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

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

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

6.8 Skewness

带来许多问题
难以设置minsup:高会滤掉有意思的低频项,低会产生大量规则,计算量大,提取出高频项和低频项关联的虚假模式,叫cross support
支持度比率:
则被称为交叉支持模式
可以由检查指定项集的最低置信度规则来检测交叉模式。
1.
所以最低置信度的规则左边只有一个项
2. 在经过1筛选过后,取
有最小支持度
3. 可得最小置信度为 这个是反单调的,确保h置信度大于阈值hc即可
h置信度可以保证内部是强关联的,hyperclique pattern超团模式

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注