Fast algorithms for mining association rules in large databases pdf

More Filters. Highly Influenced. View 9 excerpts, cites methods and background. View 2 excerpts, cites methods. The role of Apriori algorithm for finding the association rules in Data mining. View 4 excerpts, cites background. Parallel mining of association rules using a lattice based approach. View 1 excerpt, cites background.

Fast mining of association rules in large-scale problems. View 5 excerpts, cites methods and results. View 3 excerpts, cites background and methods. Two revised algorithms based on apriori for mining association rules.

View 2 excerpts, cites background. Mining association rules between sets of items in large databases. View 10 excerpts, references methods, background and results. Efficient Algorithms for Discovering Association Rules. It is only for which is as follows. Figure 5. However, Apriori still examines every Figure 7 shows the performance of AprioriHybrid transaction in the database. On the other hand, relative to Apriori and AprioriTid for three datasets. For T DK with 1.

In general, Apriori the advantage of AprioriHybrid over Apriori depends 12 AprioriTid on how the size of the C k set decline in the later passes. If C k remains large until nearly the end and 10 then has an abrupt drop, we will not gain much by using AprioriHybrid since we can use AprioriTid only Time sec 8 for a short period of time after the switch. This is 6 what happened with the T DK dataset. We used the combinations Based on these observations, we can design a T5.

I2 , T I4 , and T I6 for the average sizes hybrid algorithm, which we call AprioriHybrid, that of transactions and itemsets respectively. All other uses Apriori in the initial passes and switches to parameters were the same as for the data in Table 3. The memory in the next pass. As shown, the execution times scale quite linearly.

I6 AprioriHybrid T I4 10 T5. I6 AprioriTid T I4 50 Apriori 12 T5. We increased the num- ber of items from to 10, for the three pa- rameter settings T5. DK, T DK and Time sec T All other parameters were the same as for the data in Table 3. We ran experiments for a minimum support at 0. The execution times decreased a little since the average support for an item decreased as we increased the number of items. This resulted in fewer large itemsets and, hence, faster execution 0 times. Finally, we investigated the scale-up as we increased 2 1.

The aim of this Figure 7: Execution times: AprioriHybrid experiment was to see how our data structures scaled with the transaction size, independent of other factors like the physical database size and the number of large itemsets. I6 40 T I4 T5. I2 25 35 30 20 Time sec Time sec 25 15 20 15 10 10 5 5 0 0 5 10 20 30 40 50 Number of Items Transaction Size Figure 9: Number of items scale-up Figure Transaction size scale-up database roughly constant by keeping the product posed algorithms can be combined into a hybrid al- of the average transaction size and the number of gorithm, called AprioriHybrid, which then becomes transactions constant.

The number of transactions the algorithm of choice for this problem. Scale-up ex- ranged from , for the database with an average periments showed that AprioriHybrid scales linearly transaction size of 5 to 20, for the database with with the number of transactions. In addition, the ex- an average transaction size Fixing the minimum ecution time decreases a little as the number of items support as a percentage would have led to large in the database increases.

As the average transaction increases in the number of large itemsets as the size increases while keeping the database size con- transaction size increased, since the probability of stant , the execution time increases only gradually.

The results are shown in The algorithms presented in this paper have been Figure The numbers in the key e. The main reason for the increase was that customer data, the details of which can be found in in spite of setting the minimum support in terms [5]. In the future, we plan to extend this work along of the number of transactions, the number of large the following dimensions: itemsets increased with increasing transaction length.

An example of such a present in a transaction took a little longer time. The performance gap increased with the in the context of the Quest project at the IBM Al- problem size, and ranged from a factor of three for maden Research Center. In Quest, we are exploring small problems to more than an order of magnitude the various aspects of the database mining problem. Machine Learning, sequences [1].

We believe that database mining is an 2 2 , Han, Y. Cai, and N. Knowledge questions. In Proc. Holsheimer and A. Data mining: The References search for knowledge in databases.

