Introduction

The technique to be discussed in this chapter is used in frequent itemset mining. There are several situations which people are interested on co-occurrence of two or more item of a set. It is important to establish which items co-occur, since based on them, association rules can be extracted between itemsets [1]. A typical example of an application is about a supermarket when one discovery customers who buy meat and beer also tend to buy coal. Thus, a frequent item set would be meat-beer-coal and an association rule would be customers, in general, who buy meat and beer, have more chances to buy coal.

Many works have dealt with the problem of frequent itemset mining. Most of them show the necessity of a min_support threshold, which is an itemset minimum frequency in the data and in general defined by the miner user. Besides, these studies have as goal to mine a complete set of frequent itemsets that satisfy min_support [2]. The application of a minimum support results in several assumptions which are rarely discussed or verified. One assumptions is items occur in the database following a, possibly unknown, but stable process and that the items occur in the database with roughly similar frequencies. Nevertheless, in the real world, transactions data have a frequency distribution highly skewed with almost items occurring in an infrequent way while just some of them occur with high frequency. In database where this phenomenon happens, interesting patterns are not found since some of the associated items are too infrequent to satisfy the user-specified minimum support [3].

Some algorithms such as TFP were developed in a way that a user do not need determine a min_support, however, he needs to inform the minimum size of itemset (min_l) and the number of itemset which he desires mining (k). Furthermore, the TFP algorithms just mine frequent closed itemset.[2]. Again, the user has a parameter (min_l) which he should specify before mining the data, what is a subtle decision.

Therefore, this chapter presents an algorithm, which is implemented at R-package and uses a simple stochastic model (Negative Binomal model or NB-model) to estimate a minimum support utilizing knowledge of the process which generates transaction data and allows for highly skewed frequency distributions. The name of package in R program is arulesNBMiner that is the Java implementation of a depth first search algorithm to mine NB-frequent itemsets of NB-precise rules [4]. Beside the algorithm utilize the information contained in own data structure to estimate the minimum support, it uses a precision limit to estimate min_support and for each k-itemset plus 1 extension it calculates a different minimum support.