一种开采频繁项目集集合的快速算法

在大的数据集合中,开采其中的频繁项目集集合是数据挖掘中极具挑战的重要任务。已经有很多高效的算法被总结了出来。本文提出了一种思想,即开采频繁项目集集合的一 个子集,我们称之为频繁无析取规则集集合,而并非开采完全的频繁项目集集合。我们证明能借助它不读取数据库而还原出频繁项目集集合的全集和它们的支持度。本文还提 提出了一个开采无析取规则集集合的算法HOPE-Ⅱ,实验结果显示了其高效性。我们将它与另一种称为频繁封闭集的精简集进行对比,几乎所有的实验结果都显示使用无析取规则集集合比使用封闭集集合来开采频繁项目集集合更有效。     

一种更新频繁项目集的快速算法

数据库的更新会引起数据库中的关联规则的更新,找出更新后的所有的频繁项目集,也就能生成更新后的关联规则,因此关联规则的更新就转化为频繁项目集的更新。UWEP算法 利用以前的挖掘结果来减少挖掘新的频繁项目集的开销,采用了一些优化技术来减少数据库的扫描次数和候选项目集的数量,但UWEP算法只能处理增加新事务的情况。本文提出 的UWEP2算法是UWEP算法的扩展,能处理数据库中事务的增加、删除、修改等情况。我们将它与另一种更新频繁项目集的算法FUP2比较,实验显示,UWEP2算法比FUP2算法生成的候选项目集要少,性能要高。     

一种基于F-矩阵的最大频繁项目集快速挖掘算法

最大频繁项目集挖掘是多种数据挖掘应用研究的一个重要方面,最大频繁项目集的快速挖掘算法研究是当前研究的热点。传统的最大频繁项目集挖掘算法要多遍扫描数据库并产生大量的候选项目集。为此,该文提出了基于F-矩阵的最大频繁项目集快速挖掘算法FMMFIBFM,FMMFIBFM采用FP-tree的存储结构,仅须扫描数据库两遍且不产生候选频繁项目集,有效地提高了频繁项目集的挖掘效率。实验结果表明,FMMFIBFM算法是有效可行的。     

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

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

基于项目序列集操作的关联规则挖掘算法

最大频繁项目序列集的生成是影响关联规则挖掘的关键问题，传统的算法是通过对事务数据库的多次扫描实现的，最新的研究已经开始通过减少事务数据库的扫描次数进而减少挖掘过程的I／O代价来获得更高的效率，随着计算机性能的提高，探索合适的数据结构来支持基于一次事务数据库扫描的高效算法成为可能，该文首先给出项目序列集和它的基本操作的严格定义，然后在此基础上提出了一个称为ISS－DM的最大频繁项目序列集生成算法。ISS－DM算法是通过对事务数据库的一次扫描而逐步演化成最大频繁项目序列集的，最后作者对这一算法的时间和空间效率进行了理论分析和实验验证。     

分段扫描生成频繁项目序列集的挖掘算法

关联规则挖掘是数据挖掘研究的重要分支。发现频繁项目序列集又是关联规则挖掘中的一个关键阶段。十几年来,许多发现频繁项目集的算法已经被提出。近几年来,人们更关注于在大型数据集中高效发现频繁项目集的算法研究,特别是在减少数据库的扫描次数、提高内存利用率等方面。该文提出一个称为DFISP的算法,它是基于数据分段扫描策略的,并且只需两次数据库扫描即可完成频繁项目序列集的生成。实验表明,DFISP算法是稳定而高效的。     

关联规则挖掘Apriori算法的改进

在对Apriori算法分析的基础上,针对该算法存在的两个缺陷,即多次扫描事务数据库和产生大量的候选数据集,提出了改进的Apriori算法。改进后的算法采用矩阵表示数据库,只扫描1次数据库,改变由低维频繁项目集到高维频繁项目集的多次连接运算,直接从高阶项目集着手寻找最大频繁项目集,从而提高了运算效率。     

频繁项目集及相关事务集的挖掘算法

发现频繁项目集所关联的事务集是十分有意义的,它能使人们了解频繁项目集是由哪些顾客的购买行为所引起的。文章首先定义了事务树及其相关操作,在此基础上,设计了一种能在挖掘频繁项目集的同时发现项目集所在事务集的算法(FS-TS_DM),该算法具有仅需扫描一次事务数据库的特点。另外,还定义了“分散度”指标,用于指导“真频繁项目集”的挖掘。     

