一、介绍

假如，我们手中有一个顾客在商场中购买物品交易记录的数据库。我们如何通过这个数据库，找出一些规则，再通过一些方法，让这些规则被顾客接受，促使他们在商场中购买更多的商品？、

就像很早以前所说的——啤酒与尿布

二、几个基本概念

2.1项集(Items)

在商场中购物，我们看到的所有商品。例如：Bread, Milk, Chocolate, Butter… 它们组成的集合就称为项集，我们可以用符号 I 表示。其中的每一样商品被称作项，用符号 Ii 表示。

2.2事务(Transaction)

事务其实就是项集的一个非空子集。形象地理解就是，顾客在商场购买完商品之后的小票。每一张小票对应着一个Transaction，通常我们用符号 T 表示。所以，T={ia,ib,ic...}。 千万注意： T 一定是非空的。

2.3数据库(Databases)

一个数据库包含着所有事务,用符号D表示，同时 T∈D

2.4关联规则(association rule)

P⇒Q  where  P⊂I,Q⊂I  and  P∩Q=∅

根据公式，我们可以知道，关联规则，就是找到一种关系。

用商场中的例子来说就是买了牛奶、面包的人，会去买黄油、果酱。这就是关联规则。

2.5支持度

其实就是一个频率，假如，我们手上同时有8个客户的购物小票，其中有3个客户购买了Butter。那么，我们称 Support(Butter)=38

另外，通常对于关联规则的的支持度，我们如下定义：

Support(X→Y)=#(X∪Y)n

2.6置信度

置信度可以看做条件概率。也就是在同时购买 X 的条件下，购买Y的概率，就是置信度。也就是我们的信心，再通俗一些的说就是，我们有多大的信心，在一个人买了面包的情况下，去购买牛奶。

Confidence(X→Y)=#(X∪Y)#(X)

2.7频繁项集和强规则

我们先给定一个支持度和置信度的最小阈值：

Minimum support θ Minimum confidence ϕ

一个频繁项集就是一个支持度大于 θ 的项集。

一个强规则就是频繁项集中置信度大于 ϕ 的的规则。

最后，关于关联规则的问题，用一句形容就是：

Given I,D,σ  and  Φ,to find all strong rules in the form of X→Y.

三、Apriori算法

Apriori算法的核心思想就是2句话：

A subset of a frequent itemset must be frequent. 任何一个频繁项的非空子集必须是频繁的。 {Milk, Bread, Coke} is frequent ⇒ {Milk, Coke} is frequent

The supersets of any infrequent itemset cannot be frequent. 任何一个非频繁项的超集（父类）不可能使频繁的。 {Battery} is infrequent  {Milk, Battery} is infrequent

伪算法：

例子：

四、Reference

清华大学袁博老师《数据挖掘：理论与算法》课程：http://www.xuetangx.com/courses/course-v1:TsinghuaX+80240372X+2016_T2/about

Python Implementation of Apriori Algorithm https://github.com/asaini/Apriori