论文部分内容阅读
频繁模式挖掘是数据挖掘领域的一个基本问题,研究内容一般包括项目集合、项目序列和时间序列等各种数据中的频繁模式挖掘。其方法被广泛应用于许多其它数据挖掘任务中,如关联规则、分类和聚类、周期分析、相似性查询等等。由于问题本身的基础性和内在复杂性,频繁模式挖掘方法成为许多研究者关注的课题。本文对频繁模式挖掘的算法进行了研究。重点研究了以下几个方面的频繁模式挖掘算法问题:项目集合的完全频繁模式和部分频繁模式挖掘算法;项目序列中的Web频繁路径挖掘算法;时间序列的频繁模式挖掘算法等。本文研究内容和创新工作主要包括以下几个方面:对频繁模式挖掘算法中常用的数据结构FP-tree进行了深入的研究,提出了多种FP-tree的新操作方法,包括FP-tree的拆分、合并、投影等操作,使FP-tree在频繁模式挖掘算法中得到更加灵活的运用,从而有利于提高算法的效率。提出了在项目集合中挖掘频繁模式的FP-DFS算法和FIPT算法。前者用于完全频繁模式挖掘,后者用于部分频繁模式挖掘。FP-DFS算法以FP-tree为基本数据结构,但不再使用条件模式基递归地构造FP-tree,而是通过使用本文提出的FP-tree的新操作方法,以及新的搜索策略和剪枝策略,提高算法的搜索效率,并且减少了对内存的占用。FIPT算法的特点是将概念格与FP-tree结合起来,通过使用本文提出的FP-tree的新操作方法提高概念格的更新效率,解决了批处理大量事务时的效率问题,而生成的概念格又可用于增量挖掘。对于项目序列的频繁模式挖掘,重点研究了其中的Web频繁访问路径挖掘问题,提出了基于网页模糊分类的Web事务识别方法,并在此基础上提出了一种挖掘频繁访问路径的高效混合式算法WDHP。WDHP算法继承了DHP算法使用hash树过滤候选集以及裁剪数据库的基本方法,当数据库被逻辑裁剪到一定程度时,便将数据库以FP-tree的方式存储于内存,并在内存中完成后继的挖掘,既减少了内存占用,又提高了算法的运行效率。对于时间序列的频繁模式挖掘,本文首先分析了时间序列子序列聚类方法中存在的问题,提出了一种基于小波滤波的聚类算法。在此基础上,进一步提出了基于小波滤波的时间序列频繁模式挖掘算法,Frequent-Wavelet算法。Frequent-Wavelet算法的基本原理是使时间序列通过多孔平滑滤波器组,然后对来自多个尺度序列的子序列进行聚类,从而将时间序列的频繁模式挖掘问题转化为项目序列的频繁模式挖掘问题。由于成功地解决了时间序列频繁模式挖掘中的平凡相似和时间轴伸缩问题,与同类算法相比,该算法能够更有效地发现时间序列中的频繁模式。