【理论篇】数据挖掘 第六章 挖掘频繁模式、关联和相关性：基本概念和方法（上）
说明：文章为《数据挖掘：概念与技术 原书第03版》的学习笔记，该书是数据挖掘领域的经典之作，想了解更多内容请参阅原著。
一、频繁模式基本概念
模式 ：通常指的是数据中的一种规律、趋势或特征，可以是单一的特征、属性，也可以是多个特征之间的关系或组合；
频繁模式 ：频繁地出现在数据集中的模式。
1.1、购物篮分析：一个诱发例子
频繁项集挖掘的一个典型例子是购物篮分析。该过程通过发现顾客放入他们“购物篮” 中的商品之间的关联，分析顾客的购物习惯(见图)。这种关联的发现可以帮助零售商 了解哪些离品频繁地被顾客同时购买，从而帮助他们制定更好的营销策略。例如，如果顾客 在一次超市购物时购买了牛奶，他们有多大可能也同时购买面包（以及何种面包）?这种信息可以帮助零售商做选择性销售和安排货架空间，导致增加销售量。
1.2、频繁项集、闭项集和关联规则
在学习频繁项集挖掘之前，需要了解以下概念：
项的集合 ：牛奶、面包等超市所有商品的集合；
事务 ：购物篮分析中的每一笔订单：非空集合，每一个事务都有一个标识符；
项集 ：商品的集合，项集的项可以是1个也可以是多个；包含1个项就是1项集，包含k个项就是k项集；
关联规则： 项集A(前置项) => 项集B(后置项)；
支持度 ：同时包含项集A，B的事务 / 总事务；
置信度 ：包含A的事务同时也包含B的事务的百分比，可以理解为顾客选择A的情况下选择B的概率；
强规则 ：同时满足最小支持度阅值(min_sup)和最小置信度阈值(min con)的规则称为强规则；
相对支持度 ：P(A U B) 概率；
绝对支持度 ：项集的频度、支持度计数或计数。计数
频繁项集： 相对支持度满足预定义的最小支持度阈值；
闭频繁项集： 假设项集X在数据集D中，如果不存在真超项集Y使得Y与X在D中具有相同的支持度计数，则项集X是闭项集，如果项集X又是频繁的，则项集X为闭频繁项集；
极大频繁项集： 假设项集X在数据集D中，且X是频繁的，没有其他频繁项集是X的真超集，则项集X为极大频繁项集；
二、频繁项集挖掘方法
2.1、Apriori 算法：通过限制候选产生发现频繁项集
Apriori算法是经典的关联规则算法。Apriori算法的目标是找到最大的K项频繁集。
Apriori算法的核心思想
- 先验性质 ：频繁项集的子集必定也是频繁项集；
- 反单调性 ：非频繁项集的超集必然不是频繁项集；
Apriori算法原理
Apriori算法从寻找1项集开始，通过最小支持度阈值进行剪枝，依次寻找2项集，3项集直到没有更过项集为止。
下面是一个案例图解（这个案例看懂的话，建议查看原文的案例）：
- 图中有4个记录，可以理解为4个订单，记录项有1，2，3，4，5若干;
- 首先先找出1项集对应的支持度（C1），可以看出4的支持度低于最小支持阈值，先剪掉，生成（L1），这过程称为剪枝步 ;
- （L1）中的1项集连接产生候选2项集集合（C2）的过程称为连接步 ，计算支持度（C2），可以看出（1，5）（1，2）支持度低于最小支持阈值，先剪掉（L2）;
- 从2项集生成3项集，（1，2，3）（1，2，5）（2，3，5）只有（2，3，5）满足要求;
- 3项集满足要求的项只有（2，3，5），没有更多的项集连接为4项集，停止迭代。
2.2、由频繁项集产生关联规则
一旦由事务找出频繁项集，就可以直接由频繁项集产生强关联规则(强关联规则 满足最小支持度 和最小置信度)，关联规则的公式如下：
让我们看一个例子，也是书本中的例子，现在有9个事务，如图所示，有I1，I2，I3，I4，I5项。
假设最小支持度计数为2,即min_sup=2，则最小支持度为 2/9约22%。根据Apriori算法 计算，过程如下：
计算的结果中包含多个频繁项集，其中频繁项集X = {I1,I2,15}可以产生哪些关联规则？X的非空子集 是{I1,I2} 、{I1,I5}、{I2,I5}、{I1}、{I2}和{I5}。结果关联规则如下，每个都列 出了置信度。
如果最小置信度阈值为70%，则只有第2、第3和最后一个规则可以输出，因为只有这些是强规则。
2.3、提高 Apriori 算法的效率
提高Apriori算法的效率是数据挖掘领域的一个重要研究方向。Apriori算法是一种用于挖掘频繁项集的经典算法，但其性能受到一些因素的制约，如候选项集数量庞大、数据库扫描次数多等。以下是一些提高Apriori算法效率的方法：
1. 减少候选项集的生成
- 剪枝技术 ：利用Apriori原理，即一个项集是频繁的，则它的所有非空子集也必须是频繁的。在生成候选项集时，可以剪去那些其子集不是频繁项集的候选项集，从而减少候选项集的数量。
- 优化连接步骤 ：在生成候选项集时，避免重复连接相同的项，以减少不必要的计算。
2. 减少扫描数据库的次数
- 使用更高效的数据结构 ：如位图（bitmap）或哈希表（hash table）来存储频繁项集和候选项集，这样可以更快地判断一个项集是否频繁，从而减少扫描数据库的次数。
- 结合其他算法 ：如FP-Growth算法，该算法通过构建FP树来减少数据库扫描次数，并直接在树上进行频繁项集的挖掘。
3. 并行化处理
- 分布式计算 ：将数据集分成多个子集，分别在不同的机器或线程上并行处理，然后将结果合并。这样可以显著提高算法的处理速度。
4. 参数调优
- 调整最小支持度阈值 ：适当提高最小支持度阈值可以减少生成的频繁项集数量，但也可能导致一些重要的关联规则被遗漏。因此，需要根据具体应用场景和需求来设置合适的最小支持度阈值。
- 调整其他参数 ：如最小置信度阈值等，也可以对算法的性能产生影响。
5. 算法改进
- 引入新的优化策略 ：如GE-Apriori算法等，通过改进候选项集的生成和剪枝策略，以及优化数据库扫描方式等，来提高算法的效率。
6. 数据预处理
- 数据清洗 ：确保输入数据的准确性和完整性，避免因为数据错误或缺失而导致的算法性能下降。
- 数据转换 ：将数据转换成适合Apriori算法处理的格式，如事务数据集的形式。
提高Apriori算法的效率需要从多个方面入手，包括减少候选项集的生成、减少数据库扫描次数、并行化处理、参数调优、算法改进以及数据预处理等。这些方法可以单独使用，也可以结合使用，以达到更好的优化效果。
2.4、挖掘频繁项集的模式增长方法（FP-growth)
虽然Apriori算法在数据挖掘领域具有重要地位，但FP-growth算法在减少数据库扫描次数、提高挖掘效率等方面具有显著优势。
我单独出了一篇文章介绍FP-growth，在此节便略过。
总的来说就是大部分场景下，特别是对于大规模数据集，FP-growth比Apriori快，效率更好。
2.5、使用垂直数据格式挖掘频繁项集
使用垂直数据格式挖掘频繁项集是另一种有效的方法，与经典的Apriori算法和FP-growth算法相比，它在处理大规模数据集时具有一定的优势。下面将分别介绍垂直数据格式挖掘频繁项集的基本思想，并与Apriori和FP-growth进行对比。
2.5.1 垂直数据格式挖掘频繁项集
垂直数据格式（Vertical Data Format, VDF）是一种数据结构，它将事务集中的项（items）作为列，事务ID作为行来组织数据。在这种表示法中，如果事务中包含某个项，则在该项对应的列中标记该事务的ID。例如，如果事务集包含三个事务T1={a, b, c}, T2={b, d}, T3={a, c, e}，则垂直格式的数据表可能会是这样：
| a | b | c | d | e | |
|---|---|---|---|---|---|
| T1 | 1 | 1 | 1 | 0 | 0 |
| T2 | 0 | 1 | 0 | 1 | 0 |
| T3 | 1 | 0 | 1 | 0 | 1 |
基本思想
在垂直数据格式下，挖掘频繁项集的基本思想是：
事务剪枝 ：通过计算每个项的出现频率，可以立即删除那些频率小于最小支持度（min_sup）的项，因为它们不能构成频繁项集。
候选项集生成 ：使用剩余的项来生成候选项集。由于项是按列组织的，因此可以更高效地计算项之间的交集和并集，进而确定候选项集的支持度。
支持度计数 ：由于数据是按项组织的，所以支持度计数可以通过计算每个候选项集（即一组项）在垂直表中的行交集的大小来快速完成。
2.5.2 与Apriori算法的对比
效率 ：Apriori算法在生成候选项集时需要多次扫描数据集，并且随着项集长度的增加，候选项集的数量会呈指数级增长。而垂直数据格式下的挖掘方法通常只需要扫描数据集一次（用于生成项的初始频率），并且在后续过程中，候选项集的生成和支持度计算都可以更高效地执行。
内存使用 ：Apriori算法在候选项集数量庞大时可能会遇到内存不足的问题。垂直数据格式可以通过减少需要同时存储在内存中的候选项集数量来减轻这一问题。
2.5.3 与FP-growth算法的对比
数据结构 ：FP-growth算法使用FP-tree（频繁模式树）来存储数据，这是一种高度压缩的数据结构，可以有效地存储频繁项及其之间的关系。而垂直数据格式则是一种简单的行列转换，没有FP-tree那样复杂的结构。
性能 ：FP-growth算法在构建FP-tree时可能需要一些计算，但一旦树被构建，它就可以非常高效地回答所有频繁项集的查询，而无需多次扫描数据集。垂直数据格式虽然也能减少数据集扫描次数，但在处理大数据集时，其性能可能不如FP-tree稳定。
适应性 ：FP-growth算法特别适合于挖掘包含大量重复项的数据集，因为它可以通过共享前缀来压缩数据。而垂直数据格式在处理这类数据集时，其压缩效率可能不如FP-tree。
垂直数据格式挖掘频繁项集是一种有效的方法，尤其在数据集的某些维度上具有较高的稀疏性时。然而，在处理大规模数据集或需要高度优化的性能时，FP-growth算法可能更加适用。而Apriori算法则因其简单性和易实现性，在数据量不是极端大的情况下仍然是一个很好的选择。
2.6、挖掘闭模式和极大模式
挖掘闭模式思路：
项合并 ：如果包含频繁项集X的每个事务都包含项集Y,但不包含Y的任何真超集，则 XUY形成一个闭频繁项集，并且不必再搜索包含X但不包含Y的任何项集。
子项集剪枝 ：如果频繁项集X是一个已经发现的闭频繁项集Y的真子集，并且support_count(X) = support_count(Y)，则X和X在集合枚举树中的所有后代都不可能是闭频繁项集， 因此可以剪枝。
项跳过 ：在深度优先挖掘闭项集时，每一层都有一个与头表和投影数据库相关联的前缀 项集X。如果一个局部频繁项p在不同层的多个头表中都具有相同的支持度，则可以将p从 较高层头表中剪裁掉。
极大模式与闭模式具有许多相似性，这里介绍的技术都可以扩展到挖掘极大频繁项集。
思考 ：满足最小支持度 和最小置信度 的模式一定是有趣的吗？