An efficient cluster and decomposition algorithm for mining association rules

Conventional algorithms for mining association rules operate in a combination of smaller large itemsets. This paper presents a new efficient which combines both the cluster concept and decomposition of larger candidate itemsets, while proceeds from mining the maximal large itemsets down to large 1-itemsets, named cluster-decomposition association rule (CDAR). First, the CDAR method creates some clusters by reading the database only once, and then clustering the transaction records to the kth cluster, where the length of a record is k. Then, the large k-itemsets are generated by contrasts with the kth cluster only, unlike the combination concept that contrasts with the entire database. Experiments with real-life databases show that CDAR outperforms Apriori, a well-known and widely used association rule.     

基于概念格的关联规则算法

对经典Apriori算法的优、缺点进行了剖析,在实际应用项目中,提出了一种基于概念格的关联规则算法ACL(AprioriAlgorithmBasedOnConceptLattices)。在该算法中,引入了概念格和等价关系等概念,利用粗糙集相关方面的理论,计算得到频繁2-项集L2。实验表明,ACL算法是一种有效的快速的关联规则挖掘算法。     

高效的关联规则挖掘算法研究

目前已经提出了许多用于高效地发现大规模数据库中的关联规则的算法,但都是对关联规则中满足最小支持度的频繁项集的研究,没有对频繁项集中如何高效地计算得到满足最小置信度的关联规则进行研究.针对这种情况,提出了一种高效关联规则的挖掘算法EA,解决了在挖掘关联规则过程中如何高效挖掘满足最小置信度的关联规则问题.     

一种高效的关联规则增量更新算法

对挖掘关联规则中FUP算法的关键思想以及性能进行了研究,提出了改进的FUP算法SFUP。该算法充分利用原有挖掘结果中候选频繁项集的支持数,能有效减少对数据库的重复扫描次数,并通过实验对这两种算法进行比较,结果充分说明了SFUP算法的效率要明显优于FUP算法。     

TopPI: An efficient algorithm for item-centric mining

In this paper, we introduce item-centric mining, a new semantics for mining long-tailed datasets. Our algorithm, TopPI, finds for each item its top-k most frequent closed itemsets. While most mining algorithms focus on the globally most frequent itemsets, TopPI guarantees that each item is represented in the results, regardless of its frequency in the database.TopPI allows users to efficiently explore Web data, answering questions such as “what are the k most common sets of songs downloaded together with the ones of my favorite artist?”. When processing retail data consisting of 55 million supermarket receipts, TopPI finds the itemset “milk, puff pastry” that appears 10,315 times, but also “frangipane, puff pastry” and “nori seaweed, wasabi, sushi rice” that occur only 1120 and 163 times, respectively. Our experiments with analysts from the marketing department of our retail partner demonstrate that item-centric mining discover valuable itemsets. We also show that TopPI can serve as a building-block to approximate complex itemset ranking measures such as the p-value.Thanks to efficient enumeration and pruning strategies, TopPI avoids the search space explosion induced by mining low support itemsets. We show how TopPI can be parallelized on multi-cores and distributed on Hadoop clusters. Our experiments on datasets with different characteristics show the superiority of TopPI when compared to standard top-k solutions, and to Parallel FP-Growth, its closest competitor.     

有效的矩阵加权正负关联规则挖掘算法——MWARM-SRCCCI

针对现有加权关联规则挖掘算法不能适用于矩阵加权数据的缺陷,给出一种新的矩阵加权项集剪枝策略,构建矩阵加权正负关联模式评价框架SRCCCI,提出一种新的基于SRCCCI评价框架的矩阵加权正负关联规则挖掘算法MWARM-SRCCCI。该算法克服了现有挖掘技术的缺陷,采用新的剪枝技术和模式评价方法,挖掘有效的矩阵加权正负关联规则,避免一些无效和无趣的模式产生。以中文Web测试集CWT200g为实验数据,与现有无加权正负关联规则挖掘算法比较,MWARM-SRCCCI算法的挖掘时间减幅最大可达74.74%。理论分析和实验结果表明,MWARM-SRCCCI算法具有较好的剪枝效果,候选项集数量和挖掘时间明显减少,挖掘效率得到极大提高,其关联模式可为信息检索提供可靠的查询扩展词来源。     

EDUA: An efficient algorithm for dynamic database mining

Maintaining frequent itemsets (patterns) is one of the most important issues faced by the data mining community. While many algorithms for pattern discovery have been developed, relatively little work has been reported on mining dynamic databases, a major area of application in this field. In this paper, a new algorithm, namely the Efficient Dynamic Database Updating Algorithm (EDUA), is designed for mining dynamic databases. It works well when data deletion is carried out in any subset of a database that is partitioned according to the arrival time of the data. A pruning technique is proposed for improving the efficiency of the EDUA algorithm. Extensive experiments are conducted to evaluate the proposed approach and it is demonstrated that the EDUA is efficient.     

