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

砖8 g 1 9 2 北京交通大学硕士学位论文 摘要 关联规则挖掘是数据挖掘的一个重要研究课题， 其主要任务是发现大 量数据中项集之间的关联。 本论文对基于数据仓库的关联规则挖掘进行了 研究，主要从体系结构和算法方面进行了讨论，包括基本的理论和方法， 以及基于数据立方体的维内和维间关联规则挖掘算法: 对多层关联规则挖 掘和基于约束的关联挖掘也进行了讨论。具体研究内容如下: 1 )对基于数据仓库的关联规则挖掘的系统结构进行了讨论， 设计了 一种集成数据仓库、o l a p 引擎和关联规则挖掘引擎的系统结构。 该结构使得关联规则挖掘引擎与o l a p 引擎相互作用: 关联规则挖 掘引擎不但可对数据仓库中的数据立方体进行关联规则挖掘，也 可对o l a p 的结果进行挖掘; o l a p 引擎可对关联挖掘结果进行o l a p 操作。 2 )对基于数据仓库的关联规则挖掘算法进行了研究，主要集中在如 何利用数据仓库的数据立方体进行有效的关联规则挖掘。提出了 基于数据立方体结构的维内、维间关联规则挖掘算法，针对维间 关联规则，本文结合立方体密度的不同设计了不同的频繁集发现 算法。对基于数据仓库的多层关联规则发现方法也进行了讨论。 3 )讨论了基于约束的关联规则挖掘，主要从数据约束、立方体维/ 层 次约束和规则约束方面进行讨论。对于数据约束和立方体维/ 层 次，首先针对约束条件，选择最小代价的立方体构造算法构造满 足约束条件的立方体，再在此数据量相对较小的立方体上进行挖 掘，从而提高效率。对于规则约束，针对约束的不同种类，提出 了相应的关联规则挖掘方法。 来经作介、 导 必i w h o 勿 全 义公 布 北京交通大学硕士学位论文 4 )设计了基于数据仓库的关联挖掘系统 a r m i n e r ， 它以 s q l s e r v e r 2 0 0 0 为数据仓库平台， 在由a n a l y s i s s e r v i c e s创建的数据立方 体上进行关联规则挖掘。同时 a r m i n e :也实现了对数据仓库中多 维数据进行浏览功能。 关键词数据挖掘、数据仓库、关联规则、o l a p ,频繁集、数据立方体、 维内关联规则、维间关联规则、多层关联规则 北京交通大学硕士学位论文 ab s t r a c t a s s o c i a t i o n r u l e m i n i n g t e c h n o lo g y w h i c h i n t e n d s t o d i s c o v e r a s s o c i a t i o n r e l a t i o n b e t w e e n it e m s i n a l l k i n d s o f d a t a s e t s , i s a n i m p o r t a n t t a s k o f d a t a m i n i n g玩t h i s t h e s i s , w e p u t g r e a t e m p h as i s o n a s s o c i a t i o n m i n i n g b a s e d o n d a t a w a r e h o u s e , m a i n l y i n c lu d i n g i t s b a s i c t h e o r i e s a n d m e t h o d s , t h e a l g o r i t h m s f o r in t e a - d i m e n s i o n a l a s s o c i a t i o n r u l e a n d i n t e r - d i m e n s i o n a l a s s o c i a t i o n r u l e b a s e d o n d a t a c u b e . we a l s o d i s c u s s mu l t i l e v e l a s s o c i a t i o n ru l e m in i n g a n d c o n s t r a i n t s - b as e d a s s o c i a t i o n r u l e m i n i n g . t h e c o n c r e t e r e s e a r c h c o n t e n t s a r e a s f o l l o ws : 1 ) we d i s c u s s t h e s y s t e m a r c h i t e c t u r e o f a s s o c i a t i o n r u l e m i n i n g b a s e d o n d a t a w a re h o u s e , w h i c h i n t e g r a t e s t h e d a t a w a r e h o u s e , o l a p e n g i n e a n d a s s o c i a t i o n m i n i n g e n g i n e . i n t h e s y s t e m a r c h it e c t u r e , a s s o c i a t i o n m i n i n g e n g i n e a n d o l a p e n g i n e in t e r a c t w i t h e a c h o t h e r s i n c e a s s o c i a t i o n m i n in g e n g i n e c a n p e r f o r m ass o c i a t i o n m i n i n g n o t o n l y o n d a t a c u b e o f d a t a w a r e h o u s e b u t a l s o o n t h e o l a p r e s u l t s a n d o l a p e n g i n e c a n p e r f o r m o l a p o p e r a t i o n s o n t h e a s s o c i a t i o n m i n i n g r e s u l t s 2 ) we r e s e a r c h t h e a l g o r i t h m s f o r as s o c i a t i o n r u l e m i n i n g b a s e d o n d a t a w a r e h o u s e , m a i n l y d i s c u s s i n g h o w t o e f f i c i e n t ly m i n e a s s o c i a t i o n rul e s o n d a t a c u b e . w e p r o p o s e t h e a l g o r i t h m s f o r m i n i n g i n t r a - d i me n s i o n a l a s s o c i a t i o n rul e s a n d i n t e r - d i me n s i o n a l a s s o c i a t i o n r u l e s , a n d a c c o r d i n g t o d i ff e r e n t d a t a c u b e d e n s i t y , w e d e s i g n t h e d i ff e r e n t a l g o r i t h ms o f d i s c o v e r i n g fr e q u e n t i t e ms e t s f o r i i i 北京交通大学硕士学位论文 3 ) 4 ) i n t e r - d i me n s i o n a l a s s o c i a t i o n r u l e . we a l s o d i s c u s s t h e me t h o d f o r m i n i n g m u l t i l e v e l a s s o c i a t i o n r u l e s i n d a t a w a r e h o u s e . we d i s c u s s c o n s t r a i n t s - b a s e d a s s o c i a t i o n m i n i n g m a i n l y i n c l u d i n g d a t a c o n s t r a i n t s , d i m e n s i o n / l e v e l c o n s t r a i n t s a n d rul e c o n s t r a i n t s . c o n c e r n i n g d a t a c o n s t r a i n t s a n d d i m e n s i o n / l e v e l c o n s t r a i n t s w e f i r s t l y c r e a t e d a t a c u b e w i t h l e a s t - c o s t a l g o r i t h m s f o r c u b e c o n s t r u c t i o n , a n d t h e n min e o n t h e c u b e w i t h l e s s s i z e , t h u s e f f i c i e n c y i s i m p r o v e d . a c c o r d i n g t o t h e k i n d s o f ru l e c o n s t r a i n t s , w e p r o p o s e c o r r e s p o n d i n g a l g o r i t h m s f o r m i n i n g a s s o c i a t i o n rul e s . we d e v e l o p a d a t a w a r e h o u s e - b a s e d a s s o c i a t i o n m i n i n g s y s t e m c a l l e d a r mi n e r . wi t h s q l s e r v e r 2 0 0 0 a s d a t a w a r e h o u s e p l a t f o r m , a r mi n e r c a n m i n e a s s o c i a t i o n rul e s o n c u b e s c r e a t e d b y a n a l y s i s s e r v i c e s a n d c a n a l s o v i e w mu l t i d i me n s i o n a l d a t a i n d a t a wa r e h o u s e . k e y w o r d s : d a t a m i n i n g , d a t a w a r e h o u s e , a s s o c i a t i o n rul e , o l a p , f r e q u e n t s e t , d a t a c u b e , i n t r a - d i m e n s i o n a l a s s o c i a t i o n r u l e , i n t e r - d i m e n s i o n a l a s s o c i a t i o n r u l e , m u l t i l e v e l a s s o c i a t i o n r u l e . i v 北京交通大学硕士学位论文 第一章 绪 论 1 . 1背景 无论是商业企业、科研机构或者政府部门，在过去若干年的时间里都 积累了海量的、以不同形式存储的数据资料。由于这些资料十分繁杂， 要 从中发现有价值的信息或知识， 达到为决策服务的目的， 成为非常艰巨的 任务，数据挖掘方法的提出， 让人们有能力最终认识数据的真正价值，即 蕴藏在数据中的信息和知识。数据挖掘( d a t a m i n i n g ) ，指的是从海量数 据中提取人们感兴趣的知识， 这些知识是隐含的、 事先未知的潜在有用信 息。数据挖掘是目前国际上数据库和信息决策领域的最前沿研究方向之 一， 引起了学术界和工业界的广泛关注。 一些国际上高级别的工业研究实 验室，例如 i b m a l m a d e n 和 g t e ， 众多的学术单位，例如 u c b e r k e l e y , 都在这个领域开展了各种各样的研究计划。 研究的主要目 标是发展有关的 方法论、 理论和工具， 以支持从大量数据中提取有用的和让人感兴趣的知 识和模式。 数据仓库是近年来才提出的新概念，1 9 9 2 年， w . h .工 n m o n 在其里程 碑式的 建立数据仓库)中提出了“ 数据仓库 的概念， 数据仓库的研究和 应用从此得到了广泛的关注。 i n m o n 认为数据仓库是一个更好地支持企业 或组织的决策分析处理的数据集合， 它具有面向主题、 集成、稳定、随时 间变化等四个基本特征。 此外也有人认为， 数据仓库是来自多个源的数据 的存储库， 它可通过 i n t e r n e t 将不同的数据库连接起来，并将数据全部 或部分复制到一个数据存储中心。 数据仓库通过 工 n t e r n e t 打破地域界限， 将它们合成一个逻辑整体，把一个海量的数据库展现在用户面前。 数据挖掘正是从海量的数据中挖掘知识。 数据仓库的产生和飞速发展 为数据挖掘技术开辟了新的战场， 同时也提出了新的要求和挑战。 一方面: 随着数据仓库的飞速发展和越来越广泛的应用， 大量而全面的数据被收集 在数据仓库中， 而且全面的数据处理和数据分析基础设施已经或将要围绕 数据仓库而系统地建立，数据挖掘不但可以利用数据仓库中的海量数据， 同时也可尽量利用数据仓库中可用的基础设施， 而不是从头做起。 另一方 面:数据挖掘在数据仓库未出现之前的研究主要是面向一般的数据库系 统， 并相应地发展起来一系列的理论和方法。 现在将平台转移到数据仓库 上来， 由于数据仓库本身具有与一般数据库不同的特点， 这就给基于数据 北京交通大学硕士学位论文 仓库的数据挖掘的研究提出了新的问题。 1 . 2相关工作 目 前，基于数据仓库的数据挖掘得到越来越广泛的关注和研究， 许多 学者从基于数据仓库的数据挖掘的体系结构出发， 研究如何将数据挖掘集 成到数据仓库的环境中去，如何在挖掘系统中实现各种挖掘任务 8 ,9 , 1 1 , 1 2 , 1 8 ,2 6 ,2 7 1 。 如由 加 拿 大s i m o n f r a s e r 大 学 “ 智能 数 据库 系 统 研究 实验室” 创建的d b mi n e r ，中国科学院计算技术研究所研制的ms mi n e r . 一些国际上著名的数据库厂商也纷纷在自己的数据仓库产品中集成数据 挖 掘 功能， 如n c r t e r a d a t a , s a s ,m i c r o s o ft 等 关联规则挖掘是数据挖掘的重要研究方向， 对关联规则挖掘的研究主 要集中其算法设计方面 4 , 7 , 1 6 , 1 7 ，为了 挖掘出 有用的 规则，关联挖掘算 法需多次扫描数据库， 这要耗费大量的时间。 到目 前为止， 关联挖掘针对 的目 标主要是事务数据库和关系型数据库 3 , 6 , 1 3 , 1 5 , 1 9 , 2 0 ,2 2 , 2 4 1 ， 关联规 则挖掘首先需对选定的挖掘数据集进行预处理，以作为挖掘算法的输入。 由于关系数据库及事务数据库的特点， 通常数据预处理时间在整个挖掘过 程中占相当大的比例， 而且， 预处理后的数据可存储在任何地方， 如文件 中， 可以与最初提取数据的数据库完全脱离， 挖掘算法与数据库系统是不 藕合的或松散祸合的。 随着基于数据仓库的数据挖掘研究的逐渐深入， 对关联挖掘的研究也 开始由基于事务型、 关系型数据库转向数据仓库。 本论文从如何充分结合 数据仓库进行有效的关联规则挖掘出发， 对基于数据仓库的关联挖掘进行 了研究。主要从体系结构、挖掘算法等方面对其进行了讨论。 对基于数据仓库的关联挖掘的体系结构， 本论文设计了一种集成数据 仓库， o l a p 引擎和关联规则挖掘引擎的体系结构。 该结构使得关联规则 挖掘引擎与o l a p引擎相互作用， 关联规则挖掘引擎对数据仓库中的多维 数据模型进行关联规则挖掘， 并可以对通过o l a p 的结果进行挖掘. o l a p 引 擎可对关联挖掘结果进行o l a p 操作。 对基于数据仓库的关联规则挖掘算法研究主要集中在如何利用数据 仓库的多维数据模型一 数据立方体进行有效的多维关联规则挖掘。本论文 结合数据立方体密度的不同， 对基于立方体结构的多维关联规则挖掘算法 进行了讨论，同时也对维内关联规则挖掘算法进行了讨论。 本论文对基于约束的关联规则挖掘进行了讨论。日前 对于基于约束 北京交通大学硕士学位论文 的关联规则挖掘的研究， 主要针对项包含约束， 即挖掘包含某些项目的关 联规则， 如 2 8 中的m u lt i p l e j o i n s , r e o r d e r 和 r e o r d e r 算法， 2 9 中的 s e p a r a t e 算法。 对基于数据仓库的关联规则挖掘的 约束问 题， 本论文主要 从数据约束、 立方体维和层次约束以及规则约束方面进行讨论。 刘 于数据 约束、 立方体维和层次， 首先针对约束条件， 选择最小代价的立方体构造 算法构造满足约束条件的立方体， 再在此数据量相对较小的立方体上进行 挖掘，从而提高效率。 对于规则约束， 针对约束的不同种类， 提出了相应 的关联规则挖掘方法。 1 . 3论文的研究内 容和组织安排 本论文从建立适合数据挖掘的数据环境出发， 从数据挖掘和数据仓库 融合发展的角度， 针对数据挖掘中的关联规则挖掘， 对基于数据仓库的关 联规则挖掘进行了研究，本文具体研究内容如下: i . 结合数据挖掘、数据仓库的研究和发展现状，从总体上讨论了基 于数据仓库的数据挖掘的体系结构和实现方法。 2 .针对数据挖掘中关联规则挖掘技术，提出了基于数据仓库的关联 规则挖掘的体系结构。不同于基于关系数据库的平面关系表结构 进行的关联规则挖掘方法，基于数据仓库的关联规则挖掘的体系 结构以数据仓库为挖掘平台， 集成了o l a p 技术与关联挖掘技术， 在数据仓库的多维数据模型即数据立方体上进行关联规则挖掘。 3 .论述了如何利用数据仓库的多维数据模型( 数据立方体) 进行关联 规则挖掘，提出了维间和维内的关联挖掘频繁集发现算法，结合 具体例子阐述了如何在算法中充分利用o l a p技术， 将o l a p操 作集成到算法中。并针对立方体密度的不同，对算法的性能和执 行效率进行了分析。利用数据立方体的维度层次结构信息讨论了 多层关联规则挖掘。 4 .对关联规则挖掘的第二步一 由 频繁集生成关联规则进行了讨论， 利 用反单调性质，对规则的生成算法进行了改进。 5 .对规则的兴趣度进行了讨论，为了修剪一些支持度和可信度都很 高但却可能会误导的关联规则，提出了基于相关性的另一规则兴 趣度定义，并利用此过滤一些误导的关联规则。 6 .讨论了基于约束的关联规则挖掘。对于约束的关联挖掘主要从数 据约束、 维/ 层次约束和规则约束进行了讨论。由于在整个数据集 北京交通大学硕士学位论文 上进行关联挖掘数据集太大，本文从数据约束和层次约束角度出 发，提出了基于约束立方体的关联挖掘方法。对于规则约束，针 对约束的不同种类，提出了相应的关联规则挖掘方法。 本文的主要内容组织如下: 第一章 绪论。 介绍论文研究的背景、 相关工作以及本文的组织安排。 第二章 数据挖掘和数据仓库技术。 介绍了数据挖掘、数据仓库技术 的基本理论和概念， 并总体上讨论了基于数据仓库的数据挖 掘的体系结构和实现方法。 第三章 关联规则挖掘技术。介绍了关联规则挖掘的基本理论与方 法，可应用的领域，面临的问题及发展方向，重点介绍了现 有的几种成熟的算法。 第四章 基于数据仓库的关联规则挖掘体系结构设计。 设计了基于数 据仓库的关联规则挖掘体系结构， 对该体系结构的特点和组 成进行了讨论。 第五章 基于数据立方体的关联规则挖掘。首先讨论了用于关联挖掘 的数据立方体的构建， 讨论了基于立方体结构的维内、维间 关联挖掘频繁集发现算法和在数据仓库中进行多层关联规 则挖掘的相关问题。 最后论述了如何由已发现的频繁集生成 规则，如何评价生成规则的兴趣度。 第六章 基于约束的关联规则挖掘。讨论了基于约束的关联规则挖 掘， 主要从数据约束、维/ 层次约束和规则约束进行了讨论。 由于在整个数据集上进行关联规则挖掘数据集太大， 本文从 数据约束和层次约束角度出发， 提出了基于约束立方体的关 联挖掘方法。针对规则约束的不同种类，提出了相应的关联 规则挖掘方法。 第七章 a r mi n e r简介。对基于数据仓库的关联挖掘系统 a r mi n e r 进行了介绍。 在前几章研究的基础上， 设计了基于数据仓库 的关联挖掘系统a r m i n e r ， 它以s q l s e r v e r 2 0 0 0 为数据仓库 平台，在由a n a ly s i s s e r v i c e s 创建的数据立方体上进行关联 规则挖掘。同时也实现了对数据仓库中多维数据进行浏览功 9 旨 。 第八章 结束语。 对全文进行了总结，并提出了 课题下一步的研究方 向和目标。 北京交通大学硕士学位论文 第二章 数据挖掘和数据仓库技术 合理而科学的数据环境是确保数据挖掘有效和正确实施的基础和关 键。 它需要支持o l a p 数据系统与o l t p 数据系统的分离， 需要服务于数据 挖掘总体目 标的数据再组织， 需要有单独的数据分析和数据处理环境。 数 据仓库正是为了构建这种新的分析处理环境而出现的一种数据存储和组 织技术产品。 数据仓库技术能够满足数据挖掘技术对数据环境的要求。实际上，数 据仓库技术所要研究和解决的问题就是从o l t p系统、异构分散的外部数 据源、 脱机的历史业务数据中获取数据， 处理后为数据分析和管理决策提 供应用服务。 数据挖掘和数据仓库的协同工作，一方面，可以迎合和简化数据挖掘 过程中的重要步骤， 提高数据挖掘的效率和能力， 确保数据挖掘中数据来 源的广泛性和完整性。 另一方面， 数据挖掘技术已经成为数据仓库应用中 极为重要和相对独立的方面和工具。 本章从数据挖掘和数据仓库技术融合的角度讨论数据挖掘和数据仓 库的相关概念和理论。 第一部分简要介绍数据挖掘技术; 第二部分介绍数 据仓库技术， 主要包括数据仓库的体系结构、 数据模型等; 第三部分介绍 了o l a p 技术; 第四部分对基于数据仓库， 集成o l a p 和数据挖掘的联机分 析挖掘 ( o l a m ) 进行了介绍。 z . ，数据挖掘技术 数据挖掘 ( d a t a m i n i n g， 也称作 数据 采掘、 数据开采等。 许多 人把 “ 数据挖掘”和 “ 数据库中的知识发现”( k n o w l e d g e d i s c o v e ry i n d a t a b a s e s , 简 称 k d d ) 看 作是等价的 概念 3 0 , 3 1 ， 在这种意义下， 它 们 的 定义是一 致的。 一种比 较公 认的 定 义 是f r a w le y u , p i a t e s t s k y - s h a p ir o g 等人提出的 3 : 数据挖掘，即数据库中的知识发现 ( k d d ) ， 是一个在数 据中提取模式的过程， 这些模式是有效的、 新颖的、 有潜在实用价值和易 于理解的。 北京交通大学硕士学位论文 2 . 1 . 1数据挖掘的挖掘任务和挖掘方法 数据挖掘所能发现的知识有如下几种:广义型知识，反映同类事物共 同性质的知识; 特征型知识，反映事物各方面的特征知识;差异型知识; 反映不同事物之间属性差别的知识; 关联型知识， 反映事物之间依赖或关 联的知识; 预测型知识， 根据历史的和当前的数据推测未来数据; 偏离型 知识， 揭示事物偏离常规的异常现象。 所有这些知识都可以在不同的概念 层次上被发现， 随着概念树的提升， 从微观到中观再到宏观，以满足不同 用户、不同层次决策的需要。例如，从一家超市的数据仓库中，可以发现 的一条典型关联规则可能是” 买面包和黄油的顾客十有八九也买牛奶” ， 也 可能是” 买食品的顾客几乎都用信用卡” ， 这种规则对于商家开发和实施客 户化的销售计划和策略是非常有用的。 数据挖掘涉及的学科领域和方法很多，有多种分类法。根据挖掘任务 分，可分为分类或预测模型发现、 数据总结、聚类、关联规则发现、序列 模式发现、 依赖关系或依赖模型发现、 异常和趋势发现等等; 根据挖掘对 象分，有关系数据库、面向对象数据库、空间数据库、时态数据库、文本 数据源、多媒体数据库、异质数据库、 遗产数据库以及环球网we b ; 根据 挖掘方法分，可粗分为二 机器学习方法、统计方法、神经网络方法和数据 库方法。 机器学习中 ， 可细分为 : 归 纳学习 方法( 决 策树、 规则归 纳等 ) 、 基 于范例学习、 遗传算法等。 统计方法中， 可细分为: 回归分析( 多元回归、 自 回归等 ) 、 判别分 析( 贝叶 斯判别、 费 歇尔判别、 非 参数判别等 ) 、 聚 类分 析( 系统聚类、 动态聚类等) 、 探索性分析( 主元分析法、 相关分析法等) 等。 神 经网 络方法中， 可细 分为: 向 神 经网 络 ( b p 算 法等 ) 、 自 组织神经网 络 ( 自 组织特征映射、 竞争学习等) 等。 数据库方法主要是多维数据分析或o l a p 方法，另外还有面向属性的归纳方法。 以下将主要从挖掘任务和挖掘方法的角度， 着重讨论分类、估计、 预 iy !1 、关联分析及聚类五种非常重要的发现任务。 分类、估计、 预测为定向 式d m ( d i r e c t e d d a t a m i n i n g ) ，其目 的是利 用现有的资料来建立模型， 借此描述某一个特定变量: 关联分析、 聚类为 非定向式d m ( u n d i r e c t e d d a t a m i n i n g ) 口 在非监督式数据采矿中，并未特 别标明某一个变量，其目的是在所有的变量中找出有可能存在的关系。 ( 1 ) 分 类 ( c l a s s i f ic a t i o n ) 依照所分析对象的属性分门别类、加以定义、建立类组 ( c l a s s ) 。比 如，将信用卡申请人分为低、中、高风险群， 或是将顾客分到事先定义好 北京交通大学硕士学位论文 的族群。所使用的技巧有决策树( d e c i s i o nt r e e ) ，记忆基础推理 ( m e m o r y b a s e dr e a s o n i n g ) 等。 ( 2 ) 估计( e s t i m a t i o n ) 根据既有的连续性数值相关属性资料，求得某一属性的未知值。比如， 估计家中小孩的数量、一个家庭的总收入或是不动产的价值。所使用的技 巧有相关分析、回归分析及类神经网络方法。 ( 3 ) 预测( p r e d i c t i o n ) 根据对象属性过去的观察值来估计此属性未来的值。比如，预测哪些 顾客会在未来的半年内取消该公司的服务，或是预测哪些电话用户会申请 增值服务，如三方通话、语音信箱等。所使用的技巧有回归分析、时间序 列分析及类神经网络方法。 ( 4 ) 关联分析( a s s o c i a t i o na n a l y s i s ) 关联分析发现关联规则，这些规则展示属性值频繁地在给定数据集中 一起出现的条件 1 。我们将在第三章对关联规则的一些基本概念和理论 进行讨论。 ( 5 ) 聚类( c l u s t e r i n g ) 将不同的母体区隔为较具同构型的群组( c l u s t e r ) ，换句话说，其目的 是将组与组之间的差异分辨出来，并对个别组内的相似样本进行挑选。在 聚类技术中，没有预先定义好的类别和训练样本存在，所有纪录都根据彼 此相似程度来加以归类。比如，在市场营销调查前，先将顾客聚类，再来 分析每群顾客最喜欢哪一类促销，而不是对每个顾客都用相同的标准规则 来分析。所使用的技巧有k - m e a n s 法及a g g l o m e r a t i o n 法。 2 1 2 数据挖掘的过程 数据挖掘作为知识发现的过程，一般由三个主要的阶段组成：数据准 备、数据挖掘、以及结果的解释评估。知识的发现可以描述为这三个阶段 的反复过程 3 0 ，3 1 ，如图2 ，l 所示。 1 ) 数据准备 数据准备又可分为三个子步骤：数据选取( d a t as e l e c t i o n ) 、数据预处 理( d a t a p r e p r o c e s s i n g ) 和数据变换( d a t a t r a n s f o r m a t i o n ) 。数据选取的目 的是确定发现任务的操作对象，即目标数据，它是根据用户的需要从原始 数据库中抽取的一组数据。数据预处理一般包括消除噪声、推导计算缺值 数据、消除重复记录、完成数据类型转换( 如把连续值数据转换为离散值 北京交通大学硕士学位论文 数据，以便于符号归纳，或是把离散值数据转换为连续值数据，以便于神 经网络归纳) 图2 1 数据挖掘一股过程 等。当数据挖掘的对象是数据仓库时，一般来说，数据预处理已经在生成 数据仓库时完成了。数据变换的主要目的是将数据转换成适合数据挖掘需 要的形式，例如将文档信息转换成数值向量形式，另外还包括数据维度的 削减或降维( d i m e n s i o nr e d u c t i o n ) ，即从初始特征中找出真正有用的特征 以减少数据挖掘时要考虑的特征或变量个数。 2 ) 数据挖掘 数据挖掘阶段首先要确定挖掘的任务或目的是什么，如数据总结、分 类、聚类、关联规则发现或序列模式发现等。确定了挖掘任务后，就要决 定使用什么样的挖掘算法。同样的任务可以选用不同的算法来实现。选择 实现算法有两个考虑因素：一是不同的数据有不同的特点，因此需要用与 之相关的算法来挖掘：二是用户或实际运行系统的要求，有的用户可能希 望获取描述型的、容易理解的知识( 采用规则表示的挖掘方法显然要好于 神经网络之类的方法) ，而有的用户或系统的目的是获取预测准确度尽可 能高的预测型知识。完成了上述准备工作后，就可以实施数据挖掘操作了。 具体的数据挖掘方法将在后面章节中作较为详细的论述。需要指出的是， 尽管数据挖掘算法是k d d 的核心，也是目前研究人员主要努力的方向， 但要获得好的挖掘效果，必须对各种挖掘算法的要求或前提假设有充分的 理解。 3 ) 结果解释评估 数据挖掘阶段发现的模式，经过用户或机器的评估，可能存在冗余或 北京交通大学硕士学位论文 无关的模式， 这时需要将其剔除; 也可能挖掘结果不满足用户要求， 这时 则需要整个发现过程退回到发现阶段之前， 如重新选取数据、 采用新的数 据变换方法、 设定新的数据挖掘参数值， 甚至换一种挖掘算法 ( 如当发现 任务是分类时，有多种分类方法，不同的方法对不同的数据有不同的效 果) 。另外，由于 k d d最终是面向用户的，因此可能要对发现的模式进 行可视化， 或者把结果转换为用户易懂的另一种表示， 如把分类决策树转 换为 “ i f . . t h e n . . . 规则。 2 . 2数据仓库技术 数据仓库技术所要研究和解决的问题就是从 o l t p系统、异构分散的 外部数据源、 脱机的历史业务数据中获取数据， 处理后为数据分析和管理 决策提供应用服务。 2 .2 . 1数据仓库的定义 公认的数据仓库概念是w . h . i n m o n 在 建立数据仓库 一书中提出的: 数据仓库就是面向主题的、 集成的、 不可更新的( 稳定性) 随时间不断变化 ( 不同时间)的数据集合，用以支持经营管理中的决策制定过程。 数据仓库中的数据是面向主题的， 它与传统数据库中的面向应用相对 应。 数据仓库的主题是一个在较高层次上将数据归类的标准， 每一个主题 对应一个宏观的分析领域: 数据仓库的集成特性是指在数据进入数据仓库 之前， 必须经过数据加工和集成， 这是建立数据仓库的关键步骤。 它能够 统一原始数据中的矛盾之处， 还能够将原始数据结构从面向应用向面向主 题转变; 数据仓库的稳定性是指数据仓库反映的是历史数据的内容， 而不 是日 常事务处理产生的 数据， 数据经加工和集成进入数据仓库后是极少或 根本不修改的; 数据仓库是不同时间的数据集合， 它要求数据仓库中的数 据保存时限能满足进行决策分析的需要， 而且数据仓库中的数据都要标明 该数据的时间属性。 2 .2 . 2数据仓库体系结构及应用模型介绍 数据仓库是一种对数据进行建模和管理的技术。 从不同的数据源提取 数据和信息， 然后把这些数据转换成公共的数据模型并且和仓库中已有的 北京交通大学硕士学位论文 数据集成在一起。当用户向仓库进行查询时，需要的信息已经准备好了， 数据冲突、表达不一致等问题己经得到了解决。这使得决策查询更容易、 更有效。 作为一个系统， 数据仓库至少应包括3 个基本的功能部分 3 2 : 1 )数据获取: 负责从外部数据源获取数据。 数据被区分出来， 进行 拷贝或重新定义格式等处理后，准备载入数据仓库。 2 )数据存储和管理:负责数据仓库的内 部维护和管理， 提供的 服务 包括数据存储的组织、数据的维护、数据的分发、数据仓库的例 行维护等。 3 )信息访问: 信息访问部分属于数据仓库的 前端，面向 不同种类的 最终用户，这里主要由桌面系统的各种工具组成。数据仓库的最 终用户在这里提取信息、分析数据集、实施决策，从而可望取得 竞争优势。进行数据访问的软件工具，主要是查询生成工具、多 维分析工具和数据挖掘工具等。这里也是工具制造商们竞相争夺 的地段。新的发展趋势是把信息访问工具紧密集成到数据仓库系 统中。 图2 .2 给出了数据仓库的一般体系结构和应用模型。 数据模型 构造工具 监督管理 工具 olap 分 析 巴巴巳 数据挖掘 工具 巴巴 操作型 数据库 预测工具 数据集市 图2 .2数据仓库体系结构及其应用模型 2 . 2 . 3数据仓库的数据模型 在数据仓库中，逻辑上一般采用多维的形式对数据进行组织和处理。 北京交通大学硕士学位论文 维可以看成是数据分析的角度， 维内不同的分析角度间具有层次特点。 数 据仓库中的数据通常组织成多个维的形式， 即 d = d l , d 2 , . . . ,d n ) . 每个维 d i 组织成一个层次 h i , 每个层次由一些维层组成.所有维层次的笛卡尔集p = h l x h 2 x 二x h n 可以 用一 个 格结 构来描述 4 5 ，格结构 是一个有向 图 ， 它 的每个结点代表一个c u b o i d ， 即视图，边代表各个 c u b o i d 之间的相互依赖 关系。 在实际中， 为了降低查询处理的时间， 通常将格结构中的一些。 u b o i d 预先实体化存储在数据仓库中， 即数据仓库通常采用物化视图的方案来提 高查询性能， 2 . 2 . 3 . 1维 维是人们观察数据的特定角度。 例如，当人们从时间的角度来观察一 个企业的产品销售数据时，数据可以分为1 9 9 9 年的销售额、 2 0 0 0 年的销 售额和 2 0 0 1 年的销售额等;当人们从地区的角度来观察一个企业的产品 销售数据时， 数据就又可以看成是北京市的销售额、 上海市的销售额和广 州市的销售额等。 数据的维往往有多个， 这里， 时间、 地区都各是一个维。 假设该销售数据只有时间维和地区维， 那么如果我们在时间维上取一个值 2 0 0 0 年” ， 地区维上取一个值 “ 北京” ，就唯一确定了销售额的一个值。 一维层次关系 人们通过某个特定角度观察数据 ( 即 “ 维” )时，对数据进行描述的 细节程度可能是不同的，这些细节程度不同的描述形成了维的层次。 d i ,发送站 d a 日 4 1 2 发送分局 d x z月 d u 发送局 6 fg ib l 内: 常 d 1 1 年 ( a ) 发送方维ro、时间维 图 2 . 3 例如，时间维的层次可以是: 维格示例 日，月，季 月为次细节层。这些层次可以组织成层次图， 次图，d 2 1，d 2 2，d 2 :和 d 2 4 分别表示年，季， 年。其中日是最细节层， 图2 . 3 ( b ) 给出了时间维的 层 月，日。在维层次图的最 低层，加入了最高抽象层元素， 表示为小， 对于时间维而言，它表示对所 北京交通大学硕士学位论文 有日期的数据进行聚集，即分组属性集中不包含日期维。 在 o l a p系统中，维层次是相当重要的，它对应于 “ 向下钻取” ( d r i l l - d o w n ) 和 “ 卷起” ( r o l l - u p ) 两个操作。向 下钻取对应于沿某一维逐步 地向更细节层的方向观察数据。 例如， 按从所有日期到年到季到月到日的 方向钻取，用户看到的数据就越来越详细。而卷取则正好相反。 同时，维内层次也带来维内查询依赖问题。例如，仅考虑按时间维进 行聚集的查询， 如果我们用图2 . 3 ( b ) 给的时间维层次进行聚集， 可以 得到 五种聚集视图，分别为按日、月、 季、年和全部日 期进行聚集的视图， 这 些视图对应于时间维上的不同粒度级的数据。 用前面所提的表示方法， 可 以 表示为: ( d a y ) , ( m o n t h ) , ( q u a r t e r ) , ( y e a r ) 和小 。 显然， 这些聚集视图 间存在如下查询依赖关系: 4)分( y e a r ) 令( q u a rt e r ) 令( m o n t h ) e - ( d a y ) 我们这里采用的日 期维属性间的层次关系为全序。实际上，有些维的 属性间层次关系并不是全序， 而是偏序。 例如， 在货运量主题中， 货物发 送者维需要考虑按省市自 治区进行分析统计， 而铁路局和分局的设置是跨 省区的， 同属于某一分局的不同货运站可能属于不同的省份， 这样， 货物 发送者维的元素具有如图2 . 3 ( a ) 所示的层次关系， 这些元素间的关系是偏 序。维层次结构中的维元素集合 d与维元素间的层次关系一设为延一构 成的代数系统 y的蕴涵式，其中x c h y c h x n y = o o规 则x = : y 在d中的支持度 ( s u p p o r t ) 是d中同时 支持x和y 的事务数与 所有事务数之比， 记为s u p p o rt c x = : y ) ，即: 北京交通大学硕士学位论文 s u p p o r t ( x = : y ) = i t : x v y c t , t e d i1 id i 规则x = y 在d中的 可信度( c o n f id e n c e ) 是同时 支持x和y 的 事务数 与支持x的事务数之比， 记为c o n f i d e n c e ( x = y ) ，即 c o n f i d e n c e ( x = y ) = i t : x v y c t , t e d ii i t : x c_ t , t e d i 给定一个事务数据库d ，关联规则的挖掘问题就是产生支持度和可信 度分别大于给定的 最小 支持度 ( m i n s u p p ) 和最小 可信度 ( m i n c o 动 的 规 则。 关联规则挖掘过程一般可分为两步 i : 第一步:找出所有的频繁项集: 满足最小支持的项集，称为频繁项集 ( f r e q u e n t i t e m s e t ) 。 第二步:由频繁项集产生强关联规则:根据定义，这些规则必须满足 最小支持度和最小可信度。 在这两步中， 第二步最容易。 挖掘关联规则的总体性能由第一步决定。 3 . 2关联规则的种类 我们将关联规则按不同的情况进行分类: ( i ) 基于规则中处理的变量的类别，关联规则可以分为布尔型和数值 型。 布尔型关联规则处理的值都是离散的、 种类化的，它显示了这些变量 之间的关系;而数值型关联规则可以和多维关联或多层关联规则结合起 来， 对数值型字段进行处理， 将其进行动态的分割， 或者直接对原始的数 据进行处理，当然数值型关联规则中也可以包含种类变量。例如:性别二 “ 女” 补职业二 “ 秘书” ，