频繁项集是指支持度大于等于最小支持度(minsup)的集合(颜跃进等，2004)，频繁项集挖掘的主要步骤为:①候选生成，在集合I中，每一个项集都可能是频繁模式，候选项集的搜索空间是指数式的；②支持度计算，计算每个候选模式X并判定它是否为频繁的。
在所有可能的项集中，有很多候选都不是频繁的。令X，Y⊆I为任意两个项集，若X⊆Y，则sup(X)≥sup(Y)，由此可得:①如果X是频繁的，则其任意子集Y⊆X也是频繁的；②如果X不是频繁的，则其任意超集Y⊇X都不是频繁的。
Apriori方法利用以上两个性质，采用逐层或宽度优选的方法来访问项集搜索空间，并修剪掉所有非频繁候选的超集，因为非频繁项集的超集都是非频繁的，这就避免了生成含有非频繁项子集的候选。
除了通过项集剪枝来改进候选的生成步骤，Apriori方法同样大大降低了I/O复杂性，它对前缀进行深度优先搜索，并计算所有大小为k的有效候选(即构成了前缀树的第k层)的支持。
计算流程见算法4.2中伪代码。令C(k)代表包含所有k-项集的前缀树。首先将单个项插入一个初始为空的前缀树，得到C(1)。while循环(第5～11行)通过生成D中每个事务的k-子集，对每个这样的子集，对C(k)中的对应候选(如果存在)的支持度加1，从而实现第k层支持的度的计算。通过这种方式，在每一层都只会扫描一次，并且在扫描的过程中对所有候选k－项集的支持度进行增量。接下来，移除任意的非频繁候选(第9行)。剩余的前缀的叶子就构成了频繁k-项集的集合F(k)，然后可用于下一层的候选(k＋1)－项集(第10行)。
算法4.2 Apriori算法伪代码
FPGrowth方法使用一种增强的前缀树对数据D进行索引(冯晓龙等，2018)，以实现快速的支持度计算。树中的每个节点都用单个项标注，每一个子节点代表一个不同的项，每个节点同时存储了从根节点到它路径上的项，从而构成项集的支持度信息。
FP树按照以下方式构建:树的根初始化为空项∅。对于每一个＜t，X＞∈D，其中X＝i(t)，将项集X插到FP树，代表X的路径上的所有节点的计数值都加1。若X与某些之前插入的事务共享前缀，则在整个共同前缀上，X会遵循相同的路径。对于X中剩余的项，在共同前缀下创建新的节点(计数初始化为1)。当所有事务都插入之后，FP树就构建完成了。
FPGrowth将所有的项按照支持度的降序排列。首先计算所有单项i＝I的支持度；然后，丢弃非频繁的项，并对频繁项按支持度值降序排列；最后，每个元组＜t，X＞∈D都插到FP树中(X中的项按照支持度降序重新排列)。FP树构建完成后，所有的频繁项集就可以从树中挖掘出来。
基于频繁树模式的频繁集搜索方法见算法4.3。当FP树是多条路径时，枚举所有路径子集的项集，且每个项集的支持度等于其中最不频繁项的支持度值(第2～6行)。当FP树是单一路径时，按照支持度的升序为其中的每一个频繁项i建立投影FP树。产生FP树是当前前缀和项i的项集X的投影(第9行)。找到树中所有i的出现，对于每一个出现，确定其对应的从根到i的路径(第13行)。一个给定路径中的项i的计数存在于cnt(i)中(第14行)，并将该路径插到新的投影树RX，其中X是对前缀P新增项i得到的项集。然后，以FP树RX和新的前缀集X作为参数，递归调用FPGrowth。
算法4.3 FPGrowth算法伪代码
有关应急大数据的空间分析与多因素关联挖掘的文章
在借助数据结构存放中间结果来挖掘关联规则的算法中，FP-growth算法[89]效率较高，其中使用的树结构FP-Tree成为很多研究的基础。通过递归调用FP-growth的方法来直接产生频繁项目集。为方便后面叙述，表2.1中在第3列列出了每个事务中按降序排列的频繁项。第二次扫描数据库并构建FP-Tree。图2.6[例2.1]生成的FP-TreeFP-Tree的构造算法如图2.7所示。FP-growth算法以FP-Tree头表的倒序为计算顺序，从下至上递归搜索FP-Tree，逐步生成所有的频繁项集。图2.7FP-Tree的构造算法图2.8FP-growth算法......
2023-06-16
图2.2事务数据库的4种表示形式项目向量；项目列表；Tid向量；Tid列表设X为I中某些项目的集合，简称为项集。如果项目集XT，则称事务T包含项集X，或称事务T支持项集X。频繁项集具有如下两个性质：如果X是频繁项目集，那么X的任何非空子集都是频繁项目集。还有相当多的学者研究了关联规则挖掘与关系数据库紧密结合的问题[71，72-88]，关联规则的结果评价标准问题[81]，挖掘系统的构架、交互方式及可视化问题[83]等。......
2023-06-16
设数据集D被分割成分块D1，D2，...，Dn，全局最小支持数为minsup_count。因此，探索新的理论和算法来减少数据库的扫描次数和候选集空间占用，已经成为近年来关联规则挖掘研究的热点之一，典型的方法是FP-tree算法。......
2023-11-08
Apriori算法[3]是单维、单层、布尔关联规则挖掘算法，是最简单形式的关联规则挖掘。该算法是挖掘产生布尔关联规则频繁项目集的经典算法，对关联规则挖掘研究有着重要影响。图2.3Apriori-gen算法Apriori算法调用Apriori-gen，生成所有频繁项集，如图2.4所示。Apriori算法假定数据库驻留在内存中。Apriori算法之后，学者们不断研究其改进算法及其他思想的关联规则挖掘算法，取得了很多成果。图2.4Apriori算法图2.5找出频繁项集L后生成关联规则算法......
2023-06-16
设某一属性的所有值的数据集为S，其平均值为Smean。根据这些想法，提出一种基于聚类的全局特异数据挖掘方法。构架仍由挖掘特异属性和挖掘特异记录两个层次构成。从原则上讲可以采用任何基于距离的聚类算法对S进行聚类，采用的聚类算法的效果好，可以减少后续的计算量。图3.2SimC聚类算法可以看出，k是控制聚类半径Cd的。现在根据式（3.9）计算每个类的特异因子，记为CPF。显然，CPF越小的类，其中的元素是特异数据的可能性越小。......
2023-06-16
计算这些序列的频率和时间平均方差形成特征向量，利用此特征向量数据进行了多方面的实验，验证其在人的行为识别方面的有效性。实验表明，当分段长度达到30帧以上时，就可获得很高的分类精度，且分段长度的变化对识别精度影响就会很小了。......
2023-06-16
量子遗传算法是一种将遗传算法和量子计算相结合的概率优化方法，两者相互作用。量子遗传算法是一种将量子比特的概率幅用于染色体编码，用量子门的调整操作来实现染色体更新，以完成进化搜索的方法。量子遗传算法的流程如下：初始化种群Q，随机生成n个用量子比特编码的染色体。......
2023-06-29
关联规则挖掘及算法郑继刚杨春华曾庆红赵若男摘要:关联规则可分为布尔型和数值型、单层和多层、单维和多维关联规则挖掘。本文阐述关联规则的定义以及分类，详细介绍经典的关联规则挖掘Apriori算法。可信度是对关联规则准确性的衡量，是得出关联规则的依据。......
2024-03-27
相关推荐