《数据挖掘基础与案例》课件 第5章 关联分析概念与方法

第5章关联分析概念与方法数据挖掘基础与案例学习目标/Target掌握Apriori算法挖掘关联规则的基本步骤，能够熟练完成频繁项集挖掘和规则生成。了解Apriori算法的优缺点，了解提升算法效率的方法。了解关联模式评估的指标,

熟悉各指标的应用场景。掌握关联分析的基本概念，理解频繁项集和关联规则的内容，掌握先验原理。引言/Introduction关联分析（associationanalysis）从大量数据中发现项集之间有趣的联系，被用于发现隐藏在大型数据集中的有意义的关联。通常将所发现的联系表示为关联规则（associationrule）或频繁项集（frequentitemset）。目录/Contents01基本概念02关联分析的基本任务04频繁项集的紧凑表示03关联分析方法05关联分析的基本任务06关联分析的典型应用基本概念5.15.1.1购物篮分析关联分析的目的是发现被顾客放入购物篮中的不同商品之间的联系，从而分析顾客的购买习惯，了解哪些商品经常被顾客连带购买，为制定方便顾客选取的货架摆放方案和合理的营销策略提供依据，也被称为购物篮分析。完整的购物篮数据至少包含两方面的信息：一方面是顾客的购买行为序号，一个顾客可能会发生多次购买行为，每次购买行为均被记录下来，这个序号也就是超市或者商店的交易流水号；另一方面是顾客在每次购物过程中交易的商品列表，此处商品列表只涉及顾客购买的不同商品的名称。5.1.1购物篮分析购物篮数据涉及关联分析的两个基本术语：事务（transaction）和项集（itemset）。事务是关联分析的研究对象，一个事务包含一个唯一标识TID和对应顾客购买的商品的集合。项目（item）是事务中的单个对象。一次交易中的商品通常是若干个项目的集合，叫作项集。购物篮分析的目的是找到所有购物篮中不同商品之间的关联关系，从而了解哪些商品频繁地被顾客同时购买，帮助零售商制定合理的营销策略。5.1.1购物篮分析在对购物篮数据进行关联分析时，需要处理两个关键问题：第一，计算复杂度问题。从大型事务数据集中发现有意义的规则在计算上要付出很高的代价；第二，规则的筛选问题。所发现的某些规则可能是虚假的或不令人感兴趣的，因为它们可能是偶然发生的或者是已经被研究者所熟知的。除了购物篮分析外，关联分析也被应用于公共管理、生物信息学、医疗诊断、网页挖掘和推荐系统等领域。例如，关联分析可以帮助公安机关从已有的案件中找到各属性之间的隐含关系，发现其中的犯罪行为规律，为新案件的侦破提供线索；在移动通信行业，关联分析可以帮助运营商发现不同业务之间的关联关系，从而推进新业务的发展；关联分析也可以用来分析保险行业的客户数据，找到各险种可能被购买的人群特征，进而进行精准营销。5.1.2频繁项集和关联规则

5.1.2频繁项集和关联规则

5.1.2频繁项集和关联规则

5.1.2频繁项集和关联规则实际应用中的关联规则有许多类型，可以根据不同的标准对关联规则进行分类。根据处理的数据类型，关联规则可以分为布尔关联规则和量化关联规则。布尔型关联规则是指处理的数据类型都是离散属性或分类属性，量化关联规则则是指处理的数据类型包含连续属性。根据处理的数据维度，关联规则可以分为单维关联规则和多维关联规则。单维关联规则通常从事务数据中挖掘，涉及到数据的只有一个维度，处理的是单个维内的关系。根据数据的抽象层次，关联规则可以分为单层关联规则和多层关联规则。在单层关联规则中，没有考虑现实数据的多层次性。多层关联规则是指在规则挖掘中，对数据的多层性进行了充分考虑。关联分析的基本任务5.25.2关联分析的基本任务大多数关联规则挖掘算法通常将关联规则挖掘任务分解为如下两个主要的子任务，以方便进行剪枝。产生频繁项集目标是发现满足最小支持度阈值的所有项集，这些项集称作频繁项集。产生规则目标是从上一步发现的频繁项集中提取所有高置信度的规则，高置信度的规则满足最小置信度阈值，这些规则称为强规则。如何高效率地生成频繁项集，并从得到的频繁项集中找到所有的强规则，是关联分析相关算法需要解决的两个问题。关联分析方法5.3

