第
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