流数据分析技术全套课件

1、流数据分析技术（引言） 1课程情况2课程目标3课程内容4考核方式5参考资料有什么差别3计算机科学与技术软件工程计算机网络大数据软件硬件多机数据科学软件所处理的内容4V数据流数据在线数据人工智能深度学习数据科学4数学/统计学Math/Statistics软件工程Programming/Hacking领域知识DomainKnowledgeModeling/MLAnalysis ResearchData SoftwareEngineer5我们希望从数据中得到什么数据信息知识洞察智慧无结构有结构可检索有关联可检索相关性可推理关系型数据库数据库分布式存储数据挖掘人工智能学的是什么使同学们理解大数据与流数

2、据的区别大数据是什么？流数据是什么？流数据处理与流计算是一个概念吗？对流式数据处理形成自己的观点和看法对适合流计算的数据处理方式和数据处理方法有认识和一定的掌握能够“触类旁通”的学习新的流式数据处理方法6知其然，知其所以然7课程内容引言第一章 大数据与流数据第二章 流数据处理与流计算流数据处理模型概要结构流数据处理算法Think More, Think Different8课程内容第三章 流数据概要结构构建技术第四章 流数据频繁模式挖掘技术第五章 流数据聚类分析技术第六章 流数据分类分析技术第七章 流数据时间序列分析技术第八章 流数据处理框架学习的关键是抓住其中的“实时性”9考核方式考试：大作

3、业难度：中体力要求：较高参考资料10交换与智能控制研究中心 流数据分析技术（大数据与流数据） 1从物联网到信息物理系统2从抽样数据到大数据3从大数据到人工智能4大数据与流数据从一个例子开始5实际应用场景信息社会的基础电信网络2G（程控交换）下一代网络3G（软交换）IMS/FMC互联网IPv4下一代互联网IPv6Web 2.0移动互联网云计算I 云P 云S 云下下一代网络3.9G（LTE）4G（LTE-A）5GLTE：Long Term Evolution（长期演进）LTE-A：LTE-Advanced（LTE技术后续演进）IMS：IP Multimedia Subsystem（IP多媒体子系统

4、）FMC：Fixed-Mobile Convergence（固网移动融合）IOT：Internet of ThingsRFID：Radio Frequency Identification个人电脑台式机笔记本平板大型机小型机PC服务器传感网RFID（射频识别）现场总线M2M物联网（IoT）产业互联网人工智能车联网（IoV）工业4.015IoT 与 CPS物联网IoT ：Internet of Things 侧重于机器之间的通信过程通过网络设施实现广域或大范围的人与物、物与物之间信息交换信息物理系统CPS：Cyber Physical Systems通过3C技术的有机融合与深度协作，实现对物的实

5、时、动态的信息控制与信息服务强调与物理世界交互的感知与反馈控制过程，通过计算进程和物理进程相互影响实现信息空间与物理空间的密切互动信息采集传输汇集 分析 处理存储应用感知组网数据挖掘 反馈 控制施效计算(Computation)通信(Communication)控制(Control)大规模数据如何使用1从物联网到信息物理系统2从抽样数据到大数据3从大数据到人工智能4大数据与流数据从一个例子开始5实际应用场景17从小规模数据到大规模数据应用平台服务G-T级T-P级大规模互联网/物联网服务18从小规模数据到大规模数据规模大 用户多 总量大 分布广变化快种类杂数据源多样数据类型多样数据结构多样价值密

6、度低 数据高冗余 数据特征不明显 数据信息量低 用户强交互性 数据具有传播性 传播行为复杂大数据的4V特征19大数据的意义揭示宏观变化规律发现不同事物间的关联关系规模大少量数据无价值抽取目标对象的特征百度通过4亿用户分析提供个性化搜索服务2008年谷歌通过庞大搜索数据训练4.5亿个数学模型，提前几周预测出H1N1流感的爆发和传播2008年阿里巴巴提前8-9个月预测出金融危机短时变化无规律单一来源无特征20从抽样数据到全量数据从抽样到全样大数据数量大，数据统计特征分布不均匀，传统采样方法不适用从精确到非精确大数据下精确性不再是绝对追求目标，需对宏观趋势给出快速预测从因果到关联仅需知其然，无需知其

7、所以然，用于“发现事实、预测未来”传统数据处理：抽样数据精确结果准确建模SELECT FROM WHERE ORDER BYSUM( ) GROUP BY Google流感预测采用搜索数据取代抽样百度地图给出的交通拥堵状态及变化趋势沃尔玛啤酒尿布商业案例数据价值密度低数据变化快数据种类杂Inexact近似性Incremental增量性 Inductive归纳性21举个例子从你的新闻，到我的新闻只有让人看到的才是新闻新闻的生产新闻的推送22举个例子内容数据内容获取内容推荐新闻内容相关性知识行为数据行为获取行为相似性知识1从物联网到信息物理系统2从抽样数据到大数据3从大数据到人工智能4大数据与流数