5.3.1先验原理

5.3.1先验原理即，一旦发现一个非频繁项集，那么包含该项集的所有超集都可以被剪枝，这样的方法被称为基于支持度的剪枝（support-basedpruning）。基于支持度的剪枝依赖于支持度度量的性质，即一个项集的支持度决不会超过它的子集的支持度，这个性质也被称为支持度度量的反单调性（anti-monotone）。任何具有反单调性的度量都能够直接结合到挖掘算法中，对候选项集的指数搜索空间有效地进行剪枝，以降低生成频繁项集的计算代价。5.3.2Apriori算法产生频繁项集Apriori算法是关联规则挖掘的经典算法，它开创性地使用了基于支持度的剪枝技术来控制候选项集的指数增长。此处以下表所示的事务数据集为例，展示Apriori算法挖掘频繁项集产生强关联规则的基本过程。TID商品集合1牛奶，鸡蛋，面包，薯片2鸡蛋，爆米花，薯片，啤酒3鸡蛋，面包，薯片4牛奶，鸡蛋，面包，爆米花，薯片，啤酒5牛奶，面包，啤酒6鸡蛋，面包，啤酒7牛奶，面包，薯片8牛奶，鸡蛋，面包，黄油，薯片9牛奶，鸡蛋，黄油，薯片5.3.2Apriori算法产生频繁项集

项集支持度计数{爆米花}2{黄油}2{鸡蛋}7{面包}7{牛奶}6{薯片}7{啤酒}45.3.2Apriori算法产生频繁项集

项集支持度计数{鸡蛋}7{面包}7{牛奶}6{薯片}7{啤酒}45.3.2Apriori算法产生频繁项集

项集支持度计数{鸡蛋，面包}5{鸡蛋，薯片}6{鸡蛋，啤酒}3{面包，薯片}5{面包，啤酒}3{牛奶，鸡蛋}4{牛奶，面包}5{牛奶，薯片}5{牛奶，啤酒}2{薯片，啤酒}25.3.2Apriori算法产生频繁项集

项集支持度计数{鸡蛋，面包}5{鸡蛋，薯片}6{鸡蛋，啤酒}3{面包，薯片}5{面包，啤酒}3{牛奶，鸡蛋}4{牛奶，面包}5{牛奶，薯片}55.3.2Apriori算法产生频繁项集

5.3.2Apriori算法产生频繁项集

项集支持度计数{鸡蛋，面包，薯片}4{鸡蛋，面包，啤酒}2{牛奶，鸡蛋，面包}3{牛奶，鸡蛋，薯片}4{牛奶，面包，薯片}45.3.2Apriori算法产生频繁项集

项集支持度计数{鸡蛋，面包，薯片}4{牛奶，鸡蛋，面包}3{牛奶，鸡蛋，薯片}4{牛奶，面包，薯片}45.3.2Apriori算法产生频繁项集

项集支持度计数{牛奶，鸡蛋，面包，薯片}35.3.2Apriori算法产生频繁项集

5.3.2Apriori算法产生频繁项集

项集支持度计数5.3.2Apriori算法产生频繁项集

5.3.2Apriori算法产生频繁项集

产生候选项集5.3.2Apriori算法产生频繁项集

产生候选项集5.3.2Apriori算法产生频繁项集

5.3.2Apriori算法产生频繁项集候选项集剪枝

5.3.2Apriori算法产生频繁项集计算支持度计数

