（计算机应用技术专业论文）频繁模式挖掘算法研究.pdf

频繁模式挖掘算法研究 摘要 频繁模式挖掘是数据挖掘领域的一个基本问题，研究内容一般包括项目 集合、项目序列和时间序列等各种数据中的频繁模式挖掘。其方法被广泛应 用于许多其它数据挖掘任务中，如关联规则、分类和聚类、周期分析、相似 性查询等等。由于问题本身的基础性和内在复杂性，频繁模式挖掘方法成为 许多研究者关注的课题。 本文对频繁模式挖掘的算法进行了研究。重点研究了以下几个方面的频 繁模式挖掘算法问题：项目集合的完全频繁模式和部分频繁模式挖掘算法； 项目序列中的w e b 频繁路径挖掘算法；时间序列的频繁模式挖掘算法等。本 文研究内容和创新工作主要包括以下几个方面： 对频繁模式挖掘算法中常用的数据结构f p - t r e e 进行了深入的研究，提出 了多种f p - t r e e 的新操作方法，包括f p - t r e e 的拆分、合并、投影等操作，使 f p - t r e e 在频繁模式挖掘算法中得到更加灵活的运用，从而有利于提高算法的 效率。 提出了在项目集合中挖掘频繁模式的f p - d f s 算法和f i p t 算法。前者用 于完全频繁模式挖掘，后者用于部分频繁模式挖掘。f p - d f s 算法以f p - t r e e 为基本数据结构，但不再使用条件模式基递归地构造f p - t r e e ，而是通过使用 本文提出的f i - t r e e 的新操作方法，以及新的搜索策略和剪枝策略，提高算法 的搜索效率，并且减少了对内存的占用。f i p t 算法的特点是将概念格与 f i - t r e e 结合起来，通过使用本文提出的f p - t r e e 的新操作方法提高概念格的 更新效率，解决了批处理大量事务时的效率问题，而生成的概念格又可用于 增量挖掘 对于项目序列的频繁模式挖掘，重点研究了其中的w e b 频繁访问路径挖 掘问题，提出了基于网页模糊分类的w e b 事务识别方法，并在此基础上提出 了一种挖掘频繁访问路径的高效混合式算法w d h p 。w d h p 算法继承了d h p 算法使用h a s h 树过滤候选集以及裁剪数据库的基本方法，当数据库被逻辑裁 剪到一定程度时，便将数据库以f p - t r e e 的方式存储于内存，并在内存中完成 后继的挖掘，既减少了内存占用，又提高了算法的运行效率。 对于时间序列的频繁模式挖掘，本文首先分析了时间序列子序列聚类方 哈尔滨工程大学博士学位论文 法中存在的问题，提出了一种基于小波滤波的聚类算法。在此基础上，进一 步提出了基于小波滤波的时间序列频繁模式挖掘算法，f r e q u e n t - w a v e l e t 算 法。f r e q u e n t - w a v e l e = t 算法的基本原理是使时间序列通过多孔平滑滤波器组， 然后对来自多个尺度序列的子序列进行聚类，从而将时间序列的频繁模式挖 掘问题转化为项目序列的频繁模式挖掘问题。由于成功地解决了时间序列频 繁模式挖掘中的平凡相似和时间轴伸缩问题，与同类算法相比，该算法能够 更有效地发现时间序列中的频繁模式。 关键词：频繁模式挖掘；f p - t r e e , 频繁访问路径；小波变换 频繁模式挖掘算法研究 a b s t r a c t f r e q u e n tp a t t e r nm i n i n gi sa b a s i cp r o b l e mo ft b ed a t am i n i n ga r e a , a n di t s r e s e a r c hi n c l u d e sf r e q u e n tp a t t e r nm i l l i n go fv a r i o u sd a t as u c ha si t e ms e t ，i t e m s e q u e n c ea n dt i m es e r i e se t c i t sm e t h o d sa r cw i d e l yu s e di no t h e rd a t am i n i n g a r e a s ，s u c ha sa s s o c i a t i o nr u l e ，c l a s s i f i c a t i o na n dc l u s t e r i n g ，p e r i o d i ca n a l y s i s ，a n d s i m i l a r i t yq u e r ye t c t h et o p i co ff r e q u e n tp a r e mm i n i n gh a sa t t r a c t e dm o r ea n d n l 哦r e s e a r c h e r s a t t e n t i o nb e c a u s eo f i t sb a s i cn a t u r ea n di n n e rc o m p l e x i t y t l l i sd i s s e r t a t i o nm a k e sar e s e a r c ho nm g o f i t h m so ff r e x l u e n tp a t t e r nm i n i n g , a n df o c u s e do nt h ef o l l o w i n ga s p e c t s ：m m la n dp a r t i a lf r e q u e n tp a r e mm i n i n go f i t e ms e t ；f r e q u e n tw e ba c c e s sp a t hm i n i n g ；a n df r e q u e n tp a t t e r nm i n i n go ft i m e s e r i e s 1 1 艟m a j o rc o n t r i b u t i o n so f t h i sd i s s e r t a t i o na sf o l l o w i n g ： b ym a k i n gad c 印r e s e a r c ho nf p - t r e e ，w h i c hi sak i n do fd a t as t m c t i l 佗 f r e q u e n t i yu s e di nf r e q u e n tp a t t e r nm i n i n ga l g o r i t h m , s e v e r a ln o v e lp r o c e s s m e t h o d sa r cp r o p o s e d , i n c l u d i n gd i s a s s e m b l e ，m e r g i n g ，a n dp r o j e c t i o no ff p - t r e e b yu s i n gt h e s e n o v e lp r o c e s sm e t h o d sf l e x i b l yi n f r e q u e n tp a r e r n m i n i n g a l g o r i t h m , t h ee f f i c i e n c yo f t h ea l g o r i t h m c a nb ei m p r o v e d t w om g o r i t h m s , f p - d f sa n df i p t ，a r cp r o p o s e df o ri t e ms e tf r e q u e n t p a t t e r nm i n i n g 1 1 l ef o r m e ri sa na l g o r i t h mf o rt o t a lf i e q u e n tp a r e mm i n i n g 。a n d t h el a t e ri sf o rp a r t i a lf r e q u e n tp a t t e r nm i n i n g f p d f st a k e sf p - t r e ea si t sb a s i s d a t as t r u c t u r e ，b u tn ol o n g e rc o n s t r u c t sf p - t r e er e e u r s i v e l yb yu s i n gc o n d i t i o n p a t t e mb a s e , n e v e r t h e l e s st h ea l g o r i t h mi m p r o v e si t ss e a r c h i n ge f f i c i e n c y 。a n d d i m i n i s h e si t sm a i nm e m o r ys p a c eo c c u p a t i o n , b yu s i n gt h en o v e lp r o c e s s m e t h o d so f f p - u e e ，n o v e ls e a r c h i n gs t r a t e g y ，a n dn o v e lp r u n i n gs t r a t e g yp r o p o s e d b yt h i sd i s s e r t a t i o n t h ec h a r a c t e r i s t i co ff i p ti st oc o m b i n eg a l l i a sl a t t i c ew i t h f p - t r e e ，w h i c hi m p r o v e st h ee f f i c i e n c yo fg a l l i a s l a t t i c em o d i f i c a t i o nb y a p p l y i n gt h en o v e lp r o c e s sm e t h o d s o ff p - t r e ep r o p o s e db yt h i sd i s s e r t a t i o n , e n d s o l v e st h ee f f i c i e n c yp r o b l e mo fh - a n s a c t i o u sb a t c hp r o c e s s t h ec o n s t r u c t e d l a t t i c ec a nb eu s e di ni n c r e m e n t a l l i i l i n g f o rt h ec a s eo ff r e q u e n tp a r e mm i n i n go fi t e ms e q u e n c e ，t h ed i s s e r t a t i o ni s f o c u s e do ns o l v i n gt h ep r o b l e mo ff r e q u e n tw e ba c c e s sp a r e mm i n i n g an o v e l 哈尔滨工程大学博十学位论文 w e bt r a n s a c t i o nm o d e li sp r o p o s e d t h e nan o v e lh y b r i da l g o r i t h mf o rw e ba c c e s s p a t t e r nm i n i n gn a m e dw d h p i sp r o p o s e db a s e d0 1 1t h i sm o d e l ，d h pc a r r i e st h e i d e a so fd h pt of i l t e rc a n d i d a t es e ta n dp r u n ed a t a b a s e ，l l e nt h ed a t a b a s eh a s b e e np r u n e dt oap r o p e rs i z e ，i ti ss t o r e di nm a i nm e m o r yb yc o n s t r u c t i n gf p - t r e e ， a n dt h e nt h ec o n s e c u t i v es t e p so f t h ea l g o r i t h ma l ee x e c u t e di nm a i nm e m o r y ，b y w h i c hr e d u c e st h eo c c u p a t i o no fm a i nm e m o r ys p a c ea n di m p r o v e st h ee x e c u t i v e e f f i c i e n c yo f t h ea l g o r i t h m f o rt h ec a s eo ff r e q u e n tp a t t e r nm i n i n go ft i m es e r i e s ，t h ed i s s e r t a t i o nf i r s t l y a n a l y s i st h ee x i s t i n gp r o b l e mo fs u b s e q u e n c ec l u s t e r i n g ，t h e np r o p o s e san o v e l c l u s t e r i n ga l g o r i t h mb a s e do nw a v e l e tf i l t e r f u r t h e r m o r e ，an o v e la l g o r i t h mb a s e d o nw a v e l e tf i l t e rf o rf r e q u e n tp a r e m m i n i n go ft i m es e r i e s ，f r e q u e n t w a v e l e t ，i s p r o p o s e d t h eb a s i ci d e ao ff r e q u e n t - w a v e l e ti st op a s st i m es e r i e st h r o u g ht h e a t r o u ss m o o t hf i l t e r ss e t , a n dt h e nc l u s t e rt h ed e r i v e ds u b s e q u e n c e s ，s ot h e p r o b l e mo ff t sm i n i n gi sc o n v e r t e dt ot h ep r o b l e m o f f i sm i n i n g t h ea l g o r i t h m s u c c e s s f u l l ys o l v e st h ep r o b l e m so ft r i v i a ls i m i l a r i t ya n dt i m ea x es t r e t c h i n go f t i m es e r i e sf r e q u e n tp a t t e r nm i n i n g ，s oc o m p a r e d 诵t ho t h e rs i m i l a ra l g o r i t h m s ， t h ea l g o r i t h mc a n b em o r ee f f e c t i v et of i n df r e q u e n tp a t t e r n si nt i m es e r i e s k e yw o r d s ：f r e q u e n tp a r e mm i n i n g ；f p - t r e e ；f r e q u e n ta c c e s sp a t h ；w a v e l e t t r a m f o r m a t i o n 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导下， 由作者本人独立完成的。有关观点、方法、数据和文献的引 用已在文中指出，并与参考文献相对应。除文中已注明引用 的内容外，本论文不包含任何其他个人或集体已经公开发表 的作品成果。对本文的研究做出重要贡献的个人和集体，均 已在文中以明确方式标明。本人完全意识到本声明的法律结 果由本人承担。 第1 章绪论 第1 章绪论 数据挖掘( d a mm i n i n g ) 是数据库技术与人工智能技术相结合的产物， 是一门新兴的数据分析技术，目前已成为数据库研究、开发和应用最活跃的 分支之一。频繁模式挖掘是数据挖掘中的一项基础性的工作，它是关联规则 挖掘的一个关键步骤，也可以应用于诸如分类、聚类、预测、相似模式查找 和周期模式挖掘等数据挖掘任务中。自从a g r a w a l 等人提出关联规则发现算 法之后，该问题得到了众多学者的广泛研究，人们尝试从各种途径出发解决 频繁访问模式挖掘的效率问题，提出了许多形形色色的算法，并且不断有新 的研究成果出现【1 l 。本章首先对数据挖掘技术进行了简单概述，介绍了频繁 模式挖掘的的基本概念，重点介绍了频繁模式挖掘的研究现状与成果应用， 最后介绍了本文的主要研究内容和结构安排。 1 1 选题的研究背景与研究意义 计算机通信技术的快速发展和软件技术的广泛应用使人们积累了大量的 数据，而计算机硬件技术的不断进步又使大规模数据的集中存储成为可能。 但是随之而来的是另外一个问题：如何从这些杂乱的数据中获取有用的信息 和知识。 上世纪7 0 年代以后关系数据库技术日渐成熟，使得人们得以将大量的数 据有效地组织和存储起来。但是随着数据积累的不断增长，人们不再满足于 从数据的简单查询和统计分析中获得少量信息，人们迫切需要透过数据表面 去挖掘蕴含于其中的丰富知识。数据挖掘之所以引起人们的日益关注，原因 就在于它是分析海量数据的强有力的工具。数据挖掘满足了人们对海量数据 进行更深层次分析的需要，不仅提高了人们对于海量数据的理解能力，而且 可以透过数据表面提取更多有价值的信息和知识，这些信息可以广泛应用于 商务管理、生产控制、市场分析和科学研究等领域。 频繁模式挖掘是数据挖掘中的一项基础性的工作，它是关联规则挖掘的 一个关键步骤，也可以应用于诸如分类、聚类、预测等数据挖掘任务中。为 了发现大型超市中顾客购买行为之间的有趣联系，a g r a w a l 于1 9 9 4 年开创性 地提出了关联规则挖掘问题，并提出了著名的a p r i o r i 算法，用频繁项集产生 哈尔滨丁程大学博士学位论文 关联规则，发现顾客购买的不同商品之间的联系，分析顾客的购物习惯，帮 助零售商制定营销策略。1 9 9 5 年，为描述同一顾客在多次购物所购商品之间 可能存在的某种关联关系，a g r a w a l 又发表了序列模式挖掘算法。近年来， i n t e m e t 的飞速发展为人们提供了浩如烟海的信息资源，研究人员将传统的数 据挖掘技术与w e b 技术相结合，对原始的w e b 数据进行挖掘，而w e b 频繁 访问模式挖掘作为w e b 挖掘的一个重要组成部分，对于网站的优化设计以及 电子商务的智能化都具有十分重要的实践意义。此外，近年来对时间序列频 繁模式挖掘的研究也取得了相当大的进展。时间序列数据存在于社会的各个 领域，如科学研究记录、气象观测数据、股票数据等，传统时间序列分析的 任务仅仅是为了对系统整体行为进行预测和控制，而时间序列的频繁模式挖 掘则可以对时间序列局部特征进行分析，发现经常出现的变化模式，对于时 间序列的预测、相似性挖掘、周期模式挖掘等应用都具有十分重要的意义。 经过十几年的研究，已经奠定了较成熟的频繁模式挖掘方法的理论基础。 本文围绕频繁模式挖掘算法的效率问题展开研究。重点研究了以下几个问题： 将对f p - 订e e 的研究成果应用于项目集合以及w e b 路径的频繁模式挖掘，利 用小波滤波解决时间序列的子序列聚类问题，并将其应用于时间序列的频繁 模式挖掘。在技术路线上，一是通过对f p t r e e 的进一步研究，提出关于f p - t r e e 的更多新操作方法；二是将f p - 仃e e 的新操作方法引入项目集合以及w e b 路 径的频繁模式挖掘算法，设计出过程简单而又高效的挖掘算法；三是将小波 滤波方法引入时间序列的子序列聚类，将时间序列转化为项目序列后应用 f p - t r e e 的新操作方法从时闻序列中发现频繁模式。理论和实验表明，这些方 法不仅过程简单，而且具有较好的时空效率，可广泛应用于与频繁模式相关 的诸多领域中，具有广泛的应用前景。 1 2 数据挖掘概述 数据挖掘就是从大量数据中挖掘有价值的信息和知识。与统计分析、人 工智能、机器学习不同的是，数据挖掘所要处理的是大量的未经加工的原始 数据1 2 l 。从本质上来说，数据挖掘是一个对原始大量数据进行加工、分析、 抽取的过程，目的是获得有价值的信息和知识【3 j 。 与数据挖掘有着同样内涵的另外一个概念是知识发现( 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 ，简称k d d ) 。一种观点认为数据挖掘是知识发现过程 2 第1 章绪论 中的一个基本步骤( 如图1 1 所示) ；另一种观点则将数据挖掘视为知识发 现的同义词【4 l 。持前一种观点的人将知识发现分成如下几个步骤： ( 1 ) 需求分析：不同领域的用户对数据挖掘有着不同的需求，分析用户的 需求是为了确定挖掘的技术路线并使挖掘的最终结果符合用户的期望，为此 需要了解原始数据所涉及的应用领域和相关知识，掌握用户的需求和目标， 并制定挖掘计划。 ( 2 ) 数据清理：大型数据库或数据仓库中往往包含有大量不完整的、含噪 声的和不一致的数据，如果不对这些数据加以处理，就有可能使数据挖掘过 程陷入混乱，导致不可靠的输出。数据清理是对原始数据的初步加工，目标 是识别原始数据中的孤立点、消除噪声、填充空缺的值，并纠正数据中的不 一致。 ( 3 ) 数据筛选：参与挖掘任务的数据集的规模对于挖掘过程和结果都有重 要的影响。数据太少往往不具有代表性，会影响挖掘结果的正确性；数据太 多难免包含一些与挖掘任务不相干的数据，会影响挖掘过程的效率。数据筛 选就是将来自多个数据源的数据组合在一起，根据一定的标准从中检索或分 析出任务相关的数据，并将筛选出的数据变换成适合挖掘的统一形式。 ( 4 ) 数据挖掘：这是知识发现全部过程中的基本步骤，是对海量数据进行 加工和分析的过程。从本质来说，数据挖掘的基本任务是从大规模数据集中 发现有价值的模式，如关联规则、分类模式、序列模式等等。数据挖掘是1 个智能分析过程，所使用的方法和手段涉及机器学习、神经网络、遗传算法、 序列模式分析，以及其它一些相关领域的知识。 ( 5 ) 知识表示：数据挖掘系统应当能够将所得知识直观、形象地展示给用 户，如采用表、饼图、直方图、判定树、曲线等来表示。此外用户常常会发 现系统将一大堆无用的结果展示出来，只有少数有用的知识却被淹没在其中。 因此系统应该能够在将挖掘结果提交给用户之前先进行筛选。最后，数据挖 掘系统还应当是一个能够与用户交互的系统，允许用户将修正后的参数输入 系统，开始新一轮的挖掘。 数据挖掘涉及多种学科的相关技术，包括数据库技术、概率与数理统计、 机器学习、高性能计算、数据可视化等。其中数据库技术是数据挖掘的基础， 因为数据库为数据挖掘提供数据来源，而数据挖掘则为数据库提供智能化的 分析手段。与机器学习等其他人工智能技术相比，数据挖掘有其自身的特点： 哈尔滨工程大学博士学位论文 首先，数据挖掘通常要处理大规模的数据集，即数据挖掘的目标是从数据库 的海量数据中发现有价值的知识，因此，算法的可扩展性通常是衡量数据挖 掘算法的主要指标。第二，数据挖掘系统具有多种不同的挖掘工具，可以从 同一海量数据集中发现不同类型的知识。通常用户不知道他们的数据中什么 类型的模式是有趣的、有价值的，因此想尽可能搜索多种不同的模式，这就 要求数据挖掘系统能够挖掘多种不同类型的模式，以适应不同用户的需求或 不同的应用。第三，数据挖掘系统能够发现各种粒度( 即不同抽象层次) 的 知识，通过用户与数据挖掘系统之间的交互，由用户输入参数来指导或聚焦 有趣模式的搜索。用户的输入参数对于数据挖掘的结果和质量会产生重要的 影响，这就要求用户具备一定的数据挖掘知识。第四，数据挖掘通常并不产 生精确的结果，而是基于概率的统计规律。这意味着有些被发现的模式并非 对数据库中的所有数据都成立，通常每个被发现的模式带有一个确定性或“可 信性”度量。 数据源 口竺曰 数据獯 口h a l - 理臼 图1 1k d d 处理过程 f i 9 1 1p r o c e s so f k d d 数据挖掘的任务是从指定的数据中发现各种类型的有价值的知识。从总 体上看，数据挖掘的任务可以分为两类：描述和预测。描述性挖掘任务刻画 数据库中数据的一般特性，而预测性任务在当前数据上进行推断，以进行预 测。描述和预测又体现为多种不同的具体挖掘任务，而且在数据挖掘领域不 断有新的任务被提出。j i a w e ih a r t 在g d a t am i n i n g ：c o n c c p t & t e c h n i q u c s 中 将目前的数据挖掘任务分为以下几类【5 l ： ( 1 ) 概念描述 数据可以由一定的概念和类来抽象表示人们对其关心的那部分性质。概 念描述即是用汇总的、简洁的、准确的方式描述每个类和概念。概念描述可 以通过数据特征化或数据区分来实现。概念特征化是目标数据的一般特征或 特性的汇总，而数据区分是将目标类对象的一般特征与一个或多个对比类对 4 第1 章绪论 象的一般特征比较。 ， ( 2 ) 关联规则挖掘 关联规则挖掘的目标是从指定数据中发现关联规则。关联规则反映不同 属性值集合在指定数据集中同时出现的可能性。关联规则挖掘通常分为两个 步骤进行。第一步，从指定数据集中找出所有出现频率超过最小支持度阙值 的频繁模式；第二步，从频繁模式中得到关联规则。第一步是关联规则挖掘 中最困难、最关键的一步。关联规则挖掘最初用于购物篮分析，目前己广泛 应用于各个领域。 ( 3 ) 分类和预测 分类是用一个函数或模型，把各个类标号未知数据项映射到预定义的类 中，从而得到这些数据的类标号。分类挖掘的关键是导出用于分类的函数或 模型，人们对于这一问题的研究由来已久，提出了许多用于导出分类模型的 方法，包括决策树分类方法、统计方法、神经网络方法，粗糙集( r o u g hs e t ) 方法等。预测分析是对于类标号未知数据项预测其可能的类标号，也可以通 过预测分析估计出一组数据中的某些丢失数据的可能值或一个数据集合中某 种属性值的分布情况。一般是利用数理统计的方法，找出所要预测的属性并 根据相似数据的分析估算属性值的分布情况。 ( 4 ) 聚类分析 聚类分析同样是将类标号未知数据项进行归类的过程。聚类分析与分类 挖掘不同，分类挖掘的各种类标号是已知的，分类挖掘的目标是将各种己知 的类标号合理地分配给类标号未知的数据项，而在聚类分析中类标号是未知 的，事先并不知道指定的数据集会被划分为哪几个类，甚至可能不知道类标 号的数目，聚类分析的目标是按照一定的原则形成类标号，并将指定的数据 集划分到各个类中，这个原则就是聚类分析的结果应使每个类内部对象间的 相似性尽可能大，而不同类对象间的相似性尽可能小。在具体实现中，一般 用计算对象属性的距离( 欧几里德距离、曼哈顿距离等) 来体现对象间的相 似度。 ( 5 ) 孤立点分析 数据库中包含的一些数据对象可能与数据的般行为不一致，或者不遵 循总的数据模型，这样的数据称为孤立点。在通常的数据挖掘应用中需要将 孤立点排除掉，然而在一些特殊的应用( 如欺诈检测) 中，孤立点反而成为 哈尔滨工程大学博士学位论文 挖掘的目标。孤立点分析大致有统计、基于距离和基于偏差三种方法。 ( 6 ) 趋势分析 趋势分析描述对象行为随时间变化的趋势和规律，它是对时态数据挖掘 的总称。趋势分析自然包括概念描述、关联规则、分类与预测、聚类以及孤 立点分析针对时态数据的应用，但它也包括时态数据挖掘特有的任务，如周 期模式匹配和相似性查找等。 数据挖掘技术的应用领域非常广泛，在政府管理决策、商业运营决策、 科学研究和工业企业决策支持等各个领域都能应用数据挖掘技术。其中比较 成功的应用领域包括： ( 1 ) 商业管理 通过对顾客交易的数据进行分析可以有效地对顾客群体进行划分，预测 不同群体的购买行为和需求大小，进行有针对性的营销设计。运用模式识别 和聚类分析的方法，通过提取客户资料，对客户和它们对几种不同商品的兴 趣进行聚类分析，可以发现潜在客户的具体特征，从而对这些潜在客户进行 相应的促销宣传1 6 - 7 1 。 ( 2 ) 网站管理 网站是电子商务的基础平台，大型网站每日都有数以万计的访问量，如 何合理安排网站组织结构，是一个非常困难的任务。通过应用数据挖掘可以 从用户的访问信息中发现有价值的知识，从而指导网站设计者更新网站结构 与内容，更好地与客户进行交流，发现潜在客户，改进客户关系管理，提高 网络营销效率，而且可以进一步实施针对个性化用户或用户群的访问界面， 从而开展有针对性的电子商务以满足访问者的需求f 8 _ 9 1 。 ( 3 ) 信息安全 在电子商务中，电子交易是其中的一个重要组成部分，而信用卡又在电 子交易中扮演了重要的角色。通过运用数据挖掘中的离群数据挖掘方法或聚 类方法总结正常交易行为和诈骗行为之间的关系，获取诈骗行为的一些特性。 利用这些知识去分析和判断现有交易中具有诈骗的倾向，如发现某项业务符 合这些特征时，可以向决策人员提出警告i l o j 。 ( 4 ) 金融证券 数据挖掘已广泛地应用于银行和金融市场。金融市场中的数据挖掘主要 应用于改进预测市场波动的能力、建立预测模型以识别出历史上曾引起市场 6 第1 章绪论 波动的因素所具有的模式、进行投资分析增加收入、以及减少商业欺诈所造 成的损失【i l - 1 2 l 。典型的应用有：贷款偿还预测和客户信用政策分析； 股票预测；客户保持；实时营销。 ( 5 ) 科学研究 利用数据挖掘技术可以处理极大量的数据，例如在生物d n a 分析、新 药的药理分析和治疗机理和天文学研究等领域都可以找到数据挖掘技术的应 用空间【1 3 l 。 1 3 频繁模式挖掘的基本概念 频繁模式挖掘最初是作为关联规则挖掘的一个子问题被提出来的，而关 联规则挖掘又源于购物篮分析的需要。大型超市通过日常经营积累了大量的 销售数据，企业经营者希望通过分析这些数据，得到一些有价值的规则，例 如：通过分析发现了这样的关联规则，面包j 牛奶( 8 0 ) ，意思是8 0 的 顾客在购买面包的同时也会购买牛奶。这样的关联规则可以为企业的产品定 价、促销以及商场布局等经营决策提供有力支持。 设，： i l ，i 2 ，i 。) 是由m 个不同的项( i t e m ) 所组成的集合，每一个项 目可以是一种商品或一个网页。不同的项目所组成的集合称为项集，由k 个 项目所组成的集合称为卜项集。d 代表一个事务数据库，简称为数据库。d 中的一条事务r 是，中一组项目的集合，即7 c ，口丁代表顾客的一次购买行。 为中所购买的商品的集合或用户一次浏览的网页的集合。每个事务有一个标 识符，称作r 谢。一条事务r 包含项集x 当且仅当x _ c 扎 项集x 在d 中的覆盖( c o v e r ) 是由d 中包含项集x 的所有事务的，耐组成 的集合： e o v e r ( x , d ) = t i d 陡t i d 0 - 0 项集工在d 中的支持度( s u p p o r t ) 是d 中包含项集戈的事务数占d 中事务 总数的比例： s u p p o r t ( x , d ) = c o v _ e r ( 鬲x 一, d ) i ( 1 - 2 ) l j i 因为i d l 的值是一定的，为了方便有时也用l e o v e r ( x , d ) l 表示支持度。满足 最小支持度阈值的项集被称为频繁项集。最小支持度阙值a 曲是由用户指定 的一个阈值，呸。曲s l ，代表用户认可的频繁项集的最低出现频率。 7 哈尔滨工程大学博士学位论文 关联规则是形如x j y 的蕴涵式，其中x hy c 厶并且彳n 产矿。 关联规则由支持度和可信度进行度量。支持度表示规则出现的频度，可信度 表示规则的强度。 s u p p o r t ( x = y , d ) = s u p p o r t ( x uy , d ) = ic o v e r ( 再x 汀u y , d ) i ( i - 3 ) l l 关联规则j jy 的可信度( c o n f i d e n c e ) 是d 中同时包含项集x 和项集y 的 事务数占包含项集x 的事务数的比例： c o m q d e n e e j 只d ) s u p p o r t ( x oy , d ) ( i - 4 ) s u p p o r t ( x ，d ) 给定项集，事务数据库d ，以及最小支持度o 。和最小可信度t 曲，关 联规则挖掘就是找出d 中所有满足最小支持度和最小可信度的关联规则： r ( d ，a ，y 产 x 兮yi x , r 厶x ny - _ ，s u p p o r t ( x y d ) g m i n ， c o n f i d e n c e ( x j 巧d ) t 曲 在频繁模式挖掘或关联规则挖掘中谈到数据库时通常是指关系数据库中 的一个二维表。如表1 1 代表了一个象征性的事务数据库。 例1 1 在表1 1 代表的象征性事务数据库d 中，卢 a ，b ，c ，d ，e ) ，如果 设定a 血- 3 ，则挖掘得到的频繁模式及其支持度如表1 2 所示。 表1 1 事务数据库表1 2 频繁模式及其支持度 t a b l e l 1t r a n s a c t i o n d b t a b l e l 2 f r e q u e n t p a t t e r n sa n d t h e i rs u p p o r t s t i d b c d e l x置x 2xxx x 3zzx 4i xz工 5x xz 6 zi i 7zz 8工 频繁模式f 支持度频繁模式1 支持度 5柏3 b6配5 c6曲3 d4c 3 “3口3 皿4o4 篮4曲c3 b 3 b o3 频繁模式挖掘只需用户指定一个参数。幽，而关联规则挖掘则需要用户 指定两个参数a 。和t 曲。显然，如果关联规则x y 成立，则项集x u 】，必 是频繁的，反之则不然，所以关联规则挖掘的过程通常分为两个大的阶段： 第一阶段找出所有满足最小支持度阈值的频繁项集；第二阶段在频繁项集中 找出所有满足最小可信度阈值的关联规则。关联规则挖掘通常要处理规模庞 8 第1 章绪论 大的数据集，在大数据集中搜索频繁项集需要大量的时间和空间，而在频繁 项集中搜索关联规则要简单得多。因此在关联规则挖掘的过程中，第一阶段 是解决问题的关键。目前绝大多数关于关联规则挖掘的算法都主要解决第一 阶段问题，即如何高效率地挖掘频繁项集的问题。 频繁模式挖掘的问题可以看作是一个搜索问题，目标是在数据库空间中 以尽可能高的效率搜索频繁模式。由于数据库的规模通常很大，频繁模式挖 掘算法需要在一个庞大的空间中进行搜索，因此如何提高算法的效率始终是 频繁模式挖掘算法要解决的一个主要问题。频繁模式挖掘的搜索空间并不等 同于数据库空间，数据库空间是物理数据空间，而搜索空间是逻辑数据空间。 在一些层次挖掘算法中由于要多次扫描数据库，使得算法的搜索空间大于数 据库空间，而在一些采用抽样技术和剪枝策略的算法中，算法搜索的数据可 能只是数据库中数据的一部分，算法的搜索空间可能会小于数据库空间。频 繁模式挖掘算法的搜索空间大小取决于许多因素，主要有： ( 1 ) 数据库纪录的数目：以纪录为单位的数据库规模是决定搜索空间大小 的最主要因素。在已有的频繁模式挖掘算法中，大多数算法可以找出数据库 中所有的频繁模式，这要求算法对数据库中的每条纪录至少作一次搜索。虽 然一些算法采用在数据库中抽样的技术，但这些算法不能保证得到所有的频 繁模式。 ( 2 ) 数据库包含的项目数：数据库纪录的属性即是数据库记录包含的项 目。数据库中可能的频繁模式数与数据库记录包含的项目数之间呈指数关系。 对于项目集合的关联规则而言，设数据库记录包含的项目数为i 卅，则数据库 中可能的频繁模式数为2 ，而对于序列模式而言，可能的频繁模式数日会更 多。因此，随着数据库记录包含的项目数的增加，频繁模式挖掘算法的搜索 空间可能会以指数方式增长。 ( 3 ) 数据库记录和频繁模式的长度：在数据库记录数目一定的前提下，数 据库记录和频繁模式的平均长度越长，频繁模式挖掘算法的搜索空间就越大， 尤其是对于层次搜索算法( 如类a p f i o r i 算法) ，算法搜索数据库的次数直接 取决于数据库记录的最大长度。 ( 4 ) 数据库的类型：尽管没有严格的界定方式，在频繁模式挖掘的实践中， 人们仍然将数据库分为两种，即稠密数据库和稀疏数据库。一般认为，在数 据库中记录数目一定的前提下，如果数据库包含的项目数较少，且数据库记 9 哈尔滨工程大学博十学位论文 录和频繁模式的平均长度也较短，则这样的数据库属于稠密数据库，反之， 则是稀疏数据库。在稀疏数据库中搜索要比在稠密数据库中搜索困难得多。 ( 5 ) 搜索的策略：对于同样的数据库，算法采用的策略方式不同，搜索的 空间也有很大差别。采用层次搜索的方式进行搜索通常要产生候选模式集， 需要多次搜索数据库，数据库中的一条纪录被多次搜索，搜索的相对空间较 大，而基于内存的算法通常不产生候选模式集，一般只需要对数据库进行一 二次的搜索，搜索的效率较高。 频繁模式挖掘根据处理的数据集的性质和挖掘结果的不同有不同的分类 方式： ( 1 ) 根据处理数据的类型不同，频繁模式挖掘可以分为布尔型频繁模式挖 掘和数值型频繁模式挖掘。布尔型频繁模式挖掘处理的数据都是离散的枚举 类型数据，数据被限制在一个枚举集合中取值，枚举集合中的元素称为项目， 项目被包含于一个模式中，或者不被这个模式包含，因此项目对于模式来说 是布尔型数据。例如某商场发现，在顾客的购买模式中，( 面包，牛奶) 的 支持度为1 0 ，超过了5 的最小支持度阈值，因此是布尔型频繁模式。现 实世界中数据库存储的数据不全是布尔型的数据，绝大多数数据是连续的数 值型数据，如工资、年龄、商品价格等。布尔型频繁模式的相关概念通常不 能直接应用于数值型频繁模式的挖掘，例如某个大型企业将( 年龄= 2 0 ，月收 , k = 2 0 0 0 ) 作为一个模式，希望知道该模式在企业员工中的支持度，结果发现 该模式的支持度为0 ，因为根本没有员工的月收入正好等于2 0 0 0 。在挖掘数 值型频繁模式时，通常要将数值型数据离散化，从而将数值型频繁模式挖掘 的问题转化为布尔型频繁模式挖掘问题。 ( 2 ) 根据处理数据是否有序，频繁模式挖掘可以分为项目集合的频繁模式 挖掘和时态数据的频繁模式挖掘。项目集合中元素之间是无序的，因此在项 目集合的频繁模式挖掘过程中，可以根据需要对项目集合中的元素排序，如 按项目的支持度降序排序。时态数据本身是有序的数据，它的数据之间存在 着某种顺序，这种顺序关系可以是时间上的先后关系，也可以是与时间无关 的某种顺序。在对时态数据进行挖掘时，必须考虑时态数据之间的顺序关系。 时态数据是对具有时间关系的一大类数据的统称，可以是各种类型的数据， 如数值型数据、枚举型数据、布尔型数据、事务性数据等。数值型时态数据 又称为时间序列( t i m es e r i e s ) ，如证券市场上股票价格的历史数据、商业零 1 0 第1 苹绪论 售行业中某种商品销售额的历史数据，以及天气预报中某地区每天气温气压 的历史数据等。枚举型时态数据则通常被称为序列( s e q u e n c e ) ，如用户浏览 某网站时的路径、用户购买商品构成的序列，以及d n a 中基因排列构成的 序列等。 ( 3 ) 根据模式中数据的抽象层次，可以分为单层频繁模式挖掘和多层频 繁模式挖掘。在单层的频繁模式挖掘中，所有的变量都没有考虑到现实的数 据是具有多个不同的层次的；而在多层的频繁模式挖掘中，对数据的多层性 已经进行了充分的考虑。例如：( 计算机，打印机) 和( m m 计算机，s o n y 打印机) 分别是2 个不同层次上的频繁模式，前者是对后者的高层次上的抽 象，后者则是前者在低层次上的细节表现。 ( 4 ) 根据模式中数据元素的维数，可以分为单维频繁模式挖掘和多维频 繁模式挖掘。在单维模式中，模式中的数据元素是单维的，而在多维模式中， 模式中的数据元素是多维的，例如在时间序列数据库中发现的频繁模式是单 维的，在图像数据库中发现的频繁模式是2 维的，在空间数据库中发现的频 繁模式则是3 维的。 ( 5 ) 根据频繁模式挖掘的结果集，可以分为完全频繁模式挖掘和部分频 繁模式挖掘。完全频繁模式挖掘得到数据库中包含的全部频繁模式，在最小 支持度阈值较小的情况下，结果集的规模可能会很大，使用户无法从中得到 有价值的信息。部分频繁模式挖掘得到一个比较小的结果集。目前部分频繁、 模式挖掘主要有最大频繁模式挖掘和频繁闭项集挖掘。如果模式p 是最大频 繁模式，则包含p 的任何模式都是非频繁的模式。而如果模式p 是频繁闭项 集，则包含p 的任何模式的支持度都小于p 的支持度。显然，频繁闭项集是 频繁模式的子集，而最大频繁模式又是频繁闭项集的子集。表1 3 为频繁模 式挖掘常用分类的表示。 表1 3 频繁模式挖掘分类的表示 分类表示含义分类表示含义 f i频繁项集f i s频繁项目序列 f c i频繁闭项集f t s