（计算机软件与理论专业论文）基于数据仓库的关联规则挖掘算法研究.pdf

独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的成果，也不包含为获得西北大学或其他教育机构的学位 或证书而使用过的材料。与我一起工作的同志对本研究所做的任何贡献均已在论 文中做了明确的说明并表示谢意。 学位论文作者签字：勘岛沁签字日期：刀乡年争月2 日 摘要 摘要 关联规则是数据挖掘中的一个比较活跃的分支，它用于发现数据库或数据仓 库中潜在的、对用户感兴趣的信息。本文在分析目前关联规则挖掘算法中存在的 不完善之处的基础上，提出了各种改进方法，取得了一定的效果，研究内容主要 包括： ( 1 ) 引入最优支持度和最优置信度的概念，使得在特定环境1 - - 百t 以挖掘出最 需要的关联规则，产生预期的决策效果。 ( 2 ) 提出了一种改进的关联规则并行挖掘算法，通过减少库扫描次数和减少 候选项目集数目来提高算法的效率。新算法具有较好的扩展性。 ( 3 ) 提出了, f c b d i i 权关联规则的并行挖掘算法，通过给每个项目赋予不同的 权值来标识数据库或数据仓库中项目的不同重要性，使得算法更切合现实，从而 发现用户需要的关联规则。 ( 4 ) 研究了数值属性关联规则的挖掘算法，利用数据本身的特性来划分区间， 然后将划分后的区间映射为布尔属性，最后发现用户感兴趣的关联规则。 理论分析和仿真实验证明了本文中方法的正确性和有效性。 关键词： 数据挖掘；数据仓库：关联规则；并行关联规则；加权关联规则：数 值属性关联规则 a b s t r a c t 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 d p o t e n t i a la n di n t e r e s t e di n f o r m a t i o nf o rc u s t o 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 o nt h eb a s i so fa n a l y z i n gt h ed e f e c to fe 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 m s w e p r o p o s ea s e r i e so fn 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 c e da l g o r i t h m sa n da c h i e v e f a v o c a b l er e s u l t t h em a i nr e s e a r c hw o r k sa r ef o l l o w s ： ( 1 ) t h ec o n c e p to ft h eb e s ts u p p o r ta n dt h eb e s tc o n f i d e n ta r ep u tf o r w a r di n a s s o c i a t i o nr u l e j ic a r lb 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 n c i r c u m s t a n c ea n da t t a i nf a v o r a b l er e s u l to fm 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 y g e t t i n gr i do ft h et i m e so fs c a n n i n gd a t a b a s e so rd a t aw a r e h o u s e sa n dt h en u m b e ro f c a n d i d a t ei t e m s ，w ec a ne n h a n c et h e e 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 e e x t e n s i t yo fn e wa l g o r i t h mi sb 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 n o r d e rt om 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 t w e i g h tv a l u es ot 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 s o rd a t aw a r e h o u s e s i nt h i s w a y , w em a yd i s c o e rt h eu s e f u la s s o c i a t i o nr u l e sf o r c u s t o m s ， f 4 ) a na l g o r i t h mo fm i n i n g 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 si sp u tf o r w a r d q u a n t i t a t i v ea 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 r d i s t r i b u t i o ni nt h ed 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 c i 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 t l 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 ea s s o c i a t i o nr u 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 e m e t h o d sa 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 u l e ； w e i g h t e da 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 年代有了突飞猛进的发展， 特别是在关联规则与聚类方面，取得了很大的成果。 数据挖掘任务一般可以分为两类：描述和预测。描述性挖掘任务刻划数据库 中数据的一般特性；预测r | 生挖掘任务在当前数据上进行推断，以进行预测。 通常，一个典型的数据挖掘过程可以分为三个阶段： 1 数据预处理：这是数据挖掘的前期工作，由于现实世界的数据库存在不 完整的、含噪声的和不一致的数据，因此必须对这些原始数据进行加工处理， 具体如下： ( 1 ) 数据清理：填充数据库中空缺的值，识别孤立点，清除噪声，并纠正 数据中的不一致。 ( 2 ) 数据集成：将多个数据源中的数据结合起来存放在一个一致的数据存 储中。 第一章绪论 ( 3 ) 数据转换：利用平滑、聚集、数据概化、规范化和属性构造等技术将 原始数据转换成合适于挖掘的形式。 ( 4 ) 数据缩减：利用数据立方体聚集、维归约、数据压缩、数值压缩、离 散化和概念分层等技术得到原始数据集的缩减表示，它比原始数据库小的多，但 仍然几乎保持原数据库的完整性，使得在其上挖掘更有效。 2 数据建模和评估：这是数据挖掘的核心部分，目前的大部分研究都集中 在数据挖掘算法和应用上。理论上可以把模型按功能分为描述型和预测型，但在 实际应用中，往往会根据实际作用而分类，下n u 介绍几种常用的模型。 ( 1 ) 关联规则模型：即寻找给定数据集。 j 项之间的有趣联系并用关联烈则 的模型描述给用户。 关联规则是形如爿jy 的蕴含式，其中x ，y 为属性一值对集( 或称为项目 集) ，且x n1 7 为空集。在数据库中，若j 的实例同时包含x 和n 则关联规则 jy 的支持度为s ：若c 的包含属性一值对集的事务也包含属性值集h 则关联规则a 7 y 的置信度为c 。如下关联舭则： c o m p u t e rj s y s t e ms 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 ) ；其中x 表示字段值，c 表示类别。 第一章绪论 目前，比较流行的分类算法有决策树、b a y e s 、后向传播分类等，对于这些 算法构造的模型通常用准确性来进行衡量，度量合格后提供给用户。 ( 3 ) 聚类模型：按照某个特定标准( 通常采用某种距离算法) 将数据对象 分成多个类或簇，在同一个簇中的对象之间具有较高的相似度，而在不同的簇中 的对象差别较大。直观的说，最终形成的每个聚类在空间上都是一个稠密的区域。 聚类是典型的无指导学习算法。 聚类中最常用的几种方法有划分方法、层次方法和基于网格的方法。划分方 法是给定一个包含n 个对象的数据库以及要生成的类的数目足，用某算法将数 据对象组织为足个划分( k ”) ，其中每个划分代表一个类，典型的有芷一平均 和k 一中心点方法。划分方法是基于距离( 欧氏距离，曼哈坦距离和明考斯基距 离) 的度量方法，采用平方误差准则来评估聚类模型：层次方法是将数据对象组 织成一棵聚类的树，根据层次分解是自底向上还是白顶向下形成，典型的b r l c h 和c u r e 方法就属于层次方法的范畴；基于网格的方法通常采用一个多分辨率的 网格数据结构，它将空间量化为有限数目单元，这些单元形成了网格结构，所有 的聚类操作都在网格上进行。在实际应用中有s i n g ( 统计信息网格) 和 w a v e c l u s t e r ( 小波变换聚类) 等方法。 聚类模型的质量是基于对象相异度来评估的，相异度可以对多种类型的数据 进行计算，包括区间标度变量、二元变量、标称变量、序数型变量和比例标度型 变量以及这些变量的组合。 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 l 提出关联规则挖掘以来，有关关 联规则的期刊论文和会议论文每年都有数百乃至上千篇这些文献主要是在现有 理论的基础h 从某个方面对关联规则进行不同形式的改进，并且有针对性地用 于解决某类实际问题。下面从几个方面进行讨论： 1 冗余性 这一问题彳i 仪存在于有内在联系的数据库之间，在由传统算法生成的关联规 则之间也存在着大量的冗余规则。如何解决这世规则之间的冗余性成为众多专家 学者所关注和探讨的焦点。这方面的算法在国内有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 ) 2 1 。 2 多维性 在数据仓库建立起来以后，随着数据的不断增多，带有某种关联属性的谓词 数量也随之增多。如我们发现布尔关联规则“，b md 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 k ：r ( x ，“i b m d e s k t o pc o m p u t e r ”) j b y s ( x , “勋砂b w p r i n t e r ”) 在这里，是变量，代表购物的顾客。若我们把每个不同的谓词称作维，那么我 们称上面的规则为单维规则( s i n g l e - d e m e n s i o nr u l e ) 或维内关联规则 ( i n t r a d i m e n s i o na s s o c i a t i o nr 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 t 3 0g e n m l r u l e s 钔。 3 分布性( 并行性) 理论上，我们通常把挖掘关联规则看成是在一个大型数据仓库中进行的，而 在实际操作中却经常会遇到这样的情况，一个完整的数据仓库或数据库被分成若 干子库放在不同的地方，这些计算机有的是“端对端”相连，有的则没有物理连 接。在这些数据仓库上要进行数据挖掘是极具挑战性的一项任务。但仍有许多研 第一章绪论 究者取得了一定的研究成果，有c d ”，d d t ”，c a d ，f d m “，d d m ，p d d m ， d d d m l 。 4 加权性 在同数据仓库内，不同的项目往往有着刁i 同的重要性，这儿乎是现实世界 数据仓库的内在特征。为了反映各个项目的不同重要性，使之更切合实际情况， 就需要一个项目权值。这样就更有利丁挖掘有价值的关联规则。这方面的算法有 d w a r 8 1 。 5 多层性 对于许多应用由于多维数据空问数据的稀疏性，在低层或原始层的数据项 之问很难找出强关联规则。在较高的概念层发现的关联规则可能提供普遍意义的 知识。然而，对一个用户代表普遍意义的知识，对另一个用户可能是新颖的。这 样，数据挖掘系统就应当提供一种能力，在多个抽象层挖掘关联规则，并容易在 f ；同的抽象空间转换。多层关联规则挖掘存h a n 和f u h f 9 5 ，s r i k a n t 和 a g r a w a l s a 9 5 中研究。在s r i k a n t 和a g r a w a l s a 9 5 中，这种挖掘以概化关联规 则的形式研究，并提出r 一兴趣度度量，以删除冗余规则。 1 3 论文研究的意义和所做的主要工作 本文是在陕西省自然科学基金大型数据库中的数据挖掘算法研究与陕西 省教委重点科研计划项目基于并行优化算法的智能数据挖掘模型的研究的基 础上进行研究的。 关联规则是数据挖掘中比较重要的一部分，也是目前发展比较成熟的一个分 支。它可以帮助企业管理人员正确分析市场并做出明智的决策。为了使关联规则 更好地服务于企业管理人员，本文针对关联规则现有研究状况，提出了新的概念 和相关算法，主要研究内容包括： 1 在可信度和支持度上提出了在特定条件下的优化，并给出算法。 2 为提高挖掘效率引入了并行的概念。 3 鉴于数据库中项目的不同重要性，引入权值的概念并给出了并行算法。 4 对数值连续属性的关联规则问题，引入了不采用平均划分数值属性来挖 第一章绪论 掘规则的一点思想，同时给出了算法框架。 1 4 本文内容安排 本文在对人量相关文献资料进行研究的基础上，针对现有的关联规则挖掘算 法的不足，提出几种改进的算法。本文内容安排蜘1 下： 第一章绪论介绍了数据挖掘产生的背景及其挖掘的几种类型，重点提出 丁关联规则挖掘算法以及目前的发展概况，新算法研究的意义和方向以及本文所 完成的主要工作。 第二章数据仓库简述关联规则算法的操作平台数据仓库的基本概念、原 理、和实现方法。着重介绍数据仓库及其在数据挖掘中的应用，进一步分析和讨 论了数据挖掘中一些基本技术。 第三章关联规则的并行挖掘算法介绍了关联规则的基本定义，类型，各 种类型的现有研究状况，同时，在a p r i o r i 算法的基础上提出了布尔关联规则的 优化方案并给出其优化并行算法框架。 第四章加权关联规则的并行挖掘算法由于数据仓库中各项的分布不均现 象相当频繁，且其重要性也并非相同，因此，为了体现各项目的不同重要性，我 们存关联规则的基础上引入了权值的概念。另外，随着分布式技术的发展，传统 的串行操作已经显得力不从心，这卑提出了并行的概念，使得算法更具扩展性。 第五章数值型关联规则的挖掘算法关联规则可以分为逻辑关联规则和数 值关联规则两类。本章讨论了包含数值属性的大型关系数据库中关联规则发现的 问题，针对平均划分数值属性值域区间存在的缺陷，采用以支持度为基础的方法， 根据数据本身的特征来决定基本区间的大小和数目，并对相邻基本区间进行了必 要的合并，从而将数值属性转化为逻辑属性，最后给出算法框架。 第六章结论与展望总结了在关联规则挖掘方面的初浅研究成果，同时， 就关联规则挖掘目前的研究进展，分析了今后的研究方向。 第二章数据仓库 第二章数据仓库 弟一早 揪惦巳佯 2 1引言 计算机网络与数据库技术的迅速发展和厂泛应用，使得企业管理进入一个崭 新的时代。广大基层管理人员摆脱了繁重的制表业务和数据处理工作，管理工作 得到进一步规范化，许多业务得到了联机事务处理信息的支持。然而，面对当前 竞争日趋激烈与瞬息万变的市场经济，再级管理人员迫切需要面对不同层次的大 量信息迅速作出抉择。这就要求各级管理人员能够从大量复杂的业务数据中获取 各自权限内的决策信息及时把握市场变化的脉搏，作出正确有效的判断和抉择。 特别是随着数据库系统的逐f 1 运行，数据的堆积将越来越大，这种需求就比以往 任何时候都更加迫切。从各级决策者角度来看，数据处理的重点应该从传统的业 务过程扩展到对业务数据的联机分析处理，并从中得到面向各种管理主题的统计 信息和决策支持信息。这就使得数据仓库应用而生。 2 2 数据仓库的基本概念 2 2 1 数据仓库定义 数据仓库为商务运作提供结构与工具，以便系统地组织、理解和使用数据进 行战略决策。大量组织机构已经发现，在当今这个充满竞争和快速发展的世界， 数据仓库是一个有价值的工具，许多公司已花费数百万美元建立企业范围的数据 仓库。 数据仓库是一个面向主题的、集成的、时变的，非易失的数据集合，支持管 理部门的决策过程。这定义指出了数据仓库的主要特征。四个关键词，面向主 题的、集成的、时变的、非易失的，将数据仓库与其他数据存储系统相区别。 1 面向主题的( s u b j e c t o r i e n t e d ) ：数据仓库围绕一些主题，如顾客、供应商、 产品和销售组织。数据仓库关注决策者的数据建模与分析，而不是集中于组织机 构的同常操作和事务处理。因此，数据仓库排除对于决策无用的数据提供特定 第二章数据仓库 主题的简明视图。 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 - l 数据仓库的结构 生产线每月销售 l9 8 l l9 92 子生产线每周销售 1 9 8 4 一1 9 9 2 销售细节级 ( 1 9 9 0 1 9 9 1 ) 销售细节级 ( 1 9 8 4 1 9 8 9 ) 级：早期细节级( 通常是备用的、批量的存储) 、当前细节级、轻度综合数据级( 数 据集市) v 2 及高度综合数据级。数据是由操作型环境导入数据仓库的。相当数量 的数据转换通常发生在由操作型级别向数据仓库级别传输过程中。 一旦数掘过期，就由当前细节级进入早期细节级。综合后的数掘由当前细节 第二章数据仓库 级进入轻度综合数据级，然后由轻度综合数据级进入高度综合数据级。 2 23 数据仓库中的几个重要概念 粒度粒度问题是设计数据仓库的一个最重要的方面。粒度是指数据仓库的 数据单位中保存数据的细化或综合程度的级别。细化程度越高，粒度级就越小： 相反，细化程度越低，粒度级就越大。 在数据仓库环境中粒度之所以是主耍的设计问题，是因为它深深地影响存放 在数据仓库中的数据量的大小，同时影u 曲数据仓库所能回答的查询类型。在数据 仓库中的数据量大小与查询的详细程度之问要作出权衡。 很多时候，十分需要提高存储与访问数据的效率，以及非常详细地分析数据 的能力。当一个企业或组织的数据仓库叶i 拥有大量数据时，在数据仓库的细节部 分考虑双重( 或多重) 粒度是很有意义的。事实上需要多个粒度级而不是一个 粒度级的需求，是因为粒度级设计采用双重级别应该足几乎每个机构默认的选 择。 分割这是数据仓库中数据的第二个主要的设计问题，数据分割是指把数据 分散到各自的物理单元中去，它们能独立地处理。在数据仓库环境中，问题不是 要不要对当前细节数据进行分割，而是怎样对当前细节数据进行分割。对当前细 节数据进行分割的总体目的是把数据划分成小的物理单元。因为小的物理单元能 为操作者和设计者在管理数据时提供比对大的物理单元更大的灵活性。 数据的唯一性：当结构相同的数据被分成多个数据物理单元时，数据便被分 割了。此外，任何给定的数据单元属于且仪属1 二一个分割。 有多种数据分割的标准。如按时间、商业线、地理位置、组织单位等，但在 数据仓库环境中，按日期几乎总是分割标准中的一个必然组成部分。 另外，数据仓库开发人员所面临的主要问题之一是在系统层上还是在应用层 上对数据进行分割。通常，在应用层上分割数据仓库的数据是很有意义的，最重 要的是应用层上每年的数据可以有不同的定义。另一重要特点是它能从一个处理 集转移到另一个处理集而没有损失。在数据仓库环境中，当工作负载和数据量成 为真正的负担时，这种特点就是一种真正的优点。 第= 章数据仓库 o 2 3数据仓库设计 建造数据仓库有两个主要方面一一与操作型系统接口的设计和数据仓库本 身的设计。 ( 1 ) 与操作型系统接口的设计 操作数据库虽然存放了大量数据，但这种库一般不维护历史数据。而决策支 持是需要历史数据的。因此，数据仓库必须与操作数据库分离。 从操作数据库到数据仓库有三种装载工作要做： 1 装载档案数据。 2 装载在操作型系统中目前已有的数据。 3 将自数据库上次刷新以来在操作操作型环境中不断发生的变化( 更新) 从操作型环境中装载到数据仓库中。 ( 2 ) 数据仓库本身的设计 数据仓库的设计始于数据模型，即数据模型是设计数据仓库的基础。企业数 据模型用于操作型环境的设计。企业数据模型的一种变型用于数据仓库的设计。 有三个层次的数据建模：高层建模( e r d ，实体关系层) ，中间层建模( d i s ， 数据项集) ，底层建模( 物理层) 。 1 高层建模高层建模的特点是实体和关系，如下图，实体的名字放在椭 圆内，实体间的关系用箭头描述。箭头的方向和数量表示关系的基数，只有直接 的关系才标志。这样，关系的传递依赖就可以最小化。 ( 二二) o 卜 1 _ 卜斗 一个椭圆表示一个实体或者主要主题 一个1 ：月的关系 一个l ：】的关糸 一个m ：n 的关系 第二章数据仓库 2 中间层数据模型这是对高层模型中的各个主要的实体都要建一个中间 层模型。如下图所示，对高层数据模型标识的四个实体分别扩展成自己的中间层 模型。 d i s 图2 - 3e r d 和d i s 的关系 中间层模型一般有四个基本的构造 初始数据组即对每个主要主题域存在且只存在一次。 e r d d i s 二次数据组对各个主要主题域可以存在多次，从初始数据组有直线指向 二次数据分组。有几个可以多次出现的不同数据组就含有几个二次数据组。 连接件该部分是将数据从一个组到另一个组联系起来。 数据“类型”由指向右边数据组的线段指示。左边是超类型数据组，右边 是子类型数据组。 初始数据组 二次数据组 图2 - 4 中间层数据模型的四个组成部分 据“类型” 蘑了职 意 第二章数据仓库 这四项用来标识数据模型中的数据属性及其关系。当一个关系在e r d 层标 识以后，在d i s 层就用一对连接件关系来表现。 3 物理数据模型即由中间层数据模型创建，它只是通过包含键码和模型 的物理特性来扩展中问层数据模型而得到的。物理数据模型看上去像一系列表， 这些表有时称做关系表。 总之，建立数据仓库后还必须从宏观和微观上对这个仓库的各个部分进行 反复的测试修改，众所周知，任何开发( 软件) 都不可能在一。丌始达到完美的境 界，必须经过工作人员的反复工作以后才能达到既定的目标。 2 4 分布式数据仓库 大部分企业建立和支持单一的中央数据仓库环境。原因有三： ( 1 ) 数据仓库中的数据是全企业集成的数据，仅在总部使用集成视图。 ( 2 ) 数据仓库中的大量数据使数据的单一的集中式存储具有意义。 ( 3 ) 即使数据能被集成，但是若将它们分布于多个局部结点，则存耿这些 数据也是很麻烦的。 作为存储数据的数据仓库其主要目的是帮助企业管理人员及时地进行市场 决策。可随着企业的不断发展壮大，以及各种子公司的出现，这种中央数据仓库 就显的有点跟不上时代的脚步了，处理数据的复杂性和各子公司的区域性导致了 企j 世管理人员在决策上失去了市场实时性和准确性。因而，建立分布式数据仓库 便成了各大企业的当务之急。 分布式数据仓库有两大优点：一是引入代价低。二是存放在数据仓库中的数 据量理论上无限制。如果数据仓库中的数据量开始超过分布式处理器的能力。那 么我们只要在网络中再加入一个处理器即可。即可实现持续增加数据。但是，管 理和协调分布式数据仓库环境要比管理和协调单一场地的数据仓库复杂的多。 2 5 数据仓库作为数据挖掘的平台，它的建立好坏直接影响到后期各种类型的数 第二章数据仓库 据挖掘算法在其上的使用。因此，数据仓库必须科学、合理地建立。正如数据仓 库之父w h i n m o n 所定义的，数据仓库是一个面向主题的、集成的、不可更新的 且随时间不断变化的数据集合，用来支持管理人员的决策。只有这样，数据仓库 才能满足不断发展的市场的需求。 第三章关联规则的并行挖掘算法 第三章关联规则的并行挖掘算法 3 1引言 数据丰富和知识贫乏是信息时代发展所带给人们的新问题，数据挖掘( d a t a m i n i n g ) 技术一是在这样的背景下产乍和发展起来的，其中最活跃的研究方向应 是关联规则( a s s o c i a t i o nr u l e ) 挖掘。 3 2 1 关联规则定义 3 2 基本概念 设= i l , i 2 ，- i 。 是项的集合，设任务相关的数据d 是数据库事务的集合， 其中每个事务t 是项的集合，使得t e l 。每一个事务有一个标识符，称作t i d 。 设a 是一个项集，事务7 1 包含爿当且仅当a t 。关联规则是形如a b 的蕴涵 式，其中a c ，b c l ，并且a n 口= o 。规则a j b 在事务集d 中成立，具有支 持度s ，其中s 是d 中事务包含a j 日( 即a 和b 二者) 的百分比，它是概率 尸( 爿u b ) ，设m i n s u p 为最小支持度，若s m i r l s t t p ，则称项集为频繁项集( f r e q u e n t i t e m s e t ) ：规则a j b 在事务d 中具有置信度n 如果d 中包含a 的事务同时也 包含曰的百分比是c ，这是条件概率尸( 爿ib ) ，即是 s u p p o r t ( aj 团= 尸( 爿ub ) c o n f i d e n c e j 研= p ( b la ) 同时满足最小支持度阈值加j 嘲和最小置信度阈值f ”啊c o 研的规则称作 强规则。通常，为方便计，我们用o 和1 0 0 之间的值来表示支持度和置信度， 而尽量避免用0 到l 之间的值表示。 项的集合称为项集( i t e m s e t ) ，包含k 个项的项集称为t 一项集。集合 c o m p u t e r ， f i n a n c i a l _ m a n a g e m e n t _ s o f t w a r e ) 是一个2 一项集。项集的出现频率是包含项集的 事务数，简称为项集的频率、支持计数或计数。项集满足最小支持度r a i ns u p ， 第三章关联规则的并行挖掘算法 如果项集的出现频率大于或等于r a i ns u p 与d 中事务总数的乘积。如果项集满足 最小支持度，则称它为频繁项集( f r e q u e n ti t e m s e t ) 。频繁女一项集的集合通常记 作 从大型数据库中挖掘关联规则一般有以下两步： 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 ) 。如果规则描述的是量化的项的属 性之l 刈的关联，则它是量化关联规则( 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 ) 。在这种规则 巾，项或属性的量化值划分为区f b j 。 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 0 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 9 ”) jb u y s ( x ， c o m p u t e r ”) 在以上规则巾，购买的商品涉及不同的抽象层( 即“c o m p u t e r ”在比“i a p t o p 第三章关联规则的井行挖掘算法 6 c o m p u t e r ”高的抽象层) 。我们称所挖掘的规则集由多层关联规则( m u l t i l e v e l a s s o c i a t i o nr u l e ) 组成。反之，如果在给定的规则集中，规则不涉及不同抽象层的 项或属性，则该集合包含单层关联规t ( 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 r i o r i 算法，即使用候选项集来找频繁项集。它采用一种称作迓层搜索的迭代方法，k 项集用于探索( 肛1 ) 一项集。首先，找出频繁1 - 项集的集合。该集合已作三i 。三i 用 于找频繁2 一项集的集合三2 ，而2 用于找l 3 ，如此下去，直到不能找到频繁k 项 集。找每个“需要一次数据库扫描。 a p r i o r i 算法的理论基础：频繁项集的所有非空子集必须也是频繁的。 其算法如卜： 输入：事务数据库d ；最小支持度阈值m i ns u p 输出：d 中的频繁项集三 上1 2 矗n d - f r e q u e n t _ i t e m s e t s ( d ) ； f o r ( k = - 2 ： i 巾：女+ 十) c k 2 a p r i o r i _ g e n ( l k l ，m i n s u p ) ： f o re a c ht r a n s a c t i o n ，d f c t = s u b s e t ( g ，) ； f o re a c hc a n d i d a t e c c ， cc o u n t + + ： 第三章关联规则的并行挖掘算法 产 c c kc c o u n t 一m i n _ s u p ) ) r e t u r nl = u 止 ； p r o c e d u c ea p r i o r i g e n ( l k - 1 ：f r e q u e n t ( k - 1 ) 一i t e m s e t sm i ns u p ：m i m n u 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 t l 一i f o re a c hi t e m s e t ，2e i i i f ( 1 = 2 1 1 】) 八( 2 = 1 2 1 2 】) a 八k - 2 1 = 6 k - 2 ) t h e n c = l l 。1 2 i fh 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 ea d dc t o q ； ) r e t u r nq ； p r o e e d u c eh a s i n f r e q u e n t _ s u b s e t ( c ：c a n d i d a t ek - i t e m s e t ；l k 、：f r e q u e n t ( 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 e l k - it h e n r e t u r nt u r e ： r e t u r nf a l s e ； 2 多层关联规则：可以根据每个抽象层上的最小支持度阈值如何定义，使 用多种策略挖掘。当在较低层使用递减的支持度时，剪枝方法包括层交叉按单项 过滤，层交叉按k - 项集过滤。冗余的多层( 后代) 关联规则可以删除，不向用户提 供，如果根据其对应的祖先规则。它们的支持度和置信度接近于期望值的话。 3 多维关联规则：可以根据对量化属性处理分为若干类。第一，量化属性 可以根据预定义的概念分层静态散化。数据立方体非常适用这种方法。第二，可 以挖掘量化关联规则，其量化属性根据分箱动态离散化，其中“i 临近的”关联规 则可以用聚类组合。第三，可以挖掘基于距离的关联规则，其中区间根据聚类定 第三章关联规则的并行挖掘算法 义。 3 5关联规则优化 3 5 1 关联规则的形式描述 作者进行关联规则挖掘的目的是要找出正常的企、比经营中相关的冈素及对 企业经营结果的影响。即要求效率高，同时又要使发现的舰则有用，及时准确地 反映出目前的实际情况，f 确地指导企业生产，最大限度地舍弃没有价值的规则， 保留那些可信度的支持度较高的有价值的规则，即挖掘那些最优规则。例如对于 规则收入一购买产品s a l a r y v l ，v 2 】c u s t o m = 1 ，即收入在某一范围 v 1 v 2 】的工作 人员至少p 的可能成为购买公司产品的客户，目的在于要确定这个范围以便在 此范刚内火力发展客户，提高企业效益。总的来说，有两种思路：一是可信度大 j 二等于某个阈值，二是支持度大于等于某个阈值，