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

中文摘要 数据挖掘是致力于数据分析和理解，揭示数据内部蕴藏知识的技术，它成为 未来信息技术应用的重要目标之一经过十几年的努力，数据挖掘产生了许多新 的概念和方法特别是最近几年，一些基本概念和方法趋于清晰，它的研究正向 着更深入的方向发展。数据挖掘利用分类、关联性、序列分析、群集分析、机器 自我学习及其它统计方法，从数据库庞大的数据中，找出隐含的、未知的、但却 十分有用的信息。它是一个涉及多学科领域的新兴学科，并伴随着这些学科的发 展而不断发展。数据挖掘系统可以挖掘出多种类型的模式，而其中描述给定数据 集的项之间有趣联系的关联分析模式就是一个非常重要的研究方向。本文主要从 事的是数据挖掘中关联规则的研究。 在整个数据挖掘的研究中，算法的研究占有特别重要的地位。一方面，数据 挖掘面对的是大量数据集，因此算法的效率将对其应用起关键的作用：另一方面， 我们面对的计算机系统在其性能上远远不能满足对大量数据集进行处理的要求。 因此，我们必须研究和改进现有的算法，使其有更广泛的应用前景。鉴于此，本 文着重对关联规则挖掘算法进行了研究。 本文首先对数据挖掘作了一般性讨论，包括数据挖掘的产生、概念、数据挖 掘的方法和存在的主要问题。然后，本文对数据挖掘中重要的关联规则挖掘算法 做了深入的研究，分析了关联规则中经典的a p r i o r i 算法及其他学者对a p r i o r i 算 法的改进算法，其中重点介绍了改进算法f pg r o w t h 算法：接着，详细介绍了我们 提出的改进算法i a p r i o r i ( i m p r o v e da p r i o r i ) 算法的思想，理论基础，以及该算 法与a p r i o r i 算法和f p _ g r o w t h 算法的比较，给出了该算法实现的伪代码，最后举 例对该算法的挖掘步骤进行了详细说明。在用n e t 实现这两个算法的基础上，对 两个算法分别用了两组具有代表性的数据进行测试。对测试结果进行了分析。 关键词：数据挖掘：关联规则；a p r i o r i 算法：f pg r o w t h 算法：i a p r i o r i 算法 分类号：t p 3 1 l a b s t r a c t d a t am i n i n g i sat e c h n i q u et h a ta i m st oa n a l y z ea n du n d e r s t a n dl a r g es o u r c e d a t aa n dr e v e a lk n o w l e d g eh i d d e ni nt h ed a t a i th a sb e e nv i e w e da sa ni m p o r t a n t e v o l u t i o ni ni n f o r m a t i o np r o c e s s i n g d u r i n gt h ep a s td e c a d eo ro v e r , t h ec o n c e p t sa n d t e h n i q u e so hd a t am i n i n gh a v e b e e np r e s e n t e d ，a n de s p e c i a l l yi nt h el a t e s tf e w ) , c a r s s o m eo f t h e mh a v eb e e nd i s c u s s e di nh i g h e rl e v e l s d a t am i n i n gu s e st h ec l a s s i f i c a t i o n , a s s o c i a t i o n , s e q u e n c ea n a l y s i s ，o l u s t c r i n ga n a l y s i s ，m a c h i n es e l f - s t u d ya n do t h e rs t a t i s t i c a p p r o a c h e st of i n dp o t f i a l ，u n a w a r ea n du s e f u li n f o r m a t i o na n dk n o w l e d g ef r o ml a r g e d a t a b a s e i ti san e w s u b j e c tt h a ti n v o l v e sal o to f s u b j e c t sa n dd e v e l o p sw i t l lt h e s e s u b j e c t s d a t am i n i n gs y s t e mc a nf i n dl o t so f p a t t e r n s , i nw h i c ha s s o c i a t i o nr u l e st h a t d e s c r i b et h ei n t e r e s t i n gr e l a t i o n sa m o n gt h ei t e m si ng i v e nd a t as e t sa r et h ei m p o r t a n t a r e a t b i st h e s i si sf o c u so nt h ec o r r e l a t i v es t u d yo f a s s o c i a t i o nr u l ed a t am i n i n g a l g o r i t h mi sk e yp a r ti nd m o nt h eo n eh a n d ，d a t am i n i n gf a c e sl a r g ed a t a b a s e , s ot h ee f f i c i e n c yo f a l g o r i t h mi st h em o s ti m p o r t a n t ；o nt h eo t h e rh a n d ，t h ec o m p 懈i n u s ed o e sn o tm e e tt h ed e m a n do f t h ep r o c e s s i n go f l a r g ed a t a b a s e c o n s e q u e n t l w e s h o l l l dr e s e a r c ha n di m p r o v ep r e s e n ta l g o r i t h m si no r d e rt om a k et h e mb ea p p l i e d e f f e c t i v e l ya n dw i d e l y b a s e do na b o v e , t h i st h e s i sm a i n l y s t u d i e st h ea l g o r i t h mo f d a t a m i n i n g f i r s t l y , t h i st h e s i sg e n e r a l l y d i s c u s s e st h ed a t am i n i n g , m c l u d i n gt h ec o n c e p t sa n d t h ep a t t e r no f t h ed a t am i n i n g , m a i nm i n i n gp r o b l e m s ，s y s t e m i cc l a s s i f i c a t i o n , t h e a p p l i c a t i o na n dd e v e l o p m e n tt r e n do f t h ed a t am i n i n g , s e c o n d l y , t h i st h e s i sd e e p l yr e s e a r c h e st h ea s s o c i a t i o nr u l ea l g o r i t h m , w h i c hi s i m p o r t a n ti nt h ed a t am i m n 辱i ta n a l y s e sa p r i o r ia l g o r i t h m , w h i c hi s c l a s s i ci nt h e a s s o c i a t i o nr u l e sa l g o r i t h m s , a n dt h ei m p r o v e da l g o r i t h m so fa p r i o r i , t h e nw e a n a l y s e sf p _ g r o w t ha l g o r i t h m f o l l o w i n g , d e t a i l so f t h ep r o p o s e da l g o r i t h mi a p r i o r i ( i m p r o v e da p r i o r i ) a l g o r i t h m ，t h e o r e t i c a lb a s i s ，a n dt h ea l g o r i t h ma p r i o r ia l g o r i t h m a n df p g r o w t hc o m p a r i s o n 皿ep s e u d o c o d ei sg i v e na l g o r i t h m , t h ea l g o r i t h mf i n a l e x c a v a t i o nf o rad e t a i l e de x p l a n a t i o ns t e p s i nu s e n e tr e a l i z e do nt h eb a s i so f t h e s et w o a l g o r i t h m s t w oa l g o r i t h m sw e f eu s e df o rt h et w or e p r e s e n t a t i v ed a t af o rt e s t i n g a n a n a l y s i so f t h et e s tr e s u l t s 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 ；a p r i o r i ；f p _ g - r o w t h ；i a p r i o r i c l a s s n o ：1 甲3 1 1 致谢 本论文从选题到写作都是在导师黄厚宽教授的悉心指导下完成的。在两年多 的学习生活和论文的进行工作中，黄老师始终关注着学生的成长，为学生的进步 倾注了大量的心血和汗水，在此，向我的导师致以衷心的感谢和深深地敬意。导 师高深的学术造诣、严谨的治学态度、一丝不苟的工作作风、渊博的知识以及诲 人不倦的导师风范，使我在学习生活中受益非浅，并激励着我在今后的学习工作 中不断进步，这里再次对导师致以最诚挚的谢意。 在论文的写作中，我得到了计算机学院老师及同学的热心帮助和支持，在此， 谨向黄厚宽老师以及所有给予我帮助和鼓励的老师及同学致以诚挚的谢意和由衷 的敬意! 另外也感谢家人，他们的理解和支持使我能够在学校专心完成我的学业。 1 1 问题的提出 1 引言 随着数据库技术的迅速发展以及数据库管理系统的广泛应用，人们积累的数 据越来越多。激增的数据背后隐藏着许多重要的信息，人们希望能够对其进行更 高层次的分析，以便更好地利用这些数据。耳前的数据库系统可以高效地实现数 据的录入、查询、统计等功能，但无法发现数据中存在的联系和规则，无法根据 现有的数据预测未来的发展趋势。缺乏挖掘数据背后隐藏知识的手段，导致了“数 据爆炸但知识贫乏”的现象。正是在这种情况下，数据挖掘( d a t am i n i n g ) 技术应 运而生。 有关调查显示，数据挖掘市场是目前数据库市场中最重要和发展最快的部分 据国外专家预测，在今后的5 1 0 年内，随着数据量的日益积累以及计算机的广泛 应用，数据挖掘将在中国形成一个产业。2 0 0 0 年7 月i d c 发布了关于信息存取工具 市场的报告，其中1 9 9 9 年的数据挖掘的市场大概是7 5 亿美元，估计在下个5 年内 市场的年增长率( c o m p o u n da n n u a lg r o w t hr a t e ) 为3 2 4 ，其中亚太地区为2 6 6 ， 并且预测此市场在2 0 0 3 年时会达至1 j 2 2 亿美元。随着数据挖掘应用领域的发展和成 熟，市场份额将继续加速增长。 在数据挖掘中，关联分析( a s s o c i a t i o na n a l y s i s ) 是其中十分重要的组成部分。 关联分析的主要目标是发现关联规则。自从a g r a w a l 在1 9 9 3 年提出挖掘关联规则的 问题后，关联规则的研究出现了一个热潮。它最早解决的问题是购物篮分析，就 是在超市的交易数据库中发现顾客购买物品间的相关性。但是关联规则算法仍然 存在着一些问题：第一，关联规则的发现算法主要集中在事务数据库的应用上，但 是目前数据库系统中应用最广泛的是关系数据库，它和事务数据库的结构和处理 方法存在着相当大的区别，事务数据库上关联规则算法如何改进以应用到关系数 据库中急待解决。第二，关联规则挖掘算法大部分需要较大的时间开销，不太适 合实际应用。如何提高算法效率，缩短算法的执行时间，从而使该算法从理论应 用到实践中去。本论文就是基于关联规则中如何提高算法效率进行研究的。 1 2 本文的研究背景 本文的主要研究背景如下： 1 计算机技术的飞速进步 自从1 9 4 6 年世界上第一台计算机问世以来，计算机的硬件发展迅速，从最初 的电子管到随后的晶体管，直到目前的大规模集成电路芯片的应用，硬件性能成 级数增长 硬件的发展也同样促进了软件的发展。过去的3 0 年中，计算机稳定的、令人 吃惊的进步导致了功能强大的计算机、数据收集设备和存储介质的大量供应。这 些技术推动了数据库和信息产业的发展，大量数据库信息被用于事务管理、信息 检索和数据分析。因为计算能力的大幅度提升，数据挖掘所需的大量计算和实时 分析成为可能。人们可以利用先进的计算机软件及硬件技术发现数据间感兴趣的 隐含联系。 2 数据库技术的迅速发展 自2 0 世纪6 0 年代以来，数据库技术得到迅速发展，新的数据库系统层出不穷， 从早期的层次数据库到后来的网状数据库，直到目前广泛应用的关系数据库。系 统和数据建模工具、索引和数据组织技术不断进步，数据库存储、统计和分析数 据的能力大大增强。用户通过查询语言、用户界面、优化的查询处理和事务管理， 可以方便、灵活地访问数据。 8 0 年代中期以来，数据库技术的特点是广泛吸收关系技术，研究和开发新的、 功能强大的数据库系统。这些系统使用了先进的数据模型，如扩充关系模型、面 向对象模型和演绎模型等：主动数据库、科学数据库、知识库和办公信息库在内的 面向应用的数据库系统广泛出现。上世纪末发展起来的联机分析处理( o l a p ) 和数 据仓库的应用，使数据的存储和分析更加迅速、便捷。凭借这些技术和设备，人 们存储了海量的数据，这就要求提供更加高效的数据分析处理工具。 3 各类数据挖掘技术的出现和发展 数据挖掘技术主要分为基于统计的方法和基于知识发现的方法。从上世纪6 0 年代以来，基于统计思想的聚类和时间序列技术得到了迅速的发展；随着人工智能 的出现和计算技术的长足进步，自学习的知识发现技术得到了人们的重视，并被 应用到生产实践中，这类技术主要有神经网络、遗传算法、关联规则等。各类数 据挖掘技术的出现和发展，为本文随后的研究提供了坚实的理论基础和丰富的应 用实例。 1 3 论文的结构 本文的组织如下：第二章简单介绍了数据挖掘的产生、基本概念、方法、对象 和数据挖掘存在的主要问题：第三章首先介绍了关联规则的概念，关联规则挖掘的 步骤，重点介绍了关联规则的经典挖掘算法a p r i o r i 算法的思想并给出了一个该算 法挖掘的具体的事例，在总结和分析了a p r i o r i 算法的性能和特点的基础上，给出 了其他学者对a p r i o r i 算法的一些改进算法，并详细介绍了该算法的一个改进算法 2 f pg r o w t h 算法第四章介绍了我们提出的改进算法i a p r i o r i 算法的基本思想和理 论基础，对该算法与a p r i o r i 算法和f p _ 6 r o w t h 算法进行了比较，并给出了该算法 实现的伪代码和一个具体的实例。第五章通过执行自己在n e t 环境下实现的这两 个算法，具体对i a p r i o r i 算法与a p r i o r i 算法进行实验比较：给出了执行结果，并 作了分析。最后，总结全文并提出以后研究的方向。 3 2 数据挖掘 数据挖掘在近年来已经引起了信息产业界的极大关注，这是快速增长的数据 量和日益贫乏的信息量之间矛盾运动的必然结果。在对基于关联规则的数据挖掘 算法进行深入研究之前，我们有必要对数据挖掘的由来、概念，挖掘的对象、常 用的技术等内容有一个较为全面的了解，以期更加透彻地领悟数据挖掘这一极具 发展潜力的新兴领域! 为本文的全面展开作好铺垫。 2 1 数据挖掘技术的产生和概念 2 1 1 数据挖掘的产生 近年来，信息技术以日新月异的速度飞速发展，由此带动了数据库技术的迅 猛发展。各种存储着大量信息的数据库不断出现。数据的丰富带来了对强有力的 数据分析工具的需求，大量的数据被描述成“数据丰富，但信息贫乏”快速增 长的海量数据收集、存放在大型数据库中，没有强有力的工具，理解它们已经远 远超出了人的能力收集在大型数据库中的数据变成了“数据坟墓”一一很难再 访闯的数据档案。人们陷入了一个尴尬的境地，即“丰富的数据”( d a t ar i c h ) 和“贫乏的知识”( k n o w l e d g ep o o r ) 并存。 需要是发明之母。目前的数据库系统无法发现数据中存在的关系和规则，无 法根据现有的数据预测未来的发展趋势。缺乏挖掘数据背后隐藏的知识的手段。 如何有效的利用这些数据从这些随机数据中发掘一些有价值的信息，达到为决策 服务的目的成为一个重要的课题。面对这一挑战，数据挖掘和知识发现技术( d a t a m i n i n ga n dk n o w l e d g ed i s c o v e r yi nd a t a b a s e ) 应运而生，并很快成为一种决策 支持的新手段数据挖掘可以视为数据管理与分析技术的自然进化产物。 数据挖掘的主要任务就是从巨大的数据库中找出用户感兴趣的知识而且这些 知识是隐含的、事先未知的潜在的有用信息。数据挖掘的提出使人们认识到数据 的真正价值，即蕴含在数据中的知识和信息。帮助实现将“数据坟墓”中的数据 转化为知识财富。 数据挖掘是目前国际数据库和信息决策领域的最前沿研究方向之一，已经引 起了学术界和工业界的广泛关注。目前研究的主要目标是发展有关理论、方法和 工具，以支持从大量数据中提取有价值的知识和模式。 我国的数据挖掘技术研究开始于9 0 年代中期，到9 0 年代中后期，初步形成了 知识发现和数据挖掘的基本框架。 4 数据挖掘是属于知识发现( 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 s ；k d d ) 中最重 要的一环，以技术方面来看，它泛指各式各样从大量数据中抽取挖掘出未知的、 有价值的模式或规律等知识的方法，其中包含关联规则、时间序列、人工智能、 统计，数据库等方式“。 数据挖掘按功能分主要有以下几种：1 关联规则；2 分类规则：3 聚类规则：4 异类分析：5 趋势分析：其中挖掘关联规则是数据挖掘领域中一个非常重要的研究 课题。 关联规则( a s s o c i a t i o nr u l e ) 的概念最早是由i b m ai m a d e nr e s e a r c hc e n t e r 的a g r a w a l 首先提出的。关联规则就是从大量的数据中挖掘出有价值的描述数据项 之间相互联系的有关知识。“1 关联规则的一个典型例子是购物篮分析，例如“在购 买面包和黄油的顾客中有9 0 的顾客也购买了牛奶”，这样的规则指导超市的管理 人员把这三种商品摆放的近一点，方便顾客购买，从而促进销售提高效益。找出 这样的数据信息很有价值。寻找这种信息的过程就是挖掘关联规则的过程。 2 1 2 数据挖掘概念 1 9 9 5 年在美国计算机年会( a c m ) 上，提出了数据挖掘( d m ，d a t am i n i n g ) 的概 念。数据挖掘，英文是d a t am i n i n g ，中文又译作数据采掘。数据挖掘，就是从大 型数据库的数据中提取有效的、新颖的、潜在有用的、最终可被理解的模式的非 平凡过程。下面是对这个定义做出的详细解释。 数据：指一个有关事实f 的集合，用以描述事物的基本信息。如学生档案数据 库中有关学生基本情况的记录。一般来说这些数据都是准确无误的。数据是数据 挖掘的对象，不仅只是数据库，也可以是文件系统，或其它以任何方式组织在一 起的数据集合，例如w w w 信息资源，数据仓库等等。 模式：对于集合f 中的数据，我们可以用l 来描述其中的数据的特征。语言l 中 的表达式e ，e 所描述的数据是集合f 的一个子集f e ，f e 表明数据集f 中的数据具有特 性e 。作为一个模式，e 比枚举数据子集简单。如“如果分数在8 1 至u 9 0 之间，则成 绩优良”可称为一个模式。 非平凡过程：所谓非平凡过程是指具有一定程度的智能性和自动性，而绝不 仅仅是简单的数值统计和计算。 有效性( 可信性) ：从数据中发现的模式必须有一定的可信度，否则数据挖掘 就没有意义了。可以通过新增数据来检验模式的正确性，以c 来表示模式e 的可信 度c = c ( e ，f ) ，其中e e l ，e 所描述的数据集合f 。属于f 。 新颖性：提取出的模式必须是新颖的。模式是否新颖可以通过两个途径来衡 量：一是通过比较当前得到的数据和以前的数据或期望得到的数据来判断：二是通 5 过对比发现的模式与已有模式的关系来判断。通常用一个函数n ( e ，f ) 来表示模式 的新颖程度，该函数的返回值是逻辑值或是对模式e 的新颖程度的一个判断数值 潜在作用：指提取出的模式将来会被实际运用，可以通过函数u 的值来衡量， 函数u 把l 中的表达式映射到度量空问，u 表示模式e 的有作用程度，u = u ( e 。f ) 。 可理解性：数据挖掘的一个目标就是将数据中隐含的模式以可被人理解的形 式表现出来，从而帮助人们更好地了解和使用数据中所包含的信息，这主要体现 在简洁性上。要想让一个模式更容易地被人们理解并不是一件很容易的事，需要 对其简单程度进行度量。用s 表示模式e 的简单度( 可理解度) ，s - s ( e ，f ) 。 数据挖掘发现知识是隐含的、事先未知的、潜在的有用的信息。提取的知识 表示为概念、规则、规律等形式。这些规则蕴涵了数据库中一组对象之间的特定 关系，揭示出一些有用的信息，为经营决策、市场策划、金融预测等提供了依据。 通过数据挖掘，有价值的知识、规则或高层的信息就能从大型数据库的相关数据 集合中抽取出来，并从不同的角度显示，从而使大型数据库作为一个丰富而可靠 的资源为知识归纳服务。因此，数据挖掘被认为是目前解决“数据爆炸”和“数 据丰富”、“信息贫乏”的一种有效方法。 数据挖掘是一门交叉学科，融合了数据库、人工智能、机器学习、统计学等 多个领域的理论和技术。数据库、人工智能和数理统计是数据挖掘研究的三根强 大的技术支柱。数据挖掘的方法和数学工具包括统计学、决策树、神经网络、模 糊逻辑、线性规划等。 我国的数据挖掘技术研究开始于9 0 年代中期，到9 0 年代中后期，初步形成 了知识发现和数据挖掘的基本框架 2 2 数据挖掘的对象 原则上讲数据挖掘可以在任何类型的信息存储上进行这包括关系数据库、 数据仓库、事务数据库、高级数据库系统、展开文件和w 唧 1 关系数据库 关系数据库是表的集合，每个表都赋予一个唯一的名字。每个表包含一组属 性( 列或字段) ，并通常存放大量元组( 记录或行) 。关系中的每个元组代表一个被 唯一的关键字标识的对象，并被一组属性值描述。语义数据模型，如实体一联系 ( e r ) 数据模型，将数据库作为一组实体和它们之间的联系进行建模。 当数据挖掘用于关系数据库时，可以进一步搜索趋势或数据模式。例如，数 据挖掘系统可以分析顾客数据，根据顾客的收入、年龄和以前的信用信息预测新 顾客的信用风险。数据挖掘系统也可以检测偏差，如与以前的年份相比，哪种商 6 品的销售出人预料。这种偏差可以进一步考察( 例如，包装是否有变化，或价格是 否大幅度提高) 。 关系数据库是数据挖掘最流行的、最丰富的数据资源，因此它是我们数据挖 掘研究的主要数据形式 2 数据仓库 数据仓库是一种全新的数据存储模式。按照w h i n m o n 数据仓库系统构造方面 的设计师的说法，“数据仓库是一个面向主题、集成的、时变的、非易失的数据 集合，支持管理部门的决策过程”与其它数据存储系统( 如关系数据库系统、事 务处理系统和文件系统) 相比，数据仓库具有四个明显的特征： 概言之，数据仓库是一种语义上一致的数据存储，它充当决策支持数据模型 的物理实现，并存放企业战略决策所需的信息。数据仓库也常常被看作一种体系 结构，通过将异种数据源中的数据集成在一起而构造，支持结构化的和专门的查 询、分析报告和决策制定。 有三种数据仓库应用：信息处理、分析处理和数据挖掘。 信息处理：支持查询和基本的统计分析，并使用交叉表、表、图表或图进行 报告。数据仓库信息处理的当前趋势是构造低成本的基于w e b 的存取工具，然后与 w e b 浏览器集成在一起。 分析处理：支持基本的o l a p 操作，包括切片与切块、下钻、上卷和转轴。一 般地，它在汇总的和细节的历史数据上操作。与信息处理相比，联机分析处理的 主要优势是它支持数据仓库的多维数据分析 数据挖掘：支持知识发现，包括找出隐藏的模式和关联，构造分析模型，进 行分类和预测，并用可视化工具提供挖掘结果。 在数据仓库的三种应用中，信息处理可以反映直接存放在数据库中的信息， 但不反映复杂的模式或隐藏在数据库中的规律；联机分析处理可以由用户选定的 数据仓库子集，在多粒度上导出汇总的信息，它帮助简化数据分析：而数据挖掘更 进一步，它的目标是尽可能自动发现隐藏在大量数据中的隐含模式和有趣知识。 3 事务数据库 事务数据库是由一个文件组成，其中每个记录代表一个事务通常，一个事 务包括一个唯一的事务标识号( t r a n s a c t i o ni d ，简称t i d ) ，和一个组成事务的项 的列表( 如，在商店购买的商品) 。事务可以存放在表中，每一条记录代表一个事 务。 4 高级数据库系统和高级数据库应用 高级数据库系统和面向特殊应用的数据库系统，为数据挖掘提供了肥沃的土 壤。包括以下一些： 7 面向对象的数据库：采用基于面向对象的程序设计范例。每个实体被看作一 个对象。涉及一个对象的数据和代码封装在一个单元中。 对象一关系数据库：基于对象一关系数据模型构造该模型通过提供处理复 杂对象的丰富数据类型和对象定位，扩充关系模型。此外，还包括关系查询语言 的特殊构造，以便管理增加的数据类型。 空间数据库：包含涉及空间的信息这种数据库包括地理( 地图) 数据库、 v l s i ( v e r yl a r g es c a l ei n t e g r a t i o n 。超大规模集成电路) 芯片设计数据库、医疗 和卫星图像数据库。空间数据可能以光栅( r a s t e rf o r m a t ) 格式提供，由n 维位图 或象素图构成。 时间和时间序列数据库：时问数据库通常存放包含时问相关属性的数据。时 间序列数据库存放随时间变化的值序列，如收集的股票交易数据。 文本数据库：包含对象文字描述的数据库通常，这种词描述不是简单的关 键词，而是长句子或短文，如产品介绍、错误或故障报告、警告信息、汇总报告、 笔记或其他文档。文本数据库可能是高度非结构化的( 如w w w 上的网页) ，可能是半 结构化的( 如e - m a i l 消息和一些盯m l 】( m l 网页) ，也可能是良结构化的( 如图书馆数 据库) 多媒体数据库：存放图像、音频和视频数据。它们用于基于图像内容的检索、 声音传递、视频点拨、w l g w 和识别口语命令的基于语音的用户界面等方面。 异种数据库：由一组互连的、自治的成员数据库组成。这些成员相互通信， 以便交换信息和回答查询。一个成员数据库中的对象可能与其它成员数据库中的 对象很不相同，使得很难将它们的语义吸收进一个整体的异种数据库中。 遗产数据库：是一组异种数据库，它将不同的数据系统组合在一起。 基于w 啊全球信息系统：w w w 与之关联的分布式信息服务提供了丰富的、世界 范围的联机信息服务：这里，数据对象被链接在一起，便于交互访问。 2 3 数据挖掘的方法 数据挖掘常用的技术有神经网络、遗传算法、决策树、关联规则等。 1 神经网络方法 模拟人的神经元功能，经过输入层、隐藏层、输出层等，对数据进行调整、 计算，最后得到结果，用于分类和回归。神经网络由于本身良好的自组织自适应 性、并行处理、分布存储和高度容错等特性非常适合解决数据挖掘的问题。 2 遗传算法 遗传算法是一种基于生物自然选择与遗传机理的随机搜索算法，是一种仿生 全局优化方法。遗传算法具有的隐含并行性、易于和其它模型结合等性质使得它 8 在数据挖掘中被加以应用。 3 决策树方法 决策树是一种常用于预测模型的算法，它通过将大量数据有目的分类，从中 找到一些有价值的潜在的信息它的主要优点是描述简单，分类速度快，特别适 合大规模的数据处理。常用的算法有c a r t 、c h a i d 、i d 3 、c 4 5 、c 5 o 等。其中最 有影响和最早的决策树方法是由q u i n l a n 提出的著名的基于信息的i d 3 算法。 4 关联规则挖掘算法 关联规则是描述数据之间存在关系的规则，形式为“a 。 a 2 a a a 。- b 。 b 2 a a b , ”般分为两个步骤：1 求出频繁数据项集。2 用频繁数据项集产生关联规 则。 5 统计分析方法 传统的统计方法有：1 抽样技术。面对大量的数据，对所有数据进行分析是不 可能也没有必要的，要在理论指导下进行合理的抽样：2 多元统计分析如因子分 析、聚类分析等：3 统计预测方法。如回归分析、时闻序列分析等。 6 粗糙集方法 粗糙集理论是一种研究不精确、不确定知识的数学工具。粗糙集方法有几个 优点：不需要给出额外信息：简化输入信息的表达空间：算法简单，易于操作。粗糙 集处理的对象是类似二维关系表的信息表。目前成熟的关系数据库管理系统和新 发展起来的数据仓库管理系统，为粗糙集的数据挖掘奠定了坚实的基础。但粗糙 集的数学基础是集合论，难以直接处理连续的属性。而现实信息表中连续属性是 普遍存在的。因此连续属性的离散化是制约粗糙集理论实用化的难点。 7 覆盖正例排斥反例方法 它是利用覆盖所有正例、排斥所有反例的思想来寻找规则。首先在正例集合 中任选一个种子，到反例集合中逐个比较。与字段取值构成的选择不相容则舍去， 相反则保留。按此思想循环所有正例种子，将得到正例的规则( 选择子的合取式) 。 2 4 数据挖掘的主要问题 数据挖掘的研究方兴未艾，其主要问题涉及数据挖掘技术、用户交互、性能 和可扩展性，以及各种不同数据类型的处理。现对这些问题介绍如下： 1 挖掘方法和用户交互问题 在数据库中挖掘不同类型的知识：由于不同的用户可能对不同类型的知识感 兴趣，数据挖掘系统应当覆盖范围很广的数据分析和知识发现任务，包括数据特 征化、区分、关联、分类、聚类、趋势和偏差分析以及类似性分析。这些任务可 能以不同的方式使用相同的数据库，并需要开发大量数据挖掘技术。 9 多个抽象层的交互知识挖掘：由于很难准确地知道能够在数据库中发现什 么，数据挖掘过程应当是交互的对于包含大量数据的数据库，应当使用适当的 抽样技术，进行交互式数据探查。交互式挖掘允许用户聚焦搜索模式，根据返回 的结果提出和精炼数据挖掘请求。特殊地，类似于o l a p 在数据立方体上做的那样， 应当通过交互地在数据空间和知识空间下钻、上卷和转轴来挖掘知识。用这种方 法，用户可以与数据挖掘系统交互，以不同的粒度和从不同的角度观察数据和发 现模式 结合背景知识：可以使用背景知识或关于所研究领域的信息来指导发现过 程，并使得发现的模式以简洁的形式在不同的抽象层表示。关于数据库的领域知 识，如完整性约束和演绎规则，可以帮助聚焦和加快数据挖掘过程，或评估发现 的模式的兴趣度。 数据挖掘查询语言和特定的数据挖掘：关系( 数据库) 查询语言( 如s q l ) 允许 用户提出特定的数据检索查询类似地，需要开发高级数据挖掘查询语言，帮助 用户描述特定的挖掘任务( 包括描述其中的数据特征) 、描述任务所涉及的领域知 识、挖掘结果的模式知识类型，以及对挖掘结果有趣性等约束条件。这种语言应 当与数据库或数据仓库查询语言集成，并且对于有效的、灵活的数据挖掘是优化 的。 数据挖掘结果的表示和显示：发现的知识应当用高级语言、可视化表示或其 他表示形式表示，使得知识易于理解，能够直接被人们使用。如果数据挖掘系统 是交互的，这一点尤为重要。这要求系统采用有表达能力的知识表示技术，如树、 表、规则、图、图表、交叉表、矩阵或曲线。 处理噪声和不完全数据：存放在数据库中的数据可能反映噪声、异常情况或 不完全的数据对象。这些对象可能搞乱分析过程，导致数据与所构造的知识模型 过分适应。其结果是，所发现的模式的精确性可能很差。这时就需要处理数据噪 声的数据清理方法和数据分析方法：有时也需要发现和分析异常情况的孤立点挖 掘方法。 模式评估一兴趣度问题：数据挖掘系统可能发现数以千计的模式。对于给定 的用户，许多模式不是有趣的，它们表示公共知识或缺乏新颖性。关于开发模式 兴趣度的评估技术，特别是关于给定用户类，基于用户的信赖或期望，评估模式 价值的主观度量，仍然存在一些挑战。使用兴趣度度量，指导发现过程和压缩搜 索空间，是又一个活跃的研究领域。 2 性能问题 数据挖掘算法的有效性和可伸缩性：为了有效地从数据库的大量数据中提取 信息，数据挖掘算法必须是有效的和可伸缩的。换句话说，对于大型数据库，数 l o 据挖掘算法的运行时间必须是可预计的和可接受的从数据库角度，有效性和可 伸缩性是数据挖掘系统实现的关键问题。上面讨论的挖掘方法和用户交互问题的 大多数问题，也必须考虑有效性和可伸缩性 并行、分布式和增量挖掘算法：许多数据库的大容量、数据的广泛分布和一 些数据挖掘算法的计算复杂性是促使开发并行和分布式数据挖掘算法的因素。这 些算法将数据划分成各部分，这些部分可以并行处理。然后合并每部分的结果。 此外，有些数据挖掘过程的高花费导致了对增量数据挖掘算法的需要。增量算法 与数据库更新结合在一起，而不必重新挖掘全部数据这种算法渐增地进行知识 更新，修正和加强先前业己发现的知识。 3 关于数据库类型的多样性问题 关系的和复杂的数据类型的处理：由于关系数据库和数据仓库己经广泛使 用，对它们开发有效的数据挖掘系统是重要的然而，其他数据库可能包括复杂 的数据对象、超文本和多媒体数据、空间数据、时间数据或事务数据。由于数据 类型的多样性和数据挖掘的目标不同，指望一个系统挖掘所有类型的数据是不现 实的。为挖掘特定类型的数据，应当构造特定的数据挖掘系统。这样，对于不同 类型的数据，我们可能有不同的数据挖掘系统 由异种数据库和全球信息系统挖掘信息：局域网和广域网( 如i n t e r n e t ) 连结了 许多数据源，形成了庞大的、分布式的和异种的数据库。从具有不同数据语义的 结构化的、半结构化的和非结构化的不同数据源发现知识，对数据挖掘提出了巨 大挑战。数据挖掘可以帮助发现多个异种数据库中的数据规律，这些规律多半难 以被简单的查询系统发现，并可以改进异种数据库的信息交换和互操作性。w e b 挖掘发现关于w c b 内容、w e b 使用和w e b 动态情况的有趣知识，已经成为数据挖掘 的一个非常具有挑战性的领域。 3 关联规则挖掘算法综述 关联规则挖掘是数据挖掘领域中一个非常重要的研究课题，它是由h g r a w a l 等 人首先提出的，是k d d 数据研究的重要内容。最初提出的动机是针对购物篮分析问 题提出的，其目的是为了发现事务数据库中不同商品之间的联系规则。这些规则 刻画了顾客购买行为模式，可以用来指导商家科学地安排进货、库存以及货架设 计等。之后诸多的研究人员对关联规则的挖掘问题进行了大量的研究。他们的工 作涉及到关联规则挖掘理论的探索、原有算法的改进和新算法的设计、并行关联 规则挖掘( p a r a l l e la s s o c i a t i o nr u l em i n i n g ) 以及数量关联规则挖掘( q u a n t i t a t i r ea s s o c i a t i o nr u l em i n i n g ) 等闯题。在提高挖掘规则算法的效率、适应性、 可用性以及应用推广方面，许多学者进行了不懈的努力。 本章主要阐述了数据挖掘中关联规则挖掘的基本概念，概述了关联规则的分 类，挖掘关联规则的步骤及经典关联规则挖掘算法a p r i o r i 算法，给出了该算法实 现的伪代码，并给出一个具体的例子演示了该算法的挖掘过程。最后给出一些学 者对经典算法a p r i o r i 的一些改进，其中重点介绍了f pg r o w t h 算法。 3 1 关联规则挖掘的基本概念 3 1 1 购物篮分析：一个引发关联规则挖掘的例子 作为一个零售商，如果你想了解顾客的购买习惯，想知道什么商品组或集合 顾客多半会在一次购物时同时购买，那么在你的商店顾客事务零售数据上运行购 物篮分析，就可以得到你想要的答案。 通过分析得到的结果可以用于市场规划、广告策划和分类设计等。例如，购 物篮分析可以帮助经理设计不同的展场一种策略是：经常一块购买的商品可以放 近一些，以便进一步刺激这些商品一起销售。例如：一个超市中顾客购买面包的同 时一般要购买牛奶或者饮料，那么把销售牛奶或者饮料的展台放在销售面包的展 台附近，就可以促进增加二者的销售。另一种策略是：将面包和牛奶分别放在展场 的两端，在两者之间放上销售情况一般或者是销量不好的商品，那么顾客在决定 购买面包以后，从一端的面包展场走向另一端牛奶展场的路上，他可能看到果酱， 就会产生购买果酱的愿望。 购物篮分析也可以帮助商家进行贱卖分析。例如，如果一些顾客趋向于在购 买面包的同时购买黄油，那么黄油的降价就可能既促进黄油的销售情况，又促进 面包的销售情况。 1 2 关联规则可以以蕴涵式来表示上述购物篮分析的具体情况例如，购买面包 也趋向于同时购买牛奶可以用以下关联规则表示： 规则的支持度和置信度是两个规则兴趣度度量。支持度反映发现规则的有用 性，上述规则中的支持度是5 意味着分析中的全部事务的5 同时购买面包和牛奶。 置信度反映发现规则的确定性，规则中的置信度7 5 意味着购买面包的顾客7 5 也 购买牛奶。如果上述规则中的支持度和置信度满足最小支持度和最小置信度阀值， 则认为该关联规则是有趣的。最小支持度和置信度阀值可以由用户或专家设定。 3 1 2 关联规则基本概念 关联规则可形式化定义为： 设i = i 。，i ：，i 。 是由m 个不同的项组成的集合。给定一个事务数据库d ， 其中每一个事务t 是i 中一组项的集合，即t i ，t 有一个唯一的标示符t i d 。若项 集x gi j r x t ，则事务t 包含项集x 。 关联规则是形如x - y 的蕴涵式，其中x c t ，y t ，并且x n y = m ，如果d 中事务 包含x u y 的百分比为s ，则称s 为关联规则x = y 的支持度，它是概率p ( x uy ) ：如果 d 中包含x 的事务同时也包含y 的百分比为c ，则称c 为关联规则x - y 的置信度，它是 条件概率p ( y x ) 。习惯上将关联规则表示为x _ y ( s ，c ) 。 关联规则的发现任务或问题就是在事务数据库d 中找出所具有用户给定的最 小支持度阀值( m i n _ s u p ) 和最小置信度阀值( m i n _ c o f ) 的关联规则，即这些关联规 则的支持度和置信度分别不小于最小支持度和最小置信度，这样，每条被挖掘出 来的关联规则就可以用一个蕴涵式( j 矽j ) 和两个阀值( 最小支持度m i n _ s u p 和最小 置信度m i n _ c o f 表示) 。 3 2 关联规则分类 根据不同的标准，关联规则有多种分类方法： ( 1 ) 根据规则中所处理的值类型可以分为布尔关联规则和量化关联规则。布尔 关联规则( b o o l e a na s s o c i a t i o nr u l e ) 处理的值都是离散的、种类化的，它所考 虑的是项的在与不在。例如，下面的规则是布尔关联规则： 霞圣匮= 牛奶i s u p p o r t = 蹶c o n f j d e n c e = 7 5 量化关联规则( 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 ) 也是多值关联规则，所描述 的是量化的项或属性之间的关联。例如，下面的规则是量化关联规则： 年龄。3 0 3 9 ) a 投入t 2 万4 2 ) - 4 ) = 购买面包 ( 2 ) 根据规则中涉及的数据维可以分为单维关联规则和多维