（计算机科学与技术专业论文）分布式环境下的支持向量数据描述外壳算法.pdf

独创性声明 m l l l l i 洲1 1 1 1 l j l l l f l l l l l l y 17 8 8 3 6 5 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 签名： 至鲤旦垒 日期：鲨! ：笸：! 口 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名：圣：臼臼乌导师签名：主细日期：独也：z 口 - - 摘要 摘要 对分布式数据流的分析与挖掘正与日俱增地在众多领域变得十分重要，如网 络流分析和金融交易分析等。在分布式环境中，将所有数据都传输到一个节点进 行处理是不现实的；更加合理的方法是各个局部节点从数据中提取的最具代表性 的精华部分，进而基于这些精华部分整合学习成为全局模型。 本文分析了支持向量机( s v m ) 在分布式环境下进行模型表示和集成的利弊， 支持向量的核心作用及其在模型集成时带来的问题和风险，以及在不同分布式结 构下具体的实现方法。针对分布式环境下数据分析模型集成的问题和特点，基于 支持向量机理论和支持向量数据描述( s v d d ) 算法，本文提出了一种基于支持向量 机理论的支持向量数据描述外壳算法( s v d d s ) ，构造的外壳根据数据的分布形态， 仅包含支持向量以及向内部延伸一定厚度的区域，实现了无需修改支持向量机算 法即可适用于分布式环境下的全局模型。 本算法在描述数据的外围轮廓的同时，通过控制系统的参数，保留轮廓以内 的潜在支持向量，去除对未来的模型集成没有影响的数据，构成描述数据特性的 有一定厚度的潜在支持向量的超球壳。它平衡了模型准确性与潜在支持向量数 量，权衡了全局模型集成的风险与总体传输负载，达到了用尽量少的数据准确表 达模型，从整体上降低了未来的模型集成的风险和总体传输负载的目的。 本算法适用于在众多典型分布式结构下进行模型集成。对典型情况的比较性 实验表明，该算法能在较好保持全局精确度的同时，显著地降低总体传输负载。 关键词数据描述外壳；模型集成：支持向量；分布式环境 a b s t r a c t a b s t r a c t d i s t r i b u t e dd a t as t r e a m sm i n i n gi si n c r e a s i n g l yd e m a n d e di nm o s t e x t e n s i v ea p p l i c a t i o nd o m a i n s ，1 i k ew e bt r a f f i ca n a l y s i sa n df i n a n c i a l t r a n s a c t i o n s i nd i s t r i b u t e de n v i r o n m e n t s ，i ti si m p r a c t i c a lt ot r a n s m i t a lld a t at oo n en o d ef o rg l o b a lm o d e l i tisr e a s o n a b l et oe x t r a c tt h e e s s e n t i a lp a r t so ft h e1 0 c a lm o d e l so fs u b o r d i n a t en o d e s ， t h e r e b y i n t e g r a t i n gi n t ot h e9 1 0 b a lm o d e l t h i sp a p e ra n a l y z e st h em o d e ld e s c r i p t i o na n di n t e g r a ti o no fs u p p o r t v e c t o rm a c h i n e s ( s v m ) i nd i s t r i b u t e de n v i r o n m e n t s t h ee s s e n t i a lr 0 1 eo f s u p p o r tv e c t o r sa n dt h ep r o b l e m sa n dr i s k st h e r e o ff o rt h em o d e l i n t e g r a t i o na n dt h et y p i c a li m p l e m e n t a t i o ni s s u e si nt h ep r a c t i c a l d i s t r i b u t e de n v i r o n m e n t sa sw e l l i nt h isp a p e r ，b a s e do nt h es v mt h e o r ya n dt h es u p p o r tv e c t o rd a t a d e s c r i p ti o n( s v d d )a l g o r it h n l ，a na p p r o a c hn a m e ds u p p o r tv e c t o rd a t a d e s c r i p t i o ns h e l l ( s v d d s ) a l g o r i t h mi sp r e s e n t e dt os o l v et h ei s s u e so f m o d e li n t e g r a t i o ni nd i s t r i b u t e de n v i r o n m e n t s i te n a b l e st h es v m a l g o r i t h i n sw i t hn om o d i f i c a t i o n st od i s c o v e rt h eg l o b a lm o d e l s t h es v d d sa l g o r i t h mc o n s t r u c t sas h e ll li k el a y e ra r o u n dt h ed a t a ， w h i c hd e s c r i b e st h eo u t l i n eo ft h ed a t aa n dr e t a i n sn e c e s s a r yp o t e n t i a l s u p p o r tv e c t o r s ， n a m e de x t e n d e dc a n d i d a t es u p p o r tv e c t o r s ，f o rf u t u r e m o d e li n t e g r a t i o n ， b ye x c l u d i n gt h ei n e f f e c t i v ed a t af o rt h em o d e l i n t e g r a t i o n i tt r a d e so f ft h eg e n e r a li z a t i o nr i s ko ft h e9 1 0 b a lm o d e l a f t e rt h ee x c l u s i o n sa g a i n s tt h et o t a lt r a n s m i s s i o n1 0 a d i ta c h i e v e st h a t w i t ht h ef a i r l yc o m p a c td e s c r i p t i o n so ft h el o c a lm o d e l s ，t h et o t a l t r a n s m i s s i o nl o a dg e t s1 0 w e r e dw h i l eb o t ht h eg e n e r a l i z a t i o nr i s ko ft h e g l o b a lm o d e lr e m a i n sa n dt h er i s ko fm o d e li n t e g r a t i o nw i t ht h ee x c l u s i o n s k e e p s1 0 w t h es v d d sa l g o r i t h mi sa p p l i c a b l et oa c c o m p l i s ht h eg l o b a lm o d e l i n t e g r a ti o ni nm o s tt y p i c a ld is t r i b u t e da r c h it e c t u r e 8 t h ee x p e r i m e n t s u p o nt y p i c a lc a s e ss h o wt h a tt h es v d d sa l g o r i t h me f f e c t i v e l yl o w e r st h e t o t a lt r a n s m i s s i o nl o a dw h i l et h eg l o b a la c c u r a c yd r o p sc o m p a r a t i v e l y 】jt t 】e i i i k e y w o r d sd a t ad e s c r i p t i o ns h e l l ：m o d e l i n t e g r a t i o n ：s u p p o r tv e c t o r ： d is t r i b u t e de n v i r o n m e n t 目录 目录 摘要i a b s t r a c t i i i 第l 章绪论1 1 1 背景与意义1 1 2 国内外研究现状2 1 2 1 分布式数据流的挖掘2 1 2 2 支持向量机( s v m ) 算法3 1 3 主要研究内容6 1 4 本论文的组织形式7 第2 章研究所依附的基础环境和方法9 2 1 数据流9 2 2 分布式数据流1 0 2 3 支持向量机( s v m ) 算法概述1 4 2 4 支持向量数据描述( s v d d ) 算法概述1 6 2 5 本章小结1 7 第3 章支持向量数据描述外壳( s v d d s ) 算法1 9 3 1 分布式环境下的s v m 模型的集成整合1 9 3 2 基本目的2 5 3 3 模型2 5 3 4 分析3 0 3 5 本章小结3 7 第4 章分布式环境下s v d d s 算法的应用3 9 4 1 分布式环境中的架构3 9 4 2 节点的结构4 1 4 3 本章小结4 4 第5 章实验与分析4 5 5 1 实验环境和条件4 5 5 2 实验内容和结果4 5 5 3 实验结果分析4 7 5 4 本章小结4 8 结论4 9 v 妻考文献5 1 附录 5 7 s v d d s 模型的一些属性及其证明5 7 登读篓士学位期间发表的学术论文6 7 致谢 品 v i 第l 章绪论 1 1 背景与意义 第1 章绪论 在现代信息社会中，数字化带来了数据的大爆炸。人们往往不再担心无法采 集到足够多的数据，而是关注怎样才能够准确、快速地对数据进行分析，从中获 取所需要的知识。数字化的变革带来的是海量的数据。这些数据每时每刻都在源 源不断地生成，分布在世界各地的众多感应器、探测器和终端设备上。如果不能 及时有效地利用这些数据，那么这些沉睡的数据浪费的不仅仅是资源，更是难以 挽回的知识。 传统的观点通常假设有待分析的数据是存储在某个介质上，在需要时可以不 止一次地读取。受制于对数据的假设，传统的数据挖掘算法通常也只是针对可多 次读取的数据而设计的，因此读写数据的次数也成为衡量特定算法性能的重要指 标。然而，这种假设并不适用于当今如泉涌般的数据源。 当今的数据往往不再是固定地存储在某种介质上，能够多次读取，而是实时、 动态而迅速地从数据源产生。这种数据称为数据流，其定义将在下文中给出。即 便是拥有最强大的计算能力和存储能力，将数据先存储下来再慢慢处理的离线 ( o f f l i n e ) 想法也是不切实际的。 为了能够实时处理数据，在线( o n l i n e ) 算法应运而生。这类算法不依赖于数 据的多次读取，而是强调只读取一次，随着每个新数据的到来，实时维护着自身 的状态，也因此称为增量式( i n c r e m e n t a l ) 算法。相比之下，传统的算法称为批 量式( b a t c h ) 算法。 增量式算法的成功，不仅是因为它们能够满足新型的源源不断的数据，更是 因为它们一次读取的性能优势。有了增量式算法，目前实际应用背景下的绝大多 数海量数据都可以实现只读取一次的实时分析。实时处理海量数据己成为数据挖 掘的必要能力。 随着互联网的迅速发展，网络变得无处不在。层出不穷的各种终端设备每时 每刻都在连接进入网络，互联和扩展是网络最重要的特点。局限于某部分的知识 是不够的，人们需要的是不断整合信息和知识，从更广大的范围把握全局。 这就需要把局部发现的知识进行整合，不断扩展延伸。因此，分布式环境下 的知识整合成为正日渐成为分布式数据挖掘的另一个必要能力。 传统的数据挖掘算法通常假设能够直接面对全部数据，而不是经过其它算法 处理过的“二手”数据。然而，这种假设并不适用于分布式环境下的知识整合。 北京t 业大学下学硕士学位论文 在分布式环境中，将所有数据都传输到一个节点进行处理是不现实的：更加 合理的方法是各个局部节点从数据中提取的最具代表性的精华部分，进而基于这 些精华部分进行整合学习。同时，精华部分的体积需要比较小，以便于网络传输。 如果一个传统的数据挖掘算法在独立环境下可以取得很好的效果，而不能将自身 的信息用比较小的精华部分来表示，或者必须依赖于直接读取全部数据，那么它 就很难应用于分布式环境。 因此，一种适合分布式环境的算法成为分布式环境下的数据挖掘的关键。这 种算法应该不仅能够从局部数据中提取精华部分，而且还能够只依赖于这些精华 部分整合成为全局模型。 1 2 国内外研究现状 1 2 1 分布式数据流的挖掘 单数据流的挖掘算法首先是从传统数据挖掘算法中迁移过来的，但需要根据 数据流的特点进行改造创新n 卫1 。d o m i n g o s 和h u l t e n 分别提出了处理数据流问题 的典型算法v f d t 嵋1 和c v f d tn 1 。基于h o e f f d i n g 边界和h o e f f d i n g 树实现了足够 近似地构造对数据流的决策树算法。由v f d t 到c v f d t 的改进表达了一个重要的 结论：处理数据流问题需要维护数据窗口( w i n d o w ) ，才能有效解决概念漂移问题。 w i d m e r 等通过f l o r a 2 算法嵋引，证明了动态长度的数据窗口相比于固定长度 的有更强的能力解决概念漂移问题。滑动窗口算法也是也比较成熟的数据流算法 之一盯1 。随后的f l o r a 4 算法1 表明，解决概念漂移问题窗口中的样本数据尤为重 要，而不能仅仅依靠统计量，这与c v f d t 的结论类似。 反垃圾邮件的问题和分布式数据流挖掘有着类似的特点。由此，反垃圾邮件 的成果有着重要的参考价值，主要包括文献 8 和 9 等。实践证明了在采用了有 效的窗口样本的维护和组织算法( c a s e b a s ee d i t i n g ) n 之后，就可以明显提高 数据流算法的泛化性能。 w i d m e r 等的f l o r a 3 3 算法，尽管显示出了历史上学习获得的概念再次使用 的效果并不理想，但是却为概念漂移提供了另一种解决的途径，即在多个简单的 有针对性的基础学习器的集成( e n s e m b l e ) 。在参考了t u r n e y 的上下文相关 ( c o n t e x t u a l ) 属性的想法n 胡之后，w i d m e r 提出了元学习( m e t a l e a r n i n g ) n 3 1 的方 法。这种方法的最大特点是只在窗口中部分符合条件的样本范围内使用特定的分 类器( 如决策树) 。 集成( e n s e m b l e ) 学习逐渐显示了在数据流及其概念漂移方面的优势，比如文 献 1 4 、 1 5 、 1 6 等。另外还有文献 1 7 的短生命周期的集成学习，文献 1 8 第1 蕈绪论 的隐式m a r k o v 模型和文献 1 9 从前后交叉的概念的之间的关系来考虑概念漂移 问题，都有一定的借鉴意义。 “分布式数据流 的提法较早见于文献 2 0 。c h e n 等基于网格( g r i d ) 计算 的环境提出了分布式环境下的数据流挖掘模型g a t e s 。反垃圾邮件系统也是比较 典型的分布式数据流挖掘系统。分布式环境下，由于数据流之间存在着相位差和 速度差，突出的问题是多数据流之间的并发协作问题心“2 引。相比s v m 算法，文献 2 3 和 2 4 尝试用h a a r 小波分析来解决问题，取得了比较好的效果。 1 2 2 支持向量机( s v m ) 算法 1 2 2 1s v m 算法的特点 支持向量机( s v m ) 算法是上世纪九十年代正式提出的一种基于统计学习理论 的模式识别算法乜5 - 2 制。作为优秀的算法，有着成熟的理论背景以及广泛的应用背 景晗训。它的特点有： 一 模型简单，体积小。模型只包括支持向量( s u p p o r tv e c t o r ) ，判别超平面 的参数，核函数的参数等。相比于其他方法( 如决策树的结构和k n n 的样 一 本集) 而言，这些参数都是比较少的。这就大大减小了针对模型的运算以及 传输的复杂度和负荷。 - 泛化( g e n e r a l i z a t i o n ) 能力强，大大减小了过度拟合训练数据的程度啪1 。 泛化错误率的期望的上界仅仅由支持向量的个数与样本总量的比值确定。 - 很少的先验知识( p r i o r ik n o w l e d g e ) 。作为一种线性判别方法的泛化，先 验知识仅仅局限于归一化部分。 一 适合高维度的情况。由于仅仅依赖于两个样本之间的特定运算，而不是所 有样本都要参与的运算，它更加适合每个样本都有很高维度( 属性的个数) 的情况。 - 对训练集的顺序不敏感。 一 灵活性好，可以针对不同的应用背景对模型的参数进行调整。 在分布式数据流的环境下，s 、| ，m 算法的如下特点尤其重要： 模型简单体积小有利于模型的提取、比较、传输和集成。 泛化能力强，以及对训练集的顺序不敏感使得模型在工作中针对错误而发 生的修正减少，模型更稳定。 北泵t 业大学t 宁硕士学位论文 另一方面，由于s v m 算法最初是针对模式识别的问题提出的，没有考虑到分 布式环境下的某些具体需求，因此在分布式数据流的环境下，仍然有着不少需要 研究的方面： o增量式算法相对较少，尤其是在分布式数据流的环境下的应用和改进 。 计算量相对较大。虽然经过很多人的共同努力，s v m 算法的计算有了很大的 优化，但是作为有可能部署在轻量级设备上的算法，计算复杂性和效率需 要尽量降低。 o模型之间的增量式集成方法。在分布式模型下，如何仅仅根据支持向量， 判别超平面的参数，核函数的参数等实现全局模式的集成是一个核心问题。 1 2 2 2 s v m 算法的一些研究成果 通过十几年的研究和发展，s v m 算法不仅在应用中取得了良好的表现( 例如 文献 2 9 ，以及垃圾邮件过滤m 3 和入侵检测n 2 1 ) ，更有了不少重要分支进展( 例 如s m o 算法1 ，v s 算法屯3 副，p s v m 算法b 6 l ，和s v d d 算法b 7 1 等) ，在原有的s v m 算法m 8 1 基础上，具备了更多更优良的特性心引，主要有： 训练算法不断加强，速度有很大提高。如文献 3 9 ，4 l 4 4 等。 能够利用未标签( u n l a b e l e d ) 数据进行学习，提高泛化性能。 能够进行异常点检测( n o v e l t yd e t e c t i o n ) 。 增量式s 算法得到迅速发展。 成熟的提供支持的程序库公开提供，方便研究。如s v m mn 副，1 i b s v m h 劬和 y a l e n 利。另外数学软件如m a t l a b 和r h 8 1 也有支持s v m 的包。 利用未标签数据进行学习 v a p n i k 嘶1 提出了传导性( t r a n s d u c t i v e ) 学习算法。这种算法能够利用未标签 数据，在s v m 的基础上具有更高的泛化性能。j o a c h i m s 卅发展并实践了这种方法。 因为s v m 的泛化错误率的期望的上界仅仅由支持向量的个数与样本总量的比值 确定，联合使用已标签数据和未标签数据，由于数据窗口宽度相比数据流长度很 小，使得泛化性能更好。 这种方法刺激产生一种新的策略，在有指导( s u p e r v i s e d ) 学习( 例如决策 树) 和无指导( u n s u p e r v i s e d ) 学习( 例如聚类分析) 之间，为了充分利用数据， 提高泛化性能，b e n n e t t 等提出了半指导( s e m i s u p e r v i s e d ) 学习嘞1 ，并且得 到了很好的发展旧卜5 引。这些泛化性能好的算法都是很值得学习和借鉴的。 异常点检测 弟l 章绪论 基于s 算法提出的异常点检测算法( 或者称为单类分类巧制，o n e c l a s s c l a s s i f i c a t i o n ) 能够获得数据的外围轮廓模型，称为数据描述( d a t a d e s c r i p t i o n ) ：而确定这个数据描述的核心仍然是求解支持向量。在数据描述的 轮廓以内的数据是正常数据，而以外的数据则是异常点( n o v e l t y 或o u t l i e r ) 。 由于支持向量数据描述算法不依赖先验的数据分布，即使在不了解数据分布的情 况下，也能够获得数据描述。通过应用该算法，不仅能够从整体上描述数据形态， 更能够去除噪点。由于该算法是基于支持向量机算法的，增量式支持向量机算法 都能够应用。 单类分类启发了一种新的s v m 分类算法，它将输入数据的类标签( y ，= 1 ) 与数据的其它属性x ，联合起来，作为转化的无标签数据( y ，x ，) ，然后对它进行 单类分类。这就建立了单类分类与二类分类的联系。弱 增量式s v m 算法 由于s v m 算法最初是基于批量( 可不止一次读取) 数据的问题而设计，增量式 的算法相对较少。但是目前仍然取得了一些很好的发展。比较典型是分块 痞 ( p a r t i t i o n ) 5 6 ，5 7 1 ，错误驱动( e r r o r d r i v e n ) 5 8 钏，绝热平衡( a d i a b a t i c e q u i li b r i u m ) 1 ，超球面( h y p e r s p h e r e ) 旧侧，计算优化1 等。 分块的方法的策略比较简单直接，根据s m o 算法，将训练数据集册分成固 定长度的块( c h u n k 或b l o c k ) ，并对每块进行增量式的训练。在模型状态j ，令 模型表示为膨，训练集的块表示为7 咒，则分块的增量式方法可以表示为： 膨m 膨彤u 绲 彤必一u 巩 这种方法只是把批量式的学习过程做了分割和延迟：由于在对每块进行训练 的时候仍然是批量式的，没有能够真正做到实时迅速。 错误驱动方法的策略是积累判别错误或者超越边界( m a r g i n ) 的样本。当积累 到一定数量的这些样本之后，进行增量式的训练。这种方法不能保证两次学习之 间模型的及时更新，会降低工作中的准确度。 北京丁业大学t 学硕上学位论艾 绝热平衡的方法6 1 针对s 数学模型中的k k t 约束条件，推导出了s v m 数学 模型在增量更新过程中保持不变的条件和方法，使得每个数据输入后，s v m 模型 总能自适应到新的状态，而不需要重新批量式地求解。这种方法实现了步长为一 的增量式学习，能够适用于s 算法系列分类，回归分析，异常点检测等) ，具 有很好的发展前景。 超球面的方法哺2 1 受到单类分类思想的启发，为每个类或者转化的无标签数据 ( y ，薯) 构造一个单类判别超平面，称为超球面( h y p e r s p h e r e ) ，或者称为最小 包围球( m i n i m u me n c l o s i n gb a l l ，m e b ) 哺5 i ，用它来预估计潜在支持向量，选定 参与下面运算的数据。然后用选定的数据和新的输入数据进行其它增量式的训 练，并用训练结果做自我更新。与此想法类似的还有使用几何凸包的方法引。它 们的不同在于： 使用最小包围球的方法不断对距离中心最远的新数据进行增量式的学习，即 首先检测新数据是否为异常点，如果是，则增量式的自我更新。其根本思想 是错误驱动，使用的方式是绝热平衡的方法。但是它只依赖自我更新后的异 常点检测模型来去除数据，也会造成最小包围球持续膨胀。 使用超球面的方法为每个类生成一个超球面，然后用修剪改造后( 有一定的厚 度) 的超球面找到备选支持向量代表该类，与新数据进行批量式的学习。其根 本思想是错误驱动，使用的方式是分块式的方法。但是它只考虑到分类问题 的应用，不适合分布式环境的需要。 专第三种方法的思想类似，只是将方式改成了绝热平衡的方法。 这三种方法都有值得借鉴的地方。 计算优化的方法从最优化方法的角度，提出活动集的概念( a c t i v es e t ) ，在 计算方法上提供一种增量式算法。 1 2 2 3 s v m 算法与数据流挖掘 s y e d 1 首先将s v m 算法引入数据流挖掘领域。k 1 i n k e n b e r g 掣6 7 侧进一步深 入研究了s 及其增量式算法和传导性s v m 算法在数据流挖掘上，尤其是处理概 念漂移的方法。此外，s c h o l z 等7 0 1 还把集成( e n s e m b l e ) 学习和基于知识 ( k n o w l e d g e b a s e d ) 的学习等方法引入数据流挖掘的s v m 算法。 1 3 主要研究内容 第l 章绪论 在分布式环境下，模型的表达、评价、比较与匹配，尤其是模型的集成整合 以及传输等问题有着核心意义。它们是单数据流较少涉及的。因此，本文将着重 研究在分布式环境下： 1 s v m 模型的表达； 2 s 模型的集成整合： 3 上述两项的增量式算法。 1 4 本论文的组织形式 本论文共有五章，它们的内容安排如下： 第l 章绪论主要介绍研究课题的背景和意义，总结国内外在分布式数据流的 挖掘以及支持向量机相关领域的研究进展及成果、存在的不足或有待深入研究的 问题，最后明确本研究课题的主要研究内容。 第2 章引入数据流的概念和分布式环境数据流的概念，分析数据流和分布式 环境数据流挖掘的特点；通过有实际应用背景的典型例子，引入典型的集中式和 非集中式的分布式结构，并且根据它们的特点和需求，提出对应的数据流挖掘的 孝 结构框架，明确并分析分布式环境下特有的模型操作；引入支持向量机( s ) 算 法和支持向量数据描述( s v d d ) 算法，并简要分析它们的特性。 第3 章首先讨论在分布式环境下使用支持向量机模型实现模型集成的优点， 一 之后着重研究了集成支持向量机模型的时候可能遇到的典型情况及其风险：然 后，针对这些问题，提出支持向量数据描述外壳( s v d d s ) 算法，随后分析该算法 的优缺点和特性。 第4 章针对典型的集中式和非集中式的分布式结构，说明s v d d s 算法的工作 方式和在网络节点上的部署方法及其优缺点。 第5 章报告并分析实验的环境、方法和结果，通过比较验证前面理论分析的 结论。 最后对全文进行总结，并对今后的工作进行展望。 8 第2 章研究所依附的基础研：境和方法 第2 章研究所依附的基础环境和方法 在分布式环境下，模型的表达、评价、比较与匹配、集成整合以及传输等问 题是单数据流较少涉及的，其核心问题是单数据流的模型表达以及分布式数据的 集成整合。 在综合比较分析的基础上，鉴于支持向量机( s v m ) 算法的诸多优良特性，本 文解决这个核心问题的主要方法是支持向量机理论及相关算法，和对已有方法的 改进。本章将逐步归纳与本文相关的数据流、分布式数据流、s v m 理论及其对应 的算法等。 2 1数据流 单个的数据流是依时间先后次序到达的，速率不确定的，连续不断的，大量 的，潜在无限长汀的一组数据组成的流，如图2 一l 。 - - - 一 薮据洗方向 训练集丌r ) ( 为，6 1 ) ，( 憨，6 2 ) ，( x i 玎c i ，6 1 7 霄i ) ，坷 ( x | 豫| + j ，6 l i r m ) ，西i 豫硒，6 l i r 硎)( x i ，q i ) ，( 新+ j ，q f + j ) ，( 为+ r ，q l + r ) 测试集丌e ) 图2 一l 单数据流 f i g u r e2 1s i n g l ed a t a s t r e a m 图中，( 鼍，乃) 是数据流中一个数据项 薯r 是 ，个属性的取值向量( 特征向 量) f 岛t r 和t e 中该数据项的标签 胪叫笋 在现实问题中，数据流最大的特点是潜在无限性：在某个相对较长的时间里 ( 例如几年，甚至十几年) ，数据流将持续不断地流入，而且密度比较大，速度比 较快，并且用介质进行存储是很不现实的。这可以用类似数学极限的方式来表达： l i m ，l ( f ) = ( 2 1 ) ， 9 北京丁业大学丁学硕士学位论文 l i m 塑 o 一f ( 2 2 ) ! i 嗯坐掣：尸( f ，f ) o ( 2 3 ) f 川 f i i m s 以( f ) = o o h 。 ( 2 - 4 ) 其中芒是时间，芒是时间的增量，刀是数据流的长度，随时间芒单调增加， s 是存储每条数组所需的介质容量。( 2 1 ) 一( 2 4 ) 式分别表达了数据流的潜在无 限长，密度比较大，速度比较快，和存储的不可能性。其中，( 2 2 ) 式表示的是 随着数据流的不断增加，平均到每个时间上仍然有“足够 的数据。这是为了防 止退化的数据源。例如：某个数据源只产生有限的数据，不随增加而增加。 2 2 分布式数据流 来自不同数据源的多个数据流组成了多数据流。这些数据流既可以是同步 的，也可以是异步的；并且在特定条件下这些数据流可以合并为单个数据流。 在计算机网络环境下，多数据流通过网络传输介质输入到分布式系统中，称 为分布式数据流。这些数据流是相关联的，因此需要从全局的角度来分析它们。 与时间序列类似，不妨引入自相关和协相关的概念。自相关是指同一数据流在不 同时间段之间的相关性。协相关是指在同一分布式系统中不同数据流之间的相关 性。在分布式环境下，并行的数据流之间可有相似的模式，而这些模式可在不同 时刻发生。自相关描述了同一数据流的重复模式，而协相关描述了在相同或者不 同时刻同一分布式系统中不同数据流之间的重复模式。 集中式结构( c e n t r a l i z e d ) 和非集中式结构( d e c e n t r a l i z e d ) 是分布式系统 的典型结构。在本文中，集中式结构是指有一个或者多个数据中心的多层的树形 拓扑结构，而非集中式结构是指没有数据中心的拓扑结构，如环形网络。 例如，银行的交易数据是一种分布式环境下的数据流模型。银行的结构是典 型的组织结构关系：总行、分行、支行以及交易设备( 如a t m 机，p o s 机) 等，如 图2 2 所示。在各个省市设有总行，每个城市下辖一些城镇，分别设有分行。( 图 中为了简明，没有绘出分支下属的机构。) 分支机构为客户提供了用于服务的终 端：a t m 机等。此处，数据流是持续不断产生并且收集的，流向自底向上的。终 端设备收集的逐级汇集到支行、分行和总行，并且还可以及进一步汇集整合。数 据分析员可以分析不同级别的数据。 1 0 第2 章研究所依附的基础研：境和方泫 p o s 互联同支付 图2 2 银行交易数据的组织结构图 f i g u r e2 2l o g i c a la r c h i t e c t u r eo fb a n ki n s t i t u t i o n 这种抽象的集中式结构可以表示为图2 3 。图中数据流用箭头表示( 流向自 底向上) 。 图2 3 集中式结构的数据流采集流向模型 f i g u r e2 3 c e n t r a l i z e da r c h i t e c t u r eo fm o d e l i n t e g r a t i o n l l 北京t 业大学下学硕士学位论文 感应器是终端设备，只有很弱的运算能力，主要负责从客观世界采集数据， 分别成为一条数据流，并将数据流源源不断地传送到分析节点。 分析节点具备运算分析多数据流的能力。它们将进行多数据流的分析运算， 发现模型( 知识) ，并根据规则做出动作。此外，这些分析节点之间也有信息 和模型的交换，并将发现的模型传递给数据中心。 数据中心在收到各个分析节点发现的模型以后，对下属发现的模型进行整合 集成，并从中发现全局模型，然后根据规则做出动作。 进一步的集成也以此类推。 上面所述的“规则”和“动作”根据不同的应用背景各不相同。例如，银行 交易数据环境下，如果有规则：检测恶意透支行为( 在某个终端或者不同终端消 费超过某个限度) ，则报警并且冻结该账户( 不能交易) 。一个恶意的攻击者不仅 可能会在一台a t m 机上恶意透支，甚至有可能到别的场镇或者省市区恶意透支。 如何能够正确审慎地检测到这种行为是对分布式数据流挖掘系统的考验。 在分布式环境下，不同的应用背景可以有不同的拓扑结构。例如，反垃圾邮 件的体系结构，如图2 4 所示。由于电子邮件网络的分布式结构，垃圾邮件发 送者可以在伪装成普通的客户在不同的地点，通过不同的邮件服务器，发送垃圾 邮件。反垃圾邮件软件过滤器需要部署在邮件服务器上，筛选垃圾邮件。 垃扳邮件发迸者 图2 4 反垃圾邮件的网络结构图 f i g u r e2 4 a n t i s p a mn e t w o r k 第2 章研究所依附的基础功：境和方法 在这种分布式结构中，用于反垃圾邮件的模型不可能通过单一的数据中心进 行全局分析识别，而应该通过非集中式结构进行( 例如环形网络) 。其抽象结构如 图2 5 。此处数据流是电子邮件，发现的知识是垃圾邮件的识别模型。图中感应 器和分析节点的功能和图2 3 中的相同。不同之处是：不再有数据中心进行全 局模型的分析，而只能依靠各个分析节点之间的协作。 图2 5 非集中式结构的数据流采集流向模型 f i g u r e2 5 d e c e n t r a l i z e da r c h i t e c t u r eo fm o d e li n t e g r a t i o n 此外还有一种基于网格( g r i d ) 1 和点对点( p 2 p ) 网络n 2 1 的分布式数据流挖掘 模型，比较上面两种模型，对节点的客观要求更低，更加适合分布式的挖掘算法。 例如，分布在世界各地的许多数据分析节点的协作式挖掘，可以用来发现天文、 地震、气象等模型。 分布式数据流挖掘的目标是从看似独立而实则相关的分布式数据流中挖掘 出全局模型。这就需要集成整合各个分散的局部模型，而不只是也不能简单地合 并。对分布式数据流进行模型的操作包括： _ 模型评估：生成模型的摘要信息； _ 模型表达：例如将模型打包为数据元组( t u p l e ) ： - 模型传输：传输表达出来的模型； 一模型比较与匹配：根据模型的评估和或表达信息进行比较； - 模型选取：在比较与匹配的基础上，选取出符合要求的模型： _ 模型集成：将不同模型集成为单个模型。 北京丁业大学下学彤! 士学位论文 然而，因为在分布式环境中，数据流和它们的模型是分散的，集成这些模型， 甚至传输都是相当昂贵的。 随着信息社会的发展，传统的基于存储数据库的挖掘方式，必将逐步退居后 台( 传统的挖掘方式将作为离线的手段继续对数据流挖掘技术粗选的数据进行细 致分析) 。面对感应器采集的海量的数据流，数据流挖掘技术将是挖掘筛选数据 的第一手段。数据流的特性决定了其挖掘算法必须是增量式( i n c r e m e n t a l ) 的( 或 者称为在线的0 n l i n e ) 。更为重要的是，分布式环境下的数据流挖掘技术具有更 广的应用范围和更高的应用价值。在分布式环境下，这种增量式算法还要求挖掘 出来的模型之间是可以增量式的整合集成的。 2 3 支持向量机( s v m ) 算法概述 支持向量机( s v m ) 算法以及密切相关的核方法( k e r n e lm e t h o d ) 口3 1 都是在泛 化性能上表现优异的算法。支持向量机基于统计学习理论和最小化结构性风险原 理( s r m ) ，通过最优化方法，针对只依赖于部分输入数据的泛化过程以及系统近 似函数，权衡数据的实验性( e m p i r i c a l ) 风险和近似函数的结构性( s t r u c t u r a l ) 风险，实现了仅依赖固定数量的数据( 精华子集) 而达到在可控的风险上限范围内 的最优近似函数。 输入数据的精华子集，称为支持向量，仅仅取决于有极少的先验知识的实际 分布，而其他输入数据则不影响最终的判别超平面。其原理模型仅局限于线性空 间，在解决实际问题时依赖于核方法把非线性输入空间的输入数据映射到线性的 特征空