Agrawal, C. Faloutsos, and A. Houtsma and A. Set-oriented mining In Proc. Agrawal, S. Ghosh, T. Imielinski, B. Iyer, and [14] R. Krishnamurthy and T. Practi- A. Columbia, Canada, Langley, H. Simon, G. Bradshaw, and [3] R. Agrawal, T. Imielinski, and A. Explorations of the Creative Process. Special [16] H. Mannila and K. Dependency Issue on Learning and Discovery in Knowledge- inference. Mining [17] H.

Mannila, H. Toivonen, and A. Muggleton and C. Agrawal and R. Fast algorithms for of logic programs. Muggleton, editor, mining association rules in large databases. Re- Inductive Logic Programming.

Center, San Jose, California, June Probabilistic reasoning in intelligent [6] D. The new direct marketing. Business One Irwin, Illinois, Discovery, analy- [7] R. Brachman et al. Integrated support for data sis, and presentation of strong rules. In archeology. Breiman, J. Friedman, R. Olshen, and [21] G. Piatestsky-Shapiro, editor. Continuing with a specified threshold, the leaf node is converted to an the previous example, consider a transaction 1 2 interior node.

Similarly, an t aa follows. If we are at a leaf, we find which of additional three candidate itemsets will be generated the itemsets in the leaf are contained in t and add by extending the other large itemsets in LB, leading references to them to the answer set.

If we are at an to a total of 5 candidates for consideration in the interior node and we have reached it by hashing the fourth pass. For the root node, we hash possibly have minimum support. For any itemset c contained in transaction t, the have minimum support.

Hence, if we extended each first item of c must be in t. At the root, by hashing on itemset in Lk-i with all possible items and then every item in t, we ensure that we only ignore itemsets deleted all those whose k - 1 -subsets were not in that start with an item not in t. Similar arguments Lk-1, we would be left with a superset of the itemsets apply at lower depths. The only additional factor is in Lk. The condition p. By uses the apriori-gen function given in Section 2.

The interesting feature of this algorithm is Lk-1, also does not delete any itemset that could be that the database V is not used for counting support in Lk. Rather, the set ck is used for this purpose. This variation can pay off in the generated by the algorithm step If a transaction does and we terminate. In addition, for large values of Ic, , , 1 I , each entry may be smaller than the corresponding transaction because very few candidates may be contained in the transaction.

However, for small 2 values for L, each entry may be larger than the Ll Support 1 corresponding transaction because an entry in Ck Itemset Support 1 includes all candidate k-itemsets contained in the 11 2 2 transaction. See [5] for a proof of 77 5 3 3 correctness and a discussion of buffer management. Each set of candidate itemsets Ck is kept assume that minimum support is 2 transactions. In steps 6 through 10, we Each i? The first entry in itemset Ck by joining two large k - I -itemsets.

The Ct at step 7 corresponding to this entry t itemset: i generators and ii edensions. The extensions field of an itemset Calling apriori-gen with Lp gives C3. Note that are extensions of ck. Thus, when a candidate ck is there is no entry in Es for the transactions with TIDs generated by joining Ii-1 and Ziel, we save the IDS and , since they do not contain any of the of I and IiD1 in the generators field for ck. At the itemsets in Cs. The candidate 2 3 5 in C3 turns same time, the ID of ck is added to the extensions out to be large and is the only member of LB.

When field of Zisl. Recall that the AIS algorithm generates. However, to use the that the t. For structure. At the end of the pass, the support count each Ck in Tk, the generators field gives the IDS of of candidate itemsets is determined by sorting and the two itemsets that generated ck. If these itemsets aggregating this sequential structure. TID, and transactions with the candidate itemsets.

To avoid add c to Ct. For each candidate formance of the Apriori and AprioriTid algorithms. Moreover, when we are ready to sults. Finally, we describe how the best performance count the support for candidate itemsets at the end features of Apriori and AprioriTid can be combined of the pass, i? After counting and pruning out scale-up properties. After reading a transaction, it is determined which of the itemsets 3. New candidate itemsets performance of the algorithms over a large range of are generated by extending these large itemsets with data characteristics.

