频繁项集的挖掘是数据挖掘中的一个基础和核心问题,具有广泛的应用领域。由于它是关联性挖掘过程中最耗时的部分,挖掘算法的好坏直接影响数据挖掘的效率和应用范围。因此,频繁项集挖掘算法的研究具有重要的理论和应用价值。频繁项集挖掘输出的项集集合通常非常庞大。在生成的频繁集中,有相当大一部分是冗余的信息。这不仅带来了时间和空间上效率低下的问题,而且会导致生成许多冗余的关联规则。针对这个问题,存在两种解决方案。一种称为最大频繁项集,即挖掘频繁项集晶格中的最小元素。另一种称为闭合频繁项集,即挖掘Galois算子定义的频繁项集等价类内部的最小元素。闭合频繁项集保证没有任何信息损失,而最大频繁项集挖掘则无法保证。在广泛查阅国内外文献的基础上,围绕“频繁闭合项集”的概念,从传统的批量式算法,在线的增量式算法,具备高容错性的近似算法,以及频繁闭合项集在推荐系统中的应用这四个角度出发,展开系统的讨论:1.批量式算法:提出一个简单高效的频繁闭合项集的批量式算法FCⅡ。FCⅡ基于一种与目标问题等价的新表达方式,并采用深度优先的先序搜索策略以及高效的冗余信息检测技术。理论分析得出,FCⅡ可以在线性时间内找到所有的频繁闭合项集。实验数据表明,FCⅡ在标准数据集上的测试结果比业界领先的同类算法,如CLOSET+,FPCLOSE等有更好的性能。而且,FCⅡ可以增量式的处理列维度的数据添加行为。最后,FCⅡ可以同时得到项集维度与事务集维度的双重信息,这是传统的频繁闭合项集挖掘算法无法做到的。2.增量式算法:数据流环境具有海量数据,快速输入,动态变化等特性。这些特性给传统的数据挖掘算法提出了巨大的挑战。传统的数据挖掘算法允许多次遍历数据集,但在数据流环境下,因为海量数据与动态变化的特性,数据流中的每一个数据元素只能访问一次;而且快速输入的特性给数据挖掘算法提出很高的实时性要求。GC-Tree以及GC-Tree2.0是工作在数据流滑动窗口模型下的增量式算法。GC-Tree在内存中维持一棵树状结构,树中的节点与数据集中的闭合项集一一对应,并且从每一个节点到根节点的序列构成了该节点对应的闭合项集唯一的有序生成项集序列。在该树状结构的基础上,GC-Tree算法设计高效的搜索空间裁剪策略以及节点更新技术。理论分析表明,GC-Tree的计算复杂度为事务的平均长度的二次方函数。在GC-Tree的基础上,提出了改进算法GC-Tree2.0。该算法通过简单的交集操作来发现所有新增的闭合项集。理论分析表明,GC-Tree2.0的时间复杂度为闭合项集平均长度的线性函数。上述的理论分析均可以得到实验数据的有力支持。3.近似算法:由信息缺失,测量误差导致的噪音数据广泛的存在于各种数据库中。最近的理论研究表明,这些噪音和误差使得频繁项集挖掘得到的模式严重失真,并且将较长的频繁模式切割成许多对数级别大小的碎片。若能有效的去除噪音,则不仅可以恢复真实的频繁模式,而且可以将数据挖掘输出项集的数量成倍的减少。因此,开发具有高容错性的频繁闭合项集挖掘算法是一个重要的课题。AFCIM是工作在噪音环境下的近似频繁闭合项集挖掘算法。AFCIM算法是FCII算法的一个变种。该算法在搜索频繁闭合项集的同时检测数据集中的噪音数据,一旦发现噪音数据,立即更新数据集并动态更新已经发现的频繁闭合项集的集合。每一次这样的噪音数据修正迭代,都能恢复一部分真实的频繁模式,并将大量减少潜在的频繁闭合项集的数量。实验结果表明在输出结果的质量得到保证的前提下AFCIM的性能远远高于同类算法AFI与AC-CLOSE。4.在推荐系统中的应用:介绍了推荐系统的研究现状,并分析了传统的推荐系统存在的两个内在缺陷,即维度效应与数据稀疏性。为了解决这两个问题,根据“用户偏好局部性假设”,本文提出了“局部化方法”的思路。即通过AFCIM算法从整体稀疏的数据矩阵中挖掘出局部稠密的子矩阵,然后在稠密子矩阵内部建立局部的预测模型,通过计算不同局部模型的加权均值来为用户做出综合性的推荐。l-pLSI模型是局部化思路应用于传统推荐系统pLSI模型的一个例子。实验数据表明,l-pLSI局部化模型可以有效的提升推荐系统的预测准确率。