# Data Mining Algorithms In R/Frequent Pattern Mining/arulesNBMiner
## Introduction

The technique to be discussed in this chapter is used in frequent itemset mining. There are several situations which people are interested in co-occurrence of two or more items of a set. It is important to establish which items co-occur, since association rules can be extracted from frequent itemsets [1]. A typical example of an application is a supermarket where one discovers 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 that, in general, customers 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. In addition, 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 assumption is that 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 most items occurring infrequently, while just some of them occur with high frequency. In a 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 such a way that a user does not need to determine a min_support. However, he needs to inform the minimum size of itemsets (min_l) and the number of itemsets (k) he wishes to mine. Furthermore, the TFP algorithms only mine frequent closed itemsets.[2]. Again, the user has a parameter (min_l) which he should specify before mining the data, which is a subtle decision.
Therefore, this chapter presents an algorithm, which is implemented in an 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 the package is arulesNBMiner, which is a Java implementation of a depth first search algorithm to mine NB-frequent itemsets of NB-precise rules [4]. The algorithm utilizes the information contained in its own data structure to estimate the minimum support. It then uses a precision limit to estimate the min_support for each k-itemset, plus one extension it calculates at a different minimum support.

## Technique to be discussed
### Implementation (description of used modules and packages)

The first thing one has to do to use NBMiner is installing the NBMiner package. This package has three dependencies packages: arules (http://cran.r-project.org/web/packages/arules/index.html) which provides the infrastructure for representing, manipulating and analyzing transaction data and patterns (frequent itemsets and association rules), Matrix (http://cran.r-project.org/web/packages/Matrix/index.html) which is classes and methods for dense and sparse matrices and operations on them using Lapack and SuiteSparse, and lettice (http://cran.r-project.org/web/packages/lattice/index.html) which is a framework for data visualization developed at the Bell Labs. Besides, the user has to install on computer the Sun Java(TM) Development Kit (JDK) 6, since the NBMiner uses a package called rJava which is part of JDK. This must be installed in the user operational system.
Installation of the dependencies packages can be performed within the R environment using the function "install.packages(“package name”)". The name of NBMiner package is arulesNBMiner.
After the user installed the necessaries packages, he must load them. This can be done using the function "library(package name)".
However, before we show how to use the NBMiner package, it is necessary to show how to load the data. Here, we are using a data on csv format. In this format each line is a transaction like the example below:
| Employment | Education | Marital | Occupation | Sex | Accounts |
| Private | College | Separated | Service | Female | USA |
| Private | Associate | Unmarried | Transport | Male | Jamaica |
| Private | HSgrad | Divorced | Clerical | Male | USA |
| Private | Bachelor | Civil | Repair | Male | USA |
| Private | College | Civil | Executive | Male | USA |
| Private | HSgrad | Civil | Service | Male | USA |
Using the function "read.table" on R environment, we are able to load the data. This function creates a "data.frame" object. Its syntax is:
The argument header indicates the data has or does not a header while the sep indicates which character is being used to separate the elements. Later, the user has to transform this data frame object in a transaction object. For that, he can use the function "as". Its syntax is:
It is important to mention the user has to load the NBMiner package before he uses the function as with parameter transaction. Furthermore, there is another data format that some R functions can read and transform it in a transaction object. The user can utilize a binary format like the example below:
| 1 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 0 |
| 1 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 |
| 1 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 1 |
| 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 |
| 1 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 1 |
Here, each line represents a transaction and each column represents a term of the database. The number 1 means presence of that term in that transaction, while 0 means no presence. To read this data, user can first utilize the function "scan". It creates a vector object, and its syntax is:
After that, it is necessary to transform the vector object in a matrix object. This is performed using the function "dim". Its syntax is:
Dim1 and Dim2 are the dimensions of the matrix which the user want creating. If the user wants, he can name each row and column of the matrix using the function "dimnames". Its syntax is:
Where pridim is a vector with first dimension names, and segdim is a vector with second dimension names. Finally, this object can be transformed in transaction object using the function "as". Its syntax is:
Soon after the user loaded the package and the data, it is necessary to create the parameters object using the function of NBMiner called "NBMinerParameters". This function reads the data and extracts from them some parameters which will be used in the next step. The syntax of this function is:
After the user perform this procedure, he is able to run the algorithm to mine his data. For that, one will use the function called "NBMiner". Its syntax is:
If the user uses the option rules=TRUE when he created the object parameter, the algorithm will mine the NB-precise rules. Otherwise, the same algorithm will mine the NB-frequent itemsets.
Finally, we summarized the necessaries commands to use the NBMiner package for mining tasks using the first data structure mentioned above, these are below:

### Visualization

To visualize data information contained in a “data.frame” object just use the object name. Here, we use table as object name:
| # | Employment | Education | Marital | Occupation | Sex | Accounts |
| 1 | Private | College | Separated | Service | Female | USA |
| 2 | Private | Associate | Unmarried | Transport | Male | Jamaica |
| 3 | Private | HSgrad | Divorced | Clerical | Male | USA |
| 4 | Private | Bachelor | Civil | Repair | Male | USA |
| 5 | Private | College | Civil | Executive | Male | USA |
| 6 | Private | Hsgrad | Civil | Service | USA |
However, when the same principle is used in “transactions” format, we have just the number of transactions and items generated by the "as" function:
Use “inspect” function to visualize the result of the conversion to the “transactions” format:
| # | items | transactionID |
| 1 | {Employment=Private,Education=College,Marital=Separated,Occupation=Service,Sex=Female,Accounts=USA} | 1 |
| 2 | {Employment=Private,Education=Associate,Marital=Unmarried,Occupation=Transport,Sex=Male,Accounts=Jamaica} | 2 |
To summarize the data information in "transaction" format use "summary".
To see labels of the items generated in the conversion to transaction format use “itemInfo”:
Use “labels” to see only the labels of the itens and transactions:
To see NB mined results use the same commands above mentioned to “transactions” data:
Where "lhs" is the antecedent of the rules and de "rhs" is the consequent of the rules.
We can also show the data distribution in the space with “image” function:
File:ImageFunction.png

## Case study
### Scenario

It contains artificial data created by Graham Williams (developer of Rattle) and is supplied with Rattle. To quote from the Rattle documentation: "It consists of 2,000 fictional clients who have been audited, perhaps for compliance with regard to the amount of a tax refund that is being claimed. For each case an outcome is recorded (whether the taxpayer's claims had to be adjusted or not) and any amount of adjustment that resulted is also recorded."

### Input data no longer exists to download

Available on http://cs.anu.edu.au/Student/comp3420/mining/audit.csv.

### Analysis

| rules | consequent | precedent A | precedent B | precedent C | precedent D |
| 92 | Accounts=China | Employment=PSState | Education=Master | Occupation=Professional |
| 4721 | Accounts=China | Employment=PSState | Education=Master | | |
| 4762 | Accounts=China | Employment=PSState | Occupation=Professional | | |
| 4857 | Accounts=China | Education=Master | Marital=Civil | Occupation=Professional | Sex=Male |
| 5871 | Accounts=China | Education=Master | Occupation=Professional | | |
| 6131 | Accounts=China | Marital=Civil | Occupation=Professional | | |
| 10269 | Accounts=China | Education=Master | Occupation=Professional | Sex=Male | |
| 10386 | Accounts=China | Education=Master | Marital=Civil | Occupation=Professional | |
| 14791 | Accounts=China | Marital=Civil | Occupation=Professional | Sex=Male | |
Based on the data above we can note that when the Marital state is “Civil” and the "Occupation" is "Professional" we have an "Chinese" account.

## References

* [1]Mohammed j. Zaki and Wagner Meira Jr. Fundamentals of Data Mining Algorithms. Chaper 11 – Itemset Mining, 74-93
* [2]Jianyong Wang, Jiawei Han, Ying Lu and Petre Tzvetkov. TFP: An efficient algorithm for mining Top-K frequent closed itemsets. IEEE Transactions on Knowledge and Data Engineering, 17(5):652-665, May 2005
* [3]Michael Hahsler. A model-based frequency constraint for mining associations from transaction data. Data Mining and Knowledge Discovery, 13(2):137-166, September 2006.
* [4]http://cran.fiocruz.br/web/packages/arulesNBMiner/index.html