关联分析(Association Analysis)--挖掘啤酒与尿布的关联规则
通过本文我们将了解：
x到y的关系体现在
x到y的关系体现在
第一步是基于apriori原理的关联规则挖掘；
第二步则是通过剪枝优化算法来提升效率.
Apriori算法的基本思想是基于频率优先原则提取频繁项集；
其核心在于有效减少候选集合规模.
生成无重复k-项候选集的过程首先通过剪枝方法减少数量；
然后对每个候选集进行计数以确定其是否为频繁项集.
- 关联分析规则的评估指标
什么是关联分析
关联分析方法主要用于识别出数据集中属性之间的相互关系，并揭示了该事物中各属性共同出现的规律及特征。
通过深入挖掘海量数据中的商品项集关系,我们能够识别出具有吸引力和相关性的商品组合。最著名的应用便是购物篮分析,它具体关注的是顾客在购物篮中放置不同商品之间的相互关系及其购买模式。具体而言,它关注的是顾客在购物篮中放置不同商品之间的相互关系及其购买模式。通过识别出常被同时采购的商品对后,商家便可以据此制定精准的营销策略和促销活动。此外,在数据分析领域中还涉及到了价格表设计、促销活动策划、产品陈列优化以及基于购买历史进行细分营销等多个方面。
通过数据库关联分析能够提取出类似"具有类似'因某事件导致另一事件发生'结构的"类型的规则。
例如，在超市中发现有67%的顾客在购买啤酒时通常也会采购尿布。进而通过优化啤酒与尿布货架的位置布局，并采用捆绑销售的方式能够提升超市的整体服务质量及经营绩效。
在" C语言"课程中表现出色的学生群体，在深入掌握" 数据结构"这一学科时展现出较高水平的可能性达到了88%。因此，在教学实践中可以通过着重提升学生对" C语言"知识的掌握程度来显著提高整体的教学效果。
基本概念：
我们以表中的数据为基础进行分析，在以下表格展示的二维数据集中探讨事务管理的相关特性。该事务库记录的是顾客一次购物行为及其相关的商品信息，在此过程中TID字段代表每一次购物行为的独特标识符而items字段则记录了顾客在此次购物中所选购的商品种类。
• 事务（Transaction）
• 项目（Items）
由零个或多个元素组成的集合被称为项目集，在购物篮事务中, 每一件商品就是一个项目.每一次购物篮事务都会涉及多件商品, 因此这些商品就被整合形成了项目集.包含k个项目的行为则被称为k-项目.
• 关联规则（Association Rules）
基于集合 X 的前提条件，在设定的置信水平下推导出结果集 Y。关联规则通常表示为从一组项 X 推导出另一组项 Y 的逻辑关系。其中 X 被称为前件或前提是已知的条件集合，而 Y 被称为后件或结论集合。确保 X 和 Y 中没有共同的元素以避免重复推导。即在观察到 X 发生的情况下我们有较高的信心认为 Y 也会发生。例如在超市购物记录中发现顾客购买尿布后往往会同时购买啤酒。通过关联规则分析可以看出在某些情况下两种商品之间存在较强的关联性
• 支持计数（Support count）
记录集中某项组合出现的频率。举例如下：
- 一项集合\{Bread,Milk\} 在数据集中共出现3次，则其支持度为3；
- 另一项集合\{Milk,Bread,Diaper\} 共出现在数据集中2次，则其支持度为2；
记作：
support~count: \sigma(\{Milk,Bread,Diaper\}) = 2
• 支持度（Support）
表示某个频繁项集中出现的事务数量占总事务的比例。在给定的数据集中共有10个记录，在其中包含了啤酒和尿布的记录共有5条。因此该频繁项集的支持度计算为\frac{支持的数量}{总记录数}即\frac{支持的数量}{10}=0.5。
例如，在上表中总共有五个不同的事务s(\{\text{牛奶},\text{面包},\text{尿布}\})=\frac{2}{5}
我们称关联规则的支持度为其被定义为同时存在于X和Y这两个项集中的事务数量与总事务数的比例。具体而言，在涉及N个事务的情况下，
s(X\rightarrow Y)=\frac{\sigma (X \cup Y)}{N}
• Frequent item sets
如果我们对项目集的发生频率设定一个最低发生频率标准（minsup），则所有达到或超过这一标准的项目集合即被称为频繁项集。
• 置信度（Confidence）
当某些物品出现时（例如，在顾客购买尿布时），另一些特定物品必定出现的概率（通常针对关联规则而言）。
例如，在关联规则{‘尿布’} → {‘啤酒’}中，则它的 置信度 = 支持度{Support({尿布, 啤酒})} / 支持度{Support({尿布})}
对于关联规则中的置信度这一概念来说，在数据挖掘中被用来衡量Y项与X项一起出现的可能性。
关联规则算法策略
大多数关联规则挖掘算法通常采用的策略是分解为两步
生成频繁项集的过程 ，旨在找出所有满足至少达到预设最小支持度阈值的项目集合 ，这些项目集合即被称为频繁项集 （ frequent itemset ）。
生成过程是从上一步骤中提取出具有高度可靠性的关联模式这一目标下展开的操作，并被定义为强规则（strong rule）。通常情况下，从数据中提取频繁项集所需的计算资源远远超过从中生成相关关联模式所花费的时间资源。
关联规则发现：
有了上述两个度量，就可以对所有规则做限定，找出对我们有意义的规则。
首先设定数据集中的支持度阈值minsup和置信度阈值minconf。接着，在整个候选规则集合中筛选出满足支持度大于等于minsup且置信度大于等于minconf的所有候选规则。对于给定的一个事务集合T来说，关联规则挖掘的核心任务在于发现满足以下条件的全部候选模式：即每个模式都对应一个布尔函数。
支持度 ≥ 支持度最小阈值 （support ≥ minsup）
置信度 ≥ 置信度最小阈值（confidence ≥ minconf ）
需要注意的是通过简单关联规则获得的推论不涉及因果关系 我们仅能从A→B推导出A和B确实同时出现的情况 但无法断定A就是原因而B就是结果
暴力方法：
- 列举所有相关的关联规则
- 计算每条规则的支持度与置信度
- 筛选出满足支持度和置信度标准的关联规则
然而这种做法所带来的计算负担令人望其项背！实际上存在多种策略以减少生成频繁项集所需的计算复杂度。
- 缩减候选项集的数量。例如Apriori原理是一种无需计算支持度即可删除部分候选项集的方法。
- 降低比较次数。借助更高层次的数据结构实现存储候选项集合或压缩数据集合以降低比较次数。
我们来做一次分析：
观察者关注的是如何对各项进行分类与分析。在数据挖掘领域中，
我们通常会将关联规则视为一个项集的分解：
\{Milk, Diaper, Beer\}
这一集合包含了牛奶、尿布和啤酒等商品。由于这些规则均来自同一项集，
它们具备相同的支撑度（support），尽管它们可能有不同的信心度（confidence）。
因此我们得以分离出支撑度与信心度的要求。
再次强调, majority of association rule mining algorithms typically employ a two-step strategy consisting of the following two primary subtasks:
- 频繁项集的生成：其目标是识别满足最小支持度阈值的所有项集，并将这些符合标准的项集定义为频繁项集（frequent itemset）。
- 强规则的生成：其目标是从上一步骤中识别出的所有高频项集中提取所有高置信度的强规则。
通常频繁项集的产生所需的计算远大于规则产生的计算花销。
第一步，频繁项集产生（Frequent Itemset Generation）
格结构 常常用于列举所有可能的项目集合。展示的是集合I=\{a,b,c,d\}及其相关的格结构。通常来说, 一个包含k个项目的数据集可能会生成2^k-1个频繁项集（不包括空集）。考虑到实际情况中k值往往较大, 这可能会导致需要探查的巨大搜索空间。
有几种方法可以降低产生频繁项集的复杂度：
- 缩减候选集合规模 。如基于先验知识的apriori原理是一种无需计算支持度即可筛选出有效候选集合的方法。
- 优化数据结构以降低比较次数 。通过存储候选集合或压缩数据空间来提升效率。
先验原理
先验原理:\,\,\,\,\,\,\,\,\,如果一个项集是频繁的，则它的所有子集一定也是频繁的
先验原理本质上非常易于理解：如图所示
若{ABC}被视为频繁项集，则必然推导出{AB}也是一个频繁项集。反之亦然，则若{A,B}被判定为不频繁项集，则其所有的超集同样也应被视为不频繁项集。
一旦识别出某一项集{AB}不具备高频性特征，则所有包含该项集作为子集的部分（即下图中以灰色标注区域）均无需继续考虑而可直接排除（剪枝操作）。这种基于频率度量构建并逐步缩减搜索空间的方法被称为 基于频率度量的支持剪枝策略 。
该剪枝方法之所以可行的原因在于其依赖的关键属性即：任一项集的支持度必定不低于其任意子集中对应项的支持度这一特点；这一特性也被称为支持度函数满足反单调性。
apriori算法的频繁项集产生
以下作为一个示例： 针对这一类事务，我们设定其最小支持度计数值为3。
在初始阶段，每一个项目都被视为候选1-项集，在这些候选1-项集中执行支持度计数之后（如图所示），系统会剔除那些不符合标准的项目集合{coke}和{Eggs}。这是因为它们各自的出现频率均低于设定的标准值3次。
在下一轮迭代中，我们仅根据频繁1-项目集来生成候选的2-项目组。由于仅有4个独特的1-项目集可用，因此该算法将产生6个可能的2-项目组合（计算方式为C(4, 2)）。完成对这些候选集合的支持度评估后发现，在这些集合中只有4个是不满足条件的。
根据组合数学原理，在4个元素中选择3个元素会产生C^3_4种不同的组合。基于先验知识筛选出所有频繁出现的子集后，在剩下的候选集合中筛选出同时频繁出现的3-项集{bread, Milk, Diaper}。
当我们考察暴力方法生成的候选项时，在计算其数量时发现：当计算到三元组候选时（直至达到三元组会产生）的数量是C^3_6=20个。然而，在枚举所有项集时（直至达到三元组会产生）的数量则会显著增加：即一元、二元和三元候选之和即C^1_6+C^2_6+C^3_6=41个。不过，在应用先验知识进行优化后数量减少至仅需考虑六种一元、六种二元以及一种特殊的三元组合共计13种候选集合，在这个例子中优化策略使得候选集合数目减少了约68%。
关联分析规则的评估指标（Measure for Association Rules）
客观兴趣度量（interestingness Measure)
给定两个变量X和Y之间存在函数关系X→Y（或变量集合{X,Y}），我们可以通过列联表（Contingency table）这一统计工具提取出用于计算相关性度量的关键数据特征
The function f_{11} supports both variables X and Y.
The function f_{10} supports variable X but excludes variable Y.
The function f_{01} excludes variable X while supporting variable Y.
The function f_{00} excludes both variables X and Y.
举个例子：
关联规则为Tea→Coffee，在此关系中计算得到其信心水平约为P（Coffee|Tea）=15/20=0.75即75%。经计算可得其信心水平达到75%以上这表明饮用茶的人有更高的概率选择饮用咖啡而不是选择不饮用咖啡
看上去这个规范合乎逻辑
个体在喝茶时有75%的概率倾向于饮用咖啡。
然而计算得出P(Coffee)= 0.9表明，在不喝茶的情况下饮用咖啡的概率反而有所上升。
请注意P(Coffee|\bar{Tea})= (75/80) = 93.75%
再来看
P(\text{蜂蜜} \cap \text{茶}) = 50\%
Tea→honey转移的可能性较低。
然而P(\text{蜂蜜}) = 12\%，因此可以推断出喝茶的人更倾向于选择含有蜂蜜的产品。
上面茶与咖啡的例子中，
P(Coffee|Tea) = 15/20 = 0.75
P(Coffee)= 0.9
Lift = 0.75/0.9 =0.8333 （＜1，因此呈负相关）