频繁项集挖掘算法综述

频繁项集挖掘算法是关联规则挖掘问题的关键,是数据挖掘领域的一个研究热点.自从Apriori算法提出至今,学者提出来大量的关于频繁项集挖掘的算法.本文按照挖掘方式将这些算法分成三类,即宽度优先、深度优先、宽度和深度相结合,并对每类算法进行了全面的综述及深入的分析,并给出了以后的研究方向.     

频繁项集挖掘算法研究

频繁项集挖掘是许多数据挖掘任务中的关键问题,也是关联规则挖掘算法的核心,所以提高频繁项集的生成效率一直是近几年数据挖掘领域研究的热点之一.本文以频繁项集挖掘算法的搜索方式和计数方式为主线,分析频繁项集挖掘中的代表性算法及其中的关键技术和方法,对近年来相关研究的新进展做了介绍和评述,并指出了未来的研究方向.     

一种基于最大频繁项目集的挖掘事务间关联规则方法

Web事务间关联规则挖掘是通过发现网页之间的关联关系来预测用户的兴趣。提出一种新的事务间关联规则挖掘方法,通过对MAFIA算法改进,得到最大频繁项目集的同时得到对应的共有用户集,通过对事务内到事务间最大频繁项目集的转换,分析不同用户之间的关系,分析用户对网站上不同网页的访问数据,直接发现不同用户之间的关联关系来预测用户的兴趣。该方法经试验证明能够更加全面的预测用户感兴趣的网页,更好地为用户提供个性化服务。     

一种基于无向项集图的频繁项集挖掘算法

分析了Apriori算法关于发现频繁项集的方法及其效率,提出了一种基于无向项集图的频繁项集挖掘优化算法。该算法只需要扫描数据库一次,不产生候选项目集,也不使用逐层迭代的方法,大大提高了频繁项集的发现效率。     

Apriori算法中频繁项集挖掘实现研究

在数据挖掘中,关联规则是发现知识的一种有效方法,而频繁项集的挖掘是关联规则中发现强规则的基础,其中连接与剪枝是逐层迭代求解k-项频繁集的核心算法。因此,文中主要介绍了基于连接与剪枝挖掘频繁项集的实现过程,并通过挖掘对传统购物篮数据中的频繁项集进行了验证,结果是一致的。算法的有效性也为进一步挖掘关联规则中的强规则提供了基础。     

GenMax: An Efficient Algorithm for Mining Maximal Frequent Itemsets

We present GenMax, a backtrack search based algorithm for mining maximal frequent itemsets. GenMax uses a number of optimizations to prune the search space. It uses a novel technique called progressive focusing to perform maximality checking, and diffset propagation to perform fast frequency computation. Systematic experimental comparison with previous work indicates that different methods have varying strengths and weaknesses based on dataset characteristics. We found GenMax to be a highly efficient method to mine the exact set of maximal patterns.     

利用Hash树生成频繁项目集的新方法

频繁项目集的生成是关联规则挖掘中的关键问题 .提出基于 Hash树的频繁项目集生成新方法 ,探讨了 Hash树中候选项目集的数据组织与建立算法 ,提出了利用 Hash树计算候选项目集支持数的算法 ,并用 Java语言实现了该算法 ,最后通过实验验证了利用 Hash树生成频繁项目集的有效性     

基于频繁闭项集邻接图的关联规则产生算法

针对关联规则数量巨大并且存在极大冗余的问题,提出无冗余告警关联规则产生算法。从规则本身的关联性和等效性上定义规则的冗余性,通过构造频繁闭项集邻接图发现无冗余告警关联规则,用户可以通过发现的规则推导出其余所有冗余规则,并且得到用户所需的规则形式。该方法不仅能够减少关联规则数量,而且不会带来规则丢失。仿真结果表明,在相同的数据集、最小支持度门限和最小置信度门限条件下,无冗余关联规则数量和产生时间都小于冗余关联规则数量和产生时间,支持度门限越小,差距越显著。     

挖掘最大频繁项集的优化方法

通过对Apriori算法以及已有相关研究工作的分析,从数据库维数压缩、项存储结构以及剪枝几个方面对算法进行了优化,并从理论与试验两方面验证了优化算法的有效性。     

基于粒计算的关联规则挖掘算法

讨论粒计算在关联规则挖掘中的应用,通过对基本信息粒的划分、对粒子对象集合的映射,减少扫描项集所在的对象集合,提高算法的运行效率,从而更好地处理海量数据的规则发现,更适用于支持度较小、复杂度较高的数据集。仿真试验证明该算法有较低的求解复杂度及较高的求解效率。     

关联规则提取中对Apriori算法的一种改进

关联规则的提取是数据挖掘中的重要研究课题,该文对关联规则提取中的Apriori算法进行了深入研究,指出了该算法的某些不足,提出了一种改进算法。实验结果表明,该算法性能明显优于Apriori算法,具有较高的推广价值。     

Extracting Share Frequent Itemsets with Infrequent Subsets