8、据从一个例子开始5实际应用场景面向大数据的数据挖掘方法挖掘任务分类预测（Predication）：用历史预测未来描述（Description）：了解数据中潜在的规律挖掘对象场景面向多源、非结构化数据面向流式数据，时空数据挖掘方法分类分析聚类分析关联分析搜索分析24Incremental增量性 Inductive归纳性Inexact近似性分类通过学习得到目标函数（分类模型）将属性集X映射到预定义的类归纳和推论的过程分类模型决策树分类法基于规则的分类法神经网络（ANN：Artificial Neural Network）支持向量机（SVM：Support Vector Machines）贝叶斯分类

9、法25分类（Classification）聚类（Cluster）聚类类型划分聚类层次聚类划分聚类的序列模糊聚类完全/部分聚类聚类算法K均值（K-Means）K近邻（KNN：k-Nearest Neighbor）凝聚的层次聚类DBSCAN26k-means: 非监督学习 KNN: 监督学习分类和聚类的区别聚类：最大化簇内的相似性、最小化簇间相似性类中的对象具有很高相似性，与其他类中的对象很不相似分类：最大化对象与类的相似性类中的对象与类具有很高相似性，但类中的对象不一定具有很高相似性27关联（Association）反映一个事件和其他事件之间依赖或关联的知识如果两项或多项属性之间存在关联，那么其

10、中一项的属性值就可以依据其他属性值进行预测相关性分析Apriori算法/FP-growth算法（Frequent Pattern Tree）（频繁项）皮尔逊相关系数（Pearson correlation coefficient）（线性相关）主成分分析（Principal Component Analysis）（多个变量间相关性）回归分析线性回归（Linear Regression）（因变量连续，回归线的性质是线性的）逻辑回归（Logistic Regression）（因变量属于二元类型）28关联规则的例子：尿布 啤酒牛奶，面包 鸡蛋，蛋糕啤酒，面包 牛奶TID项集1面包，牛奶2面包，尿布，啤

