首先找出所有的频集,这些项集出现的频繁性至少和预定义的最小支持度一样。然后由频集产生强关联规则,这些规则必须满足最小支持度和最小可信度。然后使用第1步找到的频集产生期望的规则,产生只包含集合的项的所有规则,其中每一条规则的右部只有一项,这里采用的是中规则的定义。一旦这些规则被生成,那么只有那些大于用户给定的最小可信度的规则才被留下来。
Apriori算法过程
第一步通过迭代,检索出事务数据库中的所有频繁项集,即支持度不低于用户设定的阈值的项集;
第二步利用频繁项集构造出满足用户最小信任度的规则。
具体做法就是:
首先找出频繁1-项集,记为L1;然后利用L1来产生候选项集C2,对C2中的项进行判定挖掘出L2,即频繁2-项集;不断如此循环下去直到无法发现更多的频繁k-项集为止。每挖掘一层Lk就需要扫描整个数据库一遍。算法利用了一个性质:任一频繁项集的所有非空子集也必须是频繁的。
假设我们一共有 4 个商品: 商品0, 商品1, 商品2, 商品3。 所有可能的情况如下:
如果我们计算所有组合的支持度,也需要计算 15 次。即 \( 2^N - 1 = 2^4 - 1 = 15 \)。随着物品的增加,计算的次数呈指数的形式增长 。为了降低计算次数和时间,研究人员发现了一种所谓的 Apriori 原理,即某个项集是频繁的,那么它的所有子集也是频繁的。 例如,如果 {0, 1} 是频繁的,那么 {0}, {1} 也是频繁的。 该原理直观上没有什么帮助,但是如果反过来看就有用了,也就是说如果一个项集是 非频繁项集,那么它的所有超集也是非频繁项集,如下图所示:
在图中我们可以看到,已知灰色部分 {2,3} 是 非频繁项集,那么利用上面的知识,我们就可以知道 {0,2,3} {1,2,3} {0,1,2,3} 都是 非频繁的。 也就是说,计算出 {2,3} 的支持度,知道它是 非频繁 的之后,就不需要再计算 {0,2,3} {1,2,3} {0,1,2,3} 的支持度,因为我们知道这些集合不会满足我们的要求。 使用该原理就可以避免项集数目的指数增长,从而在合理的时间内计算出频繁项集。
Apriori 算法优缺点优点:易编码实现
缺点:在大数据集上可能较慢
适用数据类型:数值型 或者 标称型数据。
Apriori 算法流程步骤:收集数据:使用任意方法。
准备数据:任何数据类型都可以,因为我们只保存集合。
分析数据:使用任意方法。
训练数据:使用Apiori算法来找到频繁项集。
测试算法:不需要测试过程。
使用算法:用于发现频繁项集以及物品之间的关联规则。
应用场景Apriori 算法广泛应用于各种领域,通过对数据的关联性进行了分析和挖掘,挖掘出的这些信息在决策制定过程中具有重要的参考价值。
Apriori算法广泛应用于消费市场价格分析中
它能够很快的求出各种产品之间的价格关系和它们之间的影响。通过数据挖掘,市场商人可以瞄准目标客户,采用个人股票行市、最新信息、特殊的市场推广活动或其他一些特殊的信息手段,从而极大地减少广告预算和增加收入。百货商场、超市和一些老字型大小的零售店也在进行数据挖掘,以便猜测这些年来顾客的消费习惯。
Apriori算法应用于网络安全领域,比如网络入侵检测技术中。
早期中大型的电脑系统中都收集审计信息来建立跟踪档,这些审计跟踪的目的多是为了性能测试或计费,因此对攻击检测提供的有用信息比较少。它通过模式的学习和训练可以发现网络用户的异常行为模式。采用作用度的Apriori算法削弱了Apriori算法的挖掘结果规则,是网络入侵检测系统可以快速的发现用户的行为模式,能够快速的锁定攻击者,提高了基于关联规则的入侵检测系统的检测性。
Apriori算法应用于高校管理中。
随着高校贫困生人数的不断增加,学校管理部门资助工作难度也越加增大。针对这一现象,提出一种基于数据挖掘算法的解决方法。将关联规则的Apriori算法应用到贫困助学体系中,并且针对经典Apriori挖掘算法存在的不足进行改进,先将事务数据库映射为一个布尔矩阵,用一种逐层递增的思想来动态的分配内存进行存储,再利用向量求"与"运算,寻找频繁项集。实验结果表明,改进后的Apriori算法在运行效率上有了很大的提升,挖掘出的规则也可以有效地辅助学校管理部门有针对性的开展贫困助学工作。
Apriori算法被广泛应用于移动通信领域。