Itemset share has been proposed as an additional measure of the importance of itemsets in association rule mining (Carter et al., 1997). We compare the share and support measures to illustrate that the share measure can provide useful information about numerical values that are typically associated with transaction items, which the support measure cannot. We define the problem of finding share frequent itemsets, and show that share frequency does not have the property of downward closure when it is defined in terms of the itemset as a whole. We present algorithms that do not rely on the property of downward closure, and thus are able to find share frequent itemsets that have infrequent subsets. The algorithms use heuristic methods to generate candidate itemsets. They supplement the information contained in the set of frequent itemsets from a previous pass, with other information that is available at no additional processing cost. They count only those generated itemsets that are predicted to be frequent. The algorithms are applied to a large commercial database and their effectiveness is examined using principles of classifier evaluation from machine learning.     

快速更新频繁项集

发现频繁项集是数据挖掘应用中的关键问题,发现过程的高花费要求对增量数据挖掘算法进行深入研究,首先分析并指出了增量式更新频繁项集算法的技术难点－寻找新的有效频繁项集,其次提出了一种快速的增量式更新频繁项集算法FUFIA,最后对该算法进行了分析和讨论。     

关联规则挖掘在教学评价中的应用研究

教学评价是院校最重要的工作之一,而科学的评教方法又显得尤为重要。本文介绍一种更适合于关系型数据库关联规则挖掘的、基于SQL的频繁项关联规则挖掘算法,并将其应用于教学评价。通过对大量的样本数据进行试验,得出了应用以往传统的教学评价方法所无法得到重要的教学参考信息。     

分布式环境下保持隐私的关联规则挖掘算法

保持隐私是未来数据挖掘领域的焦点问题之一,如何在不共享精确数据的条件下,获取准确的数据关系是保持隐私的数据挖掘的首要任务。该文介绍了分布式环境下保持隐私的数据挖掘的基本问题和措施,研究了一种基于向量点积的关联规则挖掘算法,给出了一种安全的向量点积协议。对于垂直划分的分布式数据库,该协议既可用于搜索频繁项集,又能保持各方数据的隐私。     

最大频繁项目集挖掘技术研究与展望

提高最大频繁项目集挖掘算法的效率是关联规则挖掘研究一个重点领域.本文主要对影响最大频繁项目集挖掘效率的数据分布、搜索策略、支持度计算及剪枝策略等技术进行了研究,并对已提出的最大频繁项目集挖掘算法进行了分析.     

基于矩阵伪投影策略的频繁项集挖掘方法

挖掘频繁项集是数据挖掘应用中关键的问题。经典的FP-growth算法利用FP-tree有效的压缩了数据集的规模,但是在挖掘过程中需要反复递归构造条件FP-tree成为限制算法效率的瓶颈。本文通过将FP-tree映射成矩阵,通过在矩阵自身上进行伪投影得到条件模式阵,避免了递归构造FP-tree,从而节约了内存消耗和计算时间。     

频繁闭项目集挖掘算法研究

目前已提出了许多基于Apriori算法思想的频繁项目集挖掘算法,这些算法可以有效地挖掘出事务数据库中的短频繁项目集,但对于长频繁项目集的挖掘而言,其性能将明显下降.为此,提出了一种频繁闭项目集挖掘算法MFCIA,该算法可以有效地挖掘出事务数据库中所有的频繁项目集,并对其更新问题进行了研究,提出了一种相应的频繁闭项目集增量式更新算法UMFCIA,该算法将充分利用先前的挖掘结果来节省发现新的频繁闭项目集的时间开销.实验结果表明算法MFCIA是有效可行的.     

一种基于频繁模式树的约束最大频繁项目集挖掘及其更新算法

目前已提出了许多快速的关联规则挖掘算法,实际上用户只关心部分关联规则,如他们仅想 知道包含指定项目的规则.当这些约束被用于数据预处理或将它结合到数据挖掘算法中去时 ,可以显著减少算法的执行时间.为此,考虑了一类包含或不包含某些项目的布尔表达式约 束条件,提出了一种快速的基于FP-tree的约束最大频繁项目集挖掘算法CMFIMA,并对其更 新问题进行了研究,提出了一种增量式更新约束最大频繁项目集挖掘算法CMFIUA.     

Distributed Mining of Maximal Frequent Itemsets on a Data Grid System

In this paper, we propose a new algorithm, named Grid-based Distributed Max-Miner (GridDMM), for mining maximal frequent itemsets from databases on a Data Grid. A frequent itemset is maximal if none of its supersets is frequent. GridDMM is specifically suitable for use in Grid environments due to low communication and synchronization overhead. GridDMM consists of a local mining phase and a global mining phase. During the local mining phase, each node mines the local database to discover the local maximal frequent itemsets, then they form a set of maximal candidate itemsets for the top-down search in the subsequent global mining phase. A new prefix-tree data structure is developed to facilitate the storage and counting of the global candidate itemsets of different sizes. We built a Data Grid system on a cluster of workstations using the open-source Globus Toolkit, and evaluated the GridDMM algorithm in terms of performance, scalability, and the overhead of communication and synchronization. GridDMM demonstrates better performance than other sequential and parallel algorithms, and its performance is scalable in terms of the database size and the number of nodes. This research was supported in part by LexisNexis, NCR and AFRL/Wright Brothers Institute (WBI).