A graph-based approach for discovering various types of associationrules

Mining association rules is an important task for knowledge discovery. We can analyze past transaction data to discover customer behaviors such that the quality of business decisions can be improved. Various types of association rules may exist in a large database of customer transactions. The strategy of mining association rules focuses on discovering large item sets, which are groups of items which appear together in a sufficient number of transactions. We propose a graph-based approach to generate various types of association rules from a large database of customer transactions. This approach scans the database once to construct an association graph and then traverses the graph to generate all large item sets. Empirical evaluations show that our algorithms outperform other algorithms which need to make multiple passes over the database     

A new approach for generating efficient sample from market basket data

Classical data mining algorithms require expensive passes over the entire database to generate frequent items and hence to generate association rules. With the increase in the size of database, it is becoming very difficult to handle large amount of data for computation. One of the solutions to this problem is to generate sample from the database that acts as representative of the entire database for finding association rules in such a way that the distance of the sample from the complete database is minimal. Choosing correct sample that could represent data is not an easy task. Many algorithms have been proposed in the past. Some of them are computationally fast while others give better accuracy. In this paper, we present an algorithm for generating a sample from the database that can replace the entire database for generating association rules and is aimed at keeping a balance between accuracy and speed. The algorithm that is proposed takes into account the average number of small, medium and large 1-itemset in the database and average weight of the transactions to define threshold condition for the transactions. Set of transactions that satisfy the threshold condition is chosen as the representative for the entire database. The effectiveness of the proposed algorithm has been tested over several runs of database generated by IBM synthetic data generator. A vivid comparative performance evaluation of the proposed technique with the existing sampling techniques for comparing the accuracy and speed has also been carried out.     

一种新的基于FP-Tree的关联规则增量式更新算法

挖掘关联规则是数据挖掘研究的一个重要方面,目前已经提出了许多算法用于高效地发现大规模数据库中的关联规则,而维护已发现的关联规则同样是重要的.针对在事务数据库增加和最小支持度同时发生变化的情况下,如何进行关联规则的更新问题进行了研究,提出了一种新的基于频繁模式树的关联规则增量式更新算法,并对该算法进行了分析和讨论.     

Maintaining the discovered high-utility itemsets with transaction modification

Most approaches for discovering frequent itemsets derive association rules from a binary database. Profit, cost, and quantity are not considered in traditional association-rule mining. Utility mining was proposed to measure the utilities of purchase products to derive highutility itemsets (HUIs). Many algorithms have been proposed to efficiently find HUIs from a static database. In real-world applications, transactions are inserted, deleted, or modified in dynamic situations. Existing batch approaches have to re-process the updated database since previously discovered HUIs are not maintained. In this paper, a Fast UPdated (FUP) strategy with utility measure and a maintenance algorithm, called FUP-HUI-MOD, are developed to efficiently maintain and update discovered HUIs. When transactions are modified, the proposed algorithm partitions the transactions before and after the modification into two parts, creating four cases. Each case is maintained using a specific procedure to update the discovered HUIs. Based on the designed FUP-HUI-MOD algorithm, the original database is not required to be rescanned each time compared to the state-of-the-art high-utility itemset mining algorithms in batch mode. Experiments are conducted to show that the proposed algorithm outperforms batch algorithms in maintaining HUIs.     

一种基于BUC的水平加权关联规则挖掘算法

关联规则挖掘可以从大量数据中发现项集间潜在而有趣的相互联系。针对用户对每个项目感兴趣的程度不同,一些学者提出了水平加权关联规则。然而每次生成新候选集后对整个数据库事物的扫描成为算法效率的一大瓶颈。为进一步提高加权关联规则的挖掘效率,在原有的水平加权关联规则算法的基础上,采取了深度优先的策略,提出了一种基于BUC的水平加权关联规则挖掘算法——BUc—MINWAL。改进算法可以大大减少对数据库的扫描范围。实验结果表明,改进的算法有更好的执行效率。     

Multipass Algorithms for Mining Association Rules in Text Databases

In this paper, we propose two new algorithms for mining association rules between words in text databases. The characteristics of text databases are quite different from those of retail transaction databases, and existing mining algorithms cannot handle text databases efficiently because of the large number of itemsets (i.e., words) that need to be counted. Two well-known mining algorithms, Apriori algorithm and Direct Hashing and Pruning (DHP) algorithm, are evaluated in the context of mining text databases, and are compared with the new proposed algorithms named Multipass-Apriori (M-Apriori) and Multipass-DHP (M-DHP). It has been shown that the proposed algorithms have better performance for large text databases. Received 12 November 1999 / Revised 27 September 2000 / Accepted in revised form 25 October 2000     

