MADlib——基于SQL的数据挖掘解决方案（27）——关联规则之Apriori算法
MADlib——基于SQL的数据挖掘解决方案（27）——关联规则之Apriori算法
数据仓库或数据挖掘从业者一定对“啤酒与尿布”的故事不会陌生。这就是一个使用关联规则的经典案例。根据对超市顾客购买行为的数据挖掘发现，男顾客经常一起购买啤酒和尿布，于是经理决定将啤酒与尿布放置在一起，让顾客很容易在货架上看到，从而使销售额大幅度增长。关联规则挖掘在多个领域得到了广泛应用，包括互联网数据分析、生物工程、电信和保险业的错误校验等。本篇将介绍关联规则方法、Apriori算法和MADlib的Apriori相关函数。之后我们用一个示例说明如何使用MADlib的Apriori函数发现关联规则。
一、关联规则简介
关联规则挖掘的目标是发现数据项集之间的关联关系，是数据挖据中一个重要的课题。关联规则最初是针对购物篮分析（Market Basket Analysis）问题提出的。假设超市经理想更多地了解顾客的购物习惯，特别是想知道，哪些商品顾客可能会在一次购物时同时购买？为回答该问题，可以对商店的顾客购买记录进行购物篮分析。该过程通过发现顾客放入“购物篮”中的不同商品之间的关联，分析顾客的购物习惯。这种关联的发现可以帮助零售商了解哪些商品频繁地被顾客同时购买，从而帮助他们开发更好的营销策略。
为了对顾客的购物篮进行分析，1993年，Agrawal等首先提出关联规则的概念，同时给出了相应的挖掘算法AIS，但是性能较差。1994年，又提出了著名的Apriori算法，至今仍然作为关联规则挖掘的经典算法被广泛讨论。
Apriori数据挖掘算法使用事务数据。每个事务事件都具有唯一标识，事务由一组项目（或项集）组成。购买行为被认为是一个布尔值（买或不买），这种实现不考虑每个项目的购买数量。MADlib的关联规则函数假设数据存储在事务ID与项目两列中。具有多个项的事务将扩展为多行，每行一项目，如：
trans_id | product
---------+---------
1 | 1
1 | 2
1 | 3
1 | 4
2 | 3
2 | 4
2 | 5
3 | 1
3 | 4
3 | 6
…关联规则挖掘涉及以下一些基本概念。
（1）项目与项集
数据库中不可分割的最小单位信息，称为项目，用符号i表示。项目的集合称为项集。设集合I={i1,i2,...ik}是项集，I中项目的个数为k，则集合I称为k-项集。例如，集合{啤酒,尿布,牛奶}是一个3-项集。
（2）事务
设I={i1,i2,...ik}是由数据库中所有项目构成的集合，一次处理所含项目的集合用T表示，T={t1,t2,...tn}。每个ti包含的项集都是I的子集。例如，如果顾客在商场里同一次购买多种商品，这些购物信息在数据库中有一个唯一的标识，用以表示这些商品是同一顾客同一次购买的。称该用户的本次购物活动对应一个数据库事务。
（3）关联规则
关联规则是形如X=>Y的蕴含式，意思是“如果X则Y”，其中X、Y都是I的子集，且X与Y交集为空。X、Y分别称为规则的前提和结果，或者规则的左、右。关联规则反映X中的项目出现时，Y中的项目也跟着出现的规律。
（4）项集的频数（Count）
对于任何给定的项集X，包含X的事务数，称为X的频数。
（5）支持度（Support）
包含项集X的事务数与总事务数之比，称为X的支持度，记为：
（6）关联规则的支持度
关联规则的支持度是事务集中同时包含X和Y的事务数与所有事务数之比，其实也就是两个项集{X Y}出现在事务库中的频率，记为：
（7）关联规则的置信度（Confidence）
关联规则的置信度是事务集中包含X和Y的事务数与所有包含X的事务数之比，也就是当项集X出现时，项集Y同时出现的概率，记为：
（8）关联规则的提升度（Lift）
提升度表示含有X的条件下，同时含有Y的概率，与不含X的条件下却含有Y的概率之比。这个值越大，越表明X和Y有较强的关联度。关联规则的提升度定义为：
（9）关联规则的确信度（Conviction）
确信度表示X出现而Y不出现的概率，也就是规则预测错误的概率。确信度也用来衡量X和Y的独立性，这个值越大，X、Y越关联。关联规则的确信度定义为：
（10）最小支持度与最小置信度
通常用户为了达到一定的要求，需要指定规则必须满足的支持度和置信度阈值，当support(X=>Y)、confidence(X=>Y)分别大于等于各自的阈值时，认为X=>Y是有趣的，此两个值称为最小支持度阈值（min_sup）和最小置信度阈值（min_conf）。其中，min_sup描述了关联规则的最低重要程度，min_conf规定了关联规则必须满足的最低可靠性。
（11）频繁项集
设U={u1,u2,...,un}为项目的集合，且U⊆I，U≠∅，对于给定的最小支持度min_sup，如果项集U的支持度support(U)>=min_sup，则称U为频繁项集，否则U为非频繁项集。
（12）强关联规则
support(X=>Y)>=min_sup且confidence(X=>Y)>=min_conf，称关联规则X=>Y为强关联规则，否则称X=>Y为弱关联规则。
下面用一个简单的例子来帮助理解这些定义。假设表1是顾客购买记录的数据库D，包含6个事务。
TID | 网球拍 | 网球 | 运动鞋 | 羽毛球 |
|---|---|---|---|---|
1 | 1 | 1 | 1 | 0 |
2 | 1 | 1 | 0 | 0 |
3 | 1 | 0 | 0 | 0 |
4 | 1 | 0 | 1 | 0 |
5 | 0 | 1 | 1 | 1 |
6 | 1 | 1 | 0 | 0 |
表1 购买事务记录
项集I={网球拍,网球,运动鞋,羽毛球}。考虑关联规则：网球拍=>网球，事务1、2、3、4、6包含网球拍，事务1、2、6同时包含网球拍和网球，支持度support=3/6，置信度confidence=3/5，提升度lift=(3/6)/((5/6)*(4/6))=9/10，确信度conviction=(1-4/6)/(1-3/5)=5/6。若给定最小支持度α=0.5，最小置信度β=0.5，关联规则网球拍=>网球是有趣的，认为购买网球拍和购买网球之间存在强关联规则。但是，由于提升度Lift小于1，就是说是否够购买网球，与有没有购买网球拍关联性很小。当提升度Lift(X=>Y)>1时，则规则“X=>Y”是有效的强关联规则。否则，规则“X=>Y”是无效的强关联规则。特别地，如果Lift(X=>Y)=1，则表示X与Y相互独立。因此规则网球拍=>网球是无效的强关联规则。
二、Apriori算法
1. Apriori算法基本思想
关联规则挖掘分为两步：1. 找出所有频繁项集；2.由频繁项集产生强关联规则。其总体性能由第一步决定。在搜索频繁项集时，最简单、最基本的算法就是Apriori算法。算法的名字基于这样一个事实：使用频繁项集的先验知识。Apriori使用一种被称作逐层搜索的迭代方法，k项集用于搜索（k+1）项集。首先，通过扫描数据库，积累每个项目的计数，并收集满足最小支持度的项目，找出频繁1项集的集合。该集合记作L1。然后，L1用于找频繁2项集的集合L2，L2用于找L3，如此下去，直到不能再找到频繁k项集。找每个Lk需要一次数据库全扫描。
Apriori核心算法思想中有两个关键步骤：连接和剪枝。
（1）连接
为找出Lk（频繁k项集），通过Lk-1与自身连接，产生候选k项集，该候选项集记作Ck；其中Lk-1的元素是可连接的。
（2）剪枝
Ck是Lk的超集，即它的成员可以是也可以不是频繁的，但所有的频繁项集都包含在Ck中。扫描数据库，确定Ck中每一个候选项的计数，从而确定Lk（计数值不小于最小支持度计数的所有候选是频繁的，从而属于Lk）。然而，Ck可能很大，这样所涉及的计算量就很大。为了压缩Ck，使用Apriori性质：任一频繁项集的所有非空子集也必须是频繁的，反之，如果某个候选的非空子集不是频繁的，那么该候选肯定不是频繁的，从而可以将其从Ck中删除。例如，如果{A,B,C}是一个3项的频繁项集，则其子集{A,B}、{B,C}、{A,C}也一定是2项的频繁项集。剪枝事先对候选集进行过滤，以减少访问外存的次数，而这种子集测试本身可以使用所有频繁项集的散列树快速完成。
2. Apriori算法步骤
假设给定最小支持度和最小置信度，Apriori算法的主要步骤如下：
- 扫描全部数据，产生候选1-项集的集合C1；
- 根据最小支持度，由候选1-项集集合C1产生频繁1-项集的集合L1；
- 对k>1，重复执行步骤4、5、6；
- 由Lk执行连接和剪枝操作，产生候选（k+1）-项集的集合Ck+1；
- 根据最小支持度，由候选（k+1）-项集的集合Ck+1，产生频繁（k+1）-项集的集合Lk+1；
- 若L≠∅，则k=k+1，跳往步骤（4）；否则跳往步骤（7）；
- 设产生的频繁项集为A，A的所有真子集为B，根据最小置信度，产生B=>（A-B）的强关联规则，结束。
三、MADlib的Apriori算法函数
MADlib的assoc_rules函数实现Apriori算法，用于生成所有满足给定最小支持度和最小置信度的关联规则。
（1）语法
assoc_rules (support,
confidence,
tid_col,
item_col,
input_table,
output_schema,
verbose,
max_itemset_size );（2）参数
参数名称 | 数据类型 | 描述 |
|---|---|---|
support | DOUBLE PRECISION | 最小支持度。 |
confidence | DOUBLE PRECISION | 最小置信度。 |
tid_col | TEXT | 事务ID列名。 |
item_col | TEXT | 项目对应的列名。 |
input_table | TEXT | 包含输入数据的表名。 |
output_schema | TEXT | 存储最终结果的模式名称，调用函数前，模式必须已创建。如果此参数为NULL，则输出到当前模式。 |
verbose | BOOLEAN | 缺省为false，指示是否详细打印算法过程中每次迭代的结果。 |
max_itemset_size | INTEGER | 该参数值必须大于等于2，指定用于产生关联规则的频繁项集的大小，缺省值是产生全部项集。当项集太大时，可用此参数限制数据集的大小，以减少运行时长。 |
表2 assoc_rules函数参数说明
说明：
- 输入表的结构为：
{TABLE|VIEW} input_table (
trans_id INTEGER,
product TEXT ) assoc_rules算法将产品名称映射到从1开始的连续的整型事务ID上。如果输入数据本身已经结构化为这种形式，则事务ID保持不变。
- 结果存储在输出模式中的assoc_rules表中，具有以下列：
Column | Type
-----------+------------------
ruleid | integer
pre | text[]
post | text[]
count | integer
support | double precision
confidence | double precision
lift | double precision
conviction | double precision在HAWQ中，assoc_rules表通过ruleid列哈希分布存储。pre和post列分别是相应关联规则的左右项集。count、support、confidence、lift和conviction列分别对应关联规则的频数、支持度、置信度、提升度和确信度。
四、Apriori应用示例
我们就用“啤酒与尿布”的经典示例，人为模拟一些购买记录作为输入数据，然后调用madlib.assoc_rules函数生成关联规则。我们将对比控制台的打印信息，一步步说明该函数获取关联规则的计算过程，并对最终结果进行分析。
1. 创建输入数据集
drop table if exists test_data;
create table test_data (
trans_id int,
product text
);
insert into test_data values
(1, 'beer'), (1, 'diapers'), (1, 'chips'),
(2, 'beer'), (2, 'diapers'),
(3, 'beer'), (3, 'diapers'),
(4, 'beer'), (4, 'chips'),
(5, 'beer'),
(6, 'beer'), (6, 'diapers'), (6, 'chips'),
(7, 'beer'), (7, 'diapers');2. 调用madlib.assoc_rules函数生成关联规则
设置最小支持度min(support) = 0.25，最小置信度min(confidence) =0.5。输出模式设置为NULL，输出到当前模式。verbose设置为TRUE，这样就能观察和验证函数执行的过程。
select * from madlib.assoc_rules
( .25, -- 最小支持度
.5, -- 最小置信度
'trans_id', -- 事务ID列名
'product', -- 产品列名
'test_data', -- 输入数据表
null, -- 在当前模式创建输出表
true -- 打印详细信息
);控制台打印的输出信息如下：
INFO: finished checking parameters
CONTEXT: PL/Python function "assoc_rules"
INFO: finished removing duplicates
CONTEXT: PL/Python function "assoc_rules"
INFO: finished encoding items
CONTEXT: PL/Python function "assoc_rules"
INFO: finished encoding input table: 4.55814695358
CONTEXT: PL/Python function "assoc_rules"
INFO: Beginning iteration #1
CONTEXT: PL/Python function "assoc_rules"
INFO: 3 Frequent itemsets found in this iteration
CONTEXT: PL/Python function "assoc_rules"
INFO: Completed iteration # 1. Time: 0.756361961365
CONTEXT: PL/Python function "assoc_rules"
INFO: Beginning iteration # 2
CONTEXT: PL/Python function "assoc_rules"
INFO: time of preparing data: 0.784854888916
CONTEXT: PL/Python function "assoc_rules"
INFO: 3 Frequent itemsets found in this iteration
CONTEXT: PL/Python function "assoc_rules"
INFO: Completed iteration # 2. Time: 1.89147591591
CONTEXT: PL/Python function "assoc_rules"
INFO: Beginning iteration # 3
CONTEXT: PL/Python function "assoc_rules"
INFO: time of preparing data: 0.577459096909
CONTEXT: PL/Python function "assoc_rules"
INFO: 1 Frequent itemsets found in this iteration
CONTEXT: PL/Python function "assoc_rules"
INFO: Completed iteration # 3. Time: 1.32646298409
CONTEXT: PL/Python function "assoc_rules"
INFO: Beginning iteration # 4
CONTEXT: PL/Python function "assoc_rules"
INFO: time of preparing data: 0.31945681572
CONTEXT: PL/Python function "assoc_rules"
INFO: 0 Frequent itemsets found in this iteration
CONTEXT: PL/Python function "assoc_rules"
INFO: Completed iteration # 4. Time: 0.751129865646
CONTEXT: PL/Python function "assoc_rules"
INFO: begin to generate the final rules
CONTEXT: PL/Python function "assoc_rules"
INFO: 7 Total association rules found. Time: 1.1944539547
CONTEXT: PL/Python function "assoc_rules"
output_schema | output_table | total_rules | total_time
---------------+--------------+-------------+-----------------
public | assoc_rules | 7 | 00:00:10.566625
(1 row)madlib.assoc_rule函数产生频繁项集及关联规则的过程如下：
（1）验证参数、去除重复数据、对输入数据编码（生成从1开始的连续的事务ID，本例原始数据已经满足要求，因此不需要编码）。
（2）首次迭代，生成所有支持度大于等于0.25的1阶项集作为初始项集，如表3所示。因为三个1阶项集的支持度都大于0.25，所以初始项集包含所有三个项集。
项集 | 频数 | 支持度 |
|---|---|---|
beer | 7 | 7/7 |
diapers | 5 | 5/7 |
chips | 3 | 3/7 |
表3 1阶项集
（3）最大阶数为3，因此开始第二次迭代。迭代结果的频繁项集如表4所示。因为三个2阶项集的支持度都大于0.25，所以本次迭代结果的频繁项集包含所有三个项集。
项集 | 频数 | 支持度 |
|---|---|---|
beer, diapers | 5 | 5/7 |
beer, chips | 3 | 3/7 |
diapers，chips | 2 | 2/7 |
表4 2阶项集
（4）第三次迭代，得到的频繁项集如表5所示。因为唯一一个3阶项集的支持度大于0.25，所以本次迭代结果的频繁项集包含一个项集。
项集 | 频数 | 支持度 |
|---|---|---|
beer, diapers, chips | 2 | 2/7 |
表5 3阶项集
（5）第四次迭代，因为阶数为3，本次迭代的结果为空集。
（6）产生关联规则，置信度大于等于0.5的关联规则如表6中粗体行所示。
前提 | 结果 | 支持度 | 置信度 |
|---|---|---|---|
beer | diapers | 5/7=0.71428571 | (5/7)/(7/7)= 0.71428571 |
diapers | beer | 5/7=0.71428571 | (5/7)/(5/7)=1 |
beer | chips | 3/7=0.42857143 | (3/7)/(7/7)= 0.42857143 |
chips | beer | 3/7=0.42857142 | (3/7)/(3/7)=1 |
diapers | chips | 2/7=0.28571429 | (2/7)/(5/7)=0.4 |
chips | diapers | 2/7=0.28571429 | (2/7)/(3/7)=0.66666667 |
beer | diapers, chips | 2/7=0.28571429 | (2/7)/(7/7)= 0.28571429 |
beer，diapers | chips | 2/7=0.28571429 | (2/7)/(5/7)=0.4 |
beer，chips | diapers | 2/7=0.28571429 | (2/7)/(3/7)= 0.66666667 |
diapers | beer，chips | 2/7=0.28571429 | (2/7)/(5/7)=0.4 |
diapers，chips | beer | 2/7=0.28571429 | (2/7)/(2/7)=1 |
chips | beer, diapers | 2/7=0.28571429 | (2/7)/(3/7)= 0.66666667 |
表6 关联规则
关联规则存储在assoc_rules表中，查询结果与表6所反映的相同：
dm=# select ruleid id,
dm-# pre,
dm-# post,
dm-# count c,
dm-# round(support::numeric,4) sup,
dm-# round(confidence::numeric,4) conf,
dm-# round(lift::numeric,4) lift,
dm-# round(conviction::numeric,4) conv
dm-# from assoc_rules
dm-# order by support desc, confidence desc;
id | pre | post | c | sup | conf | lift | conv
----+-----------------+----------------+---+--------+--------+--------+--------
4 | {diapers} | {beer} | 5 | 0.7143 | 1.0000 | 1.0000 | 0.0000
2 | {beer} | {diapers} | 5 | 0.7143 | 0.7143 | 1.0000 | 1.0000
3 | {chips} | {beer} | 3 | 0.4286 | 1.0000 | 1.0000 | 0.0000
5 | {diapers,chips} | {beer} | 2 | 0.2857 | 1.0000 | 1.0000 | 0.0000
1 | {chips} | {diapers} | 2 | 0.2857 | 0.6667 | 0.9333 | 0.8571
7 | {chips} | {diapers,beer} | 2 | 0.2857 | 0.6667 | 0.9333 | 0.8571
6 | {beer,chips} | {diapers} | 2 | 0.2857 | 0.6667 | 0.9333 | 0.8571
(7 rows)3．限制生成关联规则的项集大小为2，再次执行madlib.assoc_rules函数
注意，madlib.assoc_rules函数总会新创建assoc_rules表。如果要保留多个关联规则表，需要在运行函数前备份已存在的assoc_rules表。
select * from madlib.assoc_rules
( .25, -- 最小支持度
.5, -- 最小置信度
'trans_id', -- 事务ID列名
'product', -- 产品列名
'test_data', -- 输入数据表
null, -- 在当前模式创建输出表
true, -- 打印详细信息
2 -- 最大项集数
);这次生成的关联规则如下：
dm=# select ruleid id,
dm-# pre,
dm-# post,
dm-# count c,
dm-# round(support::numeric,4) sup,
dm-# round(confidence::numeric,4) conf,
dm-# round(lift::numeric,4) lift,
dm-# round(conviction::numeric,4) conv
dm-# from assoc_rules
dm-# order by support desc, confidence desc;
id | pre | post | c | sup | conf | lift | conv
----+-----------+-----------+---+--------+--------+--------+--------
4 | {diapers} | {beer} | 5 | 0.7143 | 1.0000 | 1.0000 | 0.0000
2 | {beer} | {diapers} | 5 | 0.7143 | 0.7143 | 1.0000 | 1.0000
3 | {chips} | {beer} | 3 | 0.4286 | 1.0000 | 1.0000 | 0.0000
1 | {chips} | {diapers} | 2 | 0.2857 | 0.6667 | 0.9333 | 0.8571
(4 rows)4. 按需过滤关联规则
例如，如果想得到规则左端项集只有一个项目，并且规则右端项集为‘beer’:
dm=# select ruleid, pre, post, count c, round(support::numeric,4) sup,
dm-# confidence, lift, conviction
dm-# from assoc_rules
dm-# where array_upper(pre,1) = 1 and post = array['beer'];
ruleid | pre | post | c | sup | confidence | lift | conviction
--------+-----------+--------+---+--------+------------+------+------------
3 | {chips} | {beer} | 3 | 0.4286 | 1 | 1 | 0
4 | {diapers} | {beer} | 5 | 0.7143 | 1 | 1 | 0
(2 rows)5. 分析关联规则
madlib.assoc_rules函数是根据用户设置的支持度与置信度阈值生成关联规则的。我们以支持度和置信度阈值限制得到了7个关联规则，但这些规则的有效性如何呢？ 前面提到，满足最小支持度和最小置信度的规则，叫做“强关联规则”。然而，强关联规则里，也分有效的强关联规则和无效的强关联规则。
从提升度来看，提升度大于1，则规则是有效的强关联规则，否则是无效的强关联规则。如果提升度=1，说明前提与结果彼此独立，没有任何关联，如果<1，说明前提与结果是相斥的。以规则5为例，提升度为0.93，说明购买了diapers的顾客就不会购买chips。因此用提升度作为度量，结果中的7个规则都是无效的。
五、小节
关联规则挖掘的目标在于发现数据项集之间的关联关系，该方法常被用于购物篮分析，著名的“啤酒与尿布”案例就是关联规则的典型应用。Apriori是关联规则挖掘的经典算法，特点是比较简单，易于理解和实现。MADlib提供的assoc_rules函数实现Apriori算法，用于生成所有满足给定最小支持度和最小置信度阈值的关联规则。使用该函数生成强关联规则后，还需要分析提升度判断其有效性。