基于FP_tree的最大频繁项目集增量式更新算法

关联规则的更新是数据挖掘研究的一个重要内容,能否有效地挖掘出动态事务数据库中的最大频繁项目集是衡量一个关联规则更新算法好坏的关键因素。提出基于FP_tree的最大频繁项目集增量式更新(MFIUP)算法,以处理最小支持度和事务数据库同时发生变化之后相应频繁项目集的更新问题,其中事务数据库的变化同时包括增加和减少两种情况,并对其优越性进行了分析和测试。     

一种基于频繁模式树的最大频繁项目集挖掘算法

目前提出的频繁项目集挖掘算法大多基于Apriori算法思想,这类算法会产生巨大的候选集并且重复扫描数据库.针对这一问题,给出一种基于频繁模式树的最大频繁项目集挖掘算法FP-MFIA,该算法利用频繁模式树对最大频繁项目集进行检索,通过位图建树的方法有效的减少了扫描数据库的次数,从而节省了CPU的执行时间.另外,此算法运用独特的最大频繁项目集判断策略,同时运用投影技术进行超集检测,提高了遍历的效率,实验结果表明该算法是快速有效的.     

Non-derivable itemset mining

All frequent itemset mining algorithms rely heavily on the monotonicity principle for pruning. This principle allows for excluding candidate itemsets from the expensive counting phase. In this paper, we present sound and complete deduction rules to derive bounds on the support of an itemset. Based on these deduction rules, we construct a condensed representation of all frequent itemsets, by removing those itemsets for which the support can be derived, resulting in the so called Non-Derivable Itemsets (NDI) representation. We also present connections between our proposal and recent other proposals for condensed representations of frequent itemsets. Experiments on real-life datasets show the effectiveness of the NDI representation, making the search for frequent non-derivable itemsets a useful and tractable alternative to mining all frequent itemsets.     

DiffNodesets: An efficient structure for fast mining frequent itemsets

Mining frequent itemsets is an essential problem in data mining and plays an important role in many data mining applications. In recent years, some itemset representations based on node sets have been proposed, which have shown to be very efficient for mining frequent itemsets. In this paper, we propose DiffNodeset, a novel and more efficient itemset representation, for mining frequent itemsets. Based on the DiffNodeset structure, we present an efficient algorithm, named dFIN, to mining frequent itemsets. To achieve high efficiency, dFIN finds frequent itemsets using a set-enumeration tree with a hybrid search strategy and directly enumerates frequent itemsets without candidate generation under some case. For evaluating the performance of dFIN, we have conduct extensive experiments to compare it against with existing leading algorithms on a variety of real and synthetic datasets. The experimental results show that dFIN is significantly faster than these leading algorithms.     

Free-Sets: A Condensed Representation of Boolean Data for the Approximation of Frequency Queries

