Modeling - Association Rule Mining (ARM)

How Does Association Rule Mining Work?

Association rule mining is a technique used to find and quantify relationships within sets, specifically the occurrence of events together. A common use and colloquialism for ARM is market basket analysis, where items purchased together by customers are examined. The goal of this specific analysis is to provide an answer to the question “Given a limited number of items at a location, what items are most associated with each other?” In general, does a set or subset imply another set or subset? This is the idea of a rule. This can also be used for other purposes aside from customer-based studies, as this particular analysis will focus on.

Components of ARM

Association Rule Mining is a measure of cooccurence, not causality, and there are several key components to help analyze the findings of cooccurence.

• Support quantifies how often an itemset or rule appears in a dataset (proportion / total probability).
• Confidence quantifies the likelihood an itemset's consequent occurs given its antecent (conditional probability of a consequent occuring given its antecent).
• Lift asseses the performance of an association rule by quantifying an improvement (or degradation) from the inital prediction, where the inital prediction would the support of the antecent.
• Lift less than 1 indicates a negative correlation, or the rules are simply not correlated.
• Lift equal to 1 indicates indepedence between the rules, absolutely no correlation. "Is something is everywhere, it is nowhere". If an item is in every single set, as an antecedent, lift will always be 1.
• Lift greater than 1 indicates a positive correlation, or improvement of the initial rule. In other words, this shows a valid assocation. A high lift value inidcates that the association rule is more significant, the itemsets are highly dependent on each other.



Formulas: Support (single itemset)



\[ Support(I) = \frac{\text{number of sets containing I}}{\text{total number of sets}} \]



Formulas: Support (association rule)



Given an antecedent A and consequent C:
\[ Support(A \rightarrow C) = \frac{\text{number of sets containing A and C}}{\text{total number of sets}} \]



Formulas: Confidence (association rule)



Given an antecedent A and consequent C:
\[ Confidence(A \rightarrow C) = \frac{\text{proportion of sets containing A and C}}{\text{proportion of sets containing A}} \]
\[ Confidence(A \rightarrow C) = P(C|A) = \frac{P(CA)}{P(A)} \]
Note that caution is required when proceeding with the confidence formula. The intersection is not the true/traditional intersection of events, but that it contains every element in itemsets A and C.



Formulas: Lift (association rule)



Given an antecedent A and consequent C:
\[ Lift(C \rightarrow A) = \frac{Confidence(A \rightarrow C)}{Support(C)} \]
\[ Lift(C \rightarrow A) = \frac{Support(A \rightarrow C)}{Support(A) Support(C)} \]




Apriori Algorithm


A prominent algorithm in association rule mining is the apriori algorithm. Some key terminology in understanding the Apriori Algorithm:

• Maximal Itemset: Itemset in which none of its supersets are frequent.
• Closed Itemset: Itemset in which none of its immeidate supersets have the same support count as the itemset, itself.
• k-itemset: Itemset which contains k items
• Apriori Property: All non-empty subsets of frequent itemsets must be frequent. In other words, given a frequent itemset, all non-empty subsets of the frequent itemset are frequent as well.
• Antimonotonicity: If a set cannot pass a test, all its supersets will fail the test as well. If an itemset is infrequent, all its supersets will be infrequent as well. This is essentially the contrapositive of the Apriori Property.
• Maximum Number of Possible Frequent Itemsets
• Total: \( 2^n \)
• Excluding the Empyset: \( 2^n - 1 \)
• This can be problematic due to the factorial growth per element.
• Apriori Pruning Principal: foundation of the Apriori Algorithm, which draws on the above terminology and formulas in the following process:
1. Generate Candidate Itemsets: start with a single item and generate candidate itemsets of length 1.
2. Count Support: scan the dataset to count the support for each candidate itemset.
3. Prune Infrequent Itemsets: eliminate itemsets that do not meet the minimum support threshold.
4. Generate Next-Level Candidates: combine frequent itemsets from the previous step to generate new candidate itemsets of length k+1.
5. Repeat: continue counting support and pruning until no new frequent itemsets can be generated.
• Apriori Based Rule Generation: after the frequent itemsets are found via the pruning process, an additional rule-generating algorithm can be applied with roughly the following process:
1. Generate Frequent Itemsets: Apriori Algorithm identifies itemsets based on specified minimum support.
2. Generate Candidate Rules: for each frequent itemset, generate all possible rules by splitting it into antecedent and consequent parts.
3. Calculate Metrics: for each candidate rule, calculate metrics like support, confidence, and lift.
4. Prune Rules: retain rules which meet a minimum threshold metric (usually confidence).

