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

摘要 数据挖掘就是从大量的数据中抽取以前未知并具有潜在可用的模式。而关联规则挖 掘是近年来发展十分迅速而且非常活跃的研究领域，是数据挖掘的一个重要研究内容。 它主要应用于发现数据中不同项目或属性之间的有趣联系。随着被收集和存储数据的高 速增长，许多业界人士对于从他们的数据库中挖掘关联规则的兴趣愈加浓厚。为了进一 步适应和满足用户不断变化的需求，本文进行了一系列关于提高关联规则挖掘算法的性 能和完善相关功能的研究工作。 本文首先认真地分析和归纳了当前关联规则挖掘算法的研究成果，并分析了基于数 据水平分布相关算法，如a p r i o r i 、d h p 、f p g r o w t h 等，和基于数据垂直分布相关算法， 如e c l a t 、d i f f s e t 等的实现方法和性能特点，为提出性能和功能更优的关联规则挖掘算 法作好理论准备。然后提出应用于数据垂直分布的基于关联矩阵的深度优先关联规则挖 掘算法a d f a r ，a d f a r 用关联矩阵来描述任意2 个数据项之间的关联关系，并利用关 联矩阵来约束候选频繁项集的产生，以减少所产生候选频繁项集。并且利用关联矩阵以 深度优先策略产生频繁项集，每产生一个k 频繁项集只需要进行位图的一次交运算。算 法采用位图方式来存储频繁项集支持集，具有较小的内存开销。a d f a r 不需要多次扫 描数据集，避免了a p r i o r i 算法及类a p r i o r i 算法繁杂的候选项集产生和验证操作等优 点，具有良好的可操作性。实验证明，本文提出的基于数据垂直分布的关联规则挖掘算 法a d f a r 克服了产生大量候选集和需多次扫描数据库的缺点，且具有较高的挖掘效率。 基于数据垂直分布的关联规则挖掘算法通常采用位图方式来存储频繁项集支持集， 尽管使用位图来存储支持集映像已经减小了对内存空间的需求，但这仍然是基于数据垂 直分布的关联规则挖掘算法的主要空间开销，也是制约算法可扩展性的一个重要因素。 为此本文研究了位图压缩方法，将要存放在内存中的数据项支持集位图进行压缩，以减 小算法的空间开销，提高算法可扩展性。本文详细介绍了位图压缩和基于压缩位图进行 交运算所涉及到的有关理论和方法。实验结果表明，本文提出的位图压缩方法b c v 使 压缩率达到了7 0 左右，大大减少了基于数据垂直分布的关联规则挖掘算法运行中频繁 项集支持集在内存空间的占用。 关键词：关联规则挖掘数据垂直分布深度优先关联矩阵位图压缩 a b s t r a c t d a t am i n i n gi sm e t h o dt h a to b t a i n st h eu n k n o w na n d p o t e n t i a lu s a b l ep a t t e r nf r o mam a s s o fd a t a t h ea s s o c i a t i o nr u l em i n i n gi sa ni m p o r t a n tr e s e a r c hc o n t e n to fd a t am i n i n ga n da v e r ya c t i v er e s e a r c hf i e l dw h i c hh a sm a d ear a p i dd e v e l o p m e n ti nr e c e n ty e a r s a n di ti s a p p l i e dt od i s c o v e rt h ei n t e r e s t i n gc o n n e c t i o n sb e t w e e nt h ed i f f e r e n ti t e m so ra t t r i b u t e w i t h t h eh i g h - s p e e di n c r e m e n to ft h ec o l l e c t e da n ds t o r e dd a t a ，m o r ea n dm o r ep e o p l ea r e i n t e r e s t e di no b t a i n i n gt h ea s s o c i a t i o nr u l e sf r o mt h e i rd a t a b a s e t om e e tt h ev a r i o u sd e m a n d s o ft h eu s e r s ，as e r i e so fr e s e a r c ho ni m p r o v i n gt h ep e r f o r m a n c ea n df u n c t i o n so ft h e a l g o r i t h m so ft h ea s s o c i a t i o nr u l e sm i n i n gh a db e e nc a r r i e do u t i nt h i sp a p e r ，a no v e r v i e wo ft h ea s s o c i a t i o nr u l e sm i n i n gi sg i v e n ， a n da n a l y z es o m e p o p u l a rr e l e v a n ta l g o r i t h m s ， s u c ha sa p r i o r i 、d h p 、f p - g r o w t hb a s e do nh o r i z o n t a ld a t a ， a n de c l a t 、d i f f s e tb a s e do nv e r t i c a ld a t a p r e p a r ef o rb r i n g i n gf o r w a r da na s s o c i a t i o nr u l e s m i n i n ga l g o r i t h mw i t hab e t t e rp e r f o r m a n c e t h e n ，a na 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 m ， a d f a r ，w h i c ha p p l i e df o rv e r t i c a ld a t ab a s e do ni n c i d e n c em a t r i xd e p t h f i r s ta r ep r o p o s e d t h i s a l g o r i t h md e s c r i b e st h er e l a t i o n so fa n y2i t e m s e t sw i t hi n c i d e n c em a t r i x u s i n g i n c i d e n c em a t r i xt or e s t r i c tt h ep r o d u c i n go fc a n d i d a t ef r e n q u e n ti t e m s e t s ，s ot h a tc a nd e c r e a s e t h en u m b e ro fc a n d i d a t ef r e n q u e n ti t e m s e t s t h i sa l g o r i t h mm a k e su s eo fi n c i d e n c em a t r i xt o p r o d u c ef r e n q u e n ti t e m s e t sb ys t r a t e g yo fd e p t h f i r s t ，i to n l yn e e d si n t e r s e c t i o no p e r a t i o no n e t i m ew h e np r o d u c e dak - f r e q u e n ti t e m s e t t h i sa l g o r i t h ma d o p t sb i t m a pt os t o r et h es u p p o r t s e t so ff r e q u e n ti t e m s e t s ，h a sal e s s e rs p e n d i n go fm e m o r y t h i sa l g o r i t h md o e s n tn e e dt o s c a nm e m o r ym a n yt i m e s ，a v o i d sm u l t i f a r i o u sc a n d i d a t ei t e ms e t sp r o d u c i n ga n dv a l i d a t i n g ， a n dh a sg o o dm a n e u v e r a b i l i t y e x p e r i m e n t a lr e s u l t si n d i c a t et h a tt h ea l g o r i t h mw ep u t f o r w a r do v e r c o m e st h ed i s a d v a n t a g e st h a ta p r i o r ia n di t sr e l a t i v ea l g o r i t h m sp r o d u c el a r g e a m o u n to fc a n d i d a t ei t e m s e t sa n dr e q u i r es c a n n i n gd a t a b a s em a n yt i m e s m i n i n ge f f i c i e n c yi s h i g l l t h ea 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 mw h i c ha p p l i e df o rv e r t i c a ld a t ab a s e do ni n c i d e n c e m a t r i xd e p t h - f i r s ta d o p t sb i t m a pt os t o r es u p p o r ts e t so ff r e q u e n ti t e m s e t s u s i n gb i t m a ps p a c e t os t o r es u p p o r ts e t sa l r e a d yr e d u c e sd a t as p a c ei nt h em e m o r y ，b u ti ti st h em a i ns p a c e e x p e n s eo ft h ea l g o r i t h m ， a n da l s oak e yf a c t o rt h a tr e s t r i c t sa l g o r i t h m se x p a n s i b i l i t y t h e r e f o r e ， i nt h i sp a p e r ，w ew i l lp r e s e n ta ni m p r o v e da l g o r i t h mw h i c ha d o p t sc o m p r e s s e d b i t m a pt oi m p r o v eo nv e r t i c 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 m i tc o m p r e s s e st h es u p p o r t s e t sw h i c hw i l lb ep u ti n t ot h em e m o r yt oa c h i e v et h ep u r p o s eo fs a v i n gm e m o r ys p a c e i n t h i s p a p e r , w ew i l l i n t r o d u c eb i t m a pc o m p r e s s i o na n dt h ei n t e r s e c t i o no p e r a t i o nb a s e do n c o m p r e s s e db i t m a pi nd e t a i l o u re x p e r i m e n t a lr e s u l t si n d i c a t et h a tt h eb i t m a pc o m p r e s s i o n a l g o r i t h mf o rv e r t i c a la s s o c i a t i o nr u l e sm i n i n gm a k e st h er a t eo fc o m p r e e s i o na c h i e v i n g7 0 a n dd e c r e a s e sm e m o r y s p a c ew h e nt h ep r o c e s si sr u n n i n g k e y w o r d s ：a s s o c i a t i o nr u l e sm i n i n g ，v e r t i c a l c o m p r e s s m n d a t a ，d e p t hf i r s t ，i n c i d e n c em a t r i x ，b i t m a p 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取 得的研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得叁盗墨兰盘堂 或 其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研 究所做的任何贡献均己在论文中作了明确的说明并表示了谢意。 张论文惜粥：杨可错啪：彻月_ 日 学位论文版权使用授权书 本学位论文作者完全了解 叁盗堡墨盘堂有关保留、使用学位论文 的规定。特授权叁盗墨墨盘堂 可以将学位论文的全部或部分内容编入 有关数据库进行检索，并采用影印、缩印或扫描等复制手段保存、汇编， 以供查阅和借阅。同意学校向国家有关部门或机构送交论文的复本和电子 文件。 ( 保密的学位论文在解密后适用本授权说明) 摊擞储粕哪 签字日期：了川年f 月午日 导师签名： 签字日期：砂四年月乒日 第一章绪论 1 1 本课题研究背景 第一章绪论 自2 0 世纪6 0 年代以来，数据库技术得到迅速发展，新的数据库系统层出不穷，从 早期的层次数据库到后来的网状数据库，直到目前广泛应用的关系数据库。系统和数据 建模工具、索引和数据组织技术不断进步，数据库存储、统计和分析数据的能力大大增 强。用户通过查询语言、用户界面、优化的查询处理和事务管理，可以方便、灵活地访 问数据【1 】【2 1 。 8 0 年代中期以来，数据库技术的特点是广泛吸收关系技术，研究和开发新的、功能 强大的数据库系统。这些系统使用了先进的数据模型，如扩充关系模型、面向对象模型 和演绎模型等；主动数据库、科学数据库、知识库和办公信息库在内的面向应用的数据 库系统广泛出现【3 l 。上世纪末发展起来的联机分析处理( o l a p ) 和数据仓库的应用，使数 据的存储和分析更加迅速、便捷。凭借这些技术和设备，人们存储了海量的数据，这就 要求提供更加高效的数据分析处理工具【4 】。 与此同时，这些数据蕴含了大量用户所需的知识。尽管数据库系统具有高效的录入、 查询和统计数据等功能，但是它缺乏能发现数据背后隐藏的知识的手段，从而造成在当 今全球范围内出现“数据爆炸但知识匾乏”的窘境。正是在这种情况下，数据挖掘( d a t a m i n i n g ) 技术应运而生p j 。 数据挖掘技术主要分为基于统计的方法和基于知识发现的方法。从上世纪6 0 年代以 来，基于统计思想的聚类和时间序列技术得到了迅速的发展；随着人工智能的出现和计 算技术的长足进步，自学习的知识发现技术得到了人们的重视，并被应用到生产实践中， 这类技术主要有神经网络、遗传算法、关联规则等。各类数据挖掘技术的出现和发展， 为本文随后的研究提供了坚实的理论基础和丰富的应用实例【6 】【7 】。 在数据挖掘中，关联分析( a s s o c i a t i o n a n a l y s i s ) 是其中十分重要的组成部分。关联分 析的主要目标是发现关联规则。自从a g r a w a l 在1 9 9 3 年提出挖掘关联规则的问题后， 关联规则的研究出现了一个热潮【8 】【9 1 。起源于购物篮分析的关联规则是数据挖掘最重要 的研究内容之一。在购物篮分析中，它通过发现顾客放入其购物篮中不同商品之间的联 系，从而进一步了解顾客的购买习惯，以致获取更大的经济效益。例如：沃尔玛利用相关 技术获知将尿布与啤酒摆在一起能够同时提高两者的销售额。到目前为止，关联规则挖 掘技术已广泛应用到众多行业。例如：零售、保险、银行、通信、政府、医疗、教育等等 1 0 i h o 目前有很多经典算法已经被提出，其中包括a g r a w a l 等人提出的a p r i o r i t l 2 】、触s 【”】、 a p r i o f i t i d t l 2 】和a p f i o f i h y b f i d l l 2 1 ；p a r k 等人提出的d i - i p t l 4 1 f 1 5 1 ；s a v a d e r e 等人提出的 p a r t i t i o n ：t o i v o n e n 提出的抽样算法s a m p l i n g ；f p g r o w t h 1 6 1 ；d i c t r 7 】等。其中最有效和 第一章绪论 最有影响的算法包括a p n o d 和f p g r o w t h 算法。为了改进这些经典算法的效率，应对需 求的不断变化，多种频繁模式挖掘方法被相继提出，如：最大频繁项集挖掘【l0 1 、频繁闭 项集挖掘【1 1 1 、基于约束的频繁项集挖掘【1 8 】等等，文献【1 9 】1 2 0 】将频繁模式集组织成格，采 用垂直二进制位图来表示事务数据库，大大提高了存储效率，这些算法只对挖掘对象进 行一些“与 、“或 、“异或等逻辑运算操作，降低了传统算法的实现难度，但它们仍 然采用a p n o d 基本思想，无法避免需要对数据库进行多次遍历和候选项集的产生和验 证繁杂这2 个沉重的代价【2 l 】【2 2 】；另一方面，为提高执行挖掘任务效率，相关的改进算法 和新的高效算法不断被提出【2 3 l 。为避免多次扫描数据库的高代价开销，近期提出了改进 算法将数据库中的数据的排列方式由通常的水平方式改为垂直方式。该数据表示方式命 名为垂直数据表示。例如，文献【2 4 】采用垂直二进制位图方法，该算法克服了传统算法的 缺陷，无需产生候选集，但它们不能有效地解决有向图或关联图生成中重复路径的剪裁 问题。s l i g 算法 2 5 】虽然应用了关联矩阵，但是仍然采用宽度优先策略，每生成k 候选 频繁项集需要k 1 次交运算，时间复杂性较高。另外，e c l “2 6 】【2 7j 和d e c l a t i 列脚j 都是基 于垂直数据表示的高效的频繁项集挖掘算法，但这两种算法采用的数据存储方式为列表 的形式，占用空间过大，导致算法的可扩展性受到限制。 1 2 本文研究的意义和目的 在传统的关联规则挖掘算法中，a p f i o f i 算法是其它数据挖掘算法的基础，其不足之 处在于需要对数据库进行多次遍历和候选项集的产生和验证繁杂。即使进行了优化， a p f i o d 算法的固有的缺陷还是无法克服。而近期提出的一些数据垂直格式的关联规则 挖掘算法也有着内存空间占用过大和时间复杂行高的缺点。为了克服a p f i o d 算法和这 些近期提出的基于数据垂直格式的关联规则挖掘算法的缺陷，本文提出了应用于数据垂 直分布的基于关联矩阵的深度优先垂直关联规则挖掘算法a d f a r 。本算法采用位图的 方式来存储频繁项集支持集，占用内存空间小，并且构造关联矩阵以便更有效地利用内 存空间，提高候选频繁项集的质量，尽可能少的产生候选频繁项集，并采取深度优先策 略，使得每产生一个k 。候选项集只需进行一次交运算。使算法具有不需要多次扫描数据 集，避免了繁杂的候选项集产生和验证操作等优点，具有良好的可操作性和高效的挖掘 效率是本文的研究意义。 基于数据垂直分布的关联规则挖掘算法大多采用位图来存储频繁项集支持集，尽管 采取位图的方式已经减少了频繁项集支持集对内存空间的需求，但这仍然是算法主要的 空间开销，也是制约算法可扩展性的一个重要因素。为此本文研究了位图压缩方法，将 要存放在内存中的数据项支持集位图进行可还原的压缩，并在计算数据项支持集位图交 运算的时候动态地解压缩，以减小算法的空间开销，提高算法可扩展性，达到减小基于 数据垂直分布的关联规则挖掘算法运行中对内存空间需求的目的，是本文研究的意义。 第一章绪论 1 3 本文的主要研究内容和结构安排 本文主要研究了关联规则挖掘的国内外研究现状、垂直数据表达方法和由水平格式 向垂直格式数据的转换方法、垂直数据在内存空间的组织存储方式、基于关联矩阵的深 度优先的候选频繁项集的产生方式及验证，候选关联规则的形成及其支持度的计算方 式，位图支持集的压缩方法和基于压缩位图的支持集映像的交运算。 本文结构主要由以下几部分构成： 第一章绪言。本章首先介绍了课题的背景；接着概括了课题具体所涉及的理论及其 相应的特点，总结了所涉及技术的发展和目前的研究成果等；最后列出了本论文的结构。 第二章数据挖掘综述。本章首先介绍了数据挖掘的基本概念；然后讨论了数据挖掘 的技术分类和功能；以及关联规则挖掘的相关概念；最后简单介绍了垂直关联挖掘算法。 第三章垂直关联挖掘算法a d f a r 设计与实现。本章首先介绍了应用于数据垂直分 布的基于关联矩阵的深度优先垂直关联规则挖掘算法的必要性和利用位图计算支持度 的方法；然后详细讨论了算法及其设计基本思想；最后给出了算法的测试结果和性能评 价。 第四章频繁项集支持集位图压缩方法研究。本章首先介绍了垂直关联挖掘算法中位 图压缩的必要性；然后详细讨论了频繁项集支持集位图压缩方法b c v ：最后给出了采 用了b c v 位图压缩方法的垂直关联挖掘算法算法测试结果和性能评价。 最后是对本文所完成的工作的总结和展望。 第二章数据挖掘综述 2 1 数据挖掘的概念 第二章数据挖掘综述 为了理解数据挖掘( d a t am i n i n g ) 的含义，有必要看一下它的字面意思。英文中挖掘 ( m i n e ) 就是抽取( e x t r a c t ) ，这个词通常是指从地下抽取隐藏的贵重资源的挖掘操作。该词 和数据之间的联系是：对数据进行深入的研究。目的在于从大量数据中去发现事先未注 意到的额外信息。从科学研究的角度看，数据挖掘是一门相对较新的学科，主要基于计 算科学、市场营销学和统计学等学科的研究。用于数据挖掘的很多方法来源于两个研究 分支，一个是机器学习，另一个是统计学，特别是多元的计算统计学。 和计算机科学、人工智能相关的机器学习用于发现数据中的关系和规则，这些关系 和规则可以表示成一般规律。机器学习的目的是再现数据生成的过程，允许分析者从已 知数据归纳出新的未知的案例。1 9 6 2 年，r o s e n b l a t t 提出了称为感知器的第一个机器学 习模型，接着神经网络在2 0 世纪8 0 年代后半期得到发展。与此同时，一些研究者完善 了主要用于分类问题的决策树理论，统计学一直用于建立分析数据的模型并且目前可以 用计算机来完成。从2 0 世纪8 0 年代后半期开始，作为统计分析基础的计算方法的重要 性日益增加，统计方法用于实际的多元统计应用得到同步发展。从2 0 世纪9 0 年代开始， 统计学家也对机器学习方法表现出了兴趣，这导致了方法学的重要发展。 到2 0 世纪8 0 年代末，机器学习方法的应用已超出计算和人工智能领域。特别是在 数据库市场的应用，数据库用来提高市场竞争力，数据库中的知识发现( k d d ) 用于描述 所有从已知数据发现关系和规则的方法。逐渐地，k d d 扩展成描述从数据库中推断信 息的整个过程，从初始商业目标的确定到决策规则的使用。数据挖掘用于描述k d d 中 的一个组成部分，在k d d 中把学习算法应用于数据。 1 9 9 5 年在加拿大蒙特利尔召开的第一届知识发现和数据挖掘国际会议上，“数据挖 掘”概念第一次内u s a m af a y a a d 提出，这次会议一直被认为是该领域的主要会议之一。 k d d 是一种分成若干阶段的集成分析技术，目的在于从大量的已知数据中推断事先未 知的、看起来没有任何明显的规则或重要联系的知识。随着数据挖掘概念的建立，逐渐 变成了整个推断知识过程的同义词。先前的定义忽略了一个重要的方面数据挖掘的 根本目的，数据挖掘的目的是得到根据相关性可以测量的结果商业利益。这里给出 数据挖掘更完整的定义： 数据挖掘是为了发现事先未知的规则和联系而对大量数据进行选择、探索和建模的 过程，目的在于得到对数据库的拥有者来说清晰而有用的结果【3 0 】。 在商业领域中，结果的效用变成了商业结果本身。因此，数据挖掘与统计分析的区 别不是数据量的大小，也不是使用的分析方法的不同，而是对已知的数据库、分析工具 和商业知识的集成。应用数据挖掘方法意味着遵循一个集成的过程包括：把商业需求 第二章数据挖掘综述 转换成要分析的问题，检索用于分析的数据库，应用基于统计技术的计算机算法得到对 战略决策行用的重要结果。战略决策本身又提出新的测量需求和新的商业需求形成由 数据挖掘引起的知识的良件循环( b e r r y 和l i n o f f , 1 9 9 7 ) 。 数据挖掘不只是计算机算法和统计技术的应用，它是一个商业智能过程，可以和信 息技术一起支持商业决策。 数据挖掘是从大量的数据中提取隐含在其中的、事先不知道的、但又是潜在有用的 信息和知识的过程。它是近年来出现的c r m ( c u s t o m e rr e l a t i o n s h i pm a n a g e m e n t ) ， b i ( b u s i n e s si n t e l l i g e n c e ) 等热点领域的核心技术之一。数据挖掘技术的产生与发展为人们摆 脱这种困境提供了强有力的手段，数据挖掘本质上来说是让数据自己说明自身的价值， 即是按照既定的业务目标对大量的企业数据进行探索揭示隐藏其中的规律性，并进一步 将之模型化的先进有效的方法。 数据挖掘就是从大量的、不完全的、有噪声的、模糊的、随机的实际应用数据中， 提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程，这是技 术上的定义。美国s a s 软件研究所则将数据挖掘定义为：“按照既定的业务目标，对大量 的企业数据进行探索、揭示隐藏其中的规律性并进一步模型化的先进、有效的方法”数 据挖掘的功能主要为：分类( c l a s s i f i c a t i o n )估值( e s t i m a t i o n ) 预言( p r e d i c t i o n ) 相关性分组或关联规则( a f f i n i t yg r o u p i n go ra s s o c i a t i o nr u l e s )聚集( c l u s t e r i n g ) 描 述和可视化( d e sc r i p t i o na n dv i s u a l i z a t i o n ) 复杂数据类型挖掘( t e x t ，w e b ，图形图 像，视频，音频等) 。 数据挖掘技术从兴起到发展的十几年间，主要面对的挖掘对象是以结构化数据为主 的关系数据库和数据仓库。但随着数据库技术和i n t e m e t 技术的迅速发展，大量复杂类 型的数据不断涌现，恰恰在这些数据里隐含了更具价值的知识和信息。因此数据挖掘对 象的进一步发展就是针对复杂类型数据的挖掘。复杂类型数据的挖掘主要包括：空间数 据挖掘，多媒体数据挖掘，时序数据挖掘，文本数据挖掘，w e b 数据挖掘，数据流挖掘 垒型3 7 】 弋to 2 2 数据挖掘过程 数据挖掘是从明确目标到评价结果的一系列活动，包括七个阶段【3 8 1 ： 1 ) 明确数据分析的目标。 2 ) 对数据进行选择、组织和预处理。 3 ) 探索性分析数据及转换。 4 ) 确定在分析阶段使用的统计方法。 5 ) 用选定的方法分析数据。 6 ) 评价和比较使用的方法，选择最后的分析模型。 7 ) 解释最终模型和它在决策过程中的应用。 1 明确目标 第二章数据挖掘综述 明确目标就是定义分析的目的。要弄清所分析的现象并不总是容易的。实际上，目 标通常是清楚的，但是潜在的问题很难转化为分析需要的具体目标。对问题和目标的明 确描述是正确建立分析的先决条件。这显然是最困难的部分，因为此时确定的目标决定 随后的方法如何组织，因此必须明确无疑。 2 组织数据 当目标确定后就该为分析选择数据了。首先要确定数据源，通常使用容易获得且可 靠的内部资源，这种数据还有一个优点，就是它产生于自己的经验和经历。用户的数据 仓库是理想的数据源，存储所有不会改变的历史数据，从中我们可以容易地抽取主题数 据库、数据集市或感兴趣的数据。如果没有数据仓库，则可以不同数据源创建数据集市。 一般地，数据集市的建立为随后的数据分析提供基本的输入，通常用列表形式表示， 称为数据矩阵，这基于分析的需求和前面所建立的目标。当一个数据矩阵建立后，要进 行初步的数据清洗，换句话说，就是对数据进行质量控制。这是一个用于找出现存的不 适于分析的变量的处理过程，同时起到检查变量内容、判断是否丢失数据或有不正确数 据的作用。如果有重要信息丢失，则需要检查这个阶段并找到根源。 最后，对数据子集或抽样的分析也是有用的。因为对于整个数据集市进行完全分析 得到的信息质量并不总是比研究抽样得到的更好。实际上，数据挖掘面对的数据库都是 很大的，使用抽样可以节省分析时间。可以对比抽样之外的数据来检验模型的正确性， 还可以减小统计模型因受噪声影响失去泛化和预测能力的危险。 3 数据的探索性分析 对数据的初步探索分析与o l a p 技术非常相似。初期对数据重要性的评价有助于原 始变量的转换、更好地理解现象或者导出基于满足特定初始假设的统计模型。探索分析 可以找到反常数据与其他项不同的数据项，这些数据项不能删除，因为它们可能含 有对于达到分析目标来说很重要的信息。对数据的探索性分析是必须的，它可以使分析 者预测哪一种统计方法最适合下一阶段的分析，而这一选择必须考虑在前一阶段得到的 数据的质量。探索分析可能会因为收集到的数据不够充分而要求重新抽取。 4 确定统计方法 有多种统计方法可以使用，也有许多算法，所以对于现存方法的分类是非常重要的。 方法的选择依赖于所研究的问题或数据变量的类型。数据挖掘过程由应用引导，因此方 法可以根据分析的目的分类。可以区分出三大类方法： a ) 描述性方法：旨在更加简要地描述数据类，它们也称为对称的、无监督的或间 接的方法。观测数据被划分为若干未知的类( 聚类分析法、k o h o n c n 图法) ，变量可能根 据未知的联系互相关联( 关联方法、对数线性模型、图模型) 。在这种方式中，变量在同 一层次处理，没有因果关系的假设。 ”预副性方法：旨在描述一个或多个同其他所有变量有关系的变量，它们也称为 不对称的、有监督的或直接的方法。这需要寻找分类规则或基于数据的预测，这些规则 帮助我们预测或分类未来的与解释变量或输入变量有关的一个或多个应答变量或目标 变量的结果。这种唤型的主要方法是从机器学习领域发展起来的，例如神经网络( 多层 感知器) 和决策树；也有经典的统计模型，如线性和对数回归模型。 第二章数据挖掘综述 c ) 局部方法：旨在识别数据库中子集的特征，描述性方法和预测性方法都是全局 的而非局部的。局部方法的例子有分析相关数据的关联规则、识别反常值( 异常值) 等。 从功能的观点看，这个分类是彻底的。每一个方法可以单独使用，也在多阶段分析 中应用于其中一个阶段。 5 数据分析 当统计方法确定后必须转化成可以计算的适当算法，以便从数据库中合成出需要的 结果。市场上有大量为数据挖掘所设计的专业或非专业软件。对于大多数的标准应用而 言，我们并不需要开发特定算法，这些软件提供的算法已经足够了。然而，控制数据挖 掘过程的算法必须对不同的方法和软件方案有彻底的理解，这样它们才能适应用户的特 殊需求，在获得决策时能正确地解释结果。 6 对统计方法的评价 从可用的统计模型中找到最好的数据分析模型，对于产生最终决策是必需的，因此 模型和决策规则的选择依赖于使用不同方法得到的结果之间的比较，这是对于将要用于 待处理数据的特定统计方法正确性的重要诊断检测。可能没有一个方法能够满足目标 集，这时要为分析重新寻找更适合的新方法。 在评价一个特定方法的性能及对统计类进行诊断测量时，必须考虑其他因素，例如 时间限制、资源限制、数据质量和数据的有效性。在数据挖掘中仅使用一种统计方法分 析数据是不可取的，不同的方法强调不同的方面，否则某一方而有可能被忽略。 选择最好的最终模型，需要快速简单地应用和比较不同方法，比较产生的结果，然 后对得到的不同规则给予商业评价。 7 方法的实现 数据挖掘不仅对数据进行分析，还要把结果集成到用户决策过程中。商业知识、抽 取规则和它们在决策过程中的参与，使我们从分析阶段转移到决策引擎的产生阶段。一 旦模型被选择并在数据集上测试，分类规则可被用于整个空间。例如可以预测哪些客户 更有可能使我们获利，可以对不同的消费群体使用不同的商业策赂，从而增加用户利润。 数据挖掘有这么多好处，因此正确地实现其过程，发挥它的全部潜能是很重要的。数据 挖掘内容必须渐进地开展，建立现实的目标，一直观察结果的推进，最终目标是把数据 挖掘与其他活动完全集成，以支持客户决策【3 l 】。 集成过程可以分为4 个阶段： i 策略阶段：这个阶段需要研究用到的商业过程，以便辨别数据挖掘可以带来哪 些益处，此阶段得到的结果将确定数据挖掘工程的商业目标和评价准则。 i i 训练阶段：在此阶段更加细致地评价数据挖掘活动，建立一个指导性计划，用 上一阶段确定的目标和准则评价结果。计划的选择是一个基础因素，必须简单易用，且 必须对产生利益足够重要。如果这个指导性计划是积极的，则有两种可能的结果：对不 同数据挖掘技术有用性的初步评价和对一个数据挖掘系统原型的定义。 i i i 创建阶段：如果指导性计划的评价结果是积极的，就要实现一个完整的数据挖 掘系统，这时需要建电一个详细的计划来重新组织包括数据挖掘活动在内的商业过程。 特别要重新组织商业数据库，有可能新建数据仓库，建立数据挖掘原型，直到拥有一个 第二章数据挖掘综述 初始的可运行版本为止，同时要分配时间和人员执行这个计划。 i v 整合阶段：此阶段的工作是恰当地准备组织，使数据挖掘过程可以成功地集成。 这意味着要指导用户了解新系统的潜力，增加他们获利的信心，不断地评估和交流从数 据挖掘过程中得到的有效结果。 2 3 数据挖掘技术分类 一般而言，数据挖掘的理论技术可分为传统技术与改良技术两种。传统技术以统计 分析为代表，统计学内所含序列统计、概率论、回归分析、类别数据分析等都属于传统 数据挖掘技术，尤其数据挖掘对象多为变量繁多且样本数庞大的数据，是以高等统计学 里所含括的多变量分析中用来精简变量的因素分析( f a c t o ra n a l y s i s ) 、用来分类的判别 分析( d i s c r i m i n a n t a n a l y s i s ) ，以及用来区别群体的分群分析( c l u s t e r a n a l y s i s ) 等，在 数据挖掘过程中特别常用 3 2 】。 在改良技术方面，应用较普遍的有决策树理论( d e c i s i o nt r e e s ) 、类神经网络( n e u r a l n e t w o r k ) 、遗传算法( g e n e t i ca l g o r i t h m ) 以及关联规则挖掘算法( a s s o c i a t i o nr u l e s ) 等。 决策树是一种用树枝状展现数据受各变量的影响情形之预测模型，根据对目标变量 产生之效应的不同而建构分类的规则，一般多运用在对客户数据的分析上，例如针对有 回函与未回函的邮寄对象找出影响其分类结果的变量组合，常用分类方法为c 埘。 ( c l a s s i f i c a t i o na n dr e g r e s s i o nt r e e s ) 及c h a i d ( c h i s q u a r ea u t o m a t i ci n t e r a c t i o n d e t e c t o r ) 两种【3 3 1 。 类神经网络是一种仿真人脑思考结构的数据分析模式，由输入变量与数值中自我学 习并根据学习经验所得知识不断调整参数以期建构数据的型样( p a t t e r n s ) 。类神经网络为 非线性的设计，与传统回归分析相比，好处是在进行分析时无须限定模式，特别当数据 变量间存有交互效应时可自动侦测出；缺点则在于其分析过程为一黑盒子，故常无法以 可读模型格式展现，每阶段的加权与转换亦不明确【3 4 】。 遗传算法是基于自然进化理论，模拟基因联合、突变、选择等过程的一种优化技术 【3 5 】 o 关联规则挖掘是知识发掘的领域中最常用的格式，是指从大量的数据项集间发掘出 有意义的、隐含的关联关系，这是一种由一连串的f 如果则( i f t h e n ) j 之逻辑规 则对数据进行细分的技术，在实际运用时如何界定规则为有效是最大的问题，通常需先 将数据中发生数太少的项目先剔除，以避免产生无意义的逻辑规则。 2 4 数据挖掘的功能 数据挖掘不仅能对过去的数据进行查询和遍历，并且能够对将来的趋势和行为进行 第二章数据挖掘综述 预测，并自动探测以前未发现的模式，从而很好地支持人们的决策。被挖掘出来的信息， 能够用于信息管理、查询处理、决策支持、过程控制以及许多其它应用。数据挖掘按其 功能划分主要包括以下几类【3 6 】： ( 1 ) 分类 分类是数据挖掘中应用的最多的方法。分类是找出一个类别的概念描述，它代表了 这类数据的整体信息，即该类的内涵描述，一般用规则或决策树模式表示。一个类的内 涵描述分为特征性描述和区别性描述。特征性描述是对类中对象的共同特征的描述，区 别性描述是对两个或多个类之间区别的描述。 ( 2 ) 关联分析 若两个或多个数据项的取值重复出现且概率很高时，它就存在着某种关联，可以建 立起这些数据项的关联规则。关联分析的目的是找出数据库中隐藏的关联网。在大型数 据库中，这种关联规则是很多的，一般用“支持度 ，“可信度”两个阈值来淘汰那些无 用的关联规则。 ( 3 ) 聚类 数据库中的数据可分为一系列有意义的子集或称为类。在同一类别中，个体之间的 距离较小，而不同类别的个体之间的距离偏大。聚类增强了人们对客观现实的认识，即 通过聚类建立宏观概念。 ( 4 ) 序列模式 通过时间序列搜索出重复发生概率较高的模式，这里强调时间序列对挖掘结果的影 响。 ( 5 ) 偏差检验 数据库中的数据常有一些异常记录，从数据库中检测出这些偏差很有意义。偏差包 括很多潜在的知识，如分类中的反常实例、不满足规则的特例、观测结果与模型预测值 的偏差、量值随时间的变化等。偏差检测的基本方法是寻找观测结果与参照之间的差别。 ( 6 ) 预测 预测是利用历史数据找出变化规律，即建立模型，并用此模型来预测未来数据的种 类、特征等。 2 5 关联规则挖掘方法 关联规则( a s s o c i a t i o nr u l e s ) 是由m m 的q u e s t 研究组的a g r a w a l 等人于19 9 3 年 首先提出了挖掘顾客交易数据库中项集间的关联规则问题，他提出的关联规则是发现交 易数据库中不同商品( 项) 之间的联系，并通过这些规则找出顾客的购买行为模式，如购 买了某一商品的同时会购买其它的商品，以及购买后对其他商品的影响。发现这样的规 则可以应用于商品货架设计、库存安排以及根据购买模式对用户进行分类。关联规则是 数据挖掘的一个重要研究内容，它反映了大量数据中项目集之间有趣的关联或相关联 系，成为近年来数据挖掘研究领域的一个热点t 37 1 。 第二章数据挖掘综述 2 5 1 关联规则研究现状 关联规则作为一个研究领域仅仅是最近几年的事情，但是在出现后的几年里已经成 为数据库界广泛研究的热点。关联规则的概念最早是由a g r a w a l 等人提出的，随后，诸 多的研究人员对其进行了大量研究p 引。他们的工作包括对原有的算法进行优化，如引入 随机采样、并行的思想等，以提高算法挖掘的效率；还有就是对关联规则的应用进行推 广等。关联规则的研究主要是算法和实施，理论上的研究主要是针对不同数据形式的最 优算法，实际应用则强调关联规则与数据库技术的紧密配合及实施方法的选择。 a g r a w a l 于1 9 9 3 年在文献【l3 】中第一次提出了关联规则的基本概念，并且给出了一 个初始的a i s 算法；a g r a w a l 又于1 9 9 5 年在文献【1 2 】中提出了经典的a p d o f i 算法，这个 算法奠定了关联规则挖掘算法的基础，该算法中所使用的思想在其它多个算法中被使 用。同时，在文献【l2 j 中还提出了一个改进的算法a p r i o r i t i d 算法和其它两个算法的结合 a p f i o f i h y b f i d 算法。随后，许多人对a p r i o r i 算法进行了改进。p a r k 等人在文献【1 4 】【b 】提 出