（计算机软件与理论专业论文）关联规则的增量更新挖掘算法.pdf

摘要 y 4 16 7 45 随着计算机技术特别是数据库技术的发展，出现r 许多大规模的数据 库两目前还缺乏对其中的数据进行深八分析，找出隐含的规律或知识的有 教l ：具。为了解决这一问题，人们提出了知识发现f k n o w l e d g ed i s c o v e r y i n d a t a b a s e ) 和数据挖掘f d a t am i n i n g ) 概念。本文主要针对数据挖掘中的一个 重要方面：关联规则( a s s o c i a t i o nr u l es ) 挖掘进行探索与讨论。 关联规则是在数据库中的一些相关的数据集台中提取出系列联系，它 的表示形式：“a 】 a 。b l a b 。”，其中a ，( i e l ，m ) ) 和b j ( j 1 ，n j ) 是 数据库的璃性值集合。 目前，基于关联舰则的挖掘模式是单一豹，具有缺乏用户参与、无蘑点 和僵硬的芙系等缺点。具有用户反馈的2 阶段结构的挖掘模式，使用户和系 统能良好的进行交流，保证系统的挖掘结果能更佳地满足用，】的需要。 基于新的挖掘模式，本文提出新增量更新算法f n e w1 u a ) 。n e wt u a 算 法利用最大频繁集删除算法，建立高教的集合列举树( s e t e n u m e r a t i o n t r e e j ， 在算法中应用多种优化手段，保证了算法效率的提高。通过实验，对基本的 集合列举树算法m a x m i n e r 、n e wi u a 的性能进行评估。 最后，本文指出了关联规则挖掘所面临的问题和挑战。 关键诃r 知识发现、数据挖掘、关跃规则、反馈、挖掘模式 最大频繁集删除、集合列举树、新增量更新算法 i c a b s t r a c t c u r r e n tc o m p u t i n ga n ds t o r a g et e c h n o l o g yi s r a p i d l yo u t s t r i p p i n gs o c i e t y s a b i l i t yt 0m a k em e a n i n g f u lu s ef o rt h et o r r e n to f a v a i l a b l ed a t a t h i sp a p e rd i s c u s s e s t h ee s s e n t i a lc o n c e p t s ，t h ed e v e l o p i n gh i s t o r y , t h et a s ko fk n o w l e d g ed i s c o v e r yi n d a t a b a s e ( k d d ) a n d d a t a m i n i n g ，a sw e l la st h er e l a t e df i e l d s ，a n de x p l o r e sm o d e l o f t h ee f f i c i e n t l ym i n i n gt h ea s s o c i a t i o nr u l e sa si m p o r t a n tf i e l do f t h ed a t a m i n i n g m i n i n ga s s o c i a t i o nr u l e si st od e r i v eas e to fs t r o n ga s s o c i a t i o nr u l e si nt h e f o r mo f “a i a a m 辛b 1 a b 。”，w h e r ea 文f o ri 1 ，m ) a n db j ( f o rj 1 ，n ) 8 r es e t so f a t t r i b u t e - v a l u e s ，f r o mt h er e l e v a n td a t as e t si na 出i l a b a s e r e c e n t l y , t h em o d e lo f m i n i n ga s s o c i a t i o n r u l e si sl a c ko fu s e re x p l o r a t i o na n d c o n t r o l ，l a c ko ff o c u sa n dr i g i dn o t i o no fr e l a t i o n s h i p t h e2 - p h 嬲ea r c h i t e c t u r ew i m i n s e r t i n gt h eb r e a k p o i n t sf o rf e e d b a c k t h i sa r e h i l e c t u r ep r o v i d e sar i c hi n t e r f a c ef o r t h eu s e rt oe x p r e s sf o c u sa n de n s u r et h es y s t e md o e sa na m o u n to fc o m p u t a t i o n p r o p o r t i o n a l t ow h a tt h eu s e r g e t s t h e p a p e rp r o p o s e dt h ea l g o r i t h mn e wi l i aa c c o r d i n g t ot h e2 - p h a s e a r c h i t e c t u r e a p p l y i n gt h em a x i m u mf r e q u e n ts e tp r u n i n ga n da n yo p t i m i z i n g ，t h e n e wi u aa l g o r i t h mc r e a t e st h es e t - e n u m e r a t i o nt r e et o e f f i c i e n t l yi m p r o v e t h e e x p l o r a t o r ym i n i n g t h r o u g h t h ee x p e r i m e n t s ，t h ep a p e re v a l u a t e st h ep e r f o r m a n c eo f t h en e w1 u aa n db a s i cs e t - e n u m e r a t i o na l g o r i t h m ( i v l a x - m i n e r ) i nt h el a s to ft h i sp a p e r , t h ep a p e rd i s c u s s e st h ep r o b l e mf a c e di nt h em i n i n g a s s o c i a t i o nr u l e sf i e l d k e y w o r d s ： k n o w l e d g ed i s c o v e r y , d a t am i n i n g , a s s o c i a t i o n r u l e sy e e d h a c k , m i n i n gm o d e l m a x i m u m f r e q u e n t s e tp r u m n g ，s e t - e n u m e r a t i o nt r e e ，n e w u a i i i 背景 第一章绪论 随着大量的数据收集工具的先进性，数据生成和收集能力的迅速增强， 广泛应用的大量含有原始数据的商业产品、商务和政府事务的计算，使我们 获得了大量的数据。目前，在商务管理、政府管理、工程数据管理以及许多 其他的应用领域已经使用了成千上万个数据库，伴随着数据库系统的性能的 提高，各类数据库也正蓬勃发展起来。这种爆炸性的数据和数据库系统的发 展迫切要求一种新型的技术和工具能自动地对数据进行分析，转化为一种有 用的知识和信息f ，1 2 】。 数据挖掘是数据库中的知识发现即通过对数据库中数据的分析、处 理来获得重要的、先前未知的和潜在有用的信息【1 2 】。通过数据库中的知识 发现抽象出有意义的知识，并对数据库从不同的角度进行验证，因此一个 大的数据库不仅是一个丰富、可靠的资源而且是一个知识生成和验证的源 泉。发现的知识能技应用到信息管理、问题处理、决策、过程控制及其他领 域。 在数据库系统中，知识的发现已被研究者作为一个关键的研究课魇。 许多领域的研究者对数据挖掘都保持着浓厚的兴趣，如数据库系统、知识系 统、人工智能、机器学习、知识获取、统计、数据抽象，而且在信息服务提 供者的一些应用中如在线服务、w w w 也要求通过数据挖掘技术去分析用户 的行为，优化服务质量增加商机 数据挖掘是一个依赖于应用的技术，髓着应用的改变，要求采用不同 的技术来协作完成其中关联规则的挖掘已经吸引许多数据库研究小组的关 注。它的任务是挖掘在事务和关系数据库中一系列的联系，它的表示形式： “a l k 辛b l a b n ，其中a i e 1 ，m ) ) 和球j l ，n ) ) 是数据库的属性 值集合。例如在超市的销售记录中人们希望发现是否存在这样的联系：顾 客在购买了牛奶的同时往往购买面包。由于关联规则的获取需要对一个大型 事务数据库的重复扫描整个挖掘的计算过程是巨大的因此性能的提高是 一个必需关注的方面。同时将数据挖掘技术融入到数据库的管理系统( d b m s ) 中去也是一个相当重要的方面。 1 i 2 发展现状 熹鞋规州的港量蔓莆柁掘算击革l 膏共张页 目前，各地的研究小组针对关联规则挖掘的不同方面纷纷提出了自已 的算法，其中以a p t i o r i 的快速算法最为著名，许多算法如r a k e s ha g r a w a l 舶挖掘次序模型， s r jk a n t 的挖掘普遍的关联规则等算法都是h p r i o r i 算 法的变形， 许多算法主要是针对最大频繁集的挖掘同时对于规则的提取也有许 多文章，还有些是针对特定算法中的某些实现细节的优化。 1 2 本文内容和安捧 1 2 1 本文的主要内容 本文首先对关联规则的数据挖掘技术及目前状况作了一个整体上的讨 论，分析了数据挖掘的技术分类、关联规则挖掘所使用的各种技术方法及主 要内容。接着，本文对数据挖掘的一个重要方面关联规则的挖掘模式进行了 分析，介绍了新型的2 一阶段的挖掘模式。并根据2 一阶段的挖掘模式，基于 m a x - m i n e r 的集合列举树算法，作者提出了增量更新算法n i u a ( n e wi n c r e m e n t u p d a t i n ga 1 9 0 r i t h m ) 。 n i l j h 是以集合列举树为分析基础的算法，充分利用“子集不频繁删除 原则”、“超集频繁删除原则”并将自底向上与自顶向下有机结台起来。在 具体的实现过程中提供了许多优化手段。 最后，本文介绍了根据此算法实现的m m - - n i u a 挖搁系统和具体细节。 1 2 2 章节安排 本文的第二章介绍了数据挖掘技术及其发展 第三章概括介绍了关联规则数据挖掘技术。 第四章分析了以往关联规则的挖掘模式及特点，具有用户反馈功能的2 一 阶段挖掘模式。 第五章介绍 4 a x - m i n e r 集合列举树的一些概念、一些基本的删除原理 及基本算法。 关联托肘的增量王f 撼掘善瑶年2 百* 0 膏 第六章提出了n 儿j a 算法，详尽阐述了n i u a 的基本思想，及具体的实 现过程、伪化码，并针对不同的情况进行优化。 第七章根据n i u a 原理，实现了m m - - n i u a 挖掘系统并说明了具体 的实现细节以及挖掘的结果。 第八章对关联规则挖掘所遇到的问题和不足进行讨论，提出了以后的 发展方向。 * 础t o u 时增量要新i 哺算法年，百鼻枷膏 c ( 第二章数据挖掘技术及其发展 2 1 数据挖捆技术及其概念 无论是商业企业、科研机构或者政府部门，在过去若干年的时问里都 积累了海量的、蛆不同形式存储的数据资料，由于这些资料十分繁杂要从 中发现有价值的信息或知识，达到为决策服务的目的成为非常艰巨的任务。 数据挖掘概念的提出，解决了人们的疑惑。数据挖掘，也称作为数据库中的 知识发现是从大型数据库或数据仓库中提取人们感兴趣的知识，这些知识 是隐含的、事先未知的潜在有用信息，提取的知识表示为概念、规则、规律、 模式等形式。另外，数据挖掘还有一些意义相差不大的术语，例如，数据库 中的知识发现、知识抽取、数据挖掘等。数据挖掘是目前国际上数据库和信 息决策领域舶最前沿研究方向之一引起了学术界和工业界的广泛关注。一 些国际上高级别的工业研究实验室，如i b ma l m a d e n 和g t e ，都在这个领域 开展了各种各样的研究计划研究的主要目标是发展有关的方法论、理论和 工龄以支持从大重数据中提取有用的和让人癌兴趣的知识和模式。 对于数据挖掘我们有必要先了解它的要求， 作用的数据种类比如关系数据、结构化的数据、复杂的数据对 象，超文本和多媒体数据、空间和时间数据、事务数据等等。一个强有 力的数据挖掘系统应该有效地处理这些复杂的数据类型，然而，数据种 类的繁多，以及数据挖掘的不同目标，使得我们要求一个系统能够处理 所有种类的数据又是不现实的。 数据挖掘算法的有效性和可扩展性，也就是说算法的运行时间 对于大规模数据库，必须是可预知和可接受的。 数据挖掘结果的有用性和确定性，挖掘出来的知识应该准确地反 跌数据库的内容，并且对于用户来说，不确定的程度应反映在近似规则 和定量规则上，系统应能处理噪音数据。 知识的表达，这要求我们用高层次的语言或者圈形用户界面来表 达数据挖掘的需求和发现的知识。 多层次交互挖掘知识，既然我们事先并不知道从数据库中可眺发 现什么样的知识，交互发现就成了一种有效的手段，它允许用户交互耩 萎规刑的譬量置* 把掘算法苇筲共拈百 确化数据挖掘的耍求，动态改变数据焦点，逐步加深数据挖掘过程，从 不同的角度和层次审视数据挖掘的结果。 并行的和分布的数据挖掘算法，数据库的巨大规模、数据的广泛 分布、以及有些数据挖掘算法的计算复杂度等促进了并行和分布数据挖 掘算法的发展。 私有保护和数据安全，知识发现可能导致对于私有权的入侵，研 究应该采取哪些措施防止暴露敏感信息是很重要的。 数据挖掘的要求大体上可概括成上面七点，一个有效的数据挖掘算 法或系统都应该满足上面这些要求。 2 2 数据挖掘的过程 数据挖掘可以分为狭义的数据挖掘和广义的数据挖掘。狭义的数据挖 掘只是对指定的数据实施数据挖掘的算法。从而得到规则的具体动作而广 义的数据挖掘还包括收集数据、整理数据、分析数据和知识评价等其他步骤。 数据挖掘不是单一的一种技术或方法而是一个完整的过程- 该过程 可以详细描述为： 1 ) 熟悉有用领域的数据、背景知识，明确所要完成的数据挖掘任务性 质，例如是要验证系统的假设还是要发现新的数据模式。 。2 ) 确定与发现任务相关的数据集合。 3 ) 从与发现任务相关的数据集台中出去明显错误的数据和冗余的数 据。 4 ) 数据预处理，即创建知识发现算法所需要的数据组织形式，如概念 层次。如果发现任务属于验证则还需提出相应的假设。 5 ) 针对所要发现任务的所属类别，例如归类、回归分析、简约、聚类、 发现关联规则等等，设计或选择有效的数据挖掘算法并加以实现。 6 ) 测试和评价所发现的知识。例如对知识一致性、新颖性和效用性的 处理。 * 联规劓坩量置拜挖掘鼻洼簪5 膏共4 b 百 7 ) 解释和运用指的是对所发现的知识进行解释以及在实际系统中的应 用。 以上各个步骤不是简单的线形流程，步骤之间包含了循环和反复。这 样可以对所发现的知识不断求精、深化并使其易于理解。 2 3 数据挖掘技术的分类 从不同的视角看，数据挖掘技术有几种分类方法：根据发现知识的种类 分类、根据挖掘的数据库种类分类和根据采用的技术分类。 根据发现知识的种类分类 这种分类方法有：总结( s u m m a r iz a t i o n ) 规则挖掘、特征 ( c h a r a c t e r i z a t i o n ) 规则挖掘、聚类( c l u s t e l ? i n g ) 规则挖掘、 趋势( t r e n d ) 分析、偏差( d e v i a t i o n ) 分析、模式分析( p a t t e r n a n a l y s i s ) 等。 根据挖掘的数据库分类 数据挖掘基于的数据库类型有：关系型( r e l 8 t i o n a l ) 、事物型 ( t r a n s a c t i o n a ) 、面向对象型( o b j e c t e do r i e f t t e d ) 、主动型 ( a c t i r e ) 、空间型( s p a t i a l ) 、时间型( t e m p o r a l ) 、文本型 ( t e x t u a l ) 、多媒体( u u l t i m e d i a ) 、异质( h a t e r o g e n e o u s ) 型数据库 和遗留( l e g a c y ) 系统等。 根据采用的技术分类，最常用的数据挖掘技术是： 1 ) 人工神经网络：它从结构上模仿生物神经网络，是一种通过训练 来学习的非线形预测模型，可以完成分类、聚类、特征挖掘等多 种数据挖掘任务。 2 )决策树：用树性结构来表示决策集合。这些决策集合通过对数据 集的分类产生规则。典型的决策树方法有分类回归树( c a r t ) 典 型的应用是分类规则的挖掘。 3 )遗产算法：是一种新的优化技术，基于生物进化的概念设计了以 系列的过程来迭判优化的目的。这些过程有基困组合、交叉、变 异和自然选择。为了应用遗传算法。需要把数据挖掘任务表达为 一种搜索闯露而发挥遗产算法的优化搜索能力。 4 )最邻近技术：这种技术通过k 个晟与之接近的历史记录的组合来 辨别新的记录。有时也称这种技术为k 一最邻近方法。这种技术可 以用作聚类、偏差分析等挖掘任务。 关联规劓坩量妻所挖掘算洼舢膏共蛆页 c c 5 )规则归纳：通过统计方法归纳、提取有价值的i 卜t h e n 规则。规 则归纳的技术在数据挖掘中被广泛应用，例如关联规则的挖掘。 6 )可视化：采用直观的图形方式将信息模式、数据的关联或趋势呈 现给决策者，决策者可以通过可视化技术交互地分析数据关系。 下面，我们从发现知识的种类角度出发，就几种常见的数据挖掘方法作 个简单的介绍和比较。 2 3 1 数据总结 数据总结目的是对数据进行浓缩给出它的紧凑描述。抟统的也是最简 单的数据总结方法是计算出数据库的各个字段上的求和值、平均值、方差值 等统计值或者用真方圈、饼状圈等图形方式表示。数据挖掘主要关心从数 据泛化的角度来讨论数据总结。数据泛化是一种把数据库中的有关数据从低 层次抽象到高层次上的过程。由于数据库上的数据或对象所包含的信息总是 最原始、基本的信息。人们有时希望能从较高层次的视图上处理或浏览数据， 困此需要对数据进行不同层次上的泛化以适应各种查询要求。数据泛化目前 主要有两种技术：多维数据分析方法和面向属性的归纳方法。 多维数据分析方法是一种数据仓库技术，也称作联机分析处理( o l a p ) 。 数据仓库是面向决策支持的、集成的、稳定的、不同时间的历史数据集合。 决策的前提是数据分析。在数据分析中经常要用到诸如求和、总计、平均、 最大、最小等汇集操作，这类操作的计算量特别大。因此一种报自然的想法 是把汇集操作结果预先计算并存储起来，以便于决策支持系统使用。存储汇 集操作结果的地方称作多维数据库。多维数据分析技术已经在决策支持系统 中获得了成功的应用，如著名的s a s 数据分析软件包、b u s i n e s so b j e c t 公 司的决策支持系统b u s i n e s so b j e c t ，以及i b m 公司的决策分析工具都使用 了多维数据分析技术。 采用多维数据分析方法进行数据总结，它针对的是数据仓库数据仓库 存储的是脱机的历史数据。为了处理联机数据。研究人员提出了一种面向属 性的归纳方法。它的思路是，直接对用户感兴趣的数据视图进行泛化，丽不 是象多维数据分折方法那样预先就存储好了泛化数据。方法的提出者对这种 数据泛化技术称之为面向属性的归纳方法。原始关系经过泛化操作侯得到的 是一个泛化关系，它从较高的层次上总结了在低层次上的原始关系。有了泛 化关系后，就可以对它进行各种深入的操作而生成满足用户需要的知识，如 在泛化关系基础上生成特性规则、判别规则、分类规则以及关联规则等。 2 3 2 关联规则的发现 燕联规则曲增量蔓 把掘算法葶7 膏共 百 - 设i = i 1 ，i 2 一i m ) 是所有项目的集合，一个事物t 是一个项集，t i ， 在这里不考虑项目在事物中出现的次数，所有事物的集合设为d ，每个事物 与个称为t i d 的标识符相联系。设x 为一个项集，当且仅当x c t 时，我 们称事物r 包含x 。关联规则表示成这样的形式tx 等y ，这里x c i ，y c - z ， 并且x r h y ：o 。规则x j y 的确信度为c 是指在d 中，包含x u y 支持度的事物 所占的比例为c 。项集的支持度也是指包含项集的事物在d 中所占的比例。 一般地，由用户给定最小的确信度和支持度，发现相关规则的任务就是从数 据库中发现那些确信度和支持度都大于给定值的关联规则。 发现规则的过程可以分为两个步骤。第一步发现所有的频繁集，也就 是支持度大于给定避小支持度的项集；第二步从频繁集中产生关联撬则， 我们注意到挖掘的性能主要由第一步决定。当确定了频繁集后，关联规则就 可以很容易直观得到。 在许多应用中，人们可能不仅仅只对原始数据层次上的规则感* 趣。而 且对于更高概念层次上的规则感耀趣，因此，研究般化抽象层次上的关联 规则就显得比较重要了。这里的概念层次集合，它们代表了不同层次上的概 念之间的关系，记录了分离属性的所有不同值或者连续属性的数值范围。关 于概念层次的信息或者由领域专家提供，或者基于数据分布统计和不同属 性间的关系击自动地发现。近来，人们还对于定量关联规则以及其它种类的 关联规则的发现进行了研究。 得到关联规则以后，用户并不是对所有的规则感兴趣，而且，有些规则 可能误导人们的决策。比如，某关联规则x ；y 的支持度和确信度均大干要 求的最小值这条规则是一条强壮规则，但当y 在全体事务中所占的比率比 x 等y 的确信度还大时该规则将起误导作用。为此，我们在挖掘过程中 就要将此类规则删除掉从而引起了相关规则的兴趣度的概念。对于相关规 则x j y ，当s u p p o r t ( x u y ) 一s u p p o r t ( x ) * s u p p o r t ( y ) k 时，我们说该规则是 有兴趣的。 考虑到关联规则的数目可能是相当巨大的，人们在探索发现关联规则的 同时，对于提高数据挖掘过程的效率方露也作了不少的研究。常见的方法包 括减少对于数据库的搜索次数，适当放松对精确度的限制通过数据采样极 大地提高了采掘效率；当数据库经常变动时采用增量更新技术来防止对于 整个数据库的重新采掘；对数据挖掘进行并行化等。 2 3 - 3 数据分类 数据分类作为数据挖掘的一个重要的主题，在统计学、机器学、神经网 蔓舰刖的蕾量是新把掘算詹摹$ 筲并4 8 页 c 络和专家系统中得到了较早的研究，但只是近些年来，人们才将它与数据库 技术结合起来解决实际问题。数据分析实际上就是从数据库对象中发现共 性，井将数据对象分成不同几类的一个过程。在数据分类中一个样本数据 库被当作一个训练集，训练集中的每个元组都保持总数据库的所有属性，并 且都有个类的标识符与之相联系。分类的目标首先是对训练数据进行分 析，使用数据的某些特征属性，给出每个类的准确描述，然后使用这些描述， 对总数据库中的其它数据进行分类或者是为每个类产生更好的描述，也即 分类规则。 数据分类的方法很多，包括决策树方法、统计学方法、神经网络方法、 最近邻居方法等等。其中，基于决策树的分类方法与其它的分类方法比较起 来，具有速度较快，较易转换成简单的并且很容易理解的分类规则，或转换 成效据库查询语句，有时可得到更高的精确度等优点。在本节的余下部分， 我们主要介绍决策树方法的基本思想，以及考虑大量数据时的改进算法。 一般的决策树分类算法都可以分成两个阶段：树的构造和树的修剪。针 对某个属性对训练集进行划分，递归调用直到每个划分中所有例子属于同一 个类：当树构造好以后，要对建立在噪音数据之上的分枝进行修剪。分类的 晟终结果是一棵树，树上的结点代表了属性值，树边标识这个属性的不同值， 树叶表示不同的类，通过沿着树的路径来对数据对象进行分类。一棵树的质 量取决于分类精确度和树的规模。 通常，在构造子树的过程中，都需要对属性进行选择，从而简化树的规 模。选择的方法一般采用一个评估函数。比如，典型的决策树算法i d 3 就是 基于信息原理构造的评估函数。一棵树的复杂度于构造一棵树所需要的信息 相联系，在每次选择属性时，要保证构造以该属性作为根的子树所需要的信 息量最少。 随着数据集的增大传统的机器学习和统计学的方法就会面临着性能变 差或者精确度降低的问题，于是人们开始将一些新的技术与传统的方法结 合起来解决这些问题。最近，m e h t a 等人提出了一种称为s l i q 的方法，用 于从大型数据库中挖掘分类规则。s l i q 能移处理数字属性和范畴属性，井 将一种新的预先排序技术和宽度优先树生长策略结合起来用于决策树的构 造，在树的修剪阶段它基于m d l 原理使用了一种新的树修剪算法。这些新 技术的结台，使得s l i q 对于大规模的数据库和丈量的属性，都有较好的适 应性处理s l i o 以外，有的决策树分类方法在选择树的分支时，不只是考虑 单一属性，而是同时考虑相关的多个属性，从而提高产生分类规则的效宰。 * 累删的昔t 置新粘掘年浩弟，茸共船算 c 数据分类的应用比较广泛，包括信用认证医药诊断，治疗效果预测 货物存储等等。 2 34 数据聚类 在机器学习中，我们称数据聚类为非监督分类而数据分类则称为监 督分类两者所采用的方法帽差甚远，并且数据聚类的时间复杂度要比数据 分类大得多。数据聚类将物理的或抽象的对象分成几个群体在每个群体内 部，对象之间具有较高的相似性，而在群体之间，相似性则比较低。一般地， 一个群体也就是个类，但与数据分类不同，我们事先并不知道对象所属的 类。如果将数据集当作一个数据空间，每个数据对象当作空间上的一个点， 数据聚类的任务就是要在概率分析的基础上构造一棵树来识别各个群体，而 在统计学中，数据聚共一般采用基于距离的群聚方法。 聚类算法在统计方法、机器学习、神经元网络等领域同样得到广泛的 研究。传统的聚类分析的主要方法是似然分析。但这类方法的假设前提是不 同数据属性的概率分布援互独立。然而，在实际应用的数据挖掘系统中，也 就是说在一般的大数据集情况下，这个假设根可能是不成立的。在数据库中， 数据属性之间可能包含严重的耦合：另外，基于概率的树是非平衡树对于 这样的数据结构，其插入、检索的时间和空问代价都提高：当然这也使得聚 类结果的存取和更新都非常困难的。 n g 和h a n 发展了适用于丈规模应用的基于随机搜索的算法c l a r a n s 。 其算法复杂性基本上是正比于对象的个数的。基于此算法相关文献给出了 两种时间数据库的聚类算法s d 和n s d 。e s t e r 针对c l a r a n s 算法的缺点，提 出了改进算法，通过引入更为有效的空间数据库存取算法，如r 一树，来提 升c l a r a n s 算法的性能。t z h a n g 则提出了另一种聚类算法b i r c h 。这是一 种很好的聚类算法，具有很好的聚类品质和对阶数的不敏感性，应用表明它 基本上具有线形的规模伸缩性，以及其计算复杂度都是0 ( n ) 阶的， 2 4 典型的数据挖撼系统 在过去的几年里，世界各地的研究人员开发了大量各种各样的数据挖 掘应用系统或原形系统。主要可分为通用型和领域型两种。下面介绍几种有 代表性的系统。 2 4 1 通用型 i n l e n 系统。i n l e n 这个名字是推理( i n f e r e n c o ) 和学习( 1 e b r n i n g ) * 帆刖的越量曼新托掘算法摹l 口膏* 柏蔓 的复合，也暗含了它强大的功能。i n l e n 结合了数据库，专家系统和机器学 习功能为用户提供一个从数据库或提取有用知识的环境。它包含了专家数据 库的思想，把对数据库的存取能力和从基于知识的系统中导出良好根据的结 论的能力结合在一起。i n l e n 集成了几个先进机器学习技术，这些技术在此 之前仅仅啦独立的实验性程序存在。许多学习系统只能从实际数据的一个小 子集中学习通过把各种工具集成在一起，用户可以获得一个强有力和通用 的系统。i n l e n 系统包含一个用于存储领域事实的关系数据库，一个用于存 储规则、约束、层次、决策树带条件的方程式的知识库以及对数据库、知 识库进行各种操纵的各种先决条件。知识库中不但包含数据库内容的知识， 也包含对知识库动态维护的元知识，由于i n l e n 致力于将学习和发现算法收 集为算子，它不仅是一个工具而且还是一种方法。由于它合并了许多不同的 知识生成算子，i n l e n 有可能扩展知识发现系统的能力极限。 i b mi n t e l l i g e n tm i n e r 。它是i b m 的q u e s t 数据挖掘系统的商业版本。 它的主要功能有发现关联规则、发现序列模式、时间序列聚类、分类和增量 知识发现。采用并行算法以支持大规模数据集，提供决策支持。 d b m i n e r 系统。它的前身是著名的d b l e r n 。采用了面向属性的归纳、 统计分析、元规则指导的知识发现等技术并实现了很多数据挖掘的功能如分 类、预测、关联规则等。 4 9 e r 。4 9 e r ( f o r t h - n i n e r ) 系统是有美国j m z y t k o w 和r z e m b o w e i z 开发的一个通用数据挖掘系统。该系统可处理多个数据子集上的大规模的检 索通过产生列联表，精化韧始规则，进而生成强通用规则和有用的概念。 4 9 e r 结合了几种查询方法每一种适用于一类规舜j 的一个不同方面。 e x p l o r a 。e x p l o r a 是由h o s c h k a 和k l o s g e n 开发的一个用于概念性的 分析数据和援索感必趣关系的集成化系统。该系统的运行是通过模扳来寻找 “事实”，完成图的搜索。一个事实是一个模式模板的具体的数据实蜘。利 用交互式测览，终端用户可以得到有序的事实集，并可产生面向用户的最终 报告。用户也可以通过介入发现过程去创建新的模板，修改验证方法。 k d ，( k n o v l e d g ed i s c o v e r yw o r k b e n c h ) 。k d w 是交互式的大型数据库 的分析工具。该系统由美国g p i b t e t s k y s h a p i r o 等人开发已开发有多种 版本，所有版本都提供了一整套图形用户界面工具。该系统可用于存鞭数据 库表和创建新字段，数据汇集定义，图形显示数据和结果，选用发现算法及 处理领域知识，k d w 系统包括的模式抽取算法有：识别简单线形类别的聚类； 用决策树方法获取分类规则；能识别各类闻有显著差异的偏差检测；用于发 * 聪刖的靖量蔓秆挖掘算法 第i l 膏共8 再 现和显示随机依赖关系的依赖关系分析。 e c c 2 4 2 领域型 s k i c a t 系统。这是空间图象分类和分析工具。它的主要任务是识别空 间照片上暗天体的类别。每个天体被天文学家赋予4 0 个属性。s k i c a t 系统 采用决策树学习算法来预测天体的类别。通过统计优化后的决策数上提取规 则，s k i c a t 取得了9 4 的预测正确率并协助天文学家发现了1 6 个高度红移 的类星体。 q u a k e f i n d e r 系统。它通过检测卫星数据自动探测地壳的构造运动以发 现地震。它基于统计方法，运行与一台2 5 6 节点的c r a yt 3 d 超级并行计算 机上，曾成功发现1 9 9 2 年南加州地震的造成地表错位方向和尺寸，对方圆 数百平方公里的区域精确到1 米。 2 5 数据搠的应用 数据挖掘在应用上已取得一批丰硕成果，特别在超大型数据库方面。 芬兰著名学者k o h o n e n 教授采用“自组织映射( s o m ) ”神经网络实现超大型 数据库的数据挖掘颇受人们重视。他提出了一个实例，描述一个数据的组 织系统和按内容访问的存储器。该系统由两层s o m 体系结构组成，文本由上 层的网络节点映射，其几何图形位置的顺序反映了内容的相似性；下层网络 节点是对文字进行映射，将文字聚成若干类。使用该系统对报纸和新闻进行 分类，得到1 1 0 万条信息约2 亿文字。信息采掘系统按其语义、内容集类， 经过主体筛选，最终送s o m 处理的有6 万多个文字。这个网络根大，第一级 输入有2 7 0 个节点，第二级输入育3 l5 个节点输出最终达1 0 万个。该系 统可用于查询，人们将来可用来建立个人信箱。如果需要专门收集某一方面 的信息，该系统可在信息海洋中查询，自动将你感趣的数据信息送到你的 信箱中。 而空问数据挖掘的目的则是空间数据霹发现各种隐含知识如空间对 象的位置关系、特征模式等，可广泛应用于地理信息系统、图象数据库探索、 医学图象处理等方面。由于空间数据库具有数据量大、空问数据类型和空间 存取方法复杂等特点，空间数据算法的效率是其中最富有挑战性的问题。 数据挖掘在i n t e r n e t 中的应用也臼益增多，国外已研制开发出 h a r v e s t s h o p b o t a h o y 等系统。其中，h a r v e s t 系统是较为典型的数据挖掘 信息挺取系统。它处理的对象是半结构化的文档。每天它都利用手工编写的 _ r a p p e r 分析一批固定的e b 资源。在l a t e x 文档中，它可以找到作者、标 题等信息；在p o s t s c r i p t 文档中，它可以找到格式、位置等信息。另外， 关联规删的坩量量雠叠鼻法摹1 2 膏共4 。百 数据挖掘还可以用于金融业、大型连锁商场等。例如，利用可试化技术将银 行的存款、贷款、利率、投资基金、信托基金等数据关联呈现出来，使银行 更好地安排和管理业务。证券业采用数据挖掘技术，对全球股市、期货市场 实时数据进行提取借助人的智慧和经验进行判断，揭示其内在规律性，以 取得最大收益。大型连锁商场则可用此按术找出各种商品销售之问的关联以 及分析商品的资金占有比例，以达到最佳的资源配置。 是捌删的j l 量蔓范擅算法弟1 3 百g - 葺 c 第三章关联规则挖掘的内容及技术 3 1 关联规则的挖掘 我们对这个关赣规则作一个正式的描述：令i t j 。，i ：，i 为个文法 的集合，称为项目。d 为一个事务的集合，其中每个事务t 是项目i 的集合， t c l 。如果x c t ，则我们说事务t 包含x 。关联规则是这样一种形式的蕴含 关系：x y ，其中x c i y c i 并且x f 3 y = o 。规贝f jx y 有效必须满足下列 二个条件： 满足支持度s 即事务集d 中有s 个事务包含集台x u y 。 满足信任度c ，即在含有y 的事务中有c 个事务包含集台x u y 。 对于个事务集d 关联规则的挖掘就是产生所有的规则，其支持度和 信任度分别大于用户所定义的最小支持度和最小信任度。挖掘关联规则的问 题可分为以下二步： 发现大的频繁集。项目集的支持度太子预定义的最小支持度。 用犬的频繁集去产生关联规则。 由于发现大的频繁集需要对数据库的中数据的大量运算，因此挖掘关 联规则的性能主要由第一步决定。在最大项目集确定后，相应的关联规则可 通过一个直接的方法推断得出。有教计算最大频繁集是关联规则挖掘的一个 焦点，a p r i o r i 算法正是针对了这一问题。 3 2a p r t o r t 算法 观察所给的事务数据库如图3 1 。a p r i o r i 构造了最大项目集的候选集， 记录每个候选集在事务集中的出现次数，然后依据预定义的最小支持度确定 最大频繁集。 羽di t e m s 1 0 0a c d 2 0 0b c e 3 0 0a b c e 4 0 0b e 瞳3 f ：数据挖掘的事务数据痒 首先，a p r i o r i 衙单地扫描所有的事务，去计算每个项目的发生数。候 = i t 黛规一曲增t 量挖算法革1 膏共j | c 选集c ，如图32 所示。假设最小支持度的要求为2 ，则最大1 - 频繁集l ， 确定。为了发现最大2 - 频繁集，根据最大频繁集的子集也频繁原理，a p r i o r i 采用l ，+ l 。产生候选集c 2 。接着，数据集中的4 个事务被扫描，并且在c ： 中的每个候选集的支持被记录。图32 中的第二排表示了对c ：的计数结果。 根据c ：中的支持度，l ：确定。 候选集c ，从l ：中生成。首先对于l ：中二个2 项目集具有相同项目如 b c 和 b e 先确定。然后测试2 项目集 c e ) ( 仅包含它们第二个项目) 是否属于 l ：，由于 c e 属于l 2 ，因此可知 b c e 的所有子集都频繁，则 b c e 成为新 的候选集c 3 没有其他的3 候选集从l 2 中生成。通过扫描所有事务，发现l ，。 由于没有4 候选集从l 3 中生成，a p r i o r i 结束发现最大频繁集过程。 扫描d _ - 陌磊 i b c e l i 一 c 项目集度持度 a 2 b 3 c 3 f d ，l e 3 扫描d 扫描d + 项目集，支持度 a b i t a c 2 a e _ l b c 2 b e 3 c e ) 2 圈3 ，2 p r i o r i 生成量大频繁集过程 。 3 3 挖掘般化和多层的关联规则 蔓黼肿坩量足卉挖越算法摹i j 页共1 8 膏 实际生活中，人们感兴趣的关联规则往往是在较高层次的概念层。例 如：在一个事务数据库中的购买模型可能在原始数据层中没有显示出其可靠 的联系然而在较高的概念层次中可得出其关联关系例如牛奶和面包。所 以在一般化的抽象层和多个抽象层中对关联规则的挖掘是重要的。 圈3 3 概念层次结构 图33 显示是概念的层次分类。这些层次结构可由用户和专家清晰定 义。在原始概念层，根难发现购买模型的真实的支持度，只能知道1 瓶5 0 0 m l 光明纯牛奶和1 包5 0 0 克香提小麦面包。然而，在较高的抽象层，我们发现 8 0 的顾客在购买面包的同时购买了牛奶。而且可能发现7 0 顾客如果购买 了纯牛奶将会购买小麦面包。出于低层的概念层比上层带有更多的特定信 息，所以在般化和多层的概念层上挖掘关联规则是根重要的。 多层关联规则的挖掘概念：当且仅当高层的父母是频繁的才对相应低 层的关联规则测试，不同的层次采用不同的最小支持度门限。 并非所有的发现的关联规则都是值得去表示的。例如对一个学校的5 ，0 0 0 名学生进行早晨参与活动与早餐的情况调蠢。数据显示：6 0 学生( 3 ，0 0 0 ) 打 蓝球7 5 学生( 3 ，7 5 0 ) 吃谷类早餐，4 0 学生( 2 ，o o o ) 既打蓝球又吃谷共早餐。 假设数据挖掘系统对关联规则的参数设置如下：最小学生支持度2 ，0 0 0 、晟 小自信度6 0 。则可知关联规则“打蓝球 吃谷类早餐”将产生，其最小学 生支持度2 ，0 0 0 ，最小岛信度2 0 0 0 f 3 0 0 0 = 0 ，6 6 。然而以上规则是误导，因为 总的吃谷类早餐的学生的比例7 5 大于6 6 ，印打蓝球和吃谷类事实上是对 立的。如果没有完全正确的理解这一方面，人们可能从所挖掘出的关联规则 作出错误的决定。 关联规1 4 曲坩t 蔓井挖掘算法第1 6 奔共档寅 c c 原先定义关鞋规则有意义当且仅当“a b ”的支持度满足昂小支持度 要求同时自信度超过一个合适的常数。然而，为了过滤上例中的规则，对自 信度的测试要求满足如下表达式：p ( a n b ) 一p ( a ) p ( b ) k ，其中k 是台适常 数。 3 5 提高挖掘关联规则的效率 由于在挖掘关联规则中总的数据处理量非常巨大，设计一种有效的挖 掘算法是相当重要的。以下说明了一些提高挖掘效率的技术。 3 5 】减少效据库扫描次数 在a p r i o r i 算法中，c 3 是由l 2 l 2 构成。事实上，c 3 也常由c 2 直接生 成。由c 2 c 2 生成的c 3 显然大于i c ，i ，其中c 3 由l 2 l 2 构成。当i c 3 i 、i c 3 i 相差不多时，c ：和c ，同时存贮在内存中，当下一次数据库扫描完成后，l 2 和l ，就能同时获得，节省了一次数据库的扫描。显然通过这个概念，人 们可决定所有的l 。仅仅通过二次数据库扫描，第一次扫描决定l ，最终一 次扫描决定所有其他频繁集。假设c k ( 其中k = 3 ) 由ck 1 直接构成，并且 所有c 。，k 2 都保存在内存中，使数据库扫描次数减少，这种技术称为减