（计算机应用技术专业论文）关联规则更新算法研究与应用.pdf

关联规则更新算法的研究与应用 摘要 数据挖掘( 或知识发现) 出现于2 0 世纪8 0 年代末，目前已经成为人工智 能和数据库等领域的研究热点。它有着广阔的应用前景，并将在新的世纪里在 各个领域发挥其强大的生命力。r a g r a w a l 等在1 9 9 3 年提出了关联规则问题， 现在关联规则已经成为数据挖掘研究的重要方向，并且吸引了众多学者和专家 的关注。 关联规则挖掘的典型算法是由r a g r a w a l 等提出的a p r i o r i 算法。a p r i o r i 算法在计算侯选项目集的支持度时需要多次扫描整个数据库，而随着k 的增大， 不仅k 维项目集的数目减少了，而且能包含这些项目集的事务也是很少的。由 于数据规模大且时常更新，使得采掘效率较低，必须设计更有效的算法。另外， 当数据库中增加新的数据时，现有的多数算法要重新扫描整个大型数据库，而 且现有算法中项目集的支持度是基于整个数据库计算的，当新增的数据中出现 新项目时，即使包含新项目的项目集频繁地出现，现有算法常把这些项目集作 为非频繁项目集，由此产生的关联规则不能反映最近的商业活动。 基于数据挖掘的研究现状和关联规则挖掘算法存在的闯题，本文主要进行 了以下的研究工作： ( 1 ) 数据挖掘技术的分析与研究。在介绍数据挖掘基本概念的基础上，对数 据挖掘与传统分析方法、数据库中的知识发现和联机分析处理做了深入地分析 和比较，对数据挖掘的对象、可发现的模式进行了详细地分类、归纳和总结， 对数据挖掘常使用的技术做了介绍和分析。 ( 2 ) 关联规则数据挖掘技术的分析与研究。在提出关联规则基本概念的基础 上，本文对关联规则的种类进行了全面地分类、归纳和总结，对关联规则的典 型挖掘算法及其基本思想进行了详细地归纳、分析和研究，对各算法之问的差 别进行了客观地比较。同时，也详细地讨论了提高算法效率的各种优化技术， 客观地分析了它们的优缺点和利与弊。 ( 3 ) 针对a p r i o r i 算法的不足，提出了一种新的关联规则的高效挖掘算法。 新算法根据支持度对事务数据库进行筛选删除操作，使得在计算候选集支持度 时，所扫描的事务数据库比原来的事务数据库小，从而提高整个算法的效率： 同时，采用了一种新的产生候选集的算法，该算法避免了原有算法在产生候选 集时，对频繁集的多次扫描，提高了效率。 ( 4 ) 作为一个应用，本文对c r m 做了较全面地分析，结合数据仓库知识，探 讨了如何把数据挖掘技术及关联规则挖掘应用于c r m 中，辅助企业较好地管理 客户。 关键词：数据挖掘：关联规则：频繁项目集：最小频繁概念格：客户关系管理 2 a l g o r i t h mr e s e a r c ha n da p p l i c a t i o no fu p d a t i n g a s s o c i a t i o nr u l e s a b s t r c a t d a t am i n i n go rk n o w l e d g e d i s c o v e r ye m e r g e i n gi nt h el a t e19 8 0 sh a sb e c o m ea h o t s p o ti nt h ef i e l d so fa r t i f i c i a li n t e l l i g e n c ea n dd a t a b a s et e c h n o l o g y d a t am i n i n g h a si t sw i d ea p p l i c a t i o np r o s p e c ta n di se x p e c t e dt oc o n t i n u et of l o u r i s hi nt h en e w m i l l e n n i u m ra g r a w a le t e f i r s tp u tf o r w a r dt h ei s s u eo fm i n i n ga s s o c i a t i o nr u l e s i n19 9 3 n o wi th a sb e e na s i g n i f c a n tc o n t e n to fd a t am i n i n ga n ds od r a w sm u c h a t t e n t i o no fm a n yr e s e a r c h e r s t h et y p i c a la l g o r i t h mo fa s s o c i a t i o nr u l ei s a p r i o r it h a ti sp u tf o r w a r db y r a g r a w a l h o w e v e r ，i nc a l c u l a t i n gt h es u p p o r to fc a n d i d a t ei t e m s e t s ，t h e a l g o r i t h mn e e dt os c a nt h ew h o l ed a t a b a s e so fc i r c u l a t i o n sa p r i o r i b u ta st h e i n c r e a s e so fk ，n o to n l yt h en u m b e ro fk - i t e m s e t sr e d u c eb u ta l s ot h et h i n g sw h i c h i n c l u d et h e s ei t e m s e t sb e c o m ef e w b e c a u s ed a t ab e c o m e l a r g e r a n dr e n e w f r e q u e n t l y , i ti sr a t h e rd i f f i c u l tt od e s i g ne f f e c t i v ed a t am i n i n ga l g o r i t h m s i n a d d i t i o n ，m o s to ft h ea l g o r i t h m sm u s ts c a nt h ew h o l el a r g ed a t a b a s ew h e nn e wd a t a a r ea d d e dt oi t m o r e o v e r ，t h ei t e m s e t sw h i c hi n c l u d e sn e wi t e r n sw i l lb eo f t e n r e g a r d e da su n f r e q u e n ti t e m s e t se v e ni ft h e yh a p p e n e df r e q u e n t l yi nn e wd a t as e t b e c a u s et h es u p p o r to ft h ei t e m s e t si sc a l c u l a t e db a s e do nt h ew h o l ed a t a b a s e s o t h ea s s o c i a t i o nr u l e sc o m ef r o ma b o v ef r e q u e n ti t e ms e t sc a n tr e f l e c tt h er e c e n t b u s i n e s sa c t i v i t i e s b a s e do nt h er e s e a r c hb a c k g r o u n d so fd a t am i n i n ga n dt h ep r o b l e m so fe x i s t i n g a s s o c i a t i o nr u l ea l g o r i t h m s ，t h i sd i s s e r t a t i o nh a v ef i n i s h e dt h ef o l l o w i n gw o r k ： ( 1 ) a n a l y s et h ec u r r e n td a t am i n i n gt e c h n i q u e s b a s e do nt h eb a s i cc o n c e p t so f d a t am i n i n g ，t h i sd i s s e r t a t i o nc o m p a r e sa n d a n a l y s e st h ed i f f e r e n c e so fd a t am i n i n g a n do t h e rm e t h o d ss u c ha sk d da n do l a p , c l a s s i f i e sa n ds u m m a r i z e st h eo b j e c t s o fd a t am i n i n g ，t h ef i n d a b l ep a t t e r n sa n dt h ec o m m o nt e c h n i q u e si nd e t a i l ( 2 ) a n a l y s et h ec u r r e n td a t am i n i n gt e c h n i q u eo fa s s o c i a t i o nr u l e s b a s e do nt h e b a s i cc o n c e p t so ft h ea s s o c i a t i o nr u l e s ，t h i sd i s s e r t a t i o nc l a s s i f i e sa n ds u m m a r i z e s i t s s p e c i e sr o u n d l ya n ds u m m a r i z e s ，a n a l y s e sa n ds t u d i e si t st y p i c a lm i n i n g a l g o r i t h m sa n dt h e s ea l g o r i t h m s b a s i ci d e a si nd e t a i l i ns u c c e s s i o n ，t h ed i f f e r e n c e s a m o n gt h e s ea l g o r i t h m sa r ec o m p a r e do b j e c t i v e l y a l lk i n d so fo p t i m i z e d t e c h n i q u e sw h i c ha r ed e s i g n e dt op r o m o t et h ea l g o r i t h m se f f c i e n c ya r ea l s os t u d i e d a n dd i s c u s s e di nd e t a i lh e r ea n da tt h es a m et i m et h e i rm e r i t sa n dd e f e c t sa r e 3 a n a l y s e do b je e t i v e l y ( 3 ) t ot h ed e f i c i e n c yo fa p r i o r ia l g o r i t h m ，t h i sd i s s e r t a t i o nb r i n g sf o r w a r d a h i g h e f f i c i e n ta l g o r i t h m f o rm i n i n ga s s o c i a t i o nr u l e t h en e wa l g o r i t h mc a n f i l t e r a n dd e l e t er e c o r d so ft h ed a t a b a s ew i t ht h es u p p o r to fc a n d i d a t ei t e s m s e t s b e c a u s e t h ed a t a b a s es c a r e df o rt h es u p p o r to fi t e m s e t si s s m a l l e rt h ei t so r i g i n a l ，t h e e f f i c i e n c yo fw h o l ea l g o r i t h mc a r lb ei m p r o v e d a t t h es a m et i m e ，an e wm e t h o do f g e n e r a t i o no fc a n d i d a t ei s i n t r o d u c e dw h i c hc a na v o i dm a n ys c a d sf o ri t e m s e t s w h i l eg e n e r a t i n g ，t h u si m p r o v et h ew h o l ee f f i c i e n c y 。 ( 4 ) a tt h ee n d ，t h i s d i s s e r t a t i o na n a l y s e s t h ec u s t o m e rr e l a t i o n s h i p m a n a g e m e n tr o u n d l y ，d i s c u s s e st h ea p p l i c a t i o no f d a t am i n i n ga n da s s o c i a t i o nr u l e s i nc r mb a s e do nd a t aw a r e h o u s e k e y w o r d s ：d a t am i n i n g ；a s s o c i a t i o nr u l e s ； c o n c e p tl a t t i c e 4 f r e q u e n ti t e m s e t ；m i n i m u mf r e q u e n t 插图清单 图2 1一颗简单的决策树9 图3 1概念分层图1 4 图3 2增量式更新算法的过程2 4 图4 一lq c l f u a m m f i 算法和f u a m m f i 算法比较( 1 ) 一3 5 图4 2q c l f u a m m f i 算法和f u a m m f i 算法比较( 2 ) 3 6 7 表格清单 表4 1事务数据库d 3 4 表4 2事务数据集d 3 4 表5 1 项目名与项目号对照表4 l 表5 2 交易数据库4 2 表5 3 频繁项目集l ( d + d ) 4 3 表5 4 关联规则存储表4 3 表5 5 关联规则表示4 3 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成 果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得金避王些太堂 或其他教育机构的学位或 证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了 明确的说明并表示谢意。 学位论文作者签名：语沥 签字日期：砌7 年1 7 i 旦一当7 日 学位论文版权使用授权书 本学位论文作者完全了解金目墨王些太堂有关保留、使用学位论文的规定，有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授 权金胆王些太堂可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采 用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：般 签字日期：勿卿年9 月爿日 学位论文作者毕业后去向： 工作单位： 通讯地址： 2 导师签名： 签字日期： 电话： 邮编： 第一章综述 信息社会海量数据充斥人们的世界。如何从大量繁杂无绪的数据信息中分 析提取，发现人们需要的有用的知识和信息成为数据库、人工智能、机器学习 以及统计学等领域研究的热点。数据挖掘在这个背景下应运而生，并成为二十 年来人们不断研究和探索的课题。 1 1 数据挖掘的产生及研究现状 随着数据库技术的迅速发展以及数据库管理系统的广泛应用，人们积累的 数据越来越多。爆炸式增长的数据背后隐藏着许多重要的信息，人们希望能够 对其进行更高层次的分析，以便更好地利用这些数据。目前的数据库系统可以 高效地实现数据的录入、查询、统计等功能，但无法发现数据中存在的关系和 规则，无法根据现有的数据预测未来的发展趋势。缺乏挖掘数据背后隐藏的知 识的手段，导致了“数据爆炸但知识贫乏”的现象。 计算机技术的另一领域一人工智能自1 9 5 6 年诞生之后取得了重大进展。 经历了博弈时期、自然语言理解、知识工程等阶段，目前的研究热点是机器学 习。机器学习是用计算机模拟人类学习的一门科学，比较成熟的算法有神经网 络、遗传算法等。 用数据库管理系统来存储数据，用机器学习的方法来分析数据，挖掘大量 数据背后的知识，这两者的结合促成了数据库中的知识发现( k d d ：k n o w l e d g e d i s c o v e r yi nd a t a b a s e s ) 的产生。实际上，数据库中的知识发现是一门交叉性 学科，涉及到机器学习、模式识别、统计学、智能数据库、知识获取、数据可 视化、高性能计算、专家系统等多个领域。从数据库中发现出来的知识可以应 用在信息管理、过程控制、科学研究、决策支持等许多方面。 1 9 8 9 年8 月，在美国底特律召开的第1 l 届国际人工智能联合会议的专题 讨论会上首次出现k d d 这个术语。随后在1 9 9 1 年、1 9 9 3 年和1 9 9 4 年都举行k d d 专题讨论会，汇集来自各个领域的研究人员和应用开发者，集中讨论数据统计、 海量数据分析算法、知识表示、知识运用等问题。随着参与人员的不断增多， k d d 国际会议发展成为年会。1 9 9 5 年，在美国计算机年会( a c m ) 上，提出了数据 挖掘( d m ：d a t am in i n g ) 的概念。1 9 9 8 年在美国纽约举行的第四届知识发现与 数据挖掘国际学术会议不仅进行了学术讨论，并且有3 0 多家软件公司展示了他 们的数据挖掘软件产品，不少软件已在北美、欧洲等国得到应用。 由于数据库中的数据被形象地比喻为矿床，因此，数据挖掘一词很快流传 开来。由于它应用的普遍性及由此带来的高效益，数据挖掘己成为一个具有广 阔应用前景的热门研究方向。在一份最近的c a r t n e r 报告中列举了在今后3 5 年内对工业将产生重要影响的五项关键技术，数据挖掘就是其中的一项。 我国的数据挖掘研究开始于9 0 年代中期，到9 0 年代中后期，初步形成了 知识发现和数据挖掘的基本框架。自9 0 年代中期一批研究成果( 学术论文) 逐渐 发表在计算机学报、计算机研究与发展、软件学报、人工智能与模式 识别等刊物上，研究重点也正在从发现方法转向系统应用，并且注重多种发 现策略和技术的集成，以及多种学科之间的相互渗透。但是基本上还是以学术 研究为主，实际应用上处于起步阶段。1 9 9 3 年国家自然科学基金首次支持对该 领域的研究项目。目前，国内的许多科研单位和高等院校竞相开展知识发现的 基础理论及其应用研究，如清华大学、中科院计算技术研究所、空军第三研究 所、海军装备论证中心等。其中，华中理工大学、复旦大学、浙江大学、中国 科技大学、中科院数学研究所、吉林大学等单位开展了对关联规则开采算法的 优化和改造：南京大学、四i l 大学和上海交通大学等单位探讨、研究了非结构化 数据的知识发现以及w e b 数据挖掘。目前进行的大多数研究项目是由政府资助 进行的，如国家自然科学基金、8 6 3 计划、“九五 计划等。 1 2 数据挖掘中的关联规则 目前，数据挖掘的主要研究领域为数据总结、分类、聚类、关联规则等方 面。关联规则表示数据库中一组对象之间某种关联关系的规则。例如，关联规 则可以表示为“购买了项目a 的顾客中有9 0 9 6 的人又买了项目b 。从这些规则 可找出顾客购买行为模式，可以应用于商品货架设计、生产安排、针对性的市 场营销等。采用关联模型比较典型的例子是“啤酒和尿布 的故事。在美国， 一些年轻的父亲下班后经常到超市去买婴儿尿布，超市经过对顾客的购物信息 进行挖掘，发现在购买婴儿尿布的年轻父亲中，有3 0 - 4 0 0 ) 的人同时要买一些 啤酒。超市随后调整了货架的摆放，把尿布和啤酒放在一起。结果是：销售额明 显增加了。 关联规则问题由a g r a w a l 等于1 9 9 3 年首先提出，以后诸多的研究人员 对关联规则的挖掘问题进行了大量的研究。他们的工作包括对原有的算法进行 优化，如引入随机采样、并行的思想、增加衡量标准、规则约减、改变存储结 构等，以提高算法挖掘规则的效率：提出各种变体，如泛化的关联规则、周期关 联规则等，对关联规则的应用进行推广。 1 3 本文的主要工作 本文在以上的研究背景下，对数据挖掘技术，尤其是关联规则数据挖掘技 术进行了较为深入、全面、详尽的分析和研究，主要包括以下一些内容： ( 1 ) 数据挖掘技术的分析与研究。在介绍数据挖掘基本概念的基础上， 对数据挖掘与传统分析方法、数据库中的知识发现和联机分析处理做了深入地 2 分析和比较，对数据挖掘的对象、可发现的模式进行了详细地分类、归纳和总 结，对数据挖掘常使用的技术做了介绍和分析。 ( 2 ) 关联规则数据挖掘技术的分析与研究。在提出关联规则基本概念的 基础上，对关联规则的种类进行了全面地分类、归纳和总结，对关联规则的典 型挖掘算法及其基本思想进行了详细地归纳、分析和研究，对各算法之间的差 别进行了客观地比较。同时，也详细地讨论了提高算法效率的各种优化技术， 客观地分析了它们的优缺点和利与弊。 ( 3 ) 针对f u a m m f i 算法的不足，提出了一种新的更新最大频繁项集的高 效挖掘算法q c l f u a m m f i 。新算法在量化概念格的基础上，引进最小频繁概念格 的概念，能够在原有挖掘结果的基础上，快速有效地挖掘出更新后的数据库中 隐含的新最大频繁项目集，该算法避免了原有算法往返多次扫描数据库和新增 数据集，以计算每一个可能项目集的支持数的做法，从而提高整个算法的效率。 1 4 本文的结构 本文在第二章简单介绍了数据挖掘的概念、对象及发现模式和采用数据挖 掘的技术；对数据挖掘技术做了一个简要的概述；第三章介绍了关联规则的基 本概念以及它的分类，以经典频繁项目集算法a p r i o r 为基础时，介绍了几种优 化方法：分布式并行关联规则挖掘算法、基于h a s h 的优化方法、基于采样的 优化方法以及基于事物压缩的优化方法，并重点举例介绍了增量式更新算法的 思想；第四章首先对a p r i o r 、基于划分的算法、d h p 和增量式更新算法的优缺 点进行总结，并详细介绍了一种在动态数据库中进行更新最大频繁项目集挖掘 的算法f u a m m f i 。针对此算法因为在挖掘过程中采用了往返多次扫描数据库和 新增数据集，以计算每一个可能项目集的支持数的技术而造成效率低下的状况， 本章提出将量化概念格移植到算法中以避免该现象的出现，从而提高了挖掘效 率即q c l f u a m m f i 算法；第五章将第四章介绍的q c l f u a m m f i 算法应用于c r m 系 统中，快速地在更新后的数据库中挖掘出新的关联规则，从而使得商场可以调 整他们的整个市场策略，并且对顾客的反馈数据进行跟踪，产生具有竞争性的 市场策略。 第二章数据挖掘概述 有人说，数据挖掘将成为继网络之后的下一个技术热点，这种说法并不为 过! 近年来，数据挖掘已经引起了信息产业界的极大关注，这是快速增长的数据 量和日益贫乏的信息量之间矛盾运动的必然结果。在对基于关联规则的数据挖 掘算法进行深入研究之前，有必要对数据挖掘的概念，挖掘的对象、产生的模 式及常用的技术等内容作一个较为全面的介绍，以期更加透彻地领悟数据挖掘 这一极具发展潜力的新兴领域1 7 2 1数据挖掘的概念 从广义上讲，数据挖掘( d a t am i n i n g - d m ) 是指从大量的、不完全的、有噪 声的、模糊的、随机的数据中，提取隐含在其中的、人们事先不知道的、但又 是潜在有用的信息和知识的过程心1 。这个定义包括以下四个层次的含义： ( 1 ) 数据源必须是真实的、大量的、含噪声的： ( 2 ) 发现的是用户感兴趣的知识： ( 3 ) 发现的知识要可接受、可理解、可运用，最好能用自然语言表达发现 结果： ( 4 ) 并不是要求发现放之四海皆准的知识，也不是要去发现崭新的自然科 学定理和纯数学公式，更不是什么机器定理证明，所有发现的知识都是相对的， 是有特定前提和约束条件、面向特定领域的。 从商业角度出发，数据挖掘可以描述为：按企业既定业务目标，对大量的 企业数据进行探索和分析，揭示隐藏的、未知的或验证己知的规律性，并进一 步将其模型化的先进有效的方法。 2 1 1 传统分析方法与数据挖掘 传统分析方法包括查询、报表、联机应用分析等，它与数据挖掘的本质区 别是数据挖掘是在没有明确假设的前提下去挖掘信息、发现知识。数据挖掘所 得到的信息应具有先前未知性、有效性和可实用性三个特征。 先前未知性是指挖掘出的信息是预先未曾预料到的，即数据挖掘是要发现 那些不能靠直觉发现的信息或知识，甚至是违背直觉的信息或知识。挖掘出的 信息越是出乎意料，就可能越有价值。在商业应用中最典型的例子就是家连 锁店通过数据挖掘发现了小孩尿布和啤酒之间有着惊人的联系。有效性是指挖 掘出的信息必须是有效信息，无效信息对我们是没有任何价值的。可实用性是 指挖掘出的信息必须能应用于实际的操作，指导实际的决策。 4 2 1 2数据库中的知识发现与数据挖掘 数据库中的知识发现k d d ( 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 9 8 9 年8 月举行的第1 1 届国际联合人工智能学术会议上。其后许多专家 都给出了有关k d d 的定义、在k d d 研究领域一致认可的描述性定义是f a y y a d 等人给出的：k d d 是从数据中识别出有效的、新颖的、潜在有用的、以及最终可 理解的模式的非平凡过程n 1 。数据挖掘是k d d 最核心的部分，是采用机器学习、 统计等方法进行知识学习的阶段。数据挖掘算法的好坏将直接影响到所发现知 识的好坏。人们往往不严格区分数据挖掘和数据库中的知识发现，把两者混淆 使用。一般在科研领域中称为k d d ，而在工程领域则称为数据挖掘。 2 1 3 联机分析处理与数据挖掘 联机分析处理( o l a p ) 哺1 是决策支持领域的部分。o l a p 分析师首先建立一 系列的假设，然后通过o l a p 来证实或推翻这些假设以最终得到自己的结论。 o l a p 分析过程在本质上是一个演绎推理的过程。但是如果分析的变量达到几十 或上百个，那么再用o l a p 手动分析验证这些假设将是一件非常困难和痛苦的事 情。比如，一个分析师想找到什么原因导致了贷款拖欠，他可能先做一个初始 的假定，认为低收入的人信用度也低，然后用o l a p 来验证他的这个假设。如果 这个假设没有被证实，他可能去察看那些高负债的账户，如果还不行，他也许 要把收入和负债一起考虑，一直进行下去，直到找到他想要的结果或放弃。 与o l a p 不同的是，数据挖掘不是用于验证某个假定的模式( 模型) 的正确 性，而是在数据库中自己寻找模型。其分析过程在本质上是一个归纳的过程。 比如，一个用数据挖掘工具的分析师想找到引起贷款拖欠的风险因素。数据挖 掘工具可能帮他找到高负债和低收入是引起这个问题的因素，甚至还可能发现 一些分析师从来没有想过或试过的其他因素，比如年龄大小、婚姻状况等。 数据挖掘和o l a p 具有一定的互补性。一方面，在利用数据挖掘所得出的 结论采取行动之前，你也许要验证一下如果采取这样的行动会给公司带来什么 样的影响，那么o l a p 工具能回答你的这些问题。另一方面，在知识发现的早期 阶段，o l a p 工具还可以帮你探索数据，找到哪些是对一个问题比较重要的变量， 发现异常数据和互相影响的变量。这些都能帮助你更好的理解你的数据，加快 知识发现的过程。 2 2 数据挖掘的对象 原则上讲，数据挖掘可以在任何类型的信息存储上进行，这包括关系数据 库、数据仓库、事务数据库、w w w 、面向对象数据库、对象一关系数据库、时间 序列数据库、空间数据库，厂文本数据库，多媒体数据库等。挖掘的原始数据 可以是结构化的，如关系数据库、数据仓库中的数据：也可以是半结构化的，如 5 文本、图形和图像数据：甚至是分布在网络上的异构型数据。下面就几个重要的 数据挖掘对象予以介绍。 2 2 1 关系数据库 关系数据库是表的集合，每个表都被赋予一个唯一的名字，包含一组属性 ( 列或字段) ，并通常存放大量元组( 记录或行) 。关系中的每一个元组代表一个 被唯一的关键字标识的对象，并被一组属性值描述。语义数据模型，如实体一 联系( e r ) 数据模型，将数据库作为一组实体和它们之间的联系进行建模。 关系数据库可以通过数据库查询访问。数据库查询使用如s q l 这样的结构 化查询语言，或借助于图形用户界面书写。关系查询语言包含了连接、选择、 投影等操作，还包含了聚集函数，可以回答诸如“哪一月份销售额最高? ”，“按 分店分组，显示上月总销售额。等问题。 数据挖掘用于关系数据库时，可以进一步搜索趋势或关系模式。例如，可 以根据顾客的收入、年龄和以前的信用信息预测新顾客的信用风险，可以检测 偏差，发现与以前的年份相比，哪种商品的销售出人预料等。 关系数据库具有完备的数学理论基础和广泛的普及度，是数据挖掘最流 行、最丰富的数据源，是数据挖掘研究的最主要的数据形式。 2 2 2 事务数据库 一般地说，事务数据库由一个文件组成，其中每个记录代表一个事务。通 常，一个事务包含一个唯一的事务标识号t r a n s - i d ( 如信用卡号) 和一个组成事 务的项的列表( 如顾客购买的商品) ，有的还包含事务的处理时间。事务数据库 还可能有一些与之相关联的附加表，包含关于事务的其他信息。事务数据库通 常用于“购物篮数据分析 ，对于关联规则数据挖掘非常有效。 2 2 3网络 网络是重要的数据挖掘对象，其中，对万维网( w o r dw id ew e b ) 的挖掘尤 为有用。w w w 和与之相关联的分布式信息服务( 如g o o g l e ，y a h o o ! ) 为人们提供 了丰富的、世界范围的联机信息服务，这里，数据对象被链接在一起，便于交 互访问。用户通过链接，可以很容易地从一个对象跳到另一个对象，寻找有趣 的信息。w w w 为数据挖掘提供了大量机会和挑战。例如，挖掘路径遍历模式不 仅能够帮助改进系统设计( 提供高度相关的对象间的有效访问) ，而且还可以引 导更好的市场决策( 在频繁访问的文档上布置广告，或提供更好的顾客用户分 类和行为分析) 。尽管网页看上去好象信息丰富，但它们实际上是非结构化的并 且缺乏预定义的模式、类型和格式，这就使计算机很难理解各种网页的语义并 把它们以有组织的形式结构化。基于关键字的搜索服务只能给用户提供有限的 6 帮助，我们需要更高级的数据挖掘工具在w w w 上寻找并提供更有趣的信息，当 然，这些都为高级的数据挖掘提出了新的挑战1 2 3 数据挖掘的发现模式 随着数据挖掘和知识发现( d m k d ) 的研究逐步走向深入，其研究已经形成了 三个强大的技术支柱：数据库、人工智能和数理统计。目前，d m k d 的主要研究 内容包括基础理论、发现算法、数据仓库、可视化技术、知识表示方法、发现 知识的维护和再利用、半结构化和非结构化数据中的知识发现以及网上数据挖 掘等。下面就数据挖掘所发现的最常见的知识模式( 类型) 做一简单介绍，所介 绍的这些知识都可以在不同的概念层次上被发现，随着概念树的提升，从微观 到中观再到宏观，以满足不同用户、不同层次决策的需要。 2 3 1 关联模式 关联模式( a s s o c i a t i o np a t t e r n ) 是反映一个事件和其他事件之间相互依 赖或关联的知识。经典的关联规则发现方法可分为两步：第一步是迭代识别所有 的频繁项集，要求频繁项集的支持率不低于用户设定的最低值：第二步是从频繁 项集中构造可信度不低于用户设定的最低值的规则。识别或发现所有频繁项集 是关联规则发现算法的核心，也是计算量最大的部分。在进行关联知识发现时， 需要由用户输入最小置信度c 和最小支持度s 。 2 3 2 序列模式 序列模式( s e q u e n c ep a t t e r n ) 分析和关联分析相似，其目的也是为了挖掘 数据之间的联系，但序列模式分析的侧重点在于分析数据间的前后序列关系。 它能发现数据库中形如“在某一段时间内，顾客购买商品a ，接着购买商品b ， 而后购买商品c ，即序列a b c 出现的频度较高 之类的知识，序列模式分 析描述的问题是：在给定交易序列数据库中，每个序列是按照交易时间排列的一 组交易集，挖掘序列函数作用在这个交易序列数据库上，返回该数据库中出现 的高频序列。在进行序列模式分析时，同样需要由用户输入最小置信度c 和最 小支持度s 。 2 3 3分类模式 设有一个数据库和一组具有不同特征的类别( 标记) ，该数据库中的每一个 记录都赋予一个类别的标记，这样的数据库称为示例数据库或训练集。分类分 析就是通过分析示例数据库中的数据，为每个类别做出准确的描述或建立分析 模型或挖掘出分类规则，然后用这个分类规则对其它数据库中的记录进行分类。 导出模型是基于对训练数据集( 即其类标记己知的数据对象) 的分析而产生的。 7 分类模式的预测值可以是离散的( 如根据某种动物的特征来判断这种动物是两 栖动物还是哺乳动物) ，也可以是连续的( 如根据某人的受教育情况和工作经验 来判断这个人的工资范围) 。 2 3 4 聚类模式 聚类分析和分类分析是一个互逆的过程。在统计方法中，聚类分析是多元 数据分析的三大方法之一( 其它两种是回归分析和判别分析) 。在机器学习中， 聚类分析被称作无监督或无教师归纳。在人工智能文献中，聚类也称概念聚类。 与分类分析不同，聚类分析输入的是一组未分类记录，并且这些记录应分成几 类事先也不知道。聚类分析就是通过分析数据库中的记录数据，根据一定的分 类原则，合理地划分记录集合，确定每个记录所在类别。数据库中的记录被划 分为的一系列有意义的子集叫做聚( 簇) 类。分类原则采用最大化类内的相似性、 最小化类间的相似性原则，即使得一个簇中的对象具有很高的相似性，而与其 他簇中的对象很不相似。 2 4 数据挖掘的技术 数据挖掘的研究领域涉及广泛，主要包括数据库系统、人工智能、机器学 习、统计学和数据可视化等领域，其采用的技术也较多。在数据挖掘中，我们 很少采用一种工具或技术。对于一个给定的问题，数据本身的特点会影响如何 选择技术，因此，为了发现可能最好的模型，我们应使用多种技术或工具。下 面将对数据挖掘中经常采用的技术做一介绍和分析。 2 4 1神经网络 人工神经网络是模拟人类的形象直觉思维，是在生物神经网络的基础上， 根据生物神经元和神经网络的特点，通过简化、归纳、提炼总结出来的一类并 行处理网络。神经网络对于规模大而复杂的问题，如包含几百个相互作用的独 立变量，可以有效地建立模型，因此人们对神经网络非常感兴趣。它可用于解 决数据挖掘中的分类问题( 输出变量是离散的) 和回归问题( 输出变量是连续 的) 。 2 4 2决策树 决策树的基本思想是利用树的结构将数据记录进行分类，树的一个叶结点 就代表某个条件下的一个记录集，根据记录字段的不同取值建立树的分支：在每 个分支子集中重复建立下层结点和分支，便可生成一棵决策树。 决策树是用一系列规则导出一类值的一种方法。例如，用决策树把贷款申 请者分成好的信用和不好的信用。图2 - 1 是用于解决这类问题的一棵简单的决 策树，它包含决策树的所有组成：决策结点、分支和叶子。 衫5 。矽 g o o d r i s k 日丽r i 呔8 a d 鼬s kg o o dr i 呶 图2 1 一颗简单的决策树 根结点是其中的一个组成部分，它说明正在进行的判断条件，图2 - 1 中的 根结点是“i n c o m e $ 4 0 ，0 0 0 ”。判断的结果使树分成两个分支，每个分支代表各 种判断结果的答案。在图2 1 中，根据回答是“y e s ”或者“n o ”，而选择不同 的分支。 根据不同的算法，每个结点可选择两个或更多的分支。例如，c a r t 算法中 每个结点只产生两个分支。每个分支可以是一个决策树，也可以是叶子结点。 有了决策树和贷款申请，我们就能决定申请者是好的信用还是不好的信用。如 一位申请者“i n c o m e s 4 0 ，0 0 0 ”且“h i g hd e b t ”，那么就把他归于信用不好的 一类申请者中，同样如一位申请者“i n c o m e 5y e a r s ， 那么就把他归于信用好的一类申请者中。 决策树也能很好地处理非数值型的数据。它能接受分组的数据，这能减少 数据转变的数量，并能使神经网络固有的独立变量的组合爆炸最小化。 2 4 3遗传算法 遗传算法就其本身来说并不是用来发现模式，只是用来指导其它数据挖掘 算法的学习过程，遗传算法为在解空间里寻找好的模型作指导。 遗传算法之所以这么称呼，是因为它遵循生物进化的模式，把它们的特征 一代一代地遗传下去，直到找到最好的模型。被遗传的信息称为基因，它包含 所建立的模型的参数。 例如，在建一个神经网络时，遗传算法能替代反向传播的方法来调整权值。 在这种情况下，基因包含权值。另外，遗传算法能用来找到最佳构造，这时基 因包含隐含层的数目和每一层的结点数。 2 4 4 可视化技术 数据可视化技术经常和其它的数据挖掘技术结合起来使用，它能够对数据 进行有效分析，其重要性是不能低估的。 9 可视化技术是一种图形显示技术。例如，把数据库中多维数据变成多种图 形，这对于揭示数据中内在本质以及分布规律起到很大的作用。对数据挖掘过 程可视化，并进行人机交互可提高数据挖掘的效果。 除了以上的几种技术外，还有粗糙集、回归分析、判别分析等技术。 2 5 本章小结 本章简单介绍了数据挖掘的概念、对象、发现模式以及技术，对数据挖掘 技术做了一个简要的概述。 1 0 第三章关联规则数据挖掘 在数据挖掘所发现的知识模式中，关联规则模式是非常重要的一种，也是 最活跃的一个分支。关联规则表示数据库中一组对象之间某种关联关系的规则。 关联规则挖掘可用于发现交易数据库中不同商品( 项) 之间的联系，从而找出顾 客购买商品的行为模式，进而把它应用于商品货架设计、货存安排以及根据购 买模式对用户进行分类等。 关联规则问题由a g r a w a l 等于19 9 3 年首先提出，随即引起了广泛的关 注。许多研究者( 包括r a g r a w a l 本人) 对关联规则采掘问题进行了深入的研究， 对最初的关联规则采掘算法进行了改进和扩展。同时，关联规则的采掘被应用 到许多其它领域的数据库，取得了良好的采掘效果； 3 1关联规则的基本概念 定义l关联规则挖掘的数据集记为d ( 一般为事务数据库) ， d = t 。，t 。，t 。，t 。) ，t k = i 。，i 2 ，i 。，i ， ，t 。( k = l ，2 ，n ) 称为 事务( t r a n s a c t i o n s ) ，i ( m = 1 ，2 ，p ) 称为项目( i t e m ) 。 定义2设i = f i 。，i ：，i 是d 中全体项目组成的集合，工的任何子集 x 称为d 中的项目集( i t e m s e t ) ，l x i = k 称集合x 为k 项目集( k i t e m s e t ) 。设t 。 和x 分别为d 中的事务和项目集，如果x 气，则称事务，。包含项目集x 。每一 个事务都有一个唯一的标识符，称为t i d 。 事务和项目集虽然都是项目的集合，但两者有不同的含义。事务是数据集 d 的组成元素( 类似于关系数据库中的记录或元组) ，而项目仅仅是为采掘关联 规则而规定的项目组合( 类似于关系数据库中的字段) 。事务与项目集的包含关 系表明对该事务来说，此项目集中的各个项目是相互关联的。 定义3数据集d 中包含项目集x 的事务数称为项目集x 的支持数，记为 ，。项目集x 的支持度记作：s u p p o r t ( x ) ，及概率p ( x ) 。 s u p p o r t ( x ) = 斋1 0 0 ( 或s u p p o r t ( x ) = 斋) i u li i 其中i d l 是数据集d 的事务数，若s u p p o r t ( x ) 不小于用户指定的最小支持 度( 记作：m i n s u p p o r t ) ，则称x 为频繁项目集，简称频集( 或大项目集) ，否则称 x 为非频繁项目集，