第
35
卷第
7
期
Vol
.3
5 No.7
计算机工程
Computer Engineering
2009
年
4
月
April 2009
·软件技术与数据库·
文章编号
100
←
-3428(2009)07
-ø
078
-ø
4
文献标识码
A
中固分类号:
TP30
1.
6
基于二进制的约束性关联规则挖掘算法
方刚
(重庆三峡学院数学与计算机科学学院，万州
404000)
摘
要:提出一种基于二进制的约束性关联规则挖掘算法，用数字区间确定候选频繁项的范围，通过数值的递增/减方式交叉产生候选项，
利用二进制的逻辑操作计算支持数，并用数字特征减少扫描事务数，以提取满足约束条件的关联规则。该算法适于挖掘任何长度的约束性
频繁项目集，且具有较高的运算效率。
关键词:关联规则;约束条件;交叉搜索;数字特征;二进制
Constrained Association Rules Mining Algorithm ßased on ßinary
FANGGang
(College of Mathematics & Computer Science, Chongqing Three Gorges
Univ
巳
rsity
，
Wanzhou 404000)
IAbstract)
An
Algorithm of Constrained Association Rules Mining Based on Binary(ACARMB) is
present
巳
d
，
which uses digital section
to
ascertain rang of candidate frequent items that can crosswise
gen
巳
rate
candidate items
by
the methods about digital ascending and descending,
computes
suppo
口
by
binary logic operation and uses digital character
to
reduc
巳
the
number of scanned transactions, and extracts association rules
satisfied with Constrained Condition(CC). This algorithm
is
suitable for mining
any
length frequent
it
巳
m
sets, and has higher
e
仔
iciency
for
calculation.
IKey
words)
association rules;
Constrain
巳
d
Condition(CC); crossing search; digital character; binary
1
概述
目前，约束性关联规则挖掘算法有
MultipleJoins
l11
，
Reorder
l11
,
Directer
l11
,
Separat
巳
[21
MCARl
坷，
DAMICFP
和
DCAR
l41
等，其中
，
Separate
不适于挖掘较长的频繁项目集;
MCAR
l31
虽减少了扫描数据库的次数，但产生候选项的方式
与
Separate
类似
DAMICFP
是分布式约束性挖掘算沽，产
生候选项的方式较为复杂
DCAR
l41
产生候选项的函数
ReordecGen[4
1
与
Apriori-Gen
类似。这些算法虽减少了候选
项的个数和扫描事务数据库的次数，但不能快速产生候选项
和计算项目集的支持度，这使基于二进制的关联规则挖掘算
法应运而生
[5-61
。这类算法在产生候选项和计算支持数时，采
用二进制逻辑运算，能够快速计算和减少扫描次数，但算法
B-Apriori[5
1
策略叉基于
Apriori
思想，算法
Armab[61
在用事务
真子集产生候选项时，存在冗余候选项和计算。若这些算法
被用于约束性关联规则挖掘中，其效率受到影响，因此，本
文提出一种基于二进制的约束性关联规则挖掘算法
(Algorithm
of
Constrained
Association
Rules
Mining
Bas
巳
d
on
Binary
,
ACARMB)
。
2
基于二进制的约束性关联规则挖掘算法
2.1
相关定义及性质
设
I={il
，
i2
，...，
im}
是所有项目的集合，其中
，
i
k
EI(k=I ,2
,..,
m)
均转换成布尔量。
定义
1
约束条件
(Constrained
Condition
,
CC)
是由用户指
定的项目
i
k
E l(k=
1
，
2
，…
，
m)
构成的子集
CC
，即
i
k1
八
i
k2
^
...八
ikn (i kn
εη
，且
CCCI
，
把子集
CC
称为约束条件。
定义
2
二进制事务
(Binary
Transaction,
BT)
是个用二进
制数表示的事务。二进制数的位数由项目集的个数确定，项
目与二进制位一一对应，二进制事务表示为
BT=(b
1
b
2
…
b
m
)
。
举例:
I={
1
，
2
，
3
人町，若一个事务
T
j
为
{1
，
3
，
4
}，则
BT
j
=
(1
01
1O)
。
一
78
一
定义
3
数字事务
(Digital
Transaction
,
DT)
是个用整数表
示的事务，该值为二进制事务转换成整数的值。举例:若
一个二进制事务为
BT
j
=(
lO
11
0)
，则
DT
j
=22
。
定义
4
数字项目
(Digital
Item
,
DI)
是个用整数表示的事
务项目，该值只能是
2
1
(t=0
，
1
，..，
m-l)
，
m
为项目个数。举例:
若一个数据库中转换为布尔量后项目个数为
5
个，则数字项
目应为
D1l
= 1,
Dl
2
=2
,
Dl
3
=4
,
Dl
4
=8
,
Dl
5
=
16
。
定义
5
约束数字
(Constrained
Digital,
CD)
是表示约束条
件的数字事务。
定义
6
数字事务支持关系
(Digital
Transaction
Support
Relation
,
DTSR)
，若事务满足
DTm&DT
，，
=DT
m
，
则称
DT
，
巩"支持
DT
II
川
F
的子集。
定义
7
频繁数字事务
(Frequent
Digital
Transaction
,
FDT)
，指支持度大于最小支持度的数字事务。
定义
8
候选数字事务区间
(Candidate
Digital
Transaction
Section
,
CDTS)
是个整数区间，其包含所有可能成为频繁数字
事务的候选数字，且支持约束数字;其中最大值为
max{DT
b
DT
2
,..
,
DT
b
...
}
，且
CD
Ç，
DT
k
，
DT
k
不为数字项目，记为
[CD
，
max]
。
性质
1
若
DT
p
对应的事务为
T
p
，
DT
q
对应的事务为鸟，
那么
Tp
Ç，
T
q
的充要条件是
DTp&DTq=DT
p
。
推论
1
若
BT
p
的数字事务为
D
鸟
，
BT
q
的数字事务为
DT
q
，
BTp&BTq=BT
p
，
那么
DT
p
ζ
DT
q
。
推论
2
若事务
T
p
的数字事务为
DT
p
，
事务
T
q
的数字事
作者俯介
E
方刚
(1978
一)
，男，讲师、硕士研究生，主研方向:数
据挖掘，数据库，
GIS
收稿日期
2008-10-09
E-mail:
cqwzj
句
fg@163.com
资源评论
