流数据处理技术的概述0911
第⼀点：流数据处理技术的概述，
什么是流处理技术？
传统数据处理模型
数据流处理模型
1、数据流处理模型和传统数据处理模型的⽐较
电信查流量
如果利⽤传统技术进⾏数据处理，必须将数据全部存储到介质(如关系数据库)中，然后通过提交DML语
句访问存储介质来获取查询结果。但是，当数据规模宏⼤且到达速度很快时，因执⾏查询操作需要⼤量的I/O交换，效率低下，往往难以满⾜实时性要求。相反，数据流处理技术可以不保存整个数据集，仅维护⼀个远⼩于其规模的概要数据结构，从⽽能够常驻内存。
2、基于数据流的处理技术通常包含两部分算法:
⼀部分监控流中的数据，更新概要数据结构;
另⼀部分响应⽤户查询请求，返回近似查询结果。
⽤什么⽅法？
1、数据流聚类算法
单遍扫描算法和进化分析算法
1.1单遍扫描算法把数据流聚类看作是对数据库单遍扫描的处理过程。
传统的数据聚类算法，如k-means和k-medians，被扩展到数据流环境下，并假设数据对象以数据块的⽅式到达。该类算法通常基于分⽽治之的策略，从⽽在⼩空间上获取常数因⼦的近似结果。如：1）采⽤L
OCALSEARCH的⼦过程，在每个数据块到达时产⽣该块数据的簇中⼼。2）VFKM算法对k-means进⾏了扩展，并保证其产⽣的模型与通过⽆限次数据获取所产⽣的模型不具有太⼤差别;
3)Zhou等⼈提出⼀种⽤于数据流核密度估计的单遍扫描算法，可基于核密度估计产⽣聚类结果。4)Nam等⼈提出了⼀种基于统计⽹格的⽅法⽤于单遍扫描的数据聚类。5）此外，还有Beringer等⼈研究了对并⾏数据流的单遍扫描聚类算法。
1.2由于单遍扫描算法⽆法满⾜具有进化特征的数据流的聚类分析需求，研究者开始提出⼀系列进化分析算法。进化分析算法把数据流的⾏为看作是⼀个随时间不断变化过程。1）Dail等⼈提出了⼀种对多条数据流进⾏聚类的通⽤框架COD。该⽅法可动态地对多条数据流进⾏聚类，并可⽀持多种数据挖掘的请求。
2)Yang考虑了⼀种新的多数据流聚类问题，在该问题中，各个数据流被看作是⼀个维度不断增长的向量。两条数据流间的相似性采⽤加权距离进⾏度量，并且⼀种增量的聚类算法被⽤于产⽣数据流的聚类结果。3)Aggarwal等⼈提出了⼀种对数据流进⾏投影聚类的⽅法HPStream。其主要贡献在于引⼊了⼀个衰退簇结构和对数据流进⾏投影聚类的思想。4)Zhou等⼈提出⼀个⽤于跟踪滑动窗⼝内的簇的⽅法SWClustering。区别于该项⼯作，本⽂主要将讨论据伪和纳真误差滑动窗⼝模型中的聚类问题，并推⼴到⼀个更普遍的N-n滑动窗⼝模型。
5)Babcock等⼈基于前⼈的⼯作，从理论⾓度对滑动窗⼝的聚类问题进⾏了研究。区别于该⼯作从理论上对聚类效果进⾏分析，本⽂主要基于滑动窗⼝对数据流中簇的进化过程进⾏挖掘。6）Cao等⼈提出了⼀种基于密度的聚类算法Denstream!咒}可挖掘在有噪声环境下衰减窗⼝内数据流中任意形状的簇。7）朱蔚恒等⼈提出⼀种基于空间分割的聚类⽅法⽤于挖掘具有任意形状的簇。然⽽，这些挖掘任意形状簇的⽅法并不适⽤于滑动窗⼝。
（1）据伪和纳真误差滑动窗⼝模型中的聚类问题，并推⼴到⼀个更普遍的N-n滑动窗⼝模型。
（2）基于滑动窗⼝对数据流中簇的进化过程进⾏挖掘。
2、在实际应⽤中，⼈们往往⽐较关⼼最近⼀段时间内数据流的分布状况，
滑动窗⼝模型可被⽤来更好地获取当前数据流的特征。
在基于界标窗⼝的Clustream中，微簇的半径随界标窗⼝的增长不断增⼤。由于没有在线淘汰“⽼”元组，因⽽只有⼀个微簇⽣成。若采⽤基于滑动窗⼝的聚类，及时地淘汰“⽼”元组，新到达的元组将形成两个微簇。若将Clustream 算法应⽤到滑动窗⼝环境下，需要在每个新元组到达时存储⼀次快照(snaPsllot)，这样巨⼤的处理代价和存储开销，显然难以满⾜数据流实时在线处理的需要。如图
基于滑动窗⼝的聚类中微簇(Mc)的形成过程
3、数据流处理技术原型系统
由于是热点，近来不断出现了⼀些基于数据流处理模型的数据管理系统，这些系统⾯向不同的应⽤领域，设计了很好的系统架构，试图提供基于数据流处理模型的完整应⽤解决⽅案。与这些系统不同，本⽂的⼯作并不是设计和实现⼀个完整的基于数据流处理技术的管理系统，⽽是⾯向⽹络流量监测领域中的具体问题，采⽤数据流处理算法为⽹管⼈员提供⼀个有效的管理⼯具。
第2点：流数据处理系统在电信中应⽤前景的总结
1．数据流聚类分析
数据流环境下的聚类分析是当前数据库领域的⼀个研究热点。聚类挖掘就是把数据集合中的数据对象归为若⼲组，并使得组内对象的相似度尽可能的⾼⽽组间对象的相似度尽可能的低。数据聚类分析在图像处理、模式识别、空间数据分析、等领域有许
多实际应⽤{48}。在数据流环境中，数据聚类同样是⼀种重要的、具有强⼤信息提取功能的数据压缩技术。如何进⾏滑动窗⼝内的数据流聚类分析、提⾼数据流聚类处理效率等都是数据流聚类分析研究中的⼏个基本问题。它们在电信⽹络中的⼊侵检测、⽹络流量监控、数据流挖掘系统实现等实际应⽤中都具有重要意义。
2．⽹络流量Top⼀N排序
电信⽹络质量的管理⾸先是流量的管理，由于Internet数据量呈现爆炸式的增长，以往对流量的管理只能是总流量的检测，并不能知道流量中的不同应⽤的变化情况，因此也不能针对不同的应⽤采取不同应对措施。尤其现在新的P2P应⽤的⼤量增加，⽹络流量的特性和以前也发⽣了很⼤的变化。⽹络的管理就必须从宏观的管理进⼀步深⼊到流量的内容上来。在应⽤了Netflow技术以后，⽹络管理员可以得到流量
的抽样情况，然后对各种不同的应⽤进⾏多种纬度的排序，即所谓Top N排序问题。常见的⽅法是将这些数据存储下来以后进⾏离线分析，得出最后的结果。这样往往不能实时地反映⽹络的流量变化，⽽且也不能选取任意的时间段进⾏排序⽐较，只能使⽤预先定义的排序⽅法进⾏分析。
采⽤数据流的处理技术，本⽂试图寻⼀种能够实时地反映数据变化的算法，在任意给
定的时间段上进⾏排序、查询。从⽽更好地⽀持现在的⽹络管理需求，并且⼤幅度地压缩存储数据的空间要求。
3．SNMP数据流上的异常检测
异常流量检测⼀直是电信⽹络管理所关⼼的题⽬。基于流处理的算法能够检测出⽹络中突发出现的“⽑刺”现象，但IP⽹络的特性就是相对⽆序，存在着⽹络流量的抖动现象。电信⽹络的设计完全能够忍受这些“⽑刺”流量，并不需要预警。因此如何定义异常流量的“模型”往往是⾄关重要的。从⽹络管理的⾓度看，如果在持续的某⼀段时间上出现特性异于通常的流量分布就是值得关注的对象，这往往是⽹络遭到攻击的征兆。本⽂的⽬标就是研究SNMP的流量数据，寻合适的算法能够很好地检测出⽹络中出现的流量异常⽽且对忍受个别“⽑刺”的⼲扰，正确地反映出⽹络流量中可能出现的攻击数据流和病毒流。另外⼀个具有挑战性的问题是，SNMP数据由于基于UDP的协议，其本⾝并不提供可靠的传输链路。所以报出的数据往往会出现数据缺失、错误数据等⼀系列的问题。已有⼀些商业的ETL(Extract，Transform
and load)⼯具，可以对数据仓库的数据进⾏清洗。但这些⼯具由于下⼏个⽅⾯的原因，⽽并不适合实时处理环境:⾸先在真实的电信⽹络环境中，SNMP消息呈现出连续和量⼤的特点⽽不可能被存储在硬盘等介质中以供离线的分析。第⼆由于⽹络监控中的存在着数据质量问题，因此常规的数据清洗技术都不能满⾜实际的要求。例如InteMon等系统，基于⽂件系统的数据，⽽不能完成实时数据的清洗。