（计算机科学与技术专业论文）异构分布式数据流分类方法研究.pdf

i“嚣歹llll、 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 签名：盐必日期：么细：堑丝 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名：毖导师签名： 。、 摘要 摘要 异构分布式数据流( h e t e r o g e n e o u sd i s t r i b u t e dd a t as t r e a m ) 是指相互联系的 多个数据流，其数据来自地理上分布的数据源，且各数据源观测不同的属性集。 目前，异构分布式数据流的应用越来越广泛( 如传感器网络，进程控制等) 。从异 构分布式数据流中提取知识的能力已变得相当重要。 从异构的分布式数据流中进行知识挖掘是一个重要的研究课题，面临着许多 挑战性的问题。首先，把多个节点的数据流传送到中心节点进行数据挖掘可以是 一种解决问题的方法，目前的研究尝试这样的思路，从研究角度上对于更加深入 地了解分布式数据流的挖掘特点是有意义的。其次，从技术上这种集中式的数据 传输是不可行的，数据流的集中式挖掘缺点是显而易见的：由于数据传输量大可 能导致通讯问题、由于中心节点的处理数据量大可能导致计算瓶颈等。 本文针对这些问题，提出了两种方法分类异构分布式数据流，即基于 b o o s t i n g 的v h d d s 分类方法和基于s p r i n t 的v h d d s 分类方法，前者通过 b o o s t i n g 技术来识别“h a r d 数据( 即局部难分类数据) ，局部节点并行学习、更 新模式、传输h a r d 数据索引到中心节点；中心节点根据h a r d 数据索引，收集h a r d 数据，更新中心模式。h a r d 数据相对较少，因此该算法能有效分散计算量，降低 通讯负载。实验结果表明：我们的算法降低了通信量，整体上具有很高的分类精 度。后者采用一种分布式的挖掘架构和分块的方式处理数据流，针对局部站点的 每块数据，在中心站点上建立相应的全局分类器。在分类器的训练过程中，各局 部站点负责执行属性表分裂，计算各自的局部最佳分裂方案，并将其送往中心站 点。中心站点根据局部最佳分裂方案确定当前节点的最终分裂方案，生成相应的 决策树节点，并将最终的分裂方案传给局部站点。局部站点与中心站点之间只传 输少量用于决策的信息，不需要传输原始数据，从而有效降低了通信负载。 关键词数据挖掘；数据流；分布式数据流；异构分布式数据流 北京工业大学工学硕士学位论文 i i a b s t r a c t a b s t r a c t h e t e r o g e n e o u s d i s t r i b u t e dd a t as t r e a mr e f e r st oi n t e r r e l a t e dm u l t i p l ed a t as t r e a m s w h o s ed a t ac o m ef r o mg e o g r a p h i c a l l yd i s t r i b u t e dd a t as o u r c e sa n de a c hd a t as o u r c e o b s e r v e sd i f f e r e n ts e to fa t t r i b u t e s c u r r e n t l y , t h ea p p l i c a t i o no fh e t e r o g e n e o u s d i s t r i b u t e dd a t as t r e a m si sm o r ea n dm o r ep e r v a s i v e ( s u c ha ss e n s o rn e t w o r k s ，p r o c e s s c o n t r o l ，e t c ) s o ，t h ec a p a c i t y o f e x t r a c t i n gk n o w l e d g e f r o m h e t e r o g e n e o u s d i s t r i b u t e dd a t as t r e a m sh a sb e c o m ev e r yi m p o r t a n t m i n i n gk n o w l e d g ef r o mh e t e r o g e n e o u sd i s t r i b u t e dd a t as t r e a mi sa ni m p o r t a n t r e s e a r c ht o p i ca n df a c e sm a n yc h a l l e n g i n gi s s u e s f i r s to fa l l ，s e n d i n gd a t ao fa l ll o c a l n o d e st oc e n t r a ln o d et om i n ec a nb eas o l u t i o nt ot h ep r o b l e m ，t h ec u r r e n ts t u d y a t t e m p t st h i sl i n eo ft h o u g h t ，i ti sm e a n i n g f u lf o rm o r ei n d e p t hu n d e r s t a n d i n go f c h a r a c t e r i s t i c so fd i s t r i b u t e dd a t as t r e a mm i n i n gf r o mt h ev i e wo fr e s e a r c h s e c o n d ， s u c hac e n t r a l i z e dd a t at r a n s m i s s i o ni sn o tf e a s i b l e t e c h n i c a l l y d r a w b a c k so f c e n t r a l i z e dd a t as t r e a mm i n i n ga r eo b v i o u s ：l a r g eq u a n t i t yo fd a t at r a n s m i s s i o nm a y l e a dt oc o m m u n i c a t i o np r o b l e m s ；i tm a yl e a dt ot h ec a l c u l a t i o nb o t t l e n e c kd u et o c e n t r a ln o d ep r o c e s s i n gl a r g ev o l u m e so fd a t aa n ds oo n a c c o r d i n gt ot h e s ep r o b l e m s ，t w om e t h o d si nt h i sp a p e ra r ep r o p o s e dw h i c ha r e v h d d sc l a s s i f i c a t i o nm e t h o db a s e do nb o o s t i n ga n dv h d d sc l a s s i f i c a t i o n m e t h o db a s e do ns p r i n t t h ef o r m e ra d o p t sad i s t r i b u t e ds t r e a mp r o c e s s i n g a r c h i t e c t u r e ；i d e n t i f i e s ”h a r d ”d a t ab yb o o s t i n gt e c h n o l o g y , l o c a ln o d e sl e a r na n d u p d a t em o d e l si np a r a l l e l ，c e n t r a ln o d ec o l l e c th a r dd a t aa c c o r d i n gt ot h e i ri n d i c e sa n d u p d a t ec e n t r a lm o d e l s b e c a u s eh a r dd a t aa l es m a l lr e l a t i v e l y , i ti s e f f e c t i v ei n d i s p e r s i n gt h ec o m p u t a t i o na n dr e d u c i n gt h ec o m m u n i c a t i o nl o a d t h ee x p e d m e n t a l r e s u l t ss h o wt h a t ：o u ra l g o r i t h mc a nr e d u c et h et r a f f i c ，h a sh i g ha c c u r a c yo f c l a s s i f i c a t i o n t h el a t t e ra d o p t sad i s t r i b u t e ds t r e a mp r o c e s s i n ga r c h i t e c t u r e l o c a l n o d e sc a l c u l a t es p l i tp o i n t sa n dp e r f o r mas p l i ti np a r a l l e l ，t h e ns e n dt ot h ec e n t r a ls i t e t h ec e n t e rs i t ed e t e r m i n et h ef i n a ls p l i to ft h ec u r r e n tn o d e i to n l yt r a n s f e r sas m a l l a m o u n to fi n f o r m a t i o nf o rd e c i s i o n m a k i n g ，n o tt ot r a n s m i tr a wd a t ab e t w e e nl o c a l s i t e sa n dt h ec e n t r a ls i t e ，t h u se f f e c t i v e l yr e d u c i n gt h et r a f f i cl o a d k e y w o r d sd a t am i n i n g ；d a t as t r e a m ；d i s t r i b u t e dd a t as t r e a m ；h e t e r o g e n e o u s d i s t r i b u t e dd a t as t r e a m i i i 北京工业大学工学硕士学位论文 i v 目录 目录 摘要i a b s t r a c t i i i 第1 章绪论1 1 1 数据挖掘技术简介一1 1 2 研究背景2 1 3 研究内容4 1 4 论文的结构安排4 第2 章分布式数据流挖掘7 2 1 分布式数据流定义一7 2 2 分布式数据流挖掘面临的挑战8 2 3 分布式数据流处理框架9 2 4 研究现状10 2 5 分布式数据挖掘系统1 4 2 6 本章小结l5 第3 章基于b o o s t i n g 的v h d d s 分类方法一1 7 3 1 问题描述及相关定义1 7 3 2v h d d s 分类算法框架1 8 3 - 3b o o s t i n g 技术介绍1 8 3 4 算法设计一2 0 3 5 算法分析2 1 3 6 实验及讨论一2 2 3 7 本章小结2 5 第4 章基于s p r i n t 的v h d d s 分类方法2 7 4 1s p r i n t 算法简介一2 7 4 2 算法过程2 7 4 2 1 局部站点上的数据处理2 8 4 2 2 中心站点上的决策树生成3 2 4 3 寻找连续属性最佳分割点方法的改进3 4 4 4 实验分析3 5 4 5 本章小结3 7 结论3 9 论文的主要工作3 9 展望一4 0 参考文献4 l 攻读硕士学位期间发表的学术论文4 5 致谢一4 7 北京工业大学工学硕士学位论文 第1 章绪论 1 1 数据挖掘技术简介 第1 章绪论 近十几年来，随着数据收集和存储技术的发展，在社会生产生活的各个领域 产生了大量的数据信息，如银行每天的巨额交易数据，人类在对太空的探索中所 产生的数据等，但是，从这些海量数据提取有用的知识具有极端的挑战性。有时 数据的非传统特性意味着不能使用传统的方法进行挖掘，即使数据集相对较小。 另一方面，使用现有的数据分析技术解决不了需要解决的问题，因此，需要研究 新的技术。 数据挖掘是_ l , - j 技术，它融合了传统的数据分析方法和处理大量数据的复杂 的算法。但是面对越来越多的海量数据，人们已不满足传统的数据库查询技术， 而是希望提供更高层次的数据分析功能，自动和智能地将待处理的数据转化为有 用的信息和知识，以便更好地做出理想的决策、预测未来的发展趋势。于是，数 据挖掘技术n 一1 便成为当前研究的一项重要课题。 对于传统的数据挖掘算法来说，样本数据过小会导致学习模型的过度拟合 ( o v e r f i t t i n g ) ，样本数据过大又导致学习时间迅速增加到不可容忍的地步璐1 。因 此，样本容量已成为制约其准确度和效率的一项主要限制。但是对于当前的很多 企业和组织来说，每天都会产生大量的数据，如电子商务网站、电信领域的服务 商或者科研机构、大型的零售超市等，每天数百吉比特( g b y t e s ) 的数据量十分常 见。因此，改进传统的数据挖掘算法，扩展传统的数据挖掘模型，使其可以应用 于数据流环境，从数据流中在线提取有用的信息，有着十分重要的意义和应用价 值。 处理数据流的挑战性在于怎样用一种及时有效的方式处理如此庞大的数据。 目前大多数文献所说的数据流( d a t as t r e a m ) 或称流数据( s t r e a m i n gd a t a ) 是指单 数据流。近年来，( 单) 数据流的挖掘得到了广泛的研究h 9 1 副，提出了许多有价 值的模型和算法。随着网络环境应用的普及，单一数据流的应用必然向着多节点 的分布式数据流方向转移。所谓分布式数据流( d i s t r i b u t e dd a t as t r e a m ) 是指相互 联系的多个数据流n3 l ，它们在逻辑上是统一的整体，但在物理上是分散的。各分 布式站点如果具有相同的属性集合则称之为同构，否则称为异构。从传统的静态 数据到单数据流，再到分布式数据流，数据挖掘技术发展得越来越强大，但也面 临很多挑战，它是随着应用不断发展的技术。 常用的数据挖掘算法有以下几类：分类算法、聚类算法、关联规则挖掘算法、 序列分析算法等。 北京工业大学工学硕士学位论文 1 2 研究背景 异构分布式数据流是异构分布式数据随时间不断堆积的流，时间戳可作为异 构站点间数据关联的依据。异构分布式数据流的应用很广泛，如因特网提供了各 种各样的数据流来源，像n a s d a q 、雅虎财经和c n n 财经这样的站点提供接近实 时的股票数据；成千成万的w e b 用户创造了另一种因特网数据流，这种数据流被 称作“点击数据流”，它实质上是各种因特网用户在特定站点上的交互活动的日 志。通过分析点击数据流可以捕获有关w e b 用户的有价值的信息，这在电子商务 的扮演着一个重要角色。 知识发现( k n o w l e d g ed i s c o v e r yi nd a t a b a s e ，k j ) d ) 技术具有广泛的应用，这 不仅能对过去的数据进行查询，并且能够找出过去数据之间的潜在联系，进行更 高层次的分析，以便更好地做出理想的决策、预测未来的发展趋势等。通过数据 挖掘，有价值的知识、规则、或高层次的信息就能从数据库的相关数据集合中抽 取出来，从而使大型数据库作为一个丰富、可靠的资源为知识的提取服务。然而， 当应用于数据流时，k d d 面对实践和理论上的双重挑战。在很多情况下，挖掘数 据流要求立刻决策。例如，一触即发地检测路由到私有网络中的恶意数据包对识 别可能的攻击很关键。数据流必须被迅速挖掘，任何要求在中心数据库上存储统 计数据的离线应用都不能用这样的方式提取知识。 处理和集成大量异构数据流更具挑战。很多应用( 像进程控制、传感器网络) 包含多个数据流，有时，来自各种异构源的数据常常被分散存储在不同的数据站 点，但是，数据迅速堆积，不久便大得难以交换，这使得更加难以操作。例如， 由e o s d i s 管理的数据主要来自e o s d i s 的八个分布式存档中心，每个存档中心提 供的数据属于一个特殊的自然学科，这些存档中心共同提供了一个地理上分散但 逻辑上集成在一起的数据库以便支持交叉学科的研究。如果我们要集中数据，那 么从多个存档中心挖掘数据几乎是行不通的。因为战略上的决策经常要求以一个 及时的方式提取这样的信息。 我们再来考虑一个分布式的传感器网络，各种传感器部署到系统中，收集不 同方面的信息，如压力，温度，湿度等，这是一种异构的分布式数据流，由于传 感器是能源受限的，要得到系统的全局状态，必须进行分布式挖掘。这种异构的 分布式数据流，一般来讲数据属性之间具有某种依赖关系，由于属性之间具有某 种依赖关系，使得单节点上无法捕获交叉条件关系。如表所示，表1 - 1 是在节点 a 上采集的压力流，表卜2 是在节点b 上采集的温度流，压力流和温度流共同表 示系统的一个完整的状态。当压力和温度满足某种要求时表示系统状态正常，表 卜3 是集中后的数据流。 2 表卜1 压力流 第1 章绪论 表1 - 2 温度流 t a b l e1 - 1p r e s s u r es t r e a mt a b l el - 2t e m p e r a t u r es t r e a m 时间压力合格 11 0 0 y 21 1 0 n 39 0 n 48 0n 51 2 0y 61 3 0y 77 0n 81 5 0y 时间温度合格 15 0y 24 0n 35 0n 46 0n 55 5y 66 0y 78 0n 87 0y 表1 - 3 合成流 t a b l e1 - 3c o m p o u n ds t r e a m 时间压力温度 合格 11 0 05 0y 21 1 04 0 n 39 05 0n 48 06 0n 51 2 05 5y 61 3 06 0 y 7 7 08 0n 81 5 07 0 y 图1 - 1 压力流上的局部分类器 f i g u r el 一1l o c a lc l a s s i f i e ro np r e s s u r es t r e a m 图1 - 2 温度流上的局部分类器 f i g u r e1 - 2l o c a lc l a s s i f i e ro nt e m p e r a t u r es t r e a m 3 图1 - 3 集中式挖掘出的全局模式 f i g u r e1 - 3g l o b a lm o d e lo nc e n t r a ln o d e 北京工业大学工学硕士学位论文 我们分别在这三种流上挖掘模型，结果如图所示，图i - i 是在压力流上挖掘 的局部分类器，图卜2 是在温度流上挖掘的局部分类器，图1 - 3 是集中式挖掘的 全局模式。结果发现，节点a 上错误率1 2 5 ，节点b 上的错误率为3 7 5 ，测 试错误的数据已用粗体标出。这些数据在单节点上无法正确捕获，这是因为单节 点上无法捕获交叉条件关系。而源数据由于传输负载等原因，不可能采取集中式 数据挖掘。从分布式的异构的数据流中学习模型，并保证精度控制和最小的通讯 负载，仍然是有待解决的问题。 1 3 研究内容 目前，异构分布式数据流的应用越来越广泛( 如传感器网络，进程控制等) 。 从异构分布式数据流中提取知识的能力已变得相当重要。然而异构分布式数据流 的分类研究工作刚刚起步，当前的分类方法主要采用集中式的处理架构，这种方 法具有很多弊端： ( 1 ) 由于集中式处理容易造成通信负载过大，中心节点计算量大等原因，在 许多情况下，将所有数据集中在一起进行分析往往是不可行的。 ( 2 ) 分布式数据流挖掘应该是数据挖掘技术与分布式计算的有机结合，集中 式的挖掘方式没有充分运用这一特点，将原本可以并行处理的工作变成了串行处 理，增加了系统的传输负载和计算量，并且可能造成关键传输路径的瓶颈问题。 针对上述两个关键问题，本论文做了如下工作： ( 1 ) 提出了基于b o o s t i n g 的v h d d s 分类方法，它采用分布式挖掘架构，充分 利用分布式计算的能力对相关的数据进行分析与综合。所有局部节点并行学习， 并将学习到的局部模式和少量“h a r d 样本传输到中心节点。在中心节点上学习 “h a r d 数据蕴含的模式。从而保证了精度控制和最小的通讯负载。 ( 2 ) 提出基于s p r i n t 的v h d d s 分类方法，它针对异构数据流的分布特点，采 用具有高并行性、强可伸缩性的s p r i n g 算法来进行数据挖掘中的分类研究。 本文是在已有的算法基础上进行改进，从而将其应用到异构分布式数据流， 提高对异构分布式数据流的分类精确度和效率，进而建立改进算法的原型系统， 并通过实验验证算法的可行性。这将是本论文的研究重点。 1 4 论文的结构安排 本论文共分四章，按以下方式进行组织： 第1 章为绪论，首先介绍了数据挖掘定义，从传统的静态数据挖掘到单数据 流上的数据挖掘再到分布式数据流挖掘，数据挖掘的应用范围越来越广，面临的 4 第l 章绪论 挑战越来越多。接着介绍了本文的研究意义及主要的研究内容。 第2 章阐述了分布式数据流挖掘的相关问题，包括分布式数据流的定义、分 布式数据流挖掘面临的挑战、分布式数据流处理框架及其研究现关，最后介绍了 一个分布式数据挖掘系统b o d h i 第3 章针对异构分布式数据流环境提出了基于b o o s t i n g 的v h d d s 分类方法， 首先给出了问题描述及相关定义，接着介绍了v h d d s 分类框架、算法设计和算法 分析，最后是实验及讨论。 第4 章提出了基于s p r i n t 的v h d d s 分类方法，介绍了算法在局部站点和中 心站点上的处理方法，以及寻找连续分割点的改进方法，并给出了实验分析。 最后部分归纳了本文的研究工作，总结了文章的内容，提出了论文所做的工 作，并对今后的工作进行了展望。 5 北京工业大学工学硕士学位论文 6 第2 章分布式数据流挖掘 第2 章分布式数据流挖掘 2 1 分布式数据流定义 分布式数据流( d i s t r i b u t e dd a t as t r e a m ) 是指相互联系的多个数据流，其 数据来自于地理上分布的数据源或不同的自治单元，其本身非常适合于分布式处 理。随着技术的发展，分布式数据流的环境越来越普遍。如图2 - 1 所示的分布式 传感器网络，它包含多个节点，每个节点负责监测不同的信息( 如压力、温度或 者湿度) 。这样，每个节点监测的数据随着时间形成特定指标的数据流( 如压力流、 温度流和湿度流) ，而某一时刻系统的全局状态需要多个节点流共同来表示，各 节点处于不同的地理位置，但又相互关联，这就是一个典型的分布式数据流。 图2 - 1 异构分布式数据流 f i g u r e2 - 1d i s t r i b u t e dh e t e r o g e n e o u sd a t as t r e a m s 分布式数据流挖掘是数据流挖掘技术与分布式计算的有机结合，主要用于分 布式环境下的数据模式发现。 分布式数据流挖掘是一个快速发展领域，受到国内外的广泛关注。它考虑两 种分布式数据同构和异构。在同构的分布式环境下，每个站点观测相同的 属性集，即一个实体( 或事件) 的全部信息集中在一个局部节点上，每个局部节点 上收集整个系统的一个数据子集，所有局部节点上数据的并集构成整个系统的完 整数据集。在异构的分布式环境下，每个站点观测不同的属性集。即一个实体( 或 事件) 的完整信息分布在不同的局部节点上。每个局部节点上观测的数据是相关 实体( 或事件) 的部分信息。同构和异构有时也被称为水平和垂直划分。图2 2 、 图2 - 3 解释了这两种情况，在同构站点的情况，每行定义了一个特有的实体，然 而在异构的情况下，同一个实体的观测属性被分布在不同的位置。因此异构的情 况下必须预先定义一些方法来关联同一实体的不同属性，行索引和关键字可用于 7 北京工业大学工学硕士学位论文 识别不同站点上不同行之间的对应关系，在数据流环境下，可以时间戳来关联。 x l x l 1 - 2 1 6 1 5 1 4 1 6 1 5 x 2 2 3 2 8 2 6 2 5 2 4 2 7 x l 2 3 2 8 2 6 2 。5 2 4 2 7 站点 1f 站点b 1 2 1 6 1 5 1 - 4 1 6 1 5 站点a x 2 3 1 3 4 3 2 3 4 3 3 3 5 x l 1 2 1 6 1 5 1 4 1 6 1 5 站点c 图2 - 2 同构分布式站点 f i g u r e2 - 2h o m o g e n e o u sd i s t r i b u t e ds i t e s x 2 2 3 2 8 2 6 2 5 2 4 2 7 x 2 2 3 2 8 2 6 2 5 2 4 2 7 = = j e 站点b x 3 3 1 3 4 3 2 3 4 3 3 3 5 x l 1 2 1 6 1 5 1 4 1 6 1 5 x 2 2 3 2 8 2 6 2 5 2 4 2 7 站点c 图2 - 3 异构分布式站点 f ig u r e2 - 3h e t e r o g e n e o u sd is t r i b u t e dsit e s 2 2 分布式数据流挖掘面临的挑战 x 2 2 3 2 8 2 6 2 5 2 4 2 7 x 3 3 1 3 4 3 2 3 4 3 3 3 5 在网络环境下，不仅数据流的产生源分布在不同的网络节点，而且数据的传 输路由以及目标地址也具有分布性。很多时间关键的应用像传感器网络、网络入 侵检测和欺诈性交易检测产生像“流一样的数据。它要求基于观测的新数据立 刻做出决策。一般来说，这样的流数据在更多的新数据到达之前的短时间内有效。 ， 因此，从异构的分布式数据流中进行知识挖掘是一个重要的研究课题，面临着许 多挑战性的问题。 ( 1 ) 作为分布式数据流挖掘的基础，( 单) 数据流提出的问题对分布式数据流 来说也同样需要面对。数据流的潜在无限性和达到速率的不可预测性等，使得传 统的数据挖掘理论与算法不可能被直接利用。因为传统的处理大数据样本的多遍 扫描或者非在线的处理方式显然不能来处理随时间变化的动态数据流。目前研究 表明，数据流挖掘采用增量式算法是必须的，即随着流数据的到达不断更新模式。 当然，分布式数据流挖掘的增量式模式更新问题，面临着新的挑战：同一时间或 8 第2 荦分布式数据流挖掘 者时间段，多个节点都可能有数据到达，而且速率可能差异很大。因此，如何准 确而高效的对全局模式进行增量式更新需要有新的构架和模型来支撑。 ( 2 ) 集中式解决分布式数据流的模式挖掘问题是不现实的。由于分布式数据 流的每个节点的局部数据流的数据达到速率都是不可控的，假如设想将所有节点 的到达数据都及时送到一个中心节点来统一处理，那么网络传输时间和对中心节 点的存储需求都是无法克服的问题。因此，研究分布式的模式更新策略是必需的， 需要从可用的模型和应用构架到关键的问题( 如局部模式与全局模式的融合) 的 解决算法等方面进行深入研究。另外，对于大规模的分布式数据流来说，为了在 线实时跟踪数据的变化，采用“准精确 挖掘手段也是必需的，于是提高挖掘精 度成了一个不可回避的问题。 ( 3 ) 为了提高数据流的挖掘精度，近年来人们开始关注数据流的集成学习 ( e n s e m b l el e a r n i n g ) 模型和方法研究n 叭n 引。集成学习需要同时维护多个模式， 这样可以有效避免高速流动的数据带来的概念颠簸( 即由于只保留最新的一个， 可能使最近几个常出现的模式频繁切换) ，也可以改善传统的非集成学习对样本 数据的过分拟合的情况。对于分布式数据流而言，这样的问题存在而且更复杂。 虽然，目前有些文献提到了相关问题，但是研究还是策略性的。因此，利用集成 学习方法来解决分布式数据流的模式挖掘问题有很好的研究价值。 2 3 分布式数据流处理框架 很多系统采用集中式模式挖掘分布式数据流，如图2 4 所示。在这种模式下， 分布式数据流被集中到一个中心结点，在中心结点上进行数据挖掘。这种计算模 式受到如下几个方面的限制，首先，数据流的集中式挖掘导致响应时间长，除中 心节点外，其它节点的计算资源也是可利用的，而集中式数据挖掘没有充分利用 这些资源。集中式数据收集导致关键通讯链路的严重阻塞，如果这些通讯链路已 经限制了网络带宽，那么网络i o 可能成为性能瓶颈。而且，在能源受限的领域， 比如传感器网络，就会因过量的数据通讯导致过量的能源消耗。 为缓解以上提到的问题，c h e m i a c km 、b a l a k r i s h n a nh 、 b a l a z i n s k am 等 学者在其文章s c a l a b l ed i s t r i b u t e ds t r e a mp r o c e s s i n g 中，讨论了大规模的分布式 流处理系统设计中面临的架构问题，提出了一种分布式模型m 1 ，如图2 5 所示。 在这种分布式流挖掘模型中，不用集中数据到中心节点，分布式的计算节点执行 部分计算，同时当需要时传输计算得到的局部模式到中心结点，这样的架构有几 个优点：首先，通过使用分布式的计算节点( 这些结点是并行计算的) ，降低了响 应时间；第二，节点之间只传输局部模式，不传输源数据，因而降低了通信量， 节省了大量的时间和空间开销，在能源受限的领域可以降低能源消耗。 9 北京工业大学工学硕士学位论文 2 4 研究现状 图2 - 4 集中式流处理架构 f i g u r e2 - 4c e n t r a l i z e ds t r e a mp r o c e s s i n ga r c h i t e c t u r e il o o a l m 2 0 s t i 匦霉囤匝驷 图2 - 5 分布式挖掘架构 f i g u r e2 - 5d i s t r i b u t e ds t r e a mp r o c e s s i n ga r c h i t e c t u r e 【1 7 】 大部分分布式数据挖掘文献考虑同构的数据站点，同构站点的分布式数据挖 掘包括合并来自不同站点的模型。几种集成模型已经应用于同构分布式数据挖掘 环境。b a g g i n g 方法是同构d d m 环境下合并模型的候选方法之一，其观点在文章 1 8 中有具体讲述。和b a g g i n g 方法一样，s t a c k i n g 也能被扩展用于合并分布式 1 0 第2 苹分布式数据流挖掘 环境下的局部模式，这些合并多个模型的技术在文章 2 9 中通过实验给出了相关 评价。 元学 - - j 脚卫l 矧提供了挖掘同构分布式数据的另一类技术。这种技术跟b a g g i n g 和s t a c k i n g 方法具有相似之处。在这种技术中，局部数据站点引用有监督学习思 想来学习分类，然后将局部学习分类生成的数据集成到m e t a - l e v e l 级后，再进行 分类学习。m e t a - - l e a r n i n g 学习过程主要包括以下三个步骤：1 ) 在每个站点使用 分类学习算法生成基分类器；2 ) 将基分类器集中到一个中心站点上，用每个基分 类器产生的预测信息和一个独立的数据效验序列来生成元数据：3 ) 由元一级数据 产生最终分类器。其思想如图2 6 所示。 m e t a - l e a m i n g 中，在基分类器级使用的算法可以是i d 3 、c 4 5 等传统算法， 在m e t a - l e v e l 级使用的集成算法主要有b a g g i n g 、b o o s t i n g 、s t a c k i n g 等三种。基 分类器输出的集成方式有以下三种： ( 1 ) 投票( v o t i n g ) ：基于少数服从多数原则，有绝对( 相对) 多数投票和加权投票 方式。 ( 2 ) 决策( a r b i t r a t i o n ) ：指定特殊的“决策者 ，当基分类器的输出无法达成一 致时，采用“决策者的输出。 ( 3 ) 结合( c o m b i n i n g ) ：使用相关的先验与领域知识指导各输出的集成。 图2 - 6 元学习的具体过程 f i g u r e2 - 6c o n c r e t ep r o c e s so fm e t a - l e a r n i n g 元学习的优点： ( 1 ) 在基学习阶段，各个结点可以自主地选择合适的学习算法来生成局部的基分 北京工业大学工学硕士学位论文 类器。与此同时，各结点间不存在任何通讯与同步开销，因此系统效率较高。 ( 2 ) 在元学习阶段，由于系统可灵活采用各种集成策略，因此最终生成的元分类 器具有较高的预测精度。 j a m 系统嘲1 是一个基于元学习的分布式数据挖掘框架，已用于银行领域欺诈 检测。 文章 31 中提出d c b ( d i s t r i b u t e dc o o p e r a t i v eb a y e s i a nl e a r n i n g ) 方法，该技术 考虑同构数据集，不同的贝叶斯代理并行评估目标分布的参数，p - l e a r n e r 合并 它们输出结果得到显著改善的评估。代理和p - l e a r n e r 是基于g i b b s 算法的概率 版本。 碎片方法( f r a g m e n t e d a p p r o a c h ) 在文章 2 2 中被提出，这个方法在每个分布 式数据源产生一个简单的最好的规则，使用某些标准将这些规则划分等级，选出 等级较高的一些规则形成规则集。在文章 2 4 中，作者报告了一项技术，这项技 术用一种分布式的方法从发现的知识中产生一个贝叶斯网络。 f d m ( f a s td i s t r i b u t e dm i n i n g ) 算法用于从分布式同构数据集中挖掘关联规 则。f d m 指出，在分布式环境中，全局大的项目集在一个或多个站点上也是局部 大的。它在局部和全局大项目集之间考察这种关系以便最小化通讯负载。f d m 要 求用o ( s ) 量级的信息通讯量( s 是站点数) 确定一个候选集是否是大的。 针对问题分解和局部模型选择的一项技术在文章 2 5 中提出，这种方法首 先在局部数据站点学习衰退模型，然后鉴别出符合局部模型的数据子集。这个信 息用于把数据划分成不连接的不同子集，下一步，它学习分布函数以便识别合适 的局部模型。这种方法用于分析农业数据。作者给出了这种技术相对单个全局模 型在性能上的实质改善。 同构分布式数据使用的基于集成学习的分类方法并不适用于异构分布式数 据。由于在分布的数据站点上的数据是异构的，从局部数据挖掘结果中不能得到 系统的全部信息。p r o v o s t 和b u c h a n a n 于1 9 9 5 年提出通过将大问题分解为小问 题来实现基于特性空间的异构划分，但这种方法要求站点间必须具有相关性。 w o r l d 系统使用一种“激活传播方法 来进行异构数据的概念学习：首先计算各 个站点数据属性的主要分布，然后分布信息在个站点问传播，并根据前几阶统计 近似值来确定概念空间中具有强相似性的属性值n 引。但当概念学习要求使用高阶 统计信息时，这种方法并不适用。 a g r a w a l 等给出了分布式数据流的概念，并建立了g a t e s 原型系统。g h o t i n g 等人给出了分布式数据流的信息交换方法和评估策略。文章 2 7 从诱导偏见的角 度讨论了异构数据站点的学习。该工作指出属性空间的划分可通过将问题分解成 更小的子问题来解决。 文章 3 0 考察了通过传输部分数据的方法处理异构和同构数据的问题，作者 1 2 第2 章分布式数据流挖掘 定义了一个包含通讯代价和计算代价的代价函数，问题简化成编程问题从而使得 传统技术得以应用。 在d d m 的实际应用中，经常不能充分存取异构分布式数据集的公共值，为了 推广应用d d m ，1 9 9 8 年k a r g u p t a 和p a r k 等人提出了汇集型数据挖掘系统( c d m ) n 。 它使用正交基函数进行局部分析，解决通常的局部数据分析方法不能正确生成构 造全局数据模型所需要的局部模型的问题。c d m 是一种在分布式垂直划分特征空 间中进行归纳学习的新方法，其基本思想是将待学习的函数用一组合适的基函数 按分布式方式表示，整个c d m 算法与不同站点发现模式的特定归纳学习算法无 关。允许各数据点选择不同的学习算法，c d m 能够生成整个数据集的全局分布式 模式，不必假定按照各站点上特征空间的特殊划分方式，将整个建模问题进行分 解。 k a r g u p t a 于2 0 0 0 年提出将c d m 技术拓展到决策树领域，提出了分布式决策 树生成算法。该算法先在各分站点采用b o o s t i n g 算法建立局部模型，并确定 出置信度低于某事先设定阈值的数据为交叉项；然后将局部模型和交叉项数据传 送到总站点运用b o o s t i n g 算法进行集成。由于b o o s t i n g 算法得出的分类模型难 于理解，分布式决策树运用傅立叶技术将各站点模型转化为决策树表示形式。最 后由竞争策略，若事例戈在某个站点模型上的分类置信度大于设定阈值且最高， 则选用该分站点决策树进行预测；否则，采用全局模型进行预测。基于c d m 思想 的分布式决策树生成算法首先采用b o o s t i n g 算法来构造局部和全局站点模型， 然后采用t c f s ( t r e ec o n s t r u c t i o nf r o mf o u r i e rs p e e ) 算法将得到的模型转化为更 易于理解的决策树表示形式。该算法的优点是：( 1 ) 产生的分类规则直观易懂； ( 2 ) 可以直接从函数的傅立叶频谱计算出各属性的信息增益，运算速度较快；( 3 ) 函数的傅立叶系数随阶数增长呈指数衰减形式，即只选用几个低阶的傅氏系数即 可近似表征决策树的傅氏频谱。该算法的不足之处在于仍然没有产生一个整体的 用于分类预测的模型。 c h e ne ta l ，给出了一种集合方法挖掘来自分布式异构网络日志数据流的贝 叶斯网络n 引。在他们的方法中，他们在每个站点上用局部数据学习局部贝叶斯网 络，然后，每个站点鉴别可能是局部和非局部变量结合迹象的观测数据，并且传 输这些观测数据的一个子集到中心站点。用来自