-
关联规则基本算法及其应用
1
．关联规则挖掘
1.1
关联规则提出背景
1993
年，
Agrawal
< br>等人在首先提出关联规则概念，同时给出了相应的挖掘算法
AIS
，但
是性能较差。
1994
年
，他们建立了项目集格空间理论，并依据上述两个定理，提出了著名
的
< br>Apriori
算法，
至今
Ap
riori
仍然作为关联规则挖掘的经典算法被广泛讨论，
以后
诸多的研
究人员对关联规则的挖掘问题进行了大量的研究。
关联
规则挖掘在数据挖掘中是一个重要的
课题，最近几年已被业界所广泛研究。
关联规则最初提出的动机是针对购物篮分析
(Market
Basket
Analysis)
问
题提出的。假设
分店经理想更多的了解顾客的购物习惯（如下图）
。特别是，想知道哪些商品顾客可能会在
一次购物时同时购买？为回答该问题，
可以对商店的顾客事物零售数量进行购物篮分析。
该
< br>过程通过发现顾客放入
“购物篮”
中的不同商品之间的关
联，
分析顾客的购物习惯。
这种关
联的
发现可以帮助零售商了解哪些商品频繁的被顾客同时购买，
从而帮助他们开发更好的营<
/p>
销策略。
1.2
关联规则的基本概念
关
联
规
则
定
义
为
：
假
设
I
?
{
i
1
,
i
2
,...
i
m
}
是
项
的
集
合
，
给
定
一
个
交
易
数
据
库
D
={t
1
,t
2
,...,t
m
}
，
其中每个事务
(Transaction)t
是
I
的
非空子集，即
t
?
I
< br>，每一个交易都与
一个唯一的标识符
TID(Trans
action
ID)
对应。关联规则是形如
< br>X
?
Y
的蕴涵式，
其中
X
和
Y
分别称为关联规则的先导
(antecedent
或
left-hand-side,
LHS)
X
,Y
?
I
且
X
?
Y
?
?
，
和后
继
(consequent
或
righ
t-hand-side, RHS)
。
关联规则
X
?
Y
在
< br>D
中的支持度
(support)
是
D
中事务包含
X
< br>?
Y
的百分比，即概率
P
(
X
?
Y
)
；置信度
(confidence)
是包含
X
的事务中同
时包
含
Y
的百分比，即条件概率
P
(
Y
|
X
)
。如果满足最小支持度阈值和最小置信度阈值，
则
称关联规则是有趣的。这些阈值由用户或者专家设定。
用一个简单的例子说明。
上表是顾客购买记录的数据库
D
，
包含
6
个事务。
项集
I={
网球拍
,
网球
,
运动鞋
,
羽
毛球
}
。
考虑关联规则：
网球拍
网
球，
事务
1,2,3,4,6
包含网球拍，
事务
1,2,5,6
同时包含网球拍和
网球，
支持度
support
?
3
6
置信度
confident
?
?
0.5
，
3
5
若给定最小支持度
α = 0.5
，
?
0.6
。
最小置信度
β =
0.8
，关联规则网球拍
在关联。
网球是有趣的，认为购买网球拍和购买网球之间存
1.3
关联规则的分类
按照不同标准，关联规则可以进行分类如下：
（
1
）基于规则中处理的变量的类别，关联规则可以分
为布尔型和数值型。
布尔型关联规则处理的值都是离散的、
种类化的，
它显示了这些变量之间的关系；
而数
值型关联规则
可以和多维关联或多层关联规则结合起来，对数值型字段进行处理，将其进
行动态的分割，
或者直接对原始的数据进行处理，
当然数值型关联规则中也可以包含种类
变
量。
例如：
性别
=“<
/p>
女
”=>
职业
=
“
秘书
”
，
是布尔型关联规则；
性别
=“
女
”=>avg
（收入）
=2300
，
涉及的收入是数值类型，所以是一个数值型关联规则。
< br>
（
2
）基于规则中数据的抽象
层次，可以分为单层关联规则和多层关联规则。
在单层的关联规则中，所有的变量都没有考虑到现实的数据是
具有多个不同的层次的；
而在多层的关
联规则中，
对数据的多层性已经进行了充分的考虑。
例如：<
/p>
IBM
台式机
=>Sony
打印机，是一个细节数据上的单层关联规则；台式机
=> Sony
打印机，是一个较高层次和细
节层次之间的多层关联规则。
（
3
）基于规则中涉及到
的数据的维数，关联规则可以分为单维的和多维的。
在单维的
关联规则中，
我们只涉及到数据的一个维，
如用户购买的物品；
而在多维的关
联规则中，要
处理的数据将会涉及多个维。换成另一句话，单维关联规则是处理单个属性
中的一些关系；多维关联规则是处理各个属性之间的某些关系。例如：啤酒
=>
尿
布，这条
规则只
涉及到用户的购买的物品；
性别
=“
女
”=>
职业
=“
秘书
”
，
这条规则就涉及到两个字段
的
信息，是两个维上的一条关联规则。
2
．关联规则挖掘的相关算法
关联规则最为经典的算法是
Apriori
算
法。由于它本身有许多固有缺陷，后来的研究者
又纷纷提出了各种改进算法或者不同的算
法，频繁树（
FP-Tree
）算法应用也十分广泛。本
文将就这两种典型算法进行研究。
2.1
Apriori
算法
2.1.1
预备知识
关联规则的挖掘分为两步：
(1)
找出所有频繁项集；
(2)
由频繁项集产生强关联规则。而
其总体性能由第一步决定。
在搜索频繁项集的时候，最简单、
基本的算法就是
Apriori
算法。它是
l
和
t
于
1994
年提出的为布尔关联规则挖掘频繁项集的原创性算法。算法的名字基于这
样一个事实：算法使用频繁项集性质的先验知识。
Apriori
使用一种称作逐层搜索的迭代方
法，
k
项集用于探索（
k+1
）项集。首先，通过
扫描数据库，累积每个项的计数，并收集满
足最小支持度的项，找出频繁
1
项集的集合。该集合记作
L1
。然后，
L
1
用于找频繁
2
项集
的集合
L
2
，
L
2
用于找
L
3
，如此下去，直
到不能再找到频繁
k
项集。找每个
L<
/p>
k
需要一次数据
库全扫描。
为提高频繁项集逐层产生的效率，
一种称作
Apriori
性质的重要性质用于压缩搜索空间。
< br>Apriori
性质：频繁项集的所有非空子集也必须是频繁的。
Apriori
性质基于如下观察。根据
定义，如果项
集
I
不满足最小支持度阈值
min_s
up
，则
I
不是频繁的，即
P(I)
。如
果项
A
添加到项集
I
，则结果项
集（即
I
是频繁的，即
P(I
更频繁出现。因此，
A)
。
A
）不可能比
I
I
A
也不
2.1.2
Apriori
算法的核心思想
文献
1
中对
Apriori
核心算法思想简要描述如下：该算法中有两个关键步骤连接步和剪
枝步。
(1)
连接步：为找出
L
k
(
频繁
k
项集
)
，通过
L
k-1
与自身连接，产生候选
k
< br>项集，该候选
项集记作
C
k
；其中
L
k-1
的
元素是可连接的。
(2)
剪枝步：
C
k
是
L
k
的超集，即它的成员可以是也可以不是频繁的，但所有的频繁项<
/p>
集都包含在
C
k
中。扫描数据库，确定
C
k
中每一个候
选的计数，从而确定
L
k
(
计数值不小于
最小支持度计数的所有候选是频繁的，从而属于
L
k
)
。然而，
C
k
可能很大，这样所涉及的计
< br>算量就很大。为压缩
C
k
，使用
Apriori
性质：任何非频繁的
(
k-1)
项集都不可能是频繁
k
项集<
/p>
的子集。因此，如果一个候选
k
项集的<
/p>
(k-1)
项集不在
L
< br>k
中，则该候选项也不可能是频繁的，
从而可以由
C
k
中删除。这种子集测试可以使用所有频繁
项集的散列树快速完成。
2.1.3
Apriori
算法描述
Apriori
算法，使用逐层迭代找出频繁项集。
输入：事务数据库
D<
/p>
；最小支持度阈值
min_sup
。
输出：
D
中的频繁项集
L
。
1
）
L
1
= find_frequen
t_1_itemsets
（
D
）
；
2
）
for
（
k =
2
；
L
k-1
≠
；
k++
）
{
3
）
Ck = aproiri_gen
（
L
k-1
，
min_sup
）
；
4
）
for
each transaction t D{ //
扫描
D
用于计数
5
）
C
t
= subset
（
C
k
，
< br>t
）
；
//
得到
t
的子集，它们是候选
6
）
for
each candidate c
7
）
++
；
8
）
}
9
）
L
k
={c
10
）
}
C
t
C
k
|
≥
min_sup}
11
）
return L =
k
L
k
；
Procedure apriori_gen (L
k-1
:frequent(k-1)-itemsets)
1)
for each itemsets
l
1
L
k-1
2)
for
each itemsets
l
2
L
k-1
3)
if (l
1
[1]=l
2
[1])^ (l<
/p>
1
[2]=l
2
[2])^…^(l
1
[k-2]=l
2
[k-2])^ (l
1
<
br>L
[k-1]
2
[k-1]) then{
4)
c=l
1
l
2
;
//
连接步：产生候选
5)
if has_infrequent_subset(c,
L
k-1
) then
6)
delete c;
//
剪枝步：删除非频繁的候选
7)
else add c to
C
k
;
8)
}
9)
return C
k
;
Procedure
has_infrequent_subset (c:candidate k-itemset;L
k-1
:frequent(k-1)-itemsets)
//
使用先
验知识
1)
for each(k-1)-subset s of c
2)
If
s
3)
return TRUE;
4)
return FALSE;
L
k-1
then
2.1.4
Apriori
算法评价
基于频繁项
集的
Apriori
算法采用了逐层搜索的迭代的方法，算法简
单明了，没有复杂
的理论推导，也易于实现。但其有一些难以克服的缺点：
（
1
）对数据库的扫描次
数过多。在
Apriori
算法的描述中，我们知道，每生成一
个候选
项集，都要对数据库进行一次全面的搜索。如果要生成最大长度为
N
的频繁项集，那么就
要对数据库进行
N
次扫描。当数据库中存放大量的事务数据时，在有限的内存容量下，系
统
I/O
负载相当大，每次扫描数据库的时间
就会很长，这样其效率就非常低。
（
2
）
Apriori
算法会产生大量的
中间项集。
Apriori_gen
函数是用
k-1
产生候选
C
k
，
所产
生
C
k
由
个
< br>k
项集组成。显然，
k
越大所产
生的候选
k
项集的数量呈几何级数增加。如
频繁
1
项集的数量为
10
4
个，长度为
2
的候选
项集的数量将达到
5*10
7
个，如果
要生成一个
更长规则，其需要产生的候选项集的数量将是难以想象的，如同天文数字。<
/p>
（
3
）采用唯
一支持度，没有将各个属性重要程度的不同考虑进去。在现实生活中，一
些事务的发生非
常频繁，
而有些事务则很稀疏，
这样对挖掘来说就存在一个问题
：
如果最小
支持度阈值定得较高，
虽然
加快了速度，
但是覆盖的数据较少，
有意义的规则可能不被发现
；
如果最小支持度阈定得过低，
那么大量的无实际意义的规则将
充斥在整个挖掘过程中，
大大
降低了挖掘效率和规则的可用性。
这都将影响甚至误导决策的制定。
（
4
）算法的适应面窄。该算法只考虑了单维布尔关联规则的挖掘，但在实际应用中，
可能出现多维的、数量的、多层的关联规则。这时，该算法就不再适用，需要改进，甚至需<
/p>
要重新设计算法。
2.1.5
Apriori
算法改进
鉴于
Apriori
算法本身存在一些缺陷，在实际应用中往往不能令人感
到满意。为了提高
Apriori
算法的性能，已经有许多变种
对
Apriori
进一步改进和扩展。可以通过以下几个方面<
/p>
对
Apriori
算法进行改进：①通过
减少扫描数据库的次数改进
I/O
的性能。②改进产生频繁
项集的计算性能。③寻找有效的并行关联规则算法。④引入抽样技术改进生成频繁项集的
I/O
和计算性能。⑤扩展应用领域。如：定量关联规则、泛化关联
规则及周期性的关联规则
的研究。
目
前许多专家学者通过大量的研究工作，
提出了一些改进的算法以提高
Apriori
的效率，
简要介绍如下：
< br>
（
1
）基于抽样
(Sampling)
技术
-
-
-
-
-
-
-
-
-
上一篇：uboot编译说明
下一篇：【冷知识】几乎所有食物的英文翻译