《数据流挖掘.pptx》由会员分享，可在线阅读，更多相关《数据流挖掘.pptx（24页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数据流挖掘数据流挖掘 常艳 目录 数据挖掘概念 数据流 数据流挖掘概念 数据流模型 几种数据流挖掘算法 数据挖掘的应用 数据挖掘的概念 数据挖掘是指从海量数据中发现一些有趣的趋势或模式,以便指导有关未来的活动的决策。数据挖掘与传统的数据分析(如查询、报表、联机应用分析)的本质区别是数据挖掘是在没有明确假设的前提下去挖掘信息、发现知识。数据挖掘所得到的信息应具有先前未知、有效和可实用三个特征。数据挖掘可以是针对一般的数据源也可以针对特殊应用的数据源。针对一般数据源的挖掘主要有序列数据挖掘、流数据挖掘、文本数据挖掘、多媒体数据挖掘、空间数据挖掘等;针对特殊应用数据源的挖掘有交易数据挖掘、Web数据
2、挖掘、生物数据挖掘、金融数据挖掘、气象数据挖掘、统计数据挖掘、电信数据挖掘等。数据流概念概念：一个实时的、连续的、潜在无界的、不确定的、随时间变化的(隐含的通过到达时间或者明确的时间戳)数据项的序列，又称流数据或流式数据。其到达的速度可能突然发生变化、数据流的更新通常以插入为主。令t表示任一时间戳，at表示在该时间戳到达的数据，数据流可以表示成，at-1，at，at+1，。特点特点：数据流中的数据元素是联机实时、快速到达的;系统无法控制将被处理的数据元素的到达次序;数据规模宏大,不可能把所有的数据都放入内存甚至是硬盘;(ID3,C4.5,CART假设所有样本都存在主存，SLIQ和SPRINT假
3、设样本都存在硬盘上)数据流中的数据元素一旦被处理，要么丢弃，要么存档。除非显示地存储在内存里，否则很难检索，因为内存相对于数据流的尺寸要小得多。数据挖掘概念 概念概念：由于数据流自身的特性,数据流挖掘已经成为数据挖掘的一个新的研究方向。数据流挖掘就是在数据流上发现提取隐含在其中的、人们事先不知道的、但又潜在有用的信息和知识的过程。数据流挖掘的难点数据流挖掘的难点：流数据挖掘的特点决定了它比传统的数据挖掘要复杂，一般我们要考虑下面三个问题。：流数据是不停产生的，而内存的大小是有限的，我们无法把收集到的数据都放在内存中等待挖掘，而只能实时的进行处理。所以在设计挖掘算法时要注意怎样才能将有限的内存充
4、分利用，使得一次能处理更多的数据。：储存在内存中的数据都是最新产生的数据，我们必须在这些数据还没被后来的数据替代前，对它进行处理。这就要求我们在设计算法时要考虑算法的效率，如何在最短的时间内完成对数据的处理。：我们没有任何可以暂时阻塞数据流的操作，所以所有的数据只能扫描一次.所以我们设计的都应该是一次扫描算法(single-scan algorithm)数据流模型 为提高数据挖掘的效率,首先应该对数据流建模。根据适用范围的不同,存在多种不同的数据流式模型,可以按照不同的标准对其进行分类。4.1 按照数据描述方式进行分类设数据流中的数据项 x 1,xi,xn 依次按下标顺序到达,它们描述了一个信
5、号 A。按 xi描述信号 A的方式,数据流模型可分为以下几类 2:(1)时序时序 (Ti me Series)模型模型:A i =xi,用来描述时间序列数据。此时,数据流中的每个数据项都代表一个独立的信号。(2)现金登记现金登记 (Cash Register)模型模型:令 xi=(j,Ii),且 Ii0,则 Ai j =Ai-1 j +I i。此时,数据流中的多个数据项增量式地表达一个 A j。(3)十字转门十字转门 (Turnstile)模型模型:令 xi=(j,Ui),则Ai j =Ai-1 j +Ui。其中,Ui可为正数,也可为负数。此时,数据流中的多个数据项表达一个 A j。A j 随
6、着数据的流入,可能会增加,也可能会减小。4.2按照时序范围分类按照时序范围分类按照算法处理数据流时所采用的时序范围,数据流模型可分为以下几类 3:(1)快照模型快照模型 (Snap shotModel):处理数据的范围限制在两个预定义的时间戳之间。(2)界标模型界标模型 (Landmark Model):处理数据的范围从某一个已知的初始时间点到当前时间点为止。(3)滑动窗口模型滑动窗口模型 (SlidingWindow Model):处理数据的范围由某个固定大小的滑动窗口确定,此滑动窗口的终点永远为当前时刻。其中,滑动窗口的大小可以由一个时间区间定义,也可以由窗口所包含的数据项数目定义。（五）
7、数据流挖掘算法5.1 聚类聚类(clustering)算法算法 聚类是在预先不知道划分类的情况下根据信息相似度原则将信息分成簇的过程。同一个簇中的对象之间具有很高的相似度,而不同簇中的对象高度相异。流数据动态增量的进入系统使得对数据流的聚类必须增量更新,而且只能在有限的空间上对其进行单次扫描。近年来,有学者提出了应用于大规模数据集的一趟聚类算法,如 Birch算法,它们可以应用于某些数据流问题;也有学者提出了针对流数据的聚类算法,典型的有 Stream算法CluStream算法。5.2 频繁项挖掘频繁项挖掘 数据流上的频繁项集挖掘就是单遍扫描数据流来连续发现其中的频繁项集。频繁项集满足最小支持
8、度的项集。Manku 等人提出一个近似的数据流频繁项挖掘算法,该算法采用的是数据流的界标模型,在整个数据流上进行计算。Giannella 等人提出了 FP-Stream 的模型，它以 FP-tree 为基础，用来从数据流中挖掘频繁模型。一个 FP-Stream 模型包括：一个在内存中的，用来捕捉数据流中最频繁和次频繁元组集信息的 FP-tree 结构和为每个频繁模式建立的非均衡时间窗口(tilted-time window)表。例如，图 3 是基于非均衡时间窗口的频繁模式。我们把 t3 时刻的频繁模式以 FP-tree 的结构刻画出来就是图 4 所描述的。然而，为每个时间窗口都建立一棵树需要大
9、量的空间，通常的做法是，只建立一棵树，然后把每个模式的非均衡时间窗口表嵌入到相应的节点中。以模式 ac 为例，创建的 FP-tree 如图 5。5.3 数据流分类算法研究数据流分类算法研究 数据流上的分类就是提出一个分类模型,通过单遍扫描数据流,持续地利用分类模型将数据流对象影射到某一个给定的类别中。数据流分类算法主要是 P.Domings 和 G.Hulten 的研究成果.一种是改造的 Hoeffding决策树分类算法 VFDT,使用恒定的内存大小和时间处理每个样本,有效地解决了时间、内存和样本对数据挖掘,特别是高速数据流上的挖掘的限制。VFDT使用信息熵选择属性,通过建立Hoeffding
10、树来进行决策支持,并使用 Hoeffding约束来保证高精度地处理数据流。既可连续处理数据,也可通过二次抽样,重新扫描数据集,因此可以处理非常庞大的数据集。另一种对 VFDT算法引入了滑动窗口技术,提出了 CVFDT算法。保留了 VFDT算法在速度上和精度上的优点,增加了对数据产生过程中变化趋势的监测,使算法更好的适应对高速、随时间变化数据流的分类。Aggarwal 设计了一个基于聚类分类的数据流分类算法。Wang等人提出了一种数据流挖掘增量模糊决策树分类算法。数据挖掘的应用 应用环境中的数据主要是以连续的、无界的、快速的、随时间变化的数据项的无限序列的形式出现的应用。典型的数据流应用领域如下
11、：(1)传感器网络传感器网络：可用于地理位置监控、公路拥塞监控、运动物追踪、生命信号的医疗监控和制造过程的超级监控。这些应用都涉及复杂的过滤和发现数据中异常模式的被激活的报警设置。传感器的数据挖掘可能需要访问一些历史数据，代表性的查询操作有：激活触发器。例如，当同一地域的几个传感器报告测量值超过给定阈值;在气象图上绘制温度控制线，执行由气象监控站产生的温度流的连接，连接结果形成带有每个站的经度和纬度的静态表，将报告同一温度的点连成线。(2)网络流量分析网络流量分析：实时分析Internet流量的特殊网络已经被使用。与传感器网络功能相同的是：多个数据源到达的数据连接、包监控、包过滤、检测异常情况
12、和支持历史查询。此外，它的功能还包括监控对热点URL的需求或发现用户消耗的最大带宽。在网络流量分析中典型的查询是：流量许可、决定源目的节点对以及不同IP地址组、子网掩码和协议类型站点的总带宽。IP流量是多元统计的，因此，流量数据流必须能逻辑分解以便能重构基本的 TCP/IP会话。而且，分解进入会话的数据流涉及临时语义问题。比较不同的源目的站点对的数量;比较在TCP三次握手中分别包含第二步和第三步的逻辑流中不同的源目的站点对的数量。若计数值超过一个大的极限，那么一个拒绝服务事件将会产生。(3)金融分析金融分析：在线股票价格分析涉及发现关联、鉴别趋势、仲裁机会和预测未来值。典型的基于Web金融分析
13、器允许用户作如下查询：查询所有股票价格在20200美元，其最高价和最低价之间在过去30分钟高过3个百分点的股票分布图，以及最后5分钟其震荡平均量超过300%的股票;查询 NASDAQ指数高于200天的平均变动，以及当天开盘起价格盈利在210个百分点，买卖量超过50亿的股票;查询所有价格在52周高度的2个百分点，每天成交量至少100万的股票。(4)事务日志分析事务日志分析：在线挖掘Web使用日志、电话记录和自动银行取款交易也符合数据流应用模型。其目标在于发现有趣的客户行为模式，鉴别可疑的开销行为以便防止欺诈和预测未来数据。与其他数据流应用一样，它需要多个数据流的连接、复杂的过滤和统计分析。常见的查询有：查询某一服务器的最近15分钟被访问的、其速率至少高于日平均速率40%的所有Web页：如果主服务器过载，实时检测Web服务器日志和重新路由的用户;漫游直径，挖掘无线电话和每个客户，决定每个电话使用的不同基站的最大数量。