# Data Mining Algorithms In R/Frequent Pattern Mining/The Apriori Algorithm
## Introduction

In computer science and data mining, Apriori is a classic algorithm for learning association rules. Apriori is designed to operate on databases containing transactions. As is common in association rule mining, given a set of itemsets, the algorithm attempts to find subsets which are common to at least a minimum number C of the itemsets. Apriori uses a "bottom up" approach, where frequent subsets are extended one item at a time (a step known as candidate generation), and groups of candidates are tested against the data. The algorithm terminates when no further successful extensions are found.
Apriori uses breadth-first search and a tree structure to count candidate item sets efficiently. It generates candidate item sets of length $k$ from item sets of length $k-1$. Then it prunes the candidates which have an infrequent sub pattern. According to the downward closure lemma, the candidate set contains all frequent $k$-length item sets. Next, it scans the transaction database to determine frequent item sets among the candidates.
Apriori, while historically significant, suffers from a number of inefficiencies or trade-offs, which have spawned other algorithms. Candidate generation generates large numbers of subsets (the algorithm attempts to load up the candidate set with as many as possible before each scan). Bottom-up subset exploration (essentially a breadth-first traversal of the subset lattice) finds any maximal subset S only after all $2^{|S|}-1$ of its proper subsets.
The quest to mine frequent patterns appears in many domains. The prototypical application is market basket analysis, i.e., to mine the sets of items that are frequently bought together, at a supermarket by analyzing the customer shopping carts (the so-called “market baskets”). Once we mine the frequent sets, they allow us to extract association rules among the item sets, where we make some statement about how likely are two sets of items to co-occur or to conditionally occur. For example, in the weblog scenario frequent sets allow us to extract rules like, “Users who visit the sets of pages main, laptops and rebates also visit the pages shopping-cart and checkout”, indicating, perhaps, that the special rebate offer is resulting in more laptop sales. In the case of market baskets, we can find rules like, “Customers who buy Milk and Cereal also tend to buy Bananas”, which may prompt a grocery store to co-locate bananas in the cereal aisle.

## Algorithm

The following is a formal statement of the problem: Let τ$=\{i_{1},i_{2},...,i_{m}\}$ be a set of literals, called items. Let $D$ be a set of transactions, where each transaction $T$ is a set of items such that $T$ ⊆ τ. Associated with each transaction is a unique identifier, called its $TID$. We say that a transaction $T$ contains $X$, a set of some items in τ, if $X$ ⊆ $T$. An association rule is an implication of the form $X$ ⇒ $Y$ , where $X$ ⊂ τ, $Y$ ⊂ τ, and $X$ ∩ $Y$ = ∅. The rule $X$ ⇒ $Y$ holds in the transaction set $D$ with confidence $c$ if $c$% of transactions in $D$ that contain $X$ also contain $Y$ . The rule $X$ ⇒ $Y$ has support $s$ in the transaction set $D$ if $s$% of transactions in $D$ contain $X$ ∪ $Y$. Given a set of transactions $D$, the problem of mining association rules is to generate all association rules that have support and confidence greater than the user-specified minimum support (called minsup) and minimum confidence (called minconf) respectively.
The problem is usually decomposed into two subproblems. One is to find those itemsets whose occurrences exceed a predefined threshold in the database; those itemsets are called frequent or large itemsets. The second problem is to generate association rules from those large itemsets with the constraints of minimal confidence. Suppose one of the large itemsets is Lk, Lk = {I1, I2, … , Ik}, association rules with this itemsets are generated in the following way: the first rule is {I1, I2, … , Ik-1}⇒ {Ik}, by checking the confidence this rule can be determined as interesting or not. Then other rule are generated by deleting the last items in the antecedent and inserting it to the consequent, further the confidences of the new rules are checked to determine the interestingness of them. Those processes iterated until the antecedent becomes empty. Since the second subproblem is quite straight forward, most of the researches focus on the first subproblem. The Apriori algorithm finds the frequent sets $L$ In Database $D$.
Let $X$, $Y$ ⊆ I be any two itemsets. Observe that if $X$ ⊆ $Y$ , then sup(X) ≥ sup(Y ), which leads to the following two corollaries:
* If X is frequent, then any subset Y ⊆ X is also frequent.
* If X is not frequent, then any superset Y ⊇ X cannot be frequent.
Based on the above observations, we can significantly improve the itemset mining algorithm by reducing the number of candidates we generate, by limiting the candidates to be only those that will potentially be frequent. First we can stop generating supersets of a candidate once we determine that it is infrequent, since no superset of an infrequent itemset can be frequent. Second, we can avoid any candidate that has an infrequent subset. These two observations can result in significant pruning of the search space.
* Find frequent set $L_{k-1}$.
* Join Step.
** $C_{k}$ is generated by joining $L_{k-1}$with itself
* Prune Step.
** Any $(k-1)$ -itemset that is not frequent cannot be a subset of a frequent $k$ -itemset, hence should be removed.
where
* ($C_{k}$: Candidate itemset of size $k$)
* ($L_{k}$: frequent itemset of size $k$)

