【数据挖掘笔记六】挖掘频繁模式、关联和相关性：基本概念和方法
6.挖掘频繁模式、关联和相关性：基本概念和方法
频繁模式（frequent pattern）是频繁地出现在数据集中的模式。
6.1 基本概念
频繁模式挖掘是一种用于分析给定数据集中频繁出现的关系的研究方法。其主要目标在于发现大型事务或关系型数据中涉及的项之间的有趣关联和相关性。其中最具代表性的案例是购物篮分析。
基于全域为产品集合的假设下进行购物篮分析。每个产品对应一个二元变量用于标识其是否包含于购物篮中。每个购物篮用一个二元向量来表示。通过对布尔向量进行分析从而获得这些关联模式。这些模式可用关联规则（association rule）形式表示例如：如果购买计算机则会伴随地购买杀毒软件这种关系可以用如下规则表达：computer→antivirus_software[support=2%;confidence=60%]其中支持度（support）和置信度（confidence）是衡量关联规则重要性的指标。如果一条规则同时满足最低的支持阈值和最小的置信阈值那么这条关联规则就是有意义的。
满足以下两个条件的规则即为强规则：一是最低支持度指标（min_sup）；二是最低置信度指标（min_conf）。
由若干项目组成的集合被定义为"项集"；其中包含k个项目组成的"子集"则被称为"k-项目集"。“子集”的出现次数即为该"子集"的相关属性之一——其被定义为"频率计数值"或者简而言之就是所谓的"支撑程度计数"。“子集”的支撑程度又被统称为"相对支撑程度"；而所涉及的具体事务数量则被视为它的绝对支撑程度。“当某一个特定子集I"在满足预设条件下的'最小支撑程度阈值'时（即相应地这个子集中具体存在的事务数量达到了设定好的'最小支撑程度计数值'），那么我们就称这个特定子集I"为一个'频繁项目组'"。（通常用L_k"来表示所有大小等于k"的所有频繁项目组构成的一个总称）。基于关联规则挖掘的基本流程大致分为两个步骤：
第一：找出所有的频繁项集；第二：由频繁项集产生强关联规则。
从大型数据集中挖掘高频项目群的主要困难在于生成大量满足最小支持度（min\_sup）阈值的项目群。项目群X在数据源D中被称为闭合（closed），若不存在一个真超项目群Y使得Y与X在D中的支持度计数相同。项目群X被视为数据源D中的闭合高频项目群（closed frequent itemset），当且仅当它既满足闭合性又满足高频性要求。此外，在数据源D中被称作最大高频项目群（maximal frequent itemset）或最大项目群（max-itemset）时，则需满足两个条件：其一为高频性；其二则不存在任何超项目群Y能够同时具备高频性和包含关系于X之中。
6.2 频繁项集挖掘方法
该Apriori算法主要针对布尔关联规则挖掘中的频繁项集提取具有开创性的贡献。
1）Apriori算法：通过限制候选产生发现频繁项集
先验性质： item sets with frequent occurrences exhibit the property that all their non-empty subsets are also frequent. This characteristic, referred to as anti-monotonicity (antimonotonicity), signifies that if a set cannot pass a particular test, none of its supersets can pass the same test either.
基于预设性质，在Apriori算法中采用逐步推进过程。其中k-项目用于生成k+1-项目的候选组合。首先通过对数据库进行扫描统计每个项目的频率值并筛选出所有满足最小支持度条件的一阶项目集合（记为L₁）。然后利用该一阶候选集合生成二阶候选组合（记为L₂）。接着利用该二阶候选组合生成三阶候选组合（记为L₃），依此类推直到无法再发现新的频繁组合为止。每次发现新的候选组合都需要对整个数据库进行一次完整的扫描以验证其真实性。
基于先验性质从Lk-1找出Lk，由连接步和剪枝步组成：
在连接步骤中,我们的目标是确定L_k.为此,我们将前一阶段的结果表L_{k-1}与其自身进行联结,从而生成一系列候选的k-项目组合.这些组合被记录为集合C_k.需要注意的是,该算法假设所有事务或项目集中各项均按字段顺序排列.
在数据挖掘过程中，在该数据结构中进行操作的主要步骤被称为"剪枝步"。具体来说，在这个过程中,"C_k"作为一个"L_k"的大集合存在,其成员既可以是非高频项,也可以是非高频项...,但所有高频k-项目集必然属于这个大集合
挖掘布尔关联规则发现频繁项集的Apriori算法如下：
2）由频繁项集产生关联规则
当数据库D中的事务识别出满足条件的频繁项集时，则可以直接生成满足最小支持度和最小置信度的强关联规则。
3）提高Apriori算法的效率
提高基于Apriori挖掘的效率：
该哈希表方法能够有效地减少高阶候选集Ck(k>1)的空间占用；将数据按照哈希值分配至相应的存储容器中。
事务缩减（进一步缩减迭代扫描中的事务数量）：任何不包含频繁k项集的事务也不可能包含频繁(k+1)项集。
为了寻找候选集中所需的数据区域：首先在第一阶段中将集合D按照事务化的性质划分为n个互不重叠的部分；接着在第二阶段中计算每个候选的真实支持值，并识别出所有全局频繁项。
抽样：对给定数据的一个子集上挖掘。
动态项集计数：在扫描各个关键点时生成候选项集，在进行动态项集计数后，则会将整个数据库划分成以起始点标注的不同区域。
4）挖掘频繁项集的模式增长方法
在Apriori算法中可能会生成大量候选集合，在每次迭代中都需要对整个数据集进行扫描以收集高频项，并利用模式匹配技术检查这些候选项是否满足最小支持度要求。这一过程产生的计算开销较大。鉴于此，在数据挖掘领域提出了Frequent-Pattern Growth（即FP-Growth）算法。FP-Growth算法采用了分治法来进行优化处理：首先构建了一棵称为FP-Tree的数据结构，并在其中存储了各个项之间的关联关系信息；随后将这些数据进一步划分为多个子数据集，并分别处理以提取出所有的频繁项目组合；对于每一个生成的模式片段，则只需要关注与之相关的特定子数据集即可完成后续的操作。
FP树的模式挖掘过程从长度为1的频繁模式（初始后缀模式）开始执行。随后生成其对应的条件模式基（即一个子数据库），该子数据库由FP树中与该后缀模式一起出现的所有前缀路径组成。接着构建相应的条件FP树，并在其基础上继续进行递归分析以完成整个挖掘任务。这种基于后缀模式与条件FP树之间的连接机制实现了一种高效的多层递归分析方法。
FP-growth方法通过将发现长频繁模式的问题转化为在较小的条件数据库中逐步搜索简短的模式并连接上缀的方式实现数据挖掘功能。以频率最低的项为基础进行处理从而带来了良好的选择性大大减少了搜索成本。
算法：FP-Growth，使用FP树，通过模式增长挖掘频繁模式
输入：D:事务数据库
min_sup：最小支持度阈值
输出：频繁模式的完全集
方法：
1.按以下步骤构造 FP 树：
a.在事务数据库D中进行一次扫描，在获取其支持度计数的基础上确定频繁项集合F，并将这些项按照支持度降序进行排序以得到结果列表L
b.创建FP树的根节点，以null标记它，对于D中每个事务Trans，执行：
将Trans中的频繁项目按照L的顺序进行筛选，并定义筛选后得到的频繁项目列表为[p|P]（其中p代表第一个项目），其余项目构成一个列表P。然后调用insert_tree函数处理该列表
当树T中的某一个节点N满足其子项属性值与父节点P相同时，则将节点N的计数加一；否则，在树T中新增一个节点N，并将其初始计数值设为一。该新生成的单个子项树不仅会将其直接连接至父节点T，并依据子项属性值与其相关联的方式连接至其他拥有相同子项属性值的所有相关联的对象构成的新结构中进行处理。若集合P非空，则递归地调用insert_tree函数将集合P与新生成的单个子项树合并。
2.FP树的挖掘同构调用FP_growth(PF_tree,null)实现，该过程实现如下：
Procedure FP_growth(Tree,a)
if Tree包含单个路径P then
for 路径P中结点的每个组合（记作b）
生成模式a ∪ b ，其计算值support_count等于b中节点的最低计算值。
else for Tree的头表中的每个ai{
产生一个模式b=a ∪ ai，其支持度计数support_count=ai.support_count；
构造b的条件模式基，然后构造b的条件FP树Treeb；
if Treeb ≠ ∅ then
调用FP_growth(Treeb,b);
}
该方法性能分析表明，在发现长项项集与短项项集方面均具有良好的扩展性，并且其效率明显优于Apriori算法。
5）使用垂直数据格式挖掘频繁项集
Apriori算法与FP-growth算法均基于事务作为行、商品项作为列的组织方式，亦称横截面数据布局。
垂直数据格式，商品项为行，事务为列。
以垂直数据格式为基础，在无需从数据库中扫描以获取k+1项集的支持度信息的情况下（由于每个k项集都预存了完整的支持度计算所需的信息），这种方法实现了对所需信息的有效利用。
6）挖掘闭模式和极大模式
挖掘闭频繁项集的剪枝策略包括：
a. 项目合并：如果所有包含频繁项目集合X的事务也都包含了项目集合Y，并且没有任何Y的真超集被其覆盖，则X ∪ Y形成一个闭合频繁项目集合，并且无需进一步搜索所有包含X而不包含Y的事务。
b. 子项集剪枝：当频繁项集X被已获取的闭频繁项集Y包含为真子集时，并且X与Y的支持计数相等，则其后续节点中也不会出现任何闭频项集, 因此可以实现剪枝操作。
第c步：跳过处理
当一个新的频繁模式生成后, 必须执行两种闭包操作: 首先, 检查该新的频繁模式是否为任何一个已知的支持度相同的封闭模式（closed itemset）中的超集; 其次, 检查该新的模式是否包含任何一个已知的支持度相同的封闭模式作为其子集。
6.3 那些模式是有趣的：模式评估方法
大多数关联规则挖掘算法采用基于支持度与置信度的框架进行工作。然而，在设置过低的支持度阈值进行挖掘或试图发现长模式时，在结果中会产出大量缺乏吸引力的关联规则。这成为该技术应用中的一个关键挑战之一。
1）强规则不一定有趣的
利用支持度与置信度相结合的框架能够识别出高度相关的规则。然而，在实际应用中发现这些强关联规则仍然无法有效剔除那些不具吸引力的相关联法规则。因此，在进一步优化时必须评估它们之间的相关性及其蕴含关系
2）从关联分析到相关分析
为了识别规则的有趣性, 借助相关性指标来扩展关联规则的支持-置信度框架. 除了基于支持度和置信度的标准外, 同时考虑项集A与B的相关性评估. 具体而言, 常用的相关性评估方法包括:
提升度（Lift）：项目集合A的发生不受项目集合B的影响，当且仅当P(A∪B)=P(A)P(B)；反之，在这种情况下（即当两个项目集合的相关性存在时），项目的联合发生概率与单独发生的乘积不再相等。此时的提升度计算公式定义为：
lift(A,B)=P(A∪B)/P(A)P(B)
当计算得到lift(A,B)值小于1时, 表明事件A的发生与事件B的发生之间呈负相关关系;若lift(A,B)的结果大于1, 则事件A与事件B之间存在正相关关系;这意味每当事件A发生时, 事件B也会随之发生. 当lift(A,B)等于1时, 在统计学上认为事件A与事件B之间相互独立且互不影响.
0,1
0,1
0,1
这四个度量指标的主要影响因素是变量A、B以及它们的并集A∪B的支持度数据。或者说是这些指标主要受到条件概率P(A|B)和P(B|A)的影响。值得注意的是这些指标不受事务总数量的影响。它们的共同特点在于每个指标值都属于区间[0,1]范围，并且数值越大表示变量间的关系越紧密。
总结：主要采用支持度与置信度作为衡量标准进行关联分析时，在实际操作中可能会导致生成大量潜在关联关系；其中可能存在部分不符合用户需求的内容；因此建议引入可用模式兴趣度作为新指标加入到支持度-置信度框架中，并以此为基础进行优化调整；这样可以在一定程度上帮助我们更加集中地发现那些具有强关联性的模式之间的关系
6.4 小结
海量数据中常见模式、联系及相关的发生率在选择性销售、决策分析以及商务管理等领域具有应用价值。其中购物篮分析是一个广受欢迎的应用领域；商品集合经常被同时或顺序地采购用于了解消费者的购买行为。
海量数据中常见模式、联系及相关的发生率在选择性销售、决策分析以及商务管理等领域具有应用价值。其中购物篮分析是一个广受欢迎的应用领域；商品集合经常被同时或顺序地采购用于了解消费者的购买行为。
2）关联规则挖掘首先确定所有满足最小支持度阈值的关键组合（即频繁项集），然后通过这些频繁项集生成形式为A→B的强关联规则；这些强关联规则需达到预设的信心水平；通过进一步分析其内在联系发现统计相关性。
对于频繁项集挖掘问题而言，在实际应用中已开发出了众多高效且具备扩展性的算法体系。这些系统性方法主要可分为三大类别：其中一类是经典的Apriori系列方法；另一类是以模式为基础的发展起来的FP-growth等智能挖掘技术；第三种则是采用垂直存储策略的分析方法
4）Apriori算法是一种用于二元属性关系布尔关联规则挖掘的开创性算法，在层次化过程中不断提取频繁项集；该算法基于预设性质：所有非空子集若属于一个频繁项集，则同样具有频繁性；在第k次迭代（k≥2），系统会基于前一轮得到的所有(k-1)项频繁集合生成候选k项集合，并对数据库进行一次全面扫描以确定当前轮次中所有的完整频繁k项集合Lk；为了提高效率，在实现过程中借助散列技术和事务压缩手段优化后能显著提升效率。除此之外还引入了分区处理方法（即分别在各数据分区中执行挖掘操作后汇总结果）以及抽样分析方法（即针对部分样本数据进行分析），这些改进措施能在很大程度上减少数据库扫描次数至一两次即可完成任务。
5）FP数据挖掘算法是一种无需生成候选项集的方法用于发现频繁项目组合；构建一个高效地存储事务数据库的高度压缩数据结构（即FP树）；与基于生成式策略的Apriori算法不同 FP-growth着重于逐步扩展频繁模式段 并通过减少不必要的候选生成来提高效率
使用一种称为ECLAT的数据挖掘方法对存储于横截面数据格式中的事务数据库进行频繁模式识别；根据预设属性并结合一些额外优化技术（例如diffset方法），通过对TID-集合之间的交操作对转换后的垂直数据格式数据库进行分析。
7）不是所有强关联模式都具有吸引力。通过模式评估指标扩展支持与置信框架能有效识别出具有吸引力的关键关联模式。其中一种指标具有的特性是零不变性——即其数值不受不包含所考察项集的事务的影响，在多种常见的模式评估指标中都采用了这一特性作为基础参数。这种指标有助于计算出提升程度等关键评价值
此外，在讨论这些指标时，默认情况下我们主要关注的是全局一致性（Global Consistency）和最高一致性（Highest Consistency）。除了余弦相似性和Kulczynski相似性外，其他两种指标具有零不变性（Zero Invariance）。值得注意的是，在实际应用中可以选择将Kulczynski相似性和不均衡比率结合起来应用。