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

基于数据仓库的关联规则挖掘算法研究 摘要 关联规则是数据挖掘中的一个比较活跃的分支，它用于发现数据库或数据仓库中潜 在的、对用户感兴趣的信息。本文在分析目前关联规则挖掘算法中存在的不完善之处的 基础上，提出了各种改进方法，取得了一定的效果，研究内容主要包括： ( 1 ) 引入最优支持度和最优置信度的概念，使得在特定环境下可以挖掘出最需要的 关联规则，产生预期的决策效果。 ( 2 1 提出了一种改进的关联规则并行挖掘算法，通过减少库扫描次数和减少候选项 目集数目来提高算法的效率。新算法具有较好的扩展性。 ( 3 1 提出了一种加权关联规则的并行挖掘算法，通过给每个项目赋予不同的权值来 标识数据库或数据仓库中项目的不同重要性，使得算法更切合现实，从而发现用户需要 的关联规则。 ( 4 ) 研究了数值属性关联规则的挖掘算法，利用数据本身的特性来划分区问，然后 将划分后的区间映射为布尔属性，最后发现用户感兴趣的关联规则。 理论分析和仿真实验证明了本文中方法的正确性和有效性。 关键词；数据挖掘，数据仓库，关联规则，并行关联规则，加权关联规则，数值属性 关联规则 r e s e a r c ho f a l g o r i t h e mo fm i n i n ga s s o c i a t i o nr u l eb a s e do nd a t a w a r e h o u s e q i a oy o n g s h e n g ，c h e n l i c h a o a b s t r a c t a s s o c i a t i o nr u l ei so n eo fa c t i v ep a r to fd a t am i n i n g i th a sb e e nu s e dt of i n dp o t e n t i a l a n di n t e r e s t e di l f f o r m a t i o nf o rc u s t o m e r sf r o md a t a b a s e so rd a t aw a r e h o u s e s o nt h eb a s i so f a n a l y z i n gt h ed e f e c to f e x i s t i n ga s s o c i a t i o nr u l ea l g o r i t h n l s ，w ep r o p o s e as e r i e so f n o v e li d e a s ， r e a l i z es e v e r a la d v a n t e da l g o r i t h m sa n da c h i e v ef a v o r a b l er e s u l t t h em a i nr e s e a r c hw o i k s a r ef o l l o w s ： ( 1 ) t h ec o n c e p to f t h eb e s ts u p p o r ta n dt h eb e s tc o l t f i d e n ta r ep u tf o r w a r di na s s o c i a t i o n r u l e i tc a nb eu s e dt om i n et h em o s tu s e f u la s s o c i a t i o nr u l e si nt h ec e r t a i nc i r c u m s t a n c ea n d a t t a i nf a v o r a b l er e s u l to f m a k i n gd e c i s i o n ( 2 ) a na d v a n c e da l g o r i t h mo fm i n i n gp a r a l l e la s s o c i a t i o nr u l e si sp r o p o s e d b yg e t t i n g r i do f t h e t i m e so fs c a n n i n gd a t a b h s e so r d a t a w a r e h o u s e s a n d t h e n u m b e r o f c a n d i d a t e i t e m s ， w ec a l le n h a n c et h ee f f i c i e n c yo ft h ea l g o r i t h m m o r e o v e r , t h ee x t e n s i t yo fn e wa l g o r i t h mi s b e t t e rt h a no t h e r s ( 3 ) ap a r a l l e la l g o r i t h mf o rm i n i n gw e i g h t e da s s o c i a t i o nr u l e si sp r o p o s e d i no r d e rt o m a k et h ea l g o r i t h mc o r r e s p o n dw i t ht h er e a l i t y , w eo f f e re a c hi t e mad i f f e r e n tw e i g h tv a l u es o t h a ti tc a nr e p r e s e n tt h ei m p o r t a n c eo fi n d i v i d u a li t e m sf r o md a t a b a s e so rd a t aw a r e h o u s e s i n t h i sw a y , w em a yd i s c o v e rt h eu s e f u la s s o c i a t i o nr u l e sf o rc u s t o m s ( 4 ) a 1 la l g o r i t h mo fm i n i n gq u a n t i t a t i v ea s s b c i a t i o nr u l e si sp u tf o r w a r d q u a n t i t a t i v e a t t r i b u t ev a l u e sa r ep a r t i t i o n e di n t ob a s i ci n t e r v a l sa c c o r d i n gt ot h e i rd i s t r i b u t i o ni nt h e d a t a b a s e so rd a t aw a r e h o u s e s ，a n di fp o s s i b l e ，t h ea d j a c e n tb a s i ci n t e r v a l sw i l lb em e r g e d ， t h e nt h ei n t e r v a l sa r em a p p e di n t ob o o l e a na t t r i b u t e s a tl a s t ，g e n e r a li n t e r e s t i n gq u a n t i t a t i v e a s s o c i a t i o nr o l e sc a nb em i n e d t h e o r ya n a l y s i sa n ds i m u l a t i o nr e s u l t sf o rd a t as h o wt h er e s u l tb a s e do nt h e s em e t h o d s a r ei m p r o v e dm u c hm o r et h a nn o r m a la l g o r i t h m s k e y w o r d s ：d a t am i n i n g ；d a t aw a r e h o u s e ；a s s o c i a t i o nr u l e ；p a r a l l e la s s o c i a t i o nr o l e ；w e i g h t e d a s s o c i a t i o nr u l e ；q u a n t i t a t i v ea s s o c i a t i o nr u l e 原创性声明 本人郑重声明：所呈交的学位论文，是本人在指导教师的指导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不包含 其他个人或集体已经发表或撰写过的科研成果。对本文的研究作出重要贡 献的个人和集体，均已在文中以明确方式标明。本声明的法律责任由本人 承担。 论文作者签名：叠堑丝日期：趣= 墨：丝 关于学位论文使用权的说明 本人完全了解中北大学有关保管、使用学位论丈的规定，其中包括： 学校有权保管、并向有关部门送交学位论文的原件与复印件；学校可 以采用影印、缩印或其它复制手段复制并保存学位论文；学校可允许学 位论文被查阅或借阅；学校可以学术交流为目的，复制赠送和交换学位 论文；学校可以公布学位论文的全部或部分内容( 保密学位论文在解密 后遵守此规定) 。 签名： 导师签名： 日期型望墨丝 中北大学学位论文 1 1 研究背景和意义 第一章绪论 在过去的数十年中，我们产生和收集数据的能力已经迅速提高，起作用的因素包括 条码在大部分商业产品中的广泛使用，许多商务、科学和行政事务的计算机化，以及由 文本和图像扫描平台到卫星遥感系统的数据收集工具的进步。此外，作为全球信息系统 的万维网的流行，已经将我们淹没在数据和信息的汪洋大海中。人们没有时间看数据， 人类的关注已经成为一种宝贵的资源。而且，存储数据的爆炸性增长业已激起对新技术 和自动分析工具的需求，以便帮助我们将海量数据转换成信息和知识。 数据挖掘就是为了解决上述问题而产生的研究领域。数据挖掘为知识发现提供手 段，可以从巨量的数据集合中抽取隐含的、先前未知的、对决策有潜在价值的规则川。 数据挖掘是一个多学科领域，从多个学科汲取营养，包括数据库技术、统计学、机器学 习、高性能计算、模式识别、神经网络、数据可视化、信息检索、图象与信号处理和空 间数据分析。数据挖掘的主要类型有关联规则，序列模式，分类以及聚类。它出现于 2 0 世纪8 0 年代后期，9 0 年代有了突飞猛进的发展，特别是在关联规则与聚类方面，取 得了很大的成果。 数据挖掘任务般可以分为两类：描述和预测。描述性挖掘任务刻划数据库中数据 的一般特性；预测性挖掘任务在当前数据上进行推断，以进行预测。 通常，一个典型的数据挖掘过程可以分为三个阶段： 1 数据预处理：这是数据挖掘的前期工作，由于现实世界的数据库存在不完整的、 含噪声的和不一致的数据，因此，必须对这些原始数据进行加工处理，具体如下： ( 1 ) 数据清理：填充数据库中空缺的值，识别孤立点，清除噪声，并纠正数据中 的不一致。 ( 2 ) 数据集成：将多个数据源中的数据结合起来存放在一个下致的数据存储中。 ( 3 ) 数据转换：利用平滑、聚集、数据概化、规范化和属性构造等技术将原始数 据转换成适合于挖掘的形式。 中北大学学位论文 ( 4 ) 数据缩减：利用数据立方体聚集、维归约、数据压缩、数值压缩、离散化和 概念分层等技术得到原始数据集的缩减表示，它比原始数据库小的多，但仍然几乎保持 原数据库的完整性，使得在其上挖掘更有效。 2 数据建模和评估：这是数据挖掘的核心部分，目前的大部分研究都集中在数据 挖掘算法和应用上。理论上可以把模型按功能分为描述型和预测型，但在实际应用中， 往往会根据实际作用而分类，下面介绍几种常用的模型。 ( 1 ) 关联规则模型：即寻找给定数据集中项之间的有趣联系并用关联规则的模型 描述给用户。 关联规则是形如x 等y 的蕴含式，其中兄y 为属性一值对集( 或称为项i i 集) ，且 x n y 为空集。在数据库中，若s 的实例同时包含x 和l 则关联规则j j y 的支持度 为s ；若c 的包含属性一值对集x 的事务也包含属性一值集y ，则关联规则盖j y 的 置信度为c 。如下关联规则： c o m p u t e r s y s t e m _ s o f t w a r e s u p p o r t = 2 0 ，c o n f i d e n c e = 6 0 该关联规则表示分析数据库中实例的2 0 ( 支持度) 同时购买计算机和系统软件且数 据库中所有购买计算机的顾客6 0 ( 置信度) 也购买系统软件。 在数据建模中，基于预处理数据的关联规则是很多的，而且绝大多数对用户是没用 的。为了在建模过程中提高模型在实际应用中的准确性，通常，我们用最小支持度和置 信度来衡量关联规则，只有支持度和置信度分别大于用户指定的最小值的关联规则才是 符合要求的关联规则模型。需要注意的是最小支持度和置信度的设定是由用户或领域专 家设定的。 ( 2 ) 分类模型：即利用分类算法对数据进行建模。分类的目的是学会一个分类函 数或分类模型( 也常称作分类器) ，该模型能把数据库中的数据项映射到某个给定的类 上，分类的输出是离散的类别值。 要构造分类器，需要有一个训练样本数据集作为输入，训练集由一组数据库记录或 元组构成，每个元组是一个由有关字段( 又称属性或特征) 值组成的特征向量，此外， 训练样本还有一个类别标记。一个具体样本的形式可为：( 蜀，蜀，五；c ) ；其中 表示字段值，c 表示类别。 目前，比较流行的分类算法有决策树、b a y e s 、后向传播分类等，对于这些算法构 2 中北大学学位论文 造的模型通常用准确性来进行衡量，度量合格后提供给用户。 ( 3 ) 聚类模型：按照某个特定标准( 通常采用某种距离算法) 将数据对象分成多 个类或簇，在同一个簇中的对象之间具有较高的相似度，而在不同的簇中的对象差别较 大。直观的说，最终形成的每个聚类在空间上都是一个稠密的区域，聚类是典型的无指 导学习算法。 聚类中最常用的几种方法有划分方法、层次方法和基于网格的方法。划分方法是给 定一个包含n 个对象的数据库以及要生成的类的数目世，用某一算法将数据对象组织为 k 个划分( 足n ) ，其中每个划分代表一个类，典型的有k 一平均和k 一中心点方法。 划分方法是基于距离( 欧氏距离，曼哈坦距离和明考斯基距离) 的度量方法，采用平方 误差准则来评估聚类模型；层次方法是将数据对象组织成一棵聚类的树，根据层次分解 是自底向上还是自顶向下形成，典型的b r i c h 和c u r e 方法就属于层次方法的范畴； 基于网格的方法通常采用一个多分辨率的网格数据结构，它将空间量化为有限数目单 元，这些单元形成了网格结构，所有的聚类操作都在网格上进行。在实际应用中有s i n g ( 统计信息网格) 和w a v e c l u s t e r ( 小波变换聚类) 等方法。 聚类模型的质量是基于对象相异度来评估的，相异度可以对多种类型的数据进行计 算，包括区间标度变量、二元变量、标称变量、序数型变量和比例标度型变量以及这些 变量的组合。 3 模型应用：即把经过评估后的模型应用于对新数据的解释当中去。在应用中， 必须做到数据解释的易理解性，通常采用可视化图形用户界面和知识表示技术，向普通 用户提供隐藏于海量数据中的知识。 本文主要研究的是数据挖掘的基本问题之一关联规则，关联规则是数据挖掘中的一 个重要的研究课题，是目前应用最广泛的一种数据挖掘类型。关联规则已经被广泛地研 究了许多年，主要集中在串行关联规则研究上。通过两个或更多的对象之间的某种特定 的联系，从而抽象出一种特定的模型，这些模型可以帮助管理人员及时把握市场变化的 脉搏，作出正确有效的判断和抉择。 关联规则挖掘发现大量数据中项集之问的有趣的关联或相关联系。随着大量数据不 停地收集和存储，许多业界人士对于从他们的数据库中挖掘关联规则越来越感兴趣。从 大量商务事务记录中发现有趣的关联关系，可以帮助许多商务决策的制定，如分类设计、 3 中北大学学位论文 交叉购物和贱卖分析等。 1 2目前研究现状及发展方向 自从a g r a w a l ，i m i e l i n s k i 和s w a m i a i s 9 3 b 提出关联规则挖掘以来，有关关联规则 的期刊论文和会议论文每年都有数百乃至上千篇，这些文献主要是在现有理论的基础 上，从某个方面对关联规则进行不同形式的改进，并且有针对性地用于解决某类实际问 题。下面从几个方面进行讨论： 1 冗余性 这一问题不仅存在于有内在联系的数据库之间，在由传统算法生成的关联规则之间 也存在着大量的冗余规则。如何解决这些规则之间的冗余性成为众多专家学者所关注和 探讨的焦点。这方面的算法在国内有g n r r ( g e n e r a t e n o n r e d u n d a n t r u l e s ) f2 1 。 2 多维性 在数据仓库建立起来以后，随着数据的不断增多，带有某种关联属性的谓词数量也 随之增多。如我们发现布尔关联规则“i b m d e s k t o pc o m p u t e r = s o n yb w p r i n t e r ”，它也 可以写成： b u y s ( x , “i b m d e s k t o pc o m p u t e r ”) j b u y s ( x , “s o n yb w p r i n t e r ” 在这里，x 是变量，代表购物的顾客。若我们把每个不同的谓词称作维，那么我们称上 、 面的规则为单维规贝f l ( s i n g l e d e m e n s i o nr u l e ) 或维内关联规t ( i n t r a d i m e n s i o na s s o c i a t i o n r u l e ) 。但在实际应用中，仅仅依靠单维规则是远远不够的，大多数情况下需要涉及到多 维关联规则甚至混合维关联规则。在这方面研究的算法有e a p r i o r i ，e h a p r i o r i ， a a p r i o r i 3 1 ，g e nm lr u l e s “。 3 分布性( 并行性) 理论上，我们通常把挖掘关联规则看成是在一个大型数据仓库中进行的，而在实际 操作中却经常会遇到这样的情况，一个完整的数据仓库或数据库被分成若干子库放在不 同的地方，这些计算机有的是“端对端”相连，有的则没有物理连接。在这些数据仓库 上要进行数据挖掘是极具挑战性的一项任务。但仍有许多研究者取得了一定的研究成 果，有c d 5 1 ，d d ”，c a d ，f d m 6 1 ，d d m ，p d d m ，d d d m i ”。 4 中北大学学位论文 4 加权性 在同一数据仓库内，不同的项目往往有着不同的重要性，这几乎是现实世界数据仓 库的内在特征。为了反映各个项目的不同重要性，使之更切合实际情况，就需要一个项 目权值，这样就更有利于挖掘有价值的关联规则，这方面的算法有d w a r 8 1 。 5 多层性 对于许多应用，由于多维数据空间数据的稀疏性，在低层或原始层的数据项之间很 难找出强关联规则。在较高的概念层发现的关联规则可能提供普遍意义的知识。然而， 对一个用户代表普遍意义的知识，对另一个用户可能是新颖的。这样，数据挖掘系统就 应当提供一种能力，在多个抽象层挖掘关联规则，并容易在不同的抽象空间转换。多层 关联规则挖掘在h a r t 和f u h f 9 5 ，s d k a n t * n a g r a w a l s a 9 5 q b 研究。在s r i k a n t 和a g r a w a l s a 9 5 q u ，这种挖掘以概化关联规则的形式研究，并提出r 一兴趣度度量，以删除冗余 规则。 1 3 论文研究的意义和所做的主要工作 本文是在山西省自然科学基金大型数据库中的数据挖掘算法研究与山西省教育 厅重点科研计划项目基于并行优化算法的智能数据挖掘模型的研究的基础上进行研 究的。 关联规则是数据挖掘中比较重要的一部分，也是目前发展比较成熟的一个分支。它 可以帮助企业管理人员正确分析市场并做出明智的决策。为了使关联规则更好地服务于 企业管理人员，本文针对关联规则现有研究状况，提出了新的概念和相关算法，主要研 究内容包括： 1 在可信度和支持度上提出了在特定条件下的优化，并给出算法。 2 为提高挖掘效率引入了并行的概念。 3 鉴于数据库中项目的不同重要性，引入权值的概念并给出了并行算法。 4 对数值连续属性的关联规则问题，引入了不采用平均划分数值属性来挖掘规则 的一点思想，同时给出了算法框架。 5 中北大学学位论文 1 4 本文内容安排 本文在对大量相关文献资料进行研究的基础上，针对现有的关联规则挖掘算法的不 足，提出几种改进的算法。本文内容安排如下： 第一章绪论介绍了数据挖掘产生的背景及其挖掘的几种类型，重点提出了关联 规则挖掘算法以及目前的发展概况，新算法研究的意义和方向以及本文所完成的主要工 作。 第二章数据仓库简述关联规则算法的操作平台数据仓库的基本概念、原理、和 实现方法。着重介绍数据仓库及其在数据挖掘中的应用，进- 二步分析和讨论了数据挖掘 中一些基本技术。 第三章关联规则的并行挖掘算法介绍了关联规则的基本定义、类型及各种类型 的现有研究状况，同时，在a p r i o l i 算法的基础上提出了布尔关联规则的优化方案并给 出其优化并行算法框架。 第四章加权关联规则的并行挖掘算法由于数据仓库中各项的分布不均现象相当 频繁，且其重要性也并非相同，因此，为了体现各项目的不同重要性，我们在关联规则 的基础上引入了权值的概念。另外，随着分布式技术的发展，传统的串行操作已经显得 力不从心，这里提出了并行的概念，使得算法更具扩展性。 第五章数值型关联规则的挖掘算法关联规则可以分为逻辑关联规则和数值关联 规则两类。本章讨论了包含数值属性的大型关系数据库中关联规则发现的问题，针对平 均划分数值属性值域区间存在的缺陷，采用以支持度为基础的方法，根据数据本身的特 征来决定基本区间的大小和数目，并对相邻基本区间进行了必要的合并，从而将数值属 性转化为逻辑属性，最后给出算法框架。 第六章结论与展望总结了在关联规则挖掘方面的初浅研究成果，同时，就关联 规则挖掘目前的研究进展，分析了今后的研究方向。 6 中北大学学位论文 第二章数据仓库 计算机网络与数据库技术的迅速发展和广泛应用，使得企业管理进入一个崭新的时 代，广大基层管理人员摆脱了繁重的制表业务和数据处理工作，管理工作得到进一步规 范化，许多业务得到了联机事务处理信息的支持。然而，面对当前竞争日趋激烈与瞬息 万变的市场经济，各级管理人员迫切需要面对不同层次的大量信息迅速作出抉择。这就 要求各级管理人员能够从大量复杂的业务数据中获取各自权限内的决策信息，及时把握 市场变化的脉搏，作出正确有效的判断和抉择。特别是随着数据库系统的逐日运行，数 据的堆积将越来越大，这种需求就比以往任何时候都更加迫切。从各级决策者角度来看， 数据处理的重点应该从传统的业务过程扩展到对业务数据的联机分析处理，并从中得到 面向各种管理主题的统计信息和决策支持信息，这就使得数据仓库应运而生。 2 2 数据仓库的基本概念 数据仓库为商务运作提供结构与工具，以便系统地组织、理解和使用数据进行战略 决策。大量组织机构己经发现，在当今这个充满竞争和快速发展的世界，数据仓库是一 个有价值的工具，许多公司已花费数百万美元建立企业范围的数据仓库。 2 2 1 数据仓库定义 数据仓库是一个面向主题的、集成的、时变的、非易失的数据集合，支持管理部门 的决策过程。这一定义指出了数据仓库的主要特征，即四个关键词：面向主题的、集成 的、时变的、非易失的，将数据仓库与其他数据存储系统相区别。 1 面向主题的( s u b j e c t o r i e n t e d ) ：数据仓库围绕一些主题，如顾客、供应商、产品 和销售组织。数据仓库关注决策者的数据建模与分析，而不是集中于组织机构的日常操 作和事务处理。因此，数据仓库排除对于决策无用的数据，提供特定主题的简明视图。 7 中北大学学位论文 2 集成的( i n t e g r a t e d ) ：通常构造数据仓库是将多个异种数据源，如关系数据库、 一般文件和联机事务处理记录集成在一起。使用数据清理和数据集成技术，确保命名约 定，编码结构，属性度量等的一致性。 3 时变的( t i m e - v a r i a n t ) ：数据存储从历史的角度提供信息，数据仓库中的关键结 构隐式地或显式地包含时间元素。 4 非易失的( n o n v o l a t i l e ) ：数据仓库总是物理地分离存放数据，这些数据源于操作 环境下的应用数据。由于这种分离，数据仓库不需要事务处理，恢复和并发控制机制。 通常，它只需要两种数据访问：数据的初始化装入和数据访问。 概言之，数据仓库是一种语义上一致的数据存储，它充当决策支持数据模型的物理 实现，并存放企业战略决策所需信息。数据仓库也常常被看作一种体系结构，通过将异 种数据源中的数据集成在一起而构造，支持结构化和专门的查询、分析报告和决策制定。 2 2 2 数据仓库的结构 数据仓库的结构如下图，该图表明，在数据仓库中数据存在着不同的细节级：早 期细节级( 通常是备用的、批量的存储) 、当前细节级、轻度综合数据级( 数据集市) 以及 高度综合数据级。数据是由操作型环境导入数据仓库的。相当数量的数据转换通常发生 在由操作型级别向数据仓库级别传输过程中。 图2 1 数据仓库的结构 8 中北大学学位论文 一旦数据过期，就由当前细节级进入早期细节级。综合后的数据由当前细节级进入 轻度综合数据级，然后由轻度综合数据级进入高度综合数据级。 2 2 3 数据仓库中的几个重要概念 粒度粒度问题是设计数据仓库的一个最重要的方面。粒度是指数据仓库的数据单 位中保存数据的细化或综合程度的级别。细化程度越高，粒度级就越小；相反，细化程 度越低，粒度级就越大。 在数据仓库环境中粒度之所以是主要的设计问题，是因为它深深地影响存放在数据 仓库中的数据量的大小，同时影响数据仓库所能回答的查询类型。在数据仓库中的数据 量大小与查询的详细程度之间要作出权衡。 很多时候，十分需要提高存储与访问数据的效率，以及非常详细地分析数据的能力。 当一个企业或组织的数据仓库中拥有大量数据时，在数据仓库的细节部分考虑双重( 或 多重) 粒度是很有意义的。事实上，需要多个粒度级而不是一个粒度级的需求，是因为 粒度级设计采用双重级别应该是几乎每个机构默认的选择。 分割这是数据仓库中数据的第二个主要的设计问题，数据分割是指把数据分散到 各自的物理单元中去，它们能独立地处理。在数据仓库环境中，问题不是要不要对当前 细节数据进行分割，而是怎样对当前细节数据进行分割。对当前细节数据进行分割的总 体目的是把数据划分成小的物理单元。因为小的物理单元能为操作者和设计者在管理数 据时提供比对大的物理单元更大的灵活性。 数据的唯一性：当结构相同的数据被分成多个数据物理单元时，数据便被分割了。 此外，任何给定的数据单元属于且仅属于一个分割。 有多种数据分割的标准，如按时间、商业线、地理位置、组织单位等，但在数据仓 库环境中，按日期几乎总是分割标准中的一个必然组成部分。 另外，数据仓库开发人员所面i 临的主要问题之一是在系统层上还是在应用层上对数 据进行分割。通常，在应用层上分割数据仓库的数据是很有意义的，最重要的是应用层 上每年的数据可以有不同的定义。另一重要特点是它能从一个处理集转移到另一个处理 集而没有损失。在数据仓库环境中，当工作负载和数据量成为真正的负担时，这种特点 就是一种真正的优点。 9 中北大学学位论文 2 3 数据仓库设计 图2 2 表现实体和关系 1 0 中北大学学位论文 2 中间层数据模型这是对高层模型中的各个主要的实体都要建一个中间层模型。 如下图所示，对高层数据模型标识的四个实体分别扩展成自己的中间层模型。 d i s 图2 3e r d 和d i s 的关系 e r d d i s 中间层模型一般有四个基本的构造： 初始数据组 即对每个主要主题域存在且只存在一次。 二次数据组对各个主要主题域可以存在多次，从初始数据组有一直线指向二次数 据分组。有几个可以多次出现的不同数据组，就含有几个二次数据组。 连接件该部分是将数据从一个组到另个组联系起来。 数据“类型” 由指向右边数据组的线段指示。左边是超类型数据组，右边是子类 型数据组。 图2 4 中间层数据模型的四个组成部分 据“类型” 肇l ； 碓了驻 户啦 中北大学学位论文 这四项用来标识数据模型中的数据属性及其关系。当一个关系在e r d 层标识以后， 在d i s 层就用一对连接件关系来表现。 3 物理数据模型即由中间层数据模型创建，它只是通过包含键码和模型的物理 特性来扩展中间层数据模型而得到的。物理数据模型看上去像一系列表，这些表有时称 做关系表。 总之，建立数据仓库后，还必须从宏观和微观上对这个仓库的各个部分进行反复的 测试修改，众所周知，任何开发( 软件) 都不可能在一开始达到完美的境界，必须经过 工作人员的反复工作以后才能达到既定的目标。 2 4 分布式数据仓库 大部分企业建立和支持单一的中央数据仓库环境。原因有三： ( 1 ) 数据仓库中的数据是全企业集成的数据，仅在总部使用集成视图。 ( 2 ) 数据仓库中的大量数据使数据的单一的集中式存储具有意义。 ( 3 ) 即使数据能被集成，但是若将它们分布于多个局部结点，则存取这些数据也 是很麻烦的。 作为存储数据的数据仓库其主要目的是帮助企业管理人员及时地进行市场决策。可 随着企业的不断发展壮大，以及各种子公司的出现，这种中央数据仓库就显得有点跟不 上时代的脚步了，处理数据的复杂性和各子公司的区域性导致了企业管理人员在决策上 失去了市场实时性和准确性。因而，建立分布式数据仓库便成了各大企业的当务之急。 分布式数据仓库有两大优点：一是引入代价低，二是存放在数据仓库中的数据量理 论上无限制。如果数据仓库中的数据量开始超过分布式处理器的能力，那么我们只要在 网络中再加入一个处理器即可，即可实现持续增加数据j 但是，管理和协调分布式数据 仓库环境要比管理和协调单一场地的数据仓库复杂的多。 数据仓库作为数据挖掘的平台，它的建立好坏直接影响到后期各种类型的数据挖掘 1 2 中北大学学位论文 算法在其上的使用，因此，数据仓库必须科学、合理地建立。正如数据仓库之父wh i n m o n 所定义的，数据仓库是一个面向主题的、集成的、不可更新的且随时间不断变化 的数据集合，用来支持管理人员的决策。只有这样，数据仓库才能满足不断发展的市场 的需求。 1 3 中北大学学位论文 第三章关联规则的并行挖掘算法 数据丰富和知识贫乏是信息时代的发展所带给人们的新问题，数据挖掘( d a t a m i n i n g l l 技术正是在这样的背景下产生和发展起来的，其中最活跃的研究方向应是关联 规贝t ( a s s o c i a t i o nr u l e ) 挖掘。 3 2 基本概念 关联规则定义为：设，= ix , i 2 ，一- i m ) 是项的集合，设任务相关的数据d 是数据库 事务的集合，其中每个事务t 是项的集合，使得t c _ i 。每一个事务有一个标识符，称 作t i d 。设4 是一个项集，事务，包含4 当且仅当a c _ t 。关联规则是形如a j 口的蕴 涵式，其中a ，b c i , 并且a n b a 。规则a j b 在事务集d 中成立，具有支持度 s ，其中s 是d 中事务包含a j 曰( 即a 和b 二者) 的百分比，它是概率p ( x u 功，设 m i n s u p 为最小支持度，着s - m i n s u p ，则称项集为频繁项集( f r e q u e n ti t e m s e t ) ；规则aj b 在事务d 中具有置信度c ，如果d 中包含a 的事务同时也包含曰的百分比是c ，这是 条件概率p ( ai 曰) ，即是 s u p p o r t ( a = 亨口) 2 p 口u 口) c o n f i d e n c e = ，b ) = 尸( 口l4 ) 同时满足最小支持度阈值( m 觑s 印) 和最小置信度阈值( m i n c o j 5 的规则称作强规 则。通常，为方便计，我们用o 和1 0 0 之间的值来表示支持度和置信度，而尽量避 免用0 到1 之间的值表示。 项的集合称为项集( i t e m s e t ) ，包含k 个项的项集称为七一项集。集合( c o m p u t e r ， 向a n c i a lm a n a g e m e n ts o f t w a r e ) 是- - + 2 一项集。项集的出现频率是包含项集的事务数， 简称为项集的频率、支持计数或计数。项集满足最小支持度m i n _ s u p ，如果项集的出现 1 4 中北大学学位论文 频率大于或等于r a i ns u p 与d 中事务总数的乘积。如果项集满足最小支持度，则称它为 频繁项集( f r e q u e n ti t e m s e t ) ，频繁女项集的集合通常记作k 。 从大型数据库中挖掘关联规则一般有以下两步： 1 找出所有频繁项集：根据定义，这些项集出现的频繁性至少和预定义的最小支 持计数一样。 2 由频繁项集产生强关联规则：根据定义，这些规则必须满足最小支持度和最小 置信度。 以上定义中，支持度表征的是规则的频度，置信度表征的是规则的强度。支持度越 高，说明规则越经常出现，置信度越高，说明规则越可靠。考虑到相关规则的数目可能 相当巨大，所以在探索发现的关联规则的同时，对挖掘过程的效率非常重视，常采用减 少对数据库的搜索次数，适当放松对精确度的限制，通过数据采样极大地提高采掘的效 率。当数据库经常变动时，采用增量更新来防止整个数据库的重新采掘，及对采掘进行 并行化等手段。 3 3 关联规则分类 1 根据规则中所处理的值类型：如果规则考虑的关联是项的在与不在，则它是布 尔关联规则( b o o l e a na s s o c i a t i o nr u l e ) 。如果规则描述的是量化的项的属性之间的关联， 则它是量化关联规则( q 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 ) 。在这种规则中，项或属性的量化值 划分为区间。 2 规则中涉及的数据维：如果关联规则中的项或属性每个只涉及一个维，则它是 单维关联规则( s i n g l e d i m e n s i o n a la s s o c i a t i o nr u l e ) 。如果规则涉及两个或多个维，则它 是多维关联规则( m u l t i d i m e n s i o n a la s s o c i a t i o nr u l e ) 。 3 根据规则集所涉及的抽象层：有些挖掘关联规则的方法可以在不同的抽象层发 现规则。例如，假定挖掘的关联规则集包含下面规则： a g e ( x , 勺仉一3 9 ”) jb u y s ( x , l a p t o pc o m p u t e r ”) a g e ( x , 3 0 一3 91 、jb u y s ( x , c o m p u t e r 。、 在以上规则中，购买的商品涉及不同的抽象层( 即“c o m p u t e r ”在比“如p 印c o m p u t e r ” 1 5 中北大学学位论文 高的抽象层1 。我们称所挖掘的规则集由多层关联规, 1 ( m u l t i l e v e la s s o c i a t i o nr u l e ) 组成。 反之，如果在给定的规则集中，规则不涉及不同抽象层的项或属性，则该集合包含单层 关联规, 1 ( s i n g l e 1 e v e la s s o c i a t i o nr u l e ) 。 4 根据关联挖掘的各种扩充：关联挖掘可以扩充到相关分析，以识别项是否相关， 还可以扩充到挖掘最大模式( 即最大的频繁模式) 和频繁闭项集。最大模式是频繁模式p ， 使得p 的任何真超模式都不是频繁的。频繁闭项集是一个频繁的闭的项集，其中项集c 是闭的，如果不存在c 的真超集c ，使得每个包含c 的事务也包含c 。使用最大模式和 频繁闭项集可以显著地压缩挖掘所产生的频繁项集数。 3 4 关联规则的研究现状 1 单维、单层、布尔关联规则：对于这类关联规则，最典型的算法是a p f i o r i 算法， 即使用候选项集来找频繁项集。它采用一种称作逐层搜索的迭代方法，肛项集用于探索 ( _ 抖1 ) 一项集。首先，找出频繁1 一项集的集合，该集合记作三l ，l l 用于找频繁2 一项集的集 合三2 ，而如用于找三3 ，如此下去，直到不能找到频繁k 项集。找每个厶需要一次数据 库扫描。 a p r i o r i 算法的理论基础：频繁项集的所有非空子集必须也是频繁的。 其算法如下： 输入：事务数据库d ；最小支持度阈值m i n _ s u p 输出：d 中的频繁项集三 l l = f i n d _ f r e q u e n t _ i t e m s e t s ( d ) ： f o r ( 括2 ；l k 1 巾；抖+ ) c k = a p r i o r i _ g e n ( l k 一1 ，m i n _ s u p ) ： f o re a c ht r a n s a c t i o n t e d c t = s u b s e t ( c k ，f ) ： f o re a c hc a n d i d a t ec ec t c c o u r t f + + ： ) 1 6 中北大学学位论文 三女= c gc c o u n t 一m i n _ s u p ) r e t u r n 三= u 正 ； p r o e e d u c ea p r i o r i _ g e n ( l k - 1 ：f i e q u e n t 限1 ) 一i t e m s e t s ；m i n _ s u p ：m i n m t t ms u p p o r t t h r e s h o l d ) f o re a c hi t e m s e ti i 上“1 f o re a c hi t e m s e t 如l k q i f ( t i l l 1 】) ( 1 t 2 = 1 2 1 2 】) 八a 1 k - 2 = 2 陋2 】) t h e n ( c = l l o o ，2 i f h a s _ i n f r e q u e n t _ s u b s e t ( c ，l k - 1 ) t h e n d e l e t ec ； e l s e a d d c t o q ； ) r e t u r ng ； p r o e e d u c eh a s _ i n f r e q u e n ts u b s e t ( c ：c a n d i d a t ek - i t e m s e t ；l , t - i ：f r e q u e m ( k - 1 ) 一i t e m s e t ，) f o re a c h ( k - 1 ) 一s u b s e tso f c i f s 甚l k 1t h e n r e t u r nt u r e ； r e t u r nf a l s e ； 2 多层关联规则：可以根据每个抽象层上的最小支持度阈值如何定义，使用多种 策略挖掘。当在较低层使用递减的支持度时，剪枝方法包括层交叉按单项过滤，层交叉 按k 项集过滤。冗余的多层( 后代) 关联规则可以删除，不向用户提供，如果根据其对应 的祖先规则i 它们的支持度和置信度接近于期望值的话。 3 多维关联规则：可以根据对量化属性处理分为若干类。第一，量化属性可以根 据预定义的概念分层静态散化，数据立方体非常适用这种方法；第二，可以挖掘量化关 联规则，其量化属性根据分箱动态离散化，其中“临近的”关联规则可以用聚类组合； 第三，可以挖掘基于距离的关联规则，其中区间根据聚类定义。 1 7 中北大学学位论文 3 5 关联规则优化 3 5 1 关联规则的形式描述 作者进行关联规则挖掘的目的是要找出正常的企业经营中相关的因素及对企业经 营结果的影响。既要求效率高，同时又要使发现的规则有用，及时准确地反映出目前的 实际情况，正确地指导企业生产，最大限度地舍弃没有价值的规则，保留那些可信度的 支持度较高的有价值的规则，即挖掘那些最优规则。例如对于规则收入一购买产品 s a l a r y v l ，v 2 一c u s t o m = l ，即收入在某一范围 v l ，v 2 的工作人员至少p 的可能成为购买 公司产品的客户，目的在于要确定这个范围以便在此范围内大力发展客户，提高企业效 益。总的来说，有两种思路：一是可信度大于等于某个阈值，二是支持度大于等于某个 阈值，前者称为规则是可信的，后者称为充分挖掘规则。挖掘最优关联规则即是寻找既 可信又充分的规则。对于企业来说，更感兴趣的是可信度大于等于某个值，支持度最大 的情况下即“可能性p 在某一值之上的最大的客户范围”。称这样的规则为最优支持度 规则，或者是对“某收入范围的客户购买公司产品的可能性最大”感兴趣，把这种规则 称为最优可信度规则。 关联规则的基本形式是j ，_ + y ，记为d ，则该规则的支持度定义为s u p ( d ) ，为了涵 盖更多的内容，s u p ( d ) 习印的，而不是s u p ( x a d ，置信度是c o n ( d ) = s u p ( x ay ) s u p ( x ) 。 如企业领域