论文摘要
随着数据挖掘研究领域的不断拓宽和研究内容的不断深入,人们发现应用中越来越多的数据是以流的形式产生的,例如网络流,网页点击流,交通流以及传感器网络数据等等。分析和挖掘这类数据日益成为一个热点问题。其中,分析流数据间的相似性和模式发现成为重要的研究内容。研究数据流的相似性查询对于完善数据流查询、改进数据流系统等都有着重要的应用价值,并且对于在数据流上进行分类、聚类等也有着指导意义。当前在数据流环境下相似性查询和模式发现的研究工作没有充分考虑数据流数据自身的特点,往往假定内存空间无限或者不满足增量更新。另一方面,据我们所知,目前还没有相关工作系统地解决相似性查询的问题。基于此,本文着重研究数据流环境下相似性查询及模式发现问题,主要包括如下三个关键方面:（1）基于Lp距离,提出系统解决数据流环境下相似性查询的技术。在数据流环境下,基于Lp距离函数,本文系统的提出了一个解决相似性查询的框架,用以解决数据流环境下相似性查询。在充分分析数据流数据的特点后,提出一种新颖的数据结构SDS-Tree（the Same-DirectedSlope Tree）来分层表示数据流对象,实现对原始数据流的表示。基于Lp距离,本文证明SDS-Tree的有效性,并且进一步给出一个相似性判别中更为有效的粒度。基于有效的SDS-Tree结构,文章分别给出有效处理单一固定窗口下的相似性查询算法ASQFSW（Algorithm for SimilarityQueries in Fixed Sliding Window）以及滑动窗口下的增量相似性查询算法IASQSW（Incremental Algorithm for Similarity Queries in SlidingWindows）。特别,IASQSW算法找到了窗口滑动时数据流数据变化的一个上界,根据该上界,算法只需更新有限的SDS-Tree结点,就能够完成窗口滑动时的相似性查询。详细的理论分析以及大量的实验评估表明,我们给出的技术和方法显著优于目前的研究方法。（2）针对Lp距离无法解决时间弯曲的现象,为提高在数据流环境下相似性查询的准确度,提出了基于DTW距离的相似性查询的技术。在数据流环境下,使用Lp距离无法解决时间弯曲现象。为提高在一些应用场合中相似性匹配的准确度,基于DTW距离,提出了一个解决相似性查询的算法ESDS（Estimating Similarity on Data Streams）。算法根据数据流数据的变化特性提出了数据分段的思想,每段数据仅用三个数值（最大值,最小值和差异值）来表示原始数据流的特性。为保证数据特征提取的有效性,根据数据变化的规律,提出了振荡数据的概念,并给出了判断数据流中是否存在振荡数据的算法judgeSurge。为保证对振荡数据的处理不会影响到数据流的特性,进一步提出了有效振荡和最大有效振荡幅度的概念,设计了求解有效振荡数据的算法judgeValidSurge和求解最大有效振荡幅度的算法calMaxScope。算法基于特征数据,设计了新的DTW距离函数,基于动态规划算法,设计了在数据流环境下进行相似性判别的算法ESDS。详细的理论分析以及大量的实验评估表明,文章给出的技术和方法具有很高的准确度和效率。（3）针对Web流数据,设计了两个Web流模式挖掘算法。数据流间的相似性查询在Web数据流中有重要的应用价值。文章首先分析了Web流数据的特征,然后着重研究了Web流数据的模式发现问题。在充分分析经典算法WAP-mine的缺陷后,首先针对WAP树结构设计了一个自顶向下挖掘的算法TD-WAP-mine。算法避免了在挖掘频繁模式过程中每次需要构造大量中间数据,而直接对原始的WAP树进行挖掘,节省了生成中间数据的代价,在支持度比较小或者原始Web流数据过于大的情况下,TD-WAP-mine表现出更好的性能。其次,针对WAP树存在数据冗余情况,提出了压缩WAP树的概念,在不影响挖掘结构的前提下,设计了压缩WAP树算法,并且直接对WAP树投影,设计了一个自顶向下的挖掘算法TAM-WAP,在大规模实验集上的实验表明,TAM-WAP算法表现出更好的性能和伸缩性。