These transactions mimic the other items in the transaction. A large itemset 1 is transactions in the retailing environment. Each such set is potentially a any of the items in 1. The candidates generated maximal large itemset. An example of such a set from a transaction are added to the set of candidate might be sheets, pillow case, comforter, and ruffles. For instance, some people created by an earlier transaction. See [4] for further might buy only sheets and pillow case, and some only details of the AIS algorithm.

A transaction may contain more than one large itemset. For example, a customer might place an 3. Like AIS, another large itemset. Transaction sizes are typically the SETM algorithm also generates candidates on- clustered around a mean and a few transactions have the-fly based on transactions read from the database.

When adding an itemset to a transaction, we keep dropping Table 2: Parameters an item from the itemset as long as a uniformly distributed random number between 0 and 1 is less than c. Thus for an itemset of size 1, we will add 1 ITI Average size of the transactions items to the transaction 1 - c of the time, I- 1 items Average size of the maximal potentially c 1 - c of the time, I- 2 items c2 1 - c of the time, I,1 etc. The corruption level for an itemset is fixed and IL1 Number of maximal potentially large itemsets is obtained from a normal distribution with mean 0.

We first determine the size of the next transaction. We chose 3 values for ITI: 5, 10, and We mean p equal to ITI. Note that if each item is chosen also chose3 values for ,4, and 6. The number of with the same probability p, and there are N items, transactions was to set to , because, as we will the expected number of items in a transaction is given see in Section 3.

However, for our scale-up experiments, we and is approximated by a Poisson distribution with generated datasets with up to 10 million transactions mean Np. Table 3 summarizes the dataset We then assign items to the transaction. Each parameter settings. For the same ITI and values, transaction is assigned a series of potentially large the size of datasets in megabytes were roughly equal itemsets.

If the large itemset on hand does not fit in for the different values of There is an inverse relationship between IL1 and the average support for potentially large itemsets. Items in the first itemset are chosen randomly. To model the phenomenon 3. We use an synthetic datasets given in Table 3 for decreasing exponentially distributed random variable with mean values of minimum support.

As the minimum support equal to the correlation level to decide this fraction decreases, the execution times of all the algorithms for each itemset. The remaining items are picked at increase because of increases in the total number of random.

In the datasets used in the experiments, candidate and large itemsets. We ran some For SETM, we have only plotted the execution experiments with the correlation level set to 0. DlOOK in Figure 4. The 0. Each itemset in 1 has a weight associated with We did not plot the execution times in Table 4 it, which corresponds to the probability that this on the corresponding graphs because they are too itemset will be picked.

This weight is picked from large compared to the execution times of the other an exponential distribution with unit mean, and is algorithms. For the three datasets with transaction then normalized so that the sum of the weights for all sizes of 20, SETM took too long to execute and the itemsets in 7 is 1.

The next itemset to be put we aborted those runs as the trends were clear. DlOOK T The largest dataset in the scale- Dataset T Note that Dataset T For The problem with AIS is that it generates too many small problems, AprioriTid did about as well as candidates that later turn out to be small, causing Apriori, but performance degraded to about twice as it to waste too much effort.

Apriori also counts too slow for large problems. However, this wastage decreases dramatically from the third pass To explain these performance trends, we show in Figure 5 the sizes of the large and candidate sets in onward. Note that for the example in Figure 5, after different passesfor the T DlOOK dataset for the pass 3, almost every candidate itemset counted by minimum support of 0. Note that the Y-axis in Apriori turns out to be a large set.

As a result, the?? Apri- oriTid is also able to use a single word ID to store a candidate rather than requiring as many words as the number of items in the candidate. Hence, AprioriTid is very effective in later passes when the size of?? Before writing out entries in Ek to The fundamental problem with the SETM algo dish, we can sort them on itemsets using an internal sorting procedure, and write them as sorted runs.

These sorted NOB rithm is the size of its i!? Recall that the size of can then be merged to obtain support counts. However, the set?? However, this would Thus, the sets ck are roughly S times bigger than the destroy the set-oriented nature of the algorithm. Aiso, once we corresponding ck sets, where S is the averagesupport have the hash table which gives us the IDS of candidates, we might as weil count them at the same time and avoid the two count of the candidate itemsets.