An efficient genetic algorithm for automated mining of both positive and negative quantitative association rules

In this paper, a genetic algorithm (GA) is proposed as a search strategy for not only positive but also negative quantitative association rule (AR) mining within databases. Contrary to the methods used as usual, ARs are directly mined without generating frequent itemsets. The proposed GA performs a database-independent approach that does not rely upon the minimum support and the minimum confidence thresholds that are hard to determine for each database. Instead of randomly generated initial population, uniform population that forces the initial population to be not far away from the solutions and distributes it in the feasible region uniformly is used. An adaptive mutation probability, a new operator called uniform operator that ensures the genetic diversity, and an efficient adjusted fitness function are used for mining all interesting ARs from the last population in only single run of GA. The efficiency of the proposed GA is validated upon synthetic and real databases.     

一种有效的基于图的关联规则挖掘算法

基于图的关联规则挖掘算法是一种通过构建关联图并直接生成候选频繁项集,进而验证得到所有频繁项集的算法。在该算法中,对候选项集的验证操作占用了大量的时间,为此提出了改进算法。改进主要体现在两个方面：按支持度降序对频繁1项重新编号再构建关联图;利用Apriori性质删减用来生成候选项集的冗余扩展项节点。实验结果表明,在最小支持度阈值较小时,改进算法有效减少了冗余的候选频繁项集,提高了算法的性能。     

Progressive partition miner: an efficient algorithm for mining general temporal association rules

We explore a new problem of mining general temporal association rules in publication databases. In essence, a publication database is a set of transactions where each transaction T is a set of items of which each item contains an individual exhibition period. The current model of association rule mining is not able to handle the publication database due to the following fundamental problems, i.e., 1) lack of consideration of the exhibition period of each individual item and 2) lack of an equitable support counting basis for each item. To remedy this, we propose an innovative algorithm progressive-partition-miner (abbreviated as PPM) to discover general temporal association rules in a publication database. The basic idea of PPM is to first partition the publication database in light of exhibition periods of items and then progressively accumulate the occurrence count of each candidate 2-itemset based on the intrinsic partitioning characteristics. Algorithm PPM is also designed to employ a filtering threshold in each partition to early prune out those cumulatively infrequent 2-itemsets. The feature that the number of candidate 2-itemsets generated by PPM is very close to the number of frequent 2-itemsets allows us to employ the scan reduction technique to effectively reduce the number of database scans. Explicitly, the execution time of PPM is, in orders of magnitude, smaller than those required by other competitive schemes that are directly extended from existing methods. The correctness of PPM is proven and some of its theoretical properties are derived. Sensitivity analysis of various parameters is conducted to provide many insights into Algorithm PPM.     

An efficient algorithm for mining frequent inter-transaction patterns

In this paper, we propose an efficient method for mining all frequent inter-transaction patterns. The method consists of two phases. First, we devise two data structures: a dat-list, which stores the item information used to find frequent inter-transaction patterns; and an ITP-tree, which stores the discovered frequent inter-transaction patterns. In the second phase, we apply an algorithm, called ITP-Miner (Inter-Transaction Patterns Miner), to mine all frequent inter-transaction patterns. By using the ITP-tree, the algorithm requires only one database scan and can localize joining, pruning, and support counting to a small number of dat-lists. The experiment results show that the ITP-Miner algorithm outperforms the FITI (First Intra Then Inter) algorithm by one order of magnitude.     

An efficient algorithm for mining top-rank-k frequent patterns

Mining top-rank-k frequent patterns is a popular data mining task, which consists of discovering the patterns in a transaction database that belong to the k first ranks in terms of support. Although, several algorithms have been proposed for this task, it remains computationally expensive. To address this issue, this paper proposes a novel algorithm named BTK. It relies on a novel tree structure named TB-tree to store crucial information about frequent patterns. Moreover, BTK employs a new B-list structure to store information about patterns, and relies on subsume indexes to reduce the search space and speed up the discovery of top-rank-k frequent patterns. BTK also uses an early pruning strategy and an effective threshold raising mechanism. Additionally, BTK introduces two efficient procedures for respectively generating subsume indexes and intersecting B-lists. Extensive experiments were conducted on several datasets to evaluate the efficiency of the proposed algorithm. Results show that BTK is highly efficient and competitive.     

BitTableFI: An efficient mining frequent itemsets algorithm

Mining frequent itemsets in transaction databases, time-series databases and many other kinds of databases is an important task and has been studied popularly in data mining research. The problem of mining frequent itemsets can be solved by constructing a candidate set of itemsets first, and then, identifying those itemsets that meet the frequent itemset requirement within this candidate set. Most of the previous research mainly focuses on pruning to reduce the candidate itemsets amounts and the times of scanning databases. However, many algorithms adopt an Apriori-like candidate itemsets generation and support count approach that is the most time-wasted process. To address this issue, the paper proposes an effective algorithm named as BitTableFI. In the algorithm, a special data structure BitTable is used horizontally and vertically to compress database for quick candidate itemsets generation and support count, respectively. The algorithm can also be used in many Apriori-like algorithms to improve the performance. Experiments with both synthetic and real databases show that BitTableFI outperforms Apriori and CBAR which uses ClusterTable for quick support count.     

