机器学习关联规则算法之Apriori

欢迎关注本人的微信公众号AI_Engine

先验算法（Apriori Algorithm）是关联规则学习的经典算法之一，且应用在商业等诸多领域。本文会对Apriori算法的应用场景以及相关的基本术语加以介绍，之后对算法原理进行分析，其中包括核心原理、流程步骤、优缺点等。

关联规则算法是一种基于规则的机器学习算法，该算法可以在大数据中发现彼此之间的关系。它的目的是利用一些度量指标来分辨数据库中存在的强规则。也即是说关联规则挖掘是用于知识发现，而非预测，所以是属于无监督的机器学习方法。

应用场景：Apriori 算法广泛应用于各种领域，通过对数据的关联性进行了分析和挖掘，下面举几个例子。

Apriori算法广泛应用于消费市场价格分析中

它能够很快的求出各种产品之间的价格关系和它们之间的影响。通过数据挖掘，市场商人可以瞄准目标客户，采用个人股票行市、最新信息、特殊的市场推广活动或其他一些特殊的信息手段，从而极大地减少广告预算和增加收入。百货商场、超市和一些老字型大小的零售店也在进行数据挖掘，以便猜测这些年来顾客的消费习惯。

Apriori算法应用于网络安全领域，比如网络入侵检测技术中。

早期中大型的电脑系统中都收集审计信息来建立跟踪档，这些审计跟踪的目的多是为了性能测试或计费，因此对攻击检测提供的有用信息比较少。它通过模式的学习和训练可以发现网络用户的异常行为模式。采用作用度的Apriori算法削弱了Apriori算法的挖掘结果规则，是网络入侵检测系统可以快速的发现用户的行为模式，能够快速的锁定攻击者，提高了基于关联规则的入侵检测系统的检测性。

Apriori算法被广泛应用于移动通信领域。

移动增值业务逐渐成为移动通信市场上最有活力、最具潜力、最受瞩目的业务。随着产业的复苏，越来越多的增值业务表现出强劲的发展势头，呈现出应用多元化、营销品牌化、管理集中化、合作纵深化的特点。针对这种趋势，在关联规则数据挖掘中广泛应用的Apriori算法被很多公司应用。依托某电信运营商正在建设的增值业务Web数据仓库平台，对来自移动增值业务方面的调查数据进行了相关的挖掘处理，从而获得了关于用户行为特征和需求的间接反映市场动态的有用信息，这些信息在指导运营商的业务运营和辅助业务提供商的决策制定等方面具有十分重要的参考价值。

基本术语:

1.项集：项集是项的集合。包含k个项的项集称为k项集，如集合{面包}，{牛奶}都是一个单项集（一般人们买了面包都会买一些牛奶）。

2.支持度:项集A和B同时发生的概率（联合概率），反应出某种规则出现的是否重要。

3.置信度：当项集A发生的情况下，项集B发生的概率（条件概率），反应出某种规则是否可靠。

    等价于：

4.最小支持度和最小置信度：最小支持度是用户或专家定义的衡量支持度的一个阈值，表示项目集在统计意义上的最低重要性；最小置信度是用户或专家定义的衡量置信度的一个阈值，表示关联规则的最低可靠性。同时满足最小支持度阈值和最小置信度阈值的规则称作强规则。

核心思想与步骤：

支持度和置信度越高，说明规则越强，关联规则算法就是挖掘出满足一定强度的规则。在执行算法之前，我们需要先给定最小的支持度和最小的置信度，生成关联规则一般被划分为如下两个步骤：

1、利用最小支持度从所有事物中找到频繁项集。给定一个事物 D ，寻找频繁项集流程如下图所示（盗的）：

C1 中 {1} 的支持度为 2/4 = 0.5 表示在 D 中的 4 条事务中，{1} 出现在其中的两条事务中，以后几个步骤的支持度计算方式也是类似的。假定给定的最小支持度为 0.5，那么最后我们可以得到一个包含 3 个项的频繁项集 {2 3 5}。这里没有出现{1 2 3}和{1 3 5}的原因就是{1 2}和{1 5}在C2中不是频繁项集。这样我们可以引申出一条定律：如果一个集合不是频繁项集，则它的所有超集都不是频繁项集。举例：假设集合{A}不是频繁项集，即A出现的次数小于min_support，则它的任何超集如{A,B}出现的次数必定小于min_support，因此其超集必定也不是频繁项集。同样可推理另一条定律是：如果一个集合是频繁项集，则它的所有子集都是频繁项集。举例：假设一个集合{A,B}是频繁项集，即A、B同时出现在一条记录的次数大于等于最小支持度min_support，则它的子集{A},{B}出现次数必定大于等于min_support，即它的子集都是频繁项集。

另外，从图中我们可以看到 itemset 中所包含的 item 是从1增长到3的。并且每次增长都是利用上一个itemset 中满足支持度的 item 来生成的，这个过程称之为候选集生成（candidate generation）。譬如说C2里就不包含C1中的4 。

2、利用最小置信度从频繁项集中找到关联规则。

同样假定最小的置信度为0.5，从频繁项集 {2 3 5} 中我们可以发现规则 {2 3} ⇒ {5} 的置信度为 1 > 0.5 ，所以我们可以说 {2 3} ⇒ {5} 是一个可能感兴趣的规则。

优缺点：

优点：易编码实现

缺点：在大数据集上可能较慢

适用数据类型：数值型 或者 标称型数据。

以上这就是Apriori算法的入门教程了，今天太晚了，附上一下代码。早点休息，各位~