关联规则发现最初的形式是货蓝分析，通过货蓝分析发现顾客的购买习惯，帮助零售商制定销售策略。

关联规则领域有两个颇具影响力的算法，Apriori算法和FP-Growth 算法。

相关的内容可以参考推荐系统：关联规则(1)、推荐系统：关联规则(2)和推荐系统：关联规则(3)。在我写这个话题的时候clickstone还没有发布推荐系统：关联规则(3)。他是我认识的推荐系统领域的大牛，呵呵！

我下面涉及的内容基于Apriori算法，详细内容可参考Fast Algorithms for Mining Association Rules。

首先让我来做一个假设有10个人到超市购买自己需要的商品，形成了10个事务记录，如下(其中用A、B等大写字母代表不同的商品)：

事务ID	商品列表
1	A,B,C
2	A,C,D
3	C,D,E
4	A,B,C,E
5	B,D,E
6	B,C,D
7	A,B
8	B,C,D,E
9	B,C,E
10	A,C,E

从商品列表中我们很容易发现这10个事务记录中只涉及到5中商品，分别是A,B,C,D和E。

下面通过Apriori算法寻找频繁集的过程，其中省略了概念的介绍，如果有疑问可以参考上面给出的关于Apriori算法的资料。

我们取最小支持度(min support)为0.5，从而最小支持数(support count)为0.5x10=5。

C1为(C1是一个候选集，其定义可以查阅Apriori算法的相关资料，以后涉及到的其它概念同，不再赘述)：

itemset

{A}

{B}

{C}

{D}

{E}

通过扫描事务记录集计算支持数后有：

itemset	support count
{A}	5
{B}	7
{C}	8
{D}	5
{E}	6

依据最小支持数过滤后形成的L1为：

itemset	support count
{A}	5
{B}	7
{C}	8
{D}	5
{E}	6

L1链接产生C2为：(计算了支持数)

itemset	support count
{A,B}	3
{A,C}	4
{A,D}	1
{A,E}	2
{B,C}	5
{B,D}	3
{B,E}	4
{C,D}	4
{C,E}	5
{D,E}	3

依据最小支持数过滤后形成的L2为：

itemset	support count
{B,C}	5
{C,E}	5

L2链接产生C3为：

itemset

空

因为C3为空所以算法结束，我们找到了所有的频繁集L1和L2。至此我们完成了Apriori算法的最关键的部分：找出所有满足最小支持度的所有频繁集。下面我们来完成 Apriori算法的另一部分：找出满足最小可信度的所有关联规则。

我们以L2中的频繁集{B,C}为例来描述这个过程，假设最小可信度为70%。

B=>C的可信度为{B,C}的支持数/{B}的支持数，即5/7，约为71.4%

C=>B的可信度为{B,C}的支持数/{C}的支持数，即5/8，为62.5%

注意：这两个结果和我们对10个事务记录的初步观察感觉是一致的，即购买了商品B的顾客多半也会购买商品C，购买了商品C的顾客也会购买商品B，但是后者的比率比前者要少一些。如果事务记录数比较大的话我们就不可能通过观察来得到对关联规则的一些感觉了，这时必须依靠算法。

与最小可信度70%相比只有B=>C满足要求，所以我们得到关联规则B=>C。

这个规则告诉我们有7成以上购买商品B的顾客会同时购买商品C。