数据挖掘导论__第6章_关联分析_2017.ppt

零加性 客观度量M在零加操作下是不变的，如果增加f00而保持相依表中所有其他的频度不变并不影响M的值. 对文档分析或购物篮分析这样的应用，期望度量多在零加操作下保持不变。满足零加性的度量包括余弦（IS）和Jaccard度量，而不满足该性质的度量包括兴趣因子、PS、几率和￠系数。 缩放性 客观度量M在行/列缩放操作下是不变的，如果M（T）=M（T’），其中T是频度计数为[f11,f00,f10,f01]的相依表。T‘是频度计数为[k1k3f11, k2k3f10, k1k4f01, k2k4f00]的相依表。 Male Female High 30 20 50 Low 40 10 50 70 30 100 Male Female High 60 60 120 Low 80 30 110 140 90 230 表6-16显示了1993年和2004年注册某课程的学生的性别和成绩的相依表。 多个二元变量的度量 使用多维相依表，可以扩展到多个变量。 例如，表6-18显示了a，b和c的3维相依表。 c b b a f111 f101 F1+1 a f011 f001 F0+1 F+11 F+01 F++1 c b b a f110 f100 F1+0 a f010 f000 F0+0 F+10 F+00 F++0 6.8 倾斜支持度分布的影响 6.1 问题定义 6.2 频繁项集的产生 6.3 规则的产生 6.4 频繁项集的紧凑表示 6.5 产生频繁项集的其他方法 6.6 FP增长算法 6.7 关联模式的评估 6.8 倾斜支持度分布的影响 倾斜支持度分布的影响 许多关联分析算法的性能受输入数据的性质的影响。例如，Apriori算法的 计算复杂性依赖于数据中的项数和事务的平均长度等性质。 具有倾斜支持度分布的数据集，其中大多数项具有较低或中等频率，但是少数项具有很高的频率。 图6-29显示了一个呈现这种分布的实际数据集的例子。该数据取自PUMS人口普查数据。它包含49046条记录和2113个非对称的二元变量。 选择合适的支持度阈值较难： 如果阈值太高，则可能遗漏涉及G1中较低支持度项的有趣模式。如：在购物篮数据中，顾客很少买的昂贵商品：珠宝等 如果支持度阈值太低，提取出的关联模式大幅增加。可能提取出大量的高频率项（如“牛奶”）与低频率项（如“鱼子酱”）相关联的虚假模式，这样的模式称为交叉支持（cross-support）模式。 定义6.9 交叉支持模式交叉支持模式是一个项集X={i1, i2 , …, ik }，它的支持度比率 小于用户指定的阈值hc 假设牛奶的支持度是70%，糖的支持度是10%，鱼子酱的支持度是0.004%.给定hc=0.01，频繁项集{牛奶，糖，鱼子酱}是一个交叉支持模式，因为r=0.000580.01。 现有的度量（如支持度和置信度），都不足以消除交叉支持模式。 例如：图6-30所示，当hc=0.3时，项集{p,q}, {p,r}, {p,q,r}是交叉支持模式，虽然它们支持度很高为4/30=13.3%。因为它们的支持度比率为0.2，小于阈值0.3. 例如：置信度也无法消除交叉支持模式。因为交叉模式{q}?{p}的置信度达到80%. 图6-30 由于p的大部分事务不包含q，所以由模式{p,q}导出的规则{p} ?{q}的置信度很低。相反，由{r,q}导出的规则{r} ?{q}却有很高的置信度。 这一观察暗示，可以通过检查由给定项集提取的最低置信度规则来检测交叉支持模式。 所以，当我们保证h置信度值超过hc时，就可以消除交叉支持模式。 除可以消除交叉支持模式外，h置信度还具有反单调性的特点，所以可以直接并入挖掘算法。 此外，h置信度能够确保项集中的项之间是强关联的。即超团模式（ hyperclique pattern） 挖掘关联模式的研究问题 6.6 FP增长算法 6.1 问题定义 6.2 频繁项集的产生 6.3 规则的产生 6.4 频繁项集的紧凑表示 6.5 产生频繁项集的其他方法 6.6 FP增长算法 FP增长算法（FP-growth Algorithm） 该算法采用完全不同的方法来发现频繁项集。 该算法不同于Apriori算法的“产生-测试”范型。而是使用一种称作FP树的紧凑数据结构组织数据，并直接从该结构中提取频繁项集。 FP树是一种输入数据的压缩表示，它通过逐个读入事务，并把每个事务映射到FP树中的一条路径来构造。 构造FP树 扫描一次数据集，确定每个项的支持度计数。丢弃非频繁项，而将频繁项按照支持度的递减排序 算法第二次扫描数据集，构建FP树。读入第一个事务{a，b}之后，创建标记为a和b的结点。然后形成null-a-b路径，对该事务编码。该路径上的所有结点的