Given a large collection of transactions containing items, a basic common data mining problem is to extract the so-called frequent itemsets (i.e., sets of items appearing in at least a given number of transactions). In this paper, we propose a structure called free-sets, from which we can approximate any itemset support (i.e., the number of transactions containing the itemset) and we formalize this notion in the framework of -adequate representations (H. Mannila and H. Toivonen, 1996. In Proc. of the Second International Conference on Knowledge Discovery and Data Mining (KDD'96), pp. 189–194). We show that frequent free-sets can be efficiently extracted using pruning strategies developed for frequent itemset discovery, and that they can be used to approximate the support of any frequent itemset. Experiments on real dense data sets show a significant reduction of the size of the output when compared with standard frequent itemset extraction. Furthermore, the experiments show that the extraction of frequent free-sets is still possible when the extraction of frequent itemsets becomes intractable, and that the supports of the frequent free-sets can be used to approximate very closely the supports of the frequent itemsets. Finally, we consider the effect of this approximation on association rules (a popular kind of patterns that can be derived from frequent itemsets) and show that the corresponding errors remain very low in practice.     

Efficient algorithms for mining closed itemsets and their lattice structure

The set of frequent closed itemsets uniquely determines the exact frequency of all itemsets, yet it can be orders of magnitude smaller than the set of all frequent itemsets. In this paper, we present CHARM, an efficient algorithm for mining all frequent closed itemsets. It enumerates closed sets using a dual itemset-tidset search tree, using an efficient hybrid search that skips many levels. It also uses a technique called diffsets to reduce the memory footprint of intermediate computations. Finally, it uses a fast hash-based approach to remove any "nonclosed" sets found during computation. We also present CHARM-L, an algorithm that outputs the closed itemset lattice, which is very useful for rule generation and visualization. An extensive experimental evaluation on a number of real and synthetic databases shows that CHARM is a state-of-the-art algorithm that outperforms previous methods. Further, CHARM-L explicitly generates the frequent closed itemset lattice.     

Meta itemset: a new concise representation of frequent itemset

The sheer size of all frequent itemsets is one challenging problem in data mining research. Based on both closed itemset and maximal itemset, meta itemset which is a new concise representation of frequent itemset is proposed. It is proved that both closed itemset and maximal itemset are special cases of meta itemset. The set of all closed itemsets and the set of all maximal itemsets form the upper bound and the lower bound of the set of all meta itemsets. Then, property and pruning strategies of meta itemset are discussed. Finally, an efficient algorithm for mining meta itemset is proposed. Experimental results show that the proposed algorithm is effective and efficient.     

DBC: a condensed representation of frequent patterns for efficient mining

Given a large set of data, a common data mining problem is to extract the frequent patterns occurring in this set. The idea presented in this paper is to extract a condensed representation of the frequent patterns called disjunction-bordered condensation (DBC), instead of extracting the whole frequent pattern collection. We show that this condensed representation can be used to regenerate all frequent patterns and their exact frequencies. Moreover, this regeneration can be performed without any access to the original data. Practical experiments show that the DBCcan be extracted very efficiently even in difficult cases and that this extraction and the regeneration of the frequent patterns is much more efficient than the direct extraction of the frequent patterns themselves. We compared the DBC with another representation of frequent patterns previously investigated in the literature called frequent closed sets. In nearly all experiments we have run, the DBC have been extracted much more efficiently than frequent closed sets. In the other cases, the extraction times are very close.     

Fast and memory efficient mining of frequent closed itemsets

This paper presents a new scalable algorithm for discovering closed frequent itemsets, a lossless and condensed representation of all the frequent itemsets that can be mined from a transactional database. Our algorithm exploits a divide-and-conquer approach and a bitwise vertical representation of the database and adopts a particular visit and partitioning strategy of the search space based on an original theoretical framework, which formalizes the problem of closed itemsets mining in detail. The algorithm adopts several optimizations aimed to save both space and time in computing itemset closures and their supports. In particular, since one of the main problems in this type of algorithms is the multiple generation of the same closed itemset, we propose a new effective and memory-efficient pruning technique, which, unlike other previous proposals, does not require the whole set of closed patterns mined so far to be kept in the main memory. This technique also permits each visited partition of the search space to be mined independently in any order and, thus, also in parallel. The tests conducted on many publicly available data sets show that our algorithm is scalable and outperforms other state-of-the-art algorithms like CLOSET+ and FP-CLOSE, in some cases by more than one order of magnitude. More importantly, the performance improvements become more and more significant as the support threshold is decreased.     

一种频繁核心项集的快速挖掘算法

传统的频繁核心项集挖掘需多次生成和反复扫描数据库,导致生成效率低下。为此,提出一种快速生成频繁核心项集算法FMEP。该算法使用Rymon枚举树作为搜索空间,并采用分而治之的策略选择特定的路径进行剪枝。利用频繁核心项集特有的反单调性质,可以快速地判断某一个候选项集是否为频繁核心项集,而无需和所有直接子集的析取支持度进行比较。通过上述方法,可以达到快速挖掘的目的。实验结果证明,该算法能够在挖掘出所有的频繁核心项集精简表示元素的同时,降低消耗时间,与MEP算法相比,在密集型数据集上的时间可缩短2倍以上,在稀疏型数据集上时间至少缩短30%。     

Incremental mining of generator representation using border sets

Incremental frequent itemset mining refers to the maintenance and utilization of the knowledge discovered in the previous mining operations for later frequent itemset mining. This paper describes an incremental algorithm for maintaining the generator representation in dynamic datasets. The generator representation is a kind of lossless, concise representation of the set of frequent itemsets. It may be orders of magnitude smaller than the set of frequent itemsets. Furthermore, the algorithm utilizes a novel optimization based on generator borders for the first time in the literature. Generator borders are the borderline between frequent generators and other itemsets. New frequent generators can be generated through monitoring them. Extensive Experiments show that this algorithm is more efficient than previous solutions.