（计算机应用技术专业论文）数据库中关联规则的提取研究.pdf

数据库中关联规则的提取研究 摘要 随着数据库的增加和数据量的不断增长，数据挖掘已成为从数据库中获取 有用知识的重要手段，其中，关联规则挖掘其中的一个重要分支，它侧重于挖 掘数据库中项集之间的关联或相关联系。根据关联规则挖掘的数据集的不同， 可以将关联规则挖掘技术分为两大类：布尔关联规则挖掘技术和量化关联规则 挖掘技术。布尔关联规则挖掘技术研究仅包含二值属性的数据集中的关联规则 挖掘；量化关联规则挖掘技术研究包含分类属性或量化属性的数据集中的关联 规则挖掘。 传统的关联规则挖掘算法及其改进算法通常用来挖掘布尔关联规则；这些 算法需多次扫描数据库，产生候选项集，并在此基础上产生用来提取关联规则 的频繁项目集。本文提出一种改进的关联规则挖掘算法，只需扫描数据库一次， 且不产生候选项目集；算法的性能较传统的关联规则挖掘算法有很大的提高。 对关系数据库应用布尔关联规则算法挖掘关联规则，是量化关联规则挖掘 技术要解决的问题。该技术的中心问题是量化属性和分类属性的离散化。在完 成了数值属性的离散化之后，量化关联规则挖掘问题就转化为布尔关联规则挖 掘问题，可以应用布尔关联规则算法来对预处理后的数据集进行挖掘。 另外，现实世界的数据库中的噪音数据干扰了数据挖掘获得真实有趣的知 识。数据预处理技术的使用使数据挖掘可以在不同层次上来获取相关知识。将 数据预处理技术应用到量化关联规则的挖掘上是本文研究的另一个问题。本文 重点讨论利用基于概念分层的离散化技术处理关系数据库，进行量化关联规则 的挖掘。 关键字：知识发现关联规则概念分层离散化 r e s e a r c ho n d i s c o v e r y o fa s s o c i a t i o nr u l e si nd a t a b a s e s a b s t r a c t w i t ht h ec o n t i n u o u si n c r e a s i n go f d a t aa n df u r t h e r m o r et h ed a t a b a s e s t h ed a t a m m m g h a sb e c o m ea ni m p o r t a n tw a yt o g e tu s e f u li n f o r m a t i o nf o r i l lad a t a b a s e a m o n gt h i s ，a s s o c i a t i o nr u l e sm i n i n gi sam a j o rb r a n c h i te m p h a s i z e st h ea s s o c i a t i o n o rr e l a t e dc o n n e c t i o na m o n gi t e m si nad a t a b a s e a c c o r d i n gt ot h ed i f f e r e n c e so f t h e d a t a s e t s ，a s s o c i a t i o nr u l e m i n i n g c a nb ed i v i d e di n t o t w o c a t e g o r i e s ：b o o l a s s o c i a t i o nr u l ea n dq u a n t i t a t i v ea s s o c i a t i o nr u l em i n i n g t h eb o o la s s o c i a t i o nr u l e m i n i n go n l yf o c u s e so nt w o v a l u e dd a t as e t s h o w e v e r ，t h eq u a n t i t a t i v ea s s o c i a t i o n r u l em i n i n gs t u d i e st h em i n i n gr u l e so nt h ed a t as e t so fc a t e g o r i c a la t t r i b u t ea n d q u a n t i t a t i v ea t t r i b u t e t h et r a d i t i o n a la s s o c i a t i o nr u l e sm i n i n ga l g o r i t h ma n di t s i m p r o v e m e n tu s u a l l y a c c o r dw i t ht h eb o o la s s o c i a t i o nr u l e s w i t ht h e s ea l g o r i t h m sad a t a b a s eh a sr o b e r e p e a t e d l y s c a n n e da n dt h ec a n d i d a t ei t e m s e t sc o m eu pa f t e r s c a n n i n g w h i c h c o m p o s eo ft h ef r e q u e n ti t e m s e t su s e dt oa b s t r a c tt h ea s s o c i a t i o nr u l e s t h i sp a p e r p r e s e n t s a l li m p r o v e da s s o c i a t i o nr u l em i n i n ga l g o r i t h mt h a tn e e d st os c a nad a t a b a s e o n l yo n c ea n dt h e r ei sn oc a n d i d a t ei t e m s e t sa ta 1 1 t h i sa l g o r i t h mi sm u c hm o r e a d v a n c e dt h a nt h et r a d i t i o n a lo n e t h e p r o b l e mt h a tn e e d s t ob er e s o l v e d b yq u a n t i t a t i v ea s s o c i a t i o nr u l em i n i n gi s h o wt od i s c o v e ra s s o c i a t i o nr u l e sf r o ma s s o c i a t e dd a t a b a s e sw i t hb o o la s s o c i a t i o n r u l e m i n i n ga l g o r i t h m t h e c o r eo ft h i s t e c h n o l o g y i st h ed i s c r e t i z a t i o no f q u a n t i t a t i v e a t t r i b u t ea n d c a t e g o r i c a l a t t r i b u t e a f t e rt h ed i s c r e t i z e a t i o no fd a t a a t t r i b u t e s ，t h eq u a n t i t a t i v ea s s o c i a t i o n r u l e m i n i n g h a st r a n s f o r m e di n t ob o o l a s s o c i a t i o nr u l em i n i n g a n dt h ed a t as e t sa f t e rp r e t r e a t m e n tc a nb ea b s t r a c t e d 、i t l l b o o la s s o c i a t i o nr u l em i n i n ga l g o r i t h m f u r t h e r m o r e t 1 1 en o i s ed a t ai nr e a l w o r l dd a t a b a s e sh a v ed i s t u r b e dt h ed a t a m i n i n g t og e tr e a la n du s e f u lk n o w l e d g e n l eu s eo f p r e t r e a t m e n tt od a t ae n a b l e st h e d a t am i n i n gt og e ta s s o c i a t e dk n o w l e d g ea td i f f e r e n tl e v e l s t h ea p p l i c a t i o no fd a t a p r e t r e a t m e n ti nt h ea b s t r a c t i o no ft h eq u a n t i t a t i v ea s s o c i a t i o nr u l e si s a n o t h e rf o c u s t h i sp a p e rd i s c u s s e s 1 1 1 ep a p e re m p h a s i z e su p o nh o w t ot r e a ta s s o c i a t e dd a t a b a s e st o a b s t r a c tq u a n t i t a t i v ea s s o c i m i o nr u l e sw i t hd i s c r e t i z a t i o nt e c h n o l o g yt h a ti so nt h e b a s i so f c o n c e p t h i e r a r c h y k e yw o r d s ：k n o w l e d g e d i s c o v e r y , a s s o c i a t i o nr u l e ，c o n c e p th i e r a r c h y , d i s c r e t i z a t i o n 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。 据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写 过的研究成果，也不包含为获得 金月b 王些盔堂或其他教育机构的学位或证书而使 用过的材料。与我一同工作的同志对本研究所做的任何贡献均己在论文中作了明确的说明 并表示谢意。 学位论文作者签名：孝让一签字日期：c 哗年6 月王日 学位论文版权使用授权书 本学位论文作者完全了解金肥王些太堂有关保留、使用学位论文的规定，有权保留 并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权金 胆王些态堂可以将学位论文的全部或部分内容编入有关数据库进行检索t 可以采用影印、 缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名： 李九 签字日期：外年6 月二日 学位论文作者毕业后去向 工作单位： 通讯地址： 导师签名 签字日期 电话 邮编 致谢 本人在硕士研究生课程学习和撰写学位论文的过程中，自始至终得到，我 的导师胡学钢教授的悉心指导，无论从课程学习、论文选题，还是到收集资料、 论文成稿，都倾注了胡学钢老师的心血，由衷感谢胡学钢老师在学业指导及各 方面所给予我的关心咀及从言传身教中学到的为人品质和道德情操，老师广博 的学识、严谨的治学作风、诲人不倦的教育情怀和对事业的忠诚，必将使我终 身受益，并激励我勇往直前。 同时，深深感谢王浩老师对作者在开展课题方面的启发，并为作者的研究 工作提出了许多中肯、宝贵的意见。 真诚感谢计算机学院的全体老师，他们的教诲与帮助为本文的研究提供了 理论基础，并创造了许多必要条件和学习机会。 感谢所有的同学给予的帮助。 李红 2 0 0 4 年5 月1 5 日 第一章概述 伴随着数据库技术、网络技术以及许多高新技术的广泛应用，人们在享受 科技成果的同时，必须面对数据库数量的激增和信息处理能力有限的现状。随 着数据和数据库的急据增长，仅仅依靠数据库管理系统的查询检索机制和统计 学分析方法已经远远不能满足现实需要了，追切要求自动和智能地将数掘转化 成有用的信息和知识。于是数据库中知识发现( k o n w l e d g ed i s c o v e r y i n d a t a b a s e s 简称k d d ) 便应运而生，成为近年来人工智能、数据库应用等领域 的研究热点。目前，k d d 的研究涵盖了多个领域的多种知识发现方法，已经能 够发现时间序列规则、关联规则、分类规则、聚类规则等多种知识类型1 1 1 。本 文重点探讨其中的关联规则挖掘算法。 1 1 数据库中知识发现( k d d ) 1 1 1 数据库中知识发现的定义与目标 数据库中知识发现( k o n w l e d g ed i s c o v e r y i nd a t a b a s e s - - k d d ) 是从数据库 中识别有效的、新颖的并且可能是有价值的可理解的模式的非凡过程“1 。数据 库中知识发现是面向应用的，不同的应用需要发现的知识形式不同，采取的发 现策略和方法也不同。因此，在进行知识发现前要充分了解应用的主题。 目前，k d d 发现的知识形式主要包括以下几类”1 ： 特征( c h a r a c t e r i z a t i o n ) ：是指将与任务相关的数据集概括或抽象为某 个关系，称为泛化关系( g e n e r a l i z e dr e l a t i o n ) 。该泛化关系可用于提取 特征规则( c h a r a c t e r i s t i cr u l e s ) 特征规则可以在多层概念级上表示称 之为目标类( t a r g e tc l a s s ) 的数据集特征。 夺区分( d i s c r i m i n a t i o n ) ：是指发现分辨目标类( t a r g e tc l a s s ) 和对照类 ( c o n t r a s t i n gc l a s s ) 的特征与性质。从这些分辨目标类与对照类的特 征中，我们可以发现一系列的区分规则( d i s c r i m i n a t i o nr u l e s ) 夺分类( c l a s s i f i c a t i o n ) ：是指将数据归于一系列已知类中的某一个的标记 或分类过程。给定一训练数据集( 即已知某类别标记的客体集) ，以及基于 训练集中数据的特征建立的分类模型，目标是从该分类模型中生成一系列 的分类规则，这些分类规则可用于对其它未来的数据进行分类，从而可以 更好地理解数据库中的每一类。 夺聚类( c l u s t e r i n g ) ：只根据客体属性对一系列未分类客体进行类别的识别。 客体的聚类应使类内( i n t r a c l a s s ) 相似性最大，而类间( i n t e r c l a s s ) 相似性最小。一旦聚类得以确定，各个客体就作相应的聚类标记，并概括 同一聚类中的各个客体的共同特征，从而形成类别描述。 夺关联规则挖掘( a s s o c i a t i o nr u l e sm i n i n g ) ：是指发现客体之间的相互关 系。关联规则，形如“a 八a 1 _ b 。 八b ，”，意味着在目标数据中客体 b b 倾向于同客体a a 一起出现。 夺序列模式挖掘( s e q u e n t i a lp a t t e r n sm i n i n g ) ：是指在多个数据序列中发 现共同的行为模式。序列模式的发现方法与关联规则的发现方法大致相同。 但两者的序列包含判断是不一样的，而且，关联规则仅仅发现事务内部 ( i n t r a t r a n s a c t i o n ) 的模式( 项目集i t e m s e t s ) ，而序列模式则是发现 事务之间( i n t e r - t r a n s a c t i o n ) 的模式。 令预测( p r e d i c t i o n ) ：是指对某客体集中缺损值( m i s s i n gr u l e s ) 或某属 性值分布的估计。这涉及到寻找与兴趣属性相关的属性集和根据与选中客 体相似的数据集预测值分布。 本文所讨论的知识发现主要是关联规则的发现。 1 1 2k d d 的过程 如前定义所述，k d d 实际上是一个从数据库中发现知识的过程。1 9 9 6 年 f a y y a d p i m e t s k y s h a p i r o 和s m y t h 给出了k d d 过程的描述，如图1 1 所示： 卜备h 卜嵯主蠢叫 图1 1 k d d 过程 回 知识 从图1 1 中可以看出，k d d 过程由3 个主要阶段组成：数据准备、采掘、 结果表达和解释。知识的发现可以描述为这3 个阶段的反复过程。下面分别说 明这三个阶段： 数据准备：这个阶段又可以进一步分成2 个子步骤：数据的集成和选择、 2 数据预处理。数据集成将多文件或多数据库运行环境中的数据进行合并处 理，解决语义模糊性、处理数据中的遗漏和清洗脏数据等：数据选择的髑 的是辨别出需要分析的数据集合，缩小处理范围，提高数据采掘的质量： 数据预处理主要是对选择产生的数据进行再加工，检查数据的完整性及数 据的致性，对其中的噪音数据进行处理，对丢失的数据可以利用统计方 法进行填补，本文在数据准备阶段中，将着重研究如何针对具体问题采取 更有效的数据预处理策略，以保证数据挖掘结果的有效性。 夺数据挖掘：这个阶段进行实际的采掘操作。包括的要点有：( 1 ) 要先决定 如何产生假设，是让数据采掘系统为用户产生假设，还是用户自己对于数 据库中可能包含的知识提出假设。前一种称为发现型( d i s c o v e r y d r i v e n ) 的数据采掘；后一种称为验证型( v e r i f i c a t i o n - d r i v e n 的数据采掘：( 2 ) 选 择合适的工具：( 3 ) 发掘知识的操作：( 4 ) 证实发现的知识。 夺结果表述和解释：根据最终用户的决策目的对提取的信息进行分析，把最有 价值的信息区分出来，并且通过决策支持工具提交给决策者。因此，这一步 骤的任务不仅是把结果表达出来( 例如采用信息可视化方法) ，还要对信息 进行过滤处理。如果结果不能令决策者满意，需要重复以上数据采掘的过程。 1 2 数据挖掘 1 。2 1 数据挖掘的方法 在k d d 过程中，数据挖掘是其中最重要的部分，根据挖掘的任务不同， 数据挖掘的方法也不同常用的挖掘方法和技术可归为以下几类0 1 | 5 1 夺概念格方法：概念格( 也称g a l o i s 格) 是r w i l l e 在1 9 8 2 年h 部首先提出 的，已知上下文( c o n t e x t ) 为三元组c = ( o ，d ，r ) ，其中0 是对象集合，d 是 属性集合，r 是o 和d 之间的一个二元关系则存在唯一的偏序关系与之 对应，并且这个偏序关系产生一个格结构，它能揭示数据中所蕴含的各种 关系。 夺决策树方法：利用信息论中的互信息( 信息增益) 寻找数据库中具有最大 信息量的字段，建立决策树的一个结点。再根据字段的不圊取值建立树的 分支；在每个分支子集中重复建树的下层结点和分支的过程，即可建立决 策树。国际上最有影响和照早的决策树方法是q u i u l a n 研翻的i d 3 方法，它 对越大的数据库效果越好。在i d 3 方法的基础上，后人又发展了各种决策 树方法；如c 4 5 方法。 夺神经网络方法：它模拟人脑神经元结构。以m p 模型和h e b b 学习规则为基 础，建立了三大类多种神经网络模型。( 1 ) 前馈式网络。它以感知机、反 向传播模型、函数型网络为代表，可用于预测、模式识别等方面。( 2 ) 反 馈式网络。它以h o p f i e l d 的离散模型和连续模型为代表，分别用于联想记 忆和优化讨箅。( 3 ) 自组织网络。它以a r t 模型、k o h o l o n 模型为代表， 用于聚类。神经网络和知识体现在网络连接的权值上，是一个分布式矩阵 结构；神经网络的学习体现在神经网络权值的逐步计算上( 包括反复迭代 或累加计算) 。 夺粗糙集( r o u g hs e t ) 方法：在数据库中，将行元素看成对象，列元素看成 属性( 分为条件属性和决策属性) 。等价关系r 定义为不同对象在某个( 或 几个) 属性上取值相同，这些满足等价关系的对象组成的集合称为该等价 关系r 的等价类。条件属性上的等价类e 与决策属性上的等价类y 之帕j 有 三种情况：下近似：y 包含e ；上近似：y 和e 的交非空；无关：y 和e 的交为空。对下近似建立确定性规则，对上近似建立不确定性规则( 含 可信度) ，对无关情况不存在规则。 夺遗传算法：这是模拟生物进化过程的算法，由三个基本算法组成：( 1 ) 繁 殖( 选择) 是从一个1 日种群( s t 代) 选出生命力强的个体，产生新种群( 后 代) 的过程。( 2 ) 交叉( 重组) 选择两个不同个体( 染色体) 的部分( 基 因) 进行交换，形成新个体。( 3 ) 变异( 突变) 对某些个体的某些基因进 行变异( 1 变0 、0 变1 ) 。这种遗传算法可起到产生优良后代的作用。这些 后代需满足适应值，经过若干代的遗传，将得到满足要求的后代( 问题的 解) 。遗传算法己在优化计算和分类机器学习方面发挥了显著作用。 夺统计分析方法：在数据库字段项之间存在两种关系：函数关系( 能用函 数公式表示的确定性关系) ；相关关系( 不能用函数公式表示、但仍是相 关确定关系) 。对它们的分析采用如下方法：回归分析、相关分析、主成分 分析。 夺可视化技术：可视化数据分析技术拓宽了传统的图表功能，使用户对数据 的剖析更清楚。例如，把数据库中的多维数据变成多种图形，这对揭示数 的状况、内在本质及规律性起了很大作用。 1 2 2 关联规则挖掘 关联规则是r a k e s ha g r a w a l 等人提出的数据挖掘领域中的一个重要课题， 它揭示数据间的相互关系。关联规则的挖掘就是从一组给定的数据项以及交易 集台( 每一条交易是一个数据项的集合) 中，分析出数据项集在交易集合中出 现的频度关系。 挖掘关联规则的算法已经有很多，比较重要的有r a k e s ha g r a w a l 等人提 出的a p r i o r i 算法“、s e r g e yb r i n 等人提出的d i c 算法”1 和h a n 等人提出的 f p - - 增长算法1 4 5 1 。另外最近一些研究人员关注从概念格中挖掘各种规则。把所 感知的事物的共同特点抽象出来，并加以概括，成为概念，概念都具有内涵和 4 外延。r w i ll e 在1 9 8 2 年首先提出根据二元关系系统来构造相应概念格( 或 g a l o i s 格) 的思想，也称为形式概念分析，就是以格中的每个节点表示一个 形式概念，其中概念的外延代表相应的一组对象，内涵则为这组对象所具有的 公共特征( 属性) ；而概念格所对应的h a s s e 图表形象地揭示了概念间的泛化和 例化关系，反映出一种概念层次结构( c o n c e p th i e r a r c h y ) ，实现了对数据的 可视化，非常适用于从数据库中进行知识发现的描述”1 ，从而成为数据分析和 规则提取的一种有效工具。 根据关联规则挖掘的数据集的不同，可以将关联规则挖掘技术分为两大 类：布尔关联规则挖掘技术和数值关联规则挖掘技术。布尔关联规则挖掘技术 研究仅包含二值属性的数据集中的关联规则挖掘；数值关联规则挖掘技术研究 包含多值属性( 分类属性) 或连续属性( 量化属性) 的数据集中的关联规则挖 掘。 ( 1 ) 布尔关联规则挖掘技术 布尔关联规则挖掘技术研究仅包含二值属性的数据集的关联规则挖掘，挖 掘对象是事务数据库中的布尔型数据集，主要的任务是如何提高算法的挖掘效 率。影响布尔关联规则挖掘算法效率的主要因素有算法需要的数据库的扫描次 数、需要计算支持度的候选项目集的数量等。层次算法在修剪候选项目集上比 较有效，典型的层次算法主要是a p r i o r i 算法和f p 一增长算法。数据集划分算 法主要从减少数据库的次数着手，d i c 算法就是较典型的数据集划分算法。本 文在第三章详细描述典型的布尔关联规则挖掘算法a p r i o r i 算法、f p 一增长算法 和d i c 算法。根据数据库中存在的若干包含不同项目集的事务，对事务集进行 划分，最后将数据库划分成若干个事务集。根据该分层思想，本文第三章提出 了b d i f 算法及其实现过程。 ( 2 ) 数值或量化关联规则挖掘技术 关系数据库的广泛应用使对关系数据库的挖掘变得越来越迫切。关系数 据库中数据集的数据类型主要是连续的或多值的非二值属性( 量化属性或分类 属性) 。如何对关系数据库中的关系数据集应用布尔关联规则算法挖掘关联规 则，是量化关联规则挖掘技术要解决的问题。该技术的中心问题是量化属性和 分类属性的离散化。在完成了数值属性的离散化之后，量化关联规则挖掘问题 就转化为布尔关联规则挖掘问题，可以应用布尔关联规则算法来对预处理后的 数据集进行挖掘。本文第五章就此问题展开了讨论，并给出了实例描述。 将布尔关联规则挖掘技术和量化属性、分类属性的离散化技术集成，以期 构成完整的量化关联规则挖掘系统。本文第六章针对一个具体的、具有量化属 性和分类属性的数据库，设计了一个量化关联规则挖掘系统，包括后台数据库、 前台界面和中间挖掘部分三层结构。 1 3 数据挖掘的发展及其所面i 临的挑战 1 3 1 数掘挖掘的发展 数据挖掘是从数据库中提取知识，作为新一代数据库分析】：具和技术，借 助于计算机系统来进行自动分析，发现其中有价值的知识。从出现以来的短短 十多年的时间内迅速发展，并已经取得了许多成果t 2 l o 数据库中的知识发现( k d d ) 在1 9 8 9 年召开的第1 l 届国际人工智能联合 学术会议( i j c a i ) 上首次提出的。在这届学术会议上举行了以k d d 为主题的学 术研讨会，在1 9 9 1 、1 9 9 3 年和1 9 9 4 相继举行了k d d 专题研讨会。随着k d d 的 深入研究以及k d d 在许多领域中的成功应用，1 9 9 5 年在加拿大召开了第一届知 识发现和数据挖掘国际学术会议，此后每年都召开大规模的国际会议。第一本 关于k d d 的国际学术杂志 d a t am i n i n ga n dk n o w l e d g ed i s e o v e r y ) 也于1 9 9 7 年3 月创刊发行。亚太地区于1 9 9 7 年在新加坡召开首次k d d 研讨会( p a k d d ) ， 其后又在澳大利亚的墨尔本召开第二届，在中国北京召开第三届。目前，在 i j c a i 、a a a i 、v l d b 、a c m s i g m o d 等代表人工智能与数据库技术研究最高水平 中的国际学术会议上，知识发现的研究都占有较大的比例，知识发现的研究已 经成为当今计算机科学与技术研究、应用的热点领域之一。 k d d 的动力来自于实际应用的需求。许多公司也效力于这一领域的研究和 开发。从大量的数据中找出感兴趣且有用的模式，为决策过程提供支持。是各个 企业和研究者共同关心的课题 随着知识发现在国际上的兴起，我国也积极地开展了这方面的研究和应用 目前，国内的许多学术会议如中国人工智能联合学术会议、数据库学术会议、机 器学习学术会议等也都将知识发现列为重要的研究专题一些高等院校与科研 机构也开展了知识发现系统的研究我校是国内较早进行知识发现研究的单位 之一，八十年代末期以来相继在国家自然科学基本资助下开展了“从关系数据库 中提取领域知识的自动化获取研究”，在国家教委博士学科点专项科研基金资 助下开展了“从大规模数据库中自动提取领域知识的算法与实现研究”。本文 即是在上述背景下开展的研究。 数据库中的知识发现，是数据库与人工智能相结合的产物，但从事这一领 域和应用的许多科研人员。有关k d d 研究和发展的新情况参见“_ “1 。 1 3 2 数据挖掘所面临的挑战 经过近十多年的发现，k d d 在研究和应用方面取得了丰硕的成果，但依然 面临来自研究和应用方面的挑战。在k d d 的研究领域中，随着数据数量的激增 和数据形式的发展，常常面临下列问题： 数据库的多样性问题 6 在关系数据库和数据仓库的广泛应用中，常常可见复杂的数据对象、超文 本和多媒体数据、宅间数据、时间数据或事务数据等，由于数据不同，数掘挖 掘任务不同，采用通用的挖掘方法去实现所有的挖掘任务是不现实的。挖掘系 统必须根据数据类型和挖掘任务来构造。 夺数据挖掘的性能问题 数据挖掘通常面向大规模数据库，算法的运算量较大。提高算法的时间性 能和空间性能是提高数据挖掘性能的关键之一。当前常用的解决方法有并行挖 掘、分布式挖掘和增量挖掘，以及利用先验知识来提高挖掘的效率和精度。 令数据的预处理问题 噪声数据和不完全数据的存在，使得数据集呈现过分拟合状态，在此之上 进行的挖掘过程必然受到影响，使得挖掘效率和精度下降。因此，合理地进行 数据预处理是提前挖掘效率的前提之一。 夺先验知识的应用 利用背景知识指导挖掘过程，使挖掘的结果以简捷的形式表达，先验知识 的运用可以提高挖掘的速度和准确率。但先验知识来自于过去的实际数据，需 要进一步调整以适应当前的数据。 1 4 本文的研究内容与章节安排 本文对数据挖掘中的关联规则挖掘的方法进行了研究，结合有效的数据预 处理技术，提出了有效的关联规则挖掘算法，并设计实现了一个数据挖掘工具 的原型。各章的内容安排如下： 第一章概述概括介绍了k d d 、数据挖掘的理论与方法。 第二章关联规则挖掘概述在此介绍了关联规则挖掘的相关理论。 第三章关联规则挖掘算法的研究本章讨论了关联规则挖掘的相关算 法，并提出了一种改进的关联规则挖掘算法。 第四章数据挖掘中的数据预处理技术的研究提出了如何针对具体数据 的离散化技术。在本文的研究中，基于概念分层的连续型数据离散化的技术作 为数据准备阶段采用的策略，在数据挖掘中超重要作用。 第五章量化关联规则挖掘的研究本章讨论了量化关联规则的挖掘方法， 并用实例说明具体的实现过程。 第六章数据挖掘工具的设计与实现 本章详细描述了作者设计并实现 的一个面向土工实验数据的关联规则挖掘工具的构造、实现与应用。 第七章结束语总结全文，提出了进一步的工作。 第二章关联规则挖掘研究概述 在数据挖掘的知识模式中，关联规则模式是比较重要的一种，也是最活跃 的一个分支。关联规则挖掘能发现大量数据中项集之间有趣的关联或相关关系。 从大量商务事务记录中发现有趣的关联关系，可以帮助许多商务决策的制定， 如分类设计、交叉购物和贱卖分析。 2 1 关联规则挖掘问题描述 2 1 1 基本概念 关联规则挖掘哺1 是当前数据挖掘研究的主要内容之一，侧重于事务数据库 中不同项目间的关系。关联规则的概念由a g r a w a l ，i m i e l i n s k i 和s w a m i 提出， 是数据中一种简单但很实用的规则，它揭示数据间的相互关系。关联规则挖掘 就是从一组给定的数据项以及交易集合( 每一条交易是一个数据项的集合) 中， 分析出数据项集在交易集合中出现的频度关系。关联规则的定义见文献”1 。 定义2 1 关联规则挖掘的事务数据库记为d ，d = t l ，t 2 ，t k ，t n ) ， t k = i l ，i 2 ，i 3 ，i j ，i p ) ( k = 1 ，2 ，n ) n d 中的一条事务；t k 中的元素b ( j = 1 ，2 ，p ) 称为项目( i t e m ) 。 在事务数据库中为找出关联规则，必须处理各种不同的项目集合，每一个 项目组合都称为一个项目集。由于空集在这里没有意义，因此若项目总数为怫 所有需要考察的项目集的数量为2 1 p i _ 1 。 定义2 2 设i = i l ，i 2 ，i 3 ，i 。) 是d 中全体项目组成的集合，i 中的任 何子集x 称为d 中的项目集( i t e m s e t ) ，l x i = k 称集合x 为k 项目集。设t k 和 x 分别为d 中的事务和项目集，如果x _ t k ，称事务“包含项目集x 。 定义2 3 事务数据库d 中包含项目集x 的事务数称为项目集x 的支持数， 记为0 x ；项目集x 的支持度，记作：s u p p o r t ( x ) 。 s u p p o r t ( x ) = 普1 0 0 ( 2 1 ) 1 1 3 i 其中，l d i 是事务数据库d 中的事务集。若s u p p o r t ( ) ( ) 不小于用户指定的最 小支持度m i n s u p ，则称x 为频繁项目集( 或大项目集) ，否则称x 为非频繁项 目集( 或小项目集) 。 定理2 1 设x ，y 是事务数据库d 中的项目集 ( i ) 若x y ，则s u p p o r t ( x ) s u p p o 呱y ) ( 2 2 ) ( i i ) 若x c y ，如果x 是非频繁项目集，则y 也是非频繁项目集。 ( i i i ) 若x e y ，如果x 是频繁项目集，则y 也是频繁项目集。 定义2 4 若x 、y 为项目集，且x n y = a ，蕴含式x _ y 称为关联规则， x 、y 分别称为关联规则x = y 的前提和结论。项目集( x u y ) 的支持度称为 关联规则x = y 的支持度，记作：s u p p o r t ( x = y ) s u p p o n ( x = y ) = s u p p o r t ( x u y )( 2 3 ) 关联规则x = y 的置信度记作：c o n f i d e n c e ( x = y ) c o n n d e n c e f x ： y 1 ：s u p p o r t ( x t j y ) 10 0 ( 2 4 ) s u p p o r t ( x ) 通常，用户根据采掘需要指定的最小置信度记为：m i n c o n f 。 支持度和置信度是描述关联规则的两个重要概念。前者用于衡量关联规则 在整个数据库中的统计重要性；后者用于衡量关联规则的可信程度。般来说， 只有支持度和置信度均较高的关联规则才可能是用户感兴趣的、有用的关联规 则。 定义2 5 如果s u p p o r t ( x = 二， m i n s u p ，且c o n f i d e n c e ( x = 一 m i n c o n f ， 称关联规则x = y 为强规则，否则称之为弱规则。 2 1 2 关联规则的种类 ( 1 ) 基于规则中处理变量的类型，关联规则可以分为布尔型和数值型。 布尔型关联规则考虑的是项集的存在与否，处理的值都是离散 的、种类化的，它显示了这些变量之间的关系。而数值型关联规则 则是量化的关联规则，它可以和多维关联或多层关联规则结合起来， 对数值型字段进行处理，将其进行动态的分割，或者直接对原始的 数据进行处理，当然数值型关联规则中也可以包含种类变量。 例如：性别- 女”j 职业- 秘书”布尔型 性别= “女”ja v g ( 收入) = 2 3 0 0数值型 ( 2 ) 基于规则中数据的抽象层次，可以分为单层关联规则和多层关联规则 在单层关联规则中，所有的变量都没有考虑到现实的数据是具有多个不同 的层次的。而多层关联规则则充分考虑了数据的多层性。 ( 3 ) 基于规则中涉及到的数据的维数，关联规则可分为单维的和多维的。 在单维的关联规则中，只涉及到数据的一个维，如： b w s ( x ，“i b md e s k t o pc o m p u t e r ) 2 b u y s ( x ，“s o n y b wp r i n t e r ”) 规则中包含单个谓词( 即b w s ) 的多次出现。 在多维的关联规则中，要处理的数据会将会涉及多个维，如： a g e ( x ，“2 0 2 9 ”) a o c e u p a t i o n ( x ，“s t u d e n t ) = b u y s ( x ，“l a p t o p ”) 规则中涉及两个或多个谓词或维的出现。 我们了解了关联规则的分类之后，就可以在具体的分析过程中考虑某些具 体方法适用于哪一类规则的挖掘，某类规则又可以用哪些方法处理。 9 2 2 关联规则挖掘问题的分解 为了有效挖掘关联规则，必须给定最小支持度( m i n s u p ) 和最小可信度 ( m i n c o n f ) 。挖掘关联规则就是求解所有支持度和可信度均分别超过最小支持 度和最小可信度的规则，即要求满足 m i n c o n f 的关联规则x y 。因此， 个子问题： s u p p o r t ( x = y ) m i n s u p ，c o n f i d e n c e ( x = y ) 可以把关联规则挖掘问题的求解分解为两 根据最小支持度，从事务数据库d 中找出所有的频繁项目集； 利用频繁项目集生成不低于最小可信度的关联规则。 第一个子问题的任务是迅速高效地找出d 中全部频繁项目集，是关联规则 挖掘的中心问题，是衡量关联规则挖掘算法的标准。目前大多数有关关联规则 挖掘问题的研究都是针对第一个子问题而展开的；本文在第三章重点讨论相关 算法。第二个子问题可直接根据( 2 1 ) 式和( 2 4 ) 式求解。 2 2 1 根据频繁项目集产生强规则 由( 2 4 ) 式可知，强规则的产生过程如下： 对于每个频繁项目集l ，产生l 的所有非空真子集； 对于l 的每个非空子集m ，如果竺堡坐坚罂1 0 0 ：m i n c o n f ， s u pp o r t ( m ) 则输出强规则m = ( f m ) 。 推论2 1 对项目集l 和其真子集m 和m ，若1 1 1 m ，则关联规则m = l m 的置信度不可能大于关联规则m = l m 的置信度。 在根据频繁项目集产生强规则时，利用推论2 1 可以减少计算量，进一步提 高强规则的产生效率。 2 2 2 关联规则挖掘的基本模型 综上所述，关联规则挖掘的基本模型如图2 1 所示。其中，d 为事务数据库， a l g o r i t h m l 为频繁项目集的搜索算法，a l g o r i t h m 2 为关联规则的产生算法，r 为挖掘出的关联规则集合。 m i n c o n f o0 用户通过指定m i n s u p 、m i n c o n f 分别与算法a l g o r i t h m i 和a l g o r i t h m 2 交互 并通过与r 的交互对挖掘结果进行解释和评价。 2 3 关联规则挖掘方法 2 3 i 经典的关联规则算法及其改进算法 关联规则的挖掘问题最初是针对超市的交易数据而提出的，称之为经典关 联规则挖掘问题。解决关联规则问题的原始算法是a g r a w a l 等人提出的a i s 算 法6 1 ，该算法产生的候选项目集过大。为改进a i s 算法，h e i k k im a n n i l a 等人提 出了o c d 算法t 2 9 1 , o c d 算法利用上次搜索的组合信息来减少本次候选项目集 的生成数量。r a k e s h a g r a w a l 等人又在文献”中提出了著名的a p r i o r i 算法。 该算法改进了a i s 算法中支持度的计算方法，利用定理2 1 来对候选集进行剪 枝，从而大大减少了候选项目集的数量和计算时间，其后的很多关联规则算法 都是基于a p r i o r i 算法的。但a p r i o r i 算法需要多次扫描数据库，产生的候选项 集仍然较大：为提高算法的效率，许多学者提出了改进算法，主要的技术有： 夺散列和杂凑 实验发现，寻找频繁项集的主要计算是在生成频繁2 项集l 2 上，p a r k 利用 这个性质引入散列技术1 和杂凑技术b 9 1 来改进产生频繁2 项集的方法。其中 基于散列技术的算法的基本思想是：当扫描数据库中每个事务，由c 1 中的候选 1 项集产生频繁l 项集l 1 时，对每个事务产生所有的2 项集，将它们散列到散 列表结构的不同桶中，并增加对应的桶计数，在散列表中对应的桶计数低于支 持度阈值的2 项集不可能是频繁2 项集，可从候选2 项集中删除，这样就可大 大压缩了要考虑的2 项集。 夺事务压缩 a g r a w a l 等提出压缩进一步迭代扫描的事务数的方法h 1 3 0 因为不包含任 何k 项集的事务，不可能包含任何( k 十1 ) 项集，可对这些事务加上删除标志， 扫描数据库时不再考虑。 夺划分 s a v a s e r e 等设计了一个基于划分的算法1 3 9 1 这个算法先把数据库从逻辑上 分成几个互不相交的块，每次单独考虑一个分块并对它生成所有的频集，然后 把产生的频集合并，用来生成所有可能的频集，最后计算这些项集的支持度。 这里分块的大小选择要使得每个分块可以被放入主存，每个阶段只需被扫描一 次。而算法的正确性是由每一个可能的频集至少在某一个分块中是频集保证的。 令选样 m a n n i l a 等考虑在给定数据的一个子集挖掘1 2 7 | , 对前一遍扫描得到的信息， 仔细地组合分析，得到一个改进的算法。t o i v o n e n 进一步发展了这个思想1 3 0 1 ， 先使用从数据