数据流中频繁模式挖掘方法的研究及应用

来源 :山东师范大学 | 被引量 : 0次 | 上传用户:minister635298
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
经过近十几年的研究,数据挖掘技术已经相当成熟。作为数据挖掘研究中的基础任务,频繁模式挖掘一直是一个热点问题,得到了广泛而深入的研究。然而,随着网络、电信和传感器技术的发展,出现了一种新的流数据模型。数据流是大量的、连续的、无限的、快速变化的数据元素的序列。一般无法将数据流中的数据全部保存起来,对数据流中的数据一经处理除非刻意保存,否则就无法再次访问或再次访问的代价很大。为了从数据流中发现知识和模式,必须开发单遍扫描的、联机的、多层的和多维的流处理和分析方法。数据流挖掘是近年来数据挖掘领域的一个热点,大量数据流应用的产生促使数据流挖掘算法相继被提出。频繁模式挖掘是数据流挖掘中的重要研究内容,被广泛应用于关联规则发现、冰山查询、分类和聚类等问题。由于数据流本身的特点,数据流上的频繁模式挖掘只能对数据扫描一次,因此对频繁模式挖掘算法在时间和空间上都提出了更高的要求。许多现有的算法需要多次扫描整个数据集,因此在数据流频繁模式挖掘中的应用受到限制。与传统的频繁模式挖掘不同,为了挖掘数据流中的频繁模式,一般允许结果存在一个足够小的误差,以适应数据流的无限性并提高挖掘的效率。本文综述了数据流频繁模式挖掘研究的现状,分析了两个经典的算法Lossy Counting和FP-stream,两者都能够挖掘数据流中的频繁模式的完全集,但又具有各自的特点。Lossy Counting算法可以将候选项集存储在外存,使算法具有较好的空间效率,但算法只能给出整个流上的频繁模式,不能区分历史数据的不同影响。而FP-stream算法利用倾斜时间窗框架存储每个模式在多个时间粒度下的频数,因而具有较好的动态性,但算法在支持度较低时占用大量内存。本文在分析已有算法的基础上,提出了结合倾斜时间窗的TWCT树结构,可以保存不同时间粒度下的频繁模式的完全集,并设计了其顺序更新和删除算法,使其能够存储在外存,从而有效地降低算法的内存空间需求。结合TWCT树结构特点,提出了数据流上的频繁模式挖掘算法TWCT-Stream,其模式生长的TWCT-Growth算法按字典顺序生成频繁模式,以配合TWCT结构的顺序更新。实验证实算法的内存需求低于FP-stream等同类算法。本文结合滑动窗口模型提出了兼有水平数据格式和垂直数据格式两者特点的VDT-SW结构,该结构便于处理滑动窗口的数据更新,可以结合使用多种频繁模式挖掘算法。利用该结构特点,针对即时查询问题,提出了一个时间复杂度低的快速项集计数查询算法VDT-SW-Query。将基于VDT-SW结构的数据流频繁模式挖掘应用于电信数据分析领域,设计了一个数据流处理系统模型,通过对投诉记录的挖掘,为电信网络运行与维护工作提供有价值的信息。数据流的频繁模式挖掘已经成为当前数据挖掘领域中的一个研究热点。本文最后结合所做工作对进一步的研究进行了展望。
其他文献
随着微电子技术不断发展,片上系统(System-on-Chip,SoC)成为超大规模集成电路设计的主流。而SoC中所包含的IP(Intellectual Property)核数目也随之不断增多,使得以总线结构为
随着Internet技术的发展,网络教学已成为一种非常重要的教学手段。但与传统教学相比,网络教学的评价体系还很不完善。许多网络教学系统未能提供教学评价功能,或即使提供了相
随着世界范围内人口老龄化的日益加剧,骨关节病对人类健康的危害也日益凸显。为了诊断骨关节病的发展程度,在临床上,医学工作者们通过肉眼观察关节部位的医学图像序列,对关节
为了基带数据交换的实际应用,需要评估RapidIO协议性能以及该协议在无线基站中应用的可能性。本文在研究RapidIO协议的内容的基础上,进行了基于RapidIO技术的基带数据交换系
彩信市场经过五年多的发展已经步入了快速发展的时期。但由于种种原因彩信始终没有像短信一样获得预期的发展速度。根据对中国移动彩信业务发展现状的分析,彩信是否能为用户
电力系统的安全运行直接影响着国家经济发展以及国民生活的质量。为了确保变电站安全运转,国家电网公司对变电站中设备,特别是一次设备的监测与故障提出了更高的要求。其中,无线传感器网络以其无需布线、健壮性强、易于扩展等优点,可以作为变电站设备的重要监测方式。变压器在变电站具有举足轻重的作用,同时也是电网中核心设备之一,变压器的安全稳定运行就直接关系到了电力系统的安全性。变压器也是出现事故较为频繁的电力设备
在园林景观设计、社区规划、城市建设等领域,树木虚拟有着重要的实用价值,若能真实虚拟树木形态及随风吹动效果,将会产生栩栩如生、具有真实感的效果。本文以实现具有真实感
NoC(Networks on Chip,片上网络)最早是在SoC(System on Chip,片上系统)的研究过程中被提出来的。NoC往往被用作SoC芯片上的通信基础,具有定制化的、应用驱动的结构,其数据是
芯片的验证工作,对提高投片成功率起到关键性作用。有资料显示,造成芯片一次投片成功率低于50%的主要原因就是功能验证还不够完善。根据不同领域的验证对象和不同层次的验证
数据的指数级增长向世界互联网巨头Google、Yahoo、Amazon和Microsoft等这些处于市场领导地位的公司提出了挑战,它们需要分析TB级和PB级的海量数据以发现有价值的信息推荐给那些有潜在需求的人群。现有的工具正变得无力处理如此大的数据集,Google公司率先推出了MapReduce编程模型,这是Google公司为了在廉价的计算机集群上来存储并处理PB级的数据而提出的一种解决方案。Ha