（计算机应用技术专业论文）网上银行数据流频繁模式挖掘算法研究及应用.pdf

浙江工商大学坝一# 位论文 网上银行数据流频繁模式挖掘算法研究及应用 首先，对数据流挖掘及其模型等相关理论进行研究，总结出目前 该领域的最新研究成果，通过网上银行数据流的研究总结出网银数据 流的概念与特征，提出网上银行数据流除了具备数据流的基本特点外， 还具备连续性、多义性、冲突性和海量性等特性。结合网上银行数据 流特征，提出网上银行数据流时序轮盘模型。 然后，研究分析了现有的数据流频繁模式挖掘算法。基于数据流 时序轮盘模型，提出t t l c ( t i m e - s e r i e st u r n s t i l el o s s yc o u n t i n g ) 算 法提高t l o s s yc o u n t i n g 算法的动态性，另外设计并实现基于散列表 的数据流频繁模式挖掘算法m f s h t ，并通过实验证明算法的时空效 率优于现有算法。 最后，本文将上述算法编码实现，集成到了自行设计开发的网上 银行数据流频繁模式挖掘系统当中。并使用模拟数据，对系统进行实 验分析与研究。实验表明系统具有较高的准确性和时间效率，对上层 决策支持具有一定的指导意义。 关键词：网上银行；数据挖掘；数据流；频繁模式；散列表 浙江工商大学硕士学位论文 网上银行数据流频繁模式挖掘算法研究及应用 t h er e s e a r c ha n da p p l i c a t i o no fm i n g f r e q u e n tp a t t e r n so v e re b a n kd a t as t r a e m s a bs t r a c t w i t ht h ed e v e l o p m e n to fi n f o r m a t i o n t e c h n o l o g y ，a c h i e v i n g i n f o r m a t i o na n d k n o w l e d g ef r o mt h ee x p l o s i v e ，h i g h l y 由m a i i l i cd a t ah a s b e c o m et h ec o r ec a p a b i l i t yo fa ne n t e r p r i s ee v e na c o u n t r yt ot a k i n gt h e l e a d e r s h i pi na ni n d u s t y d a t am i n i n gi sj u s tt h ea r t i f i c i a li n t e l l i g e n c e t e c h n o l o g yt os o l v et h i sk i n d o fp r o b l e m b u tn o w a d a y ss o m en e w a p p l i c a t i o nl i k ef r a u dm o n i t o r i n gi ns e c u r i t i e st r a d i n ga n dr i s kc o n t r o lo f f i n a n c i a lt r a n s f e r s ，s e n s o rd e t e c t i o na n d p r e c a u t i o n a r yo fc r e d i tc a r df r a u d r e q u i r em o r et i m ee f f i c i e n c ye v e nm o s tt i m en e e dr e a l - t i m er e a c t i o n 。f o r t h i sr e a s o n ，d a t as t r e a m h a sb e e np r o p o s e di nt h el a s tc e n t u r y d i f f e r e n t f r o mt r a d i t i o n a ld a t a b a s et e c h n o l o g y ，t h ed a t as t r e a mi sc o n t i n u o u s ， o r d e r l y ，i n f i n i t e ，a n dq u e r i e so nd a t as t r e a m sr e q u i r eh i g h l yr e a l - t i m e f e e d b a c k i t su s u a l l ya l l o w i n go n l yo n eo rv e r yf e wn u m b e ro fs c a n s o v e rd a t as t r e a m t oo b t a i nu s e f u li n f o r m a t i o nf r o mv a s ta m o u n t so fd a t a i i l 浙江工商大近孚位论文网上银行数据流频繁模式挖掘算法研究及应用 s t r e a mw i t hl i m i t e ds y s t e mr e s o u r c e sh a sb r o u g h tn e wo p p o r t u n i t i e sa n d c h a l l e n g e sf o rd a t am i n i n g i nt h i sp a p e r , w er e s e a r c h e dt h et e c h n o l o g yo f m i n i n gf r e q u e n t p a t t e m so v e re - b a n kd a t as t r e a ma n do t h e rr e l a t e dt e c h n o l o g i e s w e f o c u s e so nt h ef o l l o w i n gi s s u e s ：e x i s t i n gd a t as t r e a md a t as t r u c t u r em o d e l a n da l g o r i t h m sf o rm i n i n gf r e q u e n tp a t t e mo v e rd a t as t r e a m ；s t r u c t u r a l c h a r a c t e r i s t i c so ff i n a n c i a lo n l i n eb a n kd a t as t r e a ma n di t sd a t am o d e l ； i m p r o v e dl o s s yc o u n t i n gt oa c h i e v em o r ed y n a m i c i t y ；d e v e l o p e d an e w a l g o r i t h mn a m e d m f s h tt om i n i n gf r e q u e n ti t e m so v e re - b a n kd a t a s t r e a mb a s e do ns a m p l i n ga n dh a s h - t a b l e ；t h ed a t as t r u c t u r eo fe b a n k d a t as t r e a m ，d e s i g na n dd e v e l o pe - b a n kd a t as t r e a mm i n i n gs y s t e mf o r f r e q u e n tp a t t e r n t h er e s e a r c hc o n c e p ta n di n n o v a t i v ew o r ko ft h i sp a p e r i n c l u d i n g ： f i r s to fa l l ，w eh a dr e s e a r c h e dt h et h e o r yo fd a t as t r e a mm i n i n ga n d i t sd a t as t r u c t u r a lm o d e l a n dt h e nw es u m m a r i z e dt h ec u r r e n to u t c o m e s o ft h el a t e s tr e s e a r c h i n gi nt h i sd o m a i n w i t ht h es t u d y i n go fe b a n kd a t a s t r e a mw es u m m e d u pt h ec o n c e p ta n dc h a r a c t e r i s t i c so fe b a n kd a t a s t r e a m s ，c o n c l u d et h a te - b a n kd a t as t r e a mh a sm o r ef e a t u r e sl i k e s e q u e n t i a l ，m u l t i s e m a n t i c ，c o n f l i c t e d ，a n dm a g n i f i ct h a ng e n e r a ld a t a s t r e a m t h e nan e wd a t as t r e a mm o d e lo fe - b a n kd a t as t r e a m t i m es e r i e s t u r n s t i l em o d e lw a sp r o p o s e d i v 浙江：商大学硕士学位论文 网上银行数据流频繁模式挖掘算法研究及应用 t h e n ，w eh a v er e s e a r c h e da n da n a l y s i s e do fe x is t i n ga l g o r i t h m sf o r m i n i n gf r e q u e n tp a t t e r n so v e rd a t as t r e a m b a s e do nt i m e s e r i e st u r n s t i l e m o d e l ，t t l c ( t i m e - s e r i e st u r n s t i l el o s s yc o u n t i n g ) a l g o r i t h mw a s p r o p o s e d i ti m p r o v e dt h ed y n a m i c i t yo fl o s s yc o u n t i n g w ea l s o d e s i g n sa n di m p l e m e n t sah a s ht a b l eb a s e da l g o r i t h mf o rm i n i n gf r e q u e n t p a r e m sn a m e dm f s h t ，a n dp r o v e db ye x p e r i m e n t st h a tt h et i m ea n d s p a c ee f f i c i e n c yo fm f s h t i ss u p e r i o rt oe x i s t i n ga l g o r i t h m s f i n a l l y ，t h ea b o v ea l g o r i t h m sh a db e e ni m p l e m e n t e d a n daf r e q u e n t p a t t e r n sm i n i n gs y s t e mo v e re 七a n kd a t as t r e a mh a db e e nd e s i g n e da n d i m p l e m e n t e d w i t ht h ee x p e r i m e n to nt h i ss y s t e ma n da n a l y z i n go i lt h e e x p e r i m e n t a lr e s u l t s ，w ec o n c l u d e dt h a tt h es y s t e mh a sh 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 k e y w o r d s ：e - b a n k ；d a t am i n m g ；d a t as t r e a m ；f r e q u e n tp a t t e r n h a s ht a b l e v 浙江工商大学硕士学位论文网上银行数据流频繁模式挖掘算法研究及应用 目录 摘要i a b s t r a c t i i i 目录v i i 一、绪论1 i i 研究背景1 i 2 国内外研究现状4 i 3 本文主要工作6 1 4 本文结构7 二、数据流和数据流频繁模式挖掘8 2 i 数据流挖掘8 2 2 i 数据流概念及特点8 2 2 2 数据流挖掘模型1 0 2 2 3 数据流挖掘处理过程1 2 2 2 数据流频繁模式挖掘算法1 2 2 2 1 问题定义1 3 2 2 2 现有频繁模式挖掘算法1 4 2 3 本章小结1 7 三、网上银行数据流挖掘模型研究1 8 3 i 网上银行数据流概念及特征1 8 3 2 网上银行数据流时序轮盘模型的构建2 0 3 4 本章小结2 l 四、基于时序轮盘模型的数据流频繁模式挖掘算法2 2 4 1 时序轮盘t t l c 算法2 2 4 2m f s h t 算法2 3 4 4 1m f s h t 2 3 4 4 2d 一散列表的定义2 4 4 4 3d 一散列表的构造2 5 4 3m f s - h t 挖掘算法2 8 4 4 算法实验及分析3 0 4 6 1 测试环境与算法实现3 0 4 6 2 测试结果与分析3 l 4 5 本章小结3 4 五、网上银行数据流挖掘系统构建3 5 5 1 系统结构3 5 5 2 系统功能介绍3 5 v i i 浙江工商大学硕士学位论文 网七银行数据流频繁模式挖掘算法磺究及应用 5 2 1 模拟数据流生成模块 5 2 2 数据处理模块 5 2 3 关联规则挖掘模块 3 5 4 0 4 3 4 5 4 5 5 l 5 2 5 2 5 2 5 3 5 8 5 9 5 9 浙江工商大学硕士学位论文 网上银行数据流频繁模式挖掘算法研究及应用 一、绪论 随着信息技术的发展，如何有效的利用信息与知识已经是一个企业乃至一个 国家取得核心竞争力、实习科学管理与决策的关键。如何获取信息与知识，特别 是在如今爆炸性增长与动态变化的海量数据中获取信息与知识就成了关键中的 关键。数据挖掘技术就是为了解决这一问题孕育而生的信息技术。数据挖掘技术 旨在从大量数据中提取有用的知识，帮助人们进行科学分析和决策。经过近十几 年来的发展，很多有用的挖掘算法和模型相继被提出，数据挖掘技术已经被应用 到多个相关领域。然而，近年来，产生了一种新的数据形式，如在传感器网络、 电子商务记录、网络监控日记。这些数据按照时间顺序，快速、无限的到来。在 这种数据形式中，挖掘算法只能对数据进行一次或者有限次顺序扫描，有限的内 存也无法处理高速大量的数据。传统的数据挖掘算法不能适用于处理这种数据形 式，这促使人们设计新的算法，开辟新的领域来适应这种数据形式的挖掘数 据流挖掘。 1 1 研究背景 数据库技术的成熟和数据库应用的普及使得人类积累的数据量正在以指数 速度增长，人们应用数据库技术处理着日常繁杂的事务。大量信息在给人们带来 方便的同时也带来了一系列问题：第一是信息过量，难以消化：第二是信息真假 难以辨识：第三是信息安全难以保证；第四是信息形式不一致，难以统一处理。 人们开始考虑如何才能不被信息淹没，而是从中及时发现有用的知识、提高信息 的利用率。这些问题的产生促成了数据挖掘技术的出现。 数据挖掘技术出现于2 0 世纪8 0 年代后期，9 0 年代有了突飞猛进的发展。数据 挖掘技术是人们长期对数据库技术进行研究和开发的结果。起初各种数据是存储 在计算机的数据库中的，然后发展到可对数据库进行查询和访问，进而发展到对 数据库的即时遍历。数据挖掘使数据库技术进入了一个更高级的阶段，它不仅能 对过去的数据进行查询和遍历，并且能够找出过去数据之问的潜在联系，从而促 进信息的传递。现在数据挖掘技术在商业应用中己经可以马上投入使用，因为对 浙江工商大学v 一 ：学位论文网上银行数据流频繁模式挖掘算法研究及应用 这种技术进行支持的三种基础技术已经发展成熟，分别是： 海量数讼搜集； 强大的彩处理器计算机； 数据挖抛算法。 数据挖掘可以从大量的、不完全的、有噪声的、模糊的、随机的数据中， 提取隐含在其中的人们事先不知道的、但又是潜在有用的信息和知识的过程【l 】。 然而将数据挖掘技术应用到数据流的挖掘仍然存在着巨大的问题。目前应用最广 泛的数据处理技术是数据库管理系统技术( d a t ab a s em a n a g e m e n ts y s t e m ，简称 d b m s ) 和数据仓库技术( d a t aw a r e h o u s e ，简称d w ) 。这些技术具有一共共 同点，即需要外部介质的辅助，如内存、磁带、磁盘等来存储这些数据。在使用 过程中，通过提交一些数据操作语言( d a t am a n i p u l a t i o nl a n g u a g e ，简称d m l ) 进行查询、添加、更新以及修改【羽。 d b m s 和d w 技术现在依然在数据处理领域担当者最重要的地位，直至l j 2 0 世 纪末，一种名为流式数据( s t r e a m i n gd a t a ) 的新的应用模型广泛出现在众多计算 机应用领域，对传统数据处理技术提出了新的挑战。对于流式数据的概念，不同 的文献给出了类似的定义【3 5 】。简单的说，流式数据是一个按照时间递增顺序排 列的无穷序列。与传统的数据库不同，这种流式数据是实时、连续、有序、无限 的，并且在这之上的查询具有很高的实时性要求，通常只允许一次或很少次数的 扫描。从数据挖掘角度，我们把流式数据的挖掘称为数据流挖掘，其中数据流就 是这种新的数据形式，即流式数据形式。在许多应用领域中处理的数据都是以数 据流的形式传输。例如：电信公司的通话记录、网络监测信息、实时股票信息、 a t m 自动取款机取款记录、传感器监测数据、p o s 机刷卡记录、电子商务交易记 录等等。虽然数据流中数据的基本单位还是数据库关系模型中的元组，但是与传 统数据库中的数据不同，这类数据的总量随时间变化，这类数据的接收顺序根据 网络情况变化，不再是固定的存储形式。从数据的角度来讲，这类数据数据量极 大，并且数据产生速率非常快；其次，从应用的角度来讲，对于这类数据的处理， 通常具有很高的实时性和连续性要求。d b m s 技术和d w 技术，需要把所有数据 先存储在存储介质( 内存，磁带或磁盘) 当中，然后通过提交数据库操作语言对 这些存储介质中的数据进行查询、添加、更新和删除。就无法对数据量变化，数 2 浙江工商大学硕士学位论文网上银行数据流频繁模式挖掘算法研究及应用 据不可预知的数据流数据进行处理。越来越多的研究人员开始针对这类应用开发 新的基于数据流处理技术的研究，试图解决传统数据处理技术在该类问题上的不 足。 伴随着信息技术的发展、国际互联网的广泛普及以及电子商务的发展，金融 业也正在产生变化。过去几十年一直沿用的网点服务、人工业务正在被信息系统 信息技术不断替代，带来的是更为自动化、低成本且不受地域限制的信息化服务。 客户足不出户就可以享受到金融企业提供的高效优质服务，相应的金融数据规模 也随之不断以指数级增长，其中包含了客户信息、存取款记录、信用卡消费记录 等等大量含金量极高的数据。近年来随着电子商务的发展，各个银行都推出了网 上银行业务，据报道淘宝网在2 0 0 9 年十一黄金周期问的日营业额都在亿元人民 币以上，每天电子商务中发生的金融交易都在数百万笔。加上银行传统业务中的 交易记录，金融数据库每天都在以数百兆甚至更多的记录数量在增加和流动，形 成了动态变化的海量金融数据。 这些数据中都蕴含着如客户消费习惯、偏好等等珍贵的信息，应用超级计算 机、并行处理、神经元网络、模型化算法和其他信息处理技术手段进行处理，从 中得到金融企业用于向特定消费群体或个体进行定向营销的决策信息。如何利用 现有信息，从中发现知识为顾客提供更好的服务，开发更加具有市场竞争力的金 融产品，是提高金融企业决策、运营的一大有效手段。例如，客户的每笔信用卡 消费，都会在发卡行中记录消费的时间、地点、感兴趣的商品或服务、愿意接受 的价格水平和支付能力等数据，在对这些数据经过挖掘之后可以结合g p s 技术， 实时的对客户可能感兴趣的消费场所进行推荐，可以提高发卡行信用卡的使用率： 或者根据记录的客户消费水平、资金闲置程度，有针对性的推销基金产品；还可 以向零售业、服务业商家提供信息服务等等。 可以看出，数据挖掘是一种新的信息处理技术，其主要特点是对数据库中的 大量业务数据进行抽取、转换、分析和其他模型化处理，从中提取辅助决策的关 键性数据。目前，金融数据库现在正在以一个空前的速度增长，从金融数据到金 融信息的进化过程中，每一步前进都是建立在上一步的基础上的，见表1 1 。表 中我们可以看到，第四步进化是革命性的，因为从用户的角度来看，这一阶段的 数据库技术已经可以快速地回答业务上的很多问题了。 。 3 浙i ( 工商大学硕士学位论文网上银行数据流频繁模式挖掘算法研究及应用 进化阶段商业问题支持技术产品厂家产品特点 数据搜集 “过去2 年中a 计算机、磁带和l b m c d c 提供历史性的、 ( 6 0 年代) 的刷卡金额是多磁盘 静态的数据信息 少? ” 数据访问“在杭州去年a关系数据库 o r a c l e 、s y b a s e 、 在记录级提供历 ( 8 0 年代) 的刷卡金额是多( r d b m s ) ，结l n f o r m i x 、i b m 、史性的、动态数 少? ”构化查询语言m i c r o s o f l据信息 ( s q l ) ，o d b c o r a c l e 、s b a s e 、 l n f o r m i x 、i b m 、 m i c r o s o f t 数据仓库：“在杭州去年a联机分析处理 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 的数据信息 可得出什么结仓库 论? ” 数据挖掘“推荐a 在合作高级算法、多处p i l o t 、i x ) c k h e e d 、 提供预测性的信 ( 正在流行)商家b 商场进行理器计算机、海i b m 、s g i 、其他息 消费? ”量数据库初创公司 1 2 国内外研究现状 表1 - 1 数据挖掘进化历程1 二十世纪九十年代末以来，由于数据流模型在很多新型应用中广泛出现，对 于借助数据挖掘技术对数据流中的知识进行发现的需求也越来越强烈，但是由于 数据流本身的特点，现有技术难以满足需求。近年来，有关数据流处理的研究受 到了国内外相关领域研究人员的广泛重视，基于数据流模型的数据挖掘技术也得 到了广泛研究，这其中包括聚类分析、决策树和分类、频繁模式挖掘等等，提出 了很多有效的模型和算法。 数据流研究的一个主要方面是基于数据流模型的算法研究。m u n r o 和 1 p a t e r s o n 7 1 在1 9 8 0 年提出的计算数据集合分位数方法，证明可以利用d ( 石) 的空 间复杂度，通过p 次遍历数据来精确获得分位数。同时创造了一次扫描数据集合 获得近似分位数的方法。另外，b o y e r 和m o o r e 8 l 在1 9 8 2 年提出了一种一次扫 4 浙江工商大学硕士学位论文网上银行数据流频繁模式挖掘算法研究及应用 描数据集合获得频数占到整个集合一半以上的元素的方法。这两种算法都可以看 成是数据挖掘算法、数据流挖掘研究的雏形。 频繁项挖掘是很多数据挖掘工作的基础，数据流频繁模式挖掘的任务就是发 现数据流中频繁模式的完全集。由于数据流中的数据快速变化、规模宏大且只能 遍历一次或很少次，对于数据流上的频繁模式挖掘算法提出了更高的要求。经过 研究人员的不断努力，数据流上的频繁项挖掘算法被陆续提出。 g i a n n e l l a 和h a n 等人基于数据库挖掘中的f p g r o w t h 算法【9 1 提出了 f p s t r e a m 算法【1 0 1 ，并在之后发表的论文中利用人们对近期的知识兴趣程度更大 的特点，引入倾斜时间窗e l ( t i t l e d t i m ew i n d o w ) 【l l 】保存不同时间粒度下的模式 信息，但是当事务的平均长度和频繁模式逐渐变长，算法效率会迅速下降。 c h a r i k a rm ，kc h e n ，a n df a r a c h c o l t o nm 在文献 1 2 】中基于散列表，提出了 空间复杂度为o ( k e 2 l o 日霸) ，以1 一艿的概率输出所有频繁度计数超过 1 ( k + 1 ) 的项集的c o u n ts k e t c h 算法。但是该算法无法完全清除高频率元素的 碰撞问题，并且在子集频繁度的估算当中容易引入大量的误差。 c h a n g 等人提出的e s t d e c 算法给每个事务一个权重值，该权重值按时间 指数进行衰减，从而保证只挖掘最近发生的频繁模式。算法采用了字典序的字典 树存储模式，应用了类似c a r m a 算法【h 】的估计频繁度思想，以新模式的子模式 中的最小计数来近似替代新模式的实际频繁度，并由阀值s 与模式长度k 约束频 繁度上限。 c o r m o d e 和m u t h u k r i s h n a n 等提出了g r o u p t e s t 算法【l 习，空间复杂度进一步 降为o ( k ( 1 0 a k + l o g l 5 ) l o g m ) 。 m a n k u 等基于抽样技术，提出了l o s s yc o u n t i n g 算法【1 q 有效解决了挖掘频繁 1 项集的问题，在同一篇文献中也给出了随机近似的s t i c k y 算法和挖掘频繁多项 集的l o s s yc o u n t i n g 扩展算法。但是由于产生的候选项集数量巨大，而且将数据 存储在辅存中，致使算法效率不高。另方面，算法只考虑了数据不断增加，没 有考虑历史数据的删减以及类似滑动时间窗口策略中历史数据的影响力不断减 小，因此动态性不够强。g u o j l es o n g 等人f 1 7 1 基于h o e f f d i n gb o u n d 理论利用数据 流分段对频繁模式进行估计。 5 浙江工商大学坝0 学位论文网上银行数据流频繁模式挖掘算法研究及应用 在国内，也吸引了众多的专家学者进行数据流频繁模式方面的研究，提出了 几个高效的算法。东南大学的刘学军等人在f p g r o w t h 算法 9 1 的基础上提出了 f p d s 算法f 闭。算法采用分段策略，将数据流分成片段进行项集频繁度计数，利 用支持度误差对非频繁项集进行裁剪，该算法可以有效的挖掘出数据流当中的 全频繁模式，并适合长频繁模式的挖掘。 东北大学的张昕等人使用一种改进的字典序树结构i l t r e e ( i m p r o v e d l e x i c o g r a p h i ct r e e ) ，并在此基础上提出了启发式算法f p i l - s t r e a m i 饽】。该算法同 时引入了倾斜时间窗口策略，降低了数据的平均处理时间，在模式查询上提供了 更细的粒度。 数据流频繁模式挖掘已经获得了大量的成果，但是在目前仅仅在商业领域的 到了应用，在网上银行以及金融领域还未得到应用。因为在网上银行和金融领域 的应用实时性要求更高，仍需进一步研究。 1 3 本文主要工作 数据流挖掘算法是近期数据挖掘的一个研究热点，其中数据流上的关联规则 挖掘更是一大重点领域。数据流中频繁模式的挖掘和应用都是数据流关联规则挖 掘处理中的基本问题，在金融信息等领域中都有重要意义。在本文中，我们在原 有静态算法的基础上对这两个问题进行了初步研究，并且做出了如下几点贡献。 首先，研究数据流与传统数据库数据的不同特点，对数据流模型的特点及其 适用范围进行分析，并重点对网上银行数据流的数据结构和内容结构进行分析， 总结网上银行数据流特征，分析设计适用于网上银行数据流挖掘的数据流模型， 进而提出数据流时序轮盘模型。 其次，对现有的数据流挖掘算法进行研究，从中选取高效的l o s s yc o u n t i n g l l 6 1 算法，应用数据流时序轮盘模型对算法进行改进，增强该算法的动态性提出算法 i t l c 。借鉴l o s s yc o u n t i n g 算法的频繁度检测方法，设计实现自由知识产权算 法m f s h t 。并使用模拟数据对算法的时空效率进行测试。 最后，使用m f s h t 算法作为基础算法，结合网上银行业务数据特点，设 计并实现针对金融网上银行数据流的关联规则挖掘系统。 6 浙江工商大学硕士学位论文 网上银行数据流频繁模式挖掘算法研究及应用 1 4 本文结构 本文共分为6 章。 第l 章绪论部分，主要介绍本文的研究背景，国内外研究现状，以及本文 的贡献和结构。通过对国内外数据流技术的研究，总结出关于数据流、数据流频 繁模式挖掘的基本特点、模型以及关键技术等； 第2 章研究数据流挖掘相关理论并对几个数据流分类、聚类和频繁模式经 典挖掘算法进行了介绍。 第3 章主要研究网上银行数据流模型。回顾数据流模型特点，总结出网银 数据流的基本概念及特征，并在此基础上提出了数据流的时序转盘模型。 第4 章重点介绍提出优化后的数据流算法，即应用时序轮盘模型的l o s s y c o u n t i n g 改进算法t t l c 和自行设计的m f s h t 算法。 第5 章分析频繁模式挖掘在网上银行中的应用，构建针对网上银行数据的 关联规则挖掘系统。 第6 章总结与展望。 浙江工商大学硕士学位论t网f ：银行数据流频繁模式挖掘算法谚亢及应用 二、数据流和数据流频繁模式挖掘 2 1 数据流挖掘 2 2 1 数据流概念及特点 最近几年涌现出一种新的数据密集的应用类型，在这种应用中，数据成倍的、 快速的、随时间变动的、不可预测的和无限的以流的方式连到达。这种应用的例 子有：金融应用、安全、电信数据管理、制造业、网络监控和流量分析、w e b 应 用和w e b 点击流、能量消耗管理、传感器网络数据分析、电子商务、股票市场联 机分析等等。举几个具体一点的例子，在传感器监控领域有一些新出现的应用， 在这些应用中，有大量的传感器分布于物理世界，它们产生各种连续不断的数据 流，需要对其进行合成、监控、和分析等。有一些大的网站需要在线监控w e b 日志，以实现一些应用，如个性化设置、网站性能监控和负载平衡等。还有，对 一个基于w e b 的金融搜索引擎，它需要在实时流入的金融数据如证券报价上计算 用户提出的单次或连续的查询等。在这些应用中必须处理一种新的数据类型：流 数据。这种数据类型不能按持久的关系表的形式来建模，而是按瞬时的数据流的 形式建模。 数据流可以定义为一系列连续且有序的数据单元组成的序列x ，如而 称为数据流。不同于传统数据库技术将数据单元存储在介质中，通过提交数据 操纵语言( d m l ) 可以多次获取查询结果，并可以在一系列数据单元当中随机 定义查询起始位置；这些数据单元只能按照先后顺序，进行一次或者极有限次的 读取。 d a t as t r e a m ： 图2 1 数据流模型图 数据流模型【捌如图1 2 ，其中f 表示任一时间戳，a 表示在该时间戳到达的 数据，数据流可以表示为o ，口f 一1 ，n f ，n l ) 。在数据流模型中，处理的数据 不再是从磁盘和内存中随机访问读取的数据，而是一个或多个连续的、无穷的数 8 浙江工商大学硕士学位论文 网上银行数据流频繁模式挖掘算法研究及应用 据项组成的序列。 总结数据流与存储在数据库中的数据的区别如下： 1 ) 数据流中的数据是非持久化的；而数据库中的数据是半持久化，存储在 磁盘中。 2 ) 数据流中的数据是无限不可预知的；而数据库中的数据是有限的。 3 ) 一般来说数据流中数据的更新频率要比数据库中数据的更新频率要快。 4 ) 数据流中的数据是按照先后顺序流入系统，对数据只能进行顺序的有限 次的访问；而数据库中的数据可以随机多次访问。 5 ) 由于系统资源有限无法存储数据流中的全部数据，并且数据流中的数据 具有不可预知性又不断流入，在查询执行时随时可能发生变化，因此数据流上的 查询只能得到近似的结果；数据库中的数据在查询之前已经存储在可持久化设备 当中，在查询执行时变化较小，可以得到精确的查询结果。 结合数据挖掘的概念f 2 l 】，对于数据流挖掘的概念总结如下：数据流挖掘是 在流式数据上发现提取隐含在其中的、人们事先不知道的、但又是潜在有用的信 息和知识的非平凡过程。由于数据流本身的特点，许多现有的数据挖掘算法无法 直接应用在数据流的挖掘。因为数据是以流动的方式出现，许多数据如果没有被 保存将无法重新访问，并且系统资源有限未及时处理的数据只能丢弃，所以要求 基于数据流的挖掘算法只能通过对数据进行一次扫描完成挖掘。此外，数据流中 的数据规模宏大、更新速度快，内存无法存储全部数据也使得基于数据流挖掘的 算法只能利用有限的内存提取数据流的一个样本作为算法的输入数据，挖掘到的 结果也随着数据流数据的不断更新不断发生着变化，所以挖掘的结果只能是近似 值。同时根据数据流挖掘的功能性需求，挖掘的结果也应该是实时结果。 现有的数据挖掘方法无法直接应用到数据流挖掘上来。例如：数据挖掘中的 经典方法a p r i o r i 算法【2 2 】，就不能直接应用于数据流上。该算法使用a p r i o r i 性质， 认为频繁模式的子集都是频繁的，然后从子集推断频繁超集。具体步骤为先扫描 一遍数据库，计算频繁l 项集的频繁度，再从频繁的l 项集求出笛卡尔积得出候选 频繁2 项集的集合。再扫描一遍数据库，求出每个候选频繁2 项集的频繁度计数， 确定频繁2 项集。以此类推，通过频繁k 一1 项集求出频繁j ：c 项集，就必须对数据 进行七次全扫描，无法满足数据流挖掘的实时性要求。另外由于数据流随着时间 9 浙江工商大学硕士学位论文网上银行数据流频繁模式挖掘算法研究及应用 的变化，连续不断的流入数据库，未来到来的数据又通常是不可预知的，所以挖 掘到的结果也在随时间不断地变化，使得挖掘的结果只能是近似的。这就要求数 据流的挖掘算法在挖掘结果的更新上具有一定的伸缩性。而且基于数据流的高速 流入和数据流中的数据量极大、对于挖掘的实时性要求等特点，要求算法的时间 复杂度尽量低，并且必须能够在内存中实现，不能进行内外存数据交换，因为这 样将耗费大量的时间进行磁盘i o 。而且由于资源有限算法所占用的内存也不能 过大。综上所述，针对数据流上的挖掘必须使用新的方法，或者是对现有的数据 挖掘方法做出某些改进，使其能适合对流式数据进行挖掘。 2 2 2 数据流挖掘模型 根据数据流对实际记录数据的不同影响方式，数据流模型可以划分为三个子 模型：时间序列模型( 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 s t i l em o d e l ) 2 3 1 。 数据流模型可分为以下3 类： ( 1 ) 时间序列模型。在这种模型中，数据元组按照时间点依次到达，以时 间为标示。典型的就是传感器监控的例子，流中每一个元组都是相隔单位时间的 传感器检测信息。另外的例子还包括网络流量监控，例如每隔1 秒钟汇报在这1 秒钟内某一个i p 地址发出的数据包个数、来源地、目的地等信息。则有 口l = ( ，r i )( 2 1 ) 其中，f 对应着递增的采样时刻。 ( 2 ) 收银机模型。由于数据流下一个到来的数据记录的不可预知性，数据 流的当前状态变化状态也同样不可预知，根据到来的数据记录的不同，数据流当 前状态可以向多个分支变化。就像超市中的收银机，永远不知道下一个顾客会支 付多少钱。这可能是最普遍的数据流模型，可以应用到大部分数据流问题上。如 对w e b j 艮务器的访问i p 的监控，同一i p 可能在不同时刻对服务器进行多次访问， 也可能因为网络延时的关系，对同一地址传送多个数据包。则有 n f = ( ，f ) ，l 0( 2 2 ) 4 f ，】= a i 一1 【】+ ，f( 2 3 ) 其中，a f 们表示在五出现之后数据流的状态。 1 0 塑望三塑奎差堡圭堂笪堡塞 塑圭堡堡垫塑堕堡茎堡茎丝堡塞生堑垄墨望里 ( 3 ) 转盘模型。该模型e h 拥挤的地铁站中记录乘客出入的十字转门启发而 得。转盘模型的条件比上述两个模型的条件都宽松，也比较常见。例如，一个大 电话公司( 例如中国电信) 想监控长途电话的使用情况，则市民拨打电话行为就构 成一个数据流。当某用户拨出一个电话时，其所在城市所对应的记录项加l ，当 通话完毕挂机时则减l 。转盘模型是研究数据流动态变化的最优模型，但是存在 比较难解决的难题，就是无法界定一次增加或者删除操作的界【2 4 】，即无法界定 操作在何时、在哪段数据结束，因此一直被用来进行理论研究。则有 n f = ( ，以) ，f 0 ( 2 - 4 ) a l ，】= a i 一1 【，】+ 仉( 2 5 ) 其中仉可视作删除与插入符，数值可正可负。正代表数据流的增加，负代 表数据流的减少。 转盘模型具有较好的理论价值，但是因为界的问题，一直无法投入到实际应 用当中。前2 种数据流模型具有很好的实际意义，特别是时序数据流，现在数据 流挖掘上的工作基本都是基于时序模型进行的。时序模型根据不同的时序范围可 以划分成多种子模型，包括界标模型、滑动窗口模型和快照模型【2 5 1 。令7 l 表示 当前时间戳，s ，e 分别是两个己知的时间戳。界标模型的查询范围从某一个已知 的初始时间点到当前时间点为止，即( ，a n ) 。滑动窗口模型仅关心数据流中 最新的w ( w 也称为滑动窗口大小) 单位数据，其查询范围是 ( a m a x ( n 一+ 1 ，o ) 一，a n ) ，随着数据的不断到达，窗口中的数据也不断平移。快照 模型则将操作限制在两个预定义的时间戳之间，表示为( ，a e ) 。界标模型和 滑动窗口模型由于要不断处理新来的数据，更接近于真实应用，因而得到更加广 泛的研究。 浙江工商大学顽i + 亿i 它网七银行数据流频繁模式挖掘算法研究及应用 2 2 3 数据流挖掘处理过程 浙江工商大学硕士学位论文网上银行数据流频繁模式挖掘算法研究及应用 或者再次提取数据代价昂贵。对于具有这样特点的数据流数据，处理时的资源消 耗成为了主要的性能瓶颈。对于计算资源的消耗，为了适应数据流快速流动的特 点，数据流处理过程必须具有较低的时间复杂度，才能在接下来的数据流数据填 满缓冲区造成溢出之前完成数据的处理。对于存储资源的消耗，一般数据流经过 处理后，除非有其特殊价值，否则不进行保存，这主要是因为系统存储资源有限 而使用低一级的辅存会增加额外的i o 处理时间。另外为了和数据流模型相适应， 对应的数据挖掘算法需要能够一遍扫描样本子集就能有效地、快速地进行学习。 另外和现实数据相关的数据流还有一些不能忽略的性质，例如数据分布可能随时 间变化而改变等，这就需要对一定时间内子样本学习的结果进行更新，这样的算 法才能自适应数据分布的变化。相对于数据库上的数据挖掘算法，数据流的算法 要求时空复杂度小，但不要求得到最优解只要求得到