5.3.2Apriori算法产生频繁项集计算支持度计数

5.3.2Apriori算法产生频繁项集计算支持度计数

5.3.2Apriori算法产生频繁项集计算支持度计数

5.3.2Apriori算法产生频繁项集计算支持度计数

5.3.2Apriori算法产生频繁项集计算支持度计数5.3.2Apriori算法产生频繁项集计算支持度计数首先进行第一层散列，首项为1的项集，应该散列在左边，而首项为2的散列在中间，首项为3的散列在右边，如下图所示：5.3.2Apriori算法产生频繁项集计算支持度计数按同样方式进行第二层散列，第1项为1的3-项集中第2项为2、3和5，其中第2项为2和5的3-项集被散列到第二层的中间结点，其第2项为3的3-项集被散列到第二层的右结点，结果如下图。5.3.2Apriori算法产生频繁项集计算支持度计数同理进行第三层散列，结果如右。图中灰色叶子结点表示候选Hash树上事务3-项集被散列的桶。5.3.2Apriori算法产生频繁项集计算支持度计数

5.3.3Apriori算法生成关联规则

5.3.3Apriori算法生成关联规则

5.3.3Apriori算法生成关联规则5.3.3Apriori算法生成关联规则

基于置信度的剪枝5.3.3Apriori算法生成关联规则基于置信度的剪枝频繁项集的紧凑表示5.4

5.4.1极大频繁项集如果某个项集的直接超集都不是频繁项集，则称该项集为极大频繁项集（maximalfrequentitemset）。极大频繁项集是一种十分有效的频繁项集的紧凑表示。极大频繁项集的任意一个子集都是频繁的，即从一个极大频繁项集中可以导出所有的频繁项集，又由于极大频繁项集的超集都不是频繁的，所以极大频繁项集是能完成这一任务的最小的项集。尽管极大频繁项集能够导出所有的频繁项集，但是它无法提供其子集的支持度信息，这就需要再扫描一遍数据集来确定这些子集的支持度计数，此时能提供保持支持度信息的频繁项集的最小表示是有用的。5.4.2闭频繁项集闭频繁项集（closedfrequentitemset）提供了频繁项集的一种最小表示，该表示不会丢失支持度信息。如果一个项集的直接超集的支持度计数都不等于该项集本身的支持度计数，则称该项集为闭项集（closeditemset）。也就是说，如果一个项集不是闭的，那么至少存在一个它的直接超集，该超集的支持度计数和它本身的支持度计数相等。如果一个项集是闭项集，同时其支持度满足支持度阈值，则称该项集为闭频繁项集。5.4.2闭频繁项集

5.4.2闭频繁项集使用极大频繁项集和闭频繁项集进行频繁项集的紧凑表示可以减少频繁项集中的冗余，降低算法计算的复杂度。需要注意的是，要使用极大频繁项集和闭频繁项集的紧凑表示，前提是能够有效地从事务数据集中快速识别极大频繁项集和闭频繁项集。关联模式评估5.5在商业数据集中挖掘关联规则时，尽管有支持度阈值和置信度阈值的限制，依然会挖掘出大量的决策者们不感兴趣的没有实际应用价值的关联规则。因此，需要建立一组能被广泛接受的评估关联模式质量的标准来评价和筛选关联规则。目前认可度较高的关联模式评估标准有两种：主观兴趣度度量和客观兴趣度度量。主观兴趣度度量主要依据人们的经验信息来判断模式是否有趣，需要收集领域专家的主观知识加入模式评估工作，在实际运用中可操作性较差，实现比较困难，这里主要讨论客观兴趣度度量。5.5.1模式的客观兴趣度度量客观兴趣度度量（ObjectiveInterestingnessMeasure）是指从数据中推导统计量，用统计量来判断关联模式是否有趣。这时，相互独立的模式或者覆盖少量事务的模式被认为是没有意义的。整体来讲，客观兴趣度度量方法在数据驱动下完成关联模式评估。其值可通过事务中变量的频度计数计算出来。关联规则挖掘算法要找出满足支持度阈值和置信度阈值的强关联规则，支持度能够确保规则的普遍性，置信度能够确保规则的合理性，这是传统的评估关联规则的有效性方法，即支持度-置信度框架。支持度和置信度都是客观兴趣度度量，除它们之外，还有很多客观兴趣度度量。5.5.2支持度-置信度框架的局限性

