（计算机应用技术专业论文）基于关系数据库的关联规则挖掘算法研究.pdf

摘要 数据库技术的逐渐成熟、网络技术的迅速普及和计算机硬件的不断出新，使 人们采集数据的能力得到了极大的提高，从而导致了全球范围内数据存储量的急 剧增大。为增强人们对这些海量数据的理解能力，数据挖掘技术近年来得到了快 速发展。而关系数据库是众多行业和部门用于存储其生产、管理和科研等大量信 息的重要形式，数据量的增长极为迅速。因此积极研究在关系数据库上的数据挖 掘的有效技术具有极为广阔的发展前景。 关联规则挖掘是数据挖掘的重要内容之一，1 9 9 3 年由a g r a w a l 等人提出，它最 初是以分析事务数据库中项与项之间联系为目标，后来的研究者们对问题原型进 行了多方面的改进和扩充。关联规则挖掘问题通常分解成两步进行：( 1 ) 找出所有 满足最小支持度的项集即频繁集；( 2 ) 从频繁集中提取出满足最小支持度和最小置 信度的规则。其中最关键的一步是频繁集产生。 本文在对a p r i o f i 等事务数据库中布尔型关联规则的典型算法进行分析后，提 出了一种关系数据库中频繁集产生算法。该算法的核心是利用s q l 语言的聚集查 询和连接等语句对关系数据库进行操作，完成频繁项集的搜索过程。由于s q l 语 言对关系数据库操作的高效性和算法与数据库管理系统的紧密性，所以该算法具 有较高的挖掘效率。 对于第二步规则的生成，目前绝大多数的研究算法主要是挖掘正关联规则。 实际上，挖掘正关联规则和负关联规则是同样重要的。为了满足数据关系的完备 性，我们需要负关联规则。另外，如何度量关联规则的不确定性是关联规则挖掘 研究中的重要问题之一。而支持度一置信度模型是关联规则挖掘普遍应用的模型。 它采用s u p ( x y ) 和c o n f f x - - - v ) 来度量关联规则的不确定性。然而用这一度量标 准可能会得到诸如x y ，但x 与y 不相关( 或独立) 的规则。因此，仅用c o n f ( x 一 来度量关联规则的不确定性是不够的。本文基于统计学相关系数的概念，给出了 一个能同时挖掘正关联规则和负关联规则的p r _ n r 算法，通过实验表明该算法是 有效的。 关键词 数据挖掘；关系数据库；关联规则；s q l 语言；负关联规则；相关系数 i i a b s t r a c t w i t hg r o w t ho fd a t a b a s et e c h n o l o g y , p o p u l a r i t yo fn e t w o r kt e c h n o l o g ya n d u p d a t i n go fc o m p u t e rh a r d w a r e ，t h ec a p a b i l i t yo fc o l l e c t i n gd a t aw a si m p r o v e dr a p i d l y h e n c e ，t h ec a p a c i t yo fs t o r i n gd a t aw a se n l a r g e dh u g e l ya l lo v e rt h ew o r l d t oi m p r o v e t h eu n d e r s t a n d i n go fv a s td a t a ，d a t am i n i n gt e c h n o l o g yh a si m p r o v e dr a p i d l y r e l a t i o n a l d a t a b a s ei sa ni m p o r t a n tf o r mt os t o r el o t so fi n f o r m a t i o no fp r o d u c t i o n ，m a n a g e m e n t a n ds c i e n t i f i cr e s e a r c h t h ei n c r e a s eo fd a t aq u a n t u mi sv e r yf a s t s t u d y i n gt h ee f f i c i e n t t e c h n o l o g yo fm i n i n ga s s o c i a t i o nr u l e sh a saw i d ed e v e l o p m e n ti nf u t u r e m i n i n ga s s o c i a t i o nr u l e si so n eo fi m p o r t a n tp a r t so fd a t am i n i n g ，w h i c hi s a d v a n c e db ya g r a w a la n dt h eo t h e ri n1 9 9 3 f i r s tt h ep u r p o s ei sa n a l y z i n gt h er e l a t i o n o fi t e m si nt r a n s a c t i o nd a t a b a s e l a t e r , b e c a u s ei n v e s t i g a t o ri m p r o v e da n de x t e n d e dt h e p r o t o t y p eo fq u e s t i o n m i n i n ga s s o c i a t i o nr u l e sh a sb e e na na c t i v er e s e a r c ha r e ao fd a t a m i n i n g m i n i n ga s s o c i a t i o nr u l e sc a l lu s u a l l yd e c o m p o s et w os t e p s ：( 1 ) g e n e r a t ea u i t e m s e t sw h o s es u p p o r ta r ea tl e a s tb i g g e rt h a nag i v e nm i n i m u ms u p p o r t ，w h i c ha r e r e f e r r e dt of r e q u e n ti t e m s e t s ；( 2 ) e x t r a c ta l lr u l e sf r o mt h ef r e q u e n ti t e m s e t s b u tt h e m o s ti m p o r t a n ts t e pi st h ef r e q u e n ti t e m s e t sg e n e r a t i o n t h i sp a p e ra n a l y z i n gr u l e si na l g o r i t h mo ft y p i c a lb o o l e a na s s o c i a t i o nr u l e si n t r a n s a c t i o nd a t a b a s e i ti sc o n c l u s i o nt h a tt h em i n i n ga l g o r i t h mo ft h ef r e q u e n ti t e m s e t s g e n e r a t i o ni nr e l a t i o n a ld a t a b a s e i ti sc o r eo ft h ea l g o r i t h mt h a tr e l a t i o n a ld a t a b a s ei s o p e r a t e dw i t ht h eg a t h e rs e l e c t i o na n dl i n ks e n t e n c ei ns q ll a n g u a g e ，i n o r d e rt o c o m p l e t et h es e l e c t i n gc o u r s eo ff r e q u e n tp r e d i c a t es e ta n de f f i c i e n tr u l e s b e c a u s ei ti s e f f i c i e n tt h a tr e l a t i o n a ld a t a b a s ei so p e r a t e dw i t ht h es o ll a n g u a g e ，a n da l g o r i t h m c o m b i n e st h ed a t a b a s em a n a g e m e n ts y s t e mc l o s e l y , t h ea l g o r i t h mi so ft h em i n i n g e f f i c i e n c y a b o u tt h er u l e sg e n e r a t i o n ，m o s to ft h ee x i s t i n gw o r kh a sf o c u s e do nm i n i n g p o s i t i v ea s s o c i a t i o nr u l e s i nf a c t ，i ti se q u a l l yi m p o r t a n tt om i n en e g a t i v ea s s o c i a t i o n r u l e s t of i l lt h ec o m p l e t e n e s so fd a t ar e l a t i o n w en e e dn e g a t i v ea s s o c i a t i o nr u l e s f u r t h e r m o r e ，o n eo ft h ei m p o r t a n tp r o b l e m si na s s o c i a t i o nr u l e sm i n i n gi sh o wt o m e a s u r et h eu n c e r t a i n t yo ft h ea s s o c i a t i o nr u l e s o n eo ft h em o s tp o p u l a rm o d e l sf o r m i n i n ga s s o c i a t i o nr u l e si s s u p p o r t - c o n f i d e n c e m o d e l ，w h i c hu s e st w ov a l u e s ： i n s u p ( x 4 y 、a n dc o n f ( x y ) a st h em e a s u r e m e n to fu n c e r t a i n t yo fa s s o c i a t i o nr u l e s h o w e v e r , i ti sp o s s i b l et oe x t r a c ta s s o c i a t i o nr u l es u c ha sx _ y ，b u txa n dy a r e i n d e p e n d e n t t h i sm e a n st h a tc o n f ( x y 、i si n s u f f i c i e n tf o rm e a s u r i n ga s s o c i a t i o nr u l e s o fi n t e r e s t t h ep r _ n ra l g o r i t h mi sp r e s e n t e db a s e do nt h ec o r r e l a t i o nc o e f f i c i e n t t h e o r yo fs t a t i s t i c s i tc o u l dm i n ep o s i t i v ea n dn e g a t i v ea s s o c i a t i o nr u l e s e x p e r i m e n t r e s u l t sd e m o n s t r a t et h ea l g o r i t h mi se f f i c i e n t k e y w o r d s d a t am i n i n g ；r e l a t i o n a ld a t a b a s e ；a s s o c i a t i o nr u l e s ；s q ll a n g u a g e ； n e g a t i v ea s s o c i a t i o nr u l e s ；c o r r e l a t i o nc o e f f i c i e n t 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及 取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包括其他人已经发表或撰写过的研究成果，也不包含为获得 西北师范大学或其他教育机构的学位或证书而使用过的材料。与我一 同工作的同志对本研究所做的任何贡献均己在论文中作了明确的说明 并表示了谢意。 签名：缎4 鸯 日期：8 翌：互丝 关于论文使用授权的说明 本人完全了解西北师范大学有关保留、使用学位论文的规定，即： 学校有权保留送交论文的复印件，允许论文被查阅和借阅；学校可以 公布论文的全部或部分内容，可以采用影印、缩印或其他复制手段保 存论文。 签名：选4 盘 导师签名： 墨缉：冁赴i ：! ：i ! 西北师范大学硕士论文 基于关系数据库的关联规则挖掘算法研究 1 1 研究背景 第一章绪论 随着计算机硬件的不断进步导致了功能强大的计算机、数据收集设备和存储 介质的大量供应。这些技术大大推动了数据库和信息产业的高速发展，使得大量数 据库和信息存储用于事务管理、信息检索和数据分析。特别是近年来商业条码的 推广、企业和政府事务的管理以及数据采集工具的发展，产生了大规模的数据， 而在商业管理、政府部门、国防建设、科学和工业数据处理等领域中也都应用了 数以百万计的数据库。而且随着科技的发展，决策所需的数据量也不断增长，即 使像使用i c 卡和打电话这样简单的事务也能产生大量的数据。 数据的丰富带来了对强有力的数据分析工具的需求，大量的数据被描述为“数 据丰富，但信息贫乏”。如何有效的利用这些数据，从这些数据中发现有价值的信 息或知识，达到为决策服务的目的，就成了一项非常艰巨的任务。采用传统的数 据分析方法和数据查询、验证方法，对这些巨量数据进行分析和处理，不仅耗费 大量的计算时间，而且完全依赖于预先对数据之间关系的假设和估计，这些方法 已经不能满足人们日益增长的对数据中隐含知识的渴求。人们希望能够提供更高 层次的数据分析功能，自动和智能地将待处理的数据转化为有用的信息和知识。 数据挖掘与知识发现就是为迎合这种要求而产生并迅速发展起来的。 数据挖掘是指从大量数据中挖掘出隐含的、先前未知的、对决策有潜在价值 的知识和规则的高级处理过程。通过数据挖掘，有价值的知识、规则或高层次的 信息就能从数据库的相关数据集合中抽取出来，并从不同角度显示，从而使大型 数据库作为一个丰富、可靠的资源为知识的提取服务。例如，超市的经营者希望 将经常被同时购买的商品放在一起，以增加销售；保险公司想知道购买保险的客 户具有哪些特征；医学研究人员希望从已有的成千上万份病历中找出患某种疾病 的病人的共同特征，从而为治愈这种疾病提供一些帮助。数据挖掘在一些文献中 还有其它名称，如数据开采、数据采掘、知识挖掘、知识抽取、知识考察等。 1 2 数据挖掘发现历程及现状 数据挖掘起源于从数据库中发现知识( k n o w l e d g ed i s c o v e r yi nd a t a b a s e ，简 1 西北师范大学硕士论文 基于关系数据库的关联规则挖掘算法研究 称k d d ) ，它首次出现在1 9 8 9 年8 月在底特律举行的第十一届国际联合人工智 能学术会议上。为了统一认识，在1 9 9 6 年出版的总结该领域进展的权威论文集知 识发现与数据进展f 1 】中，f a y y d ，p i a t e t s k y - s h a p i r oa n ds m y t h 给出了k d d 和数据 挖掘的最新定义，将二者加以区分。 k d d 的定义为：k d d 是从数据中辨别有效的、新颖的、潜在有用的、最终 可理解的模式的过程。 数据挖掘的定义为：数据挖掘是k d d 中通过特定的算法在可接受的计算效率 限制内生成特定模式的一个步骤。 由此可见，整个k d d 过程是一个以知识使用者为中心、人机交互的探索过程。 数据挖掘只是数据库中知识发现的一个步骤，但又是最重要的一步。因此，往往 可以不加区别地使用k d d 和数据挖掘。一般在研究领域被称作数据库中的知识发 现，在工程领域则称之为数据挖掘。 1 9 8 9 年举行了第一届专题讨论会后，1 9 9 1 、1 9 9 3 、1 9 9 4 年又连续举行了k d d 专题讨论会。1 9 9 5 年8 月，在加拿大的m o n t r e a l ，召开了首届知识发现和数据挖 掘的国际讨论会。亚太地区于1 9 9 7 年在新加坡举行了首届亚太知识发现和数据挖 掘的国际会议( e a r m d ，9 7 ) ；欧洲哇l 于1 9 9 8 年召开了首届欧洲知识发现和数据挖 掘的学术会议。 迄今为止，对关系数据库和事务数据库进行数据挖掘和知识发现的研究已经 取得了一定的进展，最有影响的发现算法有：加拿大s i m o nf r a s e r 大学j h a n 教 授的概念树提升算法 2 1 、i b m 的r a g r a w a l 的关联规则算法 3 1 、澳大利亚的j r o u i n l a n 教授的分类算法【“、密西根州立大学e r i c kg o o d m a n 的遗传算法等。特 别要指出的是，数据挖掘技术从一开始就是面向应用的。i b m 、g t e 、s a s 、m i c r o s o f t 、 s i l i c o ng r a p h i c s 、i n t e g r a l s o l u t i o n s 、t h i n k i n gm a c h i n e s 、d a t a m i n d 、u r b a n s c i e n c e 、a b t e c h 、u n i c a t e c h n o l o g i e s 等公司，相继开发出一些实用的k d d 商业 系统和原型系统，如市场分析用的b e h a v i o r s c a n 、e x p l o r e r 、m d t ( m a n a g e m e n t d i s c o v e r yt 0 0 1 ) ，金融投资领域的s t o c ks e l e c t o r 、a i ( a u t o m a t e di n v e s t o r ) ， 欺诈预警用的f a l c o n 、f a i s 、c l o n e d e t e c t o r 等。各种实用的数据挖掘工具层出 不穷。 与国外相比，国内对d m k d 的研究稍晚，没有形成整体力量吼1 9 9 3 年国家自 然科学基金首次支持该领域的研究项目。目前，国内的许多科研单位和高等院校 开展了知识发现的基础理论及其应用研究，如清华大学、中科院计算技术研究所、 2 西北师范大学硕士论文基于关系数据库的关联规则挖掘算法研究 空军第三研究所、海军装备论证中心等。其中北京系统工程研究所对模糊方法在 知识发现中的应用进行了较深入的研究，北京大学正从事于数据立方体代数的研 究，安徽大学、华中理工大学、复旦大学、浙江大学、中国科技大学、中科院数 学研究所、吉林大学等单位进行了对关联规则挖掘算法的优化及相关领域的研究， 取得了一定的成果，南京大学、四川联合大学和上海交通大学等单位探讨、研究 了非结构化数据的知识发现以及w e b 数据挖掘。 总之，当前数据挖掘与知识发现研究与开发的总体水平相当于数据库技术在 七十年代所处的地位。迫切需要类似于关系模式、d b m s 系统和s q l 查询语言等理 论和方法的指导，才能使d b i k d 的应用褥以普遍推广。 1 3 数据挖掘研究的主要内容 1 3 1 数据挖掘的功能 数据挖掘功能用于指定数据挖掘任务中要找的模式类型。数据挖掘任务一般 可以分为两类：描述和预测。描述性挖掘任务刻划数据库中数据的一般特性，而 预测性挖掘任务则在当前数据上进行推断，以进行预测。 在很多情况，用户并不知道什么样的模式是有趣的，因此可能想探索多种不 同的模式，以从中选择出自己感兴趣的模式。这就要求数据挖掘系统应该能够挖 掘多种类型的模式，以适应不同的需求。此外，数据挖掘系统应该能够发现各种 粒度( 即不同的抽象层) 的模式，应当允许用户给出提示，指导或聚焦有趣模式的搜 索。 数据挖掘的功能以及可以发现的模式类型有【6 】：类概念描述、关联分析、分 类和预测、聚类分析、孤立点分析和演变分析。 1 、类，概念描述 数据可以与类或概念相关联。用汇总的、简洁的、精确的方式描述每个类和 概念可能是有用的。这种类或概念的描述称为类，概念描述。这种描述可以通过以 下方法得到： 数据特征化：是目标类数据的一般特征或特性的汇总。 数据区分：将目标类对象的一般特性与一个或多个对比类对象的般特性 比较。 数据特征化和区分：同时应用数据特征化和数据区分进行描述。 3 西北师范大学硕士论文 基于关系数据库的关联规则挖掘算法研究 2 、关联分析 关联分析用于发现关联规则，关联规则描述了给定数据集中的项之间的有趣 联系。关联分析广泛应用于购物篮或事务数据分析。从大量商务事务记录中发现 有趣的关联关系，可以帮助许多商务决策的制定，如分类设计、交叉购物和贱卖 分析等。 3 、分类和预测 分类是找出描述并区分数据类或概念的模型的过程，以便能够使用模型预测 类标号未知的对象类。预测是构造和使用模型评估无标号样本类，或评估给定样 本可能具有的属性值或值区间。分类和预测之间的区别在于，分类是预测类标号( 或 离散值、，而预测是建立连续值函数模型。例如，可毗建立一个分类模型，对银行 贷款的安全或风险进行分类；同时可以建立预测模型，给定潜在顾客的收入和职 业，预测他们在计算机设备上的花费。 4 、聚类分析 聚类将数据对象分组成为多个类或簇，在同一个簇中的对象之间具有较高的相 似度，而不同簇中的对象差别较大。与分类不同的是，它要划分的类是未知的。 5 、孤立点分析 在数据库中经常存在一些数据对象，它们不符合数据的一般模型。这样的数据 对象被称为孤立点，它们与数据的其他的部分不同或不一致。孤立点可能是度量 或执行错误所导致的。例如，数据库记录中有一些人的年龄是一9 9 9 ，这可能是这些 人年龄没有被记录，而系统给未记录的年龄的缺省值就是一9 9 9 。孤立点也可能是固 有的数据变异后的结果。例如，一个公司总裁的薪水可能远远高于其他职员的薪 水，他的薪水就成为了一个孤立点。在许多时候，孤立点被视为噪声或遗产而被 丢弃，但是，在一些应用中，孤立点可能会很有用。例如，在医疗分析中，某些 对多种治疗方式的不寻常的反应数据可能成为孤立点，但是这些数据对于治疗却 非常重要。对孤立点数据进行分析称为孤立点分析。 6 、演变分析 数据演变分析描述行为随时问变化的对象的规律或趋势，并对其建模。这种 分析可能包括时间相关数据的特征化、区分、关联、分类或聚类，但是它的不同 特点包括时间序列数据分析、序列或周期模式匹配和基于类似性的数据分析。 4 西北师范大学硕士论文基于关系数据库的关联规则挖掘算法研究 1 3 2 数据挖掘的分类 从不同的角度看，数据挖掘技术有几种分类方法：根据发现知识的种类进行 分类；根据挖掘的数据库的种类进行分类和根据采用的技术分类川。 1 、根据发现知识的种类分类。这种分类方法有：总结( s u m m a r i z a t i o n ) 挖掘、 特征f c h a r a c t e r i z a t i o n ) 挖掘、关联( a s s o c i a t i o n ) 挖掘、分类( c l a s s i f i c a t i o n ) 挖掘、聚类 ( c l u s t e r i n g ) 挖掘、趋势( t r e n d ) 分析、偏差( d e v i a t i o n ) 分析、模式( p a t t e r na n a l y s i s ) 分析等。如果以挖掘知识的抽象层次划分，又有原始层次( p r i m i t i v el e v e l ) 的数据挖 掘、高层次( h i g hl e v e l ) 的数据挖掘和多层次( m u l t i p l el e v e l ) 的数据挖掘。 2 、根据挖掘数据库的类型分类。数据挖掘基于的数据库有：关系型( r e l a t i o n a l ) 事务型( t r a n s a c t i o n a l ) 、面向对象型( o b j e c t - o r i e n t e d ) 、主动型( a c t i v e ) 、空间型 ( s p a t i 扪、文本型( t e x o 、多媒体( m u l t i m e d i a ) 数据库等等。 3 、根据采用的技术，最常用的数据挖掘技术有： ( 1 ) 人工神经网络 它从结构上模仿生物神经网络，基于自学习数学模型，通过数据的编码及神经 元的迭代求解，完成复杂的模式抽取及趋势分析功能。神经网络系统由一系列类似 于人脑神经元一样的处理单元( 称之为节点，n o d e ) 组成，节点间彼此互连分为输 入层、中间( 隐藏) 层、输出层。可以完成分类、聚类、特征挖掘等多种数据挖 掘任务。 神经网络系统具有非线性学习联想记忆的优点。但也存在一些问题：神经网 络系统是一个黑盒子，不能观察中间的学习过程，最后的输出结果也较难解释， 影响结果的可信度及可接受程度。其次，神经网络需要较长的学习时间，对大数 据量，性能可能会出现严重问题。 ( 2 ) 决策树 决策树是通过系列规则对数据进行分类的过程。采用决策树，可以将数掘规 则可视化，也不需要长时间的构造过程，输出结果容易理解，精度较高，因此决 策树在知识发现系统中应用较广。典型的决策树方法有分类回归树。 然而，采用决策树方法也有其缺点，决策树方法很难基于多个变量组合发现 规则，不同决策树分支之间的分裂也不平滑。 ( 3 ) 遗传算法 遗传算法是一种新的优化技术，基于生物进化的概念设计了一系列的过程来 西北师范大学硕士论文 基于关系数据库的关联规则挖掘算法研究 达到优化的目的。这些过程有基因组合、交叉、变异和自然选择。为了应用遗传 算法，需要把数据挖掘任务表达为一种搜索问题，而发挥遗传算法的优化搜索能 力。 ( 4 ) 最邻近技术 最邻近技术通过k 个与之最相近的历史记录的组合来辨认新的纪录。也称k 一 最邻近方法。这种技术可阻用作聚类、偏差分析等数据挖掘任务。 ( 5 ) 规则归纳 规则归纳技术通过统计方法归纳、提取有价值的i f - t h e n 规则。规则归纳的技 术在数据挖掘中被广泛使用，例如关联规则挖掘。 ( 6 ) ，可视化 可视化技术采用直观的图形方式将信息模式、数据的关联或趋势呈现给决策 者，决策者可以通过可视化技术交互式的分析数据关系。 1 3 3 数据挖掘的研究方向及面临的困难 尽管取得了许多进展，数据挖掘与知识发现仍面临着许多困难与挑战，面临 的主要问题有三大类【8 i ： 1 、挖掘方法和用户交互问题 这类问题涉及到数据挖掘技术的多个方面，主要有以下一些内容1 在数据库中挖掘不同类型的知识：由于不同的用户感兴趣的知识类型可能 会很不相同，这就要求数据挖掘系统应当覆盖范围很广的数据分析和知识发现任 务，包括数据特征化、区分、关联、分类、聚类、趋势和偏差分析以及类似性分 析。这些方式可能以不同的方式使用相同的数据库，并需要开发大量的数据挖掘 技术。 多个抽象层的交互知识挖掘：由于在进行数据挖掘之前很难知道将要挖掘 出来的是什么样的知识，因此需要数据挖掘的过程具有交互性。对于大型的数据 库，应当使用抽样技术进行交互式的数据探查。交互式挖掘允许用户聚焦搜索模 式，根据返回的结果提出和精炼数据挖掘请求，从而使用户可以以不同的粒度和 从不同的角度观察数据和发现模式。 结合背景知识：可以使用背景知识或关于所研究领域的信息来指导发现过 程，并使得发现的模式以简洁的形式在不同的抽象层表示。关于数据库的领域知 识，如完整性约束和演绎规则，可以帮助聚焦和加快数据挖掘过程，或评估发现 6 西北师范大学硕士论文 基于关系数据库的关联规则挖掘算法研究 的模式的兴趣度。 数据挖掘查询语言和特定的数据挖掘：与现在存在大量的高级程序开发语 言相比，数据挖掘还缺乏- 1 7 统一的高级语言用于描述数据挖掘的过程和结果。 关系查询语言( 如s q l ) 只能允许用户提出特定的数据检索查询，而对数据挖掘高级 语言的要求则更高，它应该能够使用户通过说明分析任务的相关数据集、领域知 识、所挖掘的数据类型、被发现的模式必须满足的条件和约束，描述特定的数据 挖掘任务。这种语言应当与数据库或数据仓库查询语言集成，并且对于有效的、 灵活的数据挖掘是优化的。 数据挖掘结果的表示和显示：高级语言、可视化表示或其他形式的表示方 法可以使知识易于理解，能够被人们直接使用。这要求系统采用有表达能力的知 识表示技术，如树、表、规则、图、图表、交叉表、矩阵或曲线等。 处理噪声和不完全数据：存放在数据库中的数据可能反映噪声、异常情况 或不完全的数据对象，它们可能搞乱分析过程，导致数据与所构造的知识模型过 分适应，由此导致所发现的模式精确性很差。这就需要处理数据噪声的数据清理 方法和数据分析方法，以及发现和分析异常情况的孤立点挖掘方法。 模式评估一兴趣度问题：数据挖掘方法发现的模式通常数以千计，怎样从中 选择出用户感兴趣的模式是一个极具挑战性的问题。 2 、性能问题 数据挖掘算法的有效性和可伸缩性：数据挖掘算法的有效性要求算法的运 行时间应尽可能地少，而可伸缩性则要求算法能够适应不同大小的数据库容量， 算法的运行时间应尽可能地与数据库的容量保持线性比例的增减关系。 并行、分布式和增量挖掘算法：并行和分布式数据挖掘算法将数据划分成 多个部分，这些部分可以并行处理，然后将各个处理结果合并。这种类型的算法 可以对付数据库的大容量、数据的广泛分布和一些数据挖掘算法的计算复杂性的 问题。而数据挖掘过程的高花费导致了对增量挖掘算法的需求，这种类型的算法 和数据库更新结合在一起，它不必随着数据库的更新重新挖掘全部数据，而只需 要在原有挖掘结果的基础上修正和加强已发现的知识。 3 、关于数据库类型的多样性问题 关系的和复杂的数据类型的处理：由于数据库类型的多样性，指望一个系 统挖掘所有类型的数据是不现实的。为挖掘特定类型的数据，应当构造特定的数 据挖掘系统。 7 西北师范大学硕士论文基于关系数据库的关联规则挖掘算法研究 由异种数据库和全球信息系统挖掘信息：局域网和广域网( 如互连网) 提供了 大量庞大的、分布式的和异种的数据库。从具有不同语义的结构化的、半结构化 的和非结构化的不同数据源发现知识，是数据挖掘技术面临的一个巨大挑战。 除此之外，目前的数据挖掘与知识发现系统还不尽如人意，人们还不能象关 系数据库系统那样调用s q l 语言就能快速查询到自己想要的东西。数据挖掘系统 与实际应用相结合得也还不够，除了经典的“啤酒”与“尿布”外，还没有太多 数据挖掘成功的范例。因此数据挖掘与其它技术特别是数据仓库技术的结合将是 今后一个重要的发展方向。 1 4 本文的主要研究内容 数据挖掘是一个新兴的、极富挑战的研究领域，其涉及的内容、研究的方向 广泛而又丰富。本文的研究工作主要围绕两个主题展开：在进一步研究经典挖掘 算法的基础上，着重针对关系数据库中关联规则的快速挖掘算法进行了研究；在 规则挖掘中加入负规则的讨论，完善和扩充了原有的规则挖掘算法。本文的创新 点包括以下几个方面： 提出了基于s q l 语言的频繁模式算法挖掘。在关联规则挖掘的找出所有频繁 项集和由频繁项集产生强关联规则两步中，第二步最容易，而挖掘关联规则的总 体性能则由第一步决定。本文利用了s o l 语言来找出所有频繁项集，继承经典 a p r i o r i 算法的优点的基础上，利用s o l 的集函数及分组语句提出了一种新的关系 数据库中频繁项集的挖掘算法，由此算法挖掘得到频繁项集同其它算法相比，不产 生候选项集也不需要额外空间，由此大大的提高了算法的时间效率，减少了内存 的占用率。 提出了基于相关系数的正、负关联规则挖掘算法，利用统计学中相关系数可 以对两变量相关、独立性进行判断的特点，提出了一种新的算法p r - n r ，通过计算 相应项集的相关系数再与设定阈值做比较来得到强关联规则，并可利用程序自动 进行闽值的调整，不用再增加额外参数即可简单有效的同时挖掘出正、负强关联 规则。 本文的内容是这样组织的： 第一章主要介绍数据挖掘的基本概念、研究内容、发展现状及面i 陆的问题与 今后的发展方向。 第二章对本文的重点研究内容关联规则进行了详细的论述，主要包括相关定 r 西北师范大学硕士论文基于关系数据库的关联规则挖掘算法研究 理以及与关联规则有关的其它研究内容，并讨论介绍了a p r i o r i 、d h p 等几个经典 算法。 第三章介绍了关系数据库的特点，以及在关系数据库中进行规则挖掘的一般 思路。在继承经典a p r i o r i 算法优点的基础上，提出了改进的在关系数据库中进 行频繁模式挖掘的算法，通过与类似算法的对比实验表明，新的频繁模式挖掘算 法具有较好的有效性和较高的效率。 第四章根据统计学中相关系数可以对两变量相关、独立性进行判断的特点， 结合第三章提出的频繁模式挖掘算法，提出了一种新的可同时生成正、负关联规 则的算法p r _ n r ，通过实验表明，基于相关系数的正负关联规则挖掘算法，能较好 地解决了原有经典算法只能生成正规则，而大部分改进算法又要加入额外参数， 如兴趣度，才能生成同时生成正、负规则的问题。 第五章对全文的总结以及对今后研究工作的展望。 9 西北师范大学硕士论文基于关系数据库的关联规则挖掘算法研究 2 1 引言 第二章关联规则的基本理论 关联规则挖掘是数据挖掘中最活跃的研究方法之一。最早是由a g r a w a l 等人 于1 9 9 3 8 1 年提出了挖掘交易数据库中项集问的关联规则问题，关联规则是发现数 据库中不同商品( 项) 之间的联系，这些规则找出顾客购买行为模式，如购买了某一 商品对购买其他商品的影响。一个典型例子是购物篮分析 。该过程通过发现顾客 放入其购物篮中不同商品( 图2 1 ) 之间的联系，分析顾客的购买习惯：通过了解哪 些商品频繁地被顾客同时购买，这种关联的发现可以帮助零售商制定营销策略。 例如，在同一次去超级市场，如果顾客购买牛奶，他也购买面包( 和什么类型的 面包) 的可能性有多大? 通过帮助零售商有选择地经销和安排货架，这种信息可 以引导销售。例如，将牛奶和面包尽可能放近一些，可以进一步刺激一次去商店 同时购买这些商品。 购物篮 癌曲碴 顾客1顾客2顾客3 顾客1 1 图2 1 购物篮分析 以下引入关联规则挖掘的基本概念。 2 2 关联规则的基本概念 1 关联规则( a s s o c i a t i o nr u l e ) 定义2 1 ：没i = i l ，i 2 ，i 。) 为项目集，d = t 1 ，t 2 ，t n ) 是事物数据库， 其中每个事务t i 是项的集合，使得t j i ，且每个事务都有个确定的唯一的标识 1 0 西北师范大学硕士论文 基于关系数据库的关联规则挖掘算法研究 符t i d 。设a 是一个项集，事务t j 包含a 当且仅当a t j 。当a c i ，b c i ，并 且a n b = f 时，形如a = 争b 的蕴涵式就称为事务集d 中的关联规则。 2 支持度( s u p p o r t ) 和置信度( c o n f i d e n c e ) 定义2 2 ：给定事务集d 中的关联规则规则a b ，d 中事务包含a u b ( 即 a 和b 二者) 的百分比s ，称为关联规则规则a b 在事务集d 中成立具有支持 度s ，它是概率p ( a u b ) ；d 中包含a 的事务同时也包含b 的百分比c ，称为规 则a b 在事务集d 中具有置信度c ，这是条件概率p ( bia ) 。记为： s = s u p p o r t ( a 。b ) = p ( a ub ) c = c o n f i d e n c e ( a b ) = p ( bia ) = s u p p o r t ( a ub ) s u p p o r t ( a ) 3 最小支持度( m i n _ s u p ) 和最小置信度( m i n _ c o n f ) 定义2 3 ：由用户或领域专家指定的支持度和置信度阈值，称为最小支持度和 最小置信度。 定义2 4 ：当关联规则a b 的支持度和置信度同时满足指定的最小支持度闽 值和最小置信度阈值，则将这样的规则称作强规则。 j o t 表2 1 为一事务库d ，且l d = 6 ，i = 面包、鸡蛋、牛奶) ，m i n _ s u p = 2 5 ， m i n _ c o n f = 5 0 ，则s u p p o r t ( 买牛奶；买面包) = 2 6 3 3 3 ，c o n f i d e n c e ( 买牛奶 买面 包) = 2 4 = 5 0 ，同时满足r a i n _ s u p 和r a i n _ c o n f , 这样“买牛奶 买面包”是强规则。 表2 1 事务数据库 1 1 d项集 t l牛奶、面包 t 2 牛奶、面包、鸡蛋 b牛奶、鸡蛋 t d牛奶、鸡蛋 b鸡蛋 瓦 鸡蛋 4 项集( i t e m s e t ) 、k 项集和频繁项集( 矗e q u e n ti t e m s e t ) 定义2 5 ：项的集合称为项集。包含k 个项的项集称为k 一项集。项集的出现频 率是包含项集的事务数，称为项集的支持计数。 定义2 6 ：当项集的支持计数大于或等于m i ns u p 与d 中事务总数吲的乘积时， 称它为频繁项集( f r e q u e n tl t e m s e t ) 。 频繁k 一项集的集合通常记作h ，所有候选k 一项集的集合记作c k ，显然有 西北师范大学硕士论文 基于关系数据库的关联规则挖掘算法研究 l c c k o 表2 1 例中，2 一项集 牛奶、面包 的支持记数= 2 2 6 x 2 5 = 1 5 2 项集f 牛奶、鸡蛋) 的支持记数= 3 6 x 2 5 一1 5 2 一项集 面包、鸡蛋) 的支持记数= 1s6 x 2 5 = 1 5 所以有频繁2 一项集k = 牛奶、面包) 、 牛奶、鸡蛋) ，候选2 一项集c 2 = “牛 奶、面包) 、 牛奶、鸡蛋) 、 面包、鸡蛋) ) 。 2 3 关联规则挖掘步骤 关联规则的挖掘就是要发现所有满足最小支持度和最小置信度的关联规则。关 联规则的挖掘可以分解为两步过程i s ： 1 找出所有频繁项集。 通过用户给定的最小支持度m i n _ s u p ，从数据集合或交易集合d 中寻找所有 支持度s u p p o r t 不小于m i n _ _ s u p 的项集，即找出所有频繁项集。这个步骤也称为频 繁模式挖掘或频繁项集挖掘。这些频繁项集是形成关联规则的基础。 2 由频繁项集产生强关联规则 确定某一规则是否有效，当且仅当通过该规则的置信度c o n f i d e n c e 不小于用户 给定的最小置信度m i nc o n f 。这样该关联规则就是一条有效的规则，或是说其为 强规则。 这两步中，第二步相对容易。挖掘关联规则的总体性能主要由第一步决定。 在关联规则挖掘过程中，经常用到如下两个性质( a p r i o r i 性质) ： 性质2 1 ：任何非频繁项集的超集一定也是非频繁项集。 性质2 2 ：任何频繁项集的子集一定也是频繁项集。 2 4 关联规则分类 将关联规则按不同盼睛况可进行如下分类1 1 0 1 ： ( 1 ) 基于规则中处理的变量的类别，关联规则可以分为布尔型和数值型。布尔类 型关联规则处理的值都是离散的、种类化的；而数值型关联规则可以和多维关联 或多层关联规则结合起来，对数值型字段进行处理，当然数值型关联规则中也可 以包含种类变量。 例如：性别= “女”一职业秘书”，是布尔型关联规则；性别_ 女”一a v g ( 收 西北师范大学硕士论文 基于关系数据库的关联规则挖掘算法研究 入) = 2 3 0 0 ，涉及的收入是数值类型，所以是一个数值型关联规则。 陀) 基于规则中数据的抽象层次，可以分为单层关联规则和多层关联规则。在 单层的关联规则中，所有的变量都没有考虑到现实的数据是具有多个不同的层次 的；而在多层的关联规则中，对数据的多层性已经进行了充分的考虑。 例如：i b m 打印机一s o n y 打印机，是一个细节数据上的单层关联规则；i b m 台式机= s o n y 打印机，是一个较高层次和细节层次之间的多层关联规则。 ( 3 ) 基于规则中涉及到的数据的维数，关联规则可以分为单维的和多维的。在 单维的关联规则中，我们只涉及到数据的一个维：而在多维的关联规则中，要处理 的数据将会涉及多个维。 例如：啤酒一尿布，这条规则只涉及到用户的购买的物品；收入= “2 k 5 k ” 年龄= “3 0 3 9 ”一购买商品= “计算机”，这条规则就涉及到三个维收入、年 龄、购买商品。 将关系型数据库