### Apriori Pseudocode

Apriori $(T,\varepsilon )$
    $L_{1}\gets \{$ large 1-itemsets that appear in more than $\varepsilon$ transactions $\$
    $k\gets 2$
       while $L_{k-1}\neq \varnothing$
          $C_{k}\gets$Generate$(L_{k-1})$
          for transactions $t\in T$
             $C_{t}\gets$Subset$(C_{k},t)$
             for candidates $c\in C_{t}$
                $\mathrm {count} [c]\gets \mathrm {count} [c]+1$
          $L_{k}\gets \{c\in C_{k}|~\mathrm {count} [c]\geq \varepsilon \}$
          $k\gets k+1$
    return $\bigcup _{k}L_{k}$

### Implementation

The R package that implements association rule mining is called arules, and it can be found at http://cran.r-project.org/web/packages/arules/index.html (Details how to install R can be found here http://cran.r-project.org/bin/linux/ubuntu). In package arules we interface free reference implementations of Apriori and Eclat by Christian Borgelt (Borgelt and Kruse, 2002; Borgelt, 2003)3. The code is called directly from R by the functions apriori and éclat and the data objects are directly passed from R to the C code and back without writing to external files. The implementations can mine frequent itemsets, and closed and maximal frequent itemsets. In addition, apriori can also mine association rules.
Installation of the dependencies packages can be performed within the R environment using the function "install.packages(“package name”)". The name of the package in question is “arules”. To use this package you need R environment with version 2.7.0 at least (details how to update R can be found in http://cran.r-project.org/bin/linux/ubuntu).
After the user installed the necessary packages, they must load them. This can be done using the function "library (package name)".

### Visualization
#### Reading the data

Transactions can be read from files in the basket format, with the command read.transactions. The parameters for read.transactions are:
file
format read.transactions can get data structured in multiple formats, one of them being basket.
separator(sep)
One example of its use would be:
The object ”tr” is used to store the transactions read from the file named ”teste”, where each item is separated by a ”,”. ”teste” could be, for example:
One way to visualize the data is inspect(object). For example:
Additionally, it is possible visually inspect binary incidence matrices, or plot the frequency of items sets:

#### Rules

The function to mine frequent itemsets, association rules or association hyperedges, using the Apriori algorithm, takes 2 parameters:
Data: the object that contains the data
parameter: a multi-dimensional parameter to set up support and confidence
For example, using the dataset gathered in the previous section:
The rules can be visualized with the command inspect:
To get a summary of the rules' characteristics, the function ”summary” can be used:
Other quality measures of the rules can be displayed with:
To calculate a single measure and add it to the quality slot:
Finally, to send the output to a file use:

## Case study

We now present a brief case study to illustrate the use of apriori and the package arules in a real data set.

### Scenario

Spam is the abuse of electronic messaging systems (including most broadcast media, digital delivery systems) to send unsolicited bulk messages indiscriminately. Many filters are designed to stop spam in its tracks, but such filters are often left behind by the spammers' obfuscating techniques. One of such filters is SpamAssassin, a well known filter that relies on machine learning and fixed rules for filtering. SpamAssassin, however, doesn't consider the possible relations between its rules.

#### Input Data

22406 spams were used in this case study, ranging from 1998 to 2009, collected from the public spam corpus SpamArchive (http://untroubled.org/spam/). Each spam was analyzed by SpamAssassin, and the rules found were analyzed, as well its year. For example, a particular spam would be: YEAR=1998 INVALID_DATE INVALID_TZ_EST meaning this was a spam from 1998 in which SpamAssassin accused two rules: INVALID_DATE and INVALID_TZ_EST.

#### Implementation

The output from each spam filtered through SpamAssassin was saved in a file named output. The following commands were issued:

#### Output Data

We displayed only the itemsets of size 1, for simplicity:

#### Analysis

It takes a critical eye to spot the interesting information. Rules such as YEAR=2009 => HTML_MESSAGE carry information that is not surprising, deeming it uninteresting. However, some interesting patterns can be found:

##### MISSING_DATE => MISSING_MID

    Spammers who don't set up a date usually 'forget' about the message ID as well. Maybe spam assassin could score differently when they are found together.

##### HELO_DYNAMIC_IPADDR => FH_HELO_EQ_D_D_D_D

    When HELO is done using a suspicious hostname, it is usually in the d-d-d-d format. This characterizes a spam more than just one of the two rules separately.

##### SUBJECT_NEEDS_ENCODING => SUBJ_ILLEGAL_CHARS

    Typically this means a spam is in Chinese. These rules obviously have a strong correlation (confidence= 90%).
Many more interesting patterns can be found and studied, in order to improve the quality of the filter. Using apriori with "arules" is an easy and straightforward task.

## References

* [1]http://en.wikipedia.org/wiki/Apriori_algorithm
* [2]http://rss.acs.unt.edu/Rdoc/library/arules/html/apriori.html
* [3]http://untroubled.org/spam/