5.5.2支持度-置信度框架的局限性支持度的缺点：由于支持度阈值是由主观经验人为设定，如果阈值过低，会产生大量的频繁项集，增加算法的计算复杂度；如果阈值过高，会导致一些潜在的有意义的规则被删除。例如，在商场的购物记录中购买奢侈品的人数是比较少的，那么奢侈品的购买模式就有可能因为达不到支持度阈值而被过滤掉。置信度的缺点：计算置信度时并没有考虑规则前后件的关系，当规则的前后件是两个完全独立的事件时，就有可能生成误导性的规则。下面通过一个实例来说明。5.5.2支持度-置信度框架的局限性一个谷类早餐的零售商对一所学校学生每天早上所从事的活动进行了一次调查。该所学校共有5000名学生。数据表明：60%的学生（即3000名学生）打篮球，75%的学生（即3750名学生）吃该零售商售卖的谷类早餐，40%的学生（即2000名学生）既打篮球也吃这种谷类早餐。假设关联规则挖掘的支持度阈值40%，置信度阈值为60%。得到相依表如下。

吃谷类早餐不吃谷类早餐打篮球200010003000不打篮球175025020003750125050005.5.2支持度-置信度框架的局限性

5.5.2支持度-置信度框架的局限性

5.5.2支持度-置信度框架的局限性5.5.3提升度、相关度与IS度量

提升度（lift）

提升度（lift）5.5.3提升度、相关度与IS度量

提升度（lift）5.5.3提升度、相关度与IS度量

相关度5.5.3提升度、相关度与IS度量

IS度量5.5.3提升度、相关度与IS度量

客观兴趣度度量的性质5.5.3提升度、相关度与IS度量关联分析的典型应用5.6关联分析作为一种常用的数据挖掘技术，已在多个领域得到广泛应用。在零售业与电子商务领域，关联分析最早也是最成功的应用就是购物篮分析。通过分析顾客购买行为数据，可以发现商品之间的关联关系，从而优化商品陈列、促销策略和库存管理。医疗健康领域，研究人员利用关联规则挖掘电子病历数据可以发现疾病之间的关联关系，通过分析药物处方数据，可以发现哪些药物经常被同时开具，进而研究这些药物组合的安全性，通过分析大量处方，以发现潜在的药物组合和医疗风险等。在网络安全与欺诈检测领域，关联分析可用于检测异常行为模式，识别潜在的安全威胁和欺诈行为。通过分析网络日志和系统事件，可以发现异常访问模式。在信用卡欺诈检测方面，分析持卡人的交易模式可以发现异常交易组合。推荐系统也是关联规则挖掘的重要应用领域，特别适用于基于物品的协同过滤。流媒体平台利用用户观看历史数据挖掘视频之间的关联关系，当用户观看某部电影后，推荐与之关联的其他电影。新闻客户端分析用户的阅读序列，发现新闻内容之间的关联关系，实现个性化的新闻推送。在智慧城市建设中，关联分析可以帮助发现城市运行中的各种模式和规律。通过分析不同路口的车流量数据，可以发现交通拥堵的传播规律。工业物联网中，通过分析传感器数据，可以发现设备故障前的异常信号组合。随着大数据和人工智能技术的发展，关联分析正向着多组学整合、实时动态分析、高维数据处理等方向发展。未来，关联分析将与深度学习、图神经网络等技术深度融合，在处理更复杂的数据类型、解决更具挑战性的实际问题中发挥更大作用。参考文献[1]Jiawe