一种高效的多维多层关联规则挖掘算法

关联规则是数据挖掘中一个重要的研究方向.文章提出了一种基于遗传算法的多维多层关联规则挖掘算法.算法针对现有多维多层关联规则挖掘中存在阈值定义不合理的缺点,依据多维和多层数据的共同特点,提出了一种启发式的阈值自定义方式,来提高挖掘效率和结果的准确性.实验结果证明这种算法是有效.

维普资讯 doc.docsou.com

啦 -

数据库与信息处理 带习‘习芥习习 jI s

芥

一

种高效的多维多层关联规则挖掘算法 沈国强覃征沈云斐

(清华大学软件学院，北京 10 8 ) 0 0 4 E- i:g o 1@ 1 3 c m malsu q 5 6 .o _

摘要关联规则是数据挖掘中一个重要的研究方向。文章提出了一种基于遗传算法的多雏多层关联规则挖掘算法。算 法针对现有多维多层关联规则挖掘中存在阚值定义不合理的缺点，据多维和多层数据的共同特点，出了一种启发式依提的闻值自定义方式，来提高挖掘效率和结果的准确性。实验结果证明这种算法是有效。

关键词多维多屉

关联规则遗传算法数据挖掘

中图分类号 T 3 2 P 1文章编号 10— 3 1 (0 6 1— 1 6 0文献标识码 A o 2 8 3一 2 0 )2 0 7— 3

An Ef ce t M i i g Al o ih o u td m e so a n f in n n g rt m f r M li i n i n l a d i M u tp e lv I Aso i t n Ru e li l— e e s ca i l o S e o in Qi h n S e u fi h n Gu qa g n Z e g h n Y ne (c o lo otae T ig l nv r t, ej g 1 0 8 ) S h o fSf r,s h a U ies y B in 0 4 w n l i i 0 Ab ta t Aso it n ue miig s ey mp ra t n h a piain f aa sr c: scai rls o nn i v r i otn i te p l t o d t miigI ti a e。 meh d f c o nn . n hs p ra p to o miig mut—i n in l n l—e e scain nn lidme so a a d mut - v lAso it Rue wa r p sd b sd o te e ei lo tm. u owad— il o l s p o oe ae n h g n t ag r h I p t fr r c i t a h u si s r d f e to w ih a e n h o e r t u e— e n d meh d. h c b s d o te c mmo h r ce si f mut- i n in l An l— e e aa, i c i n c a a tr t

o l d me s a d mu t l v l t i c i o i d

t v ro h rwb c s c u e y te u rao a l meh d o e nn h eh l .o te rcs n n e ce c o o o ee me te d a a k a s d b h n e sn be to f d f ig t rsodS h pe ii a d f in y f i o i miig so it n ue i mp v dT e x e me tl eut s o ta te fce c o te lo tm fr ag nn as cai rls s o i r e,h e p r na rs l o i s h w h t h e in y f h ag r h i i o lre d tb s s aa a e. Ke wo d:mu t i n in n l p e lv l a s c ain r l, e e i l o t m, t nn y rs l d me s a a d mu t l - e e, s o it e G n t A g r h Daa Mi i g i ol i o u c i

1引言 自从 RA r a等人提出 A r r算法以来。联规则挖掘 .ga l w pi i o关

遗传算法设计了多维多层关联规则挖掘算法。过实验证明了通其有良好的性能。

已成为 K D中一个重要的研究领域。按照关联规则挖掘的不 D 同划分标准 .以分为维内、维关联规则挖掘，层、层关可多单多

2问题描述和分析 21问题描述 . 多维在关系数据库和数据仓库中是指不同的属性维，多层

联规则挖掘。大多数研究者对于维内。层关联规则挖掘算法单

研究的相对较多。但是，近年人们对于关系数据库或数据仓库中存储的具有大规模、多维、多层特性关联规则挖掘的应用需 求在日益增强。

是指挖掘的规则中的涉及不同的概念层次。,,,, l _ i… i是 维的集合，维多层关联规则可以表示成形如 X. x… AX= 多 A > y^y^.^y的蕴涵式，和 y分别表示为由不同维组成，, . .

在已有研究中，文献【 l2分别提出了一种同层和交叉层 l、 1[规则的挖掘算法，文献【】 3提出了一种多维规则挖掘算法。而对 于这些多维多层挖掘算法 .遍采用了人工自定义不同层和不普同维阈值的

方式 .对经典的 A r r算法进行了改进。当维和并 pi i o 层较多的时候。要人工定义大量的阈值，需随意性较大，且由并 于算法的复杂度增加，索空间、储空间、搜存运行时间也将大量

的规则合取范式构成的逻辑公式，和 y属于不同维的不同 . 概念层次，记为：> , y, ny咖。所有的记录构简= y,,, =成了一个数据库 D。 定义 1如果 D中数据同时满足和 y的百分比为|称 s,规则= y具有支持度 (u pr)。> S po S t定义 2如果 D中满足的数据中有百分比为 C的数据

增加。遗传算法是近年发展起来的一种模拟生物进化算法，它具有的良好全局搜索能力、强鲁棒性、隐并行性等特点，对处理大规模数据、组合优化、机器学习等方面有很好的表现。本文总 结了多维多层关联规则的特点，用不同层和不同维取值多少利

同时满足 y,称规则= y在数据库 D中的置信度 ( of> C nl - dn e为 C ec)。

这个先验知识。出了一种启发式的阈值自定义方法，提并基于 基金项目：国家 8 3 6高技术研究发展计划资助项目(编号： 0 A 4 2 2 ) 2 3 A 10 0 0

由用户设定两个阈值：摄小支持度和最小可信度，凡是满

作者简介：国强，。沈男硕士研究生，研究方向为数据挖掘。能决策系统。覃征，智教授，导。博研究方向为数据挖掘，移动计算，电子商务。沈云斐，

男，硕士研究生，研究方向为数据挖掘，计算机网络。

14 2 0 .计算机工程与应用 7 0 61 2

第1页