（应用数学专业论文）关联规则挖掘算法改进研究.pdf

信息j 群人学硕十学俯论文 摘要 近年来，随着数据库技术的迅速发展，数掘存量大量增加，数据挖掘技术变得越束越 重要，从而引起了各个学术领域的研究人员的兴趣，数据挖掘旋即扩展到各个领域。关联 规则挖掘是数据挖掘中最活跃的研究方法之一。数掘挖掘作为一种用于从大规模数掘集中 提取潜在有用的信息和知识的技术，越来越得到广泛的研究和应用。而关联规则挖掘作为 最初推动数掘挖掘迅猛发展的一个重要因素，被广泛应用于大型零售组织的决策支持中， 它为确定市场策略、提高决策支持能力提供了有力的技术和工具保证。 本文首先介绍了数据挖掘的基本任务和技术，接着引出了关联规则的挖掘问题，重 点介绍了挖掘关联规则的两种经典算法一a 叫甜算法和基于f p g r o w t h 的关联规则挖掘 算法，并对提高a p r i o d 算法效率的几种方法进行了简单分析。 在对关联规则挖掘算法进行分析之后，本文提出了两种新的关联规则挖掘算法 基于最大频繁模式的关联规则挖掘算法和基于矩阵的关联规则挖掘算法。使用最大模式挖 掘关联规则频繁项集，可以显著的压缩挖掘所产生的频繁项集数，能够快速地找出关联规 则，并且该算法避免了传统a p r i o r i 算法反复扫描数掘库所造成的时问及空f b j 上的局限。基 于矩阵的关联规则挖掘算法，可以大大减少扫描数掘库的次数，从而提高算法的效率；同 时，在生成关联规则中，利用了概率论的基本性质，与传统的要求计算频繁项集的所有非 空子集，并计算置信度进行判定相比，也是大大减少了计算量。 最后，本文将提出的两种算法与a 研嘶算法及f p g r o w t h 算法进行了性能比较，实 验证明，本文提出的这两种算法不论在时间还是空日j 上均是有效的。 关键词：数据挖掘关联规则最大模式频繁项集矩阵 第1 贞 信息i 科人学硕十学付论文 a b s t r a c t r e c e n t l yd a t am i n i n gi sb e c o m i n gm u c hm o r ei m p o r t a n ta st h en u m b e ro fd a t a b a s e sa n d d a t a b a s es i z ek e e p sg r o w i n g r e s e a r c h e r si nm a n yd i f f e r e n tf i e l d sh a v es h o w ng r e a ti n t e r e s ti n d a t am i n i n g t h es c o p eo fd a t am i n i n gr e s e a r c hi sa l s oe x t e n d e dt ov a r i o u sf i e l d s a s s o c i a t i o n r u l e sm i n i n gi so n eo f t h em o s th o t t e s tf i e l d so f d a t am i n i n gr e s e a r c h d a t am i n i n ge m e r g e da sa r a p i d l yg r o w i n gt e c h n o l o g yi no r d e rt o e x t r a c tv a l u a b l ei n f o r m a t i o na n dk n o w l e d g ei nl a r g e v o l u m e s o f d a t a m i n i n ga s s o c i a t i o n r o l e si sa ni m p o r t a n tr o l eo f d a t am i n i n gb e c a u s eo f i t sw i d e a p p l i c a b i l i t yi nm a r k e ta n a l y s i sb ye x p r e s s i n gh o wt a n g i b l ep r o d u c t sa n ds e r v i c e sr e l a t et oe a c h o t h e ra n dh o w t h e yt e n dt og r o u pt o g e t h e r i nt h i sp a p e r , w ef i r s te x p l a i nt 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 si se d u c e df o l l o w i n gt h e i n t r o d u c t i o no ft h et a s k sa n dt e c h n i q u e so fd a t am i n i n g t h e n , w ee m p h a s i z et w oc l a s s i c a l a l g o r i t h m s - - a p r i o r ia l g o r i t h ma n df p - t r e ea l g o r i t h ma n da n a l y z es o m em e t h o d so fi m p r o v i n g a p r i o r ia l g o r i t h m a f t e ra n a l y z i n gt 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 ，w ed e s i g nt w on e wm e t h o d so f m i n i n ga s s o c i a t i o nr u l e s 一- am e t h o do fm i n i n ga s s o c i a t i o nr u l e sm i n i n gb a s e do nm a x i t e m s e t s a n dam e t h o do fm i n i n ga s s o c i a t i o nr u l e sb a s e do nm a t r i x u s i n gm a xi t e m st om i n ef r e q u e n t i t e m s e t sc a nr e d u c et h ea m o u n to ff r e q u e n ti t e m s e t sr e m a r k a b l ya n df i n da s s o c i a t i o nr u l e s q u i c k l y a tt h es a m et i m e ，i ta v o i d sl o c a l i z a t i o no ft i m ea n ds p a c e m a t r i xc a n r e d u c et h ed e g r e e o fs e a n i n gt h ed a t a b a s ea n di m p r o v et h ee f f i c i e n c y d u r i n i n gm a k i n ga s s o c i a t i o nr u l e s ，i tu s e st h e k n o w l e d g eo f p r o b a b i l i t ya n d r e d u c e sc a l c u l a t i n gg r e a t l y a tl a s l w ec o m p a r et h et w on e wm e t h o d sw i t l la p r i o f ia l g o r i t h ma n df p g r o w t ha l g o r i t h m b yp e r f o r m a n c e a n df i n dt h a tt h e ya r ee f f e c t i v em e t h o d so f a s s o c i a t i o nr u l e r sm i n i n g k e yw 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 em a xi t e m f r e q u e n tp a t t e r n m a t r i x 第1 1 负 论文原创性声明和使用授权 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及 取得的研究成果。尽我所知，除了本文中特别加以标注和致谢中所罗列 的内容外，论文中不包含其它人已经发表或撰写过的研究成果；也不包 含为获得信息工程大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中做了明确 的说明并表示了谢意。 本人完全了解信息工程大学电子技术学院有关保留和使用学位论 文的规定，即：学院有权保留论文的复印件，允许查阅和借阅论文；可 以公布论文的全部或部分内容；可以采用影印、缩印或其它手段保存论 文。涉密论文按保密规定执行。本论文取得的研究成果归学院所有，学 院对该研究成果享有处置权。 本人签名：鹰趣日期：劢z 导师签名： 知乙嗍彬 信息l ：稃人学硕十学位论文 第一章绪论 数掘挖掘从大量数据中用非凡的方法发现有用的知识是数据库研究、丌发 和应用最活跃的分支之一。它是一个多学科交叉领域，从多个学科汲取营养。数掘挖掘出 现于2 0 世纪8 0 年代后期，9 0 年代有了突飞猛进的发展，并可望在新千年继续繁荣。 1 1 课题背景 需要是发明之母。近年来，数掘挖掘引起了信息产业界的极大关注，其主要原因是 存在大量数掘，可以广泛使用，并且迫切需要将这些数据转换成有用的信息和知识。获取 的信息和知识可以广泛用于各种应用，包括商务管理、生产控制、市场分析、工程设计和 科学探索等。随着提供查询和事务处理的大量数掘库系统广泛付诸实践，数掘分析和理解 自然成为下一个耳杯。 随着数掘库技术的迅速发展，人们积累的数据越来越多。数掘的背后应隐藏着许多重 要信息，人们希望能够对其进行更高层次的分析，以便更好地利用这些数据。目前的数据 库系统可以高效地实现数据的录入、统计、查询等功能，但无法发现数据中存在的关系和 规则，无法根掘现有的数据预测未来的发展趋势。缺乏挖掘数据背后隐藏的知识的手段， 导致了“数据爆炸但知识贫乏”的现象。数据挖掘就是在这种情况下产生和发展起来的。 数掘挖掘是一个从数据中提取出有效的、新颖的、潜在有用的、并能最终被人理解的模式 的非平儿过程。 例如，股票经纪人需要从同积月累的大量股票行情变化的历史记录中发现规律，以供 预测未来趋势；超级市场的经理希望能够从过去几年的销售记录中分析出顾客的消费习 惯，以便及时变换营销策略；地质学家想通过分析地球资源卫星发回的大量数据和照片束 发现有丌采价值的矿物资源等。 在经过十几年的技术发展之后，国外在数据挖掘技术上取得了丰富的经验。不但在研 究方面使各个学科的经验向该领域集中，而且也出现了大量的软件产品，在社会的各个领 域的应用也取得了丰硕的成果。 在国内，数掘挖掘已经从单纯的研究走向产品的丌发及技术的应用，随着市场经济的 不断完善，数掘挖掘的市场需求币在高速增长。数掘挖掘与其他软件不同，由于需要不断 地实验与评估，不懂原理或没有核心软件技术，其应用效果将大打折扣。在数据挖掘领域， 我国的国产商品软件刚刚起步，但发展速度很快，随着市场的成熟与应用水平的提高，将 缡1 噍( 信息i 群人学硕十学位论文 会出现大量的国产软件产品。 随着k d d 在学术界和工业界的影响越来越大，国际k d d 组委会于1 9 9 5 年把专题讨 论会更名为国际会议，在加拿大蒙特利尔市召丌了第一届k d d 国际学术会议，以后每年 召开一次。近年来，k d d 在研究和应用方面发展迅速，尤其在商业和银行领域的应用比 研究的发展速度还要快。 目前，国外数据挖掘的发展趋势及研究方面主要有：对知识发现的研究进一步发展， 如近年来注重对b a y e s ( 贝叶斯) 方法以发b o o s t i n g 方法的研究和提高；传统的统计学回 归法在k d d 中的应用；k d d 与数掘库的紧密结合。在应用方面包括：k d d 商业软件工 具不断产生和完善，注重建立解决问题的整体系统，面不是孤立的过程。用户主要集中在 大型银行、保险公司、电信公司和销售业。国外很多计算机公司非常重视数据挖掘的丌发 应用，i b m 和微软都成立了相应的研究中心进行这方面的工作，此外，一些公司的相关 软件也丌始在国内销售，如p l a t i n u m 、b o 以及i b m 。 国内从事数掘挖掘研究的人员主要在大学，也有部分在研究所或公司。所涉及的研究 领域也很多，一般集中于学习算法的研究、数掘挖掘的实际应用以及有关数据挖掘理论方 面的研究。目前进行的大多数研究项目是由政府资助进行的，如国家自然科学基会、8 6 3 计划、“九五”计划等，但还没有关于国内数掘挖掘产品的报道。 关联规则挖掘发现大量数掘中项集之间有趣的关联或相关联系。伴随着人们处理的数 据量的不断增大，产生了许多大规模的事务数掘库，这些数据库在物理上是分句的，很难 进行集中式的数据挖掘。此外，随着网络技术的发展，也促使在大型分却式事务数掘库中 挖掘关联规则成为迫切需要解决的问题。 自r a g r a w a l ，rs r i k a n t 首次提出关联规则“以来，已经提出了大量关联规则挖掘算法 ( 参见【2 】一【6 】) 。这些算法大多基于a p r i o r i 算法吨1 ，在挖掘频繁模式时需要产生大 量候选项集，多次扫描数据库和维护一椽很大的h a s h 树，时日j 和空日j 效率都有待提高。 近年来，j i a w e ih a r t ，j i a np e i 和y i w e ny i n 提出了基于模式增长的频繁模式挖掘算法。 算法不产生候选项集，只需要两次扫描数据库，其挖掘频繁模式的速度比a 研o r i 算法提 高了一个数量级。虽然算法能够有效地从数掘库中挖掘频繁模式，但如何由其挖掘出的频 繁模式有效生成关联规则仍是一个相当复杂的问题。关联规则是拙述数据之日j 存在关系的 规则，形式为“a i a a 2 a a 。一b f a b 2 a b n ”。一般分为两个步骤：求出大数据项 集。用大数掘项集产生关联规则。 第2 贝 信息l 。科人学硕十宁位论文 1 2 论文的研究内容和意义 目前大部分关联规则的挖掘算法均以a p r i o r i 算法为核心，而此算法的主要缺点是要 多次扫描数掘库，故效率不是很理想。本文对几种典型的关联规则挖掘算法进行了分析， 并提出了新的见解，提高了原有算法的效率。 同时，设计了一个基于最大频繁模式的关联规则挖掘算法，首先找到所有的频繁i 项集，由此找出所有的最大频繁项集，根掘频繁项集的性质：频繁项集的所有子集均为频 繁项集。从而得到所有的频繁项集，此算法可省去传统的剪枝步骤，而且可以很容易得到 频繁项集的所有子集，找出相应的关联规则。 对传统的a p r i o r i 算法进行改进，主要是针对该算法的剪枝步。本算法使用连接步产 生候选项集，基于频繁项集的反单调性：“频繁项集的所有子集都是频繁项集”，进一步对 候选项集进行压缩，减少扫描数掘库的次数，从而提高运算效率。 设计了一种基于矩阵的关联规则挖掘算法，此算法首先将所有的1 项集各赋值于f 2 上的一个向量，从而找出所有的频繁1 项集，然后反复利用“逻辑与”算法，得到频繁 2 项集，3 项集，。并研究了由其挖掘出的频繁模式有效生成关联规则。 1 3 论文的结构和组织脉络 论文对几种经典的关联规则算法进行了分析，对原有的算法进行了改进，通过实验分 析证明了本文提出的算法是行之有效的。具体章节如下： 第一章绪论。介绍了论文的选题背景、依据、意义及研究内容、国内外相关领域研究的 现状：简述了论文研究的内容及意义；给出了论文的结构和组织脉络。 第二章数掘挖掘。介绍了数掘挖掘的概念、数掘挖掘的数掘来源、数据挖掘的分类及数 掘挖掘的主要问题。 第三章关联规则。介绍了关联规则挖掘的基本概念、关联规则挖掘的分类、并详细介绍 了单维布尔关联规则的发现方法a 两o r i 算法及如何提高其有效性和无需产生候选 频繁项集的f p 。g r o w t h 算法。 第四章基于最大模式的关联规则挖掘。提出了一种基于最大模式的关联规则挖掘算法， 探讨了它的实现步骤，并通过实例说明它是数据挖掘中有效的关联规则挖掘算法。 第五章基于矩阵的关联规则挖掘。改进了一种基于矩阵的a p r i o r i 算法，同时改进了发现 关联规则的算法，并通过实例说明它是一种有效的关联规则挖掘方法。 第六章总结与展望。给出了本文的总结和需进一步研究的工作。 第3 虹 信息l 群人学硕十学伊论文 第二章数据挖掘 随着数据库技术的飞速发展以及人们获取数掘手段的多样化，人类所拥有的数掘急剧 增加，可是目l j i 用于对这些数掘进行分析处理的工具却很少。数据库系统所能做到的只是 对数据库中已有的数掘进行存取和简单操作，人们通过这些数据所获得的信息量仅仅是整 个数掘库所包含的信息量的很少一部分，隐藏在这些数掘之后的更重要的信息是关于这些 数掘的整体特征的描述及对其发展趋势的预测，这些信息在决策制定的过程中具有重要的 参考价值。数据挖掘应运而生了。 近年来，随着数据库技术的不断发展，存储在数掘库中的信息量也在大量增加，怎样 从一大堆随机的数据中发掘出一些有价值的信息逐渐成为一个重要的课题，由此带动了数 掘挖掘技术的产生和飞速发展。 自数掘库这一概念出现以来，数掘库技术的发展经历了几个重要的阶段。最初的数掘 是由一些原始的文件来存储，在2 0 世纪6 0 年代，功能强大也更加复杂的数掘库系统取 代了原始的文件处理，数据库技术正式进入了飞速发展的崭新阶段。自7 0 年代以来，数 掘库系统的研究和丌发已经从层次和网状数掘库系统发展到丌发关系数掘库系统、数据建 模工具、索引和数据库组织技术。此外，用户通过查询语言、用户界面、优化的查询处理 和事务管理，可以方便、灵活地访问数据。在8 0 年代中期以后，各种纷繁复杂的数据库 技术更是如阿后春笋般地出现。首先是各种类型的数掘模型被广泛采用，如扩充关系模型、 面向对象模型、对象关系模型和演绎模型。其次是数掘库存储的内容的应用的范围不 断丰富，包括空i 日j 的、时间的、多媒体的、主动的和科学的数掘库、知识库及办公信息库。 同时，涉及分伟性、多样性和数据共享问题被广泛研究。在最近的几年，异种数掘库和基 于互连网的全球信息系统，如w w w 也已出现，并成为信息产业的主力军。图2 1 归纳 了数据库技术的演化过程。 数掘的丰富带来了对强有力的数掘分析工具的需求。大量的数掘被描述为“数掘丰 富，但信息贫乏”，因为存储在大型数掘库中的数据可以用海量来形容，理解这些数掘中 隐含的知识已经超出了人力的范围，没有强有力的分析工具，这些数掘就变成了“数掘 坟墓”很难再访问的数据档案。于是，数掘挖掘技术应运而生，利用数据挖掘工具进 行数掘分析，可以发现重要的数掘模式，对商务决策、知识库、科学和医学研究作出了重 大贡献。数掘和信息之间的鸿沟要求系统地开发数据挖掘工具，将数据的“坟墓”转变 成知识的“会块”。 第4 贞 信息i 拌人学硕十学伊论文 图2 - 1 数据库技术的演化 2 1 什么是数据挖掘 数掘挖掘( d m ，d a t a m i n i n g ) 就是从大量的、不完全的、有噪声的、模糊的、随机 的数据中，提取隐含在其中的、人们事先不知道的、但又潜在的有用信息和知识的过程， 第5 贞 信息i ：稃人学硕十学付论文 即“从数掘中挖掘知识”。还有很多和这一术语相近的术语，如数据库中知识挖掘、知识 提取、数掘模式分析、数据考古和数掘捕捞等。国内的学者也把d a t am i n i n g 译为数据采 掘或数掘丌采。 当今数掘库的容量已经达到上力亿的水平。在这些大量数掘的背后隐藏了很多具有决 策意义的信息，那么怎么得到这些“知识”呢? 也就是怎样通过一棵棵的树木了解到整个 森林的情况呢? 计算机科学对这个问题给出的最新回答是数据挖掘，在“数掘矿山”中找到蕴藏的 “知识会块”，帮助企业减少不必要投资的同时提高资会回报。数掘挖掘给企业带来的潜 在的投资回报几乎是无止境的。世界范围内具有创新性的公司都丌始采用数据挖掘技术柬 判断哪些是最有价值客户，重新制定产品推广策略，以用最小的花费得到最好的回报。 基于数掘挖掘的广义观点：数掘挖掘是从存放在数掘库、数掘仓库或其他信息库中的 大量数掘中挖掘有趣知识的过程。典型的数掘挖掘系统具有以下主要成分( 见图2 2 ) ： 数据库、数据仓库或其他信息库：这是一个或一组数据库、数掘仓库、电子表格 或其他类型的信息库。可以在数据上进行数掘清理和集成。 数据库或数据仓库服务器：根掘用户的数掘挖掘请求，数掘库或数掘仓库服务器 负责提取相关数据。 知识库：这是领域知识，用于指导搜索，或评估结果模式的兴趣度。 数据挖掘引擎：这是数据挖掘系统基本的部分，由一组功能模块组成，用于特征 化、关联、分类、聚类分析以及演变和偏差分析。 模式评估模块：通常，此成分使用兴趣度度量，并与数掘挖掘模块交互，以便将 搜索聚焦在有趣的模式上。它可能使用兴趣度阈值过虑发现的模式。模式评估模块 也可以与数掘挖掘模块集成在一起，这依赖于所用的数掘挖掘方法的实现。 图形用户界面：本模块在用户和数掘挖掘系统之i 日j 通信，允许用户与系统交互， 指定数掘挖掘查询或任务，提供信息、帮助搜索聚焦，根掘数掘挖掘的中间结果进 行探索式数据挖掘。 数掘挖掘永远不会替代有经验的商业分析或管理人员所起的作用，它只是提供一个强 大的工具。每个成熟的、了解市场的公司都已经具有一些重要的、能产生高回报的模型， 这些模型可能是管理人员花了很长时f b j ，作了很多调查，甚至是经过很多失误之后得出来 的。数据挖掘工具要做的就是使模型得到更容易、更方便，而且有依据。 数掘挖掘涉及多学科技术的集成，包括数掘库技术、统计学、机器学习、高性能计算、 模式识别、神经网络、数据可视化、信息检索、图像与信号处理和空日j 数据分析。通过数 掘挖掘，可以从数掘库提取有趣的知识、规律或高层信息，并可以从不同角度观察或浏览。 第6l 且 信息i 拌人学硕+ 学位论文 发现的知识可以用于决策、过程控制、信息管理、查询处理，等等。因此，数掘挖掘被产 业界认为是数掘库系统最重要的前沿之一，是信息产业最有前途的交叉学科。 数 数据库数据仓库 图2 - 2 典型的数据挖掘系统结构 2 2 数据挖掘的数据来源 数掘挖掘所依赖的数据来源多种多样，可以是常用的关系数掘库、事务数掘库、文本 数掘库、多媒体数掘库等，主要取决于用户的目的及所处的领域。目前，数掘挖掘的数据 主要取自关系数据库与数据仓库。 1 关系数据库 关系数掘库系统，也称数据库管理系统( d b m s ) ，由一组内部相关的数掘( 称作数掘 库) ，和一组管理和存取数掘的软件程序组成。软件程序涉及如下机制：数掘库结构定义， 数掘存储，并发、共享或分布的数掘访问，在面对系统瘫痪或未授权的访问时确保数据的 一致性和安全性。 关系数掘库是表的集合，每个表都赋予一个唯一的名字。每个表包含一组属性( 列或 字段) 并通常存放大量元组。关系中的每个元组代表一个被唯一的关键字标识的对象，并 第7 虹 信息i ：拌人学硕十学位论文 被元组属性值描述。语义数掘模型，如实体一联系( e r ) 数掘模型，将数掘库作为一组实 体和它们之| 日j 的联系进行建模。通常为数据库构造e r 模型。 当数掘挖掘用于关系数据库时，可以进一步搜索趋势或数掘模式。例如，数据挖掘系 统可以分析顾客数据，根掘顾客的收入、年龄和以前的信用信息预测新顾客的信用风险。 数据挖掘系统也可以检测偏差，如与以i j 的年份相比，哪种商品的销售出人意料。这种偏 差可以进一步考察( 例如，包装是否有变化，或价格是否大幅度提高) 。 关系数掘库是数据挖掘最流行的、最丰富的数掘源，因此它是我们数掘挖掘研究的主 要数据形式。 2 数据仓库 数掘仓库是从多个数据源收集的信息存储，存放在一个一致的模式下，并通常驻留在 某个站点。数据仓库通过数掘清理、数据变换、数掘集成、数据装入和定期数掘刷新来构 造。大部分情况下，数掘挖掘都要先把数据从数掘仓库中拿到数掘挖掘库或数掘集市中。 通常，数掘仓库用多维数掘库结构建模。其中，每一维对应于模式中的一个或一组属 性，每个单元存放某个聚集度量值，如c o u n t 或s a l e sa m o u n t 。数据仓库的实际物理结构可 以是关系数据存储或多维数掘立方体( d a t a c u b e ) 。它提供数据的多维视图，并允许预计算 和快速访问汇总的数据。图2 3 给出了数掘仓库的基本结构。 数据源 图2 - 3 典型的数据仓库结构 通过提供多维数据视图和汇总数掘的预计算，数掘仓库非常适合联机分析处理 ( o l a p ) 。o l a p 操作使用数掘的领域背景知识，允许在不同的抽象层提供数据，这些操 作适合不同的用户。o l a p 操作的例予包括下钻( d r i l l d o w n ) 和上卷( r o l l u p ) ，它们允许用 户在不同的汇总级别观察数掘。 尽管数掘仓库工具对于支持数据分析是有帮助的，但仍然需要更多的数掘挖掘工具， 第8 贝 信息l 科人学硕十学位论文 以便进行更深的自动分析。 3 事务数据库 事务数据库由一个文件组成，其中每个记录代表一个事务。通常，一个事务包含一个 唯一的事务标识符( t r a n s _ i d ) ，和一个组成事务的项的列表。事务数掘库可能有一些与之相 关的附加表，包含关于销售的其他信息，如事务的同期、顾客的i d 号、销售者的i d 号、 销售分店，等等。 4 高级数据库系统和高级数据库应用 随着数据库技术的发展，各种高级数据库系统已经出现并在丌发中。由原来的单一关 系数掘库发展到面向对象数据库和对象一关系数掘库系统、空i b j 数掘库系统、时问和时间 序列数掘库系统、文本和多媒体数掘库系统、异种和遗产数据库系统、基于w w w 全球信 息系统。 虽然这样的数据库或信息存储需要复杂的机制，以便有效地存储、检索和更新大量复 杂的数掘，它们也为数据挖掘提供了肥沃的土壤，提出了挑战性的研究和现实问题。 2 3 数据挖掘的分类 数掘挖掘涉及的学科领域和方法很多，有多种分类法，根掘挖掘任务，可分为分类或 预测模型发现、数掘总结、聚类、关联规则发现、依赖关系或依赖模型发现、异常和趋势 发现等。根据挖掘对象分，有关系数据库、面向对象数据库、空间数掘库、时念数掘库、 文本数掘库、多媒体数据库、异构数掘库、遗产数掘库以及w e b 。根掘挖掘方法，可分为 机器学习方法、统计方法、神经网络方法和数据库方法。机器学习包含归纳学习方法、基 于案例学习、遗传算法等。统计方法包含回归分析、判别分析、聚类分析、探索性分析等。 神经网络方法包含i j 向神经网络、自组织神经网络等。数据库方法主要是多维数掘分析方 法，另外还有面向属性的归纳方法。 1 关联分析 关联分析( a s s o c i a t i o na n a l y s i s ) 发现关联规则，这些规则展示属性一值频繁地在给定 数据集中一起出现的条件。关联分析广泛用于购物篮或事务数掘分析。更形式地，关联规 则是形如x jy ， 即“4 以寸b i 玩”的规则， 其中， 4 ( i ( 1 ，研”，b u l ，刀) ) 是属性一值对。关联规则xj y 解释为“满足x 中条件的数 掘库元组多半也满足y 中条件”。 第9 虹 信息i ：稃人学硕十学仿论文 近年柬，已经提出了许多有效的关联规则挖掘算法。关联规则挖掘在以下章节中详细 讨论。 2 分类和预测 分类( c l a s s i f i c a t i o n ) 是这样的过程，它找出描述并区分数据类或概念的模型( 或函数) ， 以便能够使用模型预测类标记未知的对象类。导出模型是基于对训练数掘集( 即其类标记 已知的数据对象) 的分析。 分类可以用来预测数掘对象的类标记。然而，在某些应用中，人们可能希望预测某些 空缺的或不知道的数据值，而不是类标记。当被预测的值是数值数据时，通常称之为预测 ( p r e d i t i o n ) 。尽管预测可以涉及数掘值预测和类标记预测，通常预测限于值预测，并因此 不同于分类。预测也包含基于可用数据的分布趋势识别。 3 聚类分析 聚类( c l u s t e r i n g ) 用于从数掘集中找出相似的数掘并组成不同的组。与分类和预测不 同，聚类分析数据对象，而不考虑已知的类杯记。一般情况下，训练数掘中不提供类标记， 因为不知道从何丌始。聚类，可以用于产生这种标记。对象根据最大化类内的相似性、最 小化类日j 的相似性的原则进行聚类或分组。即对象的簇( 聚类) 这样形成，使得在一个簇 中的对象具有很高的相似性，而与其他簇中的对象很不相似。所形成的每个簇可以看作一 个对象类，由它可以导出规则。聚类也便于分类编制，将观察到的内容组织成类分层结构， 把类似的事件组织在一起。 4 孤立点分析 数掘库中可能包含一些数掘对象，它们与数掘的一般行为或模型不一致。这些数据对 象是孤立点( o u t l i e r ) 。大部分数据挖掘方法将孤立点视为噪声或异常而丢弃。然而，在一 些应用中( 如欺骗检测) ，罕见的事件可能比正常出现的那些更有趣。孤立点数据分析称 作孤立点挖掘。 孤立点可以使用统计试验检测。它假定一个数掘分却或概率模型，并使用距离度量， 至q 其他聚类的距离很大的对象被视为孤立点。基于偏差的方法通过考察一群对象主要特征 上的差别识别孤立点，而不是使用统计或距离度量。 5 演变分析 数掘演变分析( e v o l u t i o na n a l y s i s ) 描述行为随时问变化的对象的规律或趋势，并对其 建模。尽管这可能包括时间相关数掘的特征化、区分、关联、分类或聚类，这类分析的不 第1 0 虬 信息i ：稃人学硕十学付论文 同特点包括时h j 序列数掘分析、序列或周期模式匹配和基于类似性的数掘分析。 2 4 数据挖掘的主要问题 数掘挖掘的主要问题，包括挖掘方法、用户交互、性能和各种数据类型。介绍如下： 1 挖掘方法和用户交互问题 这反映所挖掘的知识类型、在多粒度上挖掘知识的能力、领域知识的使用、特定的挖 掘和知识显示。 在数据库中挖掘不同类型的知识：由于不同的用户可能对不同类型的知识感兴趣， 数据挖掘系统应当覆盖范围很广的数掘分析和知识发现任务，包括数掘特征化、区 分、关联、分类、聚类、趋势和偏差分析以及类似性分析。这些任务可能以不同的 方式使用相同的数掘库，并需要丌发大量数掘挖掘技术。 多个抽象层的交互知识挖掘：由于很难准确地知道能够在数据库中发现什么，数据 挖掘过程应当是交互的。对于包含大量数据的数掘库，应当使用适当的抽样技术， 进行交互式数掘探查。交互式挖掘允许用户聚焦搜索模式，根掘返回的结果提出和 精炼数掘挖掘请求。特殊地，类似于o l a p 在数掘立方体上做的那样，应当通过交 互地数据空日j 和知识空b j 下钻、上卷和转轴柬挖掘知识。用这种方法，用户可以与 数掘挖掘系统交互，以不同的粒度和从不同的角度观察数掘和发现模式。 结合背景知识：可以使用背景知谚 或关于所研究领域的信息来指导发现过程，并使 得发现的模式以简洁的形式在不同的抽象层表示。关于数掘库的领域知识，可以帮 助聚焦和加快数据挖掘过程。 数据挖掘查询语言和特定的数据挖掘：关系查询语言允许用户提出特定的数据检索 查询。这种语言应当与数据库或数掘仓库查询语言集成，并且对于有效的、灵活的 数掘挖掘是优化的。 数据挖掘结果的表示和显示：发现的知识应当用高级语言、可视化表示或其他表示 形式表示，使得易于理解，能够直接被人们使用。这要求系统采用有表达能力的知 识表示技术，如树、表、规则、图、图表、交叉表、矩阵或曲线。 处理噪声和不完全数据：存放在数掘库中的数掘可能反映噪声、异常情况或不完全 的数据对象。这些对象可能搞乱分析过程，导致数据与所构造的知识模型过分适应。 这需要处理数掘噪声的数掘清理方法和数掘分析方法，以及发现和分析异常情况的 孤立点挖掘方法。 第l l 贞 信息i 群人学硕十学位论文 模式评估兴趣度问题：对于给定的用户，许多模式不是有趣的，它们表示公共 知识或缺乏新颖性。使用兴趣度度量，指导发现过程和压缩搜索空b j ，是又一个活 跃的研究领域。 2 性能问题 这包括数掘挖掘算法的有效性、可伸缩性和并行处理。 数据挖掘算法的有效性和可伸缩性：对于大型数掘库，数据挖掘算法的运行时间必 须是可预计的和可接受的。从数据库角度，有效性和可伸缩性是数掘挖掘系统实现 的关键问题。 并行、分布式和增量挖掘算法：这些算法将数掘划分成各部分，这些部分可以并行 处理，然后合并每部分的结果。增量算法与数据库更新结合在一起，而不必重新挖 掘全部数据。这种算法渐增地进行知识更新，修证和加强先前业已发现的知识。 3 关于数据库类型的多样性问题 关系的和复杂的数据类型的处理：由于关系数掘库和数掘仓库已经广泛使用，对它 们丌发有效的数据挖掘系统是重要的。然而，其他数据库可能包含复杂的数掳：对象、 超文本和多媒体数据、空间数掘、时间数掘或事务数掘。由于数据类型的多样性和 数据挖掘的目标不同，指望一个系统挖掘所有类型的数据是不现实的。为挖掘特定 类型的数据，应当构造特定的数掘挖掘系统。这样，对于不同类型的数掘，我们可 能有不同的数据挖掘系统。 由异种数据库和全球信息系统挖掘信息：局域网和广域网连接了许多数掘源，形成 了庞大的、分布式的和异种的数掘库。从具有不同数掘语义的结构化的、半结构化 的非结构化的不同数据源发现知识，对数掘挖掘提出了巨大的挑战。数掘挖掘可以 帮助发现多个异种数掘库中的数掘规律，这些规律多半难以被简单的查询系统发现， 并可以改进异种数据库的信息交换何互操作性。w e b 挖掘发现关于w 曲内容、w e b 使用、w e b 动态情况的有趣知识，已经成为数掘挖掘的一个非常具有挑战性的领域。 以上问题是数掘挖掘技术未来发展的主要需求和挑战。在近来的数掘挖掘研究和丌发 中，一些挑战业已受到一定程度的关注，并考虑到了各种需求，而另一些仍处于研究阶段。 然而，这些问题将继续刺激进一步的研究和改进。 笫1 2 贞 信息i 稃人学硕十学俯论文 第三章关联规则 关联规则挖掘发现大量数掘中项集之间有趣的关联或相关关系。从大量商务事务记录 中发现有趣的关联关系，可以帮助许多商务决策的制定，如分类设计、交叉购物和贱卖分 析。 关联规则的数掘挖掘在商业等领域的成功应用，使它成为数掘挖掘中最成熟、最主要、 最活跃的研究内容。 3 1 关联规则挖掘的基本概念 定义3 - 1 关联规则挖掘的数据集记为d ( 一般为事务数掘库) ，d = t l ，t 2 ，t k ， t i i ，= ，f 2 ，f 。) ，( k _ 1 ，2 ，n ) 称为事务( t r a n s a c t i o n s ) ，( m = 1 ，2 ，p ) 称 为项( i t e m ) 。 定义3 - 2 设，= ，f 2 。厶 是d 中全体项组成的集合，i 的任何子集x 称为d 中的项集 ( i t e m s e t ) ，l x l = k 称集合x 为k 项集( k - l t e m s e t ) 。设和x 分别为d 中的事务和项集， 如果x ，称事务包含项集x 。每一个事务有一个唯一的标识符，称为t i d 。 定义3 - 3 数掘集d 中包含项集x 的事务数称为项集x 的支持数，记为盯，。项集x 的支持度记为s u p p o r t ( x ) ： s u p p o r t ( x ) 2 尚x l o o ( 或s u p p o r t ( x ) 2 尚) ( 3 - 1 ) 其e f l o l 是数据集d 的事务数，若s u p p o r t ( x ) 不小于用户指定的最小支持度( m i n s u p p o r t ) ， 则称x 为频繁项集，简称频集( 或大项集) ，否则称x 为非频繁项集，简称非频集( 或小 项集) 。 定理3 - 1 设x 、y 是数掘集d 中的项集： ( 1 ) 若x y ，则s u p p o r t ( x ) s u p p o r t ( y ) 。 ( 3 - 2 ) ( 2 ) 若彳y ，如果x 是非频集，则y 也是非频集。 ( 3 ) 若x r ，若y 是频集，则x 也是频集。 定义3 4 若x 、y 为项集，且x n y = ，蕴涵式z j y 称为关联规则，x 、y 分别 称为关联规则x j y 的前提和结论。项集u y 的支持度称为关联规则x j y 的支持度， 记作： s u p p o r t ( jjr ) ，s u p p o r t ( 工jy ) = s u p p o r t ( z u y ) ( 3 - 3 ) 关联规则xjy 的置信度记作，c o n f i d e n c e ( xjy ) ： 第1 3 吐( 信息j 稃人宁硕十学付论文 c o n f i d e n e e ( x = ，y 1 ：s u p p o r t ( x u y ) 1 0 0 ( 3 4 ) s u p p o r t ( x ) 通常用户根掘挖掘需要指定的最小置信度记为m i n c o n f i d e n c e 。 定义3 - 5 若s u p p o r t ( xjy ) m i n s u p p o r t ，且c o n f i d e n c e ( x 辛y ) _ m i n c o n f i d e n c e ，称 关联规则x j y 为强规则，否则称关联规则彳j y 为弱规则。 关联规则挖掘的任务就是要挖掘出d 中所有的强规则，强规则x jy 对应的项集 u y 必定是频集( 由定义3 5 和定义3 3 可知) ，由式( 3 2 ) 和式( 3 4 ) 可知，频集( x u y ) 导出的关联规则x j y 的置信度可由频集x 和( x u ，) 的支持度计算。因此，可以把关联 规则挖掘划分为以下两个予问题： ( 1 ) 根掘最小支持度找出数据集d 中的所有频繁项集； ( 2 ) 根掘频繁项集和最小冒信度产生关联规则。 关联规则挖掘的基本模型如图3 1 所示。 图3 - 1 关联规则挖掘的基本模型 图3 1 中d 为数掘集，a l g o r i t h m l 为频繁项集的搜索算法，a l g o r i t h n 一2 为关联规则产 生算法，r 为挖掘出的关联规则集合。用户通过指定的m i n s u p p o r t 、m i n c o n f i d e n c e 分别与 算法a l g o r i t h m - l 、a l g o r i t h n - 2 交互，并通过与r 的交互对挖掘结果进行解释和评价。 关联规则挖掘算法主要考虑的问题有以下两个： ( 1 ) 减少i 0 操作。关联规则挖掘的数掘集有时可达g b 甚至t b 数量级，频繁的 i o 操作必将影响关联规则的挖掘效率，减少i o 操作的方法主要是减少扫描数掘集d 的 次数。 ( 2 ) 降低需要计算支持度的项集( 常称之为候选项集) 的数量，使其与频繁项集的 数量接近。候选项集数量的降低可以节省为处理部分候选项集所需的计算时| 、b j 和存储空 日j 。 第1 4 贝 信息i ：拌人学硕+ 学付论文 3 2 关联规则挖掘的分类 事实上，关联规则有许多种。根掘下面的标准，关联规则有多种分类方法： 1 根据规则中所处理的值类型 如果规则考虑的关联是项的在与不在，则它是都尔关联规则( b o o l e a na s s o c i a t i o nr u l e ) 。 例如，规则( 3 5 ) 是由购物篮分析得到的布尔关联规则。 c o m p u t e rjf i n a n c i a l _ m a n a g e m e n t _ s o f t w a r e s u p p o r t = - 2 ，c o n f i d e n c e = 6 0 】 ( 3 5 ) 如果规则描述的是量化的项或属性之i 日j 的关联，则它是量化关联规则( q u a n t i t a t i v e a s s o c i a t i o nr u l e ) 。在这种规则中，项或属性的量化值划分为区b j 。下面的规则( 3 6 ) 是量 化关联规则的一个例子，其中，x 是代表顾客的变量。 a g e ( x , 3 0 3 9 ”) i n c o m e ( x , 4 2 k 4 8 k ”) b u y s ( x , h i g h r e s o l u t i o n 一丁y ”) ( 3 - 6 ) 注意，量化属性a g e 和i n c o m e 已离散化。 2 根据规则中涉及的数据维 如果关联规则中的项或属性每个只涉及一个维，则它是单维关联规则 ( s i n g l e _ d i m e n s i o n a la s s o c i a t i o nr u l e ) 。这罩，( 3 5 ) 式可以写作 b u y s ( x , c o m p u t e r ”) jb u y s ( x , f i n a n c i a l m a n a g e m e n t s o f t w a r e ”) ( 3 - 7 ) 是单维关联规则，因为它只涉及一个维b u y s 。如果规则涉及两个或多个维，则它是多维关 联规则( m u l t i d i m e n s i o n a la s s o c i a