《数据挖掘课件第八章1数据流.ppt》由会员分享，可在线阅读，更多相关《数据挖掘课件第八章1数据流.ppt（60页珍藏版）》请在三一办公上搜索。
1、2023/10/14,1,第八章 挖掘流、时间序列、和序列数据,数据流挖掘时间序列数据挖掘挖掘事务数据库中的序列模式挖掘生物学数据中的序列模式,2023/10/14,2,挖掘数据流,什么是数据流？流数据系统？流数据管理系统：问题及解决方法多维OLAP分析和流数据立方体数据流中的频繁模式分析数据流分类数据流聚类分析研究问题,2023/10/14,3,数据流的特征,数据流数据流连续的，有序的，快速变化的，海量的 传统的 DBMS数据存放在有限的，固定的数据集中特征海量的持续不断地数据，可能是无限的快速变化的，要求实时响应数据流准确抓住了今天我们的数据处理需求随机访问的开销太大单遍扫描（只能查看一次
2、）只存储即时数据的概要多数流数据倾向于很低抽象层或多维的数据，需要多层次，多维的处理过程,2023/10/14,4,流数据的应用,通信行业记录商业:信用卡交易流交通监视系统金融行业：股票交易工业工程行业：电力供应，工业生产过程传感器，监视：视频流，RFIDs安全监控系统网络日志,2023/10/14,5,DBMS 与DSMS,数据是固定的只查询一次随机访问极大的磁盘存储只存放当前数据不需要实时服务更新频率低任何粒度的数据数据是精确的访问是由查询程序或DB的物理设计决定的,暂时数据流 连续查询顺序访问内存受限历史数据是很重要的要求实时响应可能是多GB 的到达率数据粒度小数据不是精确的访问不是预先
3、确定的,Ack.From Motwanis PODS tutorial slides,2023/10/14,6,挖掘数据流,什么是数据流？流数据系统？流数据管理系统：问题及解决方法多维OLAP分析和流数据立方体数据流中的频繁模式分析数据流分类数据流聚类分析研究问题,2023/10/14,7,建筑学:数据流查询过程,Scratch Space(主存/硬盘),用户/应用,数据流查询处理器,结果,Multiple streams,SDMS(数据流管理系统）,2023/10/14,8,数据流处理面临的挑战,多维，连续，迅速，随时间变化，顺序的流数据主存计算查询往往是 连续的随着数据流的到来要连续不断地
4、计算结果要随时间的变化更新查询往往是复杂的跨元素处理跨流处理跨相关的查询(scientific,data mining,OLAP)多层/多维 处理和数据挖掘多数流数据都倾向于很底的抽象层，而且是多维的,2023/10/14,9,数据流查询处理,查询类型只查询一次 vs.连续不断地查询(随着数据流连续不断地到来需要连续不断地计算)预先确定的查询 vs.特殊查询(联机发布)极大的内存需求实时响应，需要用到主存算法如果要与未来元组链接则对内存的需求是极大地近似的查询回答由于主存的限制，往往不可能得到精确地解期望能够得到高质量的近似解减少数据，建立大纲梗概，随机取样，直方图，小波,2023/10/14
5、,10,数据流处理的方法,主要挑战数据量很大，如ip地址技术对照表(准确率与存储空间之间的交换)使用对照表数据要不使用基本数据集小的多在一个小的误差范围内计算近似值主要方法 随机抽样直方图滑动窗口多分辨率办法梗概随机算法,2023/10/14,11,数据流处理的方法(1),随机抽样(预先不知道长度)水库抽样:在水库中维护s个候选集合，形成到目前看到的流元素的真正随机样本。随着数据的流动，每个新元素以概率s/N取代水库中的旧元素。滑动窗口仅仅基于最近的数据作出决策（滑动窗口的大小为w）一个新的数据元素在t时刻到来，在t+w时刻过期直方图近似数据中元素值的频率分布将数据分成一系列相邻的桶等宽(通的
6、值域)与V最优(最小化每个桶的频率方差)多分辨率模型常用模型:平衡二叉树,微簇和小波,2023/10/14,12,数据流处理方法(2),梗概直方图和小波需要扫描数据多遍，梗概可以一遍完成数据流A的频率矩 A=a1,aN,Fk:其中 v是全域或定义域的大小，mi 是i在序列中出现的频率给定序列的长度N和v，梗概近似的为 F0,F1,F2在O(log v+log N)维空间随机化算法蒙特卡洛算法:算法的运行时间有上界，但是可能无法返回正确的解切比雪夫不等式:设x是随机变量，均值为方差为切尔诺夫界:令X是独立泊松实验 X1,Xn的和。属于(0,1随着偏离均值，改改了指数地递减,2023/10/14,
7、13,近似的查询回答,滑动窗口仅仅对最近的数据作出决策 得到近似的结果但通常更为实用分批处理,抽样和对照表如果更新很快而计算相对较慢则分批处理 周期性的计算，而不是即时计算如果更新较慢而计算较快则抽样实用抽样数据计算，但是对连接不利.对照表数据结构存储一小部分数据的对照表或梗概对查询历史数据比较有利封闭操作,例如：排序，均值，最小值等当在全部的输入没有完成就得不到初始输出时，是封闭运算,2023/10/14,14,DSMS(数据流管理系统)上的项目,研究工程和系统原型STREAM(Stanford):DSMS的一般用途 Cougar(Cornell):传感器Aurora(Brown/MIT):
8、传感器监测,数据流Hancock(AT&T):电信流Niagara(OGI/Wisconsin):因特网的XML数据库OpenCQ(Georgia Tech):触发器,增量寄存器，视图维护Tapestry(Xerox):pub/sub 基于容量的过滤Telegraph(Berkeley):传感器的自适应发动Tradebot():股票行情自动收录器 Tribeca(Bellcore):网络监控MAIDS(UIUC/NCSA):数据流的事件挖掘算法,2023/10/14,15,数据流挖掘 vs.数据流查询,流挖掘在很多情况下更具挑战流查询遇到的大部分困难，也同样约束着流挖掘但是，常常对精度的要求不
9、是很高.例如,没有链接，分组，排序模式是隐藏的，且比查询的要普遍需要探测分析不需要连续查询数据流挖掘的任务流的多维联机分析在数据流中挖掘离群点和不寻常模式聚类流数据对流数据分类,2023/10/14,16,挖掘数据流,什么是数据流？流数据系统？流数据管理系统：问题及解决方法多维OLAP分析和流数据立方体数据流中的频繁模式分析数据流分类数据流聚类分析研究问题,2023/10/14,17,动态数据流挖掘的挑战,自然界中大部分流数据是在低抽象层或者是多维数据的:需要 ML/MD处理分析需求多维趋势，不寻常模式在多维/层捕捉重要的变化 快，实时探测和响应与数据立方体比较:相似点和不同点流（数据）立方体
10、或流OLAP:是否可行?我们是否能够有效的执行它?,2023/10/14,18,多维流数据分析:例,对网站点击流的分析未处理的数据处于低抽象层：秒，网页地址，用户ip地址分析希望：变化，倾向，不寻常模式，细节在可以理解的抽象层 例：在北美过去15分钟内对运动的点击率要比过去24小时的平均点击率高40%对能量消耗流的分析初始数据:每户每分钟对能量的消耗流 模式应该找到：在芝加哥，工厂在今天最后两个小时内每个小时对能量的消耗比上个星期高出了 30%,2023/10/14,19,流立方体结构,倾斜时间框架不同的时间尺度秒，分，刻，时，天，周关键层最小兴趣层(m-layer)观察层(o-layer)用
11、户:在观察层观察，偶尔需要下钻到最小兴趣层流立方体的部分物化完全物化:对时间和空间的开销都太大不物化:对查询的响应会很慢部分物化：部分的概念？,2023/10/14,20,倾斜时间模型,自然倾斜时间框架:例：:最小的 quarter,然后 4 quarters 1 hour,24 hours day,对数尺度倾斜时间框架:例：最小的是1分钟然后 1,2,4,8,16,32,2023/10/14,21,倾斜时间模型(2),金字塔型的倾斜时间框架:例:假设有5个框架每个最多有3个快照给定快照N,如果 N mod 2d=0,插入到框架d.如果有多于3个快照则将最老的那个删除,2023/10/14,2
12、2,流立方体中的两个关键层,(*,theme,quarter),(user-group,URL-group,minute),m-layer(minimal interest),(individual-user,URL,second),(primitive)stream data layer,o-layer(observation),2023/10/14,23,联机部分物化与OLAP处理,联机物化物化需要宝贵的空间和时间仅增量物化(with tilted time frame)仅物化关键层的立方体？联机计算要花费太多的时间首选解决方案:常用途径:物化那些在常用下钻路径上立方体H-tree结构:用
13、H-tree结构可以有效的将这些立方体计算并存储联机聚集于基于查询的计算在流动时联机计算:聚集流立方体基于查询的计算：使用已被计算的立方体,2023/10/14,24,流立方体结构:从 m-layer到 o-layer,2023/10/14,25,H-Tree计算结构,最小兴趣层,2023/10/14,26,使用 H-Tree和 H-Cubing的好处,H-tree 和 H-cubing 从数据立方体和冰山立方体的计算发展而来J.Han,J.Pei,G.Dong,and K.Wang,“使用复杂的度量来有效的计算冰山立方体”,SIGMOD01快速计算，在立方体计算时保存空间使用 H-tree计
14、算流立方体空间保存中间的聚集应被增量的计算并保存到树节点中促进其他单元的计算和多维分析被计算过得单元构成的H-tree可以被看做是流立方体,2023/10/14,27,挖掘数据流,什么是数据流？流数据系统？流数据管理系统：问题及解决方法多维OLAP分析和流数据立方体数据流中的频繁模式分析数据流分类数据流聚类分析研究问题,2023/10/14,28,数据流中的频繁模式,挖掘频繁模式在数据流中是很有用的e.g.,网络入侵挖掘(Dokas,et al02)在流数据中挖掘精确的频繁模式:不现实的存储时采用压缩存储，如 FPtree如何挖掘频繁项的好的近似解？近似频繁项(Manku&Motwani VL
15、DB02)仅保存当前的频繁小？探测不到改变挖掘频繁项的进化(C.Giannella,J.Han,X.Yan,P.S.Yu,2003)使用倾斜时间窗口框架挖掘频繁项的进化和戏剧性的变化频繁项和top-k元素的充分利用空间的计算(Metwally,Agrawal,and El Abbadi,ICDT05),2023/10/14,29,挖掘近似频繁项,挖掘数据流中的确定频繁项是不现实的存储的时候采用压缩存储如 FPtree近似解集通常就足够了(e.g.,trend/pattern analysis)例：一个路由器对以下所有的项感兴趣:频率不小于迄今看到的整个通信流量的 1%()且，看来 1/10 o
16、f(=0.1%)是一个可接受的误差范围如何挖掘频繁项的好的近似解？有损计数算法(Manku&Motwani,VLDB02)除非元组成为频繁项否则不追踪它提倡:保证误差界不提倡:保存大量追踪,2023/10/14,30,频繁项的有损计数,将流分成 Buckets(bucket 的大小 1/=1000),2023/10/14,31,第一桶流数据,2023/10/14,32,下一桶流数据,2023/10/14,33,近似性保证,给定:(1)最小支持阈值：,(2)误差界:,(3)流的长度 N 输出:频率计数超过()N的元素我们可以少计算？如果 到目前为止数据流的长度=N 且 桶的大小=1/则 频率计数
17、误差#buckets=N近似性保证不存在假负假正也相当正，因为输出项的频度至少为()N频繁项的频度最多低估 N,2023/10/14,34,频繁项的有损计数,将流数据根据其频率分成桶，但是每次尽量多的将桶放入内存,如果我们一次将3个桶放入内存，则对每个频率计数减少3,2023/10/14,35,更新数据结构的概要,概要数据,删除集合()这是我们选择大量的桶的原因 删除更多,2023/10/14,36,剪枝 Apriori规则,如果我们发现项目集合()不是频繁项目,我们就不需要考虑他的任何超集,3 bucket datain memory,+,summary data,2,1,1,2023/10
18、/14,37,有损计数小结,优点思想简单可以给出频繁项集 缺点:空间不足对于频繁项集，算法多次扫描每个事务输出时基于以前的所有数据的，但有时我们只对当前数据感兴趣数据流频繁项挖掘的充分利用空间的方法Metwally,Agrawal，El Abbadi,ICDT05,2023/10/14,38,挖掘流数据频繁项的进展,近似频繁项(Manku&Motwani VLDB02)仅保存当前的频繁项探测不到变化挖掘频繁模式的演变和重大变化(Giannella,Han,Yan,Yu,2003)使用倾斜时间窗口框架 采用压缩方式存储重要的频繁项以及他们的与时间相依的路径Note:为了挖掘精确的计数，必须跟踪合
19、适的项集,2023/10/14,39,利用倾斜时间窗口挖掘频繁模式的两种结构,FP-Trees存储频繁项，而不是每个事务倾斜时间的主要特征:每个倾斜时间框架一个FP-tree,2023/10/14,40,频繁项和倾斜时间窗口(2),第二种数据结构:直观的:不同时间单位的 FP-Trees是类似 的模式树主要特征：每个结点与一个倾斜时间窗口相关,2023/10/14,41,挖掘数据流,什么是数据流？流数据系统？流数据管理系统：问题及解决方法多维OLAP分析和流数据立方体数据流中的频繁模式分析数据流分类数据流聚类分析研究问题,2023/10/14,42,分类动态数据流,引入决策树来分类流数据VFD
20、T(Very Fast Decision Tree)/CVFDT(Domingos,Hulten,Spencer,KDD00/KDD01)决策树是否适于对快速变化的数据建模,例：股市分析?其他分类流数据的方法不考虑决策树而是其他的方法 朴素贝叶斯系综(Wang,Fan,Yu,Han.KDD03)K最近邻(Aggarwal,Han,Wang,Yu.KDD04)倾斜时间框架,增量更新，动态维持，建模对比模型来寻找变化,2023/10/14,43,Hoeffding 树,很可能产生于传统算法相似的分类仅使用小样本基于Hoeffding界原则Hoeffding 界(Additive Chernoff
21、Bound)r:随机变量R:r的范围n:独立观察次数以概率 1 d表明r的真正均值至少为 ravg,2023/10/14,44,Hoeffding 树算法,Hoeffding 树输入S:样本序列X:属性G():评估函数d:期望精确度Hoeffding 树算法 对S中的每个例子取G(Xa)和 G(Xb)/两个最大的 G(Xi)如果(G(Xa)G(Xb)删除 Xa递归到下一个结点break,2023/10/14,45,yes,no,Packets 10,Protocol=http,Protocol=ftp,yes,yes,no,Packets 10,Bytes 60K,Protocol=http,
22、Data Stream,Data Stream,Ack.From Gehrkes SIGMOD tutorial slides,流数据的决策树规约,2023/10/14,46,Hoeffding 树的优缺点,优点与传统算法相比具有更强的伸缩性准线性抽样使用内存很小增量即使树正在构建，也可以用它对数据进行分类随着新样本的流入，把他们并入到树中缺点：在近似等价分类的属性花费大量时间随着树的增量使用的内存也随之增大候选属性的数量,2023/10/14,47,VFDT(快速决策树),对 Hoeffding 树的修改更主动地打破接近平局训练完许多样本后计算G函数删除最没有希望的叶节点以节省空间删除拙劣的
23、分类属性用传统方式初始化(helps learning curve)与Hoeffding 相比:运行时间段，所需内存小与传统决策树相比相似的精确度1.61百万个样本的运行时间 VFDT需要21分钟C4.5需要24小时仍然不能处理数据流中的概念漂移问题,2023/10/14,48,CVFDT(概念自适应VFDT),概念漂移 随时间变化的数据流体现新的，消除旧的CVFDT增加与新样例相关联的计数减少旧的样本滑动窗口分派给结点单调递增的IDs产生替代子树当替代会产生更高的精度时=替换旧树比VFDT的运行时间要好,2023/10/14,49,分类器系综,H.Wang,W.Fan,P.S.Yu,and
24、J.Han,“使用分类器系综挖掘流数据的概念漂移”,KDD03.方法(起源于分类器系综思想)从k个块中训练k个分类器对每一个子块训练新的分类器测试其他的与该块相对的分类器对每个分类器分配权重选择最高的k个分类器,2023/10/14,50,聚类数据流 GMMO01,基于k中心点的方法度量空间中的流数据点在数据流中找到k个簇，使得每个点到离它最近的中心的距离的和最小常数因子近似算法在优先的空间，简单的两部算法:对每M个记录的集合，找出k个簇S1,Sk的中心局部聚类:将每个点放到离他最近的中心的Si 中每个中心都以指派的该簇的点的个数为权重，聚类加权中心点,2023/10/14,51,分级聚类树,
25、data points,level-i medians,level-(i+1)medians,2023/10/14,52,分级树及其缺点,方法:维持最多m个level-i中心On seeing m of them,generate O(k)level-(i+1)medians of weight equal to the sum of the weights of the intermediate medians assigned to them缺点:对演变数据流的聚类结果质量不好(仅登记k个中心)探测流数据随时间变化的不同部分的簇时功能有限,2023/10/14,53,挖掘动态流数据的聚类,
26、网络入侵检测:实时探测活动的爆发或者突变通过联机聚类 我们的方法(C.Agarwal,J.Han,J.Wang,P.S.Yu,VLDB03)倾斜时间框架:不能发现动态变化微簇：比k均值/中心点法产生的结果要好 增量，联机处理与维持两阶段：微簇和宏聚类利用有限的开支达到高效，可伸缩，高质量的结果，并有能力探测演变、变化,2023/10/14,54,CluStream:聚类演变数据流,目标利用强大的功能来聚类演变数据流考虑到数据流挖掘的要求只扫描原数据一次有限的使用空间，高效CluStream:聚类演变流数据框架将聚类过程分为联机和脱机两个阶段联机部分:周期的存储流数据的统计概要脱机部分:基于存储
27、的统计概要回答用户的各种查询,2023/10/14,55,CluStream框架,微簇数据位置的统计信息聚类特征的时间扩展多维数据点 时间戳 每个点包含d维 i.e.,N个点的微簇定义为(2.d+3)元组 金字塔型时间框架决定统计信息的对照表存入磁盘的时间,2023/10/14,56,CluStream:金字塔型时间框架,金字塔型时间框架微簇的对照表按下列金字塔模式存储基于时间将它们以不同水平的粒度存储将对照表分类成从1到 log(T)的不同命令第i个命令对照表发生在间隔i其中 1只存储最后的(+1)对照表,2023/10/14,57,CluStream:聚类联机流,维护联机微簇初始创建q个微
28、簇 q往往比自然分类的数目大得多微簇的联机增量更新如果新数据点满足最大限制，则加入微簇否则，创建新簇删除最近最少使用的簇或合并两个最近的簇基于微簇的查询基于用户指定的时间范围h，微簇数目k使用k均值算法计算宏聚类,2023/10/14,58,挖掘数据流,什么是数据流？流数据系统？流数据管理系统：问题及解决方法多维OLAP分析和流数据立方体数据流中的频繁模式分析数据流分类数据流聚类分析研究问题,2023/10/14,59,数据流挖掘研究的问题,挖掘数据流中的序列模式Mining partial periodicity in data streams挖掘数据流中的显著性梯度挖掘数据流中的离群点和不寻常模式流聚类多维聚类分析?聚类不局限于二维度量空间，如何连接其他属性，尤其是非数值属性用其他聚类方法聚类流数据？用基于约束的方法聚类流数据？,2023/10/14,60,小结:数据流挖掘,流数据挖掘：丰富的，正在发展的研究领域当前对数据库的研究集中在:DSMS 系统结构,连续查询处理，支持机制流数据挖掘与流数据OLAP分析 挖掘普通模式和不寻常模式的有力工具高效，有效，可伸缩:很多开放性问题我们对数据流挖掘和分析的哲学多维流数据分析框架时间是一个特殊的维：倾斜时间框架计算并保存关键层部分物化，预计算挖掘动态数据流,
