第六章 关联分析

第六章关联分析

基本概念与算法关联分析的基本概念Apriori算法FP增长算法关联模式的评估目录关联分析的基本概念ItemsetAcollectionofoneormoreitemsExample:{Milk,Bread,Diaper}k-itemsetAnitemsetthatcontainskitemsSupportcount()FrequencyofoccurrenceofanitemsetE.g.({Milk,Bread,Diaper})=2SupportFractionoftransactionsthatcontainanitemsetE.g.s({Milk,Bread,Diaper})=2/5FrequentItemsetAnitemsetwhosesupportisgreaterthanorequaltoaminsupthreshold项集：包含0个或多个项的集合。支持度计数：包含特定项集的事务个数。支持度：未定义。频繁项集：满足最小支持度阈值的所有项集。

关联规则形如X->Y的蕴含表达式。{牛奶，啤酒}->{尿布}偶然么？支持度：同时包含X,Y的事务的比例可信么？置信度：在包含X的事务中，Y出现的比例关联分析的基本概念关联规则挖掘：第一步：产生频繁项集；因为规则的支持度仅依赖于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%）比例。基于兴趣度的客观度量。支持度-置信度缺陷原因：忽略了后件的支持度。提升度（li