论文部分内容阅读
随着信息技术的发展,人们在日常事务处理和科学研究中积累了大量宝贵的数据。如何从中提取或挖掘用户所需要的信息,是当前信息科学和技术领域面临的一大挑战。关联规则(association rules)挖掘在数据领域是一个重要的研究内容,而频繁模式挖掘是产生关联规则的第一步。其研究内容一般包括事务、序列、树和图。其方法被广泛应用于许多其它数据挖掘任务中,如相关性分析,周期分析,最大模式,闭合模式,查询,分类,索引等等。由于问题本身的基础性和内在复杂性,频繁模式挖掘方法成为许多研究者关注的课题。
本文对频繁模式挖掘相关技术进行了研究。重点研究了以下几个问题:基于互关联后继矩阵的区间频繁模式挖掘方法;基于位图(BitVector)频繁模式挖掘算法;基于表构投影模型(ProTable)的频繁闭合模式挖掘算法及相关的实现技术等。本文研究内容和创新工作主要包括以下三个方面:
1)基于IRSM模型的区间频繁模式挖掘方面互关联后继矩阵模型是一种新型的全文存储索引模型。这种模型充分利用了字符序列的有序性和冗余性,适用于海量的全文存储和索引。其优势在于:既是全文索引模型,又是全文存储模型;对任意一全文都能构造其互关联后继矩阵,同时对于互关联后继矩阵,也能还原其对应的原文;具有极佳的空间效率;具有领域独立性和查询的完备性。本文扩展了互关联后继矩阵的应用领域,首次提出一种基于互关联后继矩阵模型的频繁模式挖掘算法。其优点在于:挖掘任务只局部关联于后继矩阵的一行,有较好的可扩展性;算法简单容易理解;具有与FP-Growth算法相当甚至更高的效率。
2)基于位图的频繁模式挖掘方法在通常的水平数据布局的频繁模式挖掘算法的基础上,本文提出一种垂直数据布局的频繁模式挖掘算法即基于位图模型的频繁模式挖掘算法BitVector。采用0,1的形式来表示该项是否存在,并且巧妙地采用了RLE压缩技术,等价类思想和混合遍历的方法。该算法无论在空间和时间效率上对于特定的数据集都有较好的效率。
3)基于表构投影模型的闭合频繁模式方法频繁闭合模式提供了完全频繁模式的所有信息,但数量却可以少几个数量级。本文给出一种基于ProTable的算法特点是:只需要扫描一遍事务库;该二维矩阵模型结构简单,利用代数运算来生成闭合频繁项集。与FP-Close算法相比较,在稠密数据集上ProTable有较好的效率。