APRIORI

关联规则挖掘算法

Apriori算法是第一个关联规则挖掘算法，也是最经典的算法。它利用逐层搜索的迭代方法找出数据库中项集的关系，以形成规则，其过程由连接（类矩阵运算）与剪枝（去掉那些没必要的中间结果）组成。该算法中项集的概念即为项的集合。包含K个项的集合为k项集。项集出现的频率是包含项集的事务数，称为项集的频率。如果某项集满足最小支持度，则称它为频繁项集。

简介

关联规则挖掘是数据挖掘中最活跃的研究方法之一。最早是由 Agrawal 等人提出的1993最初提出的动机是针对购物篮分析问题提出的，其目的是为了发现交易数据库中不同商品之间的联系规则。这些规则刻画了顾客购买行为模式，可以用来指导商家科学地安排进货，库存以及货架设计等。之后诸多的研究人员对关联规则的挖掘问题进行了大量的研究。他们的工作涉及到关联规则的挖掘理论的探索，原有的算法的改进和新算法的设计，并行关联规则挖掘Parallel Association Rule Mining，以及数量关联规则挖掘Quantitive Association Rule Mining 等问题。在提高挖掘规则算法的效率、适应性、可用性以及应用推广等方面，许多学者进行了不懈的努力。

Apriori算法是种挖掘关联规则的频繁项集算法，一种最有影响的挖掘布尔关联规则频繁项集的算法。其核心思想是通过候选集生成和情节的向下封闭检测两个阶段来挖掘频繁项集。其核心是基于两阶段频集思想的递推算法。该关联规则在分类上属于单维、单层、布尔关联规则。在这里，所有支持度大于最小支持度的项集称为频繁项集，简称频集。Apriori算法已经被广泛的应用到商业、网络安全等各个领域。Apriori算法采用了逐层搜索的迭代的方法，算法简单明了，没有复杂的理论推导，也易于实现。但其有一些难以克服的缺点：

（1）对数据库的扫描次数过多。

（2）Apriori算法会产生大量的中间项集。

（3）采用唯一支持度。

（4）算法的适应面窄。

算法思想

该算法的基本思想是：首先找出所有的频集，这些项集出现的频繁性至少和预定义的最小支持度一样。然后由频集产生强关联规则，这些规则必须满足最小支持度和最小可信度。然后使用第1步找到的频集产生期望的规则，产生只包含集合的项的所有规则，其中每一条规则的右部只有一项，这里采用的是中规则的定义。一旦这些规则被生成，那么只有那些大于用户给定的最小可信度的规则才被留下来。为了生成所有频集，使用了递归的方法。

（1） L1 = find_frequent_1-itemsets(D);

（2） for (k=2;Lk-1 ≠Φ ;k++) {

（3） Ck = apriori_gen(Lk-1 ,min_sup);

（4） for each transaction t ∈ D {//scan D for counts

（5） Ct = subset(Ck,t);//get the subsets of t that are candidates

（6） for each candidate c ∈ Ct

（7） c.count++;

（8） }

（9） Lk ={c ∈ Ck|c.count≥min_sup}

（10） }

（11） return L= ∪ k Lk;

可能产生大量的候选集,以及可能需要重复扫描数据库，是Apriori算法的两大缺点。

算法应用

经典的关联规则数据挖掘算法Apriori 算法广泛应用于各种领域，通过对数据的关联性进行了分析和挖掘，挖掘出的这些信息在决策制定过程中具有重要的参考价值。

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

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

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

在地球科学数据分析中，关联模式可以揭示海洋、陆地和大气过程之间的有意义的关系。这些信息能够帮助地球科学家更好的理解地球系统中不同的自然力之间的相互作用。

有关术语

支持度（support）：support(A=>B) = P(A∪B)，表示A和B同时出现的概率。

置信度（confidence）：confidence(A=>B)=support(A∪B) / support(A)，表示A和B同时出现的概率占A出现概率的比值。

频繁项集：频繁项集挖掘是数据挖掘研究课题中一个很重要的研究基础，它可以告诉我们在数据集中经常一起出现的变量，为可能的决策提供一些支持。频繁项集挖掘是关联规则、相关性分析、因果关系、序列项集、局部周期性、情节片段等许多重要数据挖掘任务的基础。因此，频繁项集有着很广泛的应用，例如：购物篮数据分析、网页预取、交叉购物、个性化网站、网络入侵检测等。，对频繁项集挖掘算法进行研究的方向大概可归纳为以下四个方面：一、在遍历方向上采取自底向上、自顶向下以及混合遍历的方式；二、在搜索策略上采取深度优先和宽度优先策略；三、在项集的产生上着眼于是否会产生候选项集；四、在数据库的布局上，从垂直和水平两个方向上考虑数据库的布局。对于不同的遍历方式，数据库的搜索策略和布局方式将会产生不同的方法，研究表明，没有什么挖掘算法能同时对所有的定义域和数据类型都优于其他的挖掘算法，也就是说，对于每一种相对较为优秀的算法，它都有它具体的适用场景和环境。

强关联规则：满足最小支持度和最小置信度的关联规则。

全国各地天气预报查询

上海市

云南省

云南省

云南省

云南省