（管理科学与工程专业论文）商业数据流频繁模式挖掘算法研究与应用.pdf

浙江工商大学硕士学位论文摘要 商业数据流频繁模式挖掘算法研究与实现 摘要 随着知识经济时代的来临，信息与知识已经成为国家和企业发展 的重要战略资源，是提高一个组织乃至一个国家战略竞争力的核心， 也是实施科学管理与决策的基础。如何获取信息与发现知识，尤其是 如何快速高效地在动态变化和爆炸性增长的海量数据流中获取信息 和发现知识就成了关键性问题。 与传统数据不同，数据流具有大量、快速连续到达、要求快速响 应、一次扫描等特点。而商业数据流除了具备数据流的基本特点外， 还具备连续性、冲突性、时间性、海量性和分布性等特性。因此传统 的数据挖掘技术不能直接应用到商业数据流上。利用有限系统资源对 商业数据流进行快速处理以获取有用信息，为数据挖掘在商业领域的 应用研究带来了新的机遇和挑战。 频繁模式挖掘是数据挖掘领域的一个基本问题，研究内容一般包 括事务、序列、树和图。其方法被广泛应用于许多其它数据挖掘任务 中，如相关性分析，序列周期分析，最大频繁模式，闭合频繁模式， 查询，分类等等。由于问题本身的基础性和内在复杂性，频繁模式挖 掘方法成为许多研究者关注的课题。 本文对商业数据流频繁模式挖掘相关技术进行了研究。重点研究 了以下几个问题：商业数据流的层次维度结构分析及其挖掘系统的研 浙江工商大学硕士学位论文 摘要 究；利用静态前窥树高效挖掘最大频繁模式和闭合频繁模式；利用增 量式挖掘方式和倾斜时间窗口分别挖掘商业数据流中的最大模式和 闭合模式；频繁模式算法在商业领域的实际应用问题等。本文研究内 容和创新工作主要包括以下几个方面： 首先，对数据流挖掘及其模型等相关理论进行研究，总结出目前 该领域的最新研究成果，以期取其之长运用到商业数据流相关任务的 挖掘上。 接着，提炼出商业数据流的概念及特点，分析商业数据流的内容 层次和类型维度结构，并以此构建出商业数据流管理系统b d s m s 。 然后，针对静态商业数据海量等特点，设计并实现最大频繁模式 挖掘算法m f p 和闭合频繁模式算法c f p 。其中采取前馈剪枝、合并等 策略修剪频繁模式树以提高频繁模式构成速度。在此基础上，针对时 间序列模型和收银机模型，改进静态的频繁模式挖掘算法m f p 和 c f p ，分别引入增量式挖掘和倾斜时间窗口得出商业数据流挖掘的单 遍扫描算法s m f p 和s c f p 。 最后，本文将上述算法应用到商业特定领域，设计实现了零售行 业折扣券生成系统，并对其进行实验分析与研究，挖掘数据表明各算 法都具有较高的准确性和时间效率，对商业决策支持具有一定的指导 意义。 关键词：数据挖掘；数据流；频繁模式；最大频繁模式；闭合频繁模 式；增量式挖掘；倾斜时间窗口 浙江工商大学硕士学位论文 t 艇er e s e a r c ha n dr e l i z a t i o no fm l n i n g f a e q u e n tp a t t e r n s0 nb u s i n e s sd a t a s t r a e m s a b s t r a c t w i t ht h ea d v e n to ft h ek n o w l e d g ee c o n o m ye r a , i n f o r m a t i o na n d k n o w l e d g eh a s b e c o m ea l li m p o r t a n ts t r a t e g i cr e s o u r c ea n dt h ec o l ec o m p e t i t i v e n e s s 幻a l l o r g a n i z a t i o na n dan a t i o n ，a n da l s ot h ef o u n d a t i o ni nt h ei m p l e m e n t a t i o no fs c i e n t i f i c m a n a g e m e n ta n dd e c i s i o n - m a k i n g t h e r e f o r e ，h o wt og a i ni n f o r m a t i o na n dd i s c o v e r k n o w l e d g ee s p e c i a l l yi nt h ed y n a m i ca n de x p l o s i v eg r o w i n gd a t as t r e a m sb e c o m et h e k e yi s s u e s 。 d i f f e r e n tf r o mt h et r a d i t i o n a ld a t a ，t h ed a t as t r e a mi sa b o u n d e d ，r a p i d , a n d c o n t i n u o u s 。i na d d i t i o n , t h eb u s i n e s sd a t as t r e a mi sc o n t i n u o u s ，c o n f l i c t , t i m i n g , m a s s i v ea n dd i s t r i b m e d ，s ot r a d i t i o n a ld a t am i n i n gt e c h n i q u e sc a nn o tb e a p p l i e dd i r e c t l yt ot h eb u s i n e s sd a t as t r e a m m a k i n gu s eo f t h el i m i t e ds y s t e m t c s o u l c c st oo b t a i nu s e f u li n f o r m a t i o nf r o mt h eb u s i n e s sd a t as t r e a m sh a sb r o u g h tn e w o p p o r t u n i t i e sa n dc h a l l e n g e sf o rt h ea p p l i c a t i o nr e s e a r c ho f d a t am i n i n gi nb u s i n e s s a r e a s f r e q u e n tp a t e mm i n i n gi sab a s i cp r o b l e mo f d a t am i n i n g , i n c l u d i n gm i n i n g t r a n s a c t i o n s ，s e q u e n c e s ，t r e e sa n dg r a p h s t h ea l g o r i t h mf o ri th a sb e e np r e v a l e n t l y u s e di nm a n yo t h e rd a t am i n i n gt a s k ，s u c ha sa s s o c i a t i o n a n a l y s i s ，s e q u e n c e - p e r i o d s a n a l y s i s ，m a x i m a la n dc l o s e df r e q u e n tp a t e m s ，q u e r ya n dc l a s s i f i c a t i o nt e c h n o l o g yc t e 。 s i n c ei tl a y sg r o u n d w o r kf o ro t h e rp r o b l e ma n di t si n t r i n s i cc o m p l e x i t y , t h ea l g o r i t h m f o rf r e q u e n tp a t e r nm i m i n gh a sb e c o m et h ef o c u so fm a n yr e s e a r c hw o r k e r s 。 浙江工商大学硕士学位论文 a b s t r a c t s o m er e l e v a n tt e c h n i q u e sa b o u tf r e q u e n tp a t t e r nm i n i n gi nt h eb u s i n e s sd a t a s t r e a ma r ea d d r e s s e di nt h et h e s i s ，w h i c hc o v e r st h ea n a l y s i so ft h el e v e la n ds t r u c t u r a l d i m e n s i o n so ft h eb u s i n e s sd a t as t r e a m ，m i n i n gm a x i m a la n dc l o s e df r e q u e n tp a t t e m s b yu s i n gt h es t a t i cg l e a n e dt r e ee f f i c i e n t l y , u s i n gi n c r e m e n t a lm i n i n gm e t h o d sa n dt h e t i l tt i m ew i n d o wr e s p e c t i v e l yt om i n et h em a x i m a la n dc l o s e dp a t t e r n si nt h eb u s i n e s s d a t as t r e a m ，t h ea p p l i c a t i o no ff r e q u e n tp a t t e r na l g o r i t h m si nt h eb u s i n e s sf i e l d 。m a j o r c o n t r i b u t i o n so ft h i st h e s i si n c l u d e ： f i r s t l y ，s t u d yt h er e l e v a n tt h e o r i e so ft h ed a t as t r e a mm i n i n ga n di t sm o d e l ， s u m m a r i z et h el a t e s tr e s e a r c ha c h i e v e m e n t so ft h ef i e l di no r d e rt ou s et h e mi nt h e b u s i n e s sd a t as t r e a mm i n i n gt a s k s s e c o n d l y , e x t r a c tc o n c e p t sa n df e a t u r e so ft h eb u s i n e s sd a t as t r e a m ，a n a l y s et h e c o n t e n th i e r a r c h i c a ls t r u c t u r ea n dt y p ed i m e n s i o ns t r u c t u r ea n du s et h e mt oc o n s t r u c t t h eb u s i n e s sd a t as t r e a mm a n a g e m e n ts y s t e mb d s m s t h i r d l y ，a c c o r d i n gt ot h ec h a r a c t e r i s t i c so fs t a t i cb u s i n e s sd a t a , d e s i g nt h e m a x i m a lf 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 mm f pa n dt h ec l o s e df r e q u e n tp a t t e r n m i n i n ga l g o r i t h mc f p u s et h ef e e d f o r w a r dp r u n i n g ，t h em e r g e rs t r a t e g y t oe n h a n c e t h ec o n s t r u c t i o no ft h ef r e q u e n tp a t t e r n o nt h i sb a s i sa n dr e s p o n s et ot h et i m es e r i e s m o d e la n dt h ec a s hr e g i s t e rm o d e l ，b r i n gi nt h ei n c r e m e n t a lm i n i n ga n dt h ef l i tt i m e w i n d o wr e s p e c t i v e l yt og e tt h es i n g l es c a n n i n ga l g o r i t h m ss m f pa n ds c f p f i n a l l y ，u s et h ea b o v ea l g o r i t h m si nt h es p e c i f i cb u s i n e s sa r e a s ，a n dd e s i g na r e t a i l o rd i s c o u n tc o u p o n sg e n e r a t i o ns y s t e m t h ee x p e r i m e n tr e s u l t ss h o wt h a tt h e a l g o r i t h m sh a v eh i 【g ha c c u r a c ya n d t i m ee f f i c i e n c y ，w h i c hc a nb eu s e di nt h eb u s i n e s s d e c i s i o nm a k i n gs u p p o r t k e y w o r d s ：d a t am i n i n g ；d a t a s t r e a m ；f r e q u e n tp a t t e r n ；m a x i m a lf r e q u e n tp a t t e r n ； d o s e df r e q u e n tp a t t e r n ；i n c r e m e n t a lm i n i n g ；t i l t e d t i m ew i n d o w 一i v 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 本人为获得浙江工商大学或其它教育机构的学位或证书而使用过的 材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作 了明确的说明并表示谢意。 签名：日期；纱够年涉胃褊 关于论文使用授权的说明 本学位论文作者完全了解浙江工商大学有关保留、使用学位论文 的规定：浙江工商大学有权保留并向国家有关部门或机构送交论文的 复印件和磁盘，允许论文被查阅和借阅，可以将学位论文的全部或部 分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制 手段保存、汇编学位论文，并且本人电子文档的内容和纸质论文的内 容相一致。 保密的学位论文在解密后也遵守此规定。 签名：墟导师签 园期： 浙江工商大学硕士学位论文1 绪论 1 绪论 1 1 研究背景 随着信息化的纵深发展以及全球互联网的进一步拓展，商业数据库的规模越 来越大，数据量呈指数级增长。目前应用最广泛的数据处理技术是数据库管理系 统技术( d a t a b a s em a n a g e m e n ts y s t e m ，简称d b m s ) 和数据仓库技术( d a t a w a r e h o u s e ，简称d w ) 。这些传统的数据处理技术具有一个共同点，即需要首 先将数据存储到外部介质中，然后提交至一些数据操纵语言( d a t am a n i p u l a t i o n l a n g u a g e ，简称d m l ) 进行处理。【1 】 尽管d b m s 技术和d w 技术获得了巨大成功，但是在2 0 世纪末，一种名为流 式数据( s t r e a m i n gd a t a ) 新的应用模型广泛出现在众多商业领域，对传统数据处理 技术提出了新的挑战。从数据挖掘角度，我们把流式数据的挖掘称为数据流挖掘， 其中数据流就是这种新的数据形式，即流式数据形式。在许多应用领域中处理的 数据都是以数据流的形式传输。例如：进行网络监测时获取的监测信息1 2 1 、股票 分析系统接受的实时的股票信息【3 , 4 1 、a t m 自动取款机的取款记录【5 1 、电信公司 的通话记录【6 1 、传感器监测到的各类数据【7 t 8 ，9 ，1 0 1 、p o s 机刷卡记录、电子商务等 等。虽然数据流中数据的基本单位还是关系模型中的元组，但是与传统数据库中 的数据不同，这类数据不再是固定的存储形式，而是源源不断的到来、随时间变 化的。从数据的角度来讲，数据量极大且数据产生速率非常快；其次，从应用的 角度来讲，要求获得实时、连续的查询结果。传统的数据处理技术( 如d b m s ， d w 等) 由于需要首先将所有的数据存到存储介质( 磁盘或者内存) 中，然后再 进行查询处理，不适合处理这类应用。越来越多的研究人员开始针对这类应用开 发新的基于数据流处理技术的研究。 1 1 1 商业应用背景 随着知识经济时代的来临，信息与知识已经成为国家和企业发展的重要战略 资源，是提高一个组织乃至一个国家战略竞争力的核心，也是实施科学管理与决 浙江工商大学硕士学位论文 l 绪论 策的基础。如何获取信息与发现知识，尤其是如何快速高效地在动态变化和爆炸 性增长的分布型海量数据流中获取信息和发现知识就成了关键性问题。同时，它 也是政府部门、企事业单位等关注的焦点、难点问题和学术界研究的热点问题。 作为国民经济和社会发展的重要组成部分，商贸流通业已经在过去的发展中 形成了大量的商业数据库，并且其数据流量仍在以几何方式继续保持增长。尤其 是商业领域中大型连锁零售企业( 如沃尔玛w a l m a r t 、家乐福c a r r e f o u r 、麦得 龙m e t r o 、上海百联、解百集团等) 通过网络实现上千家连锁分店、配送中心与 总店间内部信息的互连，以及与众多供应商、银行等外部信息的交换，形成了分 布型的商业数据共享环境。这些分布的数据库以每天几百兆甚至更多的数据记录 量速度增加和流动，形成了动态变化的海量商业数据流。 同时，商业零售业和顾客之间的关系是一种持续不断的发展关系，商业消费 信息来自市场中的各种渠道。例如，每当我们用信用卡消费时，商业企业就可以 在信用卡结算过程收集商业消费信息，记录下我们进行消费的时间、地点、感兴 趣的商品或服务、愿意接收的价格水平和支付能力等数据；当我们在申办信用卡、 办理汽车驾驶执照、填写商品保修单等其他需要填写表格的场合时，我们的个人 信息就存入了相应的业务数据库；企业除了自行收集相关业务信息之外，甚至可 以从其他公司或机构购买此类信息为自己所用。 这些来自各种渠道的数据信息被组合，应用超级计算机、并行处理、神经元 网络、模型化算法和其他信息处理技术手段进行处理，从中得到商家用于向特定 消费群体或个体进行定向营销的决策信息。 可以看出，数据挖掘是一种新的商业信息处理技术，其主要特点是对商业数 据库中的大量业务数据进行抽取、转换、分析和其他模型化处理，从中提取辅助 商业决策的关键性数据。目前，商业数据库现在正在以一个空前的速度增长，从 商业数据到商业信息的进化过程中，每一步前进都是建立在上一步的基础上的， 见表1 1 。表中我们可以看到，第四步进化是革命性的，因为从用户的角度来看， 这一阶段的数据库技术已经可以快速地回答商业上的很多问题了。 - 2 - 浙江工商大学硕士学位论文 1 绪论 表1 - 1 数据挖掘的进化历程 进化阶段 商业问题 支持技术产品厂家产品特点 数据搜集“过去五年中我的计算机、磁带和i b m ，c d c提供历史性 ( 6 0 年代)总收入是多少? ” 磁盘 的、静态的数 据信息 数据访问 “在杭州去年三月 关系数据库 o r a c l e 、s y b a s e 、 在记录级提 ( 8 0 年代) 的销售额是多( i b m s ) ，结i n f o r m i x 、m m 、供历史性的、 少? ”构化查询语言m i c r o s o f t动态数据信 ( s q l ) ，o d b c息 o r a c l e 、s y b a s e 、 i n f o r m i x 、1 1 3 m 、 m i c r o s o f t 数据仓库：“在杭州去年三月联机分析处理 p i l o t 、c o m s h a r e 、 在各种层次 决策支持的销售额是多少?( o l a p ) 、多维 a r b o r 、c o g n o s 、上提供回溯 ( 9 0 年代) 百货大楼据此可得数据库、数据仓 m i c r o s t r a t e g y 的、动态的数 出什么结论? ” 库 据信息 数据挖掘“下个月百货大楼高级算法、多处 p i l o t 、l o c k h e e d 、 提供预测性 ( 正在流行)的销售会怎么样?理器计算机、海m m 、s g i 、其他初的信息 为什么? ”量数据库创公司 尽管数据挖掘技术在挖掘静态数据集方面已经取得了很多成果，但将它扩展 到动态数据流挖掘中，尤其是商业数据流挖掘中仍具有很大的挑战性。 近年来涌现了大量的商业数据流应用问题，如：连锁零售分店运行状态的动 态监测与应急管理、动态订货与库存控制、价格波动动态追踪、敏捷供应响应分 析等，使得人们研究动态商业数据流的兴趣不断提高，快速数据挖掘日益成为人 们的需要。 显然，在知识成为企业核心竞争力的今天，如何从海量动态商业数据流中提 炼出有价值的商业知识，指导企业经营管理和科学决策，已经成为连锁零售企业 持续健康发展的关键所在。因此，针对商业数据流的特性，开展网络环境下商业 数据流的频繁模式发现问题研究，实现复杂环境下商业数据流的挖掘处理，从而 发掘商业企业运行的特征，找出具有共性或规律性的知识，掌握商业企业变化情 况，分析运行状况变化的动因，为商业企业提供科学和有效的管理与决策支持， 具有十分重要的理论价值和现实意义，同时对其他领域的知识发现技术应用具有 指导意义。 浙江工商大学硕士学位论文l 绪论 1 1 2 数据流挖掘 数据挖掘( d a t am i n i n g ) ，又称为数据库中的知识发现( k 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 ，l d ) ，它是由数据库、机器学习、统计学等多门学科形成的一门新兴 学科。其目标是从大量原始数据中获取有效的、新颖的、潜在有用的、最终可理 解的模式的非平凡过程，简单的说，数据挖掘就是从大量数据中提取或“挖掘 知识，其所发现的知识可以是描述数据特性的规则、频繁出现的模式、数据集中 目标的聚类、预测模型等。 并非所有的信息发现任务都被视为数据挖掘。例如，使用数据库管理系统查 找个别的记录，或通过因特网的搜索引擎查找特定的w e b 页面，则是信息检索 ( i n f o r m a t i o nr e t r i e v a l ) 领域的任务。虽然这些任务是重要的，可能涉及使用复杂的 算法和数据结构，但是它们主要依赖传统的计算机科学技术和数据的明显特征来 创建索引结构，从而有效地组织和检索信息。尽管如此，数据挖掘技术也已用来 增强信息检索系统的能力。图1 1 为典型的数据挖掘系统结构。 里! 墨望 j 争 二二 侮纛 数据挖掘引擎 l r 一一、一 圭奎 蕊翮服务器i 图i - i 典型的数据挖掘系统结构 数据挖掘是- - n 交叉学科，它把人们对数据的应用从低层次的简单查询，提 升到从数据中挖掘知识，提供决策支持。在这种需求牵引下，汇聚了不同领域的 研究者，尤其是数据库技术、人工智能技术、数理统计、可视化技术、并行计算 等方面的学者和工程技术人员，投身到数据挖掘这一新兴的研究领域，形成新的 技术热点。其主要目的是为了提高市场决策能力，检测异常模式，并在过去的经 - 4 - 1 苗 一择一厂1舅一、 一选一 阿一一商一备 面 浙泷一商大学硕士学位论文l 绪论 验基础上预畜未来趋势等。 而数据流挖掘就是在流式数据上发现提取隐含在其中的、人们事先不知道 的、但又是潜在有用的信息和知识的过程。由于数据流本身的特点，许多传统的 数据挖掘算法并不适合于数据流的挖掘。因为数据是以流动的方式出现，并不象 传统的数据是静态存储在磁盘中。许多数据如果没有被保存将无法重新访问。所 以要求基予数据流的挖掘算法不能多次重复扫描数据，只能通过对数据进行一次 扫描完成挖掘。此外，数据流中的数据量规模宏大，内存无法存储全部数据也使 得基于数据流挖掘的算法只能利用有限的内存提取数据流的一个样本作为算法 的输入数据，所以挖掘的结果也是近似值。同时根据数据流的特点，挖掘的结果 也应该是实时结果。 基于以上数据流挖掘的特点，传统的数据挖掘方法如果不改进多数不适合在 数据流上挖掘。例如：在数据流中挖掘关联规则时，用基于频集理论的a p r i o r i 算法获取最大频繁项集，就不能直接应用于数据流上。因为该算法必须经过多次 扫描事务数据库，才能获取最大频繁项集，进丽产生关联规则。还有由于数据流 随着时间的变化，新数据将被不断地读入，许多算法在处理数据时并不能将流入 的所有数据堆积处理，即便算法有这样的能力，数据也是随着时间鲶变化不断更 新，所以挖掘到的结果也在随时间不断地变化，使得挖掘的结果不能是绝对精确 的。这就要求数据流的挖掘算法要有一定的修改能力，即伸缩性。丽且基予数据 流的高速流入和数据流中的数据量极大的特点，要求算法的时间复杂度必须较 低，必须能够在内存中实现，不能进行内外存数据交换。因为这样将耗费大量的 时间，而且由于资源有限算法所占用的内存也不能过大。综上所述，针对数据流 上的挖掘必须使用新的方法，或者是对传统的方法做出某些改进，使其能适合对 流式数据进行挖掘。 本文针对商业数据流的特征，在静态频繁模式挖掘算法的基础上分别采取增 量式和倾斜时间窗口的方式存取数据流中的训练数据，当用户发出查询请求时， 算法将给出根据当前训练数据得到的挖掘结果以流的形式输出。并且有些结果只 能是近似结果。算法对内存的需求取决于倾斜时间窗口的大小和算法需要的缓冲 区的尺寸。 浙江工商大学硕士学位论文 1 绪论 1 1 3 数据流挖掘模型 根据数据流对实际记录数据的不同影响方式，数据流模型可以划分为三个子 模型：时间序列模型( t i m e s e r i e sm o d e l ) 、收银机模型( c a s h r e g i s t e rm o d e l ) 和转盘模型( t u r n t i l em o d e l ) t il l 。 1 时间序列模型：在这种模型中，实际记录数据的各项值被依次修改，且 每次只被改变一次。该模型主要出现在时间序列数据中。一个典型的例子是监控 一只股票报价的数据流，流中每一个元组都是相隔单位时间的股票报价。另外的 例子还包括网络流量监控，例如每隔1 秒钟汇报过去1 秒钟内某一个口地址发出的 数据包个数。 2 收银机模型：在这种模型中，实际记录数据不是按序变化的，但是每次 变化都增加项值。例如，每个客户在购物完毕之后都需要到超市收银机前付款， 从而产生一个顾客付款流。当某一个顾客要付钱时，首先找到属于这个人的记录 项，然后增加所付金额。值得注意的是，增加的金额总是一个正数。 3 转盘模型：在这种模型中，实际记录数据也不是按序变化的，而且每次 变化，其项值可能增加，也可能减小。转盘模型的条件比上述两个模型的条件都 宽松，也比较常见。例如，一个大电话公司( 例如中国电信) 想监控长途电话的 使用情况，则市民拨打电话行为就构成一个数据流。当某用户拨出一个电话时， 其所在城市所对应的记录项加一，当通话完毕挂机时则减一。 数据流模型除了按照数组a 的不同变化方式分为上述三种子模型之外，还可 以按照数据流上各个元组的重要程度不同划分为另外三种子模型：界标模型 ( l a n d m a r km o d e l ) 、滑动窗1 2 1 棋型( s l i d i n gw i n d o wm o d e l ) 和衰减窗口模型 ( d a m p e dw i n d o wm o d e l ) i t 2 】。 1 界标模型：在这个模型中，数据流算法仅仅考虑从某一个固定时间戳s n 当前时间戳n 之间的所有数据，查询范围是【s 。州。换句话说，在范m 0 s ) 之间的 元组，其重要性为零；在范围【s m 之间的元组，其重要性均相等。 2 滑动窗口模型：令w 为窗口大小。在这个模型中，数据流算法仅仅考虑 最近的w 个元素。即，其查询范围是：【m a x ( 0 , n w + 1 ) 。如。处在查询范围之外 的元组，其重要性为零；处在查询范围之内的元组，其重要性均相等。滑动窗口 模型注意到了新旧元组的不同地位，旧的元素不断淘汰，不再参与计算。 浙江工商大学硕士学位论文 1 绪论 3 衰减窗口模型：在这个模型中，数据流算法的范围从初始时间点到当前 时间点，查询范围是：【o n 】。但是，处在查询范围中的各个元组的重要程度是 不相同的。新到达的元组，其重要程度较高：旧的元组，其重要程度较低。例如， 令。a v g 。w 是一个平均数，x 是新到达的元组，衰减系数是p ，0 p 2 ，i ，i ，产 生只包含集合 1 1 ，1 2 ，i k ) 中的项的所有规则( 最多k 条) ，其中每一条规则的右部 只有一项，( 即形如旷一i 。】j ，v i f k ) ，这里采用的是前面所提到的类似于 ajb 的规则定义。一旦这些规则被生成，那么只有那些大于用户给定的最小可 信度的规则才被留下来。对于规则右部含两个以上项的规则，在其以后的工作中 进行了研究。 为了生成所有频集，使用了递推的方法。其核心算法思想如下： 首先产生频繁1 项集l l ，然后是频繁2 项集l 2 ，直到有某个r 值使得k 为空， 这时算法停止。这里在第k 次循环中，过程先产生候选k 项集的集合c k ，c k 中的 每一个项集是对两个只有一个项不同的属于l k - l ，的频集做一个( 1 【2 ) 连接来产生 的。c k 中的项集是用来产生频集的候选集，最后的频集l k 必须是c k 的一个子集。 c k 中的每个元素需在交易数据库中进行验证来决定其是否) h l , k l k ，这里的验证过 程是算法性能的一个瓶颈。这个方法要求多次扫描可能很大的交易数据库，即如 浙江工商大学硕士学位论文2 频繁模式挖掘相关理论回顾 果频集最多包含1 0 个项，那么就需要扫描交易数据库l o 遍，这需要很大的i o 负 下面是引用参考文献【3 5 中的a p r i o r i 算法伪代码参考。 输入：事务数据库d ；最小支持度阈值。 输出：d 中的频繁项集l 。 方法： l 1 = f i n d _ f r e q u e n t _ l _ i t e m s e t s ( d ) ； f o r ( k = 2 ；l k - i o ；l 卅) c k = a p r o i r i _ g e n ( l k 1 ，m i n _ s u p ) ； f o re a c ht r a n s a c t i o nt d s c a ndf o rc o u n t c t = s u b s e t ( c k ，t ) ；g e ts u b s e t so f tt h a ta l e c a n d i d a t e s f o re a c hc a n d i d a t ec e c t c c o u m + + ； ) l k = c e c kc c o u n t m i n _ s u p r e t u r nl = u k l k ； p r o c e d u r ea p r i o r i _ g e n ( l k 1 ：f r e q u e n t ( 1 ( 一1 ) 一i t e m s e t ；m i n _ s u p ：s u p p o r t ) f o re a c hi t e m s e ti ie l k 1 f o re a c hi t e m s e t1 2el k 1 i f ( 1 l 1 = 1 2 1 ) a a ( 1 l k 一2 = 1 2 k - 2 】) ( 1 l k 一1 1 2 k - 2 】) t h e n c a d i d a t e c = l lo o l 2 ； j o i ns t e p ：g e n e r a t ec a n d i d a t e s i f h a s _ i n f r e q u e n t _ _ s u b s e t ( c ，l k 1 ) t h e n d e l e t ec ； e l s ea d dct oc k ； ) r e t u r n c k ； - 1 4 - p r u n es t e p ：r e m o v eu n f r e q u e n t 浙江工商火学硕士学位论文2 频繁模式挖掘桐关理论回顾 p r o c e d u r eh a s _ i n f r e q u e n t s u b s e t ( e ：c a n d i d a t ek - i t e m s e t ；l k ：f r e q u e n t ( k - 1 ) 一i t e m s e t ) u s ep r i o r ik n o w l e d g e f o re a c h ( 1 【1 ) 一s u b s e tso f e i f c 硭k l t h e n r e t u r n t r u e ； r e t m nf a l s e ； 在论文中，a g r a w a l 等还弓l 入了修剪技术( p r u n i n g ) 来减小候选集c k 的大小， 由此可以显著地改进生成所有频集算法的性能。算法中引入的修剪策略基于这样 一个性质：一个项集是频集当且仅当它的所有子集都是频集。那么，如果敛中某 个候选项集有一个( k - 1 ) 子集不属于l 懈则这个项集可以被修剪掉不再被考虑，这 个修剪过程可以降低计算所有的候选集的支持度的代价。l 蚓 虽然a p r i o r i 算法自身已经进行了一定的优化，但是在实际的应用中，许多方 面还是存在不令人满意的地方，于是人们相继提出了一些优化的方法。 1 基于t 分的方法。s a v a s e r e 等f 3 7 】设计了一个基于划分0 a n i t i o n ) 的算法，这 个算法先把数据库从逻辑上分成几个互不相交的块，每次单独考虑一个分块并对 它生成所有的频集，然后把产生的频集合并，用来生成所有可能的频集，最后计 算这些项集的支持度。这里分块的大小选择要使得每个分块可以被放入主存，每 个阶段只需被扫描一次。而算法的正确性是由每一个可能的频集至少在某个分 块中是频集保证的。上面所讨论的算法是可以高度并行的，可以把每一分块分剐 分配给某一个处理器生成频集。产生频集的每一个循环结束后，处理器之间进行 逶信来产生全局的候选k 顼集。通常这里的通信过程是算法执行时闻的主要瓶 颈；而另一方面，每个独立的处理器生成频集的时间也是一个瓶颈。其他的方法 还有在多处理器之间共享一个杂凑树来产生频集。更多的关于生成频集的并行化 方法可以在【3 5 ，3 8 ，3 9 】中找到。 2 。基于h a s h 的方法。一个高效地产生频集的基于杂凑( h a s h ) 的算法蠢p a r k 等 脚】提出来。通过实验我们可以发现寻找频集主要的计算是在生成频繁2 项集l k 上，p a r k 等就是利用了这个性质弓l 入杂凑技术来改进产生频繁2 。项集的方法。 3 基于采样的方法。基于前一遍扫描得到的信息，对此仔细地作组合分析， 浙江工商大学硕士学位论文2 频繁模式挖掘相关理论回顾 可以得到一个改进的算法，m a n n i l a 等【4 1 l 先考虑了这一点他们认为采样是发现规 则的一个有效途径。随后又由t o i v o n e n 4 2 进一步发展了这个思想，先使用从数据 库中抽取出来的采样得到一些在整个数据库中可能成立的规则，然后对数据库的 剩余部分验证这个结果。t o i v o n e n 的算法相当简单并显著地减少了i o 代价，但 是一个很大的缺点就是产生的结果不精确，即存在所谓的数据扭曲( d a t as k e w ) 。 分布在同一页面上的数据时常是高度相关的，可能不能表示整个数据库中模式的 分布，由此而导致的是采样5 的交易数据所花费的代价可能同扫描一遍数据库 相近。l i n 和d u n h a m 在 4 3 中讨论了反扭曲( a n t i s k e w ) 算法来挖掘关联规则，在 那里他们引入的技术使得扫描数据库的次数少于2 次，算法使用了一个采样处理 来收集有关数据的次数来减少扫描遍数。 b r i n 等畔4 5 1 提出的算法使用比传统算法少的扫描遍数来发现频集，同时比基 于采样的方法使用更少的候选集，这些改进了算法在低层的效率。具体的考虑是， 在计算k 一项集时，一旦我们认为某个( 1 汁1 ) 一项集可能是频集时，就并行地计算这 个时1 ) 项集的支持度，算法需要的总的扫描次数通常少于最大的频集的项数。 这里他们也使用了杂凑技术，并提出产生“相关规则”( c o r r e l a t i o nr u l e s ) 的一个 新方法，这是基于他们的工作【4 6 堪础上的。 4 减少事务个数。减少用于未来扫描的事务集的大小。一个基本的原理就 是当一个事务不包含长度为k 的大项集，则必然不包含长度为k + 1 的大项集。从而 我们就可以将这些事务移去，这样在下一遍的扫描中就可以减少要进行扫描的事 务集的个数。这个就是a p r i o r i t i d 的基本思想。 2 1 2f p g r o w t h 及其改进算法 与a p r i o r i 算法不同，f p g r o w t h 算 、法和t r e e p r o j e c t i o n 算法一玎采用深度优先的 策略挖掘频繁项集。f p g r o w t h 算法思想是：先统计出频繁1 项集( 集合中的元素 称为频繁项) ，将其压缩到内存中的一棵频繁模式树( f p 树) ，同时保留项间关联 信息；然后，通过关联信息，将压缩后的数据库分成一组条件模式库。每一个条 件模式库与一个频繁项关联。之后使用称为f p g r o w t h 的方法从频度最小的频繁 项开始自底向上，在条件模式库上进行频繁项集挖掘。研究表明：f p o w t h 算 法大约比a p r i o r i 算法快一个数量级，同时也优于t r e e p r o j e c t i o n 算法。f p g r o w t h 浙江工商大学硕士学位论义 2 频繁模式挖掘相关理论回顾 方法不是在于：当存在许多长焉复杂的模式时，f p g r o w t h 算法需要递归构造的 条件树数量巨大，时空代价较高。 下面是对过程f pg r o w t h 的伪码描述。 p r o c e d u r ef p _ g r o w t h ( t r e e ，a ) i f t r e e 含单个路径pt h e n f o r 路径p 中结点的每个组合( 记作鼢 产生模式鼬伐，其支持度s u p p o r t = j 3 中结点的最小支持度； e l s e f o re a c h 在t r e e 的头部 产生一个模式胪c i ik ) t t ，其支持度s u p p o r t = 0 q s u p p o rt 构造p 的条件模式基，然后构造p 的条件f p 树t r e e p ； i f t r e e p ! = 囝t h e n 调用f p _ _ g r o w t h ( t r e e s ，p ) ； ，|， 许多研究者对f p g r o w t h 算法进行了改进。h m i n e 算法t 4 8 谰数组，而不是树 来表示项集，在稀疏数据集条件下，前者的空间效率较好，搜索效率较高。通过 对空间使用率的预测，为挖掘无法完全放入内存的大型数据库( 指经过压缩后) 创 造了条件。但在处理稠密数据集时，h - m i n e 退化为f p 。g r o w t h 算法。 在h m i n e 算法的基础这上，o p 算法f 4 9 1 引入混和投影技术，根据数据集的局 部统计数据，在基于数组的项集表示和基于树的项集表示法之闯，和自底向上和 自顶向下的搜索策略之间进行自适应的选择，以尽可能提高算法的效率。 在一棵类似殍树的严格有序的线索树中直接挖掘频繁项集，从而避免了动 态构建条件f p 树的开销。这些方法都不同程度的提高了f p g r