（计算机应用技术专业论文）基于二维表的关联规则挖掘研究.pdf

中国民航大学硕士学位论文 摘要 关联规则挖掘是数据挖掘的一个重要内容，计算频繁项集是关联规则挖掘中的关键 技术和步骤。这方面的算法主要代表有两类：a p f i o f i 类算法、f p g r o w t h 类算法。a p f i o f i 类算法缺陷之一是需要多次重复扫描数据库；f p g r o w t h 类算法是基于内存的，这类算 法缺陷之一是当项目比较平衡或支持度阈值较低时，无法将树形结构一次性全部装入内 存。这两类算法在频繁项集的计算过程中，仅计数量不计内容，即支持频繁项集的事务 集合被舍弃了。 针对上述问题提出了基于二维表的关联规则挖掘方法，算法的中心思想是基于前缀 迭代计算，包括静态计算和动态计算两种，并借助n e t 开发环境建立了实验平台。该 算法将原事务数据经过压缩处理之后，以字符串的形式存储在二维表中，避免了重复扫 描数据库。该算法优势主要有两方面：一是挖掘结果中包含支持满足m i n s u p 频繁项集 的事务集合，即保留频繁项集的时序特征。二是基于前缀的迭代思想保证在挖掘过程中， 组合模式的计算量达到最小，如在相同的实验条件下，对主对角线上元素值为0 ，其他 元素为l 的2 0 2 0 阶矩阵，f p g r o w t h 算法将无法运行。之后将此算法应用于航空事故 数据分析，得到了良好的实验结果。 最后指出了该算法的不足之处，并对该课题的发展前景和探索的方向进行了展望。 关键词数据挖掘；关联规则；前缀迭代；频繁项集计算；时序特征 中国民航大学硕上学位论文 a b s t r a c t m i n i n gf o ra s s o c i a t i o nr u l e s i sa ni m p o r t a n tc l a s so fd a t am i n i n g t h eo v e r a l l p e r f o r m a n c eo fm i n i n ga s s o c i a t i o nr u l e si s d e t e r m i n e db yf i n d i n ga l lf r e q u e n ti t e m s e t s c l a s s i cm i n i n ga l g o r i t h m s ，s u c ha sa p r i o r i ，f p - g r o w t ha r ep r e s e n t e d a p r i o r im a ys u f f e rf r o m n o n t r i v i a lc o s t s ：i tm a yn e e dt or e p e a t e d l ys c a nt h ed a t a b a s ea n dc h e c kal a r g es e to f c a n d i d a t e sb yp a t t e r nm a t c h i n g f p - g r o w t hi sam a i nm e m o r y b a s e da l g o r i t h m i t s d i s a d v a n t a g ei s ：w h e nt h ed a t a b a s ei sl a r g e ，i t sf p t r e ec a n n o tf i ti nm a i nm e m o r y t h e e x i s t i n ga l g o r i t h m sn e g l e c tt r a n s a c t i o nf o rs u p p o r t i n gf r e q u e n ti t e m s e t s a c c o r d i n gt ot h el i m i t a t i o no ft h ee x i s t i n ga l g o r i t h m ，t h ep a p e rp u t sf o r w a r da r i t h m e t i cn a m e d b a s e do np r e f i x - a l t e m a t i o nf o rc a l c u l a t i n gf r e q u e n tp a t t e r n s ，i n c l u d i n gs t a t i ca n dd y n a m i c ， b a s e do n2 - d i m e n s i o nt a b l e t h ea l g o r i t h mc o m p r e s s e dt r a n s a c t i o nd a t a b a s ei n t od a t a b a s e a v o i d i n gr e p e a t e d l ys c a nt h ed a t a b a s e b e c a u s er e s u l t si n c l u d ec o n c r e t et r a n s a c t i o n sc a ng e t i n t e r e s t i n gf r e q u e n ti t e m s e t st h r o u g hs e t t i n gt i m eb a s e f o rm e e t i n gm i n _ s u p sf r e q u e n t i t e m s e t sc a na n a l y s i st i m ea t t r i b u t et og e ts t e a d ya n du n s t e a d yc l a s s e s i nt h es a m ec o n d i t i o n s ， t h e2 0 x 2 0m a t r i xh a sm a i nd i a g o n a le l e m e n t s0a n dt h eo t h e r s1 ，f p - g r o w t ha l g o r i t h mw i l l n o tb ea b l et oh a n d l e t h i sa r i t h m e t i ci su s e dt oa n a l y z et h ed a t af r o ma v i a t i o na c c i d e n t a tl a s t ，w ed i s c u s st h ed i s a d v a n t a g eo ft h ea l g o r i t h m w i t ht h ed e e pr e s e a r c ho ft h i s p r o j e c t ，t h ea l g o r i t h mw i l lh a v eab r i g h tf u t u r 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 ；p r e f i x - a l t e m a t i o n ； c a l c u l a t i n g f r e q u e n tp a a e m ；t i m ea t t r i b u t e i i 中国民航大学学位论文独创性声明 本人声明所旱交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所 知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果， 也不包含为获得中国民航大学或其它教育机构的学位或证书而使熠过的材料。与我一同- t 作的同志 对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。 研究生签名： 啦日期：鎏星：“ 中国民航大学学位论文使用授权声明 中国民航人学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论文的复印件 和电子文档，可以采刚影印、缩印或其他复制手段保存论文。本人电子文档的内容和纸质论文的内 容相一致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布( 包括刊登) 论文的全 部或部分内容。论文的公布( 包括刊登) 授权中国民航大学研究生部办理。 研究生妣蠡登翩虢址日期：型：丛 中国民航大学硕上学位论文 第一章数据挖掘概述 上个世纪中期，数据库和信息技术得到了很大的发展，从原始的文件处理演化到复 杂、功能强大的数据库系统。到上世纪七十年代以后，数据库系统的研究和开发已经从 层次和网状数据库系统发展到关系数据库开发系统。同时，数据建模、组织以及相关的 索引技术和存储技术也得到了巨大的发展。数据的访问也由于数据库系统的开发及其优 良的性能变得方便、灵活。联机事务处理( o l t p ) 将查询看作只读事务，对于关系技 术的发展和广泛地将关系技术作为大量数据的有效存储、检索和管理的主要工具做出了 重要贡献【l 训。上世纪八十年代以来，数据库技术的特点是广泛接受关系数据库技术，同 时研究和开发新的、功能强大的数据库系统。由于数据库的广泛应用，数据积累越来越 多。为了便于对历史数据的存储和访问，一种新的数据组织形式数据仓库应运而生， 它包括数据清理、数据集成和联机分析处理( o l a p ) ，主要用于分析静态的历史数据， 支持决策管理。o l a p 是一种分析技术，具有汇总、合并和聚集功能，以及从不同的角 度观察信息的能力。 数据收集速度的加快和数据的积累，使得数据变得非常丰富。海量的数据存放在大 型和大量的数据库或数据仓库中，没有强有力的分析工具，理解这些数据已经远远超出 了人的能力，“数据丰富，但信息贫乏就是用来描述这种情况的。需要是发明之母。 人们对海量数据和大型数据库分析方法的需要，导致了数据挖掘技术的出现。 1 1 数据挖掘历史与定义 1 1 1 数据挖掘发展历史 数据挖掘( d a t a m i n i n g ，简称为d m ) 一词是在1 9 8 9 年8 月于美国底特律市召开的 第十一届国际联合人工智能学术会议上正式形成1 2 5 j 的。许多人把数据挖掘视为另一个常 用的术语一数据库中的知识发现( k n o w l e d g ed i s c o v e r y i nd a t a b a s e ，简称为k d d ) 的同义词，常常混用。而另一些人只是把数据挖掘视为k d d 的一个基本步骤。1 9 9 5 年， 第一届知识发现和数据挖掘国际学术会议在加拿大蒙特利尔召开【2 6 1 ，从此，每年主办一 次k d d 国际学术会议，将k d d 和d m 方面的研究推向了高潮，从此，“数据挖掘 一词开始流行。会议规模由原来的专题讨论会发展到国际学术大会，人数由二三十人上 升到七八百人，论文收录比例从2 ：1 发展到3 0 8 ：4 4 ，研究重点也逐渐从发现方法转向系 统应用，并且注重多种发现策略和技术的集成，以及多种学科之间的相互渗透。 数据库、人工智能、信息处理、知识工程等领域的国际学术刊物也纷纷开辟了k d d 专题或专刊，其中i e e e 的k n o w l e d g ea n dd a t ae n g i n e e r i n g 会刊领先在1 9 9 3 年出版了 中国民航大学硕士学位论文 k d d 技术专刊，所发表的5 篇论文代表了当时k d d 研究的最新成果和动态，较全面的 论述了k d d 系统方法论、发现结果的评价、k d d 系统设计的逻辑方法，集中讨论了鉴 于数据库的动态性冗余、高噪声和不确定性与其它传统的机器学习、专家系统、人工神 经网络、数理统计分析系统的联系和区别，以及相应的基本对策。6 篇论文摘要显示了 k d d 在从建立分子模型到设计制造业的具体应用。 我国的数据挖掘研究开始于9 0 年代中期，到9 0 年代中后期，初步形成了知识发现 和数据挖掘的基本框架。自9 0 年代中期一批研究成果( 学术论文) 逐渐发表在计算 机学报、计算机研究与发展、软件学报、人工智能与模式识别等刊物上 研究重点也正在从发现方法转向系统应用，并且注重多种发现策略和技术的集成，以及 多种学科之间的相互渗透。但是基本上还是以学术研究为主，实际应用上处于起步阶段。 与国外相比，国内对数据挖掘与知识发现的研究稍晚。1 9 9 3 年国家自然科学基金首次支 持对该领域的研究项目 2 5 o 目前，国内的许多科研单位和高等院校竞相开展数据挖掘的 基础理论及其应用研究。 1 1 2 数据挖掘定义 数据挖掘是数据库技术、人工智能、机器学习和统计学等学科相结合的产物。 从技术角度看，数据挖掘( d a t am i n i n g ) 就是从大量的、不完全的、有噪声的、模 糊的、随机的实际应用数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有 用信息和知识的过程【3 “一】。 与数据挖掘相近的同义词数据融合、数据分析和决策支持等。这个定义包括好几层 含义：数据源必须是真实的、大量的、含噪声的；发现的是用户感兴趣的知识：发现的 知识要可接受、可理解、可运用；并不要求发现放之四海皆准的知识，也不是要去发现 崭新的自然科学定理和纯数学公式，更不是什么机器定理证明。实际上，所发现的知识 都是相对的，是有特定前提和约束条件的，面向特定领域的，同时还要能够易于被用户 理解。最好能用自然语言表达所发现的结果。 从商业角度看，数据挖掘是一种新的商业信息处理技术，其主要特点是对商业数据 库中的大量业务数据进行抽取、转换、分析和其他模型化处理，从中提取辅助商业决策 的关键性数据【6 j 。因此，数据挖掘可以描述为：按企业既定业务目标，对大量的企业数 据进行探索和分析，揭示隐藏的、未知的或验证已知的规律性，并迸一步将其模型化的 先进有效的方法。 1 2 数据挖掘系统 完整的知识发现的过程一般由以下步骤组成：数据清理( d a t ac l e a n i n g ) ，数据集成 ( d a t ai n t e g r a t i o n ) ，数据选择( d a t as e l e c t i o n ) ，数据变换( d a t at r a n s f o r m a t i o n ) ，数据挖 2 中国民航大学硕士学位论文 图1 1 知识发现过程 i 删 目_ j 掘( d a t am i n i n g ) ，模式评估( p a t t e r n se v a l u a t i o n ) ，知识表达( p a t t e r n sp r e s e n t a t i o n ) 等，如 图1 1 所示。典型的数据挖掘系统一般由以下部分组成：数据库、数据仓库或其他信息 库( d a t a b a s e o rd a t aw a r e h o u s e ) ，数据库或数据仓库服务器( d a t a b a s eo rd a t aw a r e h o u s e s e r v e r ) ，知识库( k n o w l e d g eb a s e ) ，数据挖掘引擎( d a t am i n i n ge n g i n e ) ，模式评估模块 ( p a t t e r ne v a l u a t i o n ) 图形用户界面等( g r a p h i c a l u s e ri n t e r f a c e ) ，系统结构如图1 2 所示。 1 3 数据挖掘方法与分类 1 3 1 数据挖掘方法 数据挖掘与传统的数据分析( 如查表、报表、联机应用分析) 的本质区别是数据挖 掘是在没有明确假设的前提下去挖掘信息、发现知识。数据挖掘所得到的信息应具有先 前未知、有效和可实用三个特征【| n 引。 先前未知的信息是指预先未曾预料到的，既数据挖掘是要发现那些不能靠直觉发现 的信息或知识，甚至是违背直觉的信息或知识，挖掘出的信息越是出乎意料，就可能越 有价值。 一一般而言，数据挖掘包括为已有的数据套用现有的数据模型，或从中找出蕴含的模 式。由于数据挖掘的分析对象是海量数据，因此挖掘算法需要考虑计算机内存空间的大 小，充分利用内存空间，使得算法能具有足够高的效率；还需要考虑数据库大小的不同， 使算法不仅能使用小型的数据库，也能适用于大型数据库。现阶段，大多数数据挖掘都 = 一 i ， 理 百 处 一 预 一 据数 _ 2 ) 得大小。基本思想：当扫描事务数据库，由候选k 项集产生频繁k 项集的时候，同时 产生每个事务的( k + 1 ) 项子集，并把它们散列到散列表的不同桶中，增加桶的计数， 在下次产生k + l 一项集的时候，可以根据散列表和最小支持度排除一些无意义的候选项 集- o 这种技术当k = 2 时特别有效。它的关键是构造一个有效的散列函数。 ( 2 ) 基于事务压缩的方法 基于事务压缩( t r a n s a c t i o nr e d u c t i o n ) 优化方法通过减少不必要的事务来减小扫描 的事务数据库的大小，以提高挖掘的效用。一个基本的原理就是当一个事务部不包含任 何k - 项集的时候，它必然不可能包含任何( k + 1 ) 一项集，从而我们可以将这些事务删 除，因为在为产生( k + 1 ) 项集而扫描事务数据库的时候已经不再需要它们了。 ( 3 ) 基于划分的优化方法 基于划分( p a r t i t i o n i n g ) 的优化方法采用对原数据库进行两遍扫描的技术。在第一 遍，首先将事务数据库划分为n 个非重叠的部分，每个部分的最小支持度等于整个事务 数据库的最小支持度与该部分的事务数之积。对于每一个部分，找出该部分的频繁项集， 称作局部频繁项集。局部频繁项集可能不是整个事务数据库的频繁项集，整个事务数据 库的任何一个频繁项集必须作为局部频繁项集至少出现在一个部分中。这样，把所有局 部频繁项集的集合作为事务数据库的候选项集，称作全局候选项集。再次扫描数据库， 根据全局候选项集和实际最小支持度确定全局频繁项集。每部分的大小和划分的数目由 是否能够把该部分放入内存来确定。 ( 4 ) 基于采样的优化 基于采样( s a m p l i n g ) 的优化方法是在一个给定数据库的随机样本中进行挖掘，这 种方法牺牲了精确性以换取有效性，样本的大小由是否能够把它放入内存来决定。样本 中的频繁项集不一定是数据库中的频繁项集，而且，数据库中的频繁项集不一定出现在 样本的频繁项集中，因此，应该使用比事务数据库最小支持度低的支持度值来搜索样本 中的频繁项集，之后，通过数据库的其余部分再来计算每个项集的实际频繁度。当效用 是决定因素的时候，采样方法比较合适。 ( 5 ) 基于动态项集计数的优化方法 基于动态项集计数( d y n a m i ci t e m s e tc o u n t i n g ) 的优化方法将数据库划分为标记开 始点的块，算法可以在任何开始点添加新的候选项集。该技术动态的评估已被计数的所 有项集的支持度，如果一个项集的所有自己已被确定为频繁的，则添加它作为新的候选 中国民航人学硕士学位论文 项集。该方法对数据库扫描次数比a 叫o r i 算法少。 上面我们介绍的都是基于a p r i o r i 的频繁项集的计算方法。即使进行了优化，但是 a p r i o r i 方法一些固有的缺陷还是无法克服： ( 1 ) 可能产生大量的候选集。当长度为1 的频繁项集有1 0 0 0 0 个的时候，长度为2 的候选集个数将会超过1 0 m 。还有就是如果要生成一个很长的规则的时候，要产生的中 问元素也是巨大的。 ( 2 ) 无法对稀有信息进行分析。由于频繁项集使用了参数m i n s u p ，所以就无法对 小于m i n s u p 的事件进行分析；而如果将m i n s u p 设成一个很低的值，那么算法的效率就 成了一个很难处理的问题。 2 2 3f p - - g r o w t h 算法 由于依赖于候选项集产生频繁项集的理论所开发的算法具有先天的弱点，使得在基 于a p r i o r i 算法基础上开发的应用没有实质性的突破。而由j i a w r e ih a n 2 】等提出的一种新 的算法理论，用一种压缩的数据结构( f pt r e e ) 可存储关联规则挖掘所需的全部数据信 息，通过对源数据的两次扫描，将数据信息存在这种结构里，避开了产生候选项集的步 骤，极大地减少了数据交换和频繁匹配的开销。这就是所谓无候选项集产生算法 ( f r e q u e n tp a t t e m sg r o w t h ，f p _ g r o w t h ) 。 1 。f pg r o w t h 算法思想 采取分治策略。将提供频繁项集的数据库压缩到一棵频繁模式树，但仍然保留项集 关联信息；然后，将这种压缩后的数据库分成一组条件数据库，每个关联一个频繁项， 并分别挖掘每个数据库。 2 f pg r o w t h 算法描述 输入：事务数据库d ；最小支持度阈值m i n s u p 。 输出：频繁模式的完全集 方法： ( 1 ) 按以下步骤构造f p 树； 1 ) 扫描事务数据库d 一次。收集频繁项的集合f 和它们的支持度。对f 按支持度 降序排序，结果为频繁项表l 。 2 ) 创建f p 树的根节点，以“n u l l 标记它。对于d 中每个事务t r a n s ，执行： 选择t r a n s 中的频繁项，并按l 中的次序排序。设排序后的频繁项表为 p p 】， 其中p 是第一个元素，而尸是剩余元素的表。调用i n s e r t t r e e ( p p ，t ) 。该过程 执行情况如下。如果t 有子女n 使得n i t e m n a m e = p i t e m n a m e ，则n 的计数增 加1 ；否则创建一个新节点n ，将其计数设置为1 ，链接到它的父节点t ，并且 通过节点链结构将其链接到具有相同i t e m n a m e 的节点。如果尸非空，递归的调 1 2 中国民航大学硕士学位论文 用i n s e r t t r e e ( p ，t ) 。 ( 2 ) f p 树的挖掘通过调用f p - g r o w t h ( f p t r e e ，n u l l ) 实现。该过程实现如下： p r o c e d u r e f p g r o w t h ( t r e e 口) 1 ) i f t r e e 含单个路径pt h e n 2 ) f o r 路径p 中节点的每个组合( 记作) 3 ) 产生模式u 口，其支持度s u p p o r t = 中节点的最小支持度： 4 ) e l s ef o re a c h c t , 在t r e e 的头部 5 ) 产生一个模式= c tu c t f ，其支持度s u p p o r t = s u p p o r t ； 6 ) 构造的条件模式基，然后构造的条件f p - 树t r e e p ； ”7 ) i ft r e e p 矽t h e n 8 ) 调用f p g r o w t h ( t r e e p ，) ；) 3 f pg r o w t h 算法的改进和创新 f pg r o w t h 算法通过如下三方面的改进和创新，脱离了必须产生候选项集的传统方 式，开辟了关联规则挖掘的新思路。 ( 1 ) 它构造了一种新颖的、紧凑的数据结构f pt r e e 。它是一种扩展的前缀树结构， 存储了关于频繁模式数量的重要信息。树中只包含长度为1 的频繁项作为叶结点，并且 那些频度高的节点更靠近树的根节点，因此，频度高的项比那些频度低的项有更多的机 会共享同一个节点。 ( 2 ) 开发了基于f pt r e e 的模式片断成长算法，它从长度为1 的频繁模式开始，只 检查它的条件模式基构建它的条件模式树，并且在这个树上递归的执行挖掘。模式的成 长通过联合条件模式树新产生的后缀模式实现。由于事务处理中的频繁项都对应着频繁 树中的路径进行编码，模式的成长确保了结果的完整性。因此，f p t r e e 算法不像a p r i o r i 类算法那样需要产生再测试。 ( 3 ) 挖掘过程中采用的搜索技术是基于划分的，通过分割再解决的方法，而不是 a p r i o r i 类算法的自下向上的产生频繁模式的集合。它通过将发现长频繁模式的问题转化 成寻找短模式然后再与后缀连接的方法，避免了产生长候选项集。 4 f p g r o w t h 算法的问题 f pg r o w t h 算法在实际应用中仍然面临着许多问题： ( 1 ) 当项目比较平衡或支持度阈值较低时，无法将f pt r e e 一次性全部装入内存， 此时算法不再可行。 中国民航大学硕士学位论文 ( 2 ) 很难实现频繁项集的增量式更新，从而严重限制了该类算法的应用。 2 3 关联规则挖掘 r a k e s ha g r a w a l 等人给出了一个有效的关联规则生成算法。对频繁项x ，设其长度 为k ( x 所包含的元素个数) ，并且假定ycx 且y 囝，即y 是x 的真子集，在上述 假定下，如果c o n f ( yjx l ，) = s ( x ) s ( n m i n c o n f 则生成关联规则yj x y 。 关联规则挖掘问题主要考虑的问题有两个c 2 2 2 3 】：一是减少i o 操作，二是降低需要 计算支持度的项目集( 常称之为候选项目集) 的数量，使其与频繁项集的数量接近。 ”如果要在一项实际应用中挖掘关联规则，应该依照数据挖掘的基本过程来进行，并 注意关联规则挖掘的特点：必要的数据整理和变换、事务数据库的存在形式、选择合适 的挖掘算法和规则的输出的形式和解释。 2 4 小结 本章主要介绍了关联规则挖掘，首先对关联规则的基本概念进行了描述。第二，对 两种经典的频繁模式挖掘算法，即a p r i o r i 、f p g r o w t h 进行了详细的介绍，最后对关联 规则挖掘主要考虑的问题及应用的要点进行了简单介绍。 1 4 中国民航久学硕士学位论文 第三章基于前缀迭代的频繁项集计算 3 1 算法提出的背景 挖掘关联规则主要包含以下两个步骤【1 9 2 m2 1 】：步骤一：找出存在于数据集中的所 有的频繁项集。步骤二：利用上一步得到的频繁项集，产生相应的强关联规则。由于步 骤二中的相应操作极为简单，因此挖掘关联规则的整个性能就是由步骤一中的操作所决 定的。 a p r i o r i 算法采用广度优先的方法枚举项集，按照项有序先挖掘出较短的项集，然后 迭代较长的项集。从k 项集到k + l 项集迭代时，取两个前k 一1 项相同的项集进行连接， 并使得新k + 1 项集的所有k 子集均为频繁的，然后对这样的k + 1 项集计算支持度，非 频繁项集剪枝比较有效。在计算每个项集支持度时，采用扫描原始数据的方法。 影响a p r i o r i 算法效率的两个主要因素：首先是产生的大量候选项集的维护，在内 存中对大量候选项集进行维护和操作处理是低效的，耗费大量时间和空间。其次采用频 繁扫描原始数据计算支持度的方法是低效的。 f p g r o w t h 算法是基于f p t r e e 数据结构进行挖掘，采用深度优先的方法枚举项集， 按照项有序先挖掘出较长的项集。由于f p t r e e 本身表示了原始数据中项之间的所有关 联关系，在计算项集支持度时采用树上的投影方法，得到特定项集下的条件信息。投影 的数据随着项集的增长而变小，使得算法能通过一定的方法在较小的内存中处理。在 f p t r e e 中直接得到了项集的支持度，根据支持度阈值判断非频繁项集，进行剪枝。 f p g r o w t h 算法使用投影的处理方法效率较高，相对于a p r i o d 方法提高了一个数量 级。 现有算法大多从a p r i o r i ，f p g r o w t h 算法的演化而来，这些方法都存在两个问题： 一是只能求得频繁项集数量，结果与事务无关，丢掉了频繁项集的时间属性；二是由于 模式组合爆炸无法适应较大的事务数据处理。对于由频繁项集产生的关联规则而言，不 考虑事务的时序因素显然是脱离了实际问题。就这一点而言，现有的方法对信息处理的 能力与社会信息处理的需求是极不相称的。 对于传统方法的组合爆炸问题，a p r i o r i 算法的问题是需要频繁扫描数据库( 存储于 文件) ；而f p g r o w t h 算法是将数据信息基于前缀的压缩到一棵树上( 存储于内存) ， 不需要扫描数据库。不过当数据项没有前缀时，它所构造的树规模巨大并且在树上挖掘 过程中会组合产生条件模式基。因此，对于具有稠密数据的事务数据库现有的方法很难 完成频繁项集的计算，比如对主对角线为0 的全1 方阵( 2 0 木2 0 ) ，在相同的实验环境 下f p g r o w t h 算法无法运行。正因如此，开发一个基于二维表的实用频繁项集挖掘算法 是十分必要的。本文将给出一个基于二维表的频繁项集计算方法( 简称a m 方法) ，实 中国民航大学硕士学位论文 验表明此方法是十分有效的频繁项集计算方法。 3 2 算法描述 3 2 1 算法涉及的基本概念 设事务数据库的关系模式为r ( 口l ，a 2 ，吗，吼) ，其中，属性的集合为s 。与关联规则 中传统的项目集与项目的定义本质上是相同的。 定义3 1 模式 所有的a i ，口，q 组成事务数据的k - 频繁项集模式。 据此定义，则所有的( 哆，口，) ( f j ) 组成事务数据的2 频繁项集模式，所有的 ( ( q ，a j ) ，a k ) ( i 后) 组成事务数据的3 频繁项集模式。一般地，事务数据的k - 频繁项集 模式( ( 口。，a ：，a k 一。) ，吼) 。所以k 频繁项集模式= ( k l 频繁项集模式a ，属性a ) 。其中， 模式a s ，属性a s 。 定义3 2 前缀 事务数据的k - 频繁项集模式( q ，a 2 ，a k - l ，a k ) ，前缀为( q ，a 2 ，a k 1 ) 。 3 2 2 基于前缀迭代的静态频繁项集计算 1 数据处理 根据完整的知识发现的过程( 数据清理( d a t ac l e a n i n g7 数据集成( d a t ai n t e g r a t i o n ) ， 数据选择( d a t as e l e c t i o n ) ，数据变换( d a t at r a n s f o r m a t i o n ) ，数据挖掘( d a t am i n i n g ) ， 模式评估( p a t t e r n se v a l u a t i o n ) ，知识表达( p a t t e r n sp r e s e n t a t i o n ) 等) ，本节主要介绍数据 处理，将事务数据存储在关系数据库中的一个表，称之为二维表。所用的数据库是 m i c r o s o f t s q l s e r v e r2 0 0 0 。处理的方法通过对表3 1 所示的事务数据库处理的过程 进行说明。 1 6 中国民航大学硕士学位论文 表3 1 事务数据库 t i di t e m t l b , c ，d ，e ，f t 2 a , c ，d ，e ，f t 3 a , b ，d ，e ，f t 4 a , b ，c ，e ，f t 5 a , b ，c ，d ，f t 6 a , b ，c ，d ，e 原事务数据经过数据处理之后将存储在m i c r o s o f ts q ls e r v e r2 0 0 0 的一张表中， 表的结构为： 其中，字段s n u m 为事务数据库中的t i d ，字段m o d e 为模式，字段q ( 0 f 疗) 为项 目，字段s e t p r i 为m o d e 的前缀，字段p r i s e t 为该频繁项集的维数。 数据处理方法：如果项目在记录中出现，则所对应的值为1 ，否则为0 。经过处理 的数据，在s q l s e r v e r2 0 0 0 中就变为如表3 2 所示的一个二维表， 表3 2 处理过的事务数据 s n u mm o d eabcdef s e t p r ip r i s e t 10 1ll1l 2 l 01l1l 3110111 41 1lo1 l 51lllo1 6111 1 l0 2 算法思想 定义3 3 相同矩阵 事务数据库中两个数据项同时为l 的矩阵称之为数据项的相同矩阵。 根据定义，表3 2 所示的事务数据库的相同矩阵如表3 3 所示。实质上，相同矩阵 就为2 频繁项集。其中每行的字段m o d e 值与所对应的列名组成的是频繁项集，所对应 的单元格记录了支持该频繁项集的事务记录号。 1 7 中国民航大学硕士学位论文 表3 3 相同矩阵 s n u mm o d e ab c def s e t p r i p r i s e t 1a3 4 5 62 4562 3 5 62 3 4 62 3 4 52 2b 1 456 1 3 5 61 3 4 6l 3452 3c1 2 5 6l - 2 4 6l 2452 4d1 2 3 61 2 3 52 5e1 2 3 42 例如m o d e = a 时，与b 列组成的是频繁项 a b ，频繁项的维数为p r i s e t 的值为2 ，并 且其支持度为3 ，即所对应的 3 - 4 - 5 的长度，也说明由记录 3 ，4 ，5 ) 支持频繁项 a b ， 以此类推。 以表3 2 所示的事务数据库为例，直观的了解该算法的思路： ( 1 ) 首先，a 分别与其集合内部的b ，e ，d ，e 迭代，得到( a b ，a c ，a d ，a e ) ，其 次，b 与其后的e ，d ，e 迭代得到( b e ，b d ，b e ) ，依此类推，e 与其后的d ，e 迭代得 到( c d ，c e ) 。其中每一个集合迭代直到出现最后一个元素e 为止，得到相同矩阵，如 表3 3 所示。 ( 2 ) 利用以上迭代的结果，a b 与其集合内部的a e ，a d ，a e ( 前缀相同都是a ) 迭 代得到( a b e ，a b d ，a b e ) 。相应的值由 3 - 4 5 - 6 ) 分别与 2 - 4 5 6 ) 、 2 - 3 - 5 - 6 ) 、 2 - 3 - 4 - 6 ) 、 2 3 4 - 5 ) 求交集得n 4 - 5 - 6 ) 、 3 5 6 、 3 - 4 6 、 3 - 4 5 。a b e 再与其集合内部的a b d ， a b e ( 前缀相同都是a b ) 迭代得到( a b e d ，a b e e ) ，同理，以此类推求得其它集合。示 意如图3 1 所示。 图3 1基于前缀迭代的静态频繁项集计算过程 3 算法描述 ”功能：逐层计算频繁项集 输入：处理后的事务数据库 输出：频繁项集 第一步：生成相同矩阵，即2 _ 频繁项集( m i n i n 9 0 3 ) 第二步：迭代计算频繁项集： 生成表m i n i n 9 0 1 ； 暂存k _ 频繁项集 生成表m i n i n 9 0 2 ； 暂存k + 1 一频繁项集 生成表m i n i n 9 0 4 ； 。暂存前缀相同的k _ 频繁项集 生成表r e s u l t ； 初始化为空 r r = m i n i n 9 0 3 的记录个数； 循环：r r ) 0 ( 将m i n i n 9 0 3 的记录追加到r e s u l t ； 将m i n i n 9 0 l 表清空； 为下次循环做准备 将m i n i n 9 0 3 的记录追加到m i n i n 9 0 1 ； 将m i n i n 9 0 3 表清空； 调用c a l f r e q u e n t ( ) 算法； i t = m i m n 9 0 3 的记录个数； ) c a l f r e q u e n t ( ) 算法： 将m i n i n 9 0 1 即k _ 频繁项集按前缀分类并汇总将结果暂存二维数组s e t p r i n u m ； 循环： 根据s e t p r i _ n u m ，从m i n i n 9 0 1 中提取记录放在m i m n 9 0 4 中，即前缀相同 的记录； 接着将m i n i n 9 0 1 中的复制到m i n i n 9 0 4 的记录删除； 计算结果放在m i n i n 9 0 3 中；删除不满足m i n - s u p 的记录 将m i n i n 9 0 2 的记录追加到m i n i n 9 0 3 中； 即k + l - 频繁项集 清空m i m n 9 0 2 ； 清空m i n i n 9 0 4 ； ) 4 算例 如表3 2 所示的事务数据库，第一步得到表3 3 所示的相同矩阵，即2 频繁项集。 则利用上述算法描述进入迭代过程，计算结果如表3 4 - 3 7 所示。 1 9 中国民航人学硕士学位论文 表3 4 第一次迭代结果 s n u m m o d eabcdef s e t p r ip r i s e t 6a b4 5 63 5 63 4 63 4 5a3 7a c2 5 62 - 4 62 4 - 5a3 8a d2 3 62 3 5a3 9a e2 3 - 4a3 1 0b c1 5 61 4 - 61 - 4 - 5b3 1 1b d1 3 61 3 5b3 1 2b e1 3 4b3 1 3c d1 2 6l 一2 - 5c3 1 4c e1 2 4c3 1 5d e1 2 - 3d3 第一次迭代得到的结果：m o d e 依据前缀相同的特点，依次进行连接，而相对应的 值就如上所述取交集得到支持该项集的记录号。 表3 5 第二次迭代结果 s n u mm o d eabcdef s e t p r ip r i s e t 1 6a b c 5 64 64 5a b4 1 7a b d3 63 5a b4 1 8a b e3 4a b4 1 9a c d2 - 6 2 5a c4 2 0 a c e2 - 4a c4 2 1a d e2 3a d4 2 2b c d1 61 5b e 4 2 3b c e1 - 4b e4 2 4b d e1 3b d4 2 5 c d e1 2e d4 第二次迭代得到的结果：m o d e 依据前缀相同的特点，依次进行连接，而相对应的 值就如上所述取交集得到支持该项集的记录号。 、 中国民航大学硕士学位论文 表3 6 第三次迭代结果 s n u mm o d e a bcd ef s e t p r ip r i s e t 2 6a b c d65a b c5 2 7a b c e4a b c5 2 8a b d e3a b d5 2 9a c d e2a c d5 3 0b c d e1b c d5 第二次迭代得到的结果：m o d e 依据前缀相同的特点，依次进行连接，而相对应的 值就如上所述取交集得到支持该项集的记录号。 表3 7 第四次迭代结果 s n u mm o d e abc d ef s e t p r ip r i s e t 3 1a b c d e a b c d 6 迭代结束。 3 2 3 基于前缀迭代的动态频繁项集计算 提出基于前缀迭代的动态频繁项集计算算法的原因是，能否根据前( k 1 ) 个项目 的频繁项集的计算结果，快速的得到k 个项目的频繁项集。根据此想法，提出基于前缀 迭代的动态频繁项集计算。 1 数据处理 本节的数据处理与上节的数据处理方法相同，都是放在s q ls e r v e r 2 0 0 0 中的一张 表中，所用的事务数据库如图3 1 所示，处理后的数据如图3 2 所示。 2 算法思想 根据前( k 1 ) 个项目的频繁项集的计算结果，计算k 个项目的频繁项集。通过寻 找规律，可以发现，由( k - 1 ) 个项目的频繁项集到k 个项目的频繁项集，主要需要做 两方面的工作： “ ( 1 ) 模式的扩展 ( 2 ) 频繁项集的扩展 对如表3 2 所示的事务数据库，首先通过基于前缀迭代的静态频繁项集的计算，得 至l j a ，b ，c ，d ，e ) 的频繁项集，如表3 8 所示。 2 l 中国民航大学硕士学位论文 表3 8 a , b ，c ，d ，e ) 的频繁项集 s n u mm o d eabcde s e t p r i p r i s e t l a3 - 4 5 62 4 5 62 3 5 62 3 _ 4 62 2b 1 456 1 3 5 6 1 3 4 ，62 3c1 2 5 61 2 - 4 62 4d1 2 3 62 5a b4 5 63 5 63 4 6a3 6a c2 5 62 4 6a3 7a d2 3 6a3 8b e 1 5 61 4 6 b3 9b d1 - 3 6b3 1 0c d1 2 6c3 11a b c5 64 6a b4 1 2a b d3 6a b4 1 3a c d2 6a c 4 1 4b c d 1 6 b c 4 1 5a b c d6a b c5 由上图的结果，当动态的增加项目f 后，工作就集中在以下两个方面： ( 1 ) 模式的扩展： a , b ，c ，d ，e ，f ) 的模式= a ，b ，c ，d ，e ) 的模式u 空格，a , b ，c ，a b ，a c ，