第六章-关联分析

第六章关联分析基本概念与算法•关联分析的基本概念•Apriori算法•FP增长算法•关联模式的评估目录关联分析的基本概念•Itemset–Acollectionofoneormoreitems•Example:{Milk,Bread,Diaper}–k-itemset•Anitemsetthatcontainskitems•Supportcount()–Frequencyofoccurrenceofanitemset–E.g.({Milk,Bread,Diaper})=2•Support–Fractionoftransactionsthatcontainanitemset–E.g.s({Milk,Bread,Diaper})=2/5•FrequentItemset–AnitemsetwhosesupportisgreaterthanorequaltoaminsupthresholdTIDItems1Bread,Milk2Bread,Diaper,Beer,Eggs3Milk,Diaper,Beer,Coke4Bread,Milk,Diaper,Beer5Bread,Milk,Diaper,Coke项集：包含0个或多个项的集合。支持度计数：包含特定项集的事务个数。支持度：未定义。频繁项集：满足最小支持度阈值的所有项集。关联规则形如X-Y的蕴含表达式。{牛奶，啤酒}-{尿布}–偶然么？支持度：同时包含X,Y的事务的比例–可信么？置信度：在包含X的事务中，Y出现的比例关联分析的基本概念4.052|T|)BeerDiaper,,Milk(s67.032)Diaper,Milk()BeerDiaper,Milk,(cTIDItems1Bread,Milk2Bread,Diaper,Beer,Eggs3Milk,Diaper,Beer,Coke4Bread,Milk,Diaper,Beer5Bread,Milk,Diaper,Coke•关联规则挖掘：–第一步：产生频繁项集；•因为规则的支持度仅依赖于XUY的支持度。–第二部：产生关联规则。难点在第一步，指数空间内的搜索。关联分析的基本概念•问题：为什么n个项的数据集中所有的可能规则为：3^n-2^(n+1)+1关联分析的基本概念•先验原理：–如果一个项集是频繁的，那么它的所有子集也一定是频繁的。Apriori算法反单调性：一个项集的支持度不会超过其子集的支持度。基于支持度的剪枝：如果某个项集是非频繁的，其超集也一定是非频繁的。Apriori算法•剪枝实例：Apriori算法蛮力法C(6,1)=6C(6,2)=15C(6,3)=2041剪枝C(6,1)=6C(4,2)=6113Apriori算法•Apriori-gen子函数–蛮力法：枚举所有C(d，k)个k-项集合；–Fk-1×F1方法：组合频繁(k-1)-项集和频繁-1项集。–Fk-1×Fk-1方法:合并前k-2项相同的两个频繁k-1项集。后两者依赖字典序以避免重复生成候选。Apriori算法•支持度计数（1）–蛮力法：对每个事务与当前项做比较，并更新当前第k-候选集中每个元素的支持度计数。Apriori算法•支持度计数（2）–枚举事务的k-项集并与候选的频繁项集比对核心思想：各项字典排序，生成有序排列Apriori算法•支持度计数（3）–使用Hash树进行支持度计数由候选项集构成Hash树，再让每条事务来遍历。Apriori算法1，确定Hash函数，本例为h(p)=pmod3;2，由hash函数确定候选项集的Hash树；3，对每一条事务，采用同样的函数遍历Hash树；4，如果叶子上的候选项集是该事务的子集，则支持度+1；•复杂度分析（1）•影响复杂度的可能因素：–支持度阈值：频繁项集的数量和长度。–项数：储存开销，候选项集数。–事务数：每次Hash剪枝都要扫描数据集。–事务的平均宽度：频繁项集的长度和支持度计数时的遍历Hash树次数。Apriori算法•复杂度分析（2）–生成候选集。采用Fk-1×Fk-1方法，每次合并前需要检查其前k-2项目是否相同，即需要做k-2次比较。在坏的情况下，需要对每一对k-1项集都要进行合并，且每次都需要比较到k-2次的时候才能决定是否合并。Apriori算法•复杂度分析（3）–针对每个k-项候选集构造Hash树并储存。K-项集存入的Hash树的深度为k，因此时间复杂度为：Apriori算法•复杂度分析（4）–候选集剪枝（计算支持度计数之前）。每一个候选k-项集由两个k-1项集合并产生，要附加的候选剪枝步骤来确保该候选的其余k-2个子集是频繁的。因此这一步的复杂度为：？？？×|Fk-1|Apriori算法•复杂度分析（5）–支持度计数。每个事务平均将产生C(w,k)个k-项集。每个k-项集在Hash树查找对应叶子的花费是O(k)。书中认为其开销为：；O(N*Σ(k*C(w,k)))Apriori算法•复杂度分析（6）–未统计的复杂度，包括了：Fk+1×Fk+1时的字典排序；结论：多次扫描事务是Apriori算法的固有缺陷，此算法有效，但是时间复杂度巨大。Apriori算法•生成规则–基于置信度的剪枝•如果规则X-Y-X不满足置信度阈值，则X’-Y-X’的规则也一定不满足置信度阈值，X’为X的子集。Apriori算法先从后件为1的的规则开始剪枝。Apriori算法•FP（频繁模式）树FP增长算法扫描数据集，统计频繁项，抛弃非频繁项，对事务进行排序；第二次扫描数据集，构建并扩充FP树；FP树中包含了：每个节点的指针和计数，另有连接相同节点的指针列表。1.找到后缀e；2.寻找e的前缀路径；3.更新条件FP树；4.迭代下一个结尾Xe；FP增长算法•如果挖掘了很多的关联模式怎么办？•每个关联模式都是非平凡的么？•仅仅依赖支持度和置信度就一定正确么？关联模式的评估{茶}-{咖啡}支持度15%，置信度75%，但是实际上喝咖啡的人爱喝茶的比例（75%）低于所有人中爱喝茶的人（80%）比例。•基于兴趣度的客观度量。–支持度-置信度缺陷原因：忽略了后件的支持度。–提升度（lift）：规则置信度与后件支持度的比值。–对于二元变化，提升度等价于兴趣因子关联模式的评估对于前一例，I(茶，咖啡)=0.15/（0.2×0.8）=0.93571,负相关•别的评价指标–相关分析–IS度量–以及别的对称和非对称的度量关联模式的评估谢谢！