CBAR: an efficient method for mining association rules

The discovery of association rules is an important data-mining task for which many algorithms have been proposed. However, the efficiency of these algorithms needs to be improved to handle real-world large datasets. In this paper, we present an efficient algorithm named cluster-based association rule (CBAR). The CBAR method is to create cluster tables by scanning the database once, and then clustering the transaction records to the k-th cluster table, where the length of a record is k. Moreover, the large itemsets are generated by contrasts with the partial cluster tables. This not only prunes considerable amounts of data reducing the time needed to perform data scans and requiring less contrast, but also ensures the correctness of the mined results. Experiments with the FoodMart transaction database provided by Microsoft SQL Server show that CBAR outperforms Apriori, a well-known and widely used association rule.     

An efficient algorithm for incrementally mining frequent closed itemsets

The purpose of mining frequent itemsets is to identify the items in groups that always appear together and exceed the user-specified threshold of a transaction database. However, numerous frequent itemsets may exist in a transaction database, hindering decision making. Recently, the mining of frequent closed itemsets has become a major research issue because sets of frequent closed itemsets are condensed yet complete representations of frequent itemsets. Therefore, all frequent itemsets can be derived from a group of frequent closed itemsets. Nonetheless, the number of transactions in a transaction database can increase rapidly in a short time period, and a number of the transactions may be outdated. Thus, frequent closed itemsets may be changed with the addition of new transactions or the deletion of old transactions from the transaction database. Updating previously closed itemsets when transactions are added or removed from the transaction database is challenging. This study proposes an efficient algorithm for incrementally mining frequent closed itemsets without scanning the original database. The proposed algorithm updates closed itemsets by performing several operations on the previously closed itemsets and added/deleted transactions without searching the previously closed itemsets. The experimental results show that the proposed algorithm significantly outperforms previous methods, which require a substantial length of time to search previously closed itemsets.     

An efficient algorithm for mining periodic high-utility sequential patterns

A periodic high-utility sequential pattern (PHUSP) is a pattern that not only yields a high-utility (e.g. high profit) but also appears regularly in a sequence database. Finding PHUSPs is useful for several applications such as market basket analysis, where it can reveal recurring and profitable customer behavior. Although discovering PHUSPs is desirable, it is computationally difficult. To discover PHUSPs efficiently, this paper proposes a structure for periodic high-utility sequential pattern mining (PHUSPM) named PUSP. Furthermore, to reduce the search space and speed up PHUSPM, a pruning strategy is developed. This results in an efficient algorithm called periodic high-utility sequential pattern optimal miner (PUSOM). An experimental evaluation was performed on both synthetic and real-life datasets to compare the performance of PUSOM with state-of-the-art PHUSPM algorithms in terms of execution time, memory usage and scalability. Experimental results show that the PUSOM algorithm can efficiently discover the complete set of PHUSPs. Moreover, it outperforms the other four algorithms as the former can prune many unpromising patterns using its designed structure and pruning strategy.     

高效的关联规则挖掘算法

针对Apriori算法多次扫描数据库且生成的候选项集数量大的缺陷,提出了一种数据库优化策略,并结合修剪频繁集和连接优化策略,得到一种新的关联规则挖掘算法-NApriori算法.该算法减小了数据库的规模以及候选项集的数目,避免了连接过程中相同项目的重复比较.实验表明此方法比Apriori算法有更好的性能.     

A fast algorithm for mining association rules

In this paper,the problem of discovering association rules between items in a large database of sales transactions is discussed.and a novel algorithm,BitMatrix,is proposed.The proposed algorithm is fundamentally different from the known algorithms Apriori and AprioriTid.Empirical evaluation shows that the algorithm outperforms the known ones for large databases.Scale-up experiments show that the algorithm scales linearly with the number of transactions.     

一种高效的基于采样的关联规则挖掘算法

在事务数据集中发现项目间的关联规则是数据挖掘的一个经典问题,但传统的关联规则挖掘方法对于大事务数据集而言,执行效率相对较低。已经有研究表明,采样技术能有效地改善挖掘效率。在分析现有采样方法的基础上,提出了一种新的基于采样的高效关联规则挖掘算法ESMA。该算法采用了更加有效的双向采样策略。通过实验分析表明,该算法明显地加快了大事务数据库中采样的速度,从而降低了CPU时间,而且具有很好的可扩展性。     

双向关联规则挖掘提取算法

传统的关联规则挖掘是单向的,不能确定相互依赖的规则,找到的规则不一定是有意义的,甚至是错误的。鉴于此,本文在分析的基础上,提出双向关联规则挖掘算法。并根据其相关性找出对我们有意义的规则。