Using an example of a small dataset containing movie watchlists, the Apriori Pruning Principal and Apriori Based Rule Generation can be illustrated.

Applying Association Rule Mining

This analysis will focus on finding associations between categories returned by the Google Places API. The API itself returns a list of categories associated with each business.
The categories themselves will be analyzed, however, a few labels can be applied to the transaction type data as well to help identify associations. Namely,

• Call Category: The actual call to the API of the business category requested.
• Country: Associated country with the business place within a ski resort radius.
• Pass: Associated ski pass with the business place within a ski resort radius.
• Region: Associated region with the business place within a ski resort radius..

Call Category will be of most interest, as this could provide insights of the Google Places API efficacy. The other labels could produce interesting relationships themselves, revealing associations seemingly not relevant during the initialization of the project.

A script for the detailed functions required for preparing data, applying apriori, and illustrating the results with a network can be found here. The application process script can be found here.

Data Preparation

Preparing data for this type of analysis consists of creating the initial transaction-type data, and then allowing for expansion into labels.
The general preparation process:

1. Obtain the initial dataset with the transaction type data.
2. Clean the initial dataset (namely steps that were previously applied to the main Google dataset):
• Drop Duplicates
• Use ast.literal_eval() to Ensure List Type.
• Create Keys to Merge back with the Google Data for Label Expansion.
• Merge back with the Google dataset.

Initial Dataset with Transaction Type Data

The initial dataset containing a column with list values required for the transaction data. Several cleaning steps mentioned above will prepare this data for merging in with the cleaned google places data.

Google Places Full Data

The cleaned final google places data used across this project. Will be merged into.

Google Merged Data

The ARM-ready dataset. The main transaction data exists in one of the columns while the labels exist for use in expansion functions available in the functions script.

Transaction-Type Data Isolated

A snippet of the transaction-type data isolated.

Results

Using just the main transaction type data (i.e. no labels included), the Apriori Algorithm was ran to find frequent itemsets and then an Apriori Rule Based Algorithm was ran to find association rules.

Given that this was a large dataset, to capture as many frequent itemsets and association rules as possible, a low support threshold was used for the inital alogrithm and a low confidence threshold was used for the secondary algorithm. The final association rules can always be reduced via filtering on different thresholds if required. The dataset being rather large is relevant to support since this is an initial measure on proportion in relation to the entire dataset. Rarer occurences would be pruned if not.

• Support Theshold: 0.01
• Confidence Threshold: 0.01

In reference to creating rules with low thresholds, the rules can now be sorted to examine important findings by metric.

• Top 15 Rules for Support
• Top 15 Rules for Support with Lift Greater Than 1: A lift value greater than 1 indicates a positive correlation. The association rule is more significant, thus the adding this parameter to the results is better indicative of relationships within the data.
• Top 15 Rules for Confidence
• Top 15 Rules for Confidence with Lift Greater Than 1: A lift value greater than 1 indicates a positive correlation. The association rule is more significant, thus the adding this parameter to the results is better indicative of relationships within the data.
• Top 15 Rules for Lift

The top rules without applying the lift parameter show that Establishment and Point of Interest are very common, if not in every rule. Therefore, by applying the lift parameter of greater than 1, rules begin to show associations with more signficant results. In fact, when sorted by descending lift values itself, these illustrate some of the most significant associations.

To further illustrate these associations, networks visualizations were created. Note that these networks are interactive and contain hover information.

Label Expansion - Call Categories

Associations between the returned categories do reveal interesting assocations in there own right. However, insight can be gained into the efficacy of the Google Places API by appending the call category label to the datasets. In other words, when the API was called with a specific business category in mind, what actually was returned?

For this process, the label was appended to the transaction-type data and association rules were made again with the same low thresholds to capture as many associations as possible. Once the rules were created, the antecedents were reduced to only rules with the call category as a single antecedent.

Label Expansion - Call Categories Assocation Rules Snippet (not sorted)

This a snippet of the assocaition rules results from this process (note this is not sorted in any manner):


Additionally, a network illustration with the same interactivity and hover information as with the previous visuals. Note that the call categories were colored differently, and when a return category had an association with multiple call categories, the call category which appeared as the antecedent the majority of the time was responsible for the coloring of the return category node.

As seen with the unlabled networks, Point of Interest and Establishment are central returns for the majority of the categories. However, this also illustrates that there are significant associations between what was called within the API and categories that could be expected as returns.

In other words, this shows that the the Google Places API did perform well in the case of properly returning business types based on a call.