数据流挖掘算法的研究及应用

来源 :华南理工大学 | 被引量 : 0次 | 上传用户:kill5678
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
随着全球信息化的发展,信息量按指数增长,出现了大量以数据流为承载形式的信息,比如通信领域中的电话记录数据流、Web上的用户点击数据流、网络监测中的数据包流、各类传感器网络中的检测数据流、金融领域的证券数据流以及零售业务中的交易数据流等。这些数据具有实时性、连续性、顺序性以及数据量庞大等特点,而且通常要求在线处理。1998年,数据流作为一种数据处理模型出现,从2000年开始,作为一个热点研究方向出现在数据挖掘与数据库领域的几大顶级会议中,如VLDB、SIGMOD、SIGKDD、ICML、ICDM等会议每年都有多篇有关数据流处理的文章。目前,数据流研究大致可分为两个方向:数据流管理系统(Data Stream Management Systems.DSMS)和数据流挖掘。数据流挖掘和传统的数据挖掘一样,从大量的数据中挖掘知识,不过挖掘的对象是数据流。数据流模型给数据挖掘带来了新的挑战,比如:必须是一遍扫描(one-pass);空间消耗最多是O(poly(fogy))(N为流的长度);不能使用必须访问整个数据流才能得到结果的操作;不能缓存所有数据,数据处理完毕后需要丢弃;处理速度必须跟上数据到达的速度,因为数据的到达不受控制等等。传统的数据挖掘方法很难被直接应用到数据流模型中,迫使研究人员深入研究数据流模型,设计新的挖掘方法。除了传统的聚类,分类和关联分析等数据挖掘问题,数据流挖掘中还有一些传统数据挖掘中没有的研究内容:设计高效的增量型概要结构(synopsis);新的数据流挖掘框架;数据流演化问题;多时间粒度查询等等。 本文对数据流挖掘中的文本聚类、频繁模式和数据流间模式依赖挖掘进行了探讨,提出了三种新的算法并将其应用到实际系统。本论文的创新点主要体现在: (1)提出了演化文本流聚类算法(CDDS)。该算法不但能进行文本流的聚类,而且还能够处理演化问题和大量孤立点的问题。算法使用在线和离线结构,采用了适合文本相似度计算的在线概要结构,并且使用了时间金字塔模型,能够进行多时间粒度的聚类查询。将在线微聚类分为潜在和异常微聚类,用来解决文本流中孤立点过多时聚类质量下降的问题。实验表明,该算法可以有效地对演化文本流进行聚类,并且在孤立点不敏感。 (2)提出了数据流频繁模式挖掘算法(FSM)。该算法基于传统的频繁模式挖掘算法:FP-growth,利用Lossy Counting算法省去了FP-growth算法所需要的第一遍数据扫描,使该算法只需要---遍扫描就能进行FP-tree的生成。Lossy Cotmting算法的引入,带来了误差ε。可以证明,该算法是一个不存在漏报(no false negative)的算法。实验表明,该算法比传统的FP-stream算法具有处理速度和空间消耗方面的优势。 (3)提出了数据流间模式依赖问题,并设计了数据流间模式依赖挖掘算法(FSDM)。通过对股票分析问题的研究,我们发现了一个数据流问的模式依赖问题。可以简单描述为:在股票数据流中,若股票A的价格出现上升,下降,急速上升后,过两天,有80%的可能股票B价格会下降,再下降。本文提出了FSDM算法,该算法使用条件规则元组描述模式间的依赖,能方便计算数据流间模式依赖的置信度和支持度,并且能够增量更新。针对数据流增多,空间消耗会按平方增长的问题,只选则数据流中选出具有高相关性的数据流进行分析。实验表明该算法可以发现股票间的模式依赖。 (4)设计并实现了两个采用数据流挖掘技术的应用系统。其中一个系统是垃圾短信过滤系统,CDDS算法用于该系统识别垃圾发送者的识别模块,另外一个是移动股票分析系统,FSDM算法可用于股票间模式依赖的挖掘。
其他文献
静校正在地震资料处理中十分重要。经野外一次静校正后,残余的静校正量可用剩余静校正方法求出。剩余静校正问题实质上是一个非线性优化问题。遗传算法是一种重要的非线性全
本文所研发的“基于GIS的多目标地球化学信息管理与综合评价系统”以国土资源部与上海合作开展的“多参数立体城市地质调查项目”为背景。 上海社会经济近十余年来发展速
随着WWW的迅速发展,Web信息检索技术成为研究者广泛关注的话题,但缺少合适的测试评测机制制约了中文网页信息检索技术的发展。参考国外测试集的构建经验,我们构建了大规模中文网
手绘草图既符合人们“笔录纸现”的思维表达习惯,又能充分利用计算机极强的信息维护功能,因此在人机交互领域具有强大的生命力。小型化、便携式和无线设备的快速发展极大地推动
随着互联网的发展,信息检索技术广泛地用于搜索任务。相比于传统的Unigram概率模型,Bigram相关性建模是提高检索精度的重要技术手段,但由于相关计算复杂性过高,难以应用于大规模
数据仓库作为支持决策制定过程的重要手段,近几年来得到了迅速发展,并已经成功应用到制造业、零售业、金融服务、电信、运输等多个行业。随着数据仓库的深入应用,数据质量问题成
贝叶斯网(Bayesian Networks,BN)是用来表示不确定变量集合联合分布的图形模式,有清晰直观、较为符合人们思维方式的特点。目前,贝叶斯网已经成为AI领域的研究热点。当使用贝叶
随着互联网和电子商务的迅猛发展,互联网上的多媒体信息急剧膨胀,数字化多媒体产品可通过下载的方式从网上购买,数字作品的拷贝、修改非常容易,且可以做到与原作完全相同。如何有
本文研究了使用不同蕴含算子和不同关系合成算子下的扩展的CRI模糊推理算法的输出模糊集采用真值递延法清晰化方法时的的应用效果。 第一章首先概要介绍模糊推理的发展过
随着Web2.0技术的成熟,Blog作为Web2.0的重要应用,以其个性化的信息发布平台、多元化的内容载体等特点,吸引着越来越多的网络用户参与其中。撰写和浏览Blog已经成为网络文化新的
学位