典型关联规则挖掘算法的分析与比较

关联规则的发现是数据挖掘的一个重要方面,目前许多研究人员正致力于关联规则的快速开采算法的研究。文中介绍了几种典型的开采大型事务数据库中所有关联规则的算法,特别针对算法过程中产生候选频繁项集的大小和所需扫描事务数据库的次数这两个影响关联规则挖掘效率的关键问题,分析各个算法采用的解决策略及相应的局限性,并比较它们的时间效率和空间效率。最后展望了关联规则挖掘算法的研究方向。     

约束性相联规则发现方法及算法

文中研究了在大型事务７库中发现有约束条件的相联规则问题,提出了有效实现约束性相联规则发现的两种方法,过滤数据库算法Ｆｉｌｔｅｒｉｎｇ和频繁项集生成算法Ｓｅｐａｒａｔｅ,这两种可以同时并有物方法比已有算法运算效率有显著性提高。     

Incrementally building frequent closed itemset lattice

A concept lattice is an ordered structure between concepts. It is particularly effective in mining association rules. However, a concept lattice is not efficient for large databases because the lattice size increases with the number of transactions. Finding an efficient strategy for dynamically updating the lattice is an important issue for real-world applications, where new transactions are constantly inserted into databases. To build an efficient storage structure for mining association rules, this study proposes a method for building the initial frequent closed itemset lattice from the original database. The lattice is updated when new transactions are inserted. The number of database rescans over the entire database is reduced in the maintenance process. The proposed algorithm is compared with building a lattice in batch mode to demonstrate the effectiveness of the proposed algorithm.     

一种基于多数组的频繁模式挖掘算法

提出了一种新颖的频繁模式挖掘算法,该算法与现有的挖掘算法相比具有明显的优点,首先,该算法不需要产生候选项集,其次该算法具有更少的数据库扫描次数,该算法在中小型数据库上挖掘关联规则只需要扫描交易数据库一次,对于大型交易数据库的关联规则挖掘最多也只需要扫描交易数据库两次。因而,该算法与现有的频繁模式挖掘算法相比具有更高的效率。     

Efficient algorithms for distortion and blocking techniques in association rule hiding

Data mining provides the opportunity to extract useful information from large databases. Various techniques have been proposed in this context in order to extract this information in the most efficient way. However, efficiency is not our only concern in this study. The security and privacy issues over the extracted knowledge must be seriously considered as well. By taking this into consideration, we study the procedure of hiding sensitive association rules in binary data sets by blocking some data values and we present an algorithm for solving this problem. We also provide a fuzzification of the support and the confidence of an association rule in order to accommodate for the existence of blocked/unknown values. In addition, we quantitatively compare the proposed algorithm with other already published algorithms by running experiments on binary data sets, and we also qualitatively compare the efficiency of the proposed algorithm in hiding association rules. We utilize the notion of border rules, by putting weights in each rule, and we use effective data structures for the representation of the rules so as (a) to minimize the side effects created by the hiding process and (b) to speed up the selection of the victim transactions. Finally, we study the overall security of the modified database, using the C4.5 decision tree algorithm of the WEKA data mining tool, and we discuss the advantages and the limitations of blocking.     

Discovering knowledge from large databases using prestored information

In this paper, we examine the two issues of mining association rules and mining sequential patterns in a large database of sales transactions. The problems of mining association rules and mining sequential patterns focus on discovering large itemsets and large sequences, respectively. We present PSI and PSI_seq for efficient large itemsets generation and large sequences generation, respectively. The main ideas of these two algorithms are using prestored information to minimize the numbers of candidate itemsets and candidate sequences counted in each database scan. The prestored informations for PSI and PSI_seq include the itemsets and the sequences along with their support counts found in the last mining, respectively. Typically a user may require to tune the value of the minimum support many times before a set of useful association rules can be obtained from the transaction database. Using prestored information, the total computation time will be reduced effectively. Empirical results show that our approaches outperform previous methods by an order of magnitude, using little storage space for the prestored information.     

Incrementally mining high utility patterns based on pre-large concept

In traditional association rule mining, most algorithms are designed to discover frequent itemsets from a binary database. Utility mining was thus proposed to measure the utility values of purchased items for revealing high utility itemsets from a quantitative database. In the past, a two-phase high utility mining algorithm was thus proposed for efficiently discovering high utility itemsets from a quantitative database. In dynamic data mining, transactions may be inserted, deleted, or modified from a database. In this case, a batch mining procedure must rescan the whole updated database to maintain the up-to-date information. Designing an efficient approach for handling dynamic databases is thus a critical research issue in utility mining. In this paper, an incremental mining algorithm is proposed for efficiently maintaining discovered high utility itemsets based on pre-large concepts. Itemsets are first partitioned into three parts according to whether they have large (high), pre-large, or small transaction-weighted utilization in the original database and in inserted transactions. Individual procedures are then executed for each part. Experimental results show that the proposed incremental high utility mining algorithm outperforms existing algorithms.     