11、酒，鸡蛋3牛奶，尿布，啤酒，可乐4面包，牛奶，尿布，啤酒5面包，牛奶，尿布，可乐搜索最优化算法动态规划（Dynamic Programming）常用于求解以时间划分阶段的动态过程的优化问题，如最短路径梯度下降法（Steepest Descent）常用于机器学习和人工智能当中用来递归性地逼近最小偏差模型蒙特卡洛树搜索（Monte Carlo Tree Search）大数定律，随机搜索足够多的点启发式算法（heuristic algorithm)模拟退火法(Simulated Annealing）基于蒙特卡洛进行串行搜索优化遗传算法（Genetic Algorithm）基于生物进化和遗传进行全局最

12、优化蚁群算法（Ant Colony Algorithm）强化学习功能的全局性并行优化算法29浅层学习（Shallow Learning）BP神经网络存在的问题神经网络容易过拟合，参数比较难调训练速度比较慢，在层次比较少（小于等于3）的情况下效果并不比其它方法更优改进方法支撑向量机（SVM）Boosting最大熵方法（LR：Logistic Regression 逻辑回归）等共同特点基本上可以看成带有一层隐层节点（如SVM、Boosting），或没有隐层节点（如LR）局限性有限样本和计算单元情况下对复杂函数的表示能力有限针对复杂分类问题其泛化能力受到一定制约30深度学习（Deep Learnin

13、g）提出2006年，加拿大多伦多大学教授Geoffrey Hinton和他的学生Ruslan Salakhutdinov提出一种基于无监督特征学习和特征层次结构的学习方法特点采用多隐层的人工神经网络深度神经网络（多层的好处是可以用较少的参数表示复杂的函数）可通过学习一种深层非线性网络结构，实现复杂函数逼近，表征输入数据分布式表示通过“逐层初始化”（Layer-wise Pre-training）来克服训练上的难度（通过无监督学习）本质“深度模型”是手段“特征学习”是目的31通过构建具有很多隐层的机器学习模型和海量的训练数据，来学习更有用的特征人工神经网络的第三次兴起32从浅层学习向深度学习演进

14、大数据算力1从物联网到信息物理系统2从抽样数据到大数据3从大数据到人工智能4大数据与流数据从一个例子开始5实际应用场景一个例子一些实际问题判断特定IP是不是第一次访问网站？访问了多少次？数据库高速缓存网站高速缓存Web服务MySQL数据库Redis缓存浏览器查询缓存查询结果数据库查询变长数据内容哈希哈希（Hash）把任意长度输入通过Hash算法变换成固定长度输出代表算法：MD5, SHA128, SHA256（32/128/256Bytes）一般是压缩映射，不可逆映射挑战如果实际数据需求远远超过内存大小？如：200,000,000量级32bit整数： 200,000,0004Bytes 763

15、MBytesMD5数字字串：200,000,00016Bytes 3GBytesMD5文本字串：200,000,00032Bytes 6GBytes0230c58281e3661b854e6f480e703d60f7173baa68212ee5fc06db4099f76454687b4aec753c2727cf66ed15d9f4eedf哈希映射？/c/7qvDJ5HbryS快速查询哈希表哈希表（Hash Map）利用线性表存储集合元素利用Hash函数计算元素对应的地址Entry，并在对应的区域存储该元素实际查找通过先hash计算Entry，再匹配元素是否相同（哈希值匹配）优势解决冲突查找复杂

16、（拉链法等）准确率100%问题填充稀疏为避免冲突，填充率50%均衡空间与效率布隆过滤器布隆过滤器 BF（Bloom Filter）1970年Burton Bloom在论文Space/time trade-offs in hash coding with errors中提出核心思想用一系列随机映射函数解决一个映射函数的冲突问题用一个很长的二进制向量来解决存储空间爆炸问题准确率换空间思想延伸优点空间效率和查询时间都远超过一般的算法缺点有一定的误识别率，删除困难应用用于检索一个元素是否在一个集合中布隆过滤器设计思想用一个很长的二进制向量来解决存储空间爆炸问题用一个包含m位的二进制位数组存储BITMA

17、P12345678mHashData1Data2m-1m-2m-3m-4m-5m-6m-7BITMAP00010000000000000000100000000000如果冲突怎么办？Data30000100000000000布隆过滤器设计思想用一系列随机映射函数解决一个映射函数的冲突问题K个相互独立的哈希函数映射到1,m的范围12345678mH1H2H3HkData10001001001000100m-1m-2m-3m-4m-5m-6m-7Data20001001000010010BITMAP布隆过滤器的使用使用判断数据 y 是否在集合 S=x1, x2,xn 中存在计算y的k个哈希函数的取

18、值判断BITMAP相应的位置取值是否为1400110111001110110BITMAPH1H2H3HkData3Data40110布隆过滤器的问题存在误报哈希函数存在冲突BITMAP中的每一位是k个哈希函数映射结果的叠加410111111001110111BITMAPH1H2H3HkData1Data2Data3假阳性 FP（False Positive） 计数型布隆过滤器BF/SBF（Standard Bloom Filter）m长BITMAP的每一个槽位只有1位，只能表示0, 1，代表“有”或“无”缺点：无法删除数据计数型布隆过滤器 CBF（Counting Bloom Filter）将

19、m长BITMAP的每一个槽位修改为多位，形成COUNTER_MAP，如3位，则可以表示0,1,7优点：可以删除数据插入数据时，Counter自增；删除数据时，Counter自减流数据最重要的特点43数据的持续抵达数据的高基数数据的特征变化 1从物联网到信息物理系统2从抽样数据到大数据3从大数据到人工智能4大数据与流数据从一个例子开始5实际应用场景行为学习：基于用户通信记录（含：主被叫、通话时间、通话频度、通话行为、特殊号码类型等）进行无监督和有监督的学习，建立行为特征模式分类器训练：基于行为特征模式，训练电信诈骗鉴别分类器电信诈骗识别：通话记录进入分类器，识别潜在的电信诈骗风险号码45结合通信

20、记录的电信诈骗鉴别基于移动轨迹大数据的模式挖掘发现移动对象在一定时空约束下共同行使所形成的行为模式，以识别潜在的异常根据交通大数据挖掘潜在的出行规律、需求，及相应的变化趋势46移动聚集模式挖掘算法城市交通结构挖掘算法 驾车出行模式公交出行模式城市交通热点聚集模式发现城市交通结构T3T1&2四惠(walk, cycle, bus, subway, car)( 0, 0, 44.40, 40.25, 15.35)%基于移动轨迹大数据的规划与调度47基于公交轨迹大数据的公交车到站时间预测算法电动汽车有序充电路线规划与调度算法分时租赁站点规划与车辆调度算法智能排班路线规划、建设规划特种车队运控特殊路段

21、联控移动群智信息感知与调度如何基于车联网采集并恢复城市环境状态，以应对数据的稀疏性48任务发布与信息感知过程t-nt-n+1t-2t-1tTime slotLocation基于相邻加权条件熵的缺失信息预测与矩阵补全按照序列相似性聚类，进行误差分析与纠错基于稀疏数据的环境状态认知智慧城市感知节点部署数量不足，数据不能反映全局状况，难以支撑决策路网监控设施覆盖不全空气质量采样点无法全面覆盖车辆移动过程中监控数据中断车联网云-端协同感知与计算引入边缘和云端，实现车辆群体的群智计算，以满足信息感知、最优决策等需求49垂直切换垂直切换水平交互水平交互边缘迁移基于邻近传播的领导人选举基于群体博弈的自适应决

22、策车联网人车、车网协同模型基于多车协作的群智认知交换与智能控制研究中心 流数据分析技术（流数据与流计算综述） 1流数据2流数据处理3流数据分析方法4流数据机器学习5小结设想一下这些场景云计算AWS 有 810 万个活跃 IP 地址阿里云有 260 万个活跃 IP 地址微软有 171 万个活跃 IP 地址大规模云计算如何进行管理和维护？54设想一下这些场景2014年12月，阿里云抵御的DDoS攻击峰值流量达到 453.8Gbps2018年02月，攻击GitHub的DDoS流量达到 1.3Tbps2018年03月，攻击Netscout的DDoS流量达到 1.7 Tbps2020年02月，亚马逊AW

23、S Shield拦截的DDoS攻击流量 2.3Tbps55分析一下这个攻击流程劫持肉鸡递归查询肉鸡冒充地址向目标DNS发送地址解析请求DNS向目标地址反馈DNS解析结果返回地址记录在哪里阻断？56攻击流量清洗实时判断流量是否存在异常拦截决策拦截执行异常拦截流数据处理流数据的特点（一）数据的持续抵达实时性：限定时间完成易失性：不可追溯突发性：不可预测无序性：无前后逻辑关联57t0t1t2t3t4t5带来的要求：处理时间要求数据精度与实时性需要平衡数据流t0t1t2数据流t3t4t5流数据处理t0+4t0+3t0+2t0+1流数据的特点（一）数据的持续抵达实时性：限定时间完成易失性：不可追溯突发性

24、：不可预测无序性：无前后逻辑关联58数据流t0t1t2数据流t3t4t5流数据处理缓存t1t2带来的要求：缓存容量要求缓存时效要求数据精度与缓存容量需要平衡流数据的特点（一）数据的持续抵达实时性：限定时间完成易失性：不可追溯突发性：不可预测无序性：无前后逻辑关联59流数据流数据处理t0t1t2t7t8t9带来的要求：数据到达量变化无法预期最大量数据重要度与处理性能需要平衡流数据的特点（一）数据的持续抵达实时性：限定时间完成易失性：不可追溯突发性：不可预测无序性：无前后逻辑关联60流数据t0t1t2t7t8t9流数据处理带来的要求：不一定有序抵达不一定存在关联不能依赖数据的内在长期关联流数据的特

25、点（二）数据的高基数（High-Cardinality）高基数“长尾” 61基数（Cardinality）：数据中不同类别的数量流数据处理缓存IP地址计数IP110IP288IPn100基数 = n带来的要求：不一定能完整记录n个标签成本高压力大流数据的特点（二）数据的高基数（High-Cardinality）高基数“长尾” 62流数据处理缓存IP地址计数IP110IP25IPm100001IPm+199876IPn-1105IPn172数量类别带来的要求：无法预期谁是“长尾”判断难度大基数（Cardinality）：数据中不同类别的数量流数据的特点（三）数据的统计特征变化63概念漂移（Con

26、cept Drift） 从流数据中获得的统计特征可能随时间而变化设：流数据是一个状态序列 S=S1, S2,. . . ,SN Si 由分布 Di 生成概念漂移可以定义为： 一个由分布变化 Dj=Dj+1 导致的状态迁移 Sj Sj+1流数据的特点（三）数据的统计特征变化64概念漂移（Concept Drift） 从流数据中获得的统计特征可能随时间而变化8:0012:0018:00例如：基于细粒度交通数据计算交通指标（密度、时距等）带来的要求：数据的分布规律随时间变化而变如何调整以适应变化Di Si 流数据的特点（三）概念漂移（Concept Drift）对学习分类边界的影响变化类型的影响 6

27、5实概念漂移：影响后验概率/无条件概率密度函数，影响决策边界虚概念漂移：影响条件概率密度函数，不影响决策边界初始分布实概念漂移虚概念漂移流数据的特点（三）概念漂移（Concept Drift）对学习分类边界的影响变化类型的影响 突发概念漂移（Sudden Concept Drift）渐进概念漂移（Gradual Concept Drift）增量概念漂移（Incremental Concept Drift）66DjDj+1 Sj Sj+1Dj Dj+1混合Dj Dj+1缓慢变化Di 流数据的特点（三）概念漂移（Concept Drift）对学习分类边界的影响变化类型的影响 经常性概念漂移（Rec

28、urring Concept Drift）异常值（Blips）噪声（Noise）67Dj+1=Dj-k Sj Sj+1偶发，随机细小的波动Di 流数据的特点（三）概念漂移（Concept Drift）对学习分类边界的影响变化类型的影响 混合概念漂移（Mixed Concept Drift）68Di 流数据定义流数据是一种实时到达的具有规模大、基数高、统计特征复杂变化特性的数据流69 t ：时间戳at ：该时间戳到达的数据数据的时间序列1流数据2流数据处理3流数据分析方法4流数据机器学习5小结离线大数据的批处理批处理模型（Batch Data Processing Model） 传统大数据处理模

29、型 核心思想：先存储，再分析71全量入库离线分析特点：数据处理算法可以按照任意方式对全量数据进行任意次数的遍历离线大数据的批处理批处理模型核心思想：先存储，再分析72Data Warehouse无界数据批处理有界数据入库数据固定窗口批处理会话窗口批处理a+b+cd+e+fh+i+ja+b+cmapreduce常用批处理方法MapReduce：海量大数据分布式处理模型例子计算通话频度73a+b+cd+e+fh+i+ja+b+cmapreduce用户通话记录按时间片分割分别统计合并4565特点：可以通过数据遍历发现数据特征，并据此分割数据块，以保障map不破坏数据的原始特征分布，或reduce能够

30、恢复特征流数据处理流式处理模型（Stream Data Processing Model） 流计算（Stream Computing） 核心思想：数据在线持续处理74特点：数据处理算法仅能对当前缓存内的数据进行遍历，仅能通过概要数据结构存储数据特征的历史记忆在线分析数据入库概要存储与查询tntn+1流数据处理概要数据结构（Synopsis Data Structure） 在有限空间条件下存储的对流数据的一种特征描述精度可接受实时响应75例如：查询访问网站的独立IP地址共访问了多少次通过历史数据挖掘：准确，但需要10分钟返回结果通过计数型布隆过滤器处理：大致准确，但只需0.1秒返回结果概要数据：

31、流数据处理算法的算法缓存和结果记录流处理与批处理的对比流处理批处理输入方式数据流数据块数据量无界数据有界数据存储内存缓存，非持久化持久化存储硬件设施有限内存更多的CPU与内存处理方式一次遍历多次遍历时间需求秒级，甚至毫秒级长应用场景实时类需求应用广泛场景76流式处理与窗口模型77流数据处理模型流数据处理模型分类时间无关型过滤型内联型78数据筛选，对数据本身的顺序、抵达时间偏差等不敏感对多源数据进行关联，对数据本身的顺序、抵达时间偏差等不敏感，但需要缓冲数据以等待关联流数据处理模型流数据处理模型分类窗口型固定窗口滑动窗口会话窗口多尺度窗口79固定窗口（Fixed Window）快照（Snapsh

32、ot）t 不能太大，要满足 实时性要求流数据处理模型流数据处理模型分类窗口型固定窗口滑动窗口会话窗口多尺度窗口80时间滑动窗口（Timebased Sliding Window /Time-Sliding Window）时间窗口大于处理时间间隔 t ti+1 - ti 衰减窗口（Damped Window）通过衰减因子使得窗口内不同时间到达的数据对整体的影响不同注意：数据可不一定是均匀速率抵达的流数据处理模型流数据处理模型分类窗口型固定窗口滑动窗口会话窗口多尺度窗口81内容滑动窗口（ Content based Sliding Window ）按照固定的数据量 W 划分窗口随着数据到达，超过窗

33、口大小的旧数据将会被抛弃，适合对数据量有要求的场景衰减窗口（Damped Window）通过衰减因子区分抵达时间新旧的影响更要注意：数据不一定是均匀速率抵达流数据处理模型流数据处理模型分类窗口型固定窗口滑动窗口会话窗口多尺度窗口82会话窗口（ Session）按照特定条件筛选数据形成会话窗口 S会话窗口是一种内容滑动窗口主要用于多源混杂数据拆分根据条件形成多个会话，每个会话可形成一个内容滑动窗口流数据处理模型流数据处理模型分类窗口型固定窗口滑动窗口会话窗口多尺度窗口近似型83固定、滑动、会话窗口的混合应用近似型采用一个类似会话窗口的可变窗口，但窗口的边界确定规则改为由近似算法确定流式处理与概要

34、结构84常用的概要结构抽样（Sampling）从原始数据集N中抽取小部分样本形成样本集S，代表整合数据集，从而减小数据集规模直方图（Histograms）将一个大数据集按照一定规则划分为小数据集（桶，bucket），并通过对每个小数据集的特征分析，来刻画大数据集的特征轮廓小波（Wavelets）小波是一种通用的数字信号处理技术，类似于傅立叶变换，可根据输入的模拟量，变换成一系列的小波参数草图（Sketches）使用概率数据结构（Probabilistic Data Structures）来抽取流数据的特征，以减小内存占用并降低处理时延85概要数据结构构建需求近似查询估计（Approximate

35、 Query Estimation）实时性和准确性的平衡抽样、直方图、小波和草图等近似连接估计（Approximate Join Estimation）评估连接的大小、强弱草图计算聚合（Computing Aggregates）计算频繁项、分位数（Quantiles）、命中率（Heavy Hitter）等草图或直方图其他数据挖掘类应用（Data Mining Applications）聚类、分类、异常检测、回归预测等86概要数据结构设计原则适用性概要数据结构能够适用更多场景，避免为每个应用计算不同的结构提高概要结构的时间和空间效率单次约束在计算过程中不能多次检查流的内容在一次通过约束下设计时空

36、效率一些方法（如动态规划）需要超线性的空间和时间，对流数据不可接受健壮性由于概要结构只能依据有限时空数据生成，其结果可能存在偏差需要设计鲁棒性度量（允许的最大误差度量）进化敏感数据流不一定存在稳定分布，其随着时间的推移会迅速发展概要结构需要对数据变化有更高敏感度，也可以用于预测871流数据2流数据处理3流数据分析方法4流数据机器学习5小结设想一个场景用户刷新新闻的最高频度是什么？在使用新闻服务的用户中，用户刷新新闻的频度有什么分布特征？针对某个用户，其刷新新闻的频度属于那种类型？针对某个用户，或整个服务系统，是否可以预测未来的刷新频度？流数据分析方法用户刷新新闻的最高频度是什么？在使用新闻服务

37、的用户中，用户刷新新闻的频度有什么分布特征？针对某个用户，其刷新新闻的频度属于那种类型？针对某个用户，或整个服务系统，是否可以预测未来的刷新频度？90频繁项挖掘算法（Frequent Items/Pattern Mining）聚类算法（Clustering）分类算法（Classification）回归算法（Regression）频繁项挖掘算法频繁项（Frequent Items）流数据中指定项目出现的频繁程度核心是计数问题频繁模式（Frequent Pattern）流数据中频繁出现的模式或结构项目集合（Item sets）序列（Sequences）树/子树（Trees）图/子图（Graphs）

38、面临的挑战需要具有很高的内存效率流数据持续抵达，不能多次遍历流数据高基数，搜索空间可能指数增长需要具有实时性流数据存在概念漂移，当前频繁，可能过一段时间就不频繁了91用户刷新新闻的最高频度是什么？聚类算法聚类（Clustering）把数据按照一定的规则分成几个簇簇内对象具有高相似度，簇间对象具有较高相异度面临的挑战需要支持聚类中心的动态迭代流数据持续抵达，不会对历史数据进行持续保存聚类处理过程必须是增量式的，聚类中心需要动态计算和迭代离群点影响变大，需要纠偏传统聚类方法可以通过优化中心点选取避免离群点影响流数据难以通过对原始数据的多次遍历完成对离群点的纠偏92用户刷新新闻的频度具有什么分布特征

39、？分类算法分类（Classification）学习一个分类函数或分类模型并使用该函数或模型将数据项映射到指定类别中的某个类别对象与类具有更近的距离面临的挑战难以获得预先标注的标签如无法预先标注，则需要依赖聚类算法学习分簇数据流持续抵达，难以多次遍历数据传统分类方法需多次遍历数据以完成最佳分裂值设置难以应用需要全体样本距离的算法概念漂移导致分类器失效概念漂移导致训练好的分类器有效性短暂93用户刷新新闻的频度属于哪一类？回归算法回归（Regression）学习一个函数或模型，估计一个或多个自变量与因变量之间的关系判断自变量与因变量是否存在影响，并估计未知参数的取值对输入样本进行“拟合”，并保证误差

40、最小面临的挑战数据流持续抵达，需要动态增量更新需要在已有函数基础上，使用新到达的数据迭代更新离群点影响变大，影响回归精度流数据难以使用长期数据过滤离群点离群点训练回归模型，影响回归精度概念漂移导致回归失效概念漂移导致训练好的回归模型有效性短暂94是否可以估计这类用户未来的刷新频度？过去现在将来1流数据2流数据处理3流数据分析方法4流数据机器学习5小结机器学习机器学习（Machine Learning）一种生产算法的算法通过特征的提取，去训练并获得一个能够实现聚类、分类、回归等特定目的的算法模型流数据环境下的机器学习方法基于流数据的窗口机制，在窗口上使用传统机器学习算法优点：能够使用传统机器学习

41、方法缺点：由于流数据的窗口限制，难以获得全面的特征来描述流数据根据流数据持续抵达的特点，在每一个时间点上，通过算法进行动态预测，从而支持模型的时间进化优点：考虑了流数据的特点缺点：场景受限96流数据机器学习分类在线学习（Online Learning）根据线上实时反馈的数据进行模型调整，从而提高在线预测的准确率主要针对时间序列数据，解决基于回归的预测问题分类：基于值：针对时间点t获得的一个观察样本和预测样本，计算遗憾值（Regret）边界基于概率：给定参数先验，在数据到达后计算后验，并将其作为下一次预测的先验增量学习（Incremental Learning）在获得新数据样本后，在保存大部分已

42、经学习到的知识基础上，从新样本中提取新的知识需要成批的处理增量数据，更适合时间窗口式的流数据微批处理演化学习（Evolutionary Learning）基于演化算法（Evolutionary Algorithms）动态寻优主要是解决参数优化、调度决策等问题971流数据2流数据处理3流数据分析方法4流数据机器学习5小结知识点99知识点100交换与智能控制研究中心 流数据分析技术（流数据概要结构） 1流数据概要结构2抽样概要结构3草图概要结构4直方图概要结构5小波概要结构流数据的概要结构概要数据结构（Synopsis Data Structure） 一种按照流数据处理模型，使用一定流数据分析技术

43、，构建出的一个流数据的主要特征集目的对流数据关键特征的抽取，以方便应用快速查询为其他更深度的流数据特征挖掘提供基础104常用的概要结构抽样（Sampling）从原始数据集N中抽取小部分样本形成样本集S，代表整合数据集，以减小数据集规模保证样本集与原始数据集的同分布，可以将传统数据挖掘处理方法应用到概要数据结构上草图（Sketches）用专用数据结构抽取流数据特征，以快速抽取常用的统计型的指标，以减小内存占用并降低处理时延在最少的空间占用和最快的查询速度之间进行平衡，加速对流数据特征的查询响应速度105常用的概要结构小波（Wavelets）小波是一种通用的数字信号处理技术，类似于傅立叶变换，可根

44、据输入的模拟量，变换成一系列的小波参数用多阶误差树来刻画原始数据，高阶系数反映数据的大趋势，低阶系数反映更局部的趋势直方图（Histograms）将大数据集按照一定规则划分为小数据集（桶，bucket），通过对每个小数据集的特征分析来刻画大数据集的特征轮廓通过与抽样、小波、草图等不同的方法整合，实现对概要结构的不同轮廓的刻画1061流数据概要结构2抽样概要结构3草图概要结构4直方图概要结构5小波概要结构抽样与抽样概要结构抽样（Sampling）从原始数据集 N 中抽取小部分样本形成样本集 S代表整个数据集目的：减小数据集规模，使得传统数据挖掘算法能够被应用到大规模数据集或流数据集特点是一种近似

45、技术能够提供可证明的无偏估计和误差保证易于应用到高维场景108抽样的形式化定义设流数据全集为： N数据内容为： X1Xn 预期的数据挖掘结果： f(N) 获得函数抽样基于抽样集合： S获得抽样函数： f(S)条件：能够通过对函数 f(S) 的均值 和标准差 等的计算 估计函数 f(N)用于估计 f(S) 概率界限的这些不等式被称为尾界 （Tail Bounds）109抽样分类均匀抽样（Uniform Sampling）数据集 N 中不同元素入选样本集合 S 的概率相同如：使用固定的时间间隔进行抽样偏倚抽样（Biased Sampling）数据集 N 中不同元素入选样本集合 S 的概率不同如：考

46、虑空间网格划分，基于密度不同设置不同的概率进行抽样混合抽样均匀抽样与偏倚抽样联合110均匀抽样分类伯努利抽样（Bernoulli Sampling）设：数据集 N 中各元素 X1Xn 服从伯努利分布（Bernoulli Distribution，或称0-1分布）入选概率： p(0 , 1落选概率： q=1 - p抽样概率： P(S; N) = p|S| (1 - p)|N|-|S|优点：采样均匀，过程简单，时间成本低缺点：需要对数据集分布概率需要有预知水库抽样（Reservoir Sampling）设：样本集 S 的大小为 s入选：第 n 个抽样样本的入选概率为 s/n去除：如果当前样本集合中

47、的样本量超过抽样集大小 s，从样本集合 S 中随机去除一个样本优点：各元素入选抽样数据集合的概率相同（随机均匀抽样）111pppps/ns/ns/ns/n随机删除均匀抽样分类简明抽样（Concise Sampling）扩展水库抽样，每个采样点一个计数器入选： 1/ 1/ （ ，概率逐渐变小）去除： /优点：支持重复数据均匀抽样链式抽样（Chain Sampling）针对滑动窗口设：滑动窗口大小 W 入选：第 n 个抽样样本的入选概率 1/min(n,W)替换：从n+1n+W中随机选择备选样本，在抵达时替换当前样本（随机选择）粘性抽样（Sticky Sampling）有损计数（Lossy Cou

48、nting）1121/概率删除1/1/1/1/min(2,W)1/min(3,W)1/min(4,W)n+1n+WW偏倚抽样分类计数抽样（Counting Sampling）设：样本集 S 的大小为 s入选：样本量超过抽样集大小 s 时，首先将参数 提高到 ，先以概率 /，之后以概率 1/ 判断样本集中的样本计数器是否减 1去除：如果样本计数器取值减为 0，则删除样本有效获得数据集中的热门元素加权抽样（Weighted Sampling）带权值的偏倚抽样将使用率高的小数据集赋予更大的权重，以体现数据集的实际分布113/1/普遍命中随机命中谁被减为0的概率大？60%30%10%混合抽样分类国会抽

49、样（Congressional Sampling）将数据集进行分组，不同分组内进行独立的水库抽样，不同组之间使用加权抽样大组抽样率比小组高兼顾组内的公平性和组间的影响力分层抽样（Stratified Sampling）利用数据分布的历史经验对数据进行分层重要的层被设置为大组，抽取更多的采样点正确体现数据的重要特征11460%30%10%组内均匀抽样高频组中频组低频组组间加权抽样伯努利抽样均匀抽样115伯努利抽样（Bernoulli Sampling）均匀抽样要求：数据的抽样分布与原始分布一致方法：对每个到达的数据按照相同的概率进行判断“去”或“留”116pppp1234567891011121

50、3141516171819202122例如：一个伯努利序列（0-1分布）N 1234567891011S pppppppppppppppppp原始序列 N 的均值 0.5采样序列 S 的均值 0.545用0.5采样率能获得与原始序列相同分布的子序列吗？伯努利抽样（Bernoulli Sampling）分析n 为随机变量个数，H(n)为 n 次处理出现成功的次数（真值）TRUE的概率 p，FALSE的概率 q =1-p （ pn ：预测值）在 n 次处理过程中，成功次数不超过 k 次的概率为：当 k=(p-)n 时Hoeffding不等式当 k=(p+)n 时Hoeffding不等式合并设 取值

51、 误差 的概率边界117n22 0.37483590.995867865 0.25341930.999526680 0.23404130.99968751150.20312630.9998488n2600.14624380.99997043200.1342610.99998054600.11545020.999990565050.03673941伯努利抽样该怎样设置抽样率？复习一下置信度与置信区间无法预计准确值只能提供一个估计如果有70%样本落在实际取值中心 正负偏差 到+ 之间置信度：70%置信区间： （均值标准差）目标：伯努利抽样的抽样结果与原序列具有相同分布的置信度满足要求11870%基

52、于Hoeffding不等式的采样率计算设 X 均值（均值 ） 预期的下界Xi 属于 ai, bi误差为 t （标准差 ）对于伯努利分布 Xi 属于 1, 0均值超出误差的概率下界为 （1-置信度）为避免均值超出误差采样 n 的取值例如输入序列符合伯努利分布（0-1分布）如果希望t 0.1 0.1119则= 65tn0.10.050.010.165801150.052603204600.016505801011505伯努利抽样该怎样设置抽样率？120例如：一个伯努利序列（0-1分布）tn0.10.050.010.165801150.052603204600.016505801011505如果希望

53、t 0.05 0.05n 320注意：这里说的是什么问题？必须采样到320才行？12345678910111213141516171819202122N 1234567891011S 窗口内的实际数据量要不小于320伯努利抽样算法121(0,1 随机数落选概率向下取整() ：步长=0：选当前元素0：跳过元素m=m+1 指示下一个入选点的位置注意：也是入选概率伯努利抽样算法效果取值0.10.20.30.40.50.60.70.80.90.121.85 10.32 6.46 4.51 3.32 2.51 1.91 1.43 1.00 0.215.28 7.21 4.51 3.15 2.32 1.7

54、6 1.34 1.00 0.70 0.311.43 5.40 3.38 2.36 1.74 1.31 1.00 0.75 0.52 0.48.70 4.11 2.57 1.79 1.32 1.00 0.76 0.57 0.40 0.56.58 3.11 1.94 1.36 1.00 0.76 0.58 0.43 0.30 0.64.85 2.29 1.43 1.00 0.74 0.56 0.42 0.32 0.22 0.73.39 1.60 1.00 0.70 0.51 0.39 0.30 0.22 0.15 0.82.12 1.00 0.63 0.44 0.32 0.24 0.19 0.14

55、 0.10 0.91.00 0.47 0.30 0.21 0.15 0.11 0.09 0.07 0.05 10.000.000.000.000.000.000.000.000.00比例0.12350.23260.35710.45450.55560.66670.76920.83330.9091122随机数取值（均匀分布）入选概率取值m = 0m =m + + 1实际步长伯努利抽样算法的局限需要预知数据的分布特征无法应对概念漂移可以支持滑动窗口，但是只能代表窗口内数据的采样结果，并不是整个流数据的无偏估计无法预计流数据大小，因此也无法预计对整个流数据的采样率1231234567891011121

56、3141516171819202122N 1234567S 45678910S 水库抽样均匀抽样124水库抽样（Reservoir Sampling）均匀抽样要求：数据的抽样分布与原始分布一致12512345678910111213141516171819202122N S S 1234567891011121323467910111215161922目标：在抽样完成后，获得大小为 S 的无偏样本水库抽样（Reservoir Sampling）均匀抽样目标：在抽样完成后，S 中的每一个元素都是按照 S/N 的概率抽取问题：由于流数据的特点，无法预知 N 的大小12612345678910111

57、213141516171819202122N S 24568911121316192012122以多大的概率入池？以多大的概率将池中的哪个元素删除？水库抽样（Reservoir Sampling）算法思路第1s个元素，按照概率 1 入池后继第 n 个元素，按照 s/n 概率入池池中元素，按照 1/s 概率删除12712345678910111213141516171819202122N S 24568911121316192012122s/n1/s1/1313/21s/n13/22概率删除概率入池水库抽样证明128s/N水库抽样算法129初始抵达元素全部入池kU ：0k的随机数以 1/k 的概

58、率，用入池的数据元素替换掉蓄水池中的原有元素抵达元素是下一跳元素Data Stream Management：Processing High-Speed Data Streams p21水库抽样算法130找到最小的，使其概率恰巧小于U就是必须得入池的步数s/(n+1) 入池概率1-s/(n+1) 不入池概率(1-s/(n+1) 个都不入池概率使用最优化方法避免计算超范围 * A.M. Law, Simulation Modeling and Analysis, 4th edn. (McGraw-Hill, New York, 2007)简明抽样均匀抽样131简明抽样（Concise Sampl

59、ing）均匀抽样要求：数据的抽样分布与原始分布一致13212345678910111213141516171819202122N S 12345678910111213如果流数据中存在大量的重复元素，水库抽样存在的问题：样本集中需要存储大量重复样本，空间利用率低0, 5简明抽样（Concise Sampling）简明抽样（精确抽样）设：样本集 S 的大小为 s阈值参数 （初始化取值1）入选：样本量小于抽样集大小 s ，以概率 1/ 入选（计数器+1）样本量大于抽样集大小 s ，以概率 1/ 入选（ ）去除：样本量大于抽样集大小 s ，以概率 / 选择样本集中的样本，将计数器减 1（ )直到某一

60、样本计数器取值减为 0，删除样本特点：随数据流推进，抽样概率逐渐降低适合重复数据较多的情况133删除操作过程134S110S221S333S411S57S62S715S881021331072158102133107115892031960137以概率 /=0.91选择样本=1=1.1以概率 /=0.91选择样本-1-1多次迭代，/=0.91，样本被选中概率很高普遍都减了几次低频率的样本被首先减到0简明抽样设计特点面向具有重复项的流以概率 / 删除样本集元素高频度的元素更大概率保留低频度的元素更大概率删除以概率 1/ 选择新元素出现新元素的时候，抽样率降低，抽到低频新元素的概率也低了低抽样率对