论文部分内容阅读
随着信息技术的发展,海量数据库迅速增加,对其有效的分析处理技术的缺乏逐渐显现。在此需求的推动下,数据库中知识发现(Knowledge Discovery in Databases,KDD)技术应运而生。而数据挖掘(Data Mining,DM)是KDD中的重要过程,在该过程中系统采用智能算法从数据中提取有益的数据模式。其中频繁模式(Frequent Pattern)挖掘是DM中重要的研究问题。近年来,大量数据以数据流(Data Streams)的形式产生,如网络数据、交易数据等。区别于传统的静态数据,数据流具有连续性、无序性、无界性及实时性的特点,这对挖掘数据流中的知识带来了新的研究挑战。挖掘数据流中的频繁模式已成为当前数据挖掘领域的一个研究热点。本文主要针对数据流挖掘中的重要问题之一—数据流频繁模式挖掘展开研究,主要内容如下:首先,对数据流挖掘技术及其特点进行了介绍,然后对数据流频繁模式挖掘的基本概念及其关键问题进行了介绍,最后对数据流频繁模式挖掘的几个典型算法进行了研究。其次,提出了基于界标窗口的数据流频繁模式挖掘算法—Prefix-stream算法,该算法利用提出的数据结构P-tree同时对整个数据流的频繁模式进行挖掘、保存和更新。此外,该方法还应用对数倾斜时间窗口达到逐步降低历史事务的权重,从而区分最近事务与历史事务。实验结果表明,该算法的性能优于同类FP-stream算法。最后,提出了基于滑动窗口的数据流频繁模式挖掘算法—PSW算法。该算法通过将滑动窗口分割为若干个基本窗口,以基本窗口为更新单位,使用提出的前缀滑动窗口树PSW-tree来挖掘基本窗口的频繁模式。挖掘时,将频繁模式存储到同一PSW-tree中,同时删除PSW-tree上过期的及不频繁的模式分支。因此,挖掘和更新滑动窗口中的所有频繁模式是在PSW-tree中同时进行。实验结果表明,算法具有较好的性能。