负增量式关联规则更新算法

模式维护是数据挖掘中一个具有挑战性的任务.现有的增量式关联规则更新算法主要解决两种情况下的维护问题：一是最小支持度不变,而数据量增加;二是数据量不变,而改变最小支持度.本文提出了一种负增量关联规则更新算法.实验表明,该算法是有效的.     

Batch incremental processing for FP-tree construction using FP-Growth algorithm

In the present scenario of global economy and World Wide Web, large sets of evolving and distributed data can be handled efficiently by incremental data mining. Frequent patterns are very important in knowledge discovery and data mining process, such as mining of association rules, correlations. FP-tree is a very versatile data structure used for mining of frequent patterns in knowledge discovery and data mining process. FP-tree is a compact representation of transaction database that contains frequency information of all relevant frequent patterns (FP) of the database. All of the existing incremental frequent pattern mining algorithms, such as AFPIM, CATS, CanTree, CP-tree, and SPO-tree, perform incremental mining by processing one transaction of the incremental part of database at a time and updating it to the FP-tree of initial (original) database. Here, in this paper, we propose a novel method that takes advantage of FP-tree representation of incremental transaction database for incremental mining. We propose a batch incremental processing algorithm BIT_FPGrowth that restructures and merges two small consecutive duration FP-trees to obtain a FP-tree of the FP-Growth algorithm. Our BIT_FPGrowth uses FP-tree as preprocessed data repository to get transactions (i.e., item-sets), unlike other sequential incremental algorithms that read transactions from database. BIT_FPGrowth algorithm takes less time for constructing FP-tree. Our experimental results show that, as the size of the database increases, increase in runtime of BIT_FPGrowth is much less and is least of all the other algorithms.     

一种改进的关联规则维护算法

提出了关联规则维护更新问题的背景,分析了经典的关联规则维护算法FUP2算法的局限性,针对在数据库数据集增加和删除时最小支持度同时变化的情况,提出了一种改进的关联规则维护算法EFUP,并与经典的Apriori算法进行了分析比较,表明了该算法充分利用了原有的信息,提高了算法的效率。     

基于频繁模式树的关联规则增量式更新算法

研究了大型事务数据库中关联规则的增量式更新总是，提出了一种基于频繁模式树的关联规则增量式更新算法，以处理最小支持度或事务数据库发生变化后相应关联规则的更新问题，并对其性能进行了分析。     

Multi-objective genetic algorithms based automated clustering for fuzzy association rules mining

Researchers realized the importance of integrating fuzziness into association rules mining in databases with binary and quantitative attributes. However, most of the earlier algorithms proposed for fuzzy association rules mining either assume that fuzzy sets are given or employ a clustering algorithm, like CURE, to decide on fuzzy sets; for both cases the number of fuzzy sets is pre-specified. In this paper, we propose an automated method to decide on the number of fuzzy sets and for the autonomous mining of both fuzzy sets and fuzzy association rules. We achieve this by developing an automated clustering method based on multi-objective Genetic Algorithms (GA); the aim of the proposed approach is to automatically cluster values of a quantitative attribute in order to obtain large number of large itemsets in less time. We compare the proposed multi-objective GA based approach with two other approaches, namely: 1) CURE-based approach, which is known as one of the most efficient clustering algorithms; 2) Chien et al. clustering approach, which is an automatic interval partition method based on variation of density. Experimental results on 100 K transactions extracted from the adult data of USA census in year 2000 showed that the proposed automated clustering method exhibits good performance over both CURE-based approach and Chien et al.’s work in terms of runtime, number of large itemsets and number of association rules.     

Shared-nothing并行事务数据库系统中规则的挖掘与更新算法

关联规则是数据挖掘中的一个重要研究内容．本文提出了Shared—nothing并行事务数据库系统(简称SNPDBS)中一种快速的关联规则挖掘算法SNPMAR，并考虑当最小支持度发生变化后SNPDBS中关联规则的高效更新问题，提出了一种有效的关联规则更新算法SNPIUA．     

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

关联规则是数据挖掘中的一个重要研究内容。目前已经提出了许多用于高效地发现大规模数据库中的关联规则的算法,而对已发现规则的更新及维护问题的研究却较少。文章提出了基于频繁模式树的关联规则增量式更新算法,以处理事务数据库中增加了新的事务数据集后相应关联规则的更新问题,并对其性能进行了分析。