数据挖掘基础及应用 课件 第5章-关联分析-蓝橙课堂版1

第5章关联分析01第5章关联分析发现共现项集，理解关联规则，比较挖掘方法数据挖掘基础及应用本章学习路线02基本概念区分事务与项集，读懂规则指标。Apriori算法逐层生成候选，按支持度筛选。FP-Growth共享事务前缀，递归挖掘模式。规则与应用筛选并解释规则，检验应用价值。学习目标：能手算小型事务集的指标，解释两种算法的过程，并对规则给出合理的应用边界。图5-1关联分析知识结构图购物篮中的共现关系03事务购买的商品1面包、牛奶、尿布2面包、尿布、啤酒3牛奶、尿布、啤酒4面包、牛奶、尿布、啤酒从记录中提出问题面包出现3次。面包与尿布共现3次。包含面包的事务中，有多大比例也包含尿布？本例中该比例为3/3=100%，但样本只有4笔。共现规律仍需在更多事务中复核。事务、项与项集04事务T：{A,B,C}单项集二项集三项集{A}{B}{C}{A,B}{A,C}{B,C}{A,B,C}一笔事务用一个项的集合表示。项集包含k个不同的项时，称为k项集。同一事务内重复项只计一次。事务表与布尔编码05事务ABCD1111021010311014011151111每一列表示一个项1表示出现，0表示未出现。同一行可以有多个1。统一商品名称和编码。明确一次事务的时间范围。这种编码也称multi-hot。TransactionEncoder把事务列表转换为布尔表，可供频繁项集函数使用。支持度：共现占全部事务的比例06support(X)=包含X的事务数/总事务数N教材中的1000笔交易同时购买牛奶与面包：200笔。项集{牛奶,面包}的支持度=200/1000=0.20。计数与比例支持度计数为200。支持度比例为20%。设置阈值时说明采用哪一种。关联规则X⇒Y的支持度等于项集X∪Y的支持度。分母始终是全部事务数。置信度：规则具有方向性07统计项目事务数牛奶300面包600牛奶与面包200全部事务1000同一共现，两条方向牛奶⇒面包：200/300≈66.7%。面包⇒牛奶：200/600≈33.3%。置信度分母是前件的出现次数。confidence(X⇒Y)=support(X∪Y)/support(X)。前件与后件均非空，并且不包含共同的项。提升度：与后件本身的常见程度比较08lift(X⇒Y)=confidence(X⇒Y)/support(Y)牛奶⇒面包面包的总体支持度=600/1000=0.60。规则置信度=200/300=2/3。提升度=(2/3)/0.60=10/9≈1.111。在这批事务中的含义购买牛奶时，购买面包的比例约为基线的1.111倍。相对高约11.1%。计算时使用未提前舍入的比例。提升度反映共现关联，单独的lift值不能证明统计显著性或因果关系。提升度的基线与条件比例09面包的出现比例总体比例为60%。条件比例约为66.7%。绝对差约6.7个百分点。相对提升约11.1%。二者采用不同的分母。lift=1对应条件比例与总体比例相同。lift大于1表示正关联，小于1表示负关联。频繁项集与最大频繁项集10频繁项集支持度达到最小支持度阈值。频繁子集频繁项集的子集也达到同一阈值。最大频繁项集没有任何更大的频繁超集。一个假设例子假设{A,B,C}频繁，并且任何更大超集都不频繁。则{A,B,C}是最大频繁项集，其子集{A,B}仍然频繁，但不是最大频繁项集。“最大”描述集合包含关系，并不表示它的支持度最高。仅保留最大项集会丢失部分子集的支持度信息。关联分析的基本过程11准备事务统一项名，定义事务边界。挖掘频繁项集设置最小支持度，统计共现模式。生成规则分出前件与后件，计算规则指标。评价与解释核对基线与样本，复核规则稳定性。阈值决定保留哪些模式支持度太高，可能遗漏较少出现的组合。支持度太低，候选模式和冗余规则会增加。应结合样本数、领域问题和验证结果选择。挖掘频繁项集与生成关联规则是两个阶段。满足阈值的规则还需要进行业务解释和新数据复核。Apriori性质与剪枝12若{A,B,C}频繁则所有子集都频繁{A,B}{A,C}{B,C}{A}{B}{C}等价的剪枝依据如果{A,B}不频繁，所有包含它的超集也不频繁。可以直接删除候选{A,B,C}，无需再扫描事务计算它的次数。增加项会使符合条件的事务数保持不变或减少。因此支持度具有反单调性。Apriori的逐层搜索过程13连接由频繁k−1项集形成候选k项集。剪枝检查每个候选的k−1项子集。计数扫描原始事务，统计候选出现次数。保留与继续达到阈值则保留，进入下一层搜索。终止条件当这一层没有频繁项集，或已经没有候选项集时停止。记录每一层的候选集合Cₖ和频繁集合Lₖ，能清楚区分“尚待检验”与“已达阈值”。剪枝依据是候选项集的全部k−1项子集，而不是任意一个子集频繁就保留。教材事务集：5笔记录14事务ID项目集合1{A,B,C}2{A,C}3{A,B,D}4{B,C,D}5{A,B,C,D}阈值约定最小支持度计数设为2。总事务数N=5。对应最小支持度2/5=40%。本例中达到2次即保留。本节各层结果均从这5笔事务逐条计数。注意“大于等于阈值”包含恰好等于阈值的项集。第一层：频繁1项集15项集支持度计数支持度{A}480%{B}480%{C}480%{D}360%得到L₁4个单项均至少出现2次。全部保留，再两两连接生成候选2项集。项集大小指不同项的个数。支持度计数指包含该项集的事务数，两者不要混淆。第二层：6个二项集全部保留16候选项集C₂计数支持度是否进入L₂{A,B}360%是{A,C}360%是{A,D}240%是{B,C}360%是{B,D}360%是{C,D}240%是{C,D}在事务4和5中出现，共2次，也达到阈值。候选项集计数达到2次后才称为频繁项集。第三层：三项集需要重新计数17候选项集C₃出现的事务计数保留{A,B,C}1、52是{A,B,D}3、52是{A,C,D}51否{B,C,D}4、52是L₃={{A,B,C},{A,B,D},{B,C,D}}{A,C,D}只有事务5包含，不能由频繁二项集的计数直接推断为2次。每一层都应回到原事务验证。第四层剪枝与最终结果18候选{A,B,C,D}子集{A,C,D}不频繁四项集的处理候选未通过子集检验，直接剪枝。若回查原数据，它也只出现1次。因此L₄为空，搜索结束。最大频繁项集{A,B,C}、{A,B,D}、{B,C,D}。频繁二项集{C,D}仍需保留计数，但它被频繁三项集{B,C,D}包含。同一数据集、同一阈值下，两种正确实现的完整频繁项集结果应一致。输出顺序可以不同。例5.1：食品购物篮数据19事务商品1牛奶、面包2牛奶、面包、黄油3牛奶、黄油4面包、黄油5牛奶、面包、黄油、鸡蛋本例阈值最小计数=3。对应支持度3/5=0.60。每笔事务先去除重复商品。例5.2继续使用同一数据。dataset表示本页5笔事务的列表。下面的手工计数与函数包调用采用同一支持度口径。例5.1：候选与频繁项集20项集计数支持度达到3次{牛奶}40.80是{面包}40.80是{黄油}40.80是{鸡蛋}10.20否三种高频食品的二项组合30.60是{牛奶,面包,黄油}20.40否“三种高频食品的二项组合”指{牛奶,面包}、{牛奶,黄油}、{面包,黄油}，各出现3次。本例没有频繁三项集。例5.1：候选生成与子集检验21fromitertoolsimportcombinationsdefcandidates(prev,k):merged={a|bforainprevforbinpreviflen(a|b)==k}return{xforxinmergedifall(frozenset(z)inprevforzincombinations(x,k-1))}#prev是上一层频繁项集的frozenset集合这段代码做什么连接得到k项候选。检查全部k−1项子集。候选还需要统计支持度，才能形成下一层频繁项集。支持度计数可写为sum(candidate<=set(t)fortindataset)。保留count>=min_count的候选。例5.2：用mlxtend挖掘项集与规则22importpandasaspdfrommlxtend.preprocessingimportTransactionEncoderfrommlxtend.frequent_patternsimport(apriori,association_rules)te=TransactionEncoder()df=pd.DataFrame(te.fit_transform(dataset),columns=te.columns_)freq=apriori(df,min_support=3/5,use_colnames=True)rules=association_rules(freq,num_itemsets=5,metric='confidence',min_threshold=0.7)输入与输出沿用例5.1的5笔事务。df记录商品是否出现。freq输出两列：support与itemsets。rules输出前件、后件以及规则指标。运行需pandas和mlxtend。min_support为比例，num_itemsets为原事务总数。例5.2：高置信度仍需比较基线23规则方向支持度置信度提升度牛奶⇒面包/面包⇒牛奶0.600.750.9375牛奶⇒黄油/黄油⇒牛奶0.600.750.9375面包⇒黄油/黄油⇒面包0.600.750.93756条规则的共同特点每一行列出两个方向。置信度0.75达到0.7阈值，但后件的总体支持度为0.80。因此提升度0.75/0.80=0.9375，杠杆率0.60−0.80×0.80=−0.04。达到支持度和置信度阈值，并不自动表示正关联。三项组合未达到最小支持度，因此不从它生成规则。Apriori与FP-Growth的处理方式24比较项AprioriFP-Growth搜索方式逐层生成候选并检验用条件模式递归增长主要结构候选集合和支持度计数FP树及条件模式基原始数据扫描通常逐层扫描通常两遍构建初始FP树适用性考虑候选少时容易观察过程共享前缀多时压缩更明显共同输出给定阈值下的频繁项集给定阈值下的频繁项集实际耗时与事务长度、项数、阈值和实现有关。比较算法时保持数据、阈值和输出约束一致。FP树示例：原始事务与单项计数25事务项目集合1{A,B,C,D}2{B,C,D}3{A,B,C}4{A,D}5{B,C,D}项计数B4C4D4A3最小计数为2，四项均保留。C位于事务1、2、3、5，D位于事务1、2、4、5。相同频率时固定项顺序。事务排序与共享前缀26事务原始集合按全局顺序排列1{A,B,C,D}BCDA2{B,C,D}BCD3{A,B,C}BCA4{A,D}DA5{B,C,D}BCD全局顺序：B、C、D、A事务2和5完全共享B-C-D路径。事务4从根节点建立D-A路径，不能并入另一条路径上的A节点。FP树：只合并相同前缀27根B:4D:1C:4A:1D:3A:1A:1节点计数的含义B:4表示4笔事务具有此前缀。三个A节点合计3次，对应3笔含A的事务。同名节点位于不同路径，不能任意合并。B-C-D路径计数为3，其中只有1笔继续包含A。树中未画同名项的链接，链接可用于回溯条件模式基。条件模式基：以A作为后缀28A之前的前缀路径权重BCD1BC1D1条件计数：B=2，C=2，D=2最小计数仍为2得到{A,B}、{A,C}、{A,D}，它们各出现2次。{A,B,C}也出现2次。{A,B,D}仅出现1次，舍弃。继续对条件模式递归处理。条件模式基保留每条前缀的权重。原项A的支持度计数为3，不把A本身写入前缀路径。例5.3：FP-Growth的食品事务29事务商品1牛奶、面包、尿布2可乐、面包、尿布、啤酒3牛奶、尿布、啤酒、鸡蛋4面包、牛奶、尿布、啤酒5面包、牛奶、尿布、可乐两种阈值口径最小支持度0.20，在5笔事务中对应1次。若改为0.40，对应最小计数2。两种设置的结果范围不同。本例与表5-7是两份不同数据。后续函数调用的dataset指本页5笔事务。例5.3：两种函数接口30frommlxtend.frequent_patternsimportfpgrowthte=TransactionEncoder()df=pd.DataFrame(te.fit_transform(dataset),columns=te.columns_)freq=fpgrowth(df,min_support=0.2,use_colnames=True)print(freq[['support','itemsets']])pyfpgrowth接口输入为事务列表，阈值为最小出现次数。本例计数阈值设为1，对应5笔中的20%。输出项集与计数。pyfpgrowth调用find_frequent_patterns(dataset,1)。mlxtend使用布尔表和比例阈值。一个频繁三项集可以生成6条规则31前件后件置信度{A}{B,C}2/4=0.50{B}{A,C}2/4=0.50{C}{A,B}2/4=0.50{A,B}{C}2/3≈0.667{A,C}{B}2/3≈0.667{B,C}{A}2/3≈0.667将频繁项集L分成不相交的非空前件X和后件L−X。含k个项时，共有2ᵏ−2条候选规则。关联规则的常用评价指标32指标计算式比较内容支持度s(X∪Y)全部事务中的共现比例置信度s(X∪Y)/s(X)给定前件后的后件比例提升度confidence/s(Y)条件比例与总体基线之比杠杆率s(X∪Y)−s(X)s(Y)实际共现与独立基线之差确信度(1−s(Y))/(1−confidence)独立预期违例/实际违例s表示支持度。confidence=1时确信度的分母为0，可能为无穷或未定义，应结合后件支持度解释。100个购物篮：常见组合也可能低于基线33购物篮有牛奶无牛奶合计有面包404080无面包20020合计6040100面包⇒牛奶支持度=40/100=0.40。置信度=40/80=0.50。提升度=0.50/0.60≈0.833。杠杆率=0.40−0.80×0.60=−0.08。独立基线下预期共现48篮，实际为40篮。这里的负关联是对这批事务的描述，不能据此直接断言搭售一定无效。应用效果需要独立测试。例5.4：用于生成规则的9笔事务34事务商品1面包、牛奶2面包、尿布3面包、啤酒4面包、牛奶、尿布5面包、牛奶、啤酒6面包、尿布、啤酒7牛奶、尿布8牛奶、啤酒9尿布、啤酒先检查项集支持度面包出现6次。牛奶、尿布、啤酒各5次。二项组合最多出现3次。最大二项支持度为3/9。dataset表示本页9笔事务。先判断频繁项集是否存在，再讨论规则的置信度和提升度。例5.4：阈值改变时的实际结果35最小支持度频繁单项集频繁二项集规则数0.404个0个01/34个3个6原阈值0.40二项集最多出现3/9≈0.333。因此没有可用于拆分规则的频繁项集。规则结果为空符合数据。课堂对照阈值1/33个频繁对均包含面包。最小置信度0.50下得到6条规则。其提升度均为0.90。改变阈值只是展示输出如何变化，并不意味着规则质量必然提高。上述计数均使用同一9笔事务。例5.4：生成并读取规则表36df=pd.DataFrame(te.fit_transform(dataset),columns=te.columns_)freq=apriori(df,min_support=1/3,use_colnames=True)rules=association_rules(freq,num_itemsets=len(df),metric='confidence',min_threshold=0.5)cols=['antecedents','consequents','support','confidence','lift','leverage','conviction']print(rules[cols])规则表的读取顺序前件和后件是项集。先看支持度与置信度，再与后件基线比较。函数已计算lift与leverage，可直接读取对应列。支持度列名为antecedentsupport和consequentsupport，均使用单数形式。规则剪枝需要固定频繁项集37固定L={A,B,C}后件为{C}{A,B}⇒{C}置信度=2/3≈0.667。设最小置信度为0.60，本规则通过。后件扩大为{B,C}{A}⇒{B,C}置信度=2/4=0.50。后件扩大，前件缩小，置信度不会因此升高。在同一频繁项集L内，如果某后件对应规则未达置信度阈值，可剪去包含该后件的更大后件。不能任意推广到其他规则。应用中的规则与解释38零售共现发现搭配候选，再测试推荐效果。门诊记录描述症状与用药在记录中的共现。设备与告警寻找环境状态和告警的组合模式。共现规律的解释边界疾病类型、就诊流程或其他共同因素，都可能造成症状与用药共现。规则用于提出待核实的问题。共现频率本身不能证明疗效、处方合理性或因果关系。在新数据及不同分组中复核规则。lift与leverage达到阈值，也不能保证排除混杂因素。图5-5关联分析的应用基于规则的Top-N推荐39匹配前件规则前件包含在当前购物篮中。生成候选从后件中移除篮中已有商品。合并与排序按统一策略合并同一商品的得分。验证推荐用留出商品检查命中率与覆盖率。教材指定的规则得分score=confidence×log(lift)需要说明多条规则推荐同一商品时采用最大值、求和或其他合并方式。lift≤1时该得分不为正。推荐规则仅用训练数据挖掘。评价时遮蔽待推荐商品，避免使用完整购物篮同时作为输入和答案。本章小结40学习内容需要掌握的判断基本概念事务、项集、计数与支持度比例规则指标置信度有方向，提升度需要比较基线Apriori连接、子集剪枝、扫描计数、逐层保留FP-Growth固定排序、共享前缀、条件模式递归规则应用结合样本数、稳定性与独立应用测试面对一条规则，先核对它来自哪些事务、用了什么阈值，再解释指标和可能的应用。课后练习1：超市事务与算法比较41构造模拟购物篮按主食、饮品、母婴、烘焙、日化等商品簇，设置共现概率并生成事务。两种算法使用相同数据。min_support=0.02。比较结果与耗时运行Apriori与FP-Growth。生成规则，min_confidence=0.4。报告support、confidence、lift、leverage和运行时间。比较前10条规则的平均lift。绘制support–confidence散点图。先说明前10条的排序方式，图中标注top-lift规则。相同约束下先核对项集和规则是否一致，再比较耗时。课后练习2：门诊记录的症状与用药42构造模拟